Search results matching tag 'Trace Flags'

Execution Plan Analysis: The Mystery Work Table

Paul White — Thu, 07 Mar 2013 19:42:04 GMT

I love SQL Server execution plans. It is often easy to spot the cause of a performance problem just by looking at one. The task is considerably easier if the plan includes run-time information (a so-called ‘actual’ execution plan), but even a compiled plan can be very useful. Nevertheless, there are still times where the execution plan does not tell the whole story, and we need to think more deeply about query execution to really understand a performance problem. This post looks at one such example, based on a recent question posted on the SQL Performance Q & A site.

The Execution Plan

This plan is reasonably large (20MB cached plan size) but not massively complex once you break it down (click on the image above to view it full-size in a new window). The context of the question is that this query usually executes in less than a minute, but sometimes it runs for nearly twenty minutes – though the plan appears identical.

High-Cost Operators

There are many different things to look for in execution plans. What you choose to look at first is as much a matter of personal preference as anything, but many people are drawn to high-cost operators, so I will start there. In this plan, the cost of one operator dominates all others, shown as being responsible for 100% of the cost of the query. It is highlighted in red in Plan Explorer; I have expanded the relevant plan section (the top right) below:

There is no doubt that this seek is busy little thing. It is executed 249,484 times, though it only produces a grand total of 167,813 rows over all iterations of the loop join – an average of just 0.7 rows per seek. There are all sorts of interesting details in the plan about this seek – I could write a whole blog post about it – but two details that stand out are the “Force Seek: True” and “Partitioned: True” attributes. These tell us that the base table is partitioned, and the query writer had to use a FORCESEEK table hint to get this plan.

Without this hint, the optimizer would almost certainly choose a Hash Match or Merge Join rather than Nested Loops. This is understandable given the optimizer’s cost model and the simplifying assumptions it makes (such as assuming every query starts with a cold buffer cache). That’s fine, but we can see from the query plan that the inner-side table has 643 million rows. Left to its own devices, the optimizer would estimate that it would be faster to perform a sequential scan of 643 million rows (with large-block read-ahead) than it would be to run a quarter-million randomly-distributed seeks driven by a Nested Loops join.

I doubt that the optimizer’s reasoning here is sound (at least on any reasonably modern hardware) but there we go. The query author probably knows that a good fraction of this table is likely to be in cache, so with all that in mind, I think we can reasonably assume at this stage that the FORCESEEK hint is genuinely needed here, and this part of the plan is at least reasonably optimal.

Important note: The seek certainly does not account for 100% of the runtime cost of this query. Remember cost percentages are always estimates – even in ‘actual’ plans. It can be useful to check the reasons for high-estimated-cost operators, but they should never be used as a primary tuning metric.

Execution Warnings

This query was executed on SQL Server 2012, so there is a handy warning triangle on the Sort operator indicating that one or more sort runs had to be spilled to physical tempdb disk. The plan clearly shows this spilling is a result of an inaccurate cardinality estimate at the Filter operator (the estimates are not bad at all prior to this). The Sort expects 9,217 rows totalling approximately 5MB, but actually encountered 61,846 rows in 35MB. As you may know, memory for sorts and hashes is allocated before execution starts, and generally cannot expand dynamically at run time.

The spilled sort is undesirable, of course, but it is unlikely to be a major cause of the occasional poor performance given the small size of the spilled data. Nevertheless, this might be a good place to split this query up. The idea would be to write the results of the query (up to and including the Filter) to a temporary heap table using SELECT INTO, and then create a clustered index with the same keys as the Sort operator. The temporary table would not be large, and may well perform better overall than the spilled sort, including the cost of creating the clustered index. Of course, creating this index will involve a sort, but it will be one based on the known cardinality of the temporary heap table. The part of the plan that could be replaced by a temporary table is shown below:

I am a big fan of simplifications like this. Smaller execution plans tend to optimize better for all sorts of reasons, and the source code usually becomes easier to maintain as well. I should mention there is another warning triangle in the 2012 execution plan (shown on the root icon), which relates to some implicit conversions that I will mention later.

I/O Information

The execution plan was captured with Plan Explorer, so we can also easily see I/O statistics for the two executions. The first is for a fast (sub-60-second) run:

Overall, these I/O numbers show pretty much what we would expect: a decent number of logical reads associated with the seeks into the Trans table (but certainly not 100% of the total, ha ha), a very small number of physical reads, and a small amount of read-ahead activity on a couple of tables.

The second set of I/O data is from a slow run (18 minutes or so):

The very obvious difference is the appearance of a work table, with 178 million logical reads and 130 million LOB logical reads. It seems very likely this work table, and its 300 million logical reads, is responsible for the dramatic decrease in query performance. But given that the execution plans are identical (right down to the XML) what is causing this?

My answer to that question (on the Q & A site) was that it is related to the increased level of read-ahead activity, but to see why that is the case, we will need to reproduce the issue and dig a bit deeper.

Execution Outline

Before we really get going on this, it will be useful to take a look at what the execution plan is doing in outline. We saw the first part of the plan earlier when looking at the spilling sort. The data set at that point (which we would like to write to a temporary table, remember) essentially represents source data for a second query, which uses a series of Nested Loops Left Joins to lookup information from other tables:

The inner side of each join involves some reasonably involved logic, which is thankfully not important to the present discussion. What is important is that the result of each lookup is a LOB data type. This begins to shed some light on the LOB logical reads reported against the work table, but it does not explain why the work table (and the 300 million associated reads) do not appear when the query runs quickly (with the same execution plan).

Reproducing the problem

Table Creation

The first part of the repro involves creating six tables that represent the lookup tables in the original query plan. Each table will have 10,000 rows, consisting of a sequential reference number and a second column containing a 2048 single-byte-character string. The source table used to drive the lookups will be a regular Numbers table containing just a single integer column.

     CREATE TABLE dbo.T1 (id integer IDENTITY PRIMARY KEY, d char(2048));

    CREATE TABLE dbo.T2 (id integer IDENTITY PRIMARY KEY, d char(2048));

    CREATE TABLE dbo.T3 (id integer IDENTITY PRIMARY KEY, d char(2048));

    CREATE TABLE dbo.T4 (id integer IDENTITY PRIMARY KEY, d char(2048));

    CREATE TABLE dbo.T5 (id integer IDENTITY PRIMARY KEY, d char(2048));

    CREATE TABLE dbo.T6 (id integer IDENTITY PRIMARY KEY, d char(2048));

    GO

    INSERT dbo.T1 WITH (TABLOCKX)

    SELECT REPLICATE('A', 2048)

    FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

    GO

    INSERT dbo.T2 WITH (TABLOCKX)

    SELECT REPLICATE('B', 2048)

    FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

    GO

    INSERT dbo.T3 WITH (TABLOCKX)

    SELECT REPLICATE('C', 2048)

    FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

    GO

    INSERT dbo.T4 WITH (TABLOCKX)

    SELECT REPLICATE('D', 2048)

    FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

    GO

    INSERT dbo.T5 WITH (TABLOCKX)

    SELECT REPLICATE('E', 2048)

    FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

    GO

    INSERT dbo.T6 WITH (TABLOCKX)

    SELECT REPLICATE('F', 2048)

    FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;

The next step is to ensure that each lookup table is optimally organized for read-ahead:

    ALTER TABLE dbo.T1 REBUILD WITH (MAXDOP = 1);

    ALTER TABLE dbo.T2 REBUILD WITH (MAXDOP = 1);

    ALTER TABLE dbo.T3 REBUILD WITH (MAXDOP = 1);

    ALTER TABLE dbo.T4 REBUILD WITH (MAXDOP = 1);

    ALTER TABLE dbo.T5 REBUILD WITH (MAXDOP = 1);

    ALTER TABLE dbo.T6 REBUILD WITH (MAXDOP = 1);

Test Query

The original query translates into our simplified test rig as:

    DECLARE @d nvarchar(max) = NCHAR(10000);

    SELECT n.n,

        DATALENGTH

        (

            CONCAT

            (

                (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T1 AS t WHERE t.id = n.n),

                (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T2 AS t WHERE t.id = n.n),

                (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T3 AS t WHERE t.id = n.n),

                (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T4 AS t WHERE t.id = n.n),

                (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T5 AS t WHERE t.id = n.n),

                (SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T6 AS t WHERE t.id = n.n)

            )

        )

    FROM dbo.Numbers AS n

    WHERE n.n BETWEEN 1 AND 10000

    ORDER BY n.n

    OPTION (LOOP JOIN, FORCE ORDER, MAXDOP 1);

The broad idea there is to concatenate our 2048-character column to itself five times and include a Unicode character that was used in the original query as a delimiter that could not appear in the source data. Each lookup performs the same basic operation against its target table, and the final result is the result of concatenating all the intermediate results. The query hints are necessary to get the right plan shape, just because my test rig tables are so much smaller than the real ones.

Note that the Unicode delimiter means the 2048-character single-byte data is implicitly converted to Unicode, doubling in size. It is not a crucial feature of the test, but it did appear in the original query and explains the type conversion warnings in the execution plan I mentioned earlier. The execution plan for the test query is (click to enlarge if necessary):

I should also stress that the CONCAT operator (new in SQL Server 2012) is not crucial either. If you are using an earlier version of SQL Server, an equivalent query (for present purposes) is shown below. I’m going to stick with CONCAT for the remainder of the post, however.

    DECLARE @d nvarchar(max) = NCHAR(10000);

    SELECT n.n,

        DATALENGTH

        (

            (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T1 AS t WHERE t.id = n.n) +

            (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T2 AS t WHERE t.id = n.n) +

            (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T3 AS t WHERE t.id = n.n) +

            (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T4 AS t WHERE t.id = n.n) +

            (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T5 AS t WHERE t.id = n.n) +

            (SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T6 AS t WHERE t.id = n.n)

        )

    FROM dbo.Numbers AS n

    WHERE n.n BETWEEN 1 AND 10000

    ORDER BY n.n

    OPTION (LOOP JOIN, FORCE ORDER, MAXDOP 1);

Warm cache results

With all data in memory, the test query (in either form) completes in about 1.6 seconds on my laptop. The result shows that each output row contains 147,468 bytes of Unicode character data. A typical set of I/O statistics follows:

Nothing too exciting to see there, but this is just our baseline.

Cold cache results

    CHECKPOINT;

    DBCC DROPCLEANBUFFERS;

