Indexes and Sorting Techniques

I'm a devoted reader of Itzik Ben-Gan's T-SQL Black Belt column, but the following passage from "Sorting Techniques" (April 2001) confused me: "Note that the Publishers table is very small. If the table were bigger, the optimizer might choose not to use an index. Using an index involves visiting a page to look up the data row for each key in the index, and the I/O involved might cost more than simply scanning the table and performing an explicit sort. Nevertheless, for this demonstration, the Publishers table's size is convenient." I always thought that, on the contrary, the optimizer would use an index for the large tables and use a row scan for the small ones. Can you clarify?

—Yul Wasserman
[email protected]

Your perception of the way the query optimizer treats small tables versus large tables is generally correct: When a table is very small, the optimizer might decide to simply scan the whole table instead of spending resources trying to find a more complex plan. However, sorting works a bit differently. When you're working with large tables and you want to sort the result by a certain combination of columns, an index defined on the same combination of columns that appear in the ORDER BY clause is efficient in the following two scenarios:

However, when you have a nonclustered index on the same combination of columns that appear in the ORDER BY clause but the index doesn't cover the query, using the index might require considerably more I/O than simply scanning the table. The optimizer has to weigh the cost of scanning fewer pages and sorting the data versus scanning the leaf level of the index in an ordered fashion and looking up the data row for each key. With large tables, a nonclustered index uses significantly more I/O than simply scanning the table and sorting the data. To see the I/O costs for different indexing methods, let's walk through a simple example.

Suppose you have a table, T1, with a million rows and each row requires around 400 bytes of storage. About 20 rows fit in a data page, thus the table requires around 50,000 data pages. And suppose you have a nonclustered index on an integer column called col1. Let's say each index row requires around 20 bytes of storage, so the index's leaf level holds around 2500 pages (about 400 index rows per page). Now consider the following query:

SELECT *FROM T1ORDER BY col1

The I/O cost of a plan that uses the nonclustered index depends on whether the table is a heap (i.e., it doesn't have clustered index) or whether it has a clustered index. If the table is a heap, scanning the leaf level of the nonclustered index in an ordered fashion costs 2,500 logical reads. Then, performing a bookmark lookup using relative identifiers (RIDs) costs one page logical read for each key, or 1 x 1,000,000. This plan costs a total of 1,002,500, logical reads.

If the table has a clustered index on a column other than col1 and that clustered index has three levels, scanning the leaf level of the nonclustered index in an ordered fashion costs 2,500 logical reads. Then, performing a bookmark lookup using clustering keys (i.e., a seek in the clustered index) costs three page logical reads per key, or 3 x 1,000,000. This plan costs a total of 3,002,500 logical reads.

However, the I/O cost of a plan that doesn't use the nonclustered index is 50,000 logical reads for a table scan, plus the cost of sorting the data—much more efficient than plans that use the nonclustered index.

—Itzik Ben-Gan