Clustered indexes

The last lesson ended with a clustered index on SaleId. Its leaf level holds the whole rows, in key order. That is the defining feature of a clustered index: it does not point to the table, it is the table. Because rows can only be stored in one order, a table can have only one clustered index.

This script rebuilds dbo.Sales, this time with a primary key, so you can start here:

1DROP TABLE IF EXISTS dbo.Sales;2CREATE TABLE dbo.Sales (3    SaleId     int           NOT NULL CONSTRAINT PK_Sales PRIMARY KEY,4    SaleDate   date          NOT NULL,5    CustomerId int           NOT NULL,6    ProductId  int           NOT NULL,7    Quantity   int           NOT NULL,8    Amount     decimal(10,2) NOT NULL,9    Channel    varchar(10)   NOT NULL,10    Notes      char(100)     NULL11);12INSERT INTO dbo.Sales (SaleId, SaleDate, CustomerId, ProductId, Quantity, Amount, Channel)13SELECT value,14       DATEADD(day, value * 37 % 1096, '2022-01-01'),15       value * 7919 % 5000 + 1,16       value % 12 + 1,17       value % 7 + 1,18       value * 31 % 9000 / 100.0 + 1,19       CASE value % 10 WHEN 0 THEN 'Phone' WHEN 1 THEN 'Shop' WHEN 2 THEN 'Shop' ELSE 'Web' END20FROM GENERATE_SERIES(1, 100000);21 22SELECT name, type_desc, is_unique, is_primary_key23FROM sys.indexes24WHERE object_id = OBJECT_ID(N'dbo.Sales');

name      type_desc  is_unique  is_primary_key
--------  ---------  ---------  --------------
PK_Sales  CLUSTERED  1          1

A PRIMARY KEY creates a clustered index unless the table already has one or you write PRIMARY KEY NONCLUSTERED. That is why every BuildMart table is already clustered on its key. Those indexes have names like PK__Products__B40CC6CD…, generated by SQL Server; naming the constraint, as here, gives the index a name you can use in scripts.

Seeks and range scans on the key

1SET STATISTICS IO ON;2SELECT SaleDate, Amount FROM dbo.Sales WHERE SaleId = 777;3 4SELECT COUNT(*) AS SalesRows, SUM(Amount) AS Total5FROM dbo.Sales6WHERE SaleId BETWEEN 10001 AND 12000;7SET STATISTICS IO OFF;

SaleDate    Amount
----------  ------
2022-09-11   61.87

Table 'Sales'. Scan count 0, logical reads 3, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.

SalesRows     Total
---------  --------
     2000  92290.00

Table 'Sales'. Scan count 1, logical reads 40, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.

One row costs one read per level of the tree. 2,000 neighbouring rows cost the trip down plus the leaf pages that hold them, about 2,000 ÷ 56.

ORDER BY on the key is free

The leaf level is already in SaleId order, so SQL Server can return rows in that order just by reading along the chain. Sorting on any other column needs a Sort step. SET SHOWPLAN_TEXT ON shows the plan SQL Server would use instead of running the query; the next lessons look at plans in detail.

1SET SHOWPLAN_TEXT ON;2GO3SELECT TOP (5) SaleId, Amount FROM dbo.Sales ORDER BY SaleId;4SELECT TOP (5) SaleId, Amount FROM dbo.Sales ORDER BY Amount DESC;5GO6SET SHOWPLAN_TEXT OFF;

StmtText
-------------------------------------------------------------
SELECT TOP (5) SaleId, Amount FROM dbo.Sales ORDER BY SaleId;

StmtText
---------------------------------------------------------------------------------------------------
  |--Top(TOP EXPRESSION:((5)))
       |--Clustered Index Scan(OBJECT:([BuildMart].[dbo].[Sales].[PK_Sales]), ORDERED FORWARD)

StmtText
------------------------------------------------------------------
SELECT TOP (5) SaleId, Amount FROM dbo.Sales ORDER BY Amount DESC;

StmtText
----------------------------------------------------------------------------------
  |--Sort(TOP 5, ORDER BY:([BuildMart].[dbo].[Sales].[Amount] DESC))
       |--Clustered Index Scan(OBJECT:([BuildMart].[dbo].[Sales].[PK_Sales]))

The first plan reads the first rows of the index in order (ORDERED FORWARD) and stops after five. The second must read all 100,000 rows to find the five largest amounts, through a Top N Sort (the Sort(TOP 5, …) line), which keeps only the five largest it has seen so far.

Other columns still scan

The tree is sorted by SaleId only. A search on any other column cannot use it to seek:

1SET STATISTICS IO ON;2SELECT COUNT(*) AS SalesRows, SUM(Amount) AS Total3FROM dbo.Sales4WHERE SaleDate = '2023-06-01';5SET STATISTICS IO OFF;

SalesRows    Total
---------  -------
       91  4269.76

Table 'Sales'. Scan count 1, logical reads 1794, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.

Every page is read again. The next lesson adds nonclustered indexes for searches like this; first, the question of which column the clustered index should be on.

Choosing the clustering key

An int or bigint IDENTITY column has all four, which is why it is the usual choice. An email address fails on narrow and static; a random GUID fails on narrow and ever-increasing.

Clustering on something else can still be right when most queries read ranges of it. A reporting table that is almost always read by date can be clustered on the date. Compare a copy of Sales clustered on SaleDate:

