Join-order search — why query planning is factorialMySQL 8.4 • MariaDB 11.4

The greedy_search algorithm enumerates partial plans up to optimizer_search_depth tables ahead, costed by the optimizer, pruned by optimizer_prune_level.

Parameters

Real OLTP joins rarely exceed 6 tables; warehouse queries can hit 15+.
Default is MAX_TABLES+1 = 62 (effective exhaustive). 1 = pure greedy.
Set 0 only when debugging; pruning is what keeps planning sub-millisecond.
Hypergraph (DPhyp) is set-based with optimizer_max_subgraph_pairs cap.

Join-order search animation

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 as candidate roots — every search starts by picking one of them as the outermost loop.
  • Center: the search tree of partial plans. Each node is a (partial-order, cost) pair the planner evaluated.
  • Yellow pulses = a partial plan is being costed by best_extension_by_limited_search.
  • Grey-out = optimizer_prune_level=1 dropped this branch because its partial cost already exceeded the best complete plan found so far.
  • Bottom strip: the chosen final order — what EXPLAIN would print.
  • Counter (top-right of stage): how many partial plans were actually evaluated. Watch it explode when you raise search_depth and turn pruning off.
Adjust parameters, then press Play
0.0s 0.0s

Cost readout (updates live)

N (tables) ?Number of non-eq_ref tables plus eq_ref groups. const and eq_ref tables are pre-placed by the planner and do not enter greedy_search.

—

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 sql_planner.cc line 2311: 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; real OLTP plans see 60-90%.

—

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 costed. 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). Setting it to 0 tells the server to pick a value automatically. Session-tunable, so you can drop it per-query if planning is a bottleneck.
  • optimizer_prune_level = 1 (cost-based pruning enabled). Set 0 only when you need to compare what the planner would have chosen without heuristics — never in production.
  • optimizer_max_subgraph_pairs = 100000. Only the hypergraph (DPhyp) optimizer respects this; it's the modern set-based optimizer enabled per-query via SET optimizer_switch='hypergraph_optimizer=on' on MySQL 8.0+.

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 and eq_ref chains are placed before greedy_search runs, so a 10-table join can have N=3 if seven of the joins are 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 lines 2275-2334 in mysql-server master. MariaDB Knowledge Base "Optimizer Switch".