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:

1. Ignore it.  It works well out of the box with default settings and automatic statistics.
2. Override it using syntax tricks, hints, and plan guides.
3. 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

© 2012 Paul White
Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com

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

© 2012 Paul White
Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com

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.

© 2012 Paul White

Twitter: @SQL_Kiwi
email: SQLkiwi@gmail.com

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

© 2011 Paul White
Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com

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 to an otherwise perfectly reasonable aggregate function in a query.  This post is an update to that, presenting a query optimizer enhancement in SQL Server 2012 RC0 that reduces the need to perform the suggested rewrite manually.  First, though, it makes sense for me to cover some broader aggregation topics in general.

Query Plan Options for DISTINCT

There are two main strategies to extract distinct values from a stream of rows.  The first option is to keep track of unique values in a hash table.  The second is to sort the incoming rows into groups and return one value from each group.  SQL Server uses the Hash Match operator to implement the hash table option, and Stream Aggregate or Sort Distinct for the sorting option.

Hash Match Aggregate

The optimizer tends to prefer the Hash Match Aggregate on larger rowsets, with fewer groups, where there is no reason to produce a sorted output, and where the incoming rows are not sorted on the DISTINCT expression(s).  Larger inputs favour hash matching because the algorithm generally scales well (although it does require a memory grant) and can make good use of parallelism.  Fewer groups are better for hashing because it means fewer entries in the hash table, and the memory needed to store unique values is proportional to the number of groups (and the size of the group).  Hash matching does not require or preserve the order of the incoming row stream.  The query and plan below show a Hash Match Aggregate building a hash table on values in the Quantity column:

SELECT DISTINCT 

    th.Quantity

FROM Production.TransactionHistory AS th

OPTION (RECOMPILE)

The standard Hash Match Aggregate is blocking: it produces no output until it has processed its entire input stream.  If we restrict the number of rows using TOP or SET ROWCOUNT the aggregate can operate in a streaming fashion, producing new unique values as soon as they are encountered.  This streaming mode is known as Flow Distinct, and is activated depending on the estimated number of unique values in the stream.  In the example above, the estimated number of output rows from the Hash Match Aggregate is 455 (based on the statistics on my test machine).  Limiting the query to 455 or fewer rows using TOP or ROWCOUNT produces a Hash Match Aggregate running in Flow Distinct mode:

SET ROWCOUNT 10

SELECT DISTINCT 

    th.Quantity

FROM Production.TransactionHistory AS th

OPTION (RECOMPILE)

SET ROWCOUNT 0

This plan is interesting because it limits the output to 10 rows without including a specific TOP operator for that purpose.  TOP is generally preferred to ROWCOUNT for the reasons set out in the Books Online topic “Limiting Result Sets by Using TOP and PERCENT”.  Ignore the part that says “because SET ROWCOUNT is used outside a statement that executes a query, its value cannot be used to generate a query plan for a query” – we have just seen how it can affect a query plan.

For completeness, this is the TOP query and execution plan:

SELECT DISTINCT TOP (10)

    th.Quantity

FROM Production.TransactionHistory AS th

OPTION (RECOMPILE)

Stream Aggregate

Performing a DISTINCT is the same as applying a GROUP BY on every expression in the SELECT list.  A stream of rows sorted on these GROUP BY expressions has the useful property that all rows with the same GROUP BY values appear together, so all we need to do is output a row of GROUP BY keys each time a change occurs.  If the required order can be obtained without an explicit sort, the query plan can use a Stream Aggregate directly:

SELECT DISTINCT 

    th.ProductID 

FROM Production.TransactionHistory AS th

OPTION (RECOMPILE)

This query plan shows an ordered scan of an index on the ProductID column, followed by a Stream Aggregate with a GROUP BY on the same column.  The Stream Aggregate emits a new row each time a new group is encountered, similar to the Hash Match Aggregate running in Flow Distinct mode.  This operator does not require a memory grant because it only needs to keep track of one set of GROUP BY expression values at a time.

Sort Distinct

The third alternative is to perform an explicit Sort followed by a Stream Aggregate.  The optimizer can often collapse this combination into a single Sort operating in Sort Distinct mode:

SELECT DISTINCT

    p.Color

