Paul White: Page Free Space

Parallel Execution Plans Suck

Paul White — Wed, 02 May 2012 17:57:00 GMT

Summary: A deep dive into SQL Server parallelism, and a potential performance problem with parallel plans that use TOP.

There was an interesting question asked by Mark Storey-Smith on dba.stackexchange.com back in October 2011. He was looking at the execution plan for a query that counts a million rows from a virtual auxiliary table of numbers. The query below is a slightly-modified version of the one in the original post:

     WITH

        N1 (n) AS

        (

            -- 10 rows

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1

        ),

        N2 AS (SELECT L.n FROM N1 AS L CROSS JOIN N1 AS R), -- 100 rows

        N3 AS (SELECT L.n FROM N2 AS L CROSS JOIN N2 AS R), -- 10,000 rows

        N4 AS (SELECT L.n FROM N3 AS L CROSS JOIN N3 AS R), -- 100,000,000 rows

        N5 AS (SELECT L.n FROM N4 AS L CROSS JOIN N1 AS R), -- 1,000,000,000 rows

        N6 AS 

        (

            SELECT TOP (1000000) n

            FROM N5

        )

    SELECT 

        COUNT_BIG(*)

    FROM N6

    OPTION (RECOMPILE, MAXDOP 1);

This particular virtual numbers table is capable of producing up to a (short-scale) billion rows, via a number of cross joins, but the final common table expression N6 limits it to one million with the TOP clause. The query plan is just a sequence of cross joins of the ten in-memory rows defined by the first common table expression, N1 (click to enlarge):

As usual, the Constant Scan operator is used to generate rows in memory without accessing a physical table, but this one has an interesting property: the ‘virtual table’ contains ten rows, but no columns. The query itself only counts rows, it does nothing at all with any column in those rows, and the optimizer contains logic to only project columns that are needed later in the query plan. If you look at the query plan in SSMS or SQL Sentry Plan Explorer, you will see that the Constant Scans have a blank output columns list; they project no columns at all.

Execution Plans Suck

The plan above does illustrate an important concept in plan-reading: execution plans start executing at the left-most node. People are often told to read execution plans from the top-right, and that is fine if you just want to follow the flow of data – so long as you bear in mind that the flow of program control starts at the root (far left).

Rob Farley (blog | twitter) sums this up by saying “execution plans suck”; a reference to the fact that rows are pulled up the tree by parent operators requesting rows, one at a time, from the its child operator(s). Query execution follows a demand-based pipeline model (except in batch mode in parallel 2012 column-store plans, but that is a tangent we will not be pursuing today). I’m not going to labour the point, but if you are interested to understand this better, take a look at my previous post on the topic, or Brad Schulz’s entertaining overview.

Let’s look at the execution plan (with runtime statistics) changing the TOP specification from one million to one hundred to make it easier to see what’s going on:

I’m just showing part of the plan for clarity. There are another four Constant Scans off to the right that all produce one row. If query plans really did start executing at the top right, we would expect one row from the right-most Constant Scan, ten rows from its parent, and one hundred at the next operator up the tree (working right to left). As it is, the expected pattern (one, then ten, then one hundred) appears closest to the Top operator. This only makes sense if a row at a time is sucked up the plan from the root. The pipelined (row-by-row) model also explains why execution stops after 100 rows; the Top operator in the plan simply stops requesting a new row from its immediate child at that point.

The Question

Back to the main thrust of today’s post. The question arose when Mark ran his query with parallelism enabled:

    WITH

        N1 (n) AS

        (

            -- 10 rows

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1

        ),

        N2 AS (SELECT L.n FROM N1 AS L CROSS JOIN N1 AS R), -- 100 rows

        N3 AS (SELECT L.n FROM N2 AS L CROSS JOIN N2 AS R), -- 10,000 rows

        N4 AS (SELECT L.n FROM N3 AS L CROSS JOIN N3 AS R), -- 100,000,000 rows

        N5 AS (SELECT L.n FROM N4 AS L CROSS JOIN N1 AS R), -- 1,000,000,000 rows

        N6 AS 

        (

            SELECT TOP (1000000) n

            FROM N5

        )

    SELECT 

        COUNT_BIG(*)

    FROM N6

    OPTION (RECOMPILE, MAXDOP 2);

That produces an actual execution plan like this (click to enlarge):

The question relates to the actual number of rows shown entering and leaving the Gather Streams exchange operator:

As expected, one million rows leave the exchange operator, but the plan shows 1,004,588 rows entering it. So the question is, are the row counts wrong, or if not, where did the rows go?

The Answer

As you may know, the answer lies in the fact that exchanges contain buffers. For efficiency reasons, rows are not passed across threads one by one as in the normal model discussed above. Instead, producer threads (on the right side of the exchange operator) pack rows one at a time into packets, and push completed packets across the exchange. Consumer thread(s) on the left side of the exchange retrieve rows one at a time from the current packet on demand, re-establishing the demand-based pipeline model. The internal class name for the packets, by the way, is Class eXchange PACKET – which gives us the familiar CXPACKET moniker.

Exploring the detail at little more, we can see from the execution plan that the two independent producer threads to the right of the exchange pack a total of 499,225 + 505,363 = 1,004,588 rows into packets, and the single consumer thread (thread zero) retrieves just the one million rows needed by the Top operator:

So, the actual row counts shown on the execution plan are correct, and the ‘missing rows’ are accounted for by rows that were added to packets but not ultimately needed by the consumer. After the one millionth row is passed by the Top to the Stream Aggregate (and remember all these things happen one row at a time), the next time the Top gets control, it starts the process of shutting down the pipeline below it, rather than asking the Gather Streams exchange for another row. Glossing over the finer details a little, instead of the Top calling a GetRow() method on the Gather Streams iterator, it calls a Close() method instead.

SQL Server 2008+

On SQL Server 2005 that is the end of the story. On SQL Server 2008 and later (including 2012), there is more. Let’s run the query one more time, but this time with a degree of parallelism of three, rather than two. Sometimes, we will get a plan that contains this sort of row count arrangement at the Gather Streams:

