Index Seek

Introduction

The Index Seek operator uses the structure of a nonclustered index to efficiently find either single rows (singleton seek) or specific subsets of rows (range seek). (When SQL Server needs to read single rows or small subsets from a clustered index, it uses a different operator: Clustered Index Seek).

An Index Seek is often used in combination with a Nested Loops operator into either a Key Lookup or RID Lookup operator; in this specific combination the Index Seek is used to quickly find required rows, and the lookup is then used to fetch additional data for columns not included in the index structure. A nonclustered index is said to be covering for a query if all data needed for the query can be read directly from the index itself, eliminating the need for this lookup.

Though the generic logic of the Index Seek operator is always the same, the exact actions taken, and also the options available to the optimizer, vary depending on the type of index used (as defined in the Storage and IndexKind properties). Most of this logic is carried out at the level of the storage engine. Since an understanding of this is important to get a proper understanding of the performance of this operator, the actual actions carried out at the level of the storage engine will be described on this page as well.

The current version of SQL Server (2017) supports four types of index storage. The Storage property distinguishes between RowStore, ColumnStore, and MemoryOptimized; for the latter type only IndexKind further differentiates this into NonClustered and NonClusteredHash.

An Index Seek operator cannot be used for columnstore indexes, so on this page we will only need to discuss how the Index Seek behaves for (nonclustered) rowstore indexes, and for (both regular nonclustered as well as nonclustered hash) memory-optimzed indexes.

Visual appearance in execution plans

Depending on the tool being used, an Index Seek operator is displayed in a graphical execution plan as shown below:

SQL Server Management Studio

Azure Data Studio

Plan Explorer

(until version 17.3)

(version 17.4 and up)

Algorithm

The basic algorithm for the Index Seek operator is as shown below:

Note that this flowchart is a simplification. It doesn’t show that execution stops whenever a row is returned, and resumes where it was upon next being called.

Also note that, depending on the transaction isolation level that is in effect for the index being read, locks may be taken and released as rows are accessed. This is part of the responsibility of the storage engine, and a detailed discussion of this functionality is beyond the scope of this website.

Seek Keys

Every Index Seek operator has a Seek Predicates property that consists of one or more elements, called Seek Keys. Each Seek Keys can specify a prefix, a range, or both. (a combination of a prefix and a range is only possible when the Index Seek targets a composite index).

Prefix specification

The prefix specification of a Seek Keys element provides an equality condition for one or more of the left-most columns in the object index. So if an index is on for instance three columns, then the prefix specification can apply to the leftmost column only, to the two leftmost columns, or to all three columns. The prefix condition is typically displayed (in SSMS) in the form “Prefix: Columns = Expressions”, where Columns is a semicolon-separated list of columns that are indexed by the index being seeked, and Expression is a semicolon-separated list of values, containing the same amount of values as there are columns in Columns. Note that the expressions may include the special value “Scalar Operator (NULL)”, and that this will be interpreted as meaning “IS NULL”.

The Index Seek will only return rows for which the values in the specified columns are all equal to the values in the corresponding expressions, optionally further narrowed down by the range specification.

Range specification

The range specification of a Seek Keys element is used to specify a range of rows within the prefix, or in case no prefix is specified a range of rows within the index as a whole. The range specification can only apply to the column that, in the index definition, immediately follows the last column of the prefix specification (which implies that when there is no prefix specification, the range specification can only apply to the leftmost column in the index definition). Typically a range specification consists of a start and end condition, though it is also possible to see a range specification that has only a start or only an end condition. There is also a special case: the “IsNotNull” condition.

Range start

The start condition of a range specification is displayed in SSMS in the form “Start: Column Op Expression”, where Column specifies the column used (always the first column in the index definition after the columns used in the prefix specification), Op specifies the operator (which will be either > or >= for most indexes, but < or <= for indexes that were built on a descending sort order), and Expression specifies the start value.

If a range is specified without a start condition and it does not use the “IsNotNull” condition, then it starts at the first row in the index that matches the prefix specification, or the very first row in the index if there is no prefix specification.

Range end

The end condition of a range specification is displayed in SSMS in the form “End: Column Op Expression”, where Column specifies the column used (always the first column in the index definition after the columns used in the prefix specification), Op specifies the operator (which will be either < or <= for most indexes, but > or >= for indexes that were built on a descending sort order), and Expression specifies the end value.