FROM Production.Product AS p 

OPTION (RECOMPILE)

To see the original Sort and Stream Aggregate combination, we can temporarily disable the GbAggToSort optimizer rule that performs this transformation:

DBCC RULEOFF('GbAggToSort')

SELECT DISTINCT

    p.Color

FROM Production.Product AS p 

OPTION (RECOMPILE)

DBCC RULEON('GbAggToSort')

The query plan now shows a regular (non-distinct) Sort followed by the Stream Aggregate:

Distinct Aggregates

The DISTINCT keyword is most commonly used with the COUNT and COUNT_BIG aggregate functions, though it can be specified with a variety of built-in and CLR aggregates.  The interesting thing is that SQL Server always processes distinct aggregates by first performing a DISTINCT (using any of the three methods shown previously) and then applying the aggregate (for example COUNT) as a second step:

SELECT 

    COUNT_BIG(DISTINCT p.Color) 

FROM Production.Product AS p 

OPTION (RECOMPILE)

One thing worth highlighting is that COUNT DISTINCT does not count NULLs.  The previous query that listed the distinct colours from the Product table produced 10 rows (9 colours and one NULL), but the the COUNT DISTINCT query here returns the value 9.  The query plan uses a Distinct Sort to perform the DISTINCT (which includes the NULL group) and then counts the groups using a Stream Aggregate.  The aggregate expression uses COUNT(expression) rather than COUNT(*), which eliminates the NULL group produced by the Distinct Sort.  This second example shows a Hash Match Aggregate performing the DISTINCT, followed by a Stream Aggregate to count the non-NULL groups:

SELECT

    COUNT_BIG(DISTINCT th.Quantity)

FROM Production.TransactionHistory AS th

OPTION (RECOMPILE)

So far, the counting step has always been performed by a Stream Aggregate.  This is because it has been a scalar aggregate – an aggregate without a GROUP BY clause – and SQL Server always implements scalar aggregates using Stream Aggregate (there would be no point using hashing since there will only be one group by definition).  If we add a GROUP BY clause, the final COUNT is no longer a single (scalar) result, so we can get a plan with two Hash Match Aggregates:

SELECT

    th.ProductID,

    COUNT_BIG(DISTINCT th.Quantity)

FROM Production.TransactionHistory AS th

GROUP BY

    th.ProductID

OPTION (RECOMPILE)

In this plan, the rightmost aggregate is performing the DISTINCT, and the leftmost one implements the COUNT (with GROUP BY).

Combining Aggregates

The decision to always implement distinct aggregates as separate DISTINCT and aggregate steps makes life easier for the optimizer.  Separating the two operations makes it easier to plan and cost parallelism, partial aggregation, combining similar aggregates, moving aggregates around (for example pushing an aggregate below a join) and so on.  On the downside, it creates problems for queries that include multiple distinct aggregates, or combine a single distinct aggregate with an ‘ordinary’ aggregate.

Multiple Aggregates

As you probably know, there is no problem combining multiple ordinary aggregations into a single operator:

SELECT

    COUNT_BIG(*),

    MAX(th.ActualCost),

    STDEV(th.Quantity)

FROM Production.TransactionHistory AS th

GROUP BY

    th.TransactionType

The single Hash Match Aggregate operator computes the three separate aggregates concurrently on the incoming stream.

Multiple Distinct Aggregates

This next query does a similar thing, but with three DISTINCT aggregations on the stream:

SELECT 

    COUNT_BIG(DISTINCT th.ProductID), 

    COUNT_BIG(DISTINCT th.TransactionDate), 

    COUNT_BIG(DISTINCT th.Quantity)

FROM Production.TransactionHistory AS th

OPTION (RECOMPILE)

It produces a more complex query plan:

The issue here is that once a DISTINCT has been performed on a stream, the stream no longer contains the columns necessary to perform the other DISTINCT operations.  To work around this, the optimizer builds a plan that reads the source stream once per DISTINCT, computes the aggregates separately, and then combines the results using a cross join (which is safe because these are all scalar aggregates, guaranteed to produce one row each).  The same basic pattern is employed if the query contains an outer GROUP BY clause, but instead of cross joins there will be inner joins on the GROUP BY columns.

