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

Details from SSMS 2005.

Details from SSMS 2008.

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 Executions | Total SubtreeCost | TotSubtreeCost -rows*CPU | Net/0.003125 |
---|---|---|---|

1 | 0.0032831 | 0.003125000 | 1.0000 |

2 | 0.005002026 | 0.004685826 | 1.4995 |

3 | 0.007066287 | 0.006591987 | 2.1094 |

4 | 0.009994013 | 0.009361613 | 2.9957 |

5 | 0.01326374 | 0.012473240 | 3.9914 |

6 | 0.01652902 | 0.015580420 | 4.9857 |

8 | 0.02304627 | 0.021781470 | 6.9701 |

9 | 0.02629826 | 0.024875360 | 7.9601 |

11 | 0.03278897 | 0.031049870 | 9.9360 |

12 | 0.03602771 | 0.034130510 | 10.9218 |

16 | 0.04893874 | 0.046409140 | 14.8509 |

17 | 0.05215554 | 0.049467840 | 15.8297 |

25 | 0.07773317 | 0.073780670 | 23.6098 |

27 | 0.08408425 | 0.079815550 | 25.5410 |

28 | 0.08725333 | 0.082826530 | 26.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.