With no data in memory, the test query now runs for 18.6 seconds – almost 12x slower. The I/O statistics show the expected (but still mysterious!) work table and its associated reads:

The Extended Events wait statistics show SQL Server spent very little of that time waiting on my laptop’s slow hard drive – just 402 ms:

Explanation

The are a number of factors in play here that we will look at in turn.

Nested Loops Prefetching

One of the reasons the optimizer prefers Hash Match and Merge Join for larger inputs is that the data access patterns tend to favour large sequential read-ahead. Both hash and merge tend to scan (range-scan in the case of a seek) their inputs, and the SQL Server Storage Engine automatically issues read-ahead when it detects this type of access. There is nothing in the execution plan to show that a base table will be read with read-ahead, it just happens.

A very basic implementation of Nested Loops join would not benefit from read-ahead at all on its inner side. The outer (driving) side of the loops join might well be a scan or range-scan of an index, and so benefit from automatic read-ahead, of course. The inner side is executed once per outer row, resulting in a rapid succession of small index seeks for different values. These small seeks will typically not be large enough to trigger the automatic read-ahead mechanism. Indeed, in our test, each inner side seek is for precisely one value.

SQL Server improves on this by implementing a second read-ahead mechanism especially for Nested Loops joins (not all N-L joins, it is a cost-based decision the optimizer makes). The basic idea is to buffer extra rows from the outer side of the join, and to use the row values in the buffer to drive read-ahead for the inner side. The effect is that the Nested Loops join becomes a partly blocking operator as outer-side rows are read into the buffer and read-ahead issued based on buffered index key values.

This read-ahead may be either order-preserving or not, and is indicated in the execution plan by the Nested Loop attributes With Ordered Prefetch and With Unordered Prefetch, respectively. When unordered prefetch occurs, the inner side is processed in whatever order the asynchronous reads happen to complete. With ordered prefetching, the mechanism is careful to ensure that the order of rows entering the join is preserved on the output.

In the test rig, the ORDER BY clause means there is a need to preserve row order, so Ordered Prefetch is used:

The issue described in this post is not specific to ordered prefetching – the same behaviour is just as likely with unordered prefetching. The point is that Nested Loops prefetching is one of the requirements.

Documented trace flags 652 and 8744 may be used (with care, and after serious testing) to disable automatic read-ahead and Nested Loops prefetching respectively. This is sometimes beneficial where all data is expected to be in memory (in which case read-ahead processing consumes resources better used by query execution) or where the I/O subsystem is extremely fast. In case you were wondering, there is no background thread for prefetching – all the work of checking whether the data is in memory, and issuing I/O if not, is performed by the worker thread executing the query.

I should stress that read-ahead and Nested Loops prefetching is generally A Very Good Thing with typical storage solutions (e.g. SANs) and both work best (or at all) when indexes have low logical fragmentation.

Manufactured LOBs

The issue described here also requires that a large object data type is manufactured before prefetching. The Compute Scalar operators in the test execution plan perform that function:

By ‘manufactured’, I mean that the source columns are not LOB types, but the expression output is – notice the implicit conversion to nvarchar(max). To be clear about it, the issue we are analysing here does not occur when Nested Loops prefetching occurs with an expression that was a LOB type to begin with.

The Outer Join

The optimizer is quite good, generally speaking, at moving scalar expressions around. If the query had featured inner joins (whether by query design or through optimizer activities) the chances are quite good that the problematic expressions (the LOB manufacturers) would have moved beyond the prefetching, and so out of harm’s way. It is quite tricky to preserve NULL-extension and other outer-join semantics properly when moving expressions above an outer join, so the optimizer generally does not even try. In essence, the outer join represents an optimization barrier to the LOB-manufacturing expressions.

Memory Allocation

When Nested Loops prefetching occurs with a manufactured LOB, the question arises of where to store the created LOBs when buffering rows for prefetch. If the source data were already a LOB type, the execution engine would already have memory structures in place to handle them. When prefetching encounters a manufactured LOB, it needs to store it somewhere, since the engine is no longer processing a stream of one row at a time. It turns out that there is a small memory buffer set aside for this eventuality, which empirical tests show to be 24KB.

However, this 24KB (directly allocated, not via workspace memory grant) is shared across all concurrently executing prefetching joins in the query. With six such joins in the test rig plan and large manufactured LOBs, the buffer stands no chance. As a result, query execution engages a bail-out option: a work table created in tempdb. Though the pages of the worktable may in fact remain memory-resident, overheads (including latching and using general-purpose code interfaces for access to the buffered rows) mean this is very much slower than using the direct-memory cache.

As with most internal work tables, the logical reads reported on this work table indicate the number of rows processed (not 8KB pages, as for regular I/O statistics). This fact, together with the large number of items processed via the worktable in our test, accounts for the millions of reads reported.

The creation and use of the work table depends on run time conditions and timing. If execution finds the data it needs is already in memory, the prefetch checks are still performed, but no asynchronous read requests end up being posted. The 24KB buffer is never filled, so the need to create a work table never arises. The more prefetch that actually occurs, the higher the chances that the buffer will fill. It is quite possible to experience a low level of prefetch with manufactured LOBs without the engine needing to bail out to a work table, especially if the LOBs are not very big and the I/O system is quite fast.

Workaround

We can rewrite the query to avoid feeding manufactured LOB data to the prefetch buffer. The idea is to use OUTER APPLY to return the data that contributes to the concatenation, rather than the result of the concatenation. We can then perform the CONCAT operation (which handles NULLs nicely without extra work) after the join, avoiding the prefetch buffer issue completely. In SQL Server versions prior to 2012, we would need to use direct string concatenation, and handle rows that are NULL-extended explicitly using ISNULL or COALESCE.

    DECLARE @d nvarchar(max) = NCHAR(10000);

    SELECT 

        n.n,

        DATALENGTH

        (

            CONCAT

            (

                CONCAT(oa1.i0, oa1.i1, oa1.i2, oa1.i3, oa1.i4, oa1.i5, oa1.i6),

                CONCAT(oa2.i0, oa2.i1, oa2.i2, oa2.i3, oa2.i4, oa2.i5, oa2.i6),

                CONCAT(oa3.i0, oa3.i1, oa3.i2, oa3.i3, oa3.i4, oa3.i5, oa3.i6),

                CONCAT(oa4.i0, oa4.i1, oa4.i2, oa4.i3, oa4.i4, oa4.i5, oa4.i6),

                CONCAT(oa5.i0, oa5.i1, oa5.i2, oa5.i3, oa5.i4, oa5.i5, oa5.i6),

                CONCAT(oa6.i0, oa6.i1, oa6.i2, oa6.i3, oa6.i4, oa6.i5, oa6.i6)

            )

        )

    FROM dbo.Numbers AS n

    OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T1 AS t WHERE t.id = n.n) AS oa1

    OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T2 AS t WHERE t.id = n.n) AS oa2

    OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T3 AS t WHERE t.id = n.n) AS oa3

    OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T4 AS t WHERE t.id = n.n) AS oa4

    OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T5 AS t WHERE t.id = n.n) AS oa5

    OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T6 AS t WHERE t.id = n.n) AS oa6

    WHERE n.n BETWEEN 1 AND 10000

    ORDER BY n.n

    OPTION (LOOP JOIN, FORCE ORDER, MAXDOP 1);

The execution plan for the rewritten query looks visually similar to the problematic one:

However, the Compute Scalars no longer manufacture a LOB data type, they just emit column and variable references:

All the concatenation work (and LOB manufacture) is performed by the final top-level Compute Scalar in a single monster expression [Expr1056]:

Warm cache results

With all data in memory, the new query completes in 1.8 seconds (very slightly up on 1.6 seconds before):

Cold cache results

When all data must be fetched from disk, the query issues optimal prefetching and completes in 7.3 seconds (down from 18.6 seconds) with no work table:

The Extended Events wait statistics now show 3.8 seconds spent waiting for my laptop’s slow spinning disk (which is a good thing!)

Final Thoughts

Work tables can appear in STATISTICS IO output for a wide range of reasons, but if you encounter one with a very large number of reads – particularly LOB reads – you may be encountering this issue. The rewrite proposed above may not always be possible, but you should be able to refactor your query to avoid the issue now you know it exists.

I am not a fan of doing large amounts of string manipulation in SQL Server. I am always particularly suspicious of the perceived need to split or concatenate large volumes of strings.

I am, however, a fan of always using explicit data types (rather than relying on implicit conversions) and generating relatively small query plans that offer the query optimizer clear and obvious choices. By necessity, this often means writing small SQL queries in logical steps (and no, long chains of common table expressions do not count!)

The real world does not always make these things possible, of course, but it is good to have goals :)

Screenshots acquired using SnagIt by TechSmith
Query plan details obtained using Plan Explorer PRO by SQLSentry

MERGE Bug with Filtered Indexes

Paul White — Sun, 09 Dec 2012 17:54:00 GMT

A MERGE statement can fail, and incorrectly report a unique key violation when:

The target table uses a unique filtered index; and
No key column of the filtered index is updated; and
A column from the filtering condition is updated; and
Transient key violations are possible

Example Tables

Say we have two tables, one that is the target of a MERGE statement, and another that contains updates to be applied to the target. The target table contains three columns, an integer primary key, a single character alternate key, and a status code column. A filtered unique index exists on the alternate key, but is only enforced where the status code is ‘a’:

     CREATE TABLE #Target 

    (

        pk          integer NOT NULL, 

        ak          character(1) NOT NULL,

        status_code character(1) NOT NULL,

        PRIMARY KEY (pk)

    );

    CREATE UNIQUE INDEX uq1

    ON #Target (ak)

    INCLUDE (status_code)

    WHERE status_code = 'a';

The changes table contains just an integer primary key (to identify the target row to change) and the new status code:

    CREATE TABLE #Changes

    (

        pk          integer NOT NULL,

        status_code character(1) NOT NULL,

        PRIMARY KEY (pk)

    );

Sample Data

The sample data for the example is:

    INSERT #Target 

        (pk, ak, status_code)

    VALUES 

        (1, 'A', 'a'),

        (2, 'B', 'a'),

        (3, 'C', 'a'),

        (4, 'A', 'd');

    INSERT #Changes

        (pk, status_code)

    VALUES

        (1, 'd'),

        (4, 'a');

         Target                     Changes
