Teorey J., Lightstone S., Nadeau T. Database Modeling and Design: Logical Design
Подождите немного. Документ загружается.
estimation of intermediate table size in a query made up of
a series of selections, projections, and joins. Table size is a
critical measure of how long merge joins take, whereas
index definitions help determine how long indexed or hash
joins take to execute.
Tips and Insights for Database
Professionals
• Tip 1. Indexes can greatly improve quer y time and
should be an integral part of a query optimizer.
Automated tools used by Microsoft and IBM integrate
index design with quer y optimization. Some basic esti-
mates for query time for a given query execution plan
can be manually estimated, with or without indexes.
3.7 Literature Summary
Burleson,D.(2005).Physical Database Design Using Oracle. Boca Raton, FL:
Auerbach Publishers.
Date, C. J. (2003). An Introduction to Database Systems (vol. 1, 8th ed.).
Boston: Addison-Wesley.
Elmasri, R., & Navathe, S. B. (2010). Fundamentals of Database Systems
(6th ed.). Boston and Redwood City, CA: Addison-Wesley.
Garcia-Molina, H., Ullman, J., & Widom, J. (2008). Database Systems: The
Complete Book (2nd ed.). Englewood Cliffs, NJ: Prentice-Hall.
O’Neil, P., & O’Neil, E. (2001). Database: Principles, Programming, and
Performance (2nd ed.). San Francisco: Morgan Kaufmann.
Ozsu, M. T., & Valduriez, P. (1991). Principles of Distributed Database
Systems. Englewood Cliffs, NJ: Prentice-Hall.
Roussopoulos, N. (1982). View Indexing in Relational Databases. ACM
Transactions Database Systems, 7(2), 258–290.
Ramakrishnan, R., & Gehrke, J. (2004). Database Management Systems
(3rd ed.). New York: McGraw-Hill.
Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A., &
Price, T. G. (1979). Access Path Selection in a Relational Database
Management System. In ACM SIGMOD Conference (pp. 23–34).
Silberschatz, A., Korth, H. F., & Sudarshan, S. (2010). Database System
Concepts (6th ed.). New York: McGraw-Hill.
24 Chapter 3 QUERY OPTIMIZATION AND PLAN SELECTION
A
A SIMPLE PERFORMANCE
MODEL FOR DATABASES
Performance is your reality. Forget everything else.
—Harold Geneen
This appendix presents a simple performance cost
model for evaluating physical design methods and tradeoffs
among various designs. The model includes estimations for
input/output (I/O) time and network delays.
A.1 I/O Time Cost—Individual
Block Access
A block (or page) has been traditionally the basic unit of
I/O from disk to fast memory (RAM). It can range in size from
2 to 16 KB, although 4,096 bytes (4 KB) is the most typical size
in many systems. Blocks usually include many rows in a
table, but occasionally a large row can span several blocks.
In recent years, prefetch buffers have been used more often
in operational systems to increase I/O efficiency. Prefetch
buffers are typically 64 KB (in DB2, for instance). In some
systems the disk track is the I/O transfer size of choice.
Block access cost
¼ disk access time to a block from a random
starting location
¼ average disk seek time þ average rotational
delay þ block transfer:
A.1
1
Disk access time is becoming much faster with new
technologies, and currently we can estimate the access
time to a 4 KB block to be well below 10 ms in a shared-
disk environment. For example, an IBM U320 146 GB hard
drive has an average seek time of 3.6 ms, average rotational
delay of 2 ms for a half rotation (at 15,000 RPM), and a
transfer rate of 320 MB/sec. For this disk, the expected
block access cost in a shared-disk environment is:
I=O timeð 4 KB block access in a shared diskÞ
¼ 3:6msþ 2msþ 4KB=320 MB=sec ¼ 5:6ms:
I=O timeð64 KB prefetch buffer in a shared diskÞ
¼ 3:6msþ 2msþ 64 KB=320 MB=sec ¼ 5:8ms:
In a dedicated disk environment, the disk-seek compo-
nent is rarely needed, so the time is considered negligible.
I=O timeð 4 KB block access in a dedicated diskÞ
¼ 2msþ 4KB=320 MB=sec ¼ 2:0ms:
I=O timeð 64 KB prefetch buffer access in a dedicated diskÞ
¼ 2msþ 64 KB=320 MB=sec ¼ 2:2ms:
A.2 I/O Time Cost—Table Scans
and Sorts
Disk technologies that create higher speeds plus special
prefetching hardware can also make table scans and
sorting operations extremely efficient. The total I/O time for
a full table scan is computed simply as the I/O time for a
single block or prefetch buffer, whichever applies, times
the total number of those I/O transfers in the table.
Sorting, which is a part of many queries, especially those
needing a sort-merge join, has progressed well beyond
the simple two-way sorts of the past. The estimated cost of
an M-way sort is approximately 2 nb log
M
nb, where
nb is the number of blocks in the table to be transferred to
memory from disk (O’Neil, 2001; Silberschatz, 2006). In the
examples in this
book, we use M ¼ 3 to represent three-
way sorts.
2 Appendix A A SIMPLE PERFORMANCE MODEL FOR DATABASES
A.3 Network Time Delays
Network delays can be significant compared to I/O
delays, and when data is accessed across a network, the
following model can be used, which is very similar to
the disk I/O model.
Network delay ¼ propagation time þ transmission time,
A.2
where
Propagation time ¼ network distance=propagation speed,
A.3
and
Transmission time ¼ packet size=network
transmission rate:
A.4
The propagation speed is estimated to be 200,000 km/sec,
which is approximately two-thirds of the speed of light,
taking into account normal degradations of transmission
media from the theoretical speed of light of approximately
300,000 km/sec. The network distance is given in kilometers
(km). If the network media you are using has a known
propagation delay, then substitute the known value for
200 km/ms in the equation. Rough approximations are
considered reasonable here to get “ballpark” estimates of
total time.
The transmission time for a packet on a network is the
time to get the packet on or off the network to or from the
controlling device in the local computer system. It is analo-
gous to the transfer time for a block on a disk. The trans-
mission rate is given in bits/second and packet size is given
in bytes. We assume an 8-bit per byte conversion factor.
For example, the time to send one packet of 1,500 bytes
(let’s say its one block of data) over an Ethernet with a
transmission rate of 1 Gb/sec in a wide area network
(WAN) at a network distance of 1,000 kilometers would be:
Network time ¼ 1, 000 km =200, 000 km=sec þ 1, 500 bytes
8 bits=byte=1Gb=sec
¼ :005 sec þ :000012 sec
¼ :005012 secðor 5:012 msÞ:
Appendix A A SIMPLE PERFORMANCE MODEL FOR DATABASES 3
For a local area network (LAN) with a network distance of
.1 km, we get:
Network time ¼ :1km=200, 000 km=sec þ 1, 500 bytes
8 bits=byte=1Gb=sec
¼ :0000005 sec þ :000012 sec
¼ :0000125 secðor :0125 msÞ:
Putting these numbers in perspective, higher-speed
Ethernet networks have very small transmission times,
and for longer distances of WANs, the total network time
is dominated by the propagation time. In this case, the typ-
ical values for network time (that is, the propagation time)
are in the same range as disk I/O times, and need to be
considered in the estimate of total response time.
For LANs where network distances may be less than .1
km, the dominating delay is transmission time, but neither
time in this example is significant compared to typical disk
I/O times. Thus, in LANs we can consider network delays
to be negligible unless there are extremely large packets
or trains of packets.
A.4 CPU Time Delays
CPU time delays are mainly dependent on the processing
required by the database application, and are largely inde-
pendent of the I/O operations. Those CPU delays caused
by the software to manage the I/O are usually negligible
compared to the I/O times, and are even further diminished
when they overlap the I/O operations. Our model assumes
database systems to be I/O-bound and considers CPU
delays as negligible.
References
O’Neil, P., & O’Neil, E. (2001). Database Principles, Programming, and
Performance (2nd ed.). San Francisco, CA: Morgan Kaufmann
Publishers.
Silberschatz, A., Korth, H., & Sudarshan, S. (2010). Database System
Concepts (6th ed.). Boston, MA: McGraw-Hill.
4 Appendix A A SIMPLE PERFORMANCE MODEL FOR DATABASES