Home, Parent: SQL Server Cost Based Optimizer
AdventureWorks, Index Seek, Key Lookups, Table Scan, Joins, Insert, Update, Delete,
Parallelism I, Parallelism II, Parallelism III,

The query below uses a CustomerID for which the data distribution Range High Key has Equal Rows 2.

SELECT SalesOrderID, TotalDue FROM Sales.SalesOrderHeader WHERE CustomerID = 11361

Key Lookup

Details from SSMS 2005.

Key Lookup Key Lookup

Details from SSMS 2008.

Key Lookup Key Lookup

Observe that the Index Seek has an estimated number of rows 2, while the key lookup shows estimated number of rows 1. The estimated IO cost for the Index Seek is still 0.003125, but the estimated CPU cost is 0.0001592, which is 0.0001581 for the first row and 0.0000011 for each additional row. The Key lookup shows the same estimated IO cost 0.003125 and CPU cost 0.0001581 as for single row query, but the Estimated Operator Cost is now 0.005002 instead of 0.0032831.

The XML plan details pertinent to the Key Lookup for 2 rows from the Index Seek are shown below. Note the Estimate Rebinds value, which is not shown in the graphical detail.

<RelOp AvgRowSize="31" EstimateCPU="0.0001581" EstimateIO="0.003125" EstimateRebinds="1" EstimateRewinds="0" EstimateRows="1" LogicalOp="Clustered Index Seek" NodeId="4" Parallel="false" PhysicalOp="Clustered Index Seek" EstimatedTotalSubtreeCost="0.00500202">

The details for 3 and 4 rows from the Index Seek are shown below.

<RelOp AvgRowSize="31" EstimateCPU="0.0001581" EstimateIO="0.003125" EstimateRebinds="2" EstimateRewinds="0" EstimateRows="1" LogicalOp="Clustered Index Seek" NodeId="4" Parallel="false" PhysicalOp="Clustered Index Seek" EstimatedTotalSubtreeCost="0.00706628">

<RelOp AvgRowSize="31" EstimateCPU="0.0001581" EstimateIO="0.003125" EstimateRebinds="3" EstimateRewinds="0" EstimateRows="1" LogicalOp="Clustered Index Seek" NodeId="4" Parallel="false" PhysicalOp="Clustered Index Seek" EstimatedTotalSubtreeCost="0.00999399">

The interpretation is that the cost assessed for Key Lookups involves the number of Rebinds, which appears to be the number of additional rows that require a key lookup after the first row. The Estimated Number of Rows represents the number of rows per key lookup (there can be only one row per key lookup, but there can be multiple rows from a loop join the inner source index seek).

The queries below are selected based on having being Range High Key values for various Equal Row values ranging from 1 to 28.

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 12375 -- 1

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 11361 -- 2

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 11965 -- 3

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 12655 -- 4

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 11784 -- 5

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 11439 -- 6

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 233 -- 8

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 191 -- 9

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 126 -- 11

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 54 -- 12

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 11519 -- 16

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 11019 -- 17

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 11566 -- 25

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 11185 -- 27

SELECT SubTotal FROM Sales.SalesOrderHeader WHERE CustomerID = 11091 -- 28

The table below shows the Estimate Executions from SHOWPLAN_ALL in the first column, the Total Subtree Cost in the second column, the net cost after subtracting 0.0001581 per row from the Total Subtree Cost, and finally the net cost divided by the IO cost for a single operation: 0.003125.

Estimate ExecutionsTotal SubtreeCostTotSubtreeCost -rows*CPUNet/0.003125
10.00328310.0031250001.0000
20.0050020260.0046858261.4995
30.0070662870.0065919872.1094
40.0099940130.0093616132.9957
50.013263740.0124732403.9914
60.016529020.0155804204.9857
80.023046270.0217814706.9701
90.026298260.0248753607.9601
110.032788970.0310498709.9360
120.036027710.03413051010.9218
160.048938740.04640914014.8509
170.052155540.04946784015.8297
250.077733170.07378067023.6098
270.084084250.07981555025.5410
280.087253330.08282653026.5045

It is apparent that the CPU cost of 0.0001581 is assessed for each execution of the key lookup (or for each row of the index seek), but only a percentage of the IO cost of 0.003125 is assessed. The figure below shows the percentage of index rows for which the IO cost is assessed.

IO percentage versus rows

The assumption is that for each subsequent key lookup, there is a chance that the required page is already in-memory, so no additional IO cost need be assessed. For a small table, the number IO assessed has an upper bound limited by the number of data pages used. For a larger table, a previously loaded page may have been evicted, so the upper bound is not limited by the number of data pages.