1DROP TABLE IF EXISTS dbo.SalesByDate;2SELECT * INTO dbo.SalesByDate FROM dbo.Sales;3CREATE CLUSTERED INDEX CX_SalesByDate ON dbo.SalesByDate (SaleDate);4 5SET STATISTICS IO ON;6SELECT COUNT(*) AS SalesRows, SUM(Amount) AS Total7FROM dbo.SalesByDate8WHERE SaleDate >= '2023-06-01' AND SaleDate < '2023-07-01';9SET STATISTICS IO OFF;10 11SELECT OBJECT_NAME(object_id) AS TableName, page_count,12       avg_record_size_in_bytes AS AvgRowBytes13FROM sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, 'DETAILED')14WHERE object_id IN (OBJECT_ID(N'dbo.Sales'), OBJECT_ID(N'dbo.SalesByDate'))15  AND index_level = 0;

SalesRows      Total
---------  ---------
     2737  125870.80

Table 'SalesByDate'. Scan count 1, logical reads 55, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.

TableName    page_count  AvgRowBytes
-----------  ----------  -----------
Sales              1786        142.4
SalesByDate        1887      149.356

A month of sales now costs a few dozen reads instead of a full scan. The price shows in the second result: SaleDate is not unique (about 91 sales a day), so most rows carry a uniquifier and the rows are a little longer. Writing CREATE UNIQUE CLUSTERED INDEX … (SaleDate, SaleId) avoids the uniquifier and gives the same range seeks.

Page splits

A clustered index keeps its rows in key order, so each new row has one correct page. If that page is full, SQL Server splits it: it allocates a new page, moves about half the rows there and links it into the chain. A split costs extra writes and log records, and it leaves two half-empty pages. The new page is usually far away in the file, so the chain no longer runs in file order: the index is fragmented.

Here is the same effect in SQL Server. Two tables get the same 10,000 keys, inserted one row at a time: one table in ascending order, the other in a scrambled order. Each row has a 400-byte filler so that pages fill up quickly.

1DROP TABLE IF EXISTS dbo.SeqKeys, dbo.RandKeys;2CREATE TABLE dbo.SeqKeys  (Id int NOT NULL CONSTRAINT PK_SeqKeys  PRIMARY KEY, Filler char(400) NOT NULL DEFAULT '');3CREATE TABLE dbo.RandKeys (Id int NOT NULL CONSTRAINT PK_RandKeys PRIMARY KEY, Filler char(400) NOT NULL DEFAULT '');4 5SET NOCOUNT ON;6DECLARE @n int = 1;7BEGIN TRANSACTION;8WHILE @n <= 100009BEGIN10    INSERT INTO dbo.SeqKeys (Id)  VALUES (@n);                 -- 1, 2, 3, …11    INSERT INTO dbo.RandKeys (Id) VALUES (@n * 7919 % 10007);  -- 7919, 5831, 3743, …12    SET @n += 1;13END;14COMMIT;15 16SELECT OBJECT_NAME(object_id) AS TableName, page_count,17       CAST(avg_page_space_used_in_percent AS decimal(5,1)) AS PctFull,18       CAST(avg_fragmentation_in_percent AS decimal(5,1)) AS PctFragmented19FROM sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, 'DETAILED')20WHERE object_id IN (OBJECT_ID(N'dbo.SeqKeys'), OBJECT_ID(N'dbo.RandKeys'))21  AND index_level = 0;

TableName  page_count  PctFull  PctFragmented
---------  ----------  -------  -------------
SeqKeys           527     96.8            0.2
RandKeys          747     68.3           99.1

The ascending keys always landed at the end of the last page, so the pages are packed full and in order. The scrambled keys caused splits all over the index: more pages, each only partly full, and most of them out of order. Every scan of that table reads more pages than it needs to.

Rebuilding an index, and fill factor

ALTER INDEX … REBUILD builds the index again from scratch: pages packed in key order, with no fragmentation. REORGANIZE is a lighter option that shuffles and compacts the leaf pages in place.

1ALTER INDEX PK_RandKeys ON dbo.RandKeys REBUILD;2 3SELECT OBJECT_NAME(object_id) AS TableName, page_count,4       CAST(avg_page_space_used_in_percent AS decimal(5,1)) AS PctFull,5       CAST(avg_fragmentation_in_percent AS decimal(5,1)) AS PctFragmented6FROM sys.dm_db_index_physical_stats(DB_ID(), OBJECT_ID(N'dbo.RandKeys'), NULL, NULL, 'DETAILED')7WHERE index_level = 0;

TableName  page_count  PctFull  PctFragmented
---------  ----------  -------  -------------
RandKeys          527     96.8            0.0

A rebuild can also leave room on each page with FILLFACTOR: ALTER INDEX PK_RandKeys ON dbo.RandKeys REBUILD WITH (FILLFACTOR = 80) fills leaf pages to 80%, so the next random inserts find space without splitting. The cost is 25% more pages for every scan to read. Use it only on indexes that really receive inserts in the middle; an IDENTITY key should stay at 100%.

1DROP TABLE IF EXISTS dbo.SalesByMonth;2SELECT * INTO dbo.SalesByMonth FROM dbo.Sales;3CREATE UNIQUE CLUSTERED INDEX CX_SalesByMonth ON dbo.SalesByMonth (SaleDate, SaleId);4 5SET STATISTICS IO ON;6SELECT COUNT(*) AS SalesRows, SUM(Amount) AS Total7FROM dbo.Sales8WHERE SaleDate >= '2023-03-01' AND SaleDate < '2023-04-01';9 10SELECT COUNT(*) AS SalesRows, SUM(Amount) AS Total11FROM dbo.SalesByMonth12WHERE SaleDate >= '2023-03-01' AND SaleDate < '2023-04-01';13SET STATISTICS IO OFF;14 15DROP TABLE dbo.SalesByMonth;

SalesRows      Total
---------  ---------
     2829  130188.01

Table 'Sales'. Scan count 1, logical reads 1794, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.

SalesRows      Total
---------  ---------
     2829  130188.01

Table 'SalesByMonth'. Scan count 1, logical reads 55, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.