╔════╦════╦═════════════╗    ╔════╦═════════════╗
║ pk ║ ak ║ status_code ║    ║ pk ║ status_code ║
╠════╬════╬═════════════╣    ╠════╬═════════════╣
║ 1 ║ A ║ a           ║    ║ 1 ║ d           ║
║ 2 ║ B ║ a           ║    ║ 4 ║ a           ║
║ 3 ║ C ║ a           ║    ╚════╩═════════════╝
║ 4 ║ A ║ d           ║
╚════╩════╩═════════════╝

The target table’s alternate key (ak) column is unique, for rows where status_code = ‘a’. Applying the changes to the target will change row 1 from status ‘a’ to status ‘d’, and row 4 from status ‘d’ to status ‘a’. The result of applying all the changes will still satisfy the filtered unique index, because the ‘A’ in row 1 will be deleted from the index and the ‘A’ in row 4 will be added.

Merge Test One

Let’s now execute a MERGE statement to apply the changes:

    MERGE #Target AS t

    USING #Changes AS c ON 

        c.pk = t.pk

    WHEN MATCHED 

        AND c.status_code <> t.status_code 

        THEN UPDATE SET status_code = c.status_code;

The MERGE changes the two target rows as expected. The updated target table now contains:

╔════╦════╦═════════════╗
║ pk ║ ak ║ status_code ║
╠════╬════╬═════════════╣
║ 1 ║ A ║ d           ║ <—changed from ‘a’
║ 2 ║ B ║ a           ║
║ 3 ║ C ║ a           ║
║ 4 ║ A ║ a           ║ <—changed from ‘d’
╚════╩════╩═════════════╝

Merge Test Two

Now let’s repopulate the changes table to reverse the updates we just performed:

    TRUNCATE TABLE #Changes;

    INSERT #Changes

        (pk, status_code)

    VALUES

        (1, 'a'),

        (4, 'd');

This will change row 1 back to status ‘a’ and row 4 back to status ‘d’. As a reminder, the current state of the tables is:

         Target                        Changes
╔════╦════╦═════════════╗    ╔════╦═════════════╗
║ pk ║ ak ║ status_code ║    ║ pk ║ status_code ║
╠════╬════╬═════════════╣    ╠════╬═════════════╣
║ 1 ║ A ║ d           ║    ║ 1 ║ a           ║
║ 2 ║ B ║ a           ║    ║ 4 ║ d           ║
║ 3 ║ C ║ a           ║    ╚════╩═════════════╝
║ 4 ║ A ║ a           ║
╚════╩════╩═════════════╝

We execute the same MERGE statement:

    MERGE #Target AS t

    USING #Changes AS c ON 

        c.pk = t.pk

    WHEN MATCHED 

        AND c.status_code <> t.status_code 

        THEN UPDATE SET status_code = c.status_code;

However this time we receive the following message:

Msg 2601, Level 14, State 1, Line 1
Cannot insert duplicate key row in object 'dbo.#Target' with unique index 'uq1'. The duplicate key value is (A).
The statement has been terminated.

Applying the changes using UPDATE

Let’s now rewrite the MERGE to use UPDATE instead:

    UPDATE t

    SET status_code = c.status_code

    FROM #Target AS t

    JOIN #Changes AS c ON

        t.pk = c.pk

    WHERE

        c.status_code <> t.status_code;

This query succeeds where the MERGE failed. The two rows are updated as expected:

╔════╦════╦═════════════╗
║ pk ║ ak ║ status_code ║
╠════╬════╬═════════════╣
║ 1 ║ A ║ a           ║ <—changed back to ‘a’
║ 2 ║ B ║ a           ║
║ 3 ║ C ║ a           ║
║ 4 ║ A ║ d           ║ <—changed back to ‘d’
╚════╩════╩═════════════╝

What went wrong with the MERGE?

In this test, the MERGE query execution happens to apply the changes in the order of the ‘pk’ column.

In test one, this was not a problem: row 1 is removed from the unique filtered index by changing status_code from ‘a’ to ‘d’ before row 4 is added. At no point does the table contain two rows where ak = ‘A’ and status_code = ‘a’.

In test two, however, the first change was to change row 1 from status ‘d’ to status ‘a’. This change means there would be two rows in the filtered unique index where ak = ‘A’ (both row 1 and row 4 meet the index filtering criteria ‘status_code = a’).

The storage engine does not allow the query processor to violate a unique key (unless IGNORE_DUP_KEY is ON, but that is a different story, and doesn’t apply to MERGE in any case). This strict rule applies regardless of the fact that if all changes were applied, there would be no unique key violation (row 4 would eventually be changed from ‘a’ to ‘d’, removing it from the filtered unique index, and resolving the key violation).

Why it went wrong

The query optimizer usually detects when this sort of temporary uniqueness violation could occur, and builds a plan that avoids the issue. I wrote about this a couple of years ago in my post Beware Sneaky Reads with Unique Indexes (you can read more about the details on pages 495-497 of Microsoft SQL Server 2008 Internals or in Craig Freedman’s blog post on maintaining unique indexes). To summarize though, the optimizer introduces Split, Filter, Sort, and Collapse operators into the query plan to:

Split each row update into delete followed by an inserts
Filter out rows that would not change the index (due to the filter on the index, or a non-updating update)
Sort the resulting stream by index key, with deletes before inserts
Collapse delete/insert pairs on the same index key back into an update

The effect of all this is that only net changes are applied to an index (as one or more insert, update, and/or delete operations). In this case, the net effect is a single update of the filtered unique index: changing the row for ak = ‘A’ from pk = 4 to pk = 1. In case that is less than 100% clear, let’s look at the operation in test two again:

         Target                     Changes                   Result
╔════╦════╦═════════════╗    ╔════╦═════════════╗    ╔════╦════╦═════════════╗
║ pk ║ ak ║ status_code ║    ║ pk ║ status_code ║    ║ pk ║ ak ║ status_code ║
╠════╬════╬═════════════╣    ╠════╬═════════════╣    ╠════╬════╬═════════════╣
║ 1 ║ A ║ d           ║    ║ 1 ║ d           ║    ║ 1 ║ A ║ a           ║
║ 2 ║ B ║ a           ║    ║ 4 ║ a           ║    ║ 2 ║ B ║ a           ║
║ 3 ║ C ║ a           ║    ╚════╩═════════════╝    ║ 3 ║ C ║ a           ║
║ 4 ║ A ║ a           ║                            ║ 4 ║ A ║ d           ║
╚════╩════╩═════════════╝                            ╚════╩════╩═════════════╝

From the filtered index’s point of view (filtered for status_code = ‘a’ and shown in nonclustered index key order) the overall effect of the query is:

Before           After
╔════╦════╗    ╔════╦════╗
║ pk ║ ak ║    ║ pk ║ ak ║
╠════╬════╣    ╠════╬════╣
║ 4 ║ A ║    ║ 1 ║ A ║
║ 2 ║ B ║    ║ 2 ║ B ║
║ 3 ║ C ║    ║ 3 ║ C ║
╚════╩════╝    ╚════╩════╝

The single net change there is a change of pk from 4 to 1 for the nonclustered index entry ak = ‘A’. This is the magic performed by the split, sort, and collapse. Notice in particular how the original changes to the index key (on the ‘ak’ column) have been transformed into an update of a non-key column (pk is included in the nonclustered index). By not updating any nonclustered index keys, we are guaranteed to avoid transient key violations.

The Execution Plans

The estimated MERGE execution plan that produces the incorrect key-violation error looks like this (click to enlarge in a new window):

The successful UPDATE execution plan is (click to enlarge in a new window):

The MERGE execution plan is a narrow (per-row) update. The single Clustered Index Merge operator maintains both the clustered index and the filtered nonclustered index. The UPDATE plan is a wide (per-index) update. The clustered index is maintained first, then the Split, Filter, Sort, Collapse sequence is applied before the nonclustered index is separately maintained.

There is always a wide update plan for any query that modifies the database. The narrow form is a performance optimization where the number of rows is expected to be relatively small, and is not available for all operations. One of the operations that should disallow a narrow plan is maintaining a unique index where intermediate key violations could occur.

Workarounds

The MERGE can be made to work (producing a wide update plan with split, sort, and collapse) by:

Adding all columns referenced in the filtered index’s WHERE clause to the index key (INCLUDE is not sufficient); or
Executing the query with trace flag 8790 set e.g. OPTION (QUERYTRACEON 8790).

Undocumented trace flag 8790 forces a wide update plan for any data-changing query (remember that a wide update plan is always possible). Either change will produce a successfully-executing wide update plan for the MERGE that failed previously.

Conclusion

The optimizer fails to spot the possibility of transient unique key violations with MERGE under the conditions listed at the start of this post. It incorrectly chooses a narrow plan for the MERGE, which cannot provide the protection of a split/sort/collapse sequence for the nonclustered index maintenance.

The MERGE plan may fail at execution time depending on the order in which rows are processed, and the distribution of data in the database. Worse, a previously solid MERGE query may suddenly start to fail unpredictably if a filtered unique index is added to the merge target table at any point.

Connect bug filed here

Bug reproduced on the following SQL Server versions (all x64 Developer Edition):

2012 SP1 CUI (build 11.0.3321 – November 2012)
2008 R2 SP2 CU3 (build 10.50.4266 – October 2012)
2008 SP3 CU8 (build 10.0.5828 – November 2012)

Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com

Query Optimizer Deep Dive - Part 4

Paul White — Mon, 30 Apr 2012 13:36:00 GMT

This is the final part in a series of posts based on the content of the Query Optimizer Deep Dive presentations I have given over the last month or so at the Auckland SQL Users’ Group and the SQL Saturday events in Wellington, New Zealand and Adelaide, Australia.

Links to other parts of this series: Part 1 Part 2 Part 3

Beating the Optimizer

Our test query produces an optimized physical execution plan that is quite different from the logical form of the query. The estimated cost of the execution plan shown below is 0.0295 units.

Since we know the database schema very well, we might wonder why the optimizer did not choose to use the unique nonclustered index on names in the product table to filter rows based on the LIKE predicate. We could use an index hint to force the name index to be used:

That’s great, and no doubt the index seek is cheaper than the scan we had previously, but the optimizer has still chosen to use a merge join, and that means having both inputs sorted on Product ID. The result of the index seek is ordered by name (the index key) rather than Product ID, so a sort is required. It looks like the new sort adds a little more cost than the seek saves over the scan, because the estimated cost of the query plan with the index hint is 0.0316 units.