More often than not, the source of rows will not be an unrestricted table scan.  Where the source is complex (and therefore expensive to re-run for every distinct aggregate) or where a filter significantly reduces the number of rows, the query optimizer may choose to Eager Spool the source rows and replay them once per distinct aggregate:

SELECT 

    COUNT_BIG(DISTINCT th.ProductID), 

    COUNT_BIG(DISTINCT th.TransactionDate), 

    COUNT_BIG(DISTINCT th.Quantity)

FROM Production.TransactionHistory AS th

WHERE

    th.ActualCost < $5

GROUP BY

    th.TransactionType

OPTION (RECOMPILE)

This is a plan shape that you are likely to encounter in the real world, since most queries will likely have a filtering condition or have a row source that is more complex than a simple scan of an index or table.  For queries over larger tables than Adventure Works provides, this plan is likely to perform poorly, as you might expect.  Aside from the obvious concerns, inserting rows into a spool has to be performed on a single thread (like all data modification operations in today’s SQL Server).  Another limitation is that the spool does not support parallel scan for reading, so the optimizer is very unlikely to restart parallelism after the spool (or any of its replay streams).  In queries that operate on large data sets, the parallelism implications of the spool plan can be the most important cause of poor performance.

Performing Multiple Distinct Aggregates Concurrently

If SQL Server were able to perform the whole COUNT DISTINCT aggregate in a single operator (instead of splitting the DISTINCT and COUNT into two steps) there would be no reason to split plans with spools as seen above.  This could not be done with a Stream Aggregate since that operator requires the stream to be sorted on the DISTINCT expression, and it is not possible to sort a single stream in more than one way at the same time.

On the other hand, the Hash Match Aggregate does not require sorted input (it keeps the distinct values in a hash table, remember), so it should be possible to design a Hash Match Aggregate that computes COUNT DISTINCT in a single operation.  We can test this idea with a User-Defined Aggregate (UDA) – SQL Server 2008 required:

using System;

using System.Collections.Generic;

using System.Data.SqlTypes;

using System.IO;

using Microsoft.SqlServer.Server;

[SqlUserDefinedAggregate

    (

    Format.UserDefined,

    IsInvariantToDuplicates = true,

    IsInvariantToNulls = true,

    IsInvariantToOrder = true,

    IsNullIfEmpty = false,

    MaxByteSize = -1

    )

]

public struct CountDistinctInt : IBinarySerialize

{

    // The hash table

    private Dictionary<int, object> dict;

    // Recreate the hash table for each new group

    public void Init()

    {

        dict = new Dictionary<int, object>();

    }

    // Ignore NULLs, store key values in the hash table

    public void Accumulate(SqlInt32 Data)

    {

        if (!Data.IsNull)

        {

            dict[Data.Value] = null;

        }

    }

    // Merge partial aggregates

    public void Merge(CountDistinctInt Group)

    {

        foreach (var item in Group.dict.Keys)

        {

            dict[item] = null;

        }

    }

    // Return the DISTINCT COUNT result

    public int Terminate()

    {

        return dict.Count;

    }

    // Required by SQL Server to serialize this object

    void IBinarySerialize.Write(BinaryWriter w)

    {

        w.Write(dict.Count);

        foreach (var item in dict.Keys)

        {

            w.Write(item);

        }

    }

    // Required by SQL Server to deserialize this object

    void IBinarySerialize.Read(BinaryReader r)

    {

        var recordCount = r.ReadInt32();

        dict = new Dictionary<int, object>(recordCount);

        for (var i = 0; i < recordCount; i++)

        {

            dict[r.ReadInt32()] = null;

        }

    }

}

This UDA does nothing more than create a hash table, add (non-NULL) values to it, and return the count of values when aggregation is complete (the hash table takes care of duplicates).  There is a little extra infrastructure code in there to allow SQL Server to serialize and reconstruct the hash table when needed (and merge partial aggregates) but the core of the function is just four lines of code.  The example above only aggregates integer values, but it is easy to extend the idea to include other types.  Anyway, armed with the integer and date time versions of the UDA, I now return to the multiple-distinct-count query that caused all the spooling, with COUNT DISTINCT replaced by UDA references:

SELECT 

    dbo.CountDistinctInt(th.ProductID), 

    dbo.CountDistinctDateTime(th.TransactionDate), 

    dbo.CountDistinctInt(th.Quantity)

FROM Production.TransactionHistory AS th

WHERE

    th.ActualCost < $5

GROUP BY

    th.TransactionType

OPTION (RECOMPILE)

Instead of all the Eager Spools, we now get this query plan:

You may be surprised to see that the three distinct count aggregates are being performed by a Stream Aggregate; after all I just finished explaining why a Stream Aggregate could not possibly do what we want here.  The thing is that all CLR UDAs are interfaced to query plans using the Stream Aggregate model.  The fact that this UDA uses a hash table internally does not change that.

The Sort in this plan is there to ensure that groups of rows arrive at the ‘Stream Aggregate’ interface in the required GROUP BY order.  This is so SQL Server knows when to call the Init() and Terminate() methods on our UDA.  The COUNT DISTINCT aggregation that is happening inside the UDA for each group could not care less about ordering, of course.  (In case you were wondering, yes, the UDA produces the same results as the original T-SQL code).

The point here is to demonstrate that multiple DISCOUNT COUNT operations can be performed within a single operator, not that UDAs are necessarily always a great way to do that in general.  As far as performance is concerned, the original spool query runs in around 220ms, and the UDA settles down around 160ms which isn’t bad, all things considered.

We can also improve the performance of the T-SQL query by rewriting it to avoid the spools by scanning the source table three times (this executes in around 75ms).  Part of the problem here (to go with the spool plan issues mentioned earlier) is that the optimizer assumes that all queries start executing with an empty data cache, and it does not account for the fact that the three scans complete sequentially, so the pages are extremely likely to be available from memory for the second and third scans.  The rewrite and query plan are below.

WITH 

    Stream AS 

    (

        SELECT 

            th.TransactionType, 

            th.ProductID, 

            th.TransactionDate, 

            th.Quantity 

        FROM Production.TransactionHistory AS th 

        WHERE 

            th.ActualCost < $5

    ),

    CountDistinctProduct AS

    (

    SELECT 

        TransactionType, 

        COUNT_BIG(DISTINCT ProductID) AS c

    FROM Stream 

    GROUP BY 

        TransactionType

    ),

    CountDistinctTransactionDate AS

    (

    SELECT 

        TransactionType, 

        COUNT_BIG(DISTINCT TransactionDate) AS c

    FROM Stream 

    GROUP BY 

        TransactionType

    ),

    CountDistinctQuantity AS

    (

    SELECT 

        TransactionType, 

        COUNT_BIG(DISTINCT Quantity) AS c

    FROM Stream 

    GROUP BY 

        TransactionType

    )

SELECT

    p.c,

    d.c,

    q.c

FROM CountDistinctProduct AS p

JOIN CountDistinctTransactionDate AS d ON

    d.TransactionType = p.TransactionType

JOIN CountDistinctQuantity AS q ON

    q.TransactionType = d.TransactionType

Combining a Single Distinct Aggregate with other Aggregates

Marc Friedman’s blog post presented a way to rewrite T-SQL queries that contain a single distinct aggregate and one or more non-distinct aggregates so as to avoid spools or reading the source of the rows more than once.  The essence of the method is to aggregate first by the GROUP BY expressions in the query and the DISTINCT expressions in the aggregate, and then to apply some relational math to aggregate those partial aggregates to produce the final result.  I encourage you to read the full post to see all the detail, but I will quickly work through an example here too:

SELECT

    dp.EnglishProductName,

    SUM(frs.SalesAmount),

    COUNT_BIG(DISTINCT frs.SalesTerritoryKey)

FROM dbo.FactResellerSales AS frs

JOIN.dbo.DimProduct AS dp ON

    frs.ProductKey = dp.ProductKey

GROUP BY

    dp.EnglishProductName

OPTION (MAXDOP 1, RECOMPILE)

This query contains a regular SUM aggregate and a COUNT DISTINCT, so as expected the query optimizer produces a plan with an Eager Spool (click to enlarge):

To the left of the spool, the top branch performs the DISTINCT followed by the COUNT per group, and the spool replay on the lower branch of the plan computes the SUM per group.  Finally, the two branches join on the common GROUP BY expression (EnglishProductName).