If a range is specified without an end condition and it does not use the “IsNotNull” condition, then it ends immediately after the last row in the index that matches the prefix specification, or at the very end of the index if there is no prefix specification.

IsNotNull

The special “IsNotNull” condition is not displayed correctly in the SSMS tooltip: it will show as an empty Seek Keys if there is no prefix condition, and if there is a prefix condition as well then only that condition is shown and the IsNotNull condition is not visible at all. The full properties window does expose this condition correctly, though.

The IsNotNull condition lists a single column (always the first column in the index definition after the columns used in the prefix specification), and specifies that all non-null values in that column are part of the range. Since null values are stored first in an index, the IsNotNull condition is equivalent to a normal range specification that starts at the first non-null value and has no end condition; or for an index built on a descending sort order as a range specification that has no start condition and ends after the last non-null value.

Note that an IsNotNull condition cannot be combined with a Start or End condition.

Also note that there is no IsNull condition. If an Index Seek is used to find null values, it will use a Prefix specification. Even though the condition will be shown as “Column = Scalar Operator (NULL)” in the SSMS rendition of the execution plan, the operator will actually apply the expected IS NULL logic.

Singleton seek vs range seek

Every Seek Keys specification can be either for a “singleton seek”, or for a “range seek”. A singleton seek applies when at most a single row can satisfy the requirement of the Seek Keys specification. A range seek means that (potentially) more than a single row can qualify.

For a singleton seek, the index structure is used to find the row that matches the specified condition. If it exists, it is returned and then the operator immediately continues to the next Seek Keys specification. If it doesn’t, then nothing is returned and  the operator continues to the next Seek Keys specification. A Seek Keys specification is considered a singleton seek if all of the following conditions are met:

  1. The index that is the target of the Index Seek has to be declared as a UNIQUE index;
  2. The Seek Keys must not have a Range specification (which implies that it must have a Prefix specification);
  3. The Prefix specification needs to provide values for all columns in the index specification, so if the index is on e.g. three columns, all three must be included in the Prefix specification of the Seek Keys.

For a range seek, the index structure is used to find the first row that matches the specified condition. If it exists, it is returned and then the operator switches to behavior similar to that of the Index Scan operator to find additional rows that meet the condition. Once a row is found that no longer qualifies (or if no qualifying row is found at all), it continues to the next Seek Keys specification. A Seek Keys specification is considered a range seek if if does not meet the requirements for a singleton seek.

Predicate

The Index Seek operator supports an option Predicate property, which can be used to push additional filter logic that cannot be used to reduce the number of rows accessed in the index, but can be used to reduce the number of rows returned by the operator to its parent operator. It is assumed (but not documented) that this logic is pushed into the storage engine where possible.

A Predicate property will typically be used for filters on indexed columns that cannot benefit from the storage structure, filters on included columns, or in a composite index a filter on e.g. the third column when there is no equality condition for both the first and second columns.

Variations by index type

The flowchart above shows the basic outline of Index Seek processing. As mentioned before, some of the actions can vary depending on the type of index that is used in the Index Seek. In the paragraphs below the different behavior of the “Read first row in range” and “Read next row in range” actions is detailed per type of index.

RowStore

For a RowStore nonclustered index (Storage = “RowStore” and IndexKind = “NonClustered”), the Index Seek operator uses the B-tree structure of the index to drive the scan. A B-tree always has a single so-called root page, with pointers to either one or more levels of intermediate index pages, or leaf pages where the actual index data is stored. A more detailed discussion of this B-tree structure is beyond the scope of this website.

The description here applies when the Scan Direction property is FORWARD. If it is BACKWARD, then the roles of the Range Start and Range End conditions are reversed and all pages (root, intermediate, and leaf) are processed in reverse logical order.

Read first row in range

The internal data structures (which can be seen through the sys.sysindexes view) are used to find the location of the root page. It brings that page into the buffer pool and compares the values of the indexed columns in each entry (in correct logical order, based on the row offset table on the page) to the specifications in the currently evaluated Seek Keys specification. As soon as it finds an entry for which the values in all columns in the Prefix and Range Start conditions are equal to or greater (lesser for descending index columns) than the specified target values, it goes back one entry (to the last entry that does not satisfy these conditions) to find the page to process at the next lower level. (If the very first entry already matches the conditions, then there is no prior entry and the first entry itself will be followed).

It now brings the page to process at the next lower level into the buffer pool and checks the page header. If the page is an intermediate level index, it is processed the same way as the root page to find the page at the next deeper level. This repeats until a leaf page is found.

