Count Rows in a Heap: Which Scan Does SQL Server Use?

To count rows in a heap, SQL Server scans every page of the table. A clustered index changes the name of the scan. A narrow nonclustered index changes its cost.

Start With a Heap

A heap is a table without a clustered index. Its rows sit in no particular order. The only way to count them from the table itself is to read all of them. The demo creates a database named CountHeapDemo with a table of 60,000 addresses. Run the scripts on a test server.

IF DB_ID(N'CountHeapDemo') IS NULL CREATE DATABASE CountHeapDemo;
GO
USE CountHeapDemo;
GO
DROP TABLE IF EXISTS dbo.HeapAddresses;
CREATE TABLE dbo.HeapAddresses (
    AddressID       int           NOT NULL,
    AddressLine     nvarchar(60)  NOT NULL,
    City            nvarchar(30)  NOT NULL,
    StateProvinceID int           NOT NULL,
    PostalCode      nvarchar(15)  NOT NULL
);
WITH Numbers AS (
    SELECT TOP (60000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS n
    FROM sys.all_objects AS a CROSS JOIN sys.all_objects AS b
)
INSERT INTO dbo.HeapAddresses (AddressID, AddressLine, City, StateProvinceID, PostalCode)
SELECT n, CONCAT(n, N' Maple Street, Suite ', n % 40), CHOOSE(1 + n % 4, N'Portland', N'Austin', N'Denver', N'Boise'),
       n % 50, RIGHT(CONCAT(N'00000', 10000 + n % 90000), 5)
FROM Numbers;

A procedure reports how each count ran. It finds the latest count in the plan cache and reads its plan XML. It returns the scan operator, the index it read, and the logical reads. Logical reads are the pages the query read from memory. The procedure reads the cache and changes no data.

CREATE OR ALTER PROCEDURE dbo.ShowCountScan
AS
BEGIN
    SET NOCOUNT ON;
    SELECT TOP (1) qs.plan_handle, qs.last_logical_reads AS Reads
    INTO #Last
    FROM sys.dm_exec_query_stats AS qs
    CROSS APPLY sys.dm_exec_sql_text(qs.sql_handle) AS st
    WHERE st.text LIKE N'SELECT COUNT(*) AS Step%FROM dbo.Heap%' AND st.text NOT LIKE N'%dm_exec%'
    ORDER BY qs.last_execution_time DESC;
    WITH XMLNAMESPACES (DEFAULT 'http://schemas.microsoft.com/sqlserver/2004/07/showplan')
    SELECT x.value('(//RelOp[contains(@PhysicalOp, "Scan")]/@PhysicalOp)[1]', 'nvarchar(60)') AS ScanOperator,
           x.value('(//RelOp[contains(@PhysicalOp, "Scan")]/*/Object/@Index)[1]', 'nvarchar(128)') AS IndexRead,
           l.Reads
    FROM #Last AS l
    CROSS APPLY sys.dm_exec_query_plan(l.plan_handle) AS q
    CROSS APPLY (SELECT q.query_plan AS x) AS p;
END;

Now run the count on the heap.

SELECT COUNT(*) AS Step1 FROM dbo.HeapAddresses;
GO
EXEC dbo.ShowCountScan;

The plan shows a Table Scan, and there is no index name because a heap has no index. The count read 770 pages. That number is the size of the table.

Add a Clustered Index

The next script builds a clustered index on AddressID. Once a clustered index exists, the table is no longer a heap. The data now lives inside the index, so a table scan is not possible anymore.

CREATE CLUSTERED INDEX CI_HeapAddresses ON dbo.HeapAddresses (AddressID);
GO
SELECT COUNT(*) AS Step2 FROM dbo.HeapAddresses;
GO
EXEC dbo.ShowCountScan;

The scan is now a Clustered Index Scan. It read 782 pages, 12 more than the heap. The rows are the same, and the count still reads all of them. The name changed, and the cost barely did.

Add a Narrow Index

Now add a nonclustered index on StateProvinceID. It holds one small column and a pointer to each row. SQL Server knows every row appears in it, so it can count the rows there.

CREATE NONCLUSTERED INDEX NCI_HeapAddresses_State ON dbo.HeapAddresses (StateProvinceID);
GO
SELECT COUNT(*) AS Step3 FROM dbo.HeapAddresses;
GO
EXEC dbo.ShowCountScan;

The count read 106 pages instead of 782. The scan operator is a plain Index Scan, and the index name shows which one SQL Server picked. The rule is the same as in Index Used for COUNT(*): SQL Server Scans the Narrowest One. The narrowest index that holds every row wins.

Drop the Clustered Index Again

Drop the clustered index, and the table is a heap again. The nonclustered index stays, so you can still count rows in a heap through it.

DROP INDEX CI_HeapAddresses ON dbo.HeapAddresses;
GO
SELECT COUNT(*) AS Step4 FROM dbo.HeapAddresses;
GO
EXEC dbo.ShowCountScan;

The narrow index still answers the count, but it grew from 106 to 136 pages. An index on a heap points to each row with an eight-byte row identifier. An index on a clustered table points with the clustering key, which is four bytes here.

A Heap Does Not Compact Its Pages

Heaps have one more trap. A delete frees space inside each page, but a heap never packs the rows together again. When a delete leaves a few rows on every page, no page becomes empty, so none is given back. A count on such a heap reads as many pages as when the table was full. The script below copies the addresses into a new heap and checks its size with a small procedure.

CREATE OR ALTER PROCEDURE dbo.ShowHeapSize
AS
BEGIN
    SET NOCOUNT ON;
    SELECT ps.used_page_count AS Pages, ps.row_count AS Rows
    FROM sys.dm_db_partition_stats AS ps
    WHERE ps.object_id = OBJECT_ID(N'dbo.HeapCopy') AND ps.index_id = 0;
END;

DROP TABLE IF EXISTS dbo.HeapCopy;
SELECT * INTO dbo.HeapCopy FROM dbo.HeapAddresses;
GO
EXEC dbo.ShowHeapSize;

The heap has 767 pages for 60,000 rows. Now delete nine rows out of ten and count again.

DELETE FROM dbo.HeapCopy WHERE AddressID % 10 <> 0;
GO
EXEC dbo.ShowHeapSize;
GO
SELECT COUNT(*) AS Step5 FROM dbo.HeapCopy;
GO
EXEC dbo.ShowCountScan;

The heap still has 767 pages, now for 6,000 rows. The count read 770 pages to find them. The reads can differ by a few pages from run to run. The delete took nine rows out of every ten, so every page still holds some rows and none was released. The scan reads every one. A rebuild packs the rows and gives the space back.

ALTER TABLE dbo.HeapCopy REBUILD;
GO
EXEC dbo.ShowHeapSize;
GO
SELECT COUNT(*) AS Step6 FROM dbo.HeapCopy;
GO
EXEC dbo.ShowCountScan;

After ALTER TABLE ... REBUILD, the heap has 79 pages, and the same count read 82. If a heap shrinks after a purge, compare its Pages with its Rows. Many pages for few rows is the sign. A rebuild of a heap also rebuilds its nonclustered indexes, so plan it like an index rebuild.

When a Delete Empties Whole Pages

The nine of ten delete left rows on every page. A delete can also empty whole pages. The script below builds two new copies of the addresses. It deletes the first 54,000 rows from each, which empties most pages. The second delete asks for a table lock with TABLOCK. Then one query reads the size of both copies.

DROP TABLE IF EXISTS dbo.HeapEmptied;
DROP TABLE IF EXISTS dbo.HeapEmptiedLocked;
SELECT * INTO dbo.HeapEmptied FROM dbo.HeapAddresses;
SELECT * INTO dbo.HeapEmptiedLocked FROM dbo.HeapAddresses;
GO
DELETE FROM dbo.HeapEmptied WHERE AddressID <= 54000;
DELETE FROM dbo.HeapEmptiedLocked WITH (TABLOCK) WHERE AddressID <= 54000;
GO
SELECT OBJECT_NAME(ps.object_id) AS TableName, ps.used_page_count AS Pages, ps.row_count AS Rows
FROM sys.dm_db_partition_stats AS ps
WHERE ps.object_id IN (OBJECT_ID(N'dbo.HeapEmptied'), OBJECT_ID(N'dbo.HeapEmptiedLocked')) AND ps.index_id = 0
ORDER BY TableName;

Both tables hold 6,000 rows. The delete without a table lock left 155 pages behind, and the delete with TABLOCK left 79. The documentation explains it. A delete on a heap that takes row or page locks can leave emptied pages allocated. No other object can use that space. A count on the first copy shows what that costs.

SELECT COUNT(*) AS Step7 FROM dbo.HeapEmptied;
GO
EXEC dbo.ShowCountScan;

The scan read 158 pages for 6,000 rows. To avoid this, delete with TABLOCK, rebuild the heap after a purge, or give the table a clustered index. The page counts can differ a little from run to run.

When a Heap Is Fine

You could argue that heaps are fine for staging tables, which fill, get read once and empty again. That is fair. Even then, a count on a heap is a full read of the table. Keep such tables small, or add a narrow index when a count must be fast.

For a table that users query every day, a clustered index is the normal choice. It gives the table an order, and it keeps the emptied pages from piling up.

What to Remember

A heap gives a Table Scan. A clustered table gives a Clustered Index Scan. A narrow index gives an Index Scan, and it wins. Read the plan, not the guess.

To count rows in a heap fast, add a narrow index. To keep a heap small, rebuild it after a purge. When you finish with the demo, remove the database.

USE master;
GO
DROP DATABASE CountHeapDemo;

A heap is not a faster table, it is a table with no order and no memory of its size.

Published by Pinal Dave on SQLAuthority. More of my work at pinaldave.com.