How does the MySQL Optimizer work
Presenter: Timour Katchaounov Time: Thursday 29. March 2007 RESCHEDULED to: Time: Thursday 05. April 2007, at 6am PST = 9am EST = 15 CET = 16 EET Estimated length of Session: '01:30 to 2:00 h'presenter to fill in here - note max 3 hours Moderator: Patrik Backman Scribe: Paul DuBois Attendees: To register for this Session - Please enter your name here: Brian Miezejewski Alexander Nozdrin Andrey Hristov Hakan Kuecuekyilmaz Marc Alff Sergei Golubchik Giuseppe Maxia User:TatjanaNurnberg Matthias Leich Axel Schwenke LarsThalmann Chris Powers IgnacioGalarza Jeffrey Pugh User:TimSmith User:GuilhemBichot GeorgiKodinov SergeyPetrunia Max Mether Kristofer Pettersson Holyfoot Jess Balint Oleksandr Byelkin David Swain Evgeny Potemkin Josh Chamas David Axmark
[edit] How_does_the_MySQL_Optimizer_work
https://inside.mysql.com/mywiki/skins/common/images/button_italic.png Presentation slides: PDF slides
[edit] Outline
- Basics
- what is a query optimizer
- query plans and their execution
- box-structure of the query engine
- Query optimization
- Logical transformations
- Cost-based optimization
- Plan refinement
[edit] “Query optimizer” = “automatic program generator”
[edit] Query execution
[edit] Query Execution Plans as operator trees
[edit] Example: “World” database
[edit] Query Execution Plans as operator sequences
[edit] Basic nested loops join
procedure nested_loops_join
input: <OP_i, ..., OP_n> - the remainder of a QEP
that has not been computed yet
{
if (init_record_scan(Table_i, Access_i, Cond_i) == EOF)
return
while (curr_row_i = get_next_record(Table_i, Aaccess_i, Cond_i))
{
joined_row = <curr_row_1 || ... || curr_row_i>
if JoinCondition_i(joined_row) /* Test the join condition. */
{
if joined_row is a complete result tuple (i.e. i = n)
output joined_row
else
nested_loops_join(<OP_[i+1], ..., OP_n>)
}
}
}
[edit] Architecture
[edit] Query engine architecture
[edit] MySQL architecture
[edit] Query optimizer modules: highly interwoven
[edit] Query optimizer outline
[edit] Query optimization: logical transformations
[edit] Equality propagation
- New plans because of new equality conditions
- Constants propagated so that we get new SARGable conditions
- Result
- Better index use
- More join predicates, more join orders
- Sample improvement: 2.4 times - 4.1 vs 5.0
- t1(1000), t2(1000000) rows
- SELECT * FROM t1,t2 WHERE t1.id=t2.id AND t1.k=t2.k AND t2.k BETWEEN 498 AND 597
[edit] Nested outer join execution, outer => inner transformation
[edit] Cost-based query optimization
- General idea:
- assign cost to operations
- assign cost to (partial) plans
- search for plans with lowest cost
- Possible because:
- query plans are simple
- there is data statistics
- there is meta-data
- Main characteristics of an optimizer:
- search space (possible plans)
- cost model
- search procedure
[edit] Cost model
- Cost ~ disk accesses
- Cost unit = random read of a data page (4 Kb)
- Main cost factors
- Data statistics:
- number of pages per table (index) - P(R) (or P(I) )
- cardinality of tables/indexes - N(R)
- length of rows and keys
- key distribution
- Schema:
- uniqueness (PK)
- nullability
- Data statistics:
- Simplified cost model (table scan):
- cost(access(R)) ~ P(R)
- cost(R join S) ~ P(R) + N(R) * P(S)
[edit] Table-order independent optimization
[edit] The ref optimizer
SELECT * FROM t1,t2,t3 WHERE t1.a = t3.c AND t2.b = t3.c;
Given indexes t1(a), t2(b) and t3(c), the ref optimizer produces the equi-join graph:
t1-- a ->- c --- --- c -<- b --- t2
^ | | ^
| | | |
-- a -<- c - v v-- c ->- b ----|
t3
where the arcs mean: [source of lookup value] -> [table/column to lookup]
[edit] Constant table detection/propagation
- find constant/system tables known to have 0/1 rows
- use the result of the ref optimizer + information about unique indexes
- replace columns with constants
- performs data access to retrieve constant rows
- may complete query execution at this point (e.g. detect empty queries)
[edit] The range optimizer
[edit] Cost-based join optimization
[edit] Query optimization - exhaustive search
- Search all plans “bottom-up”:
- begin with all 1-table plans
- for each plan QEP = <T1, ..., Tk-1>
- expand QEP with remaining {Tk, ..., Tn} tables
- if cost(<T1, ..., Tk>) < cost(best complete plan so far)
- Use the principle of optimality for pruning: “The sub-plans of an optimal plan are optimal for their size”
- The procedure “walks” over a search tree (==> next slide)
[edit] Depth-first search illustrated
[edit] The cost of optimization
- Exhaustive search with pruning still ~ N!
- for N > 13-14 => several hours/days
- => exhaustive search infeasible for big queries
- “Greedy search” in MySQL 5.0
- control how exhaustive - search depth
- each search step:
- estimate each potential extension up to search depth
- pick the best extension => “greedy”
- “forget” other extensions
- continue with remaining tables
- may miss the best plan => trade off
[edit] The “greedy” search procedure
[edit] Controlling the optimizer
- Control of access method selection
- use index: SELECT * FROM City USE INDEX (Country), ...
- force index: SELECT * FROM City FORCE INDEX (Country), ...
- ignore index: SELECT * FROM City IGNORE INDEX (Population), ...
- Control of join optimization
- degree of exhaustiveness - “optimizer_search_depth”: 0 => automatic; 1 => minimal; 62 => maximal (default)
- pruning - “optimizer_prune_level”: 0 => exhaustive; 1 => heuristic (default)
- force join order - STRAIGHT_JOIN: SELECT * FROM (CountryLanguage STRAIGHT_JOIN City) STRAIGHT_JOIN Country WHERE ...;
[edit] Plan refinement
- Condition pushdown
- Adjust data access methods after push-down analysis
- Optimize ORDER BY/DISTINCT
- Pre-create temporary tables
- Initialize all structures related to query execution
[edit] Topics for future presentations
- Details of various optimization phases
- outer => inner join transformation
- partition pruning
- range/ref optimization
- condition pushdown
- Subquery optimization & execution
- Join execution details (Monty?)
- Data access methods (index merge, loose index scan, etc.)
- other new and old functionality ...
[edit] Session notes
- Voice Recording: https://docsrva.mysql.com/MySQLU/MySQLU-How_Optimizer_Works.ogg
[edit] Questions posted for the Session
SLIDE 8: Basic nested loops join
- andrei: timour, where OP_i is in args of init_record_scan?
- timour: andrei: Table_i <==> OP_i.Table_i
- timour: there is 1:1 correspondence, this is pseudocode
- andrei: timour, so prefix is just omiiited, okay.
SLIDE 10: Query engine architecture
timour: Preprocessor ~ JOIN::prepare
timour: Optimizer ~ JOIN::optimize
- alik: Don't we do some of name resolution, etc in sql_yacc.yy, which is The Parser?
- andrey: he said it does more than just parsing :)
- alik: Ok, so The Preprocessor is divided between sql_yacc and JOIN::prepare
- alik: right?
- timour: alik: most of name resolution is done in Item::fix_fields
- timour: and setup_tables()
- andrey: and fix_fields should not be called at parsing phase, because it break prepared statements..
SLIDE 11: MySQL architecture
- andrei: query cache must an object for optimization?
- psergey: andrei: no they are totally unaware of each other
- timour: andrei: should be, but I think it has nothing to do with optimization right now
- psergey: Query cache check is performed before the optimizer is invoked
- psergey: The optimizer cannot [re]use any of the contents of the query cache
- andrei: psergey, technically yes. Principally - it's an optimization :)
- sanja: andrei: QC use text of the query and store result as it was sent to the client
SLIDE 17: Cost-based query optimization
- alik: Does the cost-optimizer store some of its data for query to query?
- sanja: AFAIK no
- alik: I mean, is there any data, that is calculated (updated) on executing Q1 and is used in Q2.
- timour: alik: you mean prepared statements? Then NO.
- alik: Well, I mean, does optimizer have state.
- psergey: alik: for NDB engine, the results if handler->records_in_range(lower_bound, upper_bound) do depend on the history of previous calls
- psergey: that is the only exception
- alik: psergey: and where this "history" is stored?
- alik: is it lost on restart?
- psergey: alik: somwehere whithin NDB table handler
- psergey: yes it is lost.
SLIDE 24: Query optimization - exhaustive search
- Azundris: andrei: If we get to throw away redundant sub-ranges etc., it seems like an optimization, arguably?
- andrei: azundris, yes, but only after some zero intersection will be evaluated . So optimization here as i see is about to remove empty sub-ranges.
SLIDE 27: The "greedy" search procedure
- TheK: timour: In the actual code these structures are lists (which structure?) of JOIN_TAB (ref as OP_i before) ? or. in other words, do you have a code ref we can look at?
- timour: thek: what we reorder is a an array of JOIN_TAB pointers
- timour: the array is part of the JOIN object
- joro: TheK: the function is greedy_search()
Post-Slide Discussion
joro: here's our optimizer team KB page : https://inside.mysql.com/wiki/OptimizerKBAndTodo
- andrei: timour, you were saying that greed alg can consider up to 7 tables at a step, not just 2 as the slide depicted?
- timour: andrei: it can consider up to total number of tables in the query
- andrei: timour, what is the major diff between ideas of The ref optimizer and query optimization (greedy search)?
- timour: andrei: ref optimization is more like a "preparation for join optmization:"
- timour: it compiles all possible ref accesses in a convenient structure
- timour: then, when the join optimizer looks at table XYZ at position "i", and it has tables T1, T2 before that in the plan, it can easily check what possible indexes can be accessed given those tables provide constants
- timour: sorry, provide column bindings
- timour: andrei: the main difference is that one is table-order independent choice of access method based on what we know for each table.
- timour: So we compile all possible index accesses for the query.
- timour: Then when the join optimizer searches for best order, it picks among the best table access method among the ones prepared by the ref and the range optimizers, and table and index scan.
- timour: andrei: clear?
- andrei: timour, warmer :) so ref optimization is over independent tables?
- andrei: timour, so ref opt results in the graph so that main opt knows that a possibility of a particular access order: t -> s ...
- timour: andrei: yes
- JoshChamas: I am particularly interested in types of HASH join, subquery type optimizations, MRR/batch key for Cluster, are these on the schedule for a future class (also discussed what is in progress for 5.2?)
- timour: JoshChamas: yes, in this order:
- timour: - subquery optimization is for 5.2
- timour: - MRR/BKA is for 5.2 (I think)
- timour: - hash join is next, most likely for 6.x
- serg: timour: how optimizer takes into account condition push-down ?
- timour: serg: the join optimizer doesn't take join condition pushdown at all if that is what you meant.
- timour: If you mean pushing conditions down to indexes (single-table conditions), then
- serg: timour: but you wrote "Adjust data access methods after push-down analysis"
- timour: yes, that is after the join order is fixed
- serg: what is adjusted ?
- timour: for example it may change a table scan to "range checked for each record"
- timour: because at this point the table order is known
- timour: so we know that for some range conditions there will be bindings from previous tables
- timour: serg: there is some questionable heuristics for this
- timour: since we don't take into account the cost of running the range optimizer itself for each intermediate result.
- serg: okay. but still no statistics back from the storage engine to the optimizer about the selectivity of pushed conditions ?
- timour: serg: no, no statistics
- timour: we don't estimate condition selectivity in general
- timour: only for range conditions when evaluating possible range accesses (and also for ref accesses)
- timour: But we have no information to evaluate the selectivity of join conditions.
- timour: serg: this is subject to a serious project, as we need to collect data statistics, build histograms, or at least
- timour: figure MIN/MAX values per column, and exact cardinality.
- serg: no, I don't think you should do it. A push-down condition means that storage engine is responsible for for filtering. Equally it's responsible for selectivity estimation When MySQL executes the join and filtering - it performs the estimation when storage engine does it as a black-box, it handles everything
- timour: serg: well, depends what you mean by "push-down" - it is used in 2 senses (at least):
- timour: - push to engine, or
- timour: - push down in the join tree
- serg: I mean push-to-engine
- serg: no, that's make_cond_for_table
- serg: let's use a different term for it :)
- timour: I meant that in the latter case we don't do anything now to estimate selectivity.
- timour: (well the general literature uses this term)
- timour: serg: it's not that simple, because for some engines, you may be able to push join conditions too.
- serg: yes, but it doesn't change what I said :)
- timour: Then in both cases we need an interface to be able to give the engine some condition, and ask it: "tell me the selectivity (or number of rows) of this condition"
- bski: Yes! (from nitro)
- serg: agree
- bski: This is a real problem for Nitro SE
- andrei: timour, do you see anything which can help to speed up rbr event appying , some token of master's optimazer to hint slave?
- timour: andrei: honestly - no idea - I don't know well enough rbr to suggest anything.
- andrei: timour, rbr is a form of digested query. But there is no optimizer's info in the stuff.
- timour: andrei: is "rbr" == "row based replication" ?
- andrei: s/rbr/row-base-replicaton event/
- andrei: timour, yes
- timour: andrei: does rbr run queries on the remote site?
- timour: (slave I suppose?)
- sanja: it should not IMHO :)
- andrei: timour, no queries - but assuming binary data - result of "digesting" have prim key value, then the row is found and modified.
- andrei: timour, actually there is little room for optimization i think.
- timour: andrei: it seems you always know what data you have, so you have a predifined access method to the data to find a row.
- andrei: timour, yes.
- andrei: timour, it might relate to engine optimization.
- timour: more likely