Logical trees shine a light into the SQL Server optimizer. This step-by-step guide will explain those trees - and how they evolve into a query plan.
To get things started we'll take a look at the bigger picture of query optimization.
Some history
Query optimizers are sometimes described as the secret sauce of database software. Indeed, the performance difference between a bad query plan and a good one can be far beyond that given by the most lavish spend on hardware. It is no surprise then that many SQL developers and DBAs want to learn more about the optimizer they use.
The science of query optimization goes back further than many realize. In 1979 Patricia Selinger and her colleagues at IBM delivered what would become a seminal white paper in the world of database software. It was part of the experimental System R project that would later evolve into IBM's now long established DB/2 product.
The paper covered the fundamentals of query optimization including search trees, costing, and join types that will be familiar to any keen SQL developer forty years later.
Before we get into the detail of logical trees - and how they evolve into a query plan that can be executed - we need to see how they fit into the optimizer as a whole.
At the end of this post I'll give a brief overview of the optimizer. But rather than just scratch the surface, here's two better resources - I'd recommend you watch and read both.
Conor Cunningham: Inside the SQL Server Query Optimizer
Conor is an architect on the SQL Server development team, with a leading role in the evolution of the optimizer. His one hour presentation from SQLBits IV is well worth watching end to end.
If you see a "plugin not supported" message, don't rush to start installing ageing plugins with dubious security - just download the video using the link in the right hand sidebar. It's a WMV file - if you're using a Mac or iOS, you can play this using a third party player. For the Mac, my personal favourite is Iina.
Paul White: Query Optimizer Deep Dive
For more than a decade, Paul has wowed the SQL Server community with his in-depth understanding of the optimizer. In this series of four blog posts he gives detailed examples using SQL queries, showing the resulting trees and the optimizer rules that shape the query into a final plan.
Building an optimizer is hard
The challenges in programmatically optimizing queries can be significant.
There may be more possible plans than there is time to evaluate. Combinations of join orders, filter placement, physical join types and table access methods, can lead to an unmanageable number of possible plans.
Even a reasonably modest query can produce a vast number of possible plans. Each consumes memory, and CPU time to produce and cost. For some queries, if every possible plan is considered, the exploration would not complete in a lifetime.
Row counts are pivotal in optimization but may be difficult to estimate. When an optimizer considers choices such as join order or physical join type, a key factor in the choice is the anticipated number of rows output by a given step. Estimates based on statistical techniques such as histograms may not cover every query accurately.
Also, some estimates are fundamentally difficult to produce - such as those based on the effect of a number of predicates across multiple tables. Additionally, errors in estimates can be cumulative: where one bad estimate feeds another progressively worse estimate in the next step of the plan.
If the estimates are grossly wrong, a bad plan is the likely outcome.
Opportunities for simplification are numerous - not all cases may be recognised or accounted for. Without a specific optimization for a defined scenario, an optimizer may produce a plan that does unnecessary work.
Opportunities for simplification include eliminating joins, sections of plans that will not produce rows, or calculations that can be done before the main query execution. Those examples just scratch the surface of possible savings.
As an optimizer matures, new functionality brings diminishing returns or even regression. In the early stages of development there are wins to be had that are both significant for query performance and relatively easy to implement. As an optimizer matures the wins may be harder to find, harder to develop, and lesser in impact. At the extreme end, some new optimizer mechanisms may actually degrade the performance of some queries.
The possibility of this regression can make a development team risk averse in implementing new ideas.
One mitigation is to offer the ability to disable a new feature. This comes with an implicit and potentially significant burden for the customer - testing a production workload to measure performance and identify what parts of a workload benefit or regress. For many applications, testing of this nature is not a trivial task. Few customers do it comprehensively.
The SQL Server optimizer has functionality covering all of these challenges except the last - which is instead mitigated with the new Query Store functionality introduced in SQL Server 2016. To learn more, check out Erin Stellato's excellent posts and training resources.
If you have time to spare, David J. DeWitt digs into some of the optimization challenges in this presentation hosted by Brent Ozar. It's 100 minutes, but has some interesting detail, including a few nuggets of insider information from his time at Microsoft with the SQL Server team.
David J. DeWitt, MIT - SQL Query Optimization: Why is it so hard to get right?
If you have time to spare, David J. DeWitt digs into some of the optimization challenges in this presentation hosted by Brent Ozar. It's 100 minutes, but has some interesting detail, including a few nuggets of insider information from his time at Microsoft with the SQL Server team.
David J. DeWitt, MIT - SQL Query Optimization: Why is it so hard to get right?
The SQL Server Optimizer - a brief overview
Hopefully you'll have now watched or read some of the optimizer deep dives linked above. Here's a quick recap. It is somewhat simplified - we'll see more detail in the next post.
Simplification
A variety of simplifications are applied, including elimination of redundant joins, unused calculated columns and detecting contradictions.Create/Update Stats
For columns that might influence the plan, statistics are either updated or created as required. This may also occur later, if new plans are created that then demand it.
Derive Cardinality
Row counts are estimated for the key operations in the plan.
Fix Initial Join Order
Using the cardinality estimates from the previous step, an initial join order is set. Later explorations may produce alternative orders for costing.
Trivial Plan
If the tree is simple enough, a best plan can be determined without needing to cost various alternatives. In this case, exploration is skipped and the optimizer moves on to copying the plan out, nearing the execution stage.
Exploration Stage 0
Different serial plans are explored, aimed at optimizing OLTP queries.
A final plan may determined at this stage for two reason. Firstly if the optimizer deems the best plan so far "good enough" - i.e. if further exploration is not expected to be worthwhile. Secondly, the optimizer may simply declare a time out - limiting the duration of the work, and returning the best plan when the exploration duration has reached a threshold.
Exploration Stage 1
Also know as Quick Plan. More rules are tried and resulting plans explored, including a potential second phase that explores parallel plans if the cost of the best serial plan exceeds a threshold.
A final plan may be declared here, for the same reasons as the previous stage.
A final plan may be declared here, for the same reasons as the previous stage.
Exploration Stage 2
More rules and plans are explored, and again with the same overall exit criteria as the previous stage.
Once a decision has been made between a serial or parallel plan at the end of stage 1, stage 2 (if entered) is committed to producing the same type. In other words, S2 only explores serial OR parallel, depending on the cost situation at the end of S1. (Paul White)
- Optimization leverages serious computer science dating back over 40 years.
- In the early stages of optimization, a logical plan is shaped and simplified.
- In later stages of optimization, thousands of physical plans may be explored.
- The optimizer tries to find a good enough plan, in a reasonable amount of time. Not necessarily the best plan.
In part 2 we will look at the different types of logical tree, and the types of operators they contain.
No comments:
Post a Comment