When heap data pages become linked…

The pages at each level of an index are linked together in a doubly-linked list (using the m_nextPage and m_prevPage fields in their page headers) to allow ascending-order and descending-order scans, based on the index key(s).

Data pages in a heap are NOT linked together, as there’s no ordering in a heap.

However, there is a special case when the data pages in a heap will become linked together in a doubly-linked list…

Here’s a script that sets up a heap and fills four data pages:

USE [master];
GO
DROP DATABASE [HeapTest];
GO
CREATE DATABASE [HeapTest];
GO
USE [HeapTest];
GO

CREATE TABLE [Test] ([c1] INT IDENTITY, [c2] VARCHAR (4000) DEFAULT REPLICATE ('Paul', 250));
GO

SET NOCOUNT ON;
GO

INSERT INTO [Test] DEFAULT VALUES;
GO 28

We can see the pages in the index using the undocumented DMV sys.dm_db_database_page_allocations that was added in SQL Server 2012:

SELECT
    [allocated_page_file_id] AS [FileID],
    [allocated_page_page_id] AS [PageID],
    [next_page_file_id] AS [NextFileID],
    [next_page_page_id] AS [NextPageID],
    [previous_page_file_id] AS [PrevFileID],
    [previous_page_page_id] AS [PrevPageID]
FROM
    sys.dm_db_database_page_allocations (
        DB_ID (N'HeapTest'),    -- database ID
        OBJECT_ID (N'Test'),    -- object ID
        0,                      -- index ID
        NULL,                   -- partition ID
        'DETAILED')             -- scanning mode, DETAILED required for my WHERE clause
WHERE [page_type] = 1; -- Just data pages
GO

FileID PageID      NextFileID NextPageID  PrevFileID PrevPageID
------ ----------- ---------- ----------- ---------- ----------
1      247         NULL       NULL        NULL       NULL
1      289         NULL       NULL        NULL       NULL
1      290         NULL       NULL        NULL       NULL
1      291         NULL       NULL        NULL       NULL

Now I’ll rebuild the heap, using functionality that was added in SQL Server 2008 to allow data compression to be enabled for a heap:

ALTER TABLE [Test] REBUILD;
GO

And now running the DMV query again, gives:

FileID PageID      NextFileID NextPageID  PrevFileID PrevPageID
------ ----------- ---------- ----------- ---------- -----------
1      296         1          297         NULL       NULL
1      297         1          298         1          296
1      298         1          299         1          297
1      299         NULL       NULL        1          298

Now the pages are linked together!

Note that this is an OFFLINE rebuild, which is the default. What happened is that the offline ALTER TABLE … REBUILD operation uses the part of the underlying functionality for an offline ALTER INDEX … REBUILD operation that builds the leaf level of the index. As that functionality builds a doubly-linked list of pages, the newly rebuilt heap initially has a doubly-linked list of pages! This doesn’t happen for an ONLINE rebuild of the heap, which uses a totally different mechanism.

Although the pages appear doubly-linked, that’s just an artifact of the mechanism used to build the new heap – the linkages aren’t used or maintained.

To prove it, I’ll update one of the rows to make it longer than there is space on its page, so it’ll be moved to a new page as a forwarded record:

UPDATE [Test] SET c2 = REPLICATE ('Long', 1000) WHERE c1 = 1;
GO

And running the DMV again gives:

FileID PageID      NextFileID NextPageID  PrevFileID PrevPageID
------ ----------- ---------- ----------- ---------- -----------
1      288         NULL       NULL        NULL       NULL
1      296         1          297         NULL       NULL
1      297         1          298         1          296
1      298         1          299         1          297
1      299         NULL       NULL        1          298

The new page, (1:288), was added to the heap but was not linked to any of the pages, and the existing pages were not updated to link to it.

Bottom line: there’s usually a special case exception to every ‘rule’ in SQL Server :-)