Much the same as before, a few thousand extra rows are processed by the producer threads than are ultimately needed by the consumer. That’s fine, of course, the threads in a parallel plan execute independently, so there are bound to be small timing differences that lead to this sort of effect. Every so often, however, executing this query on SQL Server 2008 or above will produce a result like this:

Whoa. Nearly 335 million rows entering the exchange – and the query now runs for 50 seconds or so, having run consistently for around 200ms previously. Looking at the per-thread actual row counts is revealing:

If everything were perfectly balanced, we might expect each of the three producer threads to process around 333,000 rows. Indeed, thread 1 and thread 2 are in this ballpark area, but thread 3 ground through 334 million rows on its own! I should mention that there is nothing special about thread 3 (you are as likely to find the huge row count on thread 1 or thread 2, the labels are arbitrary). Indeed, the problem can occur on any or all threads, as a second example run at DOP 3 shows below:

This time two threads went rogue, resulting in over 667 million rows being processed in a total execution time of 67 seconds.

Parallelism Problems?

There are other parallelism (exchange) operators in the plan, though we have concentrated only on the final Gather Streams operator so far. By the way, Gather Streams is also known as a Start Parallelism operator – a name that might surprise you since it seems to mark the end of parallelism in the plan, rather than the start. Remember that execution plans suck. The ‘final’ Gather Streams is in fact the first operator to start executing, and it is responsible for starting the parallel workers and attaching them to the threads that were reserved for this plan at the very start of execution. Anyway, I digress. Let’s look at the next exchange in the plan – reading left to right of course. This is a Repartition Streams exchange operating in Round Robin distribution mode:

This shows that 1,000 rows arriving on the producer side of the exchange, and a total of 668 on the consumer side. Not shown in the diagram above, the producer side has 340 rows on thread 1, and 330 rows on each of thread 2 and thread 3. Note that these are not the same threads as the ones we saw numbered the same way before. The numbering scheme is restarted for each independent parallel zone in the plan (and zones are bounded by a parallelism operator of one sort or another). Anyway, the point is that the rows are pretty evenly distributed on the producer side of the exchange.

On the consumer side (row counts illustrated above), things are rather different. Thread 1 (in this zone) processes 334 rows, thread 2 gets 333, and thread 3 gets only one. Now these are the same threads as shown in the 667 million row diagram. I mentioned that parallel zones are bordered by parallelism operators; the current zone is bordered by the Repartition Streams on its right side, and by the Gather Streams on its left. The same three threads are consumers at the Repartition Streams, and producers at the Gather Streams operator:

There is a clear relationship between the thread row counts at the consumer side of the Repartition Streams (334, 333, and 1 row) and the row counts at the producer side of the Gather Streams (334 million, 333 million, 338,614 rows). The two problematic threads have multiplied their row counts by a factor of one million – precisely the effect of the six cross joins in this parallelism zone. The Constant Scan virtual tables contain ten rows each, and multiplying by ten, six times over, gives a factor of one million.

Rogue Row Goals

Thread 3 in the example above ends up processing 338,614 rows. This number has no special significance, except it shows that this thread did not run this portion of the plan to completion. If it had, the single row it started with would have ended up as one million rows by the time it had been cross-joined six times with the ten-row Constant Scan table.

This is the row goal in action (if you need a details on exactly what a row goal is, please see my previous post). Essentially, though, things like a TOP operator or a FAST n hint set a row goal. Plans normally run to completion, but row goals modify this, producing a plan that tries to optimize for a certain number of rows rather than the full potential set. The TOP operator is even more special. As discussed briefly before, TOP can bring execution to an early end – instead of continuing to ask for rows from its child iterator, it calls the Close() method instead. This call filters down the tree, and execution comes to an early end. (Strictly, row goals affect optimizer choices and plan costing rather than being associated with the early end of execution, but I like the phrase ‘rogue row goal’).

So, thread 3 did not run to completion – it responded to the early Close() call and only processed 338 thousand of the one million rows it could have produced if left alone. Threads 1 and 2 never received the Close() call, or chose to ignore it. These two rogues went on to process their full potential row set – 667 million rows – despite the fact that the TOP had seen the million rows it needed and was waiting for operations elsewhere in the parallel plan to stop. We can see this by looking at the sys.dm_os_waiting_tasks DMV while the long-running query is executing:

The output is split across two lines for readability, and shows execution context zero blocked on a CXPACKET wait by both execution context 1 and execution context 3. Execution context zero is always thread zero – the so-called coordinator thread that runs the serial part of the execution plan to the left of the left-most Gather Streams operator. Put another way, context zero always runs the part of the plan before (reading left to right) the Start Parallelism operator (and therefore always runs a serial plan).

OK, so CXPACKET means the thread is involved in a parallelism-related wait. The extra detail in the resource_description column tells us that the wait is occurring at the node id 2. Checking the execution plan, we see that node 2 is indeed the Gather Streams exchange:

The wait type of e_waitPortClose means the consumer is waiting for the port to close. If you are wondering what a port is in this context, I will just say the parallelism architecture is more complex than just CXPACKET – the wiring includes a CXPort class, a CXPipe class, a CXTransLocal (local transport) class and a CXTransRemote class (for the Parallel Data Warehouse edition). There is also a linked map structure that shows how the various pipes, ports, and transports connect together. Closing the port is one step in shutting down part of a parallel plan which is running on the other side of an exchange (via a transport, pipe, and port). The stack trace below shows thread zero waiting for the port to close:

The important things are that (a) this problem does not occur in SQL Server 2005; and (b) a number of changes were made to the internal parallelism implementation in SQL Server 2008. These changes seem to have introduced a bug, where the consumer can wait for the port to close, but one or more producers either ignore the request, or fail to check for it, and go on to process the whole potential result set instead of stopping early.

Not Just Nested Loops

