Inside the Optimizer: Constructing a Plan—Part 3

Introduction

In order to fully explore the way the query optimizer uses rules to construct plan alternatives, we will need a way to identify the rules used to optimize a particular query.

SQL Server 2005 (later builds only) and SQL Server 2008 include an undocumented Dynamic Management View (DMV) that shows information about the internal rules used by the optimizer. By taking a snapshot of that DMV before running a test query, and comparing it with the post-optimization data, we can deduce the rules invoked by the optimizer during optimization.

Before we get to the DMV itself, we need to nail down a few more things about the internals of the SQL Server query optimizer. The next section builds on the ‘trees and rules’ information given in part 1 of this series.

The Optimization Process

Query optimization is a recursive process that starts at the root of a logical operator tree, and ends by producing a physical representation suitable for execution.

The space of possible plans is explored by applying rules that result in a logical transformation of some part of the current plan, or a conversion of that part to a particular physical implementation.

The optimizer does not try to match every available rule to every part of every query, in every possible combination. That sort of exhaustive approach would guarantee the best plan possible, but you would not like the compilation times, or the memory usage!

To find a good plan quickly, the optimizer uses a number of techniques. I plan to cover these in some detail in future posts, but two of these tricks are immediately relevant to the DMV:

1. Every logical operator contains code to describe all the rules that are capable of matching with it. This saves the optimizer from trying rules which have no chance of producing a lower-cost plan.

2. Every rule contains code to compute a value to indicate how promising the rule is in the current context. A rule has a higher promise value if it has a high potential to reduce the cost of the overall plan.

   In general, commonly-used optimizations (like pushing a predicate) have a high ‘promise’ value. More specialised rules, like those that match indexed views may have a lower promise value.

When faced with several possible rule choices, the optimizer uses promise values as part of its strategy. This helps reduce compilation time, while still pursuing the most promising transformations.

sys.dm_exec_query_transformation_stats

This DMV contains one row for each rule, with the following columns:

• The name column contains the internal name for the rule. An example is JNtoSM—an implementation rule to transform a logical inner join to a physical sort-merge join operator.
• The promised column shows how many times the rule has been asked to provide a promise value to the optimizer.
• The promise_total column is the sum of all the promise values returned.
• The promise_avg column is promise_total divided by promised.
• The built_substitute column tracks how many times the rule has produced an alternative implementation for a logical group.
• The succeeded column tracks the number of times that a rule generated a transformation that was successfully added to the space of valid alternative strategies.

Not all transformations that result in an alternative will match the specific requirements of the current query plan. For example, the alternative may not preserve a required sort order, or some other required property.

Using the DMV

The scripts included here were tested on SQL Server x86 Developer Edition, versions 10.0.2775 (2008 SP1 CU8) and 9.0.4294 (2005 SP3 CU9). This DMV may not be available on all builds of SQL Server 2005.

The DMV contains server-scoped optimizer information. For correct results, you will need to ensure that no other concurrent optimization activity is occurring on the test server. Working on a personal test SQL Server and ensuring yours is the only active connection is a good place to start with that.

First, we need to create the structure of a temporary table to hold a snapshot of the DMV contents prior to running the test query:

SELECT TOP (0)
    name,
    promise_total,
    promised,
    built_substitute,
    succeeded
INTO #Snapshot
FROM sys.dm_exec_query_transformation_stats;

Now we can write a batch to capture a DMV snapshot, run our test query, and show the DMV differences afterward:

-- Clear the snapshot
TRUNCATE TABLE #Snapshot;
 
-- Save a snapshot of the DMV
INSERT #Snapshot 
(
    [name], 
    promise_total, 
    promised, 
    built_substitute, 
    succeeded
)
SELECT
    [name],
    promise_total,
    promised, 
    built_substitute, 
    succeeded
FROM sys.dm_exec_query_transformation_stats
OPTION
    (KEEPFIXED PLAN);
 
-- Query under test
-- Must use OPTION (RECOMPILE)
SELECT
    P.ProductNumber, 
    P.ProductID, 
    total_qty = SUM(I.Quantity)
FROM Production.Product AS P
JOIN Production.ProductInventory AS I
    ON I.ProductID = P.ProductID
WHERE
    P.ProductNumber LIKE N'T%'
GROUP BY
    P.ProductID,
    P.ProductNumber
OPTION
    (RECOMPILE);
 
-- Results
SELECT
    QTS.name,
    promise = QTS.promised - S.promised,
    promise_value_avg = 
        CASE
            WHEN QTS.promised = S.promised
            THEN 0
            ELSE
                (QTS.promise_total - S.promise_total) /
                (QTS.promised - S.promised)
            END,
    built = QTS.built_substitute - S.built_substitute,
    success = QTS.succeeded - S.succeeded
FROM #Snapshot AS S
JOIN sys.dm_exec_query_transformation_stats QTS
    ON QTS.name = S.name
WHERE
    QTS.succeeded <> S.succeeded
ORDER BY
    promise_value_avg DESC
OPTION
    (KEEPFIXED PLAN);

The query to test must have the OPTION (RECOMPILE) query hint added to ensure that a compilation occurs. Other queries in the batch have OPTION (KEEPFIXED PLAN) to help avoid compilations that would skew the results.

The example above uses the AdventureWorks query we have been using in this series so far. It produces the familiar, fully-optimized, plan:

Here are partial results from a typical run:

The output shows the rule name, the number of times a promise value was calculated, the average promise values produced, the number of times a transformed structure was built, and the number of times the new structure was successfully added to the optimizer’s list of valid choices. Notice that rules can be invoked multiple times, since they may match more than one place in the query, and the compilation process is a recursive one. You might also see rules with a promise value of zero, which simply means the promise-calculating code did not have enough information to produce a value.

Next time

Now that we have found a way to identify the rules used to optimize a given query, we can move on to the really fun stuff. In the next part of the series, I will show two ways to affect the rules available to the optimizer, and present code to reproduce the ‘interesting’ partially-optimised query plans shown in parts 1 & 2.

---

This post is part of a series: Part 1 | Part 2 | Part 3 | Part 4

---