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 :-)

6 thoughts on “When heap data pages become linked…

  1. Quite a coincidence as I was very recently looking at page splits and detecting via extended events and while doing so I also observed a heap table with previous and next page pointers. It took some digging to determine what had happened that caused this and it is a different case where a heap table can contains page pointers.

    If a clustered table is changed to a heap by removal of the primary key constraint then the root page for index id 1 is updated to reflect this but the data pages are not so retain the next and previous pointers. Similar to the example you give these pointers are not maintained.

  2. Interesting. Would this effect page level compression since those values would no longer NULL? It would be ironic since that may be the reason you are doing the rebuild.

  3. This doesn’t happen for an ONLINE rebuild of the heap, which uses a totally different mechanism.

    Please elaborate this.

  4. Long Live Paul and sqlskills for sharing immense knowledge to community !!

    We are sincerely very much obliged !!

Leave a Reply

Your email address will not be published. Required fields are marked *

Other articles

Imagine feeling confident enough to handle whatever your database throws at you.

With training and consulting from SQLskills, you’ll be able to solve big problems, elevate your team’s capacity, and take control of your data career.