Parent, Previous, Next, Ó 2002 Joe Chang. All rights reserved.

SQL Server Execution Plan Costs, Part I

Every SQL query has one or more possible execution plans. An execution plan consists of one or more component operations. By examining the cost of each component operation under a range of conditions, the functional dependencies for the component operation plan cost formula can be found. It is shown that the cost formula for each SQL Server component operation depends on the number of rows and pages involved. The total estimated cost of an execution plan is calculated by using the component operation cost formulas and statistical estimates for rows and pages involved in each component. This allows query optimizer to choose an execution plan. For complex queries, not every possible execution plan is necessarily evaluated. The component operations examined here includes the Index Seek, Bookmark Lookup, Table Scan, and nested loops, hash and merge join operations and some other common operators.

Index Seek

The Index Seek is one of the basic component operations. The example below shows a simple query that returns a single row. The table has a clustered index on the ID column so a Bookmark Lookup is not required. Figure 2-1a shows the graphical execution plan and Figure 2-1b shows the Index Seek component details. The SELECT component itself also has a cost of 0.0000001 per row as shown in Figure 2-1c.

SELECT * FROM N1C WHERE ID = 1

_x0000_i1026

Figure 2-1a. Execution plan for query with Index Seek operation.

_x0000_i1027

Figure 2-1b. Index Seek component details.

_x0000_i1028

Figure 2-1c.  SELECT component details.

By examining the cost structure over a range of row counts, it is observed that the Index Seek operation cost is governed by the following formula:

I/O Cost = 0.006328500 + 0.000740741 per additional page 
(≤1GB)
         = 0.003203425 + 0.000740741 per additional page 
(>1GB)
CPU Cost = 0.000079600 + 0.000001100 per additional row

The first I/O cost formula applies for systems with up to and including 1GB of memory and the default SQL Server memory configuration (dynamic). The second I/O cost formula applies for systems with more than 1GB of memory. Static SQL Server memory settings have not been investigated. (Earlier versions of this document reported that the two I/O cost formulas depended on the number of processors. This is now known to be not the case.) The I/O cost per additional page applies when many rows are retrieved (or examined if not retrieved) and the rows in question reside in more than one leaf level page. For example, suppose an index leaf level page holds 500 rows. Retrieving up to 500 rows does not require an additional leaf level page unless the rows happen to straddle two pages. For every 500 additional rows, one additional page is required. Figure 2-2 shows the stepped nature of the Index Seek cost.

_x0000_i1029

Figure 2-2.  Multi-row Index Seek cost.

The execution plan Index Seek cost does not vary with index depth. A small table where the entire index fits in a single page has the same execution plan Index Seek cost as a medium size table with 2 index levels (root and leaf) and larger tables with 3 or more index levels (root, leaf and one or more intermediate levels).

Bookmark Lookup

The Bookmark Lookup is not a standalone operation but is always be preceded by an Index Seek. This operation occurs when a nonclustered index is employed in the Index Seek operation, and values not in the index are required. An execution plan involving a Bookmark Lookup is shown in Figure 2-3 and the Bookmark Lookup details is shown in Figure 2-4.

_x0000_i1030

Figure 2-3. Execution plan with Index Seek and Bookmark Lookup operations.

_x0000_i1031

Figure 2-4. Bookmark Lookup component details.

The cost formula for multiple Bookmark Lookup operations follows the formula below.

Estimated I/O Cost = multiple of 0.006250000 
(≤1GB)
                   = multiple of 0.003124925 
(>1GB)
Estimated CPU Cost = 0.0000011 per row

The cost formula is the same regardless of whether the table has a clustered index or is a heap. This is an important point because the Bookmark Lookup operation depends on the table organization. A nonclustered index has pointer to the specific file, page and row for a table organized as a heap. For a table with a clustered index, the nonclustered index stores the clustered index key value. The Bookmark Lookup operation is a file, page and row lookup for a heap, but requires an Index Seek for a table with a clustered index.

The multiple in the Bookmark Lookup I/O cost formula is not always equal to the number of rows. The multiple is 1 for a single row. For a small number of rows (<20) the multiple is typically one less than the number of rows retrieved. For a larger number of rows retrieved, the multiple might be anywhere from 64% to 98% of the estimated number of rows.