Fellow SQLblogger Joe Chang (blog) suggested in the comments that this problem may only occur with parallel nested loops joins. The script below reproduces the problem with parallel hash joins:

    WITH

        N1 (n) AS

        (

            -- 10 rows

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL 

            SELECT 1

        ),

        N2 AS (SELECT L.n FROM N1 AS L JOIN N1 AS R ON L.n % 1 = R.n % 1), -- 100 rows

        N3 AS (SELECT L.n FROM N2 AS L JOIN N2 AS R ON L.n % 1 = R.n % 1), -- 10,000 rows

        N4 AS (SELECT L.n FROM N3 AS L JOIN N3 AS R ON L.n % 1 = R.n % 1), -- 100,000,000 rows

        N5 AS (SELECT L.n FROM N4 AS L JOIN N1 AS R ON L.n % 1 = R.n % 1), -- 1,000,000,000 rows

        N6 AS 

        (

            SELECT TOP (1000000) n

            FROM N5

        )

    SELECT 

        COUNT_BIG(*)

    FROM N6

    OPTION (RECOMPILE, MAXDOP 4, QUERYTRACEON 8649);

The full execution plan is rather large, but the key part is shown below (click to enlarge):

Yes, that is 700 million rows entering the Gather Streams exchange (click to enlarge):

The bug does not occur in every query plan with Top and parallelism, but the choice of nested loops join is not the cause.

Final Thoughts

The potential for poor performance and excessive processor usage here is obvious; and the chance of hitting the race condition gets worse at higher DOP. With eight threads per parallel zone (DOP 8), I hit this issue almost every time on SQL Server 2008, 2008 R2, and 2012. Because this behaviour does not occur on SQL Server 2005, but does on 2008 and later, I have filed this as a bug on Connect:

https://connect.microsoft.com/SQLServer/feedback/details/740234/poor-performance-with-parallelism-and-top

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

Fun with Aggregates

Paul White — Sun, 11 Mar 2012 15:49:00 GMT

There are interesting things to be learned from even the simplest queries. For example, imagine you are given the task of writing a query to list AdventureWorks product names where the product has at least one entry in the transaction history table, but fewer than ten.

One possible query to meet that specification is:

     SELECT

        p.Name

    FROM Production.Product AS p

    JOIN Production.TransactionHistory AS th ON

        p.ProductID = th.ProductID

    GROUP BY

        p.ProductID,

        p.Name

    HAVING

        COUNT_BIG(*) < 10;

That query correctly returns 23 rows (execution plan and data sample shown below):

The execution plan looks a bit different from the written form of the query: the base tables are accessed in reverse order, and the aggregation is performed before the join. The general idea is to read all rows from the history table, compute the count of rows grouped by ProductID, merge join the results to the Product table on ProductID, and finally filter to only return rows where the count is less than ten.

This ‘fully-optimized’ plan has an estimated cost of around 0.33 units. The reason for the quote marks there is that this plan is not quite as optimal as it could be – surely it would make sense to push the Filter down past the join too? To answer that, let’s look at some other ways to formulate this query. This being SQL, there are any number of ways to write logically-equivalent query specifications, so we’ll just look at a couple of interesting ones. The first query is an attempt to reverse-engineer T-SQL from the optimized query plan shown above. It joins the result of pre-aggregating the history table to the Product table before filtering:

    SELECT p.Name

    FROM

    (

        SELECT 

            th.ProductID, 

            cnt = COUNT_BIG(*) 

        FROM Production.TransactionHistory AS th 

        GROUP BY

            th.ProductID

    ) AS q1

    JOIN Production.Product AS p 

        ON p.ProductID = q1.ProductID

    WHERE

        q1.cnt < 10;

Perhaps a little surprisingly, we get a slightly different execution plan:

The results are the same (23 rows) but this time the Filter is pushed below the join! The optimizer chooses nested loops for the join, because the cardinality estimate for rows passing the Filter is a bit low (estimate 1 versus 23 actual), though you can force a merge join with a hint and the Filter still appears below the join. In yet another variation, the < 10 predicate can be ‘manually pushed’ by specifying it in a HAVING clause in the “q1” sub-query instead of in the WHERE clause as written above.

The reason this predicate can be pushed past the join in this query form, but not in the original formulation is simply an optimizer limitation – it does make efforts (primarily during the simplification phase) to encourage logically-equivalent query specifications to produce the same execution plan, but the implementation is not completely comprehensive.

Moving on to a second example, the following query specification results from phrasing the requirement as “list the products where there exists fewer than ten correlated rows in the history table”:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID 

        HAVING COUNT_BIG(*) < 10

    );

Unfortunately, this query produces an incorrect result (86 rows):

The problem is that it lists products with no history rows, though the reasons are interesting. The COUNT_BIG(*) in the EXISTS clause is a scalar aggregate (meaning there is no GROUP BY clause) and scalar aggregates always produce a value, even when the input is an empty set. In the case of the COUNT aggregate, the result of aggregating the empty set is zero (the other standard aggregates produce a NULL). To make the point really clear, let’s look at product 709, which happens to be one for which no history rows exist:

    -- Scalar aggregate

    SELECT COUNT_BIG(*)

    FROM Production.TransactionHistory AS th 

    WHERE th.ProductID = 709;

    -- Vector aggregate

    SELECT COUNT_BIG(*)

    FROM Production.TransactionHistory AS th 

    WHERE th.ProductID = 709

    GROUP BY th.ProductID;

The estimated execution plans for these two statements are almost identical:

You might expect the Stream Aggregate to have a Group By for the second statement, but this is not the case. The query includes an equality comparison to a constant value (709), so all qualified rows are guaranteed to have the same value for ProductID and the Group By is optimized away.

In fact there are some minor differences between the two plans (the first is auto-parameterized and qualifies for trivial plan, whereas the second is not auto-parameterized and requires cost-based optimization), but there is nothing to indicate that one is a scalar aggregate and the other is a vector aggregate. This is something I would like to see exposed in show plan so I suggested it on Connect. Anyway, the results of running the two queries show the difference at runtime:

The scalar aggregate (no GROUP BY) returns a result of zero, whereas the vector aggregate (with a GROUP BY clause) returns nothing at all. Returning to our EXISTS query, we could ‘fix’ it by changing the HAVING clause to reject rows where the scalar aggregate returns zero:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID 

        HAVING COUNT_BIG(*) BETWEEN 1 AND 9

    );

The query now returns the correct 23 rows:

Unfortunately, the execution plan is less efficient now – it has an estimated cost of 0.78 compared to 0.33 for the earlier plans. Let’s try adding a redundant GROUP BY instead of changing the HAVING clause:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID

        GROUP BY th.ProductID

        HAVING COUNT_BIG(*) < 10

    );

Not only do we now get correct results (23 rows), this is the execution plan:

I like to compare that plan to quantum physics: if you don’t find it shocking, you haven’t understood it properly :) The simple addition of a redundant GROUP BY has resulted in the EXISTS form of the query being transformed into exactly the same optimal plan we found earlier. What’s more, in SQL Server 2008 and later, we can replace the odd-looking GROUP BY with an explicit GROUP BY on the empty set:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID

        GROUP BY ()

        HAVING COUNT_BIG(*) < 10

    );

I offer that as an alternative because some people find it more intuitive (and it perhaps has more geek value too). Whichever way you prefer, it’s rather satisfying to note that the result of the sub-query does not exist for a particular correlated value where a vector aggregate is used (the scalar COUNT aggregate always returns a value, even if zero, so it always ‘EXISTS’ regardless which ProductID is logically being evaluated).

The following query forms also produce the optimal plan and correct results, so long as a vector aggregate is used (you can probably find more equivalent query forms):

WHERE Clause

    SELECT

        p.Name

    FROM Production.Product AS p

    WHERE 

    (

        SELECT COUNT_BIG(*) 

        FROM Production.TransactionHistory AS th

        WHERE th.ProductID = p.ProductID

        GROUP BY ()

    ) < 10;

APPLY

    SELECT p.Name

    FROM Production.Product AS p

    CROSS APPLY

    (

        SELECT NULL

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID

        GROUP BY ()

        HAVING COUNT_BIG(*) < 10

    ) AS ca (dummy);

FROM Clause

    SELECT q1.Name 

    FROM

    (

        SELECT

            p.Name, 

            cnt = 

            (

                SELECT COUNT_BIG(*) 

                FROM Production.TransactionHistory AS th 

                WHERE th.ProductID = p.ProductID 

                GROUP BY ()

            )

        FROM Production.Product AS p

    ) AS q1 

    WHERE

        q1.cnt < 10;

This last example uses SUM(1) instead of COUNT and does not require a vector aggregate…you should be able to work out why :)

    SELECT q.Name 

    FROM

    (

        SELECT

            p.Name, 

            cnt = 

            (

                SELECT SUM(1)

                FROM Production.TransactionHistory AS th 

                WHERE th.ProductID = p.ProductID

            )

        FROM Production.Product AS p

    ) AS q

    WHERE q.cnt < 10;

The semantics of SQL aggregates are rather odd in places. It definitely pays to get to know the rules, and to be careful to check whether your queries are using scalar or vector aggregates. As we have seen, query plans do not show in which ‘mode’ an aggregate is running and getting it wrong can cause poor performance, wrong results, or both.

Twitter: @SQL_Kiwi
email: SQLkiwi@gmail.com

Dynamic Seeks and Hidden Implicit Conversions

Paul White — Tue, 17 Jan 2012 13:37:00 GMT

Most people know that a LIKE predicate with only a trailing wildcard can usually use an index seek:

     SELECT 

        p.Name 

    FROM Production.Product AS p

    WHERE 

        p.Name LIKE N'D%';

As the execution plan shows, SQL Server determines a covering range (which depends on the collation), seeks the string index using the range as the start and end points of a partial scan, and applies the original LIKE condition as a residual predicate to just the rows that match the initial seek operation. Specifically, the Storage Engine seeks the index to locate rows in the covering range, and the Query Processor applies the residual predicate (the LIKE) to the rows it receives.

Dynamic Seeks

But what if the LIKE search term is in a variable?

    DECLARE @Like NVARCHAR(50) = N'D%'

    SELECT 

        p.Name 

    FROM Production.Product AS p

    WHERE 

        p.Name LIKE @Like;

SQL Server can still perform a seek here, but it needs to determine the covering seek range for the search term at execution time, not at compilation time:

The plan now contains an extra Constant Scan, a Compute Scalar and a Nested Loops Join. These operators are interesting because they have zero cost estimates: no CPU, no I/O, nothing. That’s because they are purely architectural: a workaround for the fact that SQL Server cannot currently perform a dynamic seek within the Index Seek operator itself. To avoid affecting plan choices, this extra machinery is costed at zero.

The Constant Scan produces a single in-memory row with no columns. The Compute Scalar defines expressions to describe the covering seek range (using the runtime value of the @Like variable). Finally, the Nested Loops Join drives the seek using the computed range information as correlated values.

The upper tooltip shows that the Compute Scalar uses three internal functions, LikeRangeStart, LikeRangeEnd, and LikeRangeInfo. The first two functions describe the range as an open interval. The third function returns a set of flags encoded in an integer, that are used internally to define certain seek properties for the Storage Engine. The lower tooltip shows the seek on the open interval described by the result of LikeRangeStart and LikeRangeEnd, and the application of the residual predicate ‘LIKE @Like’.

More Dynamic Seeks

Something very similar occurs in plans that use IN or OR with variables:

    DECLARE 

        @1 INTEGER = 320,

        @2 INTEGER = 325,

        @3 INTEGER = 330

    SELECT

        p.Name

    FROM Production.Product AS p

    WHERE 

        p.ProductID IN (@1,@2,@3);

Now we have three ranges: one for each of the variables in the original query. The Compute Scalar operators again define three columns containing the start and end of the range, and the associated informational flags (previously seen as a result of the LikeRangeInfo function). This time, we see the decimal representation of these flags, which happens to be 62 for an equality comparison. The IN expands to (ProductID = @1 OR ProductID = @2 OR ProductID = @3), so each of the ‘ranges’ here is in fact a single value, so the start and end range values are the same in each Compute Scalar.

