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

F = 40%
Average 2 hits per leaf page

30%

1.7% of leaf pages
with more than 5 hits

20%

10%

Figure 11.5 Effect of
random inserts.

0 1 2345 6 7

Now, 1.7% of the leaf pages will be split, and the I/O time for an index slice
scan will become ( 1 + 1 . 7 ) × ORIG = 2 . 7 × ORIG. At this point there will be,
on average, 2 new index rows per leaf page (100,000/50,000), so 40% (2/5) of
the distributed free space will have been used.
It may seem very odd that so many leaf pages have been split (1 . 7% ×
50 , 000 = 850) when only 40% of the free space has been used. Figure 11.5
shows why this will be so, by showing how the new index rows are likely to hit
the leaf pages when the inserts are random.

ž Nearly 15% of the leaf pages will not be hit at all
ž Over 25% will be hit only once
ž

1.2% will be hit 6 times, a split occurring for each leaf page

We will see that the filling factor of the free space (40% above) plays an
important role in LPSR prediction. We will call this value F:
F = percentage of the distributed free space that has been

used at a particular point in time

When Y new rows have been added in Z leaf pages (each of which had free
space for X new rows at reorganization),

F = 100 × Y /( X × Z ) %

In the example above,

F, after 10 days = 100,000 rows /( 5 rows per page × 50,000 pages ) = 40%

The LPSR can be expressed as a function of X and F as shown in Figure 11.6.
This model gives an accurate prediction for leaf page splits when the LPSR
is low; after a lot of leaf page splits, say LPSR

10%, the prediction becomes
pessimistic because of the increase in the number of leaf pages—each split
creates two leaf pages, each having almost 50% free space.

>