Once a leaf page is found, it once more compares the values of the indexed columns in each row (in correct logical order, based on the row offset table on the page) to the specifications in the currently evaluated Seek Keys specification until it finds a row for which the values in all columns in the Prefix and Range Start conditions are equal to or greater (lesser for descending index columns) than the specified target values. If then also the Prefix and Range End columns for this row are equal to or lesser (greater for descending index columns) than the specified target values, then this row is the first row in the range. If not, then there are no rows in the specified range.

Read next row in range

For a range seek, the next call to the Index Seek uses the row offset table on the current page to find the location of the next row. If the last row on the current page was processed, it checks the NextPage pointer on the current leaf page to find the logical next leaf page, brings that into the buffer pool, and then once more uses the row offset table on that page to find the location of the first row, and then returns that row.

For each row found in this way, the values of the columns used in the Prefix and Range End conditions are compared to the target values. As soon as a row is found that does not satisfy these conditions, or when the last row of a leaf page was processed and that leaf page has a nil pointer in NextPage, the end of the range (or of the index data) is reached and no row is returned.

MemoryOptimized (NonClustered)

For a RowStore nonclustered index (Storage = “RowStore” and IndexKind = “NonClustered”), the Index Seek operator uses the Bw-tree structure of the index to drive the scan. A more detailed discussion of the Bw-tree structure is beyond the scope of this website; but since it is very similar to the B-tree structure of rowstore indexes, the processes to read it are very similar too.

Read first row in range

The operator first uses internal data structures (beyond the scope of this website) to find the Page Mapping Table (PMT) of the index, then uses that to find the location in memory of the current version of the root page. On that page, it reads the values of the indexed columns in each entry (in correct logical order) and compares them to the specifications in the currently evaluated Seek Keys specification. As soon as it finds an entry for which the values in all columns in the Prefix and Range Start conditions are equal to or greater (lesser for descending index columns) than the specified target values, it goes back one entry (to the last entry that does not satisfy these conditions) to find the pointer to the index page to process at the next lower level. (If the very first entry already matches the conditions, then there is no prior entry and the first entry itself will be followed).

It (once more via the PMT) goes to that non-leaf page. The data on this page is then processed the exact same way as the root page to find the page at the next deeper level. This repeats until a leaf page is found.

On the leaf page, it once more compares the values of the indexed columns in each row (in correct logical order) to the specifications in the currently evaluated Seek Keys specification until it finds an entry for which the values in all columns in the Prefix and Range Start conditions are equal to or greater (lesser for descending index columns) than the specified target values. If then also the Prefix and Range End columns for this row are equal to or lesser (greater for descending index columns) than the specified target values, then this entry is the first in the range. It uses the pointer to find the first row for this index value and uses the timestamp values to verify whether the row should be visible for the running transaction. If not, then the pointer to the next row is followed, and the process repeats. If a visible row is found, then that row is returned to the operator.

Read next row in range

On the next call to Index Seek, it follows the pointer to the next row from the current row, uses the timestamp values of that row to determine whether the row is visible for the current transaction. If it is, then that row is returned. Otherwise the next row in the pointer chain is checked. If the end of the pointer chain is reached, then the scan returns to the current leaf page of the index, moves to the next index value (skipping to the logically next leaf page when the current page is exhausted), and verifies the Prefix and Range End conditions. If the value is still in range, then the operator again starts following the pointer chain.

The process ends as soon as an index entry is processed that does not meet the Prefix and Range End specification, or when the last leaf page (the one with a nil pointer to the next page) has been exhausted.

MemoryOptimized (NonClusteredHash)

A MemoryOptimized nonclustered hash index (Storage = “MemoryOptimized” and IndexKind = “NonClusteredHash”) uses a hash table to store the data. Inequality and range comparisons do not work on this structure, so an Index Seek on a memory-optimized nonclustered hash index will only use prefix conditions in the Seek Keys specifications, and in the case of a composite index the prefix condition must include all indexed columns.

Read first row in range

The operator uses internal data structures (beyond the scope of this website) to find the start of the internal hash table for the index. It computes the hash of the target values specified in the prefix condition of the Seek Keys specification, computes the memory location of the corresponding hash bucket, and reads it.

If the hash bucket has a nil pointer, no rows exist in the specified range. Otherwise the operator follows the pointer and checks the timestamp values of the row found to verify whether the row should be visible for the running transaction. If not, then the pointer to the next row is followed, and the process repeats. If a visible row is found, then that row is returned to the operator.