The three dynamic ranges are concatenated, sorted (so any overlapping ranges appear next to each other in the stream) and the Merge Interval collapses these intervals into one or more disjoint (non-overlapping) ranges. This is important, because the three variables might, for example, all contain the same value, and it would be incorrect to return that value three times. Anyway, for each disjoint range produced, the Nested Loops Join drives a new seek of the Clustered Index. The overall effect is that an arbitrary number of possibly overlapping ranges are computed, merged, and then used to drive one or more seek operations. The final result of the query will be the combination of all the seek results, as you would expect.

Hidden Conversions

The following example contains a table with DATETIME2 values, and a query with a expression that at first sight seems unlikely to be able to seek on an index (the variable is typed as DATE, and there is a CONVERT function applied to the DATETIME2 column):

    DECLARE @Example TABLE (date_time DATETIME2 PRIMARY KEY);

    INSERT @Example (date_time) 

    VALUES ('20110101 12:34:56');

    DECLARE @date DATE = '2011-01-01';

    SELECT * 

    FROM @Example AS e 

    WHERE 

        @date = CONVERT(DATE, e.date_time);

Nevertheless, a query plan that uses a seek can be produced:

In this case, neither SSMS or Plan Explorer will show the contents of the Compute Scalar (this is probably just an oversight, rather than deliberate concealment!). We have to open the XML form of the execution plan to see the three familiar expressions, wrapped in a Value Vector (just a fancy container for multiple expressions).

Another internal function, GetRangeThroughConvert, is responsible for determining the the range of DATETIME2 values covered by the DATE variable @date, and the informational flags needed. In the same way the engine works out covering ranges for some LIKE predicates, this function determines ranges where certain problematic type conversions are required. Otherwise, the machinery is the same: a range description is defined by the Compute Scalar, and the Nested Loops Join driving a seek using those values.

More Hidden Conversions

There is another related internal function used when the Query Processor needs to determine a range for a comparison between different data types. This example returns rows based on a greater-than-or-equal comparison between DATE column values and the DATETIME return value of the GETDATE() intrinsic function:

    DECLARE @Example TABLE (col1 date PRIMARY KEY)

    SELECT * FROM @Example AS e 

    WHERE e.col1 >= DATEADD(DAY, -7, GETDATE());

Again, the SSMS graphical plan and Plan Explorer cannot display the contents of the Value Vector, so we have to dig into the XML again. The function evaluates the DATEADD(GETDATE()) expression, computes the open-interval start point of a DATE range accounting for the conversion from DATETIME to DATE, and specifies NULL as the end of the range (since this is a >= comparison, there is no end value). The flags value in this case is 22 (the flags for a >= seek operation).

Everything All At Once

This last example features all sorts type sloppiness, resulting in an execution plan that uses GetRangeThroughConvert on the string expression and GetRangeThroughConvert on the result of GetRangeWithMismatchedTypes applied to the result of the GETDATE function. The whole thing is then wrapped in a dynamic seek with the Merge Interval enforcing the (annoying) BETWEEN requirement that the first parameter must be less than or equal to the second. See if you can work out all the conversions necessary for this query, using the rules of data type precedence. It is really quite impressive that this example of lazy T-SQL coding results in an index seek, don’t you think?

    DECLARE @Example TABLE (col1 DATETIME PRIMARY KEY)

    SELECT * FROM @Example AS e

    WHERE CONVERT(DATE, e.col1) BETWEEN '20000101' AND GETDATE();

Conclusion

SQL Server works quite hard sometimes to produce index seeks where they might seem unlikely. This is a good thing, and it would be great to see this capability extended further in future. The downside is that this extra effort means you are less likely to see an Index Scan when you have done something daft with data types.

Why is this a bad thing if you get a seek anyway? The problem is that these hidden implicit conversions can result in inaccurate cardinality and distribution estimations at any stage of the plan. So, even if you get a seek, the plan might be way off overall. If that isn’t persuasive enough, consider this: will having hidden nested range calculations improve your chances of getting a good query plan? Probably not, no. Be very aware of types, and in particular of the types returned by functions and expressions. If in doubt, use SELECT INTO to materialize the results of an expression or query, and check the types of the columns produced.

Note: if you have any scripts that trawl the plan cache looking for implicit conversions (CONVERT_IMPLICIT), you might want to look into updating them to check for these conversions too. Not all conversions are bad ones, of course :)

Forcing a Parallel Query Execution Plan

Paul White — Thu, 22 Dec 2011 21:09:00 GMT

This post is for SQL Server developers who have experienced the special kind of frustration, which only comes from spending hours trying to convince the query optimizer to generate a parallel execution plan. This situation often occurs when making an apparently innocuous change to the text of a moderately complex query; a change which somehow manages to turn a parallel plan that executes in ten seconds, into a five-minute serially-executing monster.

SQL Server provides a number of query and table hints that allow the experienced practitioner to take greater control over the final form of a query plan. These hints are usually seen as a tool of last resort, because they can make code harder to maintain, introduce extra dependencies, and may prevent the optimizer reacting to future changes in indexing or data distribution. One such query hint is the (over) popular OPTION (MAXDOP 1), which prevents the optimizer from considering plans that use parallelism. Sadly, there is currently no corresponding hint to force the optimizer to choose a parallel plan.

The result of all this is a great deal of wasted time trying increasingly obscure query syntax, until eventually the desired parallel plan is obtained, or the developer gives up in despair. Even where success is achieved, the price is often fragile code that risks reverting to serial execution any time indexing or statistics change. In any case, the resulting SQL is usually hard to read, and scary to maintain.

Why Expensive Queries Produce Serial Plans

