Why do root and intermediate levels of NON-unique NON-clustered indexes additionally store row ID?

Question

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.

Answer 1

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.

Answer 2

The storage engine needs a way of uniquely identifying a row. It does that through the index key columns, both for clustered and non-clustered indexes.

If the index key is non-unique, and there are duplicates on the page, the storage engine will add a "uniquifier". It only adds this into the pysical page if necessary, although it always shows up in the execution plans even when not used.

What's the point of having a row ID on non-leaf index pages?

To identify the row.

That would make sense in case of UNIQUE indexes.

No it wouldn't make sense, it's not needed then as the row is identified purely by the key columns.

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.

The leaf needs to be loaded in order to get any additional INCLUDE columns, and possibly because there may be multiple rows on a single leaf page (there usually are). Remember that the intermediate pages may not point to a single unique row, they may point to a range of rows on a leaf page.

Occasionally, if there are no INCLUDEs and the exact row data has been identified from the intermediate pages then yes, the leaf can be skipped, but that does not usually happen.

There is no "row ID" as such on a clustered table, it's just a combination of unique columns. And the uniquifier is not a row ID, it's just an extra hidden column to make the row unique. You only get a row ID (bookmark) if your table is a heap, although why you would have an NCI on a heap is rather questionable.

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?

To identify which row is which. Each row must be uniquely identified, that is simply how the storage engine works. You cannot have two rows completely identical in the index, as they refer to different clustered index rows.

To bring the point home: if there were two identical rows, and they were on different leaf pages, how would the intermediate pages identify them? How would you say which row you are up to when scanning or seeking the index?