Read next row in range

For the next row, the operator follows the pointer to the next row from the current row and checks the timestamp values of that row to verify its visibility for the current transaction. If it is visible, that row is returned. Otherwise the next row in the pointer chain is checked. If the end of the pointer chain is reached, the end of the range is reached and no further rows are returned for the current Seek Keys specification.

Operator properties

The properties below are specific to the Index Seek operator, or have a specific meaning when appearing on it. For all other properties, see Common properties.

Property nameDescription
Defined ValuesFor an Index Seek, this property lists the columns read from the index and returned to the calling operator. It is therefore the same as the Output List property.
Estimated Number of Rows to be ReadThis is an estimate of the number of rows that will be read by the operator as it is navigating the index. The higher the difference between this number and the Table Cardinality, the more effective the use of this Index Seek (as opposed to an Index Scan) is estimated to be.
The difference between this property and the Estimated Number of Rows property represents the number of rows that is estimated to be read but not returned due to the Predicate property.
Forced IndexThis property is set to true if the use of this index was forced through an index hint in the query.
ForceScanThis property is set to true if the query used a FORCESCAN hint to force the use of a scan operator even if the optimizer would rather use a seek operator. On an Index Seek operator, it is therefore always false.
ForceSeekThis property is set to true if the query used a FORCESEEK hint to force the use of a seek operator even if the optimizer would rather use a scan operator.
IndexKindThis represents the type of nonclustered index being scanned. For disk based (rowstore) indexes, this is always NonClustered. For memory optimized indexes only, it can be either NonClustered or NonClusteredHash.
Note that this property is not exposed in the property list of SSMS, though the type of index is showed in parentheses below the operator. The property can be accessed through the execution plan XML.
Logical OperationAlways equal to Index Seek.
NoExpandHintThis property is set to true if the NOEXPAND hint was used in the query to force the optimizer to use indexes on an indexed view.
Number of Rows ReadThis is the number of rows that was read by the operator as it was navigating the index. In a parallel execution plan, this property shows a breakdown of rows on each individual thread.
The difference between this property and the Actual Number of Rows property represents the number of rows that was read but not returned due to the Predicate property.
Actual execution plans only. When the actual number of rows read is equal to zero, this property is omitted.
ObjectThis property lists the index that is being navigated by the Index Seek operator, using four part naming (database, schema, table, index) and optionally followed by a table alias.
OrderedThis property is always equal to True for an Index Seek.
PredicateWhen present, this property defines a logical test to be applied to all rows that are read by the Index Seek. Only rows for which the predicate evaluates to True are returned. When possible, the Index Seek operator will push this predicate into the storage engine to prevent extra roundtrips between the operator and the storage engine.
Note that a Predicate on an Index Seek does not reduce the amount of rows that is touched by the operator. The difference between the Actual Number of Rows and the Number of Rows Read property (or their estimated counterparts) shows how many rows were read but not returned. This can be used to gauge how useful an index would be that better supports the search predicates.
Scan DirectionFor range seeks, this property specifies whether the data has to be returned in normal index order (“FORWARD”) or reverse index order (“BACKWARD”).
The BACKWARD option is not available for memory-optimized indexes.
Seek PredicatesA collection of one or more Seek Keys that are used to navigate the index and locate the rows to be read. See the main text for more information.
StorageThis property determines the type of index being navigated. (Note that this could also be determined by using the DMVs based on the Object property). Possible values for an Index Seek are RowStore and MemoryOptimized.
Table CardinalityThis property shows the number of rows in the index’s table when the plan was last compiled.

Implicit properties

This table below lists the behavior of the implicit properties for the Index Seek operator.

Property nameDescription
Batch Mode enabledThe Index Seek operator supports row mode execution only.
BlockingThe Index Seek operator is non-blocking.
Memory requirementThe Index Seek operator does not have any special memory requirement.
Order-preservingThe Index Seek operator imposes an order, as specified in the Scan Direction property. If the Seek Predicates property specifies more than one Seek Keys specification, the optimizer always ensures that these are in the correct corresponding order.
Parallelism awareWhen the Index Seek operator is used for range scans in a parallel section of an execution plan, it uses the “Parallel Page Supplier”. See Index Scan for more details.
Segment awareThe Index Seek operator is not segment aware.
Menu

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close