The Figure 2-5 shows the Bookmark Lookup I/O cost multiple as a percentage of the number of rows involved for a table with 500,000 rows in 5051 8KB pages. The exact pattern for bookmark multiple is not apparent, but dip at an intermediate number of rows is frequently seen at other table sizes. It is expected that the true cost depends on how frequently each successive Bookmark Lookup involves the same leaf level page as the previous lookup. Since the query optimizer has no way to determine this, perhaps the curve represents an estimate of such an occurrence.

_x0000_i1032

Figure 2-5. Bookmark Lookup I/O cost multiple as a percentage of rows.

The single row bookmark I/O cost is exactly 0.0000785 less than the Index Seek I/O base cost (no additional pages). One possible interpretation is that 0.006250 (≤1GB) is the cost for locating and locking the desired page, 0.0000785 is the cost of reading that page, and 0.0000011 is the cost for locking and retrieving a single row. Hence an Index Seek requires first locating and reading the upper level pages, with 0.006250 + 0.0000785 I/O cost, and second, reading the leaf level page, with 0.0000785 + 0.0000011 CPU cost. This is purely speculative and there other possible interpretations.

On a Bookmark Lookup for a table organized as a heap, the nonclustered index entry has the complete pointer to the file, specific page and row offset (RID), hence only the 0.006250 I/O cost and the 0.0000011 row cost applies. For a table with a clustered index, the nonclustered index entry contains the clustered index key value; hence one would think the entire Index Seek cost applies. Many sources indicate that the Bookmark Lookup on the table with a clustered index is more expensive than the Bookmark Lookup for a table organized as a heap, but the execution plan costs for both types of Bookmark Lookups are identical.

Table Scan and Index Scan

A Table Scan operation occurs when there are no suitable indexes. This could mean that no indexes exist period, or that many rows are expected and it is less expensive to scan the entire table. The execution plan shows a Table Scan operation when the table is a heap, and an index scan operation when the table has a clustered index or if all required values are in a nonclustered index as shown in Figure 2-6. Figures 2-7a and 2-7b shows the cost detail for the Table Scan and index scan operations. The index scan has the same cost structure as a Table Scan.

_x0000_i1033   _x0000_i1034

Figure 2-6.Execution plans for Table Scan and clustered index scan operations.

_x0000_i1035

Figure 2-7a. Cost details for Table Scan.

_x0000_s1026

Figure 2-7b. Cost details for clustered index scan.

By examining the Table Scan I/O and CPU costs for tables over a range of pages and rows, the execution plan cost formula is observed to be as follows:

I/O Cost = 0.0375785 + 0.000740741 per additional page
CPU Cost = 0.0000785 + 0.0000011 per row

The I/O base cost (0.0375785) is exactly 6 x 0.0062500 + 0.0000785. None of the Table Scan cost components were observed to vary by platform or memory.

Index Seek and Table Scan cross-over point

There can only be one clustered index for each table and it is not always practical to build covered indexes for each query that does not use the clustered index. Then there will be queries where the execution plan options are either: 1) an Index Seek with a Bookmark Lookup, or 2) a Table Scan (or clustered index scan). When few rows are expected from the search arguments, the execution plan is the Index Seek with Bookmark Lookup. When many rows are expected, the execution plan is a Table Scan.  It is useful to understand exactly where the execution plan changes from one to the other.

_x0000_i1036/  _x0000_i1037

Figure 2-8. Index Seek with Bookmark Lookup and Table Scan execution plans.

The cost of a Table Scan is determined by the number of pages and the total number of rows in the table. The cost of a Table Scan does not depend on the number of rows returned (unless an aggregate is involved). The cost of the Index Seek operation depends only on the number of rows returned and the number of index leaf level pages occupied by the selected rows, but not on the absolute size of the table, which influences the index depth. The cost of the Bookmark Lookup operation is influenced by the table size (in the undetermined multiple), but is reasonably linear with the rows involved.

The cross-over point where a Table Scan becomes less expensive than an Index Seek with Bookmark Lookup can be determined by equating the two execution plan cost formulas. By representing the undetermined multiple in the Bookmark Lookup I/O cost as a correction factor (CF) and setting aside minor cost components, the cross-over point can be approximately determined.