Whenever the query optimizer produces a serial plan instead of the ‘obviously better’ parallel plan, there is always a reason. Leaving aside the more obvious causes, such as the configuration setting max degree of parallelism being set to one, running under a Resource Governor workload group with MAX_DOP = 1, or having only one logical processor available to SQL Server, the usual causes of a serial plan are parallelism-inhibiting operations, cardinality estimation errors, costing model limitations, and code path issues.

Parallelism-Inhibiting Components

There are many things that prevent parallelism, either because they make no sense in a parallel plan, or because the product just does not support them yet. Some of these force the whole plan to run serially, others require a ‘serial zone’ – a part of the plan that runs serially, even though other parts may use multiple threads concurrently.

That list changes from version to version, but for example these things make the whole plan serial on SQL Server 2008 R2 SP1:

Modifying the contents of a table variable (reading is fine)
Any T-SQL scalar function (which are evil anyway)
CLR scalar functions marked as performing data access (normal ones are fine)
Random intrinsic functions including OBJECT_NAME, ENCYPTBYCERT, and IDENT_CURRENT
System table access (e.g. sys.tables)

Inconveniently, the list of intrinsic functions is quite long and does not seem to follow a pattern. ERROR_NUMBER and @@TRANCOUNT also force a serial plan, @@ERROR and @@NESTLEVEL do not. The T-SQL scalar function restriction is also a bit sneaky. Any reference to a table with a computed column that uses such a function will result in a serial plan, even if the problematic column is not referenced in the query.

These query features are examples that require a serial zone in the plan:

TOP
Sequence project (e.g. ROW_NUMBER, RANK)
Multi-statement T-SQL table-valued functions
Backward range scans (forward is fine)
Global scalar aggregates
Common sub-expression spools
Recursive CTEs

The information presented above is based on the original list published by Craig Freedman, and updated for 2008 R2.

One way to check that a query does not have any parallelism-inhibiting components is to test the query using a CPU cost multiplier. This should only be done on a private test system where you are able to flush the whole plan cache after testing. The idea is to use an undocumented and unsupported DBCC command to temporarily increase the CPU cost of the query plan operators. It is not a fool-proof test (some rare parallelizable queries will not generate a parallel plan with this technique) but it is quite reliable:

     DBCC FREEPROCCACHE

    DBCC SETCPUWEIGHT(1000)

    GO

    -- Query to test

    SELECT

        COUNT_BIG(*) 

    FROM Production.Product AS p 

    LEFT JOIN Production.TransactionHistory AS th ON 

        p.ProductID = th.ProductID

    GO

    DBCC SETCPUWEIGHT(1)

    DBCC FREEPROCCACHE

The final commands to reset the CPU weighting factor and flush the plan cache are very important.

If you get an parallel estimated plan for a particular test query, it shows that a parallel plan is at least possible. Varying the value passed to the DBCC command adjusts the multiplier applied to normal CPU costs, so you will likely see different plans for different values. The illustrated factor of a thousand is often enough to produce a parallel estimated plan, but you may need to experiment with higher values. It is not recommended to use estimated plans obtained using this technique directly in USE PLAN hints or plan guides because these are not plans the optimizer would ever produce naturally. To be clear, direct use of the plans would likely render a production system unsupported and the person responsible might be fired, shot, or possibly both.

Cardinality Estimation Errors

If there is nothing that absolutely prevents parallelism in the target query, the optimizer may still choose a serial alternative if it has a lower estimated cost. For that reason, there are a couple of things we can do to promote the parallel option here, all based on the very sound notion of giving the optimizer accurate information to base its estimates on. The considerations here go well beyond just ensuring statistics are up-to-date, or building them with the FULLSCAN option. For example, depending on the nature of the query, you may need to provide all or some of the following:

Multi-column statistics (for correlations)
Filtered statistics or indexes (for more histogram steps)
Computed columns on filtering expressions in the query (avoid cardinality guesses)
Good constraint information (foreign keys and check constraints)
Materialize parts of the query in temporary tables (more accurate statistics in deep plans)
Regular hints such as OPTIMIZE FOR

In general, anything you can do to ensure that estimated row counts are close to the runtime values will help the optimizer cost the serial and parallel alternatives more accurately. Many failures to choose a parallel plan are caused by inaccurate row counts.

Model Limitations

SQL Server uses a model to estimate the runtime cost of each operator in a query plan. The exact calculations vary between operators, but most are based on a minimum cost, with an additional per-row component. None of these estimates of expected CPU and I/O cost take into account the specific hardware SQL Server finds itself running on. The advantage of this is that plans from one machine can be readily reproduced and compared on another machine running the same version of the software, without having to worry about hardware differences.

Not all operators can be costed reasonably, and things like functions are particularly problematic because the optimizer has no clue how many rows might be produced or what the distribution of values might look like. Even very normal-looking operators can pose problems. Consider the task of estimating the number of rows and distribution of values resulting from a join or a complex GROUP BY clause. Even where reasonable estimates can be made, the derived statistics that propagate up the query tree (from the persistent statistics at the leaves) tend to become quickly less reliable. The optimizer includes many heuristics that aim to prevent these inaccuracies getting out of control, so it might resort to complete guesses after only a few operators as the compounding effect of deriving new statistics takes hold.

There are many other assumptions and limitations of the model that will not fit into a blog post, the interested reader can find more detailed information in Chapter 8 of the indispensable SQL Server 2008 Internals book.

Costing Limitations

When SQL Server costs a parallel plan, it generally reduces the CPU cost for a parallel iterator by the a factor equal to the expected runtime DOP. For example the previous query can produce the following serial and parallel plans:

Taking the Merge Join operator as an example, the parallel version has its CPU cost reduced by a factor of 4 when the expected runtime DOP is four (serial plan on the left, parallel on the right):

On the other hand, the Index Scans show no reduction in I/O cost, though the CPU cost is again reduced by a factor of four:

As mentioned earlier, different operators cost themselves differently (for example a many-to-many merge join also has an I/O cost component that also happens to be reduced by a factor of four). These details also vary somewhat between releases, so the presentation here is to give you an appreciation of the general approach rather than to dwell too much on the specifics.

