Quaere Verum - Clustered Index Scans - Part I

Did it ever happen to you that you believed in something so strongly without ever bothering to verify the truth about it because it seemed so obvious, and one day realized that you were wrong? Well, it happened to me recently…

Before I unveil the details of the case, I’d like to express my deepest gratitude to Lubor Kollar and Srikumar Rangarajan who helped me get to the bottom of things and for explaining the behavior I couldn’t explain myself.
Lubor also gave me great guidance and advice!

Tested on SQL Server versions: 2000 Dev/SP4, 2005 Dev/SP1

I’ll start by asking you a seemingly simple question. Given a table T1 with a clustered index on col1, is the following query guaranteed to return the data in clustered index order?

SELECT * FROM T1;

Try to answer the question to yourself, and also to explain the reasoning behind your answer. Apparently, the answer is far from being simple, and the implications of what really happens are profound.

Bear with me as I go through some crucial fundamentals that you may already be familiar with before I even get to the main points I want to make and before describing the recent findings.

I’d like to stress the ANSI SQL standard’s stand on the matter. As far as the standard is concerned, such a query returns a set, and since a set has no order to its rows, the result is considered valid regardless of the order in which the rows are returned. If you want to guarantee that the result would be returned in a particular order you MUST specify an ORDER BY clause.

The implications in regards to SQL Server are that it can utilize unordered or ordered access methods as it deems fit.

I’d like to make some observations in regards to the common beliefs out there, and disprove some myths.

Clustered index physically organizes the data in order (myth/false assumption)

Some people believe that creating a clustered index on a table causes the data to be physically organized on disk by index key order.

The term “physical” itself is problematic since table/index data resides in pages, which reside in extents, which reside in files. Files are not necessarily contiguous on disk due to file system fragmentation, not to speak of a file being placed on a RAID array, and/or having multiple files in a database. But for the sake of the discussion, I’ll make things simple; I’ll work with a database that has only a single data file placed on a single drive, and ignore file system fragmentation; that is, I’ll assume that the file is a single contiguous unit.

Note that even the records within a page are not necessarily sorted physically. SQL Server organizes the records within the page in a sorted fashion by means of a row-offset array that it maintains at the end of each page.

I’ll demonstrate that the pages at the leaf level of the clustered index are not necessarily organized within the file in the same order as the logical index key order (maintained by the index leaf level’s linked list). To do so, I’ll create a table called T1 with a clustered index on col1; I’ll populate the table with a loop that inserts a row in each iteration, with a random value in col1:

SET NOCOUNT ON;USE master;GOIF DB_ID('testdb') IS NULL  CREATE DATABASE testdb;GOUSE testdb;GOIF OBJECT_ID('dbo.T1', 'U') IS NOT NULL  DROP TABLE dbo.T1;GOCREATE TABLE dbo.T1(  col1   INT NOT NULL,  filler CHAR(2000) NOT NULL DEFAULT('a'));CREATE CLUSTERED INDEX idx_cl_col1 ON dbo.T1(col1);GODECLARE @i AS INT;SET @i = 1;WHILE @i BEGIN  INSERT INTO dbo.T1(col1)    VALUES(1 + ABS(CHECKSUM(NEWID()) % 1000));  SET @i = @i + 1;END

I’m using random values so that the rows will be entered into the clustered index in random order, causing page splits which in turn cause logical fragmentation. Logical fragmentation is expressed as the percentage of out-of-order pages; that is, the discrepancybetween the logical order dictated by the index linked list vs. the
order in which the pages appear in the file.

The premise of the myth that a clustered index physically organizes the data in order is disproved by the fact that logical fragmentation exists; if you think about it, another way to express the myth is that there’s no such thing as logical fragmentation, which is of course wrong.

The following code run in SQL Server 2005 returns the level of logical fragmentation in the clustered index (in SQL Server 2000 use DBCC SHOWCONTIG):

SELECT avg_fragmentation_in_percent FROM sys.dm_db_index_physical_stats(   DB_ID('testdb'),  OBJECT_ID('dbo.T1'),  1,  NULL,  NULL);

I got the result 96.5217391304348, meaning that there are over 96 percents of out-of-order pages. If you need further proof that the pages do not necessarily reside in the file in the same order as in the linked list, use DBCC IND to show the actual pointers between the pages in the linked list:

DBCC IND('testdb', 'dbo.T1', 0);