Naturally, these numbers are rather small since AdventureWorks is not a large database, but these differences can be important in real systems. Anyway, let’s persist with the index seek idea; why is the optimizer so keen on a merge join, even though it involves an extra sort, and we don’t have an ORDER BY Product ID clause on our query? Without a top-level ORDER BY, we are giving the optimizer the freedom to return results in any order that is convenient – perhaps we can do better by forcing the index seek and a hash join instead of a merge join?

Well the sort has gone, so the plan looks visually a little simpler, but the estimated cost has increased again, to 0.0348 units. Hash join has quite a high start-up cost (and it requires a memory workspace grant). We could try other things, but it certainly seems that the optimizer had it right to begin with in this case.

The manual exploration above shows that the optimizer does generally find a good plan quickly (and sometimes it may even find the best possible plan). The terms ‘good’ and ‘best’ here are measured in terms of the optimizer’s own cost model. Whether one particular plan shape actually executes faster on a given system is another question. I might find, for example, that the first merge join plan runs fastest for me, whereas you might find the seek and sort runs fastest for you. We might both find that which is faster depends on whether the indexes and data needed are in memory or need to be retrieved from persistent storage. All these things aside, the important thing is that we are both likely to find that the optimizer’s plans are pretty good most of the time.

Models and Limitations

There are three principal models used by the optimizer to provide a basis for its reasoning: cardinality estimation, logical relational equivalences, and physical operator costing. Good cardinality estimation (row count expectations at each node of the logical tree) is vital; if these numbers are wrong, all later decisions are suspect. Fortunately, it is relatively easy to check cardinality estimation by comparing actual and estimated row counts in query plans. There are some subtleties to be aware of – for example when interpreting the inner side of a nested loops join, at least in SSMS. If you use the free SQL Sentry Plan Explorer tool, many of these common misinterpretations are handled for you.

The model used in cardinality estimation is complex, and contains all sorts of hairy-looking formulas and calculations. Nevertheless, it is still a model, and as such will deviate from reality at least to some extent. I’ll have more to say later on about what we can do to help ensure good cardinality estimates, but for now we will just note that the model has its roots in relational theory and statistical analysis.

Relational equivalences (such as A inner join B = B inner join A) are the basis for exploration rules in the cost-based optimizer. Not all possible relational transformations are included in the product (remember the goal of the optimizer is to find a good plan quickly, not to perform an exhaustive search of all possible plans). As a consequence, the SQL syntax you use will often affect the plan produced by the optimizer, even where different SQL syntaxes express the same logical requirement. Also, the skilled query tuner will often be able to do better than the optimizer, given enough time and perhaps a better insight to the data. The downside of such manual tuning is that it will usually require manual intervention again in the future as data volumes and distributions change.

Physical operator costing is very much the simplest of the three models, using formulas that have been shown to produce good physical plan selections for a wide range of queries on a wide range of hardware. The numbers used probably do not closely model your hardware or mine, but luckily that turns out not to be too important in most cases. No doubt the model will have to be updated over time as new hardware trends continue to emerge, and there is some evidence in SQL Server 2012 show plan output that things are heading in that direction.

Assumptions

All models make simplifying assumptions, and the cardinality estimation and costing models are no different. Some things are just too hard to model, and other things just haven’t been incorporated into the model yet. Still other things could be modelled, but turn out not to add much value in practice and cost too much in terms of complexity or resource consumption. Some of the major simplifying assumptions that can affect real plan quality are:

All queries start executing with a cold cache
This isn’t as crazy as it sounds. Fetching data from disk tends to dominate the overall cost of a query, modelling the amount of data that can be expected to be in cache already is hard, and this assumption does at least affect everything equally. The optimizer does contain some logic to account for pages that might be in cache after the first access.
Statistical information is independent
Correlations do frequently exist between columns in real databases, so this assumption can be problematic. Multi-column statistics, filtered indexes, and indexed views can sometimes help with this.
Distribution is uniform
This is assumed where the system has no information to the contrary. One example: costing assumes that seeks (lookups) into an index are randomly distributed throughout the full range of the index.

Helping the Optimizer

There are three approaches to working with the optimizer:

Ignore it. It works well out of the box with default settings and automatic statistics.
Override it using syntax tricks, hints, and plan guides.
Provide it with the best information you can, and override it for just a small number of problematic queries.

All three are valid approaches in different circumstances, though the third option is probably the one to recommend as the best starting point. There is much more to helping the optimizer than just making sure statistics are up-to-date, however:

Use a relational design

This is probably the biggest single item. The various models all assume that your database has a reasonably relational design, not necessarily 3NF or higher, but the closer your structures are to relational principles, the better. Cardinality estimation works best with simpler relational operations like joins, projects, selects, unions and group by. Avoid complex expressions and non-relational query features that force cardinality estimation to guess. Also remember that the cost-based optimizer’s exploration rules are based on relational equivalences, so having a relational design and writing relational queries gives you the best chance of leveraging the hard work that has gone into those rules. Some features added in 2005 (e.g. ranking functions) operate on sequences rather than multi-sets (hence the Sequence Project physical operator); the original rules all work with multi-sets, and the seams between the two approaches often show though.

Use constraints

Use check constraints, foreign keys, unique constraints to provide the optimizer with information about your data. Simplification and exploration rules match patterns in the logical tree, and may also require certain properties to be set on the matched nodes. Constraints and keys provide some of the most powerful and fundamental logical properties – omitting these can prevent many of the optimizer’s rules from successfully transforming to an efficient physical plan. If an integer column should only contain certain values, add a check constraint for it. If a foreign key relationship exists, enforce it. If a key exists, declare it. It is not always possible to predict the benefits of providing this type of optimizer information, but my own experience is that it is much greater than most people would ever expect.

Statistics, indexes and computed columns

Provide more than just default-sampled automatically-created statistics where appropriate (for example where distribution is unusual or correlations exist). Create indexes that will provide potentially useful access paths for a wide range of queries. If you have expressions on columns in your WHERE clause, consider adding a computed column that matches the expression exactly. The computed column does not have to be persisted or indexed to be useful; the system can auto-create statistics on the computed column, avoiding cardinality guessing.

Deep Trees

Large, complex queries produce large, complex logical trees. Any errors tend to multiply (perhaps exponentially) as the size of the tree increases, the search space of possible plans expands greatly, and things just become much more difficult in general. Breaking a complex query into smaller, simpler, more relational, steps will generally get greater value out of the optimizer. A side benefit is that small intermediate results stored in a temporary table can have statistics created, which will also help in many cases. There will always be cases where a large complex query is required for ultimate performance, but very often the performance difference is relatively small and may not be worth the future maintenance costs as hand-tuned monolithic queries tend to be fragile.

Opaque operators and new features

User-defined functions (other than the in-line variety) may seem convenient, but they are almost completely opaque to the optimizer – it has to guess at the cardinality and distribution of rows produced. Newer features also tend to have much shallower support in the engine than longer-established features that have been around for multiple versions of the product. By all means use all the shiny new features, just be aware that combining them may produce plans of variable quality.

Trace Flags

To summarize the flags used in this series (all assume 3604 is also active):

7352 : Final query tree
8605 : Converted tree
8606 : Input, simplified, join-collapsed, and normalized trees
8607 : Output tree
8608 : Initial memo
8615 : Final memo
8675 : Optimization stages and times

The above were used in the presentation because they all work from 2005 to 2012. There are a large number of other optimizer-related flags (some of which only work on 2012). Some are listed below for people that like this sort of thing:

2373 : Memory before and after deriving properties and rules (verbose)
7357 : Unique hash optimization used
8609 : Task and operation type counts
8619 : Apply rule with description
8620 : Add memo arguments to 8619
8621 : Rule with resulting tree

As usual, these are undocumented, and unsupported (including by me!) and purely for educational purposes. Use with care at your own risk.

Final Thoughts

I hope you have gained some insight and intuition for the workings of the query optimizer: logical trees, simplification, cardinality estimation, logical exploration and physical implementation. The geeky internals stuff is fun, of course, but I rather hope people came away from these sessions with a better understanding of how query text is transformed to an executable plan, and how relational designs and simpler queries can help the optimizer work well for you. Taking advantage of the optimizer frees up time for more productive things – new projects, tuning the odd interesting query, whatever it is you would rather be doing than fighting the same query-tuning battles over and over again.

There are some great resources out there to learn more about SQL Server. Make full use of them to continue to improve your technical skills and just as importantly, experiment with things to build your experience level. Take a deeper look at query plans and the properties they contain; there is a wealth of information there that sometimes requires a bit of thinking and research to understand, but the insights can be invaluable.

The original slides and demo code is again attached as a zip file below. Thanks for reading, all comments and feedback are very welcome.

Finally, I would like to thank Adam Machanic (blog | twitter) for introducing me to the QUERYTRACEON syntax all that time ago, and Fabiano Amorim (blog | twitter) for his email last year that kick-started the process of developing this presentation and blog series.

Links to other parts of this series: Part 1 Part 2 Part 3

Query Optimizer Deep Dive – Part 3

Paul White — Sun, 29 Apr 2012 07:30:00 GMT

This is the third part in a series of posts based on the content of the Query Optimizer Deep Dive presentations I have given over the last month or so at the Auckland SQL Users’ Group and the SQL Saturday events in Wellington, New Zealand and Adelaide, Australia.

Links to other parts of this series: Part 1 Part 2 Part 4

Storage of Alternative Plans

We saw in part 2 how optimizer rules are used to explore logical alternatives for parts of the query tree, and how implementation rules are used to find physical operations to perform each logical steps. To keep track of all these options, the cost-based part of the SQL Server query optimizer uses a structure called the Memo. This structure is part of the Cascades general optimization framework developed by Goetz Graefe. The Memo provides an efficient way to store many plan alternatives via the use of groups.

Each group in the Memo initially contains just one entry – a node from the input logical tree. As exploration and implementation phases progress, new groups may be added, and new physical and logical alternatives may be added to existing groups (all alternatives in a group share the same logical properties, but will often have quite different physical properties). Groups are also shared between plan alternatives where possible, allowing Cascades to search more plans in the same time and space compared with other optimization frameworks.

