patternsqlMinor
Why do root and intermediate levels of NON-unique NON-clustered indexes additionally store row ID?
Viewed 0 times
uniquewhyclusterednonindexesadditionallystorelevelsrootand
Problem
I'm reading Pro SQL Server Internals by Dmitry Korotkevich and in Chapter 2 (TABLES AND INDEXES: INTERNAL STRUCTURE AND ACCESS METHODS) I found this:
Like clustered indexes, the intermediate and root levels of nonclustered indexes store one row per page
from the level they reference. That row consists of the physical address and the minimum value of the key
from the page. In addition, for non-unique indexes, it also stores the row-id of such a row.
What's the point of having a row ID on non-leaf index pages? That would make sense in case of UNIQUE indexes. So if you've already found a value in the root or any intermediate level, use that row ID and don't "load" the pages at the leaf level because it's unique (won't be any additional matches). Since no additional pages need to be loaded, it saves a lot of processing time. In a non-unique index, you must "load" the pages at the leaf level anyway, because there may be more than one match. So what's the point of row IDs on non-leaf pages in non-unique indexes?
I hope I have explained well what is not clear to me.
Like clustered indexes, the intermediate and root levels of nonclustered indexes store one row per page
from the level they reference. That row consists of the physical address and the minimum value of the key
from the page. In addition, for non-unique indexes, it also stores the row-id of such a row.
What's the point of having a row ID on non-leaf index pages? That would make sense in case of UNIQUE indexes. So if you've already found a value in the root or any intermediate level, use that row ID and don't "load" the pages at the leaf level because it's unique (won't be any additional matches). Since no additional pages need to be loaded, it saves a lot of processing time. In a non-unique index, you must "load" the pages at the leaf level anyway, because there may be more than one match. So what's the point of row IDs on non-leaf pages in non-unique indexes?
I hope I have explained well what is not clear to me.
Solution
The SQL Server storage engine requires every entry in an index be unique at all levels at all times.
For a unique nonclustered index, only the nonclustered keys are required above the leaf because they're unique by definition. The full bookmark (aka row locator, RID) to the associated heap or clustered row is only needed at the leaf (to locate the parent row for bookmark lookups).
For a nonunique nonclustered index, the bookmark is added at all levels (as part of the key) to meet the storage engine requirement that all index entries be unique at every level.
For a rowstore heap table, the bookmark is the file:page:row physical RID. For a clustered rowstore table, the bookmark (logical RID) is the clustering key. The clustering key includes an integer uniquifier if the clustered index is not unique, and duplicates are present for a particular key value.
For a unique nonclustered index, only the nonclustered keys are required above the leaf because they're unique by definition. The full bookmark (aka row locator, RID) to the associated heap or clustered row is only needed at the leaf (to locate the parent row for bookmark lookups).
For a nonunique nonclustered index, the bookmark is added at all levels (as part of the key) to meet the storage engine requirement that all index entries be unique at every level.
For a rowstore heap table, the bookmark is the file:page:row physical RID. For a clustered rowstore table, the bookmark (logical RID) is the clustering key. The clustering key includes an integer uniquifier if the clustered index is not unique, and duplicates are present for a particular key value.
Context
StackExchange Database Administrators Q#318601, answer score: 7
Revisions (0)
No revisions yet.