A First Look at Execution Plan Costs in Yukon Beta 1

Most of the cost formulas appear not to have changed. This includes the index seek, table scan, and loop, hash, and merge joins. The bookmark lookup has changed. A bookmark lookup frequently follows after a nonclustered index is used to find a set of rows when more information about the table is required than resides in the index. As an example, TableA has a nonclustered index on column Col1. For a query of the form SELECT * FROM TableA WHERE Col1 = x, then execution may be an index seek on the index for Co1l, followed by a bookmark lookup to the table for the remaining column information on the valid rows. In SQL Server versions 7.0 and 2000, then execution plan would look like the plan in Figure 1. In Yukon Beta 1, then execution plan looks like one of the plans shown in Figure 2 and Figure 3.

Figure 1. SQL Server 7.0 and 2000 execution plan with Bookmark Lookup.

Figure 2. Yukon Beta 1 execution plan for “RID” Lookup.


Figure 3. Yukon Beta 1 execution plan for a lookup on a clustered index.

This change in the graphical representation of  the bookmark lookup does not actually change how the underlying operation is performed, but does present a more consistent picture of the operations involved. First, there is a difference between the bookmark lookup on a heap organized table versus a table with a clustered index. SQL Server 7.0 and 2000 did not show this, while Yukon does show the difference. In a heap organized table, the nonclustered index has the row, page and file information to directly located the page holding the row data. In a table with a clustered index, the nonclustered index has the clustered index key value. In this case, the bookmark lookup is performance with an index seek operation.

Second, there is some similarity between a bookmark lookup and a loop join operation, so the change does better represent the underlying operation. The down side is that the displayed operation is more complex than a simple bookmark lookup symbol. In complex execution plan, it is sometimes better to simplify parts of the graphical execution plan that are already understood or otherwise uninteresting (relative to the more interesting parts of the overall plan).

In addition to the change in the graphically displayed execution plan for the bookmark lookup, the cost formulas for the bookmark lookup operation has also been changed. In SQL Server 7.0 and 2000, the bookmark lookup operation had one set of cost formulas, and the loop join had another set of formulas. In Yukon Beta 1, the old bookmark lookup cost formulas have been discarded and there is now one set of cost formulas for both the bookmark lookup and loop join. The set of cost formulas is the same as the old 7.0 and 2000 loop join cost formulas. While this is a more consistent representation of the underlying operation, there are both positive and negative consequences.

First, lets quickly review some of the cost formulas involved. The index seek operation has the cost formulas below that were set in 7.0 and remains in Yukon Beta 1.

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. The additional page cost applies only to leaf level pages and not intermediate level pages.

The old SQL Server 7.0 and 2000 cost formulas for bookmark lookup operations follows the formulas below.

Estimated I/O Cost = multiple of 0.006250000 (=1GB)

= multiple of 0.003124925 (>1GB)

Estimated CPU Cost = 0.0000011 per row

The multiple is not the same as the estimated number of rows involved, but rather a close fraction of the estimated rows. Figure 4 shows one example of the old bookmark lookup multiple.    

Figure 4. Old Bookmark Lookup I/O cost multiple as a percentage of rows.

The table scan cost formula for SQL Server 7.0, 2000 and Yukon Beta 1follows the formula below.

I/O Cost = 0.0375785 + 0.000740741 per additional page

CPU Cost = 0.0000785 + 0.0000011 per row

The implication of the SQL Server 7.0 and 2000 cost formulas are that the bookmark lookup plan cost for a single row is rated at approximately 7 times more expensive than the incremental cost of each scanning one page in a table scan for =1GB system memory and 3.5 times for >1GB system memory.


Leave a comment

Your email address will not be published.