The difference in the fixed startup costs of the two execution plans is approximately the cost of 5 Bookmark Lookups for 1GB and 11 for >1GB systems. The cost for each incremental Bookmark Lookup row is a multiple of 0.0062511 for 1GB and 0.0031260 for >1GB systems, including both I/O and CPU costs. The cost of each additional page in the Table Scan is 0.000740741 + 0.0000011 × (rows per page). Then the cross-over point approximately follows the formulas below relating the rows meeting the index search condition, and the number of the pages in the table in terms of the “pages-to-rows ratio” and the correction factor CF. The “pages-to-rows ratio” is simply the number of pages for which the incremental cost in a Table Scan is equal to the cost of one Bookmark Lookup. The correction factor CF is the percentage multiple from the Bookmark Lookup cost.

Rows ~   5 + Pages ÷ (CF×(Pages-to-rows ratio))  
(1GB)
     ~ 11 + Pages ÷ (CF×(Pages-to-rows ratio))  (>1GB)

Since the cost of an incremental page in the Table Scan depends on the number of rows per page, the “pages-to-rows ratio” is a function of the row density per page. This dependency is shown in Figure 2-9.

_x0000_i1038

_x0000_i1039

Figure 2-9. “Pages-to-rows ratio” versus rows per page density.

For example, consider a table with an average density of 100 rows per page. The Pages-to-rows ratio is 7.35 for ≤1GB systems and the correction factor is ~0.90. For a table 506 pages in size, the predicted crossover cost occurs at approximately 81.5 rows, compared with the actual crossover point of 84 rows. In other words, the index selectivity needs to be better than 1 row for every 0.9*7.35 pages in the table in order for the query optimizer to use the index over a Table Scan when Bookmark Lookups are required. There may be a slight variation between the point where the costs crossover and where the plan transitions.

Figure 2-10 shows the execution plan cost for an Index Seek and Bookmark Lookup as a function of rows, and the cost of a Table Scan for 50,000 rows at 99 rows per page. The Table Scan cost does not depend on the rows returned.

_x0000_i1040

Figure 2-10. Plan costs for table with 50,000 rows and 99 rows per page.

Figure 2-11 charts the Index Seek and Bookmark Lookup plan costs for ≤1GB and >1GB systems as a function of rows involved and the plan cost for a Table Scan as a function of the number pages in a table (assuming 100 rows per page) on a common graph. Also shown for comparison is the clustered or covered Index Seek cost as a function of rows involved. If the size of the table in pages is known, then the Bookmark Lookup-Table Scan cross over point can be determined by finding the number of rows where the Bookmark Lookup plan has the same cost as the Table Scan, and vice versa.

_x0000_i1041

Figure 2-11. Plan costs versus rows (pages for Table Scan).

It takes approximately twice as many Bookmark Lookups to reach the Table Scan cross-over point on a >1GB system compared to ≤1GB  system as a result of the differences in the ≤1GB  and >1GB Index Seek and Bookmark Lookup I/O costs. One possible reason for this difference (or deliberate choice) is that a Table Scan could be a less memory intensive operation. This would be the case if SQL Server evicts pages used by Table Scans from the buffer pool before pages used by Index Seek and Bookmark Lookup operations.

At high row counts, the Bookmark Lookup plan cost is 700 times more than the covered Index Seek for ≤1GB  and 350 for >1GB. In this example, the covered index holds just over 400 rows per page. Note that the covered index and Table Scan plan costs are very flat at low row counts. This is because the cost for additional rows is very low relative to the fixed base cost of the Index Seek and Table Scan. In fact, it takes 800 rows to double the cost of a covered Index Seek at 100 rows per page based on the ≤1GB cost formula and 400 for the >1GB cost formula. It takes a Table Scan of 4,500 rows in 45 pages to double the cost of a single row Table Scan.

Aggregates

The Stream Aggregate and Compute Scalar operations occur with aggregate functions (MIN, MAX, COUNT, AVG or SUM) as shown in the query below.

SELECT COUNT(*), AVG(Value) FROM M2C_10

The MIN and MAX functions requires the Stream Aggregate operator. The other functions require a Stream Aggregate followed by one or more Compute Scalar operators in the execution plan.

_x0000_i1042

_x0000_i1043

Figure 2-12. Execution plan involving aggregates and compute scalar.

_x0000_i1044

Figure 2-13a. Cost details for Stream Aggregate operation.

_x0000_i1045

Figure 2-13b. Cost details for Compute Scalar operation.

Both operators list a CPU cost of 0.0000001 per row (zero I/O cost), but it appears that only one of the two should be counted in the final cost.