Looking again at the serial and parallel plans, it is clear that which of the two plans costs cheaper depends on whether the parallel plan saves enough by reducing CPU and I/O costs in the various operators, to pay for the extra operators in the plan. In this case, the extra operators are three exchange (parallelism) operators – two Repartition Streams to redistribute rows for correct results when joining, and one Gather Streams to merge the threads back to a single final result.

The way the numbers work means that it is often a tight race between the best parallel and serial plan alternatives. In many real-world cases, the difference between the two can be extremely small – making it even more frustrating when the serial version turns out to take fifty times as long as the parallel version to execute. One other point worth mentioning again here is that the DOP estimate is limited to the number of logical processors that SQL Server sees, divided by two. My test machine has eight cores, all available to SQL Server, but the DOP estimate used for costing calculations is limited to four. This has obvious consequences for costing, where CPU and I/O costs are typically divided by the estimated DOP of four, rather than eight.

A Note about Parallel Nested Loops

Plans with Nested Loops joins can be a particular problem, because the inner side almost always runs multiple threads serially. The parallelism icons are still present, but they indicate that there are DOP independent serial threads. The distinction is perhaps a subtle one, but it (a) explains why operators that normally force a serial zone can run ‘in parallel’ on the inner side of a loops join; and (b) the optimizer does not reduce the CPU costs on the inner side by the estimated runtime DOP. This puts nested loops at an unfair disadvantage when it comes to parallelism costing, compared with Hash and Merge Joins.

Code Path Issues

This last category concerns the fact that the optimizer may not get as far as evaluating a parallel plan at all. One way this can occur is if a final plan is found during the Trivial Plan stage. If a Trivial Plan is possible, and the resulting cost is less than the configured cost threshold for parallelism, the full optimization stages are skipped and a serial plan is returned immediately.

Trivial Plan

The following query has an estimated serial plan cost of around 85 units, but with the parallelism threshold set to 100 a Trivial Plan is produced (as shown in the plan property ‘Optimization Level’ or by checking the changes in sys.dm_exec_query_optimizer_info as shown below:

    SELECT

        deqoi.[counter],

        deqoi.occurrence

    FROM sys.dm_exec_query_optimizer_info AS deqoi 

    WHERE

        [counter] IN ('trivial plan', 'search 0', 'search 1', 'search 2')

    GO

    SET SHOWPLAN_XML ON

    GO

    SELECT

        COUNT_BIG(*) 

    FROM dbo.bigTransactionHistory AS bth

    OPTION (RECOMPILE)

    GO

    SET SHOWPLAN_XML OFF

    GO

    SELECT

        deqoi.[counter],

        deqoi.occurrence

    FROM sys.dm_exec_query_optimizer_info AS deqoi 

    WHERE

        [counter] IN ('trivial plan', 'search 0', 'search 1', 'search 2')

When the cost threshold is reduced to 84 we get a parallel plan…

A deeper analysis shows that the query still qualified for Trivial Plan (and the stage was run) but the final cost exceeded the parallelism threshold so optimization continued. This query does not qualify for ‘search 0’ (TP or Transaction Processing) because a minimum of three tables are required there.

So, optimization moves on to ‘search 1’ (Quick Plan) which runs twice. It runs once considering only serial plans, and comes out with a best cost of 84.6181. Since this exceeds the threshold of 84, Quick Plan is re-run with the parallel plan option enabled. The result is a parallel plan at cost 44.7854. The plan does not meet the entry conditions for ‘search 2’ (Full Optimization) so the finished plan is copied out.

Good Enough Plan & Time Out

Returning to code path reasons that prevent a parallel plan, the last category covers queries that enter the Quick Plan stage, but that stage terminates early, either with a Good Enough Plan Found message, or a Time Out. Both of these are heuristics to prevent the optimizer spending more time optimizing than it stands to gain by reducing estimated execution time (cost). Good Enough Plan results when the current lowest cost plan is so cheap that further optimization effort is no longer justified.

Time Out is a related phenomenon: at the start of a stage, the optimizer sets itself a ‘budget’ of a number of rule applications it estimates it can perform in the time justified by the initial cost of the plan. This means that query trees that start with a higher cost get a correspondingly larger allowance of rule applications (roughly comparable to the number of moves a chess program thinks ahead). If the optimizer explores the allowed number of rules before the natural end of the optimization stage, it returns the best complete plan at that point with a Time Out message. This may well occur during the first run of ‘search 1’, preventing us reaching the second run that adds parallelism.

One interesting consequence of the rule concerning Trivial Plan and the cost threshold for parallelism is that a system configured with a threshold of zero can never produce a Trivial Plan. Bearing this in mind, we can generate a surprising Time Out with this query:

    SELECT * FROM Production.Product AS p

As you would expect, this query is normally optimized using Trivial Plan (there are no cost-based plan choices here):

…but when the cost threshold is set to zero, we get Full Optimization with a Time Out…the optimizer timed out working out how to do SELECT * from a single table!

In this particular case, the optimizer ‘timed out’ after 15 tasks (it normally runs through many thousands). A Time Out result can sometimes also be an indicator that the input query is over-complex, but the interpretation is not at all that straightforward.

The Solution

We need a robust query plan hint, analogous to MAXDOP, that we can specify as a last resort when all other techniques still result in a serial plan, and where the parallel alternative is much to be preferred of course. I really want to emphasise that very many cases of unwanted serial plans are due to designers and developers not giving the optimizer good quality information. I see very few systems with things like proper multi-column statistics, filtered indexes/statistics, and adequate constraints. Even less frequently, do I see (perhaps non-persisted) computed columns created on query filter expressions to aid cardinality estimation. On the other hand, non-relational database designs with poor indexing, and decidedly non-relational queries are extremely common. (As are database developers complaining about the poor decisions the optimizer makes sometimes!)

There’s always a Trace Flag

In the meantime, there is a workaround. It’s not perfect (and most certainly a choice of very last resort) but there is an undocumented (and unsupported) trace flag that effectively lowers the cost threshold to zero for a particular query. It actually goes a little further than that; for example, the following query will not generate a parallel plan even with a zero cost threshold:

    SELECT TOP (1)

        p.Name

    FROM Production.Product AS p

    JOIN Production.TransactionHistory AS th ON

        th.ProductID = p.ProductID

    ORDER BY

        p.Name

This is a completely trivial query plan of course – the first row from the scan is joined to a single row from the seek. The total estimated cost of the serial plan is 0.0065893. Returning the cost threshold for parallelism to the default of 5 just for completeness, we can obtain a parallel plan (purely for demonstration purposes) using the trace flag:

    SELECT TOP (1)

        p.Name

    FROM Production.Product AS p

    JOIN Production.TransactionHistory AS th ON

        th.ProductID = p.ProductID

    ORDER BY

        p.Name

    OPTION (RECOMPILE, QUERYTRACEON 8649)

The parallel alternative is returned, despite the fact it costs much higher at 0.0349929 (5.3 times the cost of the serial plan). In my testing, this trace flag has proved invaluable in certain particularly tricky cases where a parallel plan is essential, but there is no reasonable way to get it from the standard optimizer.

Conclusion

Even experts with decades of SQL Server experience and detailed internal knowledge will want to be careful with this trace flag. I cannot recommend you use it directly in production unless advised by Microsoft, but you might like to use it on a test system as an extreme last resort, perhaps to generate a plan guide or USE PLAN hint for use in production (after careful review).

This is an arguably lower risk strategy, but bear in mind that the parallel plans produced under this trace flag are not guaranteed to be ones the optimizer would normally consider. If you can improve the quality of information provided to the optimizer instead to get a parallel plan, go that way :)