Continuing with our example query, the input tree to cost-based optimization is first copied into the Memo structure. We can see this structure using trace flag 8608:

     USE AdventureWorks2008R2;

    GO

    SET NOCOUNT ON;

    DBCC FREEPROCCACHE;

    DBCC TRACEON(3604);

    GO

    -- Initial memo contents

    SELECT

        p.Name,

        Total = SUM(inv.Quantity)

    FROM Production.Product AS p

    JOIN Production.ProductInventory AS inv ON

        inv.ProductID = p.ProductID

    WHERE

        p.Name LIKE N'[A-G]%'

    GROUP BY

        p.Name

    OPTION (QUERYTRACEON 8608);

As a reminder, this is the logical input tree to cost-based optimization shown in part 2:

This is copied to the Memo, one group per logical node, illustrated below:

The group numbers and linked structure shown are obtained directly from the trace flag output:

Each group has an entry number (all zero above since there is only one logical entry per group at this stage), with a logical operation (e.g. LogOp_Join), and the group numbers of any child groups (e.g. the logical join in group 13 references its two inputs, groups 8 and 9, and a logical comparison defined by the sub-tree starting at group 12).

Optimization Phases

One the initial Memo has been populated from the input tree, the optimizer runs up to four phases of search. There is a documented DMV, sys.dm_exec_query_optimizer_info, that contains a number of counters specific to query optimization. Four of these counters are ‘trivial plan’, search 0’, ‘search 1’, and ‘search 2’. The value for each counter keeps track of the number of times a search phase was entered. By recording the values before and after a specific optimization, we can see which phases were entered. The current counter values on one of my test SQL Server instances is shown below, as an example:

We look at each of the four phases in a bit more detail next:

Search 0 – Transaction Processing

This phase is primarily concerned with finding good plans for OLTP-type queries, which usually join a number of tables using a navigational strategy (looking up a relatively small number of rows using an index). This phase primarily considers nested-loops joins, though hash match may be used when a loops join implementation is not possible. Many of the more advanced (and costly to explore) optimizer rules are not enabled during this search phase – for example search 0 never considers indexed view matching or parallel plans.

Search 1 – Quick Plan (also known as Complex Query I)

This search phase can use most or all of the available rules, can perform limited join reordering, and may be run a second time (to consider parallel plans only) if the first run produces a plan with a high enough cost. Most queries find a final plan during one of the Search 1 runs.

Search 2 – Full Optimization

This phase uses the most comprehensive search configuration, and may result in significant compilation times in some cases. The search is either for a serial or parallel plan, depending on which type was cheaper after search 1.

The scripts accompanying this series show another way to see which phases were run, using trace flag 8675. The output provides some extra insight into how things work (for example it shows the number of optimization moves (tasks) made in each stage). The only documented and supported way to see the search phases is via the DMV, however.

Entry and Termination Conditions

Each phase has entry conditions, a set of enabled rules, and termination conditions. Entry conditions mean that a phase may be skipped altogether; for example, search 0 requires at least three joined tables in the input tree. Termination conditions help to ensure the optimizer does not spend more time optimizing than it saves – if the current lowest plan cost drops below a configured value, the search will terminate early with a ‘Good Enough Plan Found’ result.

The optimizer also sets a budget at the start of a phase for the number of optimization ‘moves’ it considers sufficient to find a pretty good plan (remember the optimizer’s goal is to find a good enough plan quickly). If the process of exploring and implementing alternatives exceeds this ‘budget’ during a phase, the phase terminates with a ‘Time Out’ message. Early termination (for whatever reason) is part of the optimizer’s design, completely normal, and not generally a cause for concern.

From time to time, we might wish that the optimizer had different goals – perhaps that we could ask it to continue searching for longer – but this is not how it works. It is all too easy to over-spend on optimization (finding transformations is not hard – finding ones that are robustly useful in a wide range of circumstances is), and full cost-based exploration is a memory and processor-intensive operation. The optimizer contains many heuristics, checks and limits to avoid exploring unpromising alternatives, to prune the search space as it goes, and ultimately produce a pretty good plan pretty quickly, most of the time, on most hardware, in most databases.

Costing

First a quick summary: The optimizer runs up to four phases, each of which performs exploration using rules (finding new logical alternatives to some part of the tree), then a round of implementation rules (finding physical implementations for a logical part of the tree). New logical or physical alternatives are added to the Memo structure – either as an alternative within an existing group, or as a completely new group. Note that the Memo allows the optimizer to consider very many alternatives at once in a compact and quick-to-search structure; the optimizer does not just work on one overall plan, performing incremental improvements (this is a common misconception).

Having found all these alternatives, the optimizer needs a way to choose between them. Costing runs after each round of implementation rules, producing a cost value for each physical alternative in each group in the memo (only physical operations can be costed, naturally). Costing considers factors like cardinality, average row size, expected sequential and random I/O operations, processor time, buffer pool memory requirements, and the effect of parallel execution.

Like many areas of optimization, the costing calculations are based on a complex mathematical model. This model generally provides a good basis on which to compare alternatives internally, regardless of the workload or particular hardware configuration. The costing numbers do not mean very much by themselves, so it is generally unwise to compare them between statements or across different queries. The numbers are perhaps best thought of as a unit-less quantity, useful only when comparing alternative plans for the same statement.

The model is just that of course: a model, albeit one that happens to produce very good results for most people most of the time. The slide deck that accompanies this series contains details of some of the simplifying assumptions made in the model.

Final Memo Contents

At the end of each search phase, the Memo may have expanded to include new logical and physical alternatives for each group, perhaps some completely new groups. We can see the contents after each phase using trace flag 8615:

    -- Final memo

    SELECT

        p.Name,

        Total = SUM(inv.Quantity)

    FROM Production.Product AS p

    JOIN Production.ProductInventory AS inv ON

        inv.ProductID = p.ProductID

    WHERE

        p.Name LIKE N'[A-G]%'

    GROUP BY

        p.Name

    OPTION (RECOMPILE, QUERYTRACEON 8615);

The final Memo (after each phase, remember) can be quite large, despite the techniques employed to constrain the search space. Our simple test query only requires a single run through search 1, and terminates early after 509 moves (tasks) with a ‘Good Enough Plan Found’ message. Despite that, the Memo contains 38 groups (up from 18) with many groups containing several alternatives. The extract below highlights just the groups that relate directly to the join implementation:

Looking at the green shaded areas, group 13 item 0 was the original (joining groups 8 and 9 and applying the condition described by the sub-tree starting with group 12). It has gained an logical alternative (via the Join Commute rule, reversing the join input groups), and two surviving physical implementations: a one-to-many merge join as item 7, with group 8 option 2 as the first input, and group 9 option 2 as the second; and a physical inner Apply driven by group 8 option 6, on group 30 option 2. Group 20 is completely new – another one-to-many merge join option, but this time with inputs from groups 19.4 and 8.2 with 12 familiar as the join condition. Again, the scripts accompanying this series can be used to explore the details further, if you wish.

The final selected plan consists of physical implementations chosen by starting with the lowest-cost physical option in the root group (18, shaded pink above). The sub-tree from that point has a total estimated cost of 0.0295655 (this is the same cost shown in the final graphical execution plan). The plan is produced by following the links in the Memo, from group 18 option 4, to group 20 option 6, and so on to the leaves:

End of Part 3

The original slides and demo code are attached below as a zip file.

Links to other parts of this series: Part 1 Part 2 Part 4

Query Optimizer Deep Dive – Part 2

Paul White — Sat, 28 Apr 2012 04:56:00 GMT

This is the second part in a series of posts based on the content of the Query Optimizer Deep Dive presentations I have given over the last month or so at the Auckland SQL Users’ Group and the SQL Saturday events in Wellington, New Zealand and Adelaide, Australia.

Links to other parts of this series: Part 1 Part 3 Part 4

Cost-Based Optimization Overview

The input to cost-based optimization is a tree of logical operations produced by the previous optimization stages discussed in part one. Cost-based optimization takes this logical tree, explores logical alternatives (different logical tree shapes that produce the same results), generates physical implementations, assigns an estimated cost to each, and finally chooses the cheapest physical option overall.

The goal of cost-based optimization is not to find the best possible physical execution plan by exploring every possible alternative; rather, the goal is to find a good plan quickly. This approach gives us an optimizer that works pretty well for most workloads, most of the time. If you think about it, that’s quite an achievement – after all, my database is likely very different from yours, and we probably run on quite different hardware as well. The point about finding a good plan quickly is also important – generally, we would not want the optimizer to spend hours optimizing a query that runs for only a few seconds.

This design has a number of important consequences. First, a skilled query tuner will often be able to come up with a better plan than the optimizer does. In some cases, this will because the human can reason about the query in a way the optimizer cannot. Other times, it is simply a question of time – we might be happy spending half a day finding a great execution plan for a crucial query, whereas the optimizer places strict limits on itself to avoid spending more time on optimization than it saves on a single execution.

Perhaps a future version of SQL Server will allow us to configure the optimizer to spend extra time on a particular query – today, we have to use query hints and ‘manual optimizations’ to encourage a particular execution plan shape. The down side to circumventing the optimizer’s natural behaviour in this way is that we then have to take responsibility for ensuring that the execution plan remains good in the future, as data volumes and distributions change. In most systems, it is best to limit the number of manually-tuned queries to a minimum, and thoroughly document any tricks you use to obtain a particular plan.

Input Tree to Cost-Based Optimization

Back to the task at hand. We have a sample query (reproduced below) that has been through all the previous optimization stages, did not qualify for a trivial plan, and so needs to go through the cost-based optimization process.

     SELECT

        p.Name,

        Total = SUM(inv.Quantity)

    FROM 

        Production.Product AS p,

        Production.ProductInventory AS inv

    WHERE

        inv.ProductID = p.ProductID

        AND p.Name LIKE N'[A-G]%'

    GROUP BY

        p.Name;

The tree of logical operations passed to the optimizer looks like this:

This looks very similar to the original logical tree seen in part one, though cardinality estimates have been added to each primary node, and the tree layout has been expanded a little into a form that is easier for the system to work with. In addition to simple cardinality estimates, remember that each node also has statistics objects (histograms and frequency information) derived from the familiar statistics associated with the tables in the query.

The tree above was built from information obtained using trace flag 3604 and 8606 (see part one for more details). Trace flag 8606 shows the tree at various stages, the diagram above is built from the view after project normalization:

Properties

There are also a number of other ‘properties’ associated with each node, that have been added by previous optimization stages. These properties include logical attributes, such as:

Output columns and expressions
Uniqueness (key) information
Type information and nullability
Functional dependencies
Domain ranges for each column or expression

There are also some physical properties that may be present on each node, for example:

Sort order at each node
Partitioning information
Halloween protection

The Halloween protection information is worth explaining in a bit more detail. A query generally executes as a pipeline, with rows being requested one at a time from the top of the tree – so rows are in effect pulled up the tree one at a time. This pipeline arrangement has a number of important advantages, but a problem can arise where the query modifies data: changes made by the query can affect rows being read by the same query – the classic example is a query that adds 10% to the salaries of every employee. When processed as a pipeline, we can get stuck in an infinite loop as rows that have had 10% added re-qualify for reading. This problem happened to be first discovered on 31 October 1976 and became known as the Halloween Problem.

One solution is to separate operations that read data from those that update data by reading all rows into temporary storage before performing any updates. In SQL Server, this simple solution typically manifests as an Eager Table Spool in the query plan – all rows are written eagerly to temporary storage before any updates are performed. This is a bit of a sledgehammer solution though, so the optimizer keeps track of which columns need protection from the Halloween problem (and how much protection they need) at each node by setting properties. Some logical operations (like sorting) naturally mean that all input rows have to be read before the first output row can be produced. These operations provide Halloween protection naturally, so an explicit Eager Table Spool would not be necessary. There are a number of logical operations that can provide some degree of Halloween protection, and properties are used to ensure that just enough protection is provided, at minimum cost.

Rules

The optimizer contains rules to transform trees. There are four classes of rule:

Simplification
Exploration
Implementation
Physical property enforcement

Simplification rules transform some part of the logical tree to a simpler logical form, and are responsible for the simplification transforms we saw in part one. Exploration rules run only during cost-based optimization, generating new logical equivalents for some part of the existing logical tree. Implementation rules produce a physical operation (like a hash or merge join) for a logical operation (a logical join). Property enforcement rules introduce new elements to the logical tree to enforce some desired physical property at that point, for example to enforce a particular sorted order of rows (as might be required by a merge join or stream aggregate).

There are 395 rules in SQL Serer 2012, most of which perform quite simple operations; it is the fact that many rules can be run in various orders that accounts for the apparent complexity of optimizer behaviour. The way that simple rules can combine to produce complex behaviours reminds me of Conway’s Game of Life – a cellular automation program with only four rules that nevertheless can produce extraordinarily complex and beautiful patterns as the rules are applied over and over.

Exploration Rule Examples

One example of a simple exploration rule is SELonJN, a rule that merges a suitable relational SELECT (row filter) into a logical join operation:

Another common exploration rule that generates a new logical alternative is JoinCommute:

As the name suggests, JoinCommute explores a different logical join order, exploiting the fact that A JOIN B is equivalent to B JOIN A for inner joins. Though logically equivalent, the different join orders may have different performance characteristics once the logical alternatives are translated to a physical implementation by a later implementation rule. A third exploration rule that is relevant to our test query is GbAggBeforeJoin, a rule that explores the possibility of pushing an aggregation operation under a join:

Implementation Rule Examples

As mentioned previously, implementation rules transform part of a logical tree into a physical alternative:

The diagram shows three join implementation rules, JNtoNL (nested loops), JNtoHS (hash join), JNtoSM (sort-merge join); two implementations for Group-By Aggregate, GbAggToStrm (Stream Aggregate) and GbAggToHS (Hash Aggregate); SelectToFilter, GetToScan, and GetIdxToRng.

Which Rules Were Used?

If we want to see which rules were used when optimizing a query, one option is to use an undocumented view which shows the number of times a rule has been asked to estimate how valuable it might be in the current context (its ‘promise’ value), the number of times the rule was used to generate an alternative section of the tree (‘built’), and the number of times the output of the rule was successfully incorporated into the search space (‘succeeded’). A sample of the contents of the sys.dm_exec_query_transformation_stats DMV is shown below:

By taking a snapshot view of this information before and after optimizing a particular query, we can see which rules were run. The DMV is instance-wide however, so you would need to run these tests on a system to which you have exclusive access. The scripts that accompany this series of posts contain a complete test rig to show the rules used by each query.

End of Part 2

Part three in this series covers the Memo structure and optimization phases in detail. The original presentation slides and demo code are contained in the zip file shown below.

Links to other parts of this series: Part 1 Part 3 Part 4

Query Optimizer Deep Dive - Part 1

Paul White — Fri, 27 Apr 2012 14:38:00 GMT

This is the first in a series of posts based on the content of the Query Optimizer Deep Dive presentations I have given over the last month or so at the Auckland SQL Users’ Group and the SQL Saturday events in Wellington, New Zealand and Adelaide, Australia.

Links to other parts of this series: Part 2 Part 3 Part 4

Introduction

The motivation behind writing these sessions is that I have found that relatively few people have a good intuition for the way the optimizer works, partly because the official documentation is rather sparse, and partly because what information is available is dispersed across many books and blog posts. The content presented here is very much geared to my preferred way of learning – it shows the concepts in what seems to me to be a reasonably logical sequence, and provides tools to enable the interested reader to explore further, if desired.

When we write a query, we are not writing a computer program that can be directly executed. SQL is a declarative language used to logically describe the results we want to see. SQL Server goes through a process of compilation and optimization to create a physically executable implementation of the stated logical requirement. To put it another way, a SQL query is the specification for an executable program that SQL Server writes for us. The SQL Server component responsible for finding an efficient physical execution plan for a given logical query requirement is the Query Optimizer.

The SQL Server Core Engine

The diagram below shows conceptually where the Query Optimizer sits in the core SQL Server engine:

Language Processing is concerned with things like parsing the text of the query to make sure it is syntactically valid, binding table references to real database objects, deriving types for expressions, semantic analysis (for example checking that the query is not trying to execute a table), and binding GROUP BY references to the appropriate logical scope. The Query Optimizer aims to find a good physical execution plan that matches the logical semantic of the query, and the Query Executor is responsible for running that plan to completion. Below that, the Storage Engine provides access to physical storage, together with locking and transaction services. Finally, SQL-OS is the layer that provides threading, memory management, and scheduling services.

Using the same colours for the components shown above, a very high-level overview of query processing looks like this:

This series of blog posts is mostly concerned with the “Optimize” step above. It takes as its input a tree of logical operations produced by the previous stages.

Optimization Pipeline

The diagram below shows the principal stages within query optimization, starting with the bound tree produced by the parser and algebrizer. The coloured steps are the ones we will explore in depth – the right hand side of the diagram lists a bit more detail that I talk through when presenting this material live:

Input Tree

We start by looking at the bound logical tree (input tree). To make the discussion a little less abstract, we will use a test query issued against the AdventureWorks sample database. This simple query shows products and the quantity in stock, limited to products with names that start with a letter between A and G:

     -- Test query

    SELECT

        p.Name,

        Total = SUM(inv.Quantity)

    FROM 

        Production.Product AS p,

        Production.ProductInventory AS inv

    WHERE

        inv.ProductID = p.ProductID

        AND p.Name LIKE N'[A-G]%'

    GROUP BY

        p.Name;

The input tree generated by this query is shown below, slightly simplified:

The operations in this tree are all purely logical, and have their roots in Relational Theory. The GET operation logically reads an entire table, though you should not yet be thinking in terms of physical operations such as a scan or a seek. The JOIN is a cartesian product, logically joining every row in one table with every row in the other. The SELECT is not a SQL statement, it is a relational operation: filtering rows based on some condition (known as a predicate). Here, we are applying two SELECT operations to filter on matching product IDs and rows where the product name starts with a letter between A and G. The next logical operation is a Group-By Aggregate, an extension to the basic relational algebra that logically groups rows by some common attribute, and optionally computes an aggregate expression for each group. Finally, we have a relational Project operation, which filters columns – here we only need the Name and Total columns, and those are the only two returned in the logical result set.

To see this tree directly, we can use undocumented trace flag 8605. This flag also requires the common trace flag 3604 to produce output to the SSMS messages window. We can use another undocumented syntax, the QUERYTRACEON hint, to set the trace flag just for this query:

    -- Input tree (ISO-92)

    SELECT

        p.Name,

        Total = SUM(inv.Quantity)

    FROM Production.Product AS p

    JOIN Production.ProductInventory AS inv ON

        inv.ProductID = p.ProductID

    WHERE

        p.Name LIKE N'[A-G]%'

    GROUP BY

        p.Name

    OPTION (RECOMPILE, QUERYTRACEON 8605);

Now, in the SSMS messages tab, we see a textual representation of the tree of logical operators I drew with coloured boxes before:

There are a few minor differences between this and the previous diagram. In particular, the expression computed by the aggregate is added by a separate projection (omitted for clarity before), and the SQL-92 join syntax means the join predicate is more tightly bound to the logical join. Rewriting the query using SQL-89 syntax highlights the second difference, producing a tree closer to the cartesian product followed by a relational SELECT:

    -- Input tree (ISO-89)

    SELECT

        p.Name,

        Total = SUM(inv.Quantity)

    FROM 

        Production.Product AS p,

        Production.ProductInventory AS inv

    WHERE

        inv.ProductID = p.ProductID

        AND p.Name LIKE N'[A-G]%'

    GROUP BY

        p.Name

    OPTION (RECOMPILE, QUERYTRACEON 8605);

Simplification

The first step of the optimization pipeline we will look at is simplification, where the optimizer looks to rewrite parts of the logical tree to remove redundancies and move logical operations around a bit to help later stages. Major activities that occur around the time simplification occurs (I have taken a little artistic licence here to group a few separate stages together) include:

Constant folding
Domain simplification
Predicate push-down
Join simplification
Contradiction detection

Constant folding is the process of evaluating an expression during optimization, rather than repeatedly at execution time. In the following example, the complex expression in the WHERE clause can safely be evaluated early, resulting in “WHERE p.Name LIKE ‘D%’:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE p.Name LIKE SUBSTRING(LEFT(CHAR(ASCII(CHAR(68))), 1) + '%', 1, 2);

Domain simplification enables the optimizer to reason about the range of valid values a column or expression can take. In the next query, the only value for Product ID that logically matches all the predicates in the extended WHERE clause is the single value ‘400’. The query plan shows that simplification has reduced the three predicates to a single equality predicate, “WHERE p.ProductID = 400”:

    SELECT TOP (10) * 

    FROM Production.Product AS p

    WHERE p.ProductID BETWEEN 300 AND 400

    AND p.ProductID BETWEEN 200 AND 500

    AND p.ProductID BETWEEN 400 AND 600;