The rewrite starts by grouping on EnglishProductName (the GROUP BY expression) and SalesTerritoryKey (the DISTINCT expression) to produce a partial aggregate:

SELECT 

    dp.EnglishProductName, 

    frs.SalesTerritoryKey, 

    SUM(frs.SalesAmount) AS ssa

FROM dbo.DimProduct AS dp

JOIN dbo.FactResellerSales AS frs ON 

    frs.ProductKey = dp.ProductKey

GROUP BY 

    frs.SalesTerritoryKey, 

    dp.EnglishProductName

This query contains no distinct aggregates, so we get a plan with an ordinary join and and ordinary SUM aggregate:

To produce the results specified by the original query, we now need to SUM the partial SalesAmount sums, and COUNT (ignoring NULLs) the SalesTerritoryKey values.  The final rewrite looks like this:

WITH PartialAggregate AS

(

    SELECT 

        dp.EnglishProductName, 

        frs.SalesTerritoryKey, 

        SUM(frs.SalesAmount) AS ssa

    FROM dbo.DimProduct AS dp

    JOIN dbo.FactResellerSales AS frs ON 

        frs.ProductKey = dp.ProductKey

    GROUP BY 

        frs.SalesTerritoryKey, 

        dp.EnglishProductName

)

SELECT

    pa.EnglishProductName, 

    SUM(pa.ssa),

    COUNT_BIG(pa.SalesTerritoryKey)

FROM PartialAggregate AS pa

GROUP BY pa.EnglishProductName

OPTION (RECOMPILE)

The query plan adds another layer of aggregation on top of the partial aggregate plan above:

This plan avoids the Eager Spools seen earlier and improves execution time from 320ms to 95ms in this example.  On larger sets, where parallelism becomes important and the spools might need to use physical tempdb storage, the gains are likely to be much larger.

New for SQL Server 2012 RC0

The good news is that SQL Server 2012 RC0 adds a new optimizer rule (ReduceForDistinctAggs) to perform this rewrite automatically on the original form of the query.  This is particularly good because the rewrite, while ingenious, can be somewhat inconvenient to do in practice, and all too easy to get wrong (particularly ensuring that NULL partially-aggregated groups are handled correctly).  The new optimizer rule was not available in CTP3, so you will need RC0 to see SQL Server turn this T-SQL:

SELECT

    dp.EnglishProductName,

    SUM(frs.SalesAmount),

    COUNT_BIG(DISTINCT frs.SalesTerritoryKey)

FROM dbo.FactResellerSales AS frs

JOIN.dbo.DimProduct AS dp ON

    frs.ProductKey = dp.ProductKey

GROUP BY

    dp.EnglishProductName

OPTION (RECOMPILE)

…directly into this query plan:

This transformation is only valid for queries with a single distinct aggregate (and at least one non-distinct aggregate of course).  If your query contains multiple distinct aggregates, it may not help you directly, though you may be able to refactor the T-SQL to take advantage.

If you want to see SQL Server 2012 RC0 produce the Eager Spool plan instead (created by the long-standing ExpandDistinctGbAgg rule), disable the new rule with:

DBCC RULEOFF ('ReduceForDistinctAggs')

…and then recompile.  Don’t forget to enable it again afterward using RULEON or by reconnecting to the server.

Even with the new rule enabled, you may still see the spool or multiple-scan plan from time to time.  As always, the optimizer may explore many alternative plan forms and choose the one that looks cheapest.  In some cases, the optimizer may still choose the spool plan, though it probably won’t be right to do so…

Thanks for reading; please consider voting for the following Connect item (to allow CLR UDA hash aggregates).  Thank you.

http://connect.microsoft.com/SQLServer/feedback/details/629920/allow-option-hash-group-with-sqlclr-udas

© 2011 Paul White

Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com

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.  A page split makes room for new records, but can take time to perform and is a resource intensive operation. Also, it can cause fragmentation that causes increased I/O operations.

Given that information, how can a SELECT statement be responsible for page splits?  Well, I suppose we could SELECT from a function that adds rows to a table variable as part of its internal implementation, but that would clearly be cheating, and no fun at all from a blogging point of view.

