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 subproperties of the Object property). 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 (2019) supports four types of nonclustered 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:

SSMS and ADS (current versions)	Legacy SSMS	Plan Explorer	Paste The Plan

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:

The index that is the target of the Index Seek has to be declared as a UNIQUE index;
The Seek Keys must not have a Range specification (which implies that it must have a Prefix specification);
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 doesn’t meet the requirements for a singleton seek.

Dynamic seek range

The exact definition of a range for a range seek is sometimes deferred to run-time. In those cases, the optimizer might create an execution plan where a special value, known as seek_flags is used to determine the exact interpretation of the range.

When a seek_flags value is present, that value itself is not directly visible in the Index Seek operator. Not even in the XML version. This is most likely due to an oversight in the logic that translates the internal representation of the execution plan into XML when the plan is copied out. The only visible indication of the seek_flags being used is that the parent Nested Loops operator has an Outer References that lists three columns, but only two appear to be used. That third one is then probably the seek_flags value. And typically, this seek_flags is computed by a special function, such as GetRangeThroughConvert, GetRangeWithMismatchedTypes, or LikeRangeInfo; or computed by a Merge Interval operator.

A dynamic seek range is always represented as “Column > Expr1 AND Column < Expr2” in the Seek Predicates property, however, the actual test is determined by the bits that are set in the seek_flags column. The following bits and their meaning are known:

Bit-0 (1): Appears to be unused.
Bit-1 (2): Represents the ANSI_NULLS setting for equality comparisons with NULL. This bit is set to 0 when ANSI_NULLS is off, but also when an IS NULL condition is internally converted to an equality comparison for a dynamic seek range.
Bit-2 (4): When this bit is on, the value in Expr1 represents the end of the interval. When this bit is off, the interval has no end. The latter is e.g. the case for an interval defined by just a single > or >= comparison.
Bit-3 (8): When this bit is on, the value in Expr2 represents the start of the interval. When this bit is off, the interval has no start. The latter is e.g. the case for an interval defined by just a single < or <= comparison.
Bit-4 (16): Only used when bit-2 is on. When this bit is on, the value in Expr1 is included in the interval. When it is off, the value in Expr1 is not included.
Bit-5 (32): Only used when bit-3 is on. When this bit is on, the value in Expr2 is included in the interval. When it is off, the value in Expr2 is not included.
Bit-6 (64) and bit-7 (128): Appear to be unused.

Predicate

The Index Seek operator supports an optional 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 find the rows to return. 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.

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.

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.

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. Properties that are included on the Common properties page but are also included below for their specific meaning for the Index Seek operator are marked with a *.

Property name	Description
Actual Partition Count	This is the number of partitions within a partitioned table that were accessed at least once during execution. Only available in execution plan plus run-time statistics and only when the Partitioned property is included and set to True.
Actual Partitions Accessed	This property lists all the partitions within a partitioned table that were accessed at least once during execution. In the execution plan XML, this is actually stored as one or more PartitionRange elements, each with a Start and End property. In tools such as SSMS, this is displayed as a semicolon separated list of ranges, where every single-partition range is displayed as a number instead. So for instance, “2-4;7;10-11” represents that partitions 2, 3, 4, 7, 10, and 11 were accessed at least once. Only available in execution plan plus run-time statistics and only when the Partitioned property is included and set to True.
Defined Values *	For 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 Read	This 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. Note that this property is computed without taking the effect of a row goal (if any) into account. If the EstimateRowsWithoutRowGoal property is present, then you need to compare that, instead of the Estimated Number of Rows, to the Estimated Number of Rows to be Read property for a proper assessment of the estimated selectivity of the Predicate.
Forced Index	This property is set to true if the use of this index was forced through an index hint in the query.
ForceScan	This 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.
ForceSeek	This 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.
NoExpandHint	This 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 Read	This 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. Only available in execution plan plus run-time statistics. When the number of rows read is equal to zero, this property is omitted.
Object	This 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. The subproperties of the Object property represent the alias and the four name parts separately, but also include two additional properties: Index Kind: Represents what kind of index is seeked. For a (nonclustered) Index Seek, this can be ViewNonClustered (for nonclustered indexes on an indexed view), NonClusteredHash (memory-optimized hash indexes only), or NonClustered (for all other cases). Storage: Determines the storage type of the index. Possible values for a (nonclustered) Index Seek are RowStore or MemoryOptimized.
Ordered	This property is always equal to True for an Index Seek.
Partitioned	This property is present and set to True when the index read by the Index Seek is a partitioned index.
Predicate	When 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 Direction	For 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 Predicates	A 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.
Table Cardinality	This 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 name	Description
Batch Mode enabled	The Index Seek operator supports row mode execution only.
Blocking	The Index Seek operator is non-blocking.
Memory requirement	The Index Seek operator does not have any special memory requirement.
Order-preserving	The 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 aware	When 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 aware	The Index Seek operator is not segment aware.