re: Debunking myths about clustered indexes - part 1 (CIXs worsen bookmark lookups)

Hugo Kornelis — Fri, 03 Nov 2006 22:20:28 GMT

Hi Greg,

You are right that a bookmark lookup through a clustered index requires the traversal of the B-tree for that index. This usually means three page reads for big table and four for HUGE tables.

However, you are NOT right that a bookmark lookup on a heap only takes a single read. That is only true for a completely "fresh" heap, or for a heap where existing rows are never updated. Update activity often causes rows to be moved to a new location. In such a case, a forwarding pointer is left at the original location. On a bookmark lookup, the nonclustered index will point to the original location, where the forwarding pointer will then provide the current location of the row. That means that for a heap, the average number of page reads for a single bookmark lookup will gradually increase from a theoretic minimum of 1 up to a theoretic maximum of 2.

Now before you say that 2 page reads is still less than the 3 to 4 page reads for a bookmark lookup in a clustered index, consider WHICH pages are read. For a heap, each qualifying row from the nonclustered index will point to a page randomly somewhere in the file, and a forwarding pointer will point to yet another random location. Once the table size is sufficiently larger than the available data cache, each logical read will also be a physical read. For a clustered index, 1 of the reads is the data page, the other 2 or 3 are for root and intermediate pages of the B-tree. These pages are accessed all the time, so they'll never be pushed out of the cache; only the data page will require a physical read.

Bottom line: for large tables with some update activity, each bookmark lookup will cost 1 physical read and 2 or 3 reads from cache if the table has a clustered index, or somewhere between 1 and 2 physical reads if it's a heap. Considering the relatively huge performance hit of physical reads, it doesn't take an awful lot of updates before the scale starts to swing back towards the clustered index.

Best, Hugo

Debunking myths about clustered indexes - part 5 - a real world example

Anonymous — Thu, 07 Jun 2007 14:52:03 GMT

This post discusses a problem experienced last year on one of the highest profile&nbsp;websites in...

SQL Server Myths

Anonymous — Wed, 27 Jun 2007 15:26:04 GMT

The whole area of "SQL Server myths" is an interesting one. One of the fascinations of working with SQL...

How earn $ 1000 a week?

AleVaserman — Sun, 07 Mar 2010 16:04:32 GMT

You can make from 3000$-5000$ a Month with this program! $30 for each refferal!
You will earn money from multiple streams: people search engine, ClickBank, HD Publishing, Google AdSense, HostGator, My Life and GDI (Global Domain International).
Visit site: [url=http://bit.ly/aLNyID]acme-people-search.com[/url]