Basic Indexing Methods - Physical Database Design - page 24

= 1.54 sec + .07 sec
= 1.61 seconds.

2.2.1 Composite Index Approach

First we need to find the height ( h ) of the multiple index. Applying Equation 2.1 and 2.2,

5,000 bytes/block >= p × 5 for pointers + ( p - 1) × 35 for index entries

p <= 5,035 / 40 = 125.875, or p = 125
p h > n , where p = 125 and n = 10,000,000 rows
h > log 10,000,000/log 125 = 7/2.097 = 3.34, or h = 4

Number of blocks needed to hold 750 target row pointers
= 750/(5,000 bytes/block/35 bytes/pointer) = 750/142
= 5.28 blocks => 6 blocks.

Query cost
= composite index search + pointer search for target records
+ final data access cost
= h + 6 + 750
= 4 + 6 + 750 block accesses.

Query I/O time
= 754

× ×

2.02 ms + (6 blocks 5,000 bytes/block)/320 MB/sec

= 1.52 seconds.

2.2.2 Table Scan

For a full scan of this table of 10 M rows or 500,000 blocks use the simple model in
Appendix A and apply it to this example. Since most disk systems use prefetch buffers to
speed up table scans, we assume a 64 KB prefetch block here. Thus, the number of I/O
operations is:

Number of prefetch buffer I/O operations
= 10,000,000 rows × 250 bytes/row/64 KB = 38,147.

Query time = time to fill 38,147 prefetch buffers in a table scan
= 38,147 × (2 ms rotational delay + 64 KB/320 MB/sec transfer)

×

= 38,147 (2 ms + .19 ms)

= 83.5 seconds.