THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Paul White: Page Free Space

A technical SQL Server blog from New Zealand. See also my articles on SQLperformance.com

Query Optimizer Deep Dive – Part 3

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:

Cost-Based Optimization Input Tree

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

Optimizer Initial Memo Contents

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

Trace Flag 8608 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:

sys.dm_exec_query_optimizer_info

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:

Final Memo Trace Flag 8615 Contents

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:

Good Enough Plan Found

Optimized Query Plan

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

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

Published Sunday, April 29, 2012 9:30 PM by Paul White

Attachment(s): Deep Dive.zip

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

Paul White: Page Free Space : Query Optimizer Deep Dive ??? Part 2 said:

April 29, 2012 3:37 AM
 

mordechai danielov said:

Thanks Paul, there is such a dearth of information on query plans and internals of the query optimizer that every bit of new knowledge is refreshing.

April 30, 2012 2:54 AM
 

Paul White: Page Free Space said:

This is the final part in a series of posts based on the content of the Query Optimizer Deep Dive presentations

April 30, 2012 9:36 AM
 

Paul White: Page Free Space : Query Optimizer Deep Dive - Part 1 said:

September 1, 2013 6:18 AM

Leave a Comment

(required) 
(required) 
Submit
Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement