{"id":4640,"date":"2016-09-22T13:32:41","date_gmt":"2016-09-22T20:32:41","guid":{"rendered":"http:\/\/3.209.169.194\/blogs\/paul\/?p=4640"},"modified":"2016-09-22T13:35:37","modified_gmt":"2016-09-22T20:35:37","slug":"when-heap-data-pages-become-linked","status":"publish","type":"post","link":"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/","title":{"rendered":"When heap data pages become linked…"},"content":{"rendered":"

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

Data pages in a heap are NOT linked together, as there’s no ordering in a heap.<\/p>\n

However, there is a special case when the data pages in a heap will become linked together in a doubly-linked list…<\/p>\n

Here’s a script that sets up a heap and fills four data pages:<\/p>\n

\r\nUSE [master];\r\nGO\r\nDROP DATABASE [HeapTest];\r\nGO\r\nCREATE DATABASE [HeapTest];\r\nGO\r\nUSE [HeapTest];\r\nGO\r\n\r\nCREATE TABLE [Test] ([c1] INT IDENTITY, [c2] VARCHAR (4000) DEFAULT REPLICATE ('Paul', 250));\r\nGO\r\n\r\nSET NOCOUNT ON;\r\nGO\r\n\r\nINSERT INTO [Test] DEFAULT VALUES;\r\nGO 28\r\n<\/pre>\n
We can see the pages in the index using the undocumented DMV sys.dm_db_database_page_allocations<\/em> that was added in SQL Server 2012:<\/p>\n
\r\nSELECT\r\n    [allocated_page_file_id] AS [FileID],\r\n    [allocated_page_page_id] AS [PageID],\r\n    [next_page_file_id] AS [NextFileID],\r\n    [next_page_page_id] AS [NextPageID],\r\n    [previous_page_file_id] AS [PrevFileID],\r\n    [previous_page_page_id] AS [PrevPageID]\r\nFROM\r\n    sys.dm_db_database_page_allocations (\r\n        DB_ID (N'HeapTest'),    -- database ID\r\n        OBJECT_ID (N'Test'),    -- object ID\r\n        0,                      -- index ID\r\n        NULL,                   -- partition ID\r\n        'DETAILED')             -- scanning mode, DETAILED required for my WHERE clause\r\nWHERE [page_type] = 1; -- Just data pages\r\nGO\r\n<\/pre>\n
\r\nFileID PageID      NextFileID NextPageID  PrevFileID PrevPageID\r\n------ ----------- ---------- ----------- ---------- ----------\r\n1      247         NULL       NULL        NULL       NULL\r\n1      289         NULL       NULL        NULL       NULL\r\n1      290         NULL       NULL        NULL       NULL\r\n1      291         NULL       NULL        NULL       NULL\r\n<\/pre>\n
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:<\/p>\n
\r\nALTER TABLE [Test] REBUILD;\r\nGO\r\n<\/pre>\n
And now running the DMV query again, gives:<\/p>\n
\r\nFileID PageID      NextFileID NextPageID  PrevFileID PrevPageID\r\n------ ----------- ---------- ----------- ---------- -----------\r\n1      296         1          297         NULL       NULL\r\n1      297         1          298         1          296\r\n1      298         1          299         1          297\r\n1      299         NULL       NULL        1          298\r\n<\/pre>\n
Now the pages are linked together!<\/p>\n
Note that this is an OFFLINE rebuild, which is the default. What happened is that the offline\u00a0ALTER TABLE … REBUILD<\/em>\u00a0operation\u00a0uses the part of the underlying functionality for an offline\u00a0ALTER INDEX … REBUILD<\/em> operation that builds the leaf level of the index. As that functionality builds\u00a0a doubly-linked list of pages, the newly rebuilt\u00a0heap 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.<\/p>\n
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.<\/p>\n
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:<\/p>\n
\r\nUPDATE [Test] SET c2 = REPLICATE ('Long', 1000) WHERE c1 = 1;\r\nGO\r\n<\/pre>\n
And running the DMV again gives:<\/p>\n
\r\nFileID PageID      NextFileID NextPageID  PrevFileID PrevPageID\r\n------ ----------- ---------- ----------- ---------- -----------\r\n1      288         NULL       NULL        NULL       NULL\r\n1      296         1          297         NULL       NULL\r\n1      297         1          298         1          296\r\n1      298         1          299         1          297\r\n1      299         NULL       NULL        1          298\r\n<\/pre>\n
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.<\/p>\n
Bottom line: there’s usually a special case exception to every ‘rule’ in SQL Server :-)<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":5,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,62],"tags":[],"class_list":["post-4640","post","type-post","status-publish","format-standard","hentry","category-inside-the-storage-engine","category-on-disk-structures"],"yoast_head":"\nWhen heap data pages become linked... - Paul S. Randal<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"When heap data pages become linked... - Paul S. Randal\" \/>\n<meta property=\"og:description\" content=\"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 […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/\" \/>\n<meta property=\"og:site_name\" content=\"Paul S. Randal\" \/>\n<meta property=\"article:published_time\" content=\"2016-09-22T20:32:41+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2016-09-22T20:35:37+00:00\" \/>\n<meta name=\"author\" content=\"Paul Randal\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Paul Randal\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/\",\"url\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/\",\"name\":\"When heap data pages become linked... - Paul S. Randal\",\"isPartOf\":{\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/#website\"},\"datePublished\":\"2016-09-22T20:32:41+00:00\",\"dateModified\":\"2016-09-22T20:35:37+00:00\",\"author\":{\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/#\/schema\/person\/ffcec826c18782e1e0adf173826a7fce\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"When heap data pages become linked…\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/#website\",\"url\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/\",\"name\":\"Paul S. Randal\",\"description\":\"In Recovery...\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/#\/schema\/person\/ffcec826c18782e1e0adf173826a7fce\",\"name\":\"Paul Randal\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/0b6a266bba2f088f2551ef529293001bd73bf026bc1908b9866728c062beeeb6?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/0b6a266bba2f088f2551ef529293001bd73bf026bc1908b9866728c062beeeb6?s=96&d=mm&r=g\",\"caption\":\"Paul Randal\"},\"sameAs\":[\"http:\/\/3.209.169.194\/blogs\/paul\"],\"url\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/author\/paul\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"When heap data pages become linked... - Paul S. Randal","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/","og_locale":"en_US","og_type":"article","og_title":"When heap data pages become linked... - Paul S. Randal","og_description":"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 […]","og_url":"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/","og_site_name":"Paul S. Randal","article_published_time":"2016-09-22T20:32:41+00:00","article_modified_time":"2016-09-22T20:35:37+00:00","author":"Paul Randal","twitter_misc":{"Written by":"Paul Randal","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/","url":"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/","name":"When heap data pages become linked... - Paul S. Randal","isPartOf":{"@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/#website"},"datePublished":"2016-09-22T20:32:41+00:00","dateModified":"2016-09-22T20:35:37+00:00","author":{"@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/#\/schema\/person\/ffcec826c18782e1e0adf173826a7fce"},"breadcrumb":{"@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/when-heap-data-pages-become-linked\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.sqlskills.com\/blogs\/paul\/"},{"@type":"ListItem","position":2,"name":"When heap data pages become linked…"}]},{"@type":"WebSite","@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/#website","url":"https:\/\/www.sqlskills.com\/blogs\/paul\/","name":"Paul S. Randal","description":"In Recovery...","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.sqlskills.com\/blogs\/paul\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/#\/schema\/person\/ffcec826c18782e1e0adf173826a7fce","name":"Paul Randal","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/0b6a266bba2f088f2551ef529293001bd73bf026bc1908b9866728c062beeeb6?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/0b6a266bba2f088f2551ef529293001bd73bf026bc1908b9866728c062beeeb6?s=96&d=mm&r=g","caption":"Paul Randal"},"sameAs":["http:\/\/3.209.169.194\/blogs\/paul"],"url":"https:\/\/www.sqlskills.com\/blogs\/paul\/author\/paul\/"}]}},"_links":{"self":[{"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/posts\/4640","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/comments?post=4640"}],"version-history":[{"count":0,"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/posts\/4640\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/media?parent=4640"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/categories?post=4640"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/tags?post=4640"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}