To save you the trouble in deciphering the output, the following code generates a string with the addresses of the pages in the order in which they appear in the linked list:

CREATE TABLE #DBCCIND(  PageFID INT,  PagePID INT,  IAMFID INT,  IAMPID INT,  ObjectID INT,  IndexID INT,  PartitionNumber INT,  PartitionID BIGINT,  iam_chain_type VARCHAR(100),  PageType INT,  IndexLevel INT,  NextPageFID INT,  NextPagePID INT,  PrevPageFID INT,  PrevPagePID INT);INSERT INTO #DBCCIND  EXEC ('DBCC IND(''testdb'', ''dbo.T1'', 0)');WITH LinkedListAS(  SELECT 1 AS RowNum, PageFID, PagePID  FROM #DBCCIND  WHERE IndexID = 1    AND IndexLevel = 0    AND PrevPageFID = 0    AND PrevPagePID = 0  UNION ALL  SELECT PrevLevel.RowNum + 1,    CurLevel.PageFID, CurLevel.PagePID  FROM LinkedList AS PrevLevel    JOIN #DBCCIND AS CurLevel      ON CurLevel.PrevPageFID = PrevLevel.PageFID      AND CurLevel.PrevPagePID = PrevLevel.PagePID)SELECT  CAST(PageFID AS VARCHAR(MAX)) + ':'  + CAST(PagePID AS VARCHAR(MAX)) + ' ' AS [text()]FROM LinkedListORDER BY RowNumFOR XML PATH('')OPTION (MAXRECURSION 0);DROP TABLE #DBCCIND;

Here’s the output that I got:

1:109 1:1567 1:1531 1:1488 1:1541 1:1508 1:1523 1:1558 1:1529 1:1501 1:1570 1:1536 1:1569 1:1491 1:1525 1:1539 1:1555 1:1486 1:1480 1:1571 1:1526 1:80 1:1527 1:1528 1:1557 1:1502 1:1548 1:1587 1:1510 1:1498 1:1483 1:1568 1:1554 1:1500 1:1519 1:1564 1:1530 1:1489 1:1575 1:1524 1:1562 1:1550 1:41 1:1583 1:1534 1:1549 1:1492 1:1566 1:1540 1:1515 1:1538 1:1551 1:1503 1:1490 1:1504 1:1559 1:174 1:1560 1:1514 1:89 1:1537 1:1563 1:1495 1:1509 1:1580 1:1505 1:1496 1:1542 1:1556 1:1573 1:1512 1:1577 1:1533 1:1485 1:1494 1:1520 1:1521 1:1547 1:1543 1:1516 1:1565 1:1497 1:1552 1:1578 1:1579 1:1581 1:1522 1:110 1:1586 1:1532 1:1507 1:1576 1:1481 1:1518 1:1487 1:1582 1:1506 1:1544 1:1511 1:1572 1:1553 1:77 1:1574 1:1546 1:1585 1:1517 1:1482 1:1493 1:1513 1:1499 1:1561 1:1535 1:1484 1:1584 1:1545

You can clearly see that there are many out of order pages (next page in linked list appears earlier in the file).

Note that when you create or rebuild an index on an existing table, SQL Server will make effort to create it in a contiguous manner (least amount of fragmentation), but there are no guarantees—especially when the SORT_IN_TEMPDB option is not specified or the operation is processed in parallel. When you do specify the SORT_IN_TEMPDB option and the index creation/rebuild is processed with a single thread, this may improve
the continuity of index extents; but again, no guarantees that the operation will end up with an index that has no fragmentation at all.

Here’s a snippet from Books Online that explains this:

“The SORT_IN_TEMPDB option may improve the contiguity of index extents, especially if the CREATE INDEX operation is not being processed in parallel. The sort work area extents are freed on a somewhat random basis with regard to their location in the database. If the sort work areas are contained in the destination filegroup, as the sort work extents are freed, they can be acquired by the requests for extents to hold the index structure as it is built. This can randomize the locations of the index extents to a degree. If the sort extents are held separately in tempdb, the sequence in which they are freed has no affect on the location of the index extents. Also, when the intermediate
sort runs are stored in tempdb instead of the destination filegroup, there is more space available in the destination
filegroup. This increases the chances that index extents will becontiguous.”

Conclusion: having a clustered index on a table does not guarantee that the data is organized within the file by index key order.

Continues in Part II...