If you would prefer to see a fully supported T-SQL OPTION (MINDOP) or OPTION (PARALLEL_PLAN) hint, please vote here:

https://connect.microsoft.com/SQLServer/feedback/details/714968/provide-a-hint-to-force-generation-of-a-parallel-plan

SQL Server Optimizer Bug with JOIN and GROUP BY

Paul White — Mon, 05 Dec 2011 23:17:58 GMT

I came across a SQL Server bug recently that made me wonder how on earth I never noticed it before. As the title of this post suggests, the bug occurs in common JOIN and GROUP BY queries, and while it does not cause incorrect results to be returned,...(read more)

Is Distinct Aggregation Still Considered Harmful?

Paul White — Sat, 03 Dec 2011 18:30:00 GMT

Back in 2008, Marc Friedman of the SQL Server Query Processor Team wrote a blog entry entitled “Distinct Aggregation Considered Harmful” , in which he shows a way to work around the poor performance that often results simply from adding the keyword DISTINCT...(read more)

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...(read more)

Can a SELECT query cause page splits?

Paul White — Mon, 29 Aug 2011 17:46:15 GMT

Books Online has this to say about page splits: When a new row is added to a full index page , the Database Engine moves approximately half the rows to a new page to make room for the new row. This reorganization is known as a page split . ...(read more)

SQL Server, Seeks, and Binary Search

Paul White — Mon, 08 Aug 2011 20:10:27 GMT

The following table summarizes the results from my last two blog entries, showing the CPU time used when performing 5 million clustered index seeks: In test 1, making the clustered index unique improved performance by around 40%. In test 2, making the...(read more)

Avoiding Uniqueness for Performance

Paul White — Wed, 03 Aug 2011 12:34:41 GMT

In my last post , I showed how using a index unique could speed up equality seeks by around 40%. For today’s entry, I’m going to use the same tables as last time (single BIGINT column, one table with a non-unique clustered index, and one table with a...(read more)

Enforcing Uniqueness for Performance

Paul White — Thu, 28 Jul 2011 15:38:43 GMT

A little while back, I posted a short series on seeks and scans, and one of the things I highlighted was the difference between a singleton seek and a range scan. You can find that post here , if you want a refresher. Anyway, the broad point is...(read more)

Paul White: Page Free Space

Parallel Execution Plans Suck

Execution Plans Suck

The Question

The Answer

SQL Server 2008+

Parallelism Problems?

Rogue Row Goals

Not Just Nested Loops

Final Thoughts

Further Reading:

Query Optimizer Deep Dive - Part 4

Beating the Optimizer

Models and Limitations

Assumptions

Helping the Optimizer

Use a relational design

Use constraints

Statistics, indexes and computed columns

Deep Trees

Opaque operators and new features

Trace Flags

Final Thoughts

Query Optimizer Deep Dive – Part 3

Storage of Alternative Plans

Optimization Phases

Search 0 – Transaction Processing

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

Search 2 – Full Optimization

Entry and Termination Conditions

Costing

Final Memo Contents

End of Part 3

Query Optimizer Deep Dive – Part 2

Cost-Based Optimization Overview

Input Tree to Cost-Based Optimization

Properties

Rules

Exploration Rule Examples

Implementation Rule Examples

Which Rules Were Used?

End of Part 2

Query Optimizer Deep Dive - Part 1

Introduction

The SQL Server Core Engine

Optimization Pipeline

Input Tree

Simplification

Cardinality Estimation

Trivial Plan

End of Part 1

Fun with Aggregates

WHERE Clause

APPLY

FROM Clause

Dynamic Seeks and Hidden Implicit Conversions

Dynamic Seeks

More Dynamic Seeks

Hidden Conversions

More Hidden Conversions

Everything All At Once

Conclusion

Further Reading:

Forcing a Parallel Query Execution Plan

Why Expensive Queries Produce Serial Plans

Parallelism-Inhibiting Components

Cardinality Estimation Errors

Model Limitations

Costing Limitations

A Note about Parallel Nested Loops

Code Path Issues

Trivial Plan

Good Enough Plan & Time Out

The Solution

There’s always a Trace Flag

Conclusion

SQL Server Optimizer Bug with JOIN and GROUP BY

Is Distinct Aggregation Still Considered Harmful?

How to Find the Statistics Used to Compile an Execution Plan

Can a SELECT query cause page splits?