Predicate push-down involves pushing relational SELECTs (logically filtering rows based on a predicate) down the logical tree toward the leaves. The heuristic here is that this is always a good thing to do (at least as far as expressions that reference a column are concerned) because it eliminates rows early, reducing the number for later logical operations. Moving SELECTs closer to the logical GETs (reading tables) also helps index and computed-column matching.

Join simplification allows the optimizer to remove unnecessary joins, convert logical outer joins to simpler inner joins where the NULLs introduces by the outer join are later rejected by another feature in the query, and remove provably empty subexpressions. This is an incredibly powerful optimizer facility, with its roots again in relational theory. Rob Farley has written (SQL Server MVP Deep Dives) and presented (http://bit.ly/SimpleRob) about ways to use this feature effectively. In particular, he talks about how to write views to benefit from compile-time simplification, and avoid the views-on-views-on-views problem. The following queries illustrate some of the join simplifications:

    -- Remove unnecessary joins

    SELECT

        th.ProductID,

        SUM(th.ActualCost)

    FROM Production.TransactionHistory AS th

    JOIN Production.Product AS p ON

        p.ProductID = th.ProductID

    GROUP BY

        th.ProductID;

    GO

    -- Outer join to join (null rejection)

    SELECT * 

    FROM Production.Product AS p

    LEFT JOIN Production.TransactionHistory AS th ON

        th.ProductID = p.ProductID

    WHERE th.ProductID < 10;

    GO

    -- Complex example combining multiple simplifications

    WITH Complex AS

    (

        SELECT

            pc.ProductCategoryID, pc.Name AS CatName,

            ps.ProductSubcategoryID, ps.Name AS SubCatName,

            p.ProductID, p.Name AS ProductName,

            p.Color, p.ListPrice, p.ReorderPoint,

            pm.Name AS ModelName, pm.ModifiedDate

        FROM Production.ProductCategory AS pc

        FULL JOIN Production.ProductSubcategory AS ps ON

            ps.ProductCategoryID = pc.ProductCategoryID

        FULL JOIN Production.Product AS p ON

            p.ProductSubcategoryID = ps.ProductSubcategoryID

        FULL JOIN Production.ProductModel AS pm ON

            pm.ProductModelID = p.ProductModelID

    )

    SELECT c.ProductID, c.ProductName

    FROM Complex AS c

    WHERE c.ProductName LIKE N'G%';

That last example, with three full outer joins in a CTE (in-line view), simplifies down to a simple index seek on one table.

Cardinality Estimation

The optimizer only has direct information about table cardinality (total number of rows) for base tables. Statistics can provide additional histograms and frequency statistics, but again these are only maintained for base tables. To help the optimizer choose between competing strategies later on, it is essential to know how many rows are expected at each node in the logical tree, not just at the GET leaf nodes. In addition, cardinality estimates above the leaves can be used to choose an initial join order (assuming the query contains several joins).

Cardinality estimation computes expected cardinality and distribution statistics for each node, working up from the leaves one node at a time. The logic used to create these derived estimates and statistics uses a model that makes certain assumptions about your data. For example, where the distribution of values is unknown, it is assumed to be uniform across the whole range of potential values.

You will generally get more accurate cardinality estimates if your queries fit the model used, and, as with many things in the wider optimizer, simple and relational is best. Complex expressions, unusual or novel techniques, and using non-relational features often means cardinality estimation has to resort to guessing.

Most of the choices made by the optimizer are driven by cardinality estimation, so if these are wrong, any good execution plans you might see are highly likely to be down to pure luck.

Trivial Plan

The next stage of the optimizer pipeline is Trivial Plan, which is a fast path to avoid the time and effort involved in full cost-based optimization, and only applies to logical query trees that have a clear and obvious ‘best’ execution plan. The details of which types of query can benefit from Trivial Plan change frequently, but things like joins, subqueries, and inequality predicates generally prevent this optimization. The queries below show some examples where Trivial Plan can, and cannot be applied:

    -- Trivial plan

    SELECT p.ProductID

    FROM Production.Product AS p

    WHERE p.Name = N'Blade';

    GO

    -- Still trivial

    SELECT

        p.Name,

        RowNumber =

            ROW_NUMBER() OVER (

                ORDER BY p.Name)

    FROM Production.Product AS p

    WHERE p.Name LIKE N'[A-G]%';

    GO

    -- 'Subquery' prevents a trivial plan

    SELECT (SELECT p.ProductID)

    FROM Production.Product AS p

    WHERE p.Name = N'Blade';

    GO

    -- Inequality

    SELECT p.ProductID

    FROM Production.Product AS p

    WHERE p.Name <> N'Blade';

One interesting case where a Trivial Plan is not applied is where the estimated cost of the Trivial Plan query exceeds the configured ‘cost threshold for parallelism’. The reasoning here is that any trivial plan that would qualify for a parallel plan suddenly presents a choice, and a choice means the query is no longer ‘trivial’, and we have to go through full cost-based optimization. Taking this to the extreme, a SQL Server instance with the parallelism cost threshold set to zero will never produce a trivial plan (since all queries have a cost greater than zero). At the risk of stating the slightly obvious, note that a plan produced at this stage will always be serial. For experimentation only, the trivial plan stage can also be disabled using trace flag 8757.

You can check whether a query used a trivial plan or not by inspecting the Properties window in SSMS, and clicking on the root node of the graphical query plan. The ‘optimization level’ property will show ‘Trivial’ or ‘Full’ – the latter shows that a trip through full cost-based optimization was required. If a query results in a trivial plan, a physical execution plan is produced and the optimization process ends here.

End of Part 1

The original slides and demo code are contained in the zip file attached below. Links to other parts of this series: Part 2 Part 3 Part 4

Upgrading to SQL Server 2012 with Lock Pages in Memory

AaronBertrand — Mon, 06 Feb 2012 20:36:00 GMT

During SQL Server 2012 RC0 setup (specifically when upgrading), you may have noticed upgrade rules regarding Lock Pages in Memory (LPIM):

However, for most folks, these rules always pass, whether or not they are actually using LPIM. I wanted to run a few tests to demonstrate why this is - or at least in which situations the rule checks will fail. So I created two virtual machines running SQL Server 2008 R2 SP1 CU3 - one running Windows Server 2008 SP2 (x86), the other running Windows Server 2008 R2 SP1 (x64 obviously). Both machines have 4 CPUs and 8GB of RAM, and have been updated with all Windows Updates (except Internet Explorer) as of the time of writing. I set up SQL Server to run as an explicit user account (to make it easy to assign LPIM rights for the appropriate tests).

I will attempt to upgrade SQL Server under various scenarios (LPIM / AWE on x86, and LPIM / trace flag 845 on x64 - required for LPIM on Standard Edition). All of these tests will be run with LPIM enabled, but other settings will vary as follows:

On the 2008 box, to make sure that AWE can be used by SQL Server, you may first need to set this at the operating system level - this depends on the specific operating system, whether DEP is enabled, amount of RAM and other factors. It used to be quite easy - go into boot.ini, add the /PAE switch, and reboot. Starting with Windows Server 2008, this changed to use the command-line utility bcdedit. To ensure that AWE and PAE are explicitly set on this specific system (x86 box with 8GB RAM), you could run the following command at an elevated command prompt:

bcdedit /set pae ForceEnable

Of course we don't have to do any of this on the x64 box - and in my case I didn't need to do this on the x86 box, either. But the matrix for the above can become quite complicated, and is just one more reason to get off of x86 - both Windows and SQL Server - as soon as you can! (Never mind that AWE is no longer supported in SQL Server 2012, nor is a cluster on WoW.)

Next, to set Lock Pages in Memory, we need to launch the Local Group Policy Editor (Start > Run > gpedit.msc) and add the SQL Server service account to Computer Configuration > Windows Settings > Security Settings > Local Policies > User Rights Assignment > Lock pages in memory:

And then set SQL Server to run as the matching account so that it inherits the LPIM rights. You can always change this later, but for a one-off test like this it can be just as easy to specify the service account during setup:

We can then enable trace flag 845 using SQL Server Configuration Manager - right click the appropriate service, choose Properties, and on the Advanced tab, add -T845 to the Startup Parameters list (make sure there is no space between the last ; and -T845):

Note that this is much easier with SQL Server 2012 client tools installed, even against older versions of SQL Server, as there is a new Startup Parameters tab to help you avoid messy typing inside that little combo box:

And finally, to enable SQL Server to utilize AWE on the x86 box, you can use the UI through Management Studio, or you can run the following code using sp_configure:

EXEC sp_configure 'show advanced options', 1;
RECONFIGURE WITH OVERRIDE;
GO

EXEC sp_configure 'awe enabled', 1;
RECONFIGURE WITH OVERRIDE;
GO

EXEC sp_configure 'show advanced options', 0;
RECONFIGURE WITH OVERRIDE;
GO

(This is all just for testing purposes, but of course I need to point out that you wouldn't just enable AWE or LPIM without also adjusting min/max server memory appropriately and without proper consideration into what other services on the box will need memory.)

Restart each box and we should be ready for the first tests. We can verify LPIM / AWE via the following entries the SQL Server error log after restart:

For x64, there will be a line item that says "Using locked pages for buffer pool.":

When LPIM is not enabled (e.g. when the user rights assignment has not been set or the trace flag is not in use), the line above does not appear.

For x86, a message like "Using locked pages for buffer pool." will not appear in the error log, even though LPIM is enabled in this case. Instead you will see a line item about AWE, "Address Windowing Extensions is enabled":

On x86 if LPIM is not enabled (e.g. if you haven't used the trace flag on Standard Edition, have not enabled AWE, or have not set the user rights correctly), you will see different error messages in the log, such as "SQL Server is not configured to use all of the available system memory. To enable SQL Server to use more memory, set the awe enabled option to 1 by using the sp_configure stored procedure." and "Addressing Windowing Extensions (AWE) requires the 'lock pages in memory' privilege which is not currently present in the access token of the process.":

One issue you might come across is the case where you've triple-checked everything - you know you've given the service account LPIM rights in the Group Policy editor, you've set the trace flag and you've restarted SQL Server, but the error log still seems to indicate that LPIM is not set. Please verify that you've entered the trace flag argument correctly. The following two entries are not the same, and only the first is valid:

...\mastlog.ldf;-T845;
 
...\mastlog.ldf; -T845;
----------------^  this space may make you scream

Once you've verified that LPIM is up and running, let's go through the first few steps of SQL Server 2012 RC0 setup and see how the rule checks pan out.

32-bit systems

AWE and trace flag 845 both enabled

If you have AWE enabled and the trace flag turned on, the AWE check fails:

---------------------------
Rule Check Result
---------------------------
Rule "Is AWE Enabled Check for x86 installations" failed.

AWE is currently enabled on a 32-bit instance of SQL Server. This feature is no longer supported.
You must disable AWE before upgrading the instance.
---------------------------
OK
---------------------------

AWE disabled, trace flag 845 enabled

If you disable AWE and restart the service, you will see the above message about using sp_configure in the error log, but both the AWE and the LPIM checks pass. This is because you didn't already have LPIM enabled, since AWE was not enabled. Even though you might have thought that you were using LPIM prior to the upgrade:

---------------------------
Rule Check Result
---------------------------
Rule "LPIM Check for x86 installations" passed.

Lock Pages In Memory (LPIM) check for X86 succeeded.
---------------------------
OK
---------------------------

AWE enabled, trace flag 845 disabled

If you re-enable AWE and then turn off the 845 trace flag, you won't see any error messages in the error log, except for the "AWE is enabled" message. And you will see the same AWE rule fail upgrade you'll see if you have the trace flag turned on:

---------------------------
Rule Check Result
---------------------------
Rule "Is AWE Enabled Check for x86 installations" failed.

AWE is currently enabled on a 32-bit instance of SQL Server. This feature is no longer supported.
You must disable AWE before upgrading the instance.
---------------------------
OK
---------------------------

AWE and trace flag 845 both disabled

If you then disable AWE and leave the trace flag disabled, you get the message in the log about not using all of the available memory, but again, like in case 2., both the AWE and LPIM upgrade rule checks pass:

---------------------------
Rule Check Result
---------------------------
Rule "LPIM Check for x86 installations" passed.

Lock Pages In Memory (LPIM) check for X86 succeeded.
---------------------------
OK
---------------------------

So for x86, I found no way to trigger an upgrade rule failure for the specific "LPIM Check for x86 installations" using RC0, but perhaps by RTM, this rule will also fail in addition to the AWE check in cases 1. and 3. above. In any case, I don't think it's that big of a deal since, if you are running x86, you won't be able to take advantage of AWE or LPIM anyway (more on that below). I think during the upgrade process you should be warned about this on any x86 machine with more than 4GB of RAM, regardless of your current AWE settings or trace flags. Not everyone is going to read the discontinued engine features topic or attend one of my "What's New in SQL Server 2012?" presentations, and they may not realize later that when they change those settings they are not going to have any effect.

Note that in SQL Server 2012, AWE is no longer supported. So it may very well be the case that you were expecting your AWE settings (in sp_configure, not in boot.ini) and LPIM to play well together after upgrading to SQL Server 2012, but this is not the case - SQL Server will no longer be able to see all of your memory, and this may have significant impact on your workload. Of course if you have a machine with 16GB of RAM and suddenly SQL Server will only see about 4GB, you might not be too impressed with the "upgrade" - hence the warnings. Note also that your experience with the RCs of SQL Server 2012 (all of which are Evaluation Edition) may yield different results than what will happen at RTM time (when you will be able to use a license key to specify "normal" editions like Standard and perform an actual end-to-end upgrade).

64-bit systems

Trace flag 845 enabled

As expected, with both LPIM and TF845 enabled, the upgrade rule "LPIM Check for x64 Installations" passes (even though the "Using locked pages in memory" message does not appear in the error log). There is nothing to warn the user about because LPIM will continue to be honored:

---------------------------
Rule Check Result
---------------------------
Rule "LPIM Check for x64 installations" passed.

Lock Pages In Memory (LPIM) check for X64 succeeded.
---------------------------
OK
---------------------------

Trace flag 845 disabled

If we restart SQL Server without the trace flag, we no longer see the "Using locked pages for buffer pool" message in the error log, but the LPIM check still succeeds - even though we're on Standard Edition and the trace flag is not set (which is the reason behind the warning):

---------------------------
Rule Check Result
---------------------------
Rule "LPIM Check for x64 installations" passed.

Lock Pages In Memory (LPIM) check for X64 succeeded.
---------------------------
OK
---------------------------

This last case is the most concerning to me. The point of the warning is to let me know that I have the LPIM permission set for the service account, but that it won't be honored without the trace flag because I'm running Standard Edition. In this specific case, I think the LPIM upgrade rule should fail, even though my current configuration also prevents me from using LPIM.

Conclusion

I quite sincerely hope this is my last 32-bit related blog post. For one, the x86 installation of SQL Server took at least five times longer than the x64 equivalent. x86 RIP!

In any case, this is just one way Microsoft is helping to prevent customers from shooting off their own feet. Especially in the x86 case where their current workloads are dependent upon AWE; it needs to be clear to them that after the upgrade to SQL Server 2012, their configuration isn't what they think it is...

How to Find the Statistics Used to Compile an Execution Plan

Paul White — Tue, 20 Sep 2011 15:22:15 GMT

In this post, I show you how to determine exactly which statistics objects were used by the query optimizer to produce an execution plan.

Trace Flags

We will need three undocumented trace flags. The first one (3604) is well-known – it redirects trace output to the client so it appears in the SSMS messages tab.

The second trace flag is 9292. With this enabled, we get a report of statistics objects which are considered ‘interesting’ by the query optimizer when compiling, or recompiling the query in question. For potentially useful statistics, just the header is loaded.

The third trace flag is 9204. With this enabled, we see the ‘interesting’ statistics which end up being fully loaded and used to produce cardinality and distribution estimates for some plan alternative or other. Again, this only happens when a plan is compiled or recompiled – not when a plan is retrieved from cache.

You can enable and disable these flags with the usual DBCC TRACEON and TRACEOFF commands, but it is also possible to enable them just for a particular statement using the undocumented QUERYTRACEON query hint (demonstrated below).

Sample Query

     DBCC FREEPROCCACHE

    SELECT 

        p.Name,

        total_quantity = SUM(th.Quantity)

    FROM AdventureWorks.Production.Product AS p

    JOIN AdventureWorks.Production.TransactionHistory AS th ON

        th.ProductID = p.ProductID

    WHERE

        th.ActualCost >= $5.00

        AND p.Color = N'Red'

    GROUP BY

        p.Name

    ORDER BY

        p.Name

    OPTION

    (

        QUERYTRACEON 3604,

        QUERYTRACEON 9292,

        QUERYTRACEON 9204

    )

The DBCC FREEPROCCACHE is just there to empty the plan cache so we get a compilation. You can also evict the current plan from cache if you know its handle (SQL Server 2008) or use a RECOMPILE query hint. Using RECOMPILE is often convenient, but you may get a different plan compared to that obtained without the hint. Note that compiling the query is enough – we do not need to execute the query; simply requesting an ‘estimated plan’ will do. It doesn’t hurt to run it either though, just to be clear.

Sample Output

    Stats header loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 1, 

        ColumnName: ProductID, 

        EmptyTable: FALSE

    Stats loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 1, 

        ColumnName: ProductID, 

        EmptyTable: FALSE

    Stats header loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 3, 

        ColumnName: Name, 

        EmptyTable: FALSE

    Stats loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 3, 

        ColumnName: Name, 

        EmptyTable: FALSE

    Stats header loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 11, 

        ColumnName: Color, 

        EmptyTable: FALSE

    Stats loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.Product, 

        IndexId: 11, 

        ColumnName: Color, 

        EmptyTable: FALSE

    Stats header loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.TransactionHistory, 

        IndexId: 2, 

        ColumnName: ProductID, 

        EmptyTable: FALSE

    Stats loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.TransactionHistory, 

        IndexId: 2, 

        ColumnName: ProductID, 

        EmptyTable: FALSE

    Stats header loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.TransactionHistory, 

        IndexId: 5, 

        ColumnName: ActualCost, 

        EmptyTable: FALSE

    Stats loaded: 

        DbName: AdventureWorks, 

        ObjName: AdventureWorks.Production.TransactionHistory, 

        IndexId: 5, 

        ColumnName: ActualCost, 

        EmptyTable: FALSE

There’s no sign of an official way to get this very useful information in Denali, despite it being requested many times over the years. Trace flag 9204 works at least as far back as SQL Server 2005. Both 92xx flags work in 2008, R2, and Denali CTP 3.

Enjoy!

SQLkiwi@gmail.com
@SQL_Kiwi

SQL Server 2008 R2 still requires a trace flag for Lock Pages in Memory

AaronBertrand — Mon, 07 Feb 2011 16:32:00 GMT

Almost two years ago, I blogged that Lock Pages in Memory was finally available to Standard Edition customers (Enterprise Edition customers had long been deemed smart enough to not abuse this feature). In addition to applying a cumulative update (2005 SP3 CU4 or 2008 SP1 CU2), in order to take advantage of LPIM, you also had to enable trace flag 845.

Since the trace flag isn't documented for SQL Server 2008 R2, several of us in the community assumed that it was no longer required (since it was introduced before 2008 R2 went RTM, and a trace flag is typically only introduced to change behavior after a product has been released). We don't expect to see documentation stating that something *isn't* required, just like we don't expect to find a page on the SQL Server site that lists all of the features not supported by SQL Server.

As it turns out, the trace flag is still required for SQL Server 2008 R2. Hopefully they will update R2's Books Online to reflect this (and Denali's, if it continues to be true for the next version of SQL Server).

SQL Server challenge: show me trace flag 1118 is significant -- a quick update

Linchi Shea — Fri, 02 Oct 2009 15:42:00 GMT

I posted the following SQL Server challenge yesterday:

Describe a reproducible workload that would see significant throughput improvement when trace flag 1118 is enabled.

In response, Konstantin Korobkov wanted to know whether the number of data files in tempdb would make a difference.

I did test that scenario and did not see any difference. But I didn’t record the results. So I didn’t have any specific numbers to show. To be absolutely sure, I thought it would be better to reconfirm that, and I decided to run the same test: (1) with spT1118_v2 (see the previous post for the code), (2) with a single data file in tempdb, and (3) with everything else being the same.

The following chart summaries the test results with tempdb having a single data file:

Just the same as the results from the other scenarios in the previous posts ([1], [2], and [3]), there was no significant difference whether or not trace flag 1118 was enabled.

So the challenge stands.