Table and Index Organization - Relational Database Index Design and the Optimizers - page 25

Three levels:
Read one page, get many rows
Read one track, get many pages
Disk server reads ahead from drives to read cache

Level 1 automatic
If 10 rows per 4K page, then I/O time = 1 ms per row
Level 2 support by DBMS or disk system
May reduce sequential I/O time per row to 0.1 ms
Level 3 support by Disk Server
May reduce sequential I/O time per row to 0.01 ms

Figure 2.10 Page adjacency.

10 rows per page and a random I/O takes 10 ms, the I/O time for a sequential
read is then 1 ms per row.
SQL Server allocates space for indexes and tables in chunks of eight 8K
pages. DB2 for z/OS allocates space in extents ; an extent may consist of many
megabytes, all pages of a medium-size index or table often residing in one extent.
The logically adjacent pages are then physically next to each other. In Oracle (and
several other systems) the placement of pages depends on file options chosen.
Many databases are now stored on RAID 5 or RAID 10 disks. RAID5 pro-
vides striping with redundancy . RAID 10, actually RAID 1 + RAID 0, provides
striping with mirroring .
The terms redundancy and mirroring are defined in the glossary. RAID strip-
ing means storing the first stripe of a table or index (e.g., 32K) on drive 1, the
second stripe on drive 2, and so on. This obviously balances the load on a set
of drives, but how does it affect sequential performance? Surprisingly, the effect
may be positive.
Let us consider a full table scan where the table pages are striped over seven
drives. The disk server may now read ahead from seven drives in parallel .When
the DBMS asks for the next set of pages, they are likely to be already in the read
cache of the disk server. This combination of prefetch activity may bring the I/O
time down to 0.1 ms per 4K page (level 3 in Fig. 2.10). The 0.1-ms figure is
achievable with fast channels and a disk server that is able to detect that a file is
being processed sequentially.

Alternatives to B-tree Indexes

BitmapIndexes

Bitmap indexes consist of a bitmap (bit vector) for each distinct column value.
Each bitmap has one bit for every row in the table. The bit is on if the related
row has the value represented by the bitmap.
Bitmap indexes make it feasible to perform queries with complex and unpre-
dictable compound predicates against a large table. This is because ANDing and