Debunking myths about clustered indexes - part 1 (CIXs worsen bookmark lookups)
One of the most widely published indexing "best practises" is that you should create a clustered index (CIX) on every table in your database. For many years, I accepted this as one of the "golden indexing rules" but over the past few years I have become increasingly more uncomfortable with this recommendation as I have worked more extensively in the database performance tuning area. Although I've seen this recommendation made time & again in books, articles, newsgroup posts and presentations, I have never seen a comprehensive explanation for WHY we need CIXs on every table in our dbs.
Curiously, this recommendation survives even though there is a very high profile problem with CIXs - that "Page Splitting" occurs as new rows are inserted or existing rows updated where insufficient space exists on the data storage pages for the newly inserted / updated data.
The page splitting "problem" doesn't really factor heavily into my reasoning though - my concerns are based on a number of other more general query efficiency problems, each of which I will try to cover in up-coming blog entries.
The biggest problem I have observed with CIXs is that they significantly worsen bookmark lookup scenarios, due to the overhead of b-tree traversal for each lookup - a phenomenon that can easily triple the workload of a bookmark lookup.
In case you're not already familiar with a bookmark lookup, it occurs when a query accesses more columns than are available in an index being accessed by the query. For example, if a query selects C2, C3 from Table1 where C1 = x and a Non-Clustered index (NCIX) exists on C1, C2, SQL Server might execute the query by accessing the index for columns C1 & C2, but then lookup C3 in the table's base CIX storage via a bookmark lookup for each row filtered during the query's execution.
Where no CIX exists on the table (a table is generally referred to as a "heap" when it has no CIX), each lookup from the index out to the table to retreive C3 is a single read against the base table's storage for the page that contains the row for which C3 is being looked up. This relatively cheap lookup is possible because the NCIX contains the actual storage address for the row (page number).
Where a CIX does exist on the table, the lookup effort is significantly worsened because NCIXs are implemented differently when the underlying table has a CIX. Instead of having a storage address for the row with each row, the NCIX contains a "logical" CIX key value for each row. To perform the C3 lookup in the tables bas storage in this case, SQL Server uses this key value to then traverse the CIX b-tree structure - a process that might take multiple reads against the database to even locate the row before even being able to read it.
Clearly, it is ideal if the NCIX contains all 3 columns required to efficiently process the query in the first place, but it's also usually not possible to index every column in a database. For the scenarios where bookmark lookups have to be performed due to some columns not being indexed, it is clearly more efficient to NOT have a CIX on a table. When large numbers of rows are involved in queries that perform these lookups, the penaly can often be huge - forcing the amount of reads performed against the database to be far higher where a CIX is involved as opposed to when no CIX is involved.
Hopefully this post has established the bookmark lookup inefficiencies involved with CIXs. To continue this discussion, I'm planning to tackle another related consequence involved with not using CIXs on tables - a phenomenon that only occurs with heaps known as "row forwarding". This argument is often used to promote the widespread use of CIXs but I'll try & put this into perspective in my next post on this topic..