CST363 - Week 5

  CST 363 Introduction to Database

If indexes are supposed to speed up performance of query,  what does the author mean by a slow index? 

In the article Slow Indexes, Part I, author Markus Winand points out the effectiveness of rebuilding the index to increase performance. He explains that the use of a self-balanced B-tree prevents the deep growth of a large index. Most of what a rebuild could do is reduce the leaf nodes. Reducing 20% to 30% of leaf nodes does not reduce the depth of an index, which in return helps with only a 0%—2% reduction in a case like INDEX UNIQUE SCAN.

The index depth of millions of records in a B-tree is only four or five. Hence, a  B-tree traversal is very efficient in finding a leaf node. According to the author, tree traverses are believed to be the culprit of slow indexes, but in reality, the leaf node chain leads to slow queries.  

The speed of an index is dependent on the scan operation. To illustrate this, Winand explains the following three different combinations of the tree traversal only and tree traversal with leaf node chain:

•      INDEX UNIQUE SCAN: the lookup operation is limited to finding the unique value. The lookup stops when the unique value is found, making this index the fastest.
•      INDEX RANGE SCAN: the lookup is somewhat ambiguous as performance depends on the count of the matching entries. The smaller the index to read, the faster the performance.
•      TABLE ACCESS BY INDEX ROWID: The additional steps to access the table rows to find a match come at a high cost and are potentially slow if the number of matched entries is high.

The point is that the index's performance depends on how the database uses the index.