Tables & Sample Data

To demonstrate the effects I want to talk about today, I’m going to use a couple of tables with data from the sales data in the Adventure Works sample database.  There’s a full script at the end of this post for those of you that like to run these things for yourselves, but the data generally looks like this: (header table on the left; detail table on the right):

Both tables have a clustered index on the Sales Order ID column.  The query I’m going to run is this:

I have expressed the natural join predicate as (X >= Y) AND (X <= Y) instead of (X = Y) to prevent the optimizer choosing a hash or merge join (both of which require at least one equality predicate to perform an inner join).  The “+ 0” is there to prevent the optimizer from using an indexed nested loop join (that is, using a seek on the inner side of the join).  These tricks are necessary to generate a plan with an eager index spool on this small sample data set.

Checking for Splits

There are several ways to check for page splits while this query is running.  I’m going to use the new extended events UI in SQL Server code name “Denali”, which, by the way, I’m quite impressed with: it’s a lot like using Profiler inside SSMS and does away with all that tedious mucking about with CREATE EVENT SESSION statements and XQuery (there are also no improbability factors to compute).  Ok, so running the query above and looking for page splits via extended events, I get output like this:

These page splits are all caused by the Index Spool in the query plan.  This iterator builds a temporary b-tree index on the data produced by its sub-tree, and like any index insert operation, page splits will occur.  In fact this is a bit of a cheat, because these page splits aren’t really page splits at all – notice the sequential nature of the pages being ‘split’ (the page_id column), and its relationship with the new page.

Even in Denali, we don’t yet have a nice easy way to distinguish between a traditional page split (where roughly half the existing rows are moved to a new page) and the case where a whole new page is allocated at one end of the index.  This strikes me as an amazing oversight.  I don’t know about you, but I generally don’t fret much over tables or indexes allocating a whole new page at one end to store new rows – I’m much more interested in existing index pages that need to split in half!  I certainly hope this improves before RTM.

Index Spool Internals

Having shown page splits that aren’t really page splits, let’s get to demonstrating an index spool that ‘really does’ split pages.  To do that, we need to know something about the way index spools build their temporary index.  You have probably noticed that most query plans that build permanent indexes involve a sort, which in turn requires a memory grant.

Index spools do not get a memory grant, and are not preceded by an explicit sort operator in query plans.  Given that indexes require sorting, how does an index spool manage to build a b-tree index structure at all?  The answer is that index spools just insert rows into an empty b-tree in the order they are received.  In general, the rows used for the index will not be received in sorted order, resulting in lots and lots of page splits in the temporary index b-tree.

The first run of the query did not suffer from this problem due to the clustered index on the header table, which tends to produce rows ordered by Sales Order ID – exactly the order of the index built by the index spool.  Let’s rebuild the header table clustered index to use the Customer ID column instead, and re-run the test.  The query plan looks exactly the same – the only difference is that the index spool is fed by a clustered index scan that is now extremely unlikely to produce rows in Sales Order ID sorted order:

The page splits reported by the extended events ‘trace’ are now very different:

Notice the same source page (page_id) being split over and over again as rows arrive in unsorted order.  There are now very many more page splits than before, and they are a lot more expensive because we are now not just allocating new empty pages at the end of the index – we have to shift half the rows and fix up all the page pointers.  In practice, this is the sort of splitting you are likely to see in tempdb with an index spool – rows are very unlikely to be in index order (else why would we need the spool at all?).  On that last point, consider the hoops I had to jump through to demonstrate a plan where the rows were in temporary index order – all that mess with “>= AND <=” and “+ 0”…

Parallel Index Spools

The last thing I want to cover about index spools is how they behave in parallel plans.  You might have noticed the MAXOP 1 hint in the previous examples.  Let’s remove that now, add some wait type monitoring, and see how we go:

Don’t be fooled by the parallelism indicator on the index spool – the index building portion of its execution happens on a single thread.  One way to see this is to capture thread and task information using the page splitting event session, where the same task and thread ids are reported for every one of the hundreds of events:

The wait statistics provide additional confirmation:

Ignore the CXPACKET waits (they are perfectly normal) and look at the EXECSYNC waits.  This query ran at DOP 8 on my machine, so 7 parallel threads had to wait while a single thread built the temporary index.  The index build took 114ms, and 7 threads waiting simultaneously for that time gives 7 x 114 = 798ms.  That’s within one quantum (4ms) of the total recorded EXECSYNC wait time.  EXECSYNC is used for lots of different things – whenever synchronization of parallel workers needs to occur outside a Parallelism operator, so please don’t take away the idea that EXECSYNC = index spool.

© Paul White 2011

Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com

Script:

-- Any AdventureWorks version should be fine

USE AdventureWorks2008R2

GO

-- Tables

CREATE TABLE #OrdHeader

(

    SalesOrderID        INTEGER NOT NULL,

    OrderDate           DATETIME NOT NULL,

    SalesOrderNumber    NVARCHAR(25) NOT NULL,

    CustomerID          INTEGER NOT NULL

)

GO

CREATE TABLE #OrdDetail

(

    SalesOrderID        INTEGER NOT NULL,

    OrderQty            SMALLINT NOT NULL,

    LineTotal           NUMERIC(38,6) NOT NULL

);

GO

-- Data

INSERT #OrdHeader

SELECT

    h.SalesOrderID,

    h.OrderDate,

    h.SalesOrderNumber,

    h.CustomerID

FROM Sales.SalesOrderHeader AS h

GO

INSERT #OrdDetail

SELECT

    d.SalesOrderID,

    d.OrderQty,

    d.LineTotal

FROM Sales.SalesOrderDetail AS d

GO

-- Clustered indexes

CREATE UNIQUE CLUSTERED INDEX cuq ON #OrdHeader (SalesOrderID) WITH (MAXDOP = 1)

CREATE CLUSTERED INDEX cuq ON #OrdDetail (SalesOrderID) WITH (MAXDOP = 1)

GO

-- Test query

SELECT

    d.OrderQty,

    h.SalesOrderNumber,

    h.OrderDate

FROM #OrdDetail AS d

JOIN #OrdHeader AS h ON

    d.SalesOrderID >= h.SalesOrderID + 0

    AND d.SalesOrderID <= h.SalesOrderID + 0

OPTION  (MAXDOP 1)

GO

-- Lose the ordering

CREATE CLUSTERED INDEX cuq ON #OrdHeader (CustomerID) 

WITH (DROP_EXISTING = ON, MAXDOP = 1)

GO

SELECT

    d.OrderQty,

    h.SalesOrderNumber,

    h.OrderDate

FROM #OrdDetail AS d

JOIN #OrdHeader AS h ON

    d.SalesOrderID >= h.SalesOrderID + 0

    AND d.SalesOrderID <= h.SalesOrderID + 0

OPTION  (MAXDOP 1)

GO

-- Parallelism

DBCC SQLPERF('sys.dm_os_wait_stats', 'CLEAR')

GO

SELECT

    d.OrderQty,

    h.SalesOrderNumber,

    h.OrderDate

FROM #OrdDetail AS d

JOIN #OrdHeader AS h ON

    d.SalesOrderID >= h.SalesOrderID + 0

    AND d.SalesOrderID <= h.SalesOrderID + 0

GO

SELECT

    ows.wait_type,

    ows.waiting_tasks_count,

    ows.wait_time_ms,

    ows.max_wait_time_ms,

    ows.signal_wait_time_ms

FROM sys.dm_os_wait_stats AS ows

WHERE

    ows.wait_type IN (N'CXPACKET', 'EXECSYNC')

GO

DROP TABLE 

    #OrdHeader, 

    #OrdDetail

GO

/*

-- Denali Extended Events Session Script (change the session_id filter!)

-- Try the UI :)

CREATE EVENT SESSION [Page Splits] ON SERVER 

ADD EVENT sqlserver.page_split

    (

    ACTION(sqlos.system_thread_id,sqlos.task_address,sqlserver.sql_text)

WHERE 

    ([package0].[equal_uint64]([sqlserver].[session_id],(60)))) 

ADD TARGET 

    package0.ring_buffer(SET max_memory=(65536))

WITH 

(

    MAX_MEMORY=4096 KB,

    EVENT_RETENTION_MODE=ALLOW_SINGLE_EVENT_LOSS,

    MAX_DISPATCH_LATENCY=30 SECONDS,

    MAX_EVENT_SIZE=0 KB,

    MEMORY_PARTITION_MODE=NONE,

    TRACK_CAUSALITY=OFF,

    STARTUP_STATE=OFF

)

*/

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 unique clustered index):

CREATE TABLE dbo.SeekTest

(

    col1    BIGINT NOT NULL,

);

GO

-- Non-unique clustered index

CREATE CLUSTERED INDEX cx

    ON dbo.SeekTest (col1)

GO

CREATE TABLE dbo.SeekTestUnique

(

    col1    BIGINT NOT NULL

);

GO

-- Unique clustered index

CREATE UNIQUE CLUSTERED INDEX cuq

    ON dbo.SeekTestUnique (col1)

Test Data

This time, instead of filling the tables with all the numbers from 1 to 5 million, we’ll add just the even numbers from 1 to 10 million.  At the risk of stating the slightly obvious, this results in tables with the same number of rows as previously, just no odd numbers:

INSERT dbo.SeekTest WITH (TABLOCKX)

    (col1)

SELECT TOP (5000000)

    2 * ROW_NUMBER() OVER (ORDER BY @@SPID)

FROM 

    master.sys.columns AS c,

    master.sys.columns AS c2,

    master.sys.columns AS c3;

GO

INSERT dbo.SeekTestUnique WITH (TABLOCKX)

    (col1)

SELECT TOP (5000000)

    2 * ROW_NUMBER() OVER (ORDER BY @@SPID)

FROM 

    master.sys.columns AS c,

    master.sys.columns AS c2,

    master.sys.columns AS c3;

Test Run: Non-Unique Index

The test is the same as before: join the test table to itself using a nested loops join, and count the rows returned.

Don’t be fooled by the simplistic nature of the test; I realize you rarely use loops join to self join all the rows in a table.  The point here is to check how long it takes to perform 5 million row joins – something that probably happens quite often in most production systems, either as 5 million lookups into a single very much larger table, or perhaps by running a query that does 50,000 row-joins 100 times.  Anyway, here’s the query:

SELECT 

    COUNT_BIG(*)

FROM dbo.SeekTest AS st WITH (TABLOCK)

INNER LOOP JOIN dbo.SeekTest AS st2 WITH (TABLOCK)

    ON st.col1 = st2.col1

OPTION (MAXDOP 1);

And the ‘actual’ query plan:

I get these results:

Notice the 5,000,001 scan count showing that we are performing 5 million range scans (not singleton seeks).  As far as performance goes, running this query with all the data in cache uses 9,251ms of CPU.

Test Run: Unique Index

Cool.  Now we know from last time that we can improve on this result by making the index unique, and performing singleton seeks instead of range scans.  Let’s do that then:

SELECT

    COUNT_BIG(*)

FROM dbo.SeekTestUnique AS stu WITH (TABLOCK)

INNER LOOP JOIN dbo.SeekTestUnique AS stu2 WITH (TABLOCK)

    ON stu.col1 = stu2.col1

OPTION (MAXDOP 1);

Actual plan:

And the results are:

As expected, the scan count confirms we are now doing singleton seeks, and the CPU time has improved to 16,005ms.

Er, Hang On…

If you think that going from 9,251ms of CPU to 16,005ms of CPU is not exactly an improvement, you’d be right.  There’s no typo there, no inadvertent switching of the unique and non-unique examples, and no tricks.

Making the index unique really has slowed down this query by around 70%.

The explanation is so interesting, it deserves a full post of its own…so stay tuned for that.  Feel free to speculate about the cause in the meantime… in the comments below, by email, or on Twitter.

There is some evidence coming through in the comments that this behaviour is specific to x64 installations. I’d love to get some more validation of this if you have time to test on x86 and/or x64. Thanks.

Disclaimer:

In general, you will want to specify an index as UNIQUE wherever you can.  Many queries will benefit from a unique index rather than a non-unique one.  This post is very much to show that “It Always Depends” and to set the stage for the next post in this series.  Don’t run with scissors.  Warning filling may be hot.  May contain nuts…

© 2011 Paul White
email: SQLkiwi@gmail.com
twitter: @SQL_Kiwi