Full Table Scans and High Water Marks

David Clement

September 2004

Oracle versions 7-8

A full table scan begins at the beginning and goes on to the end, and then stops, as the Red King recommended to Alice. The density of the table predicts the efficiency of the scan. If every database block is packed with rows that the query needs to see, then the scan will be efficient, but if it needs to read many empty database blocks for each meaningful row, it will be terribly inefficient.

The metrics in the database that reveal the density of a table are the allocated blocks, the used blocks, the free blocks, and the high water mark.

Allocated blocks are those Oracle has dedicated to storage for the table under consideration. An initial block is always allocated, because there has to be somewhere to save the segment header, at a bare minimum. As Oracle needs to insert data into a table, it will try to use blocks with free space in them; when it can't do that, it will allocate new blocks. The allocation will contain more than one block, so there is normally unused space in each fresh allocation.

The furthest address where data has been inserted, or in other words the largest that the table has ever been, measured in block addresses, is the table's "high water mark" (HWM).

The relationship can be expressed as an equation: high water mark + unused blocks + 1 = allocated blocks. The "1" is for the segment header.

As rows are deleted from a table, or as rows grow to the point that the block they started in is too small and they have to be moved, some space is freed. An actively used table (a "volatile" one in Oracle jargon) may have numerous blocks free.

While Oracle maintains a list of free blocks in the segment header (the "freelist") this does not tell a server process hunting for data that it can afford to ignore certain blocks. The server process executing its full table scan actually has no alternative to reading all blocks up to the high water mark. For a volatile table, this can imply a large amount of unrewarding I/O.

This is why truncating a table can have a surprising effect on performance. On truncation, all the blocks of a table except the one with the segment header in it are released, and the high water mark is reset. So if a table has only been using a few blocks under a very high HWM, full table scans of that table can suddenly become much, much faster.