Indexes and Reorganization - Relational Database Index Design and the Optimizers - page 205

After a split, retrieving any single index row is probably just as fast as
before. In the worst case, a split creates a new level in the index, but that adds
only an insignificant amount of CPU time if nonleaf pages are not read from the
disk drive.
Reading an index slice , however, does get slower . In all our calculations so
far, we have assumed that the chain connecting index rows always points to the
same or the next page, which may be prefetched by the DBMS. This is close
to the truth after the index has been created or reorganized, but each leaf page
split encountered in a slice may add an extra two random touches —one to find
the page to which the index rows have been moved, the second to return to the
original position in the scan. The first random touch is likely to result in a random
read from a disk drive (10 ms).
Let us assume that we need to scan 100,000 index rows. According to the
QUBE, this takes

1 × 10 ms + 100 , 000 × 0 . 01 ms = 1s

When there are 20 index rows per leaf page (and no leaf pages splits), the
DBMS must read 5000 leaf pages. If these pages are adjacent and sequential read
speed is 0.1 ms per page (40 MB/s, page size 4K), the I/O time is

10 ms + 5000 × 0 . 1ms = 510 ms

When 1% of leaf pages have been split, scanning 100,000 index rows is prob-
ably degraded by 50 random I/Os (1% of 5000). Even with such an apparently
small percentage split, the I/O time has doubled:

× + × . =

51 10 ms 5000 0 1ms 1010 ms

The general formula for the index slice scan I/O time after leaf page splits is

(1 + (LPSR × A/B)) × ORIG

Where LPSR leaf page split ratio (number of splits/number of leaf pages)

A = I/O time per random read
B

=

I/O time per sequentially read page
ORIG = I/O time before leaf page splits

=

This formula is based on two assumptions:

1. Sequential I/O time is NLP × B (the random I/O to the first leaf page
is ignored).
2. Random I/O time is LPSR × NLP × A (one random I/O per leaf page
split).

As the ratio A/B increases (which is the current technology trend), the alarm
limit for the leaf page split ratio decreases. When A/B

= 100 (our assumption),

the I/O time doubles as LPSR reaches 1%.