{"id":945,"date":"2009-03-01T10:42:00","date_gmt":"2009-03-01T10:42:00","guid":{"rendered":"\/blogs\/paul\/post\/Search-Engine-QA-27-How-does-the-storage-engine-find-variable-length-columns.aspx"},"modified":"2009-03-01T10:42:00","modified_gmt":"2009-03-01T10:42:00","slug":"search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns","status":"publish","type":"post","link":"https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/","title":{"rendered":"Search Engine Q&A #27: How does the storage engine find variable-length columns?"},"content":{"rendered":"

<\/p>\n

\nThis question came up in a class I was teaching a few weeks ago: given that the variable-length column offset array in a record only stores offsets, how does the storage engine find a particular variable-length column? <\/em>\n<\/p>\n

\nThe question comes because there's nothing in the record to say which variable-length column is which – so how does it work? The answer is a combination of the null bitmap in the record, plus the metadata for the table\/index stored in the system tables. All variable-length columns have a fixed 'location' within the variable-length portion of the record when they are non-null. Let's see what I mean.\n<\/p>\n

\nFirst off I'll create a test table with a single record, with all variable-length columns null, and dump out the record using DBCC PAGE<\/font>:\n<\/p>\n

<\/p>\n

\n

\n\tCREATE TABLE<\/font> vartest (<\/font>c1 INT<\/font>, <\/font>c2 VARCHAR <\/font>(<\/font>100), <\/font>c3 VARCHAR <\/font>(<\/font>100), <\/font>c4 varchar <\/font>(<\/font>100));<\/font>
\n\tGO
\n\tINSERT INTO<\/font> vartest VALUES <\/font>(<\/font>1, NULL, NULL, NULL);<\/font>
\n\tGO\n\t<\/p>\n

\n\tDBCC<\/font> TRACEON (<\/font>3604);<\/font>
\n\tDBCC<\/font> PAGE (<\/font>test,<\/font> 1,<\/font> 152,<\/font> 1);<\/font>
\n\tGO\n\t<\/p>\n

\n\tSlot 0, Offset 0x60, Length 11, DumpStyle BYTE
\n\tRecord Type = PRIMARY_RECORD Record Attributes = NULL_BITMAP
\n\tMemory Dump @0x66F4C060\n\t<\/p>\n

\n\t00000000: 10000800 01000000 0400fe<\/u><\/strong>†††††††††††††………..\n\t<\/p>\n<\/blockquote>\n

<\/font><\/p>\n

\nThe 0x0400fe<\/font> in bold-underlined is the null bitmap. The 0x0400<\/font> reverses to 0x0004<\/font> – which is the count of columns in the record. The 0xfe<\/font> is the actual bitmap, which is 11111110<\/font> in binary. So all columns in the record except the first are null (although the null bitmap only needs to store bits for 4 columns, all bits in the null bitmap that aren't used are set to indicate a null). You can also see that there's no variable-length column offset array as *all* the variable-length columns are null.\n<\/p>\n

\nNow I'll make the middle variable-length column non-null and dump out the record using DBCC PAGE<\/font>:\n<\/p>\n

<\/p>\n

\n

\n\tUPDATE<\/font> vartest SET<\/font> c3 = <\/font>'c3c3c3c3'<\/font>;<\/font>
\n\tGO
\n\tDBCC<\/font> PAGE (<\/font>test,<\/font> 1,<\/font> 152,<\/font> 1);<\/font>
\n\tGO\n\t<\/p>\n

\n\tSlot 0, Offset 0x60, Length 25, DumpStyle BYTE
\n\tRecord Type = PRIMARY_RECORD Record Attributes = NULL_BITMAP VARIABLE_COLUMNS
\n\tMemory Dump @0x67FEC060\n\t<\/p>\n

\n\t00000000: 30000800 01000000 0400fa<\/u>02 00110019<\/strong> †0……………
\n\t00000010: 00<\/strong>633363 33633363 33†††††††††††††††††.c3c3c3c3\n\t<\/p>\n<\/blockquote>\n

<\/font><\/p>\n

\nWe can see the null bitmap (bold-underlined) has changed to 0xfa<\/font> in hex, or 11111010<\/font> in binary, to reflect that the first and third columns are non-null. As soon as a single variable-length column in the record is non-null, the variable-length column offset array is populated for all variable-length columns up to and including the last non-null column. The array has the count of entries in the array (the 0200<\/font>, which reverses to 0x0002<\/font>), and then for each column it stores the offset to the start of the following column, to avoid storing the length too. The difference between successive start-of-column offsets is the length, with the first length calculated using the end of the array itself as the starting point of the first column. In the record above, the array has two entries, ending at offsets 0x0011-1<\/font> and 0x0019-1<\/font> in the record. The array itself finishes at 0x0010<\/font>, so the first entry in the array is essentially pointing at an empty value, which we know to be actually a null value (instead of a non-null empty value) using the null bitmap.\n<\/p>\n

\nNow if I make the first variable-length column non-null, watch what happens to the record:\n<\/p>\n

<\/p>\n

\n\tUPDATE<\/font> vartest SET<\/font> c2 = <\/font>'c2c2c2c2'<\/font>;<\/font>
\n\tDBCC<\/font> PAGE (<\/font>test,<\/font> 1,<\/font> 152,<\/font> 1);<\/font>
\n\tGO<\/p>\n

\n\tSlot 0, Offset 0x60, Length 33, DumpStyle BYTE
\n\tRecord Type = PRIMARY_RECORD Record Attributes = NULL_BITMAP VARIABLE_COLUMNS
\n\tMemory Dump @0x6714C060\n\t<\/p>\n

\n\t00000000: 30000800 01000000 0400f8<\/u>02 00190021<\/strong> †0…………..!
\n\t00000010: 00<\/strong>633263 32633263 32633363 33633363 †.c2c2c2c2c3c3c3c
\n\t00000020: 33†††††††††††††††††††††††††††††††††††3\n\t<\/p>\n<\/blockquote>\n

<\/font><\/p>\n

\nThe null bitmap has changed from 0xfa to 0xf8 to reflect the newly non-null column. The variable-length portion is re-ordered so that the newly non-null column is in its correct place (you can see the c2c2c2c2c2<\/font> comes before the c3c3c3c3<\/font> in the hex dump of the record) and the offsets have been updated accordingly. The array still only hold two values though. Now if I set the last column to be non-null:\n<\/p>\n

<\/p>\n

\n\tUPDATE<\/font> vartest SET<\/font> c4 = <\/font>'c4c4c4c4'<\/font>;<\/font>
\n\tDBCC<\/font> PAGE (<\/font>test,<\/font> 1,<\/font> 152,<\/font> 1);<\/font>
\n\tGO<\/p>\n

\n\tSlot 0, Offset 0x81, Length 43, DumpStyle BYTE
\n\tRecord Type = PRIMARY_RECORD Record Attributes = NULL_BITMAP VARIABLE_COLUMNS
\n\tMemory Dump @0x66FCC081\n\t<\/p>\n

\n\t00000000: 30000800 01000000 0400f0<\/u>03 001b0023<\/strong> †0…………..#
\n\t00000010: 002b00<\/strong>63 32633263 32633263 33633363 †.+.c2c2c2c2c3c3c
\n\t00000020: 33633363 34633463 346334†††††††††††††3c3c4c4c4c4\n\t<\/p>\n<\/blockquote>\n

<\/font><\/p>\n

\nThe null bitmap now indicates all 4 columns are non-null. The count of columns in the variable-length column offset array has increased to 3 and the new entry is added on the end, as it is the last variable-length column.\n<\/p>\n

\nYou can conceptually think of the algorithm to obtain a variable-length column value as merging the relevant parts of the null bitmap with the variable-length column offset array, and then returning the value if it's non-null.\n<\/p>\n

\nHope this explains things!\n<\/p>\n

<\/font><\/p>\n","protected":false},"excerpt":{"rendered":"

This question came up in a class I was teaching a few weeks ago: given that the variable-length column offset array in a record only stores offsets, how does the storage engine find a particular variable-length column? The question comes because there's nothing in the record to say which variable-length column is which – so […]<\/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,78],"tags":[],"class_list":["post-945","post","type-post","status-publish","format-standard","hentry","category-inside-the-storage-engine","category-on-disk-structures","category-search-engine-q-and-a"],"yoast_head":"\nSearch Engine Q&A #27: How does the storage engine find variable-length columns? - 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\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Search Engine Q&A #27: How does the storage engine find variable-length columns? - Paul S. Randal\" \/>\n<meta property=\"og:description\" content=\"This question came up in a class I was teaching a few weeks ago: given that the variable-length column offset array in a record only stores offsets, how does the storage engine find a particular variable-length column? The question comes because there's nothing in the record to say which variable-length column is which – so […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/\" \/>\n<meta property=\"og:site_name\" content=\"Paul S. Randal\" \/>\n<meta property=\"article:published_time\" content=\"2009-03-01T10:42:00+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=\"4 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\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/\",\"url\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/\",\"name\":\"Search Engine Q&A #27: How does the storage engine find variable-length columns? - Paul S. Randal\",\"isPartOf\":{\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/#website\"},\"datePublished\":\"2009-03-01T10:42:00+00:00\",\"author\":{\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/#\/schema\/person\/ffcec826c18782e1e0adf173826a7fce\"},\"breadcrumb\":{\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.sqlskills.com\/blogs\/paul\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Search Engine Q&A #27: How does the storage engine find variable-length columns?\"}]},{\"@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":"Search Engine Q&A #27: How does the storage engine find variable-length columns? - 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\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/","og_locale":"en_US","og_type":"article","og_title":"Search Engine Q&A #27: How does the storage engine find variable-length columns? - Paul S. Randal","og_description":"This question came up in a class I was teaching a few weeks ago: given that the variable-length column offset array in a record only stores offsets, how does the storage engine find a particular variable-length column? The question comes because there's nothing in the record to say which variable-length column is which – so […]","og_url":"https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/","og_site_name":"Paul S. Randal","article_published_time":"2009-03-01T10:42:00+00:00","author":"Paul Randal","twitter_misc":{"Written by":"Paul Randal","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/","url":"https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/","name":"Search Engine Q&A #27: How does the storage engine find variable-length columns? - Paul S. Randal","isPartOf":{"@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/#website"},"datePublished":"2009-03-01T10:42:00+00:00","author":{"@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/#\/schema\/person\/ffcec826c18782e1e0adf173826a7fce"},"breadcrumb":{"@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.sqlskills.com\/blogs\/paul\/search-engine-qa-27-how-does-the-storage-engine-find-variable-length-columns\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.sqlskills.com\/blogs\/paul\/"},{"@type":"ListItem","position":2,"name":"Search Engine Q&A #27: How does the storage engine find variable-length columns?"}]},{"@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\/945","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=945"}],"version-history":[{"count":0,"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/posts\/945\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/media?parent=945"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/categories?post=945"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sqlskills.com\/blogs\/paul\/wp-json\/wp\/v2\/tags?post=945"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}