Parameters
About this exampleJoin-order search animation
About this example
Example query this animation executes
-- Seven-table join: the planner must pick an order before execution SELECT u.name, SUM(li.qty * li.unit_price) AS revenue FROM users u JOIN orders o ON o.user_id = u.id JOIN line_items li ON li.order_id = o.id JOIN products p ON p.id = li.product_id JOIN suppliers s ON s.id = p.supplier_id JOIN categories c ON c.id = p.category_id JOIN warehouses w ON w.id = li.warehouse_id WHERE u.country = 'US' AND s.region = 'EU' GROUP BY u.name;
7! = 5,040 possible left-deep orders. EXPLAIN shows the one MySQL picked; this lesson shows the search that picked it.
What you'll see in the animation
- Top: the N tables (u = users, o = orders, li = line_items, p = products, s = suppliers, c = categories, w = warehouses) as candidate roots. Every search starts by picking one of them as the outermost loop.
- Center: the search tree of partial plans, three levels of it. Each node is a partial join order the planner costed; the path from the top to a node is that order.
- Orange pulses = a partial plan is being costed by best_extension_by_limited_search. Green = the cheapest order so far, which the search extends.
- Grey, dashed branches = optimizer_prune_level=1 dropped them: an earlier candidate at the same step read no more rows and cost no more, so their extensions are never explored. With 0 every drawn branch is costed.
- Bottom strip: the chosen final order, what EXPLAIN would print. Counter (top right): how many partial plans were costed; watch it explode when you raise search_depth and turn pruning off.
- Next step plays one stage of the search at a time; the simplified code beside the drawing highlights the lines each step runs.
Cost readout (updates live)
N (tables) ?Tables the search must order. const tables are placed first and do not count, and with MySQL's prune_level 1 or MariaDB's 2 a chain of eq_ref joins is added as one group, so the source counts non-eq_ref tables plus eq_ref groups.
—
effective_search_depth ?min(optimizer_search_depth, N). When equal to N the search reduces to full exhaustive enumeration.
—
Plans evaluated ?Concrete count for this N and depth. The number of times best_extension_by_limited_search is called.
—
Worst-case complexity ?From the comment above greedy_search (sql_planner.cc in MySQL, sql_select.cc in MariaDB): when search_depth >= N, greedy_search is O(N!). For smaller depth d: O(N * N^d / d).
—
Pruning ratio ?Fraction of partial plans that optimizer_prune_level=1 dropped before evaluating their full subtree. 0% means pruning is off. This lesson assumes 75%; the real share depends on the query and its statistics.
—
Planning time estimate ?At ~1 microsecond per partial plan on modern hardware. Compare to query execution: if planning approaches execution cost, raise optimizer_prune_level or lower optimizer_search_depth.
—
Plans evaluated vs N (log–log)
Learn more — what the source actually says about greedy_search
The algorithm is Optimize_table_order::greedy_search
in sql/sql_planner.cc. The doxygen comment above its
body documents the complexity directly:
procedure greedy_search
input: remaining_tables
output: pplan;
{
pplan = <>;
do {
(t, a) = best_extension(pplan, remaining_tables);
pplan = concat(pplan, (t, a));
remaining_tables = remaining_tables - t;
} while (remaining_tables != {})
return pplan;
}
"the worst-case complexity of this algorithm is
<= O(N * N^search_depth / search_depth).
When search_depth >= N, then the complexity
of greedy_search is O(N!)."
Why N!, intuitively? A left-deep plan over N
tables is an ordering — there are N! orderings. With
search_depth ≥ N and pruning off, every ordering is
considered; the only orders cut short are those already costlier
than the best complete order found so far, a bound both servers
always apply. With a depth limit d, only the next
d tables are enumerated exhaustively before the search
commits to a partial prefix, so the bound drops to
O(N · Nd / d).
Defaults you might tune (MySQL 8.4 / MariaDB 11.4):
optimizer_search_depth= 62 (MAX_TABLES + 1) in both. Setting it to0tells the server to pick a value automatically: the number of tables plus one for up to 7 tables, otherwise 7. Session-tunable, so you can drop it per-query if planning is a bottleneck.optimizer_prune_level= 1 on MySQL (0 or 1): skip a partial order that reads no fewer rows and costs no less than one already costed at the same step, and add a chain of eq_ref joins as one group. MariaDB accepts 0 to 2 and defaults to 2, the level at which MariaDB groups eq_ref chains. Set0only when you need to compare what the planner would have chosen without heuristics, never in production.optimizer_max_subgraph_pairs= 100000. Only MySQL's hypergraph (DPhyp) optimizer respects this. MySQL builds before 9.7 include that optimizer only in debug builds by default; from 9.7 the build includes it by default, and it stays off untilSET optimizer_switch='hypergraph_optimizer=on'. MariaDB has no hypergraph optimizer.
N is not always the table count in your FROM clause.
The source comment is precise: "N is the number of non-eq_ref
tables + eq_ref groups, which normally are considerably less than
total numbers of tables in the query." const
tables are placed before greedy_search runs, and with
MySQL's optimizer_prune_level=1 or MariaDB's
2 a chain of eq_ref joins is added as one
group during the search, so a 10-table join can behave like N=4 (three
tables plus one eq_ref group) if the other seven tables form one chain
of primary-key equi-joins.
How is this different from the join algorithms?
Hash join, BNL, nested loop are execution strategies — they
decide how a single join *runs* once the planner has fixed its place
in the tree. greedy_search is the layer above: given a
multi-way join, which pair joins first? Which result becomes the
outer side of the next join? EXPLAIN's table-order column is the
output of this search.
Sources: MySQL 8.4 Reference Manual §10.9.3 (Controlling
Switchable Optimizations); sql/sql_planner.cc
(greedy_search, best_extension_by_limited_search)
in mysql-server 8.4 and 9.7; sql/sql_select.cc (the same
functions) and sql/sys_vars.cc in MariaDB. MariaDB
Knowledge Base "Optimizer Switch".