Additional Estimation Considerations - Relational Database Index Design and the Optimizers - page 284

CPU Time With the worst input, the CPU time with this access path is the
sum of the three components:
At least 0.5 s + 0 . 1s + 0 . 3s = 0 . 9s

Conclusion
Alternative 1 costs 4 ms of CPU time per screen . Alternative 2 costs about 1 s
of CPU time for the maximum result (1000 rows, 50 screens). With small results
(small countries), the CPU time with merge scan approaches 0.6 s (scanning,
sorting, and merging 20,000 INVOICE index rows), while with hash join the
CPU time approaches 0.2 s (scanning 20,000 INVOICE index rows).
The estimated CPU times for alternative 2 are probably acceptable if the
SELECT is not executed very frequently. In extreme cases, two cursors could
be written, one with a MERGE hint (for large countries) and one with a HASH
hint (for small countries). This is a small price to pay for avoiding table denor-
malization.

Merge Scan and Hash Join Comparison

We considered this comparison in Chapter 8, but now that we have discussed the
CPU issues, it would be appropriate to revisit this question.
In a university installation (933 MHz per processor, no concurrent load) a
hash join was measured with the customer and invoice tables we used earlier:
5000 CUST rows were read with random touches via an index (FF CUST 0.5%)
into the hash table in memory; 4,000,000 INVOICE rows were then read using
a full table scan. The reported CPU time was 4.5 s; the CPU time per sequential
touch was therefore less than 1

.

sperrow.
These are the main components of CPU time in this case:
4,000,000 sequential touches to table INVOICE
5000 random touches to table CUST
8000 random touches to the hash table (Invoice FF = 0 . 2%, 0.2% of 4 million
rows = 8000 rows)
For each qualifying INVOICE row, the DBMS must access the hash table
with the hashed CNO value (the join predicate CUST.CNO = INVOICE.CNO).
The size of the hash table is about 5000 × 100 bytes = 0 . 5 MB. As the measure-
ment was made in a stand-alone environment, that area could reside in the CPU
cache for the duration of the INVOICE table scan. In this case, the CPU time per
random touch to the hash table could be much less than 100

1 µ

s. If the random

µ

touches to table CUST take 100 s and the sequential touches to INVOICE take

µ

1 µ s, the CPU time would be
4,000,000 sequential touches to table INVOICE 4 , 000 , 000 × 1 µ s = 4s

5000 random touches to table CUST 5000 × 100 µ s = 0 . 5s

8000 random touches to the hash table 8000 × X µ s = 8X ms

40 FETCHes 40 × 100 µ s = 4ms