Databases Reference
In-Depth Information
We use the 4 KB block size and 64 KB prefetch buffer size described in Appendix
A, and we use the block access times derived there from the IBM U320 hard drive: aver-
age seek time is 3.6 ms, average rotational delay is 2 ms, and transfer speed is 320 MB/
sec. We also assume a shared-disk environment and the use of prefetch buffers for all
table scans.
Number of 64 KB prefetch buffers needed to hold the assignedTo table
= ceiling((50,000 rows
×
100 bytes/row)/64 KB)
= ceiling (5,000,000/65,536)
= 77.
Number of 64 KB pre-fetch buffers needed to hold the project table
= ceiling((250 rows
200 bytes/row)/64 KB)
= ceiling (50,000/65,536)
= 1.
×
Nested-loop Case 1:
assignedTo is the outer loop table.
join I/O time = scan assignedTo once, scan project
n
times
= (77 buffers + 50,000 scans
×
×
1 buffer)
5.8 ms
= 290.4 seconds.
Nested-loop Case 2:
Project is the outer loop table.
join I/O time = scan project once, scan assignedTo
m
times
= (1 buffer + 250 scans
×
77 buffers)
×
5.8 ms
×
= 19,251 buffers
5.8 ms
= 111.7 seconds.
In general the smaller table is usually chosen to be the outer table as the more effi-
cient implementation of the query.
The nested-loop strategy can obviously improve its performance by a proper selec-
tion of outer and inner loop tables, but for this example both cases result in a long query
(approximately 112-290 seconds). Note that this strategy does not take advantage of
any row ordering or indexing methodology.
In general, one should avoid joins based on nonkeys. They are likely to produce
very large tables, thus greatly increasing storage and update costs. For example, if two
tables have 100 and 200 rows, respectively, then a join based on the key of either one
results in a maximum of 200 rows, but a join based on a nonkey of either one can
result in a maximum of 100
×
200, or 20,000 rows. Null values are also restricted to
nonkey attributes so that they will not be used inadvertently in join operations.
