skip to content

What is the difference between a left-deep and a bushy join tree, and why do many query optimizers restrict their search to left-deep plans?

level: middleimportance: should knowfreq 38%

answer

  1. Left-deep: right input always a base table
  2. Bushy: both inputs can be intermediates
  3. n! vs (2n-2)!/(n-1)!
  4. Left-deep pipelines with index nested loops
  5. Bushy wins on star shapes + parallelism

basics

~20 s

In a left-deep tree every join's right input is a base table, so joins form a pipeline. In a bushy tree both inputs can be intermediate results. Left-deep shrinks the search space from about (2n-2)!/(n-1)! to n! and pipelines well, but bushy plans can be far better for star-shaped queries and parallel execution.

solid answer

~50 s

A **left-deep** tree chains joins: the output of one join is the left (outer) input of the next, and the right (inner) input is always a base table. A **bushy** tree lets both inputs of a join be intermediate results, e.g. `(A⋈B)⋈(C⋈D)`. A **right-deep** tree is the mirror image, where the left input is always a base table. Optimizers restrict to left-deep for two reasons. First, the space shrinks from roughly `(2n-2)!/(n-1)!` to `n!` — about 17 million down to 40,320 at eight tables — which is what makes exhaustive dynamic programming feasible. Second, left-deep plans **pipeline** naturally with index nested-loop joins: rows stream from the bottom up, only the base-table side needs to be probed, and little needs materializing. Bushy plans win when two independent, highly reducing sub-joins exist — typical of star and snowflake queries — and when you want independent subtrees running in parallel. Most modern optimizers therefore allow bushy shapes, sometimes only in limited form.

code

text · 8 lines
text
left-deep:            bushy:
      ⋈                   ⋈
     / \                 / \
    ⋈   D               ⋈   ⋈
   / \                 / \ / \
  ⋈   C               A  B C  D
 / \
A   B

go deeper

for a junior

Be able to draw both shapes and say left-deep always joins the running result to one more base table.

for a middle

Quantify the search-space difference and explain pipelining with index nested-loop joins as the practical benefit.

for a senior

Argue when bushy pays off — independent reducing sub-joins, star shapes, parallel and distributed execution — and how thresholds interact with shape choice.

for a principal

Treat shape restriction as a planning-budget policy: decide how much of the bushy space is worth buying for which workloads, and whether wide analytic queries belong in this engine at all.

## The shapes A join plan is a binary tree: leaves are base-table accesses, internal nodes are join operators. **Left-deep:** each join's *right* input is a base table; the left input is the result of the join below. `(((A⋈B)⋈C)⋈D)`. This is a straight chain — a pipeline. **Right-deep:** the mirror — each join's *left* input is a base table, and results accumulate down the right spine. `(A⋈(B⋈(C⋈D)))`. **Bushy:** both inputs of at least one join are themselves join results. `(A⋈B)⋈(C⋈D)`. Every left-deep and right-deep tree is a special case of the general (bushy) space. ## Why the restriction exists: search space A left-deep tree is completely determined by a permutation of the base relations, so there are `n!` of them. The full space of shapes multiplies permutations by the Catalan number of tree shapes, giving `(2n-2)!/(n-1)!`. | tables | left-deep (n!) | all shapes | |---|---|---| | 4 | 24 | 120 | | 6 | 720 | 30,240 | | 8 | 40,320 | 17,297,280 | | 10 | 3,628,800 | ~17.6 billion | That gap is the whole reason the restriction was worth making in 1979 hardware terms, and it still matters: it is the difference between dynamic programming that finishes and dynamic programming that does not. ## Why the restriction is also *good* execution-wise With a left-deep tree and index nested-loop joins, execution is a clean pipeline: fetch a row from the outer stream, probe the inner table's index, emit, repeat. Nothing large is materialized; the first row can be produced almost immediately, which is exactly what a `LIMIT`-shaped OLTP query wants. Memory demand is modest and roughly constant in the number of joins. Right-deep trees suit *hash* joins in a different way: you can build hash tables on all the base tables first, then stream the single large fact table once through all of them. That is a common shape for star queries on large memory machines. ## Where bushy plans genuinely win 1. **Two independent reducing sub-joins.** If A⋈B collapses to 100 rows and C⋈D collapses to 200 rows, joining those two small results is far cheaper than dragging one of the large tables through a chain. In a left-deep tree, one of those pairs cannot be formed as a unit at all. 2. **Parallelism.** The subtrees of a bushy plan are independent and can execute concurrently on different workers; a left-deep chain is inherently sequential in its dependency structure (though each operator can still be parallelized internally). 3. **Star and snowflake shapes.** Joining several dimension-side sub-results and then combining them tends to produce bushy plans naturally. 4. **Distributed/shared-nothing engines**, where minimizing data movement often favours combining two locally reduced fragments. ## Practical consequences - Modern optimizers generally search bushy plans but keep the space in check with cross-product pruning, cost pruning, and the join-count threshold beyond which heuristics take over. - Because the left-deep space is so much smaller, some engines search bushy shapes only for small join counts and degrade to left-deep or greedy for larger ones. - When you see an engine produce a chain plan where a bushy one is obviously better, the causes are usually (a) the shape restriction, (b) a join-count threshold that flattened the search, or (c) cardinality estimates that made the reducing sub-join look non-reducing. ## How to talk about it The crisp framing is: **left-deep is a search-space and pipelining optimization; bushy is an expressiveness and parallelism win.** Neither dominates. The optimizer's job is to buy as much of the bushy space as its planning budget allows.

  • When is a right-deep tree preferable?
    With hash joins on a star-shaped query and enough memory: build hash tables on all the small dimension tables up front, then stream the single large fact table through them once. That reads the big table only once and parallelizes the build phase, whereas a left-deep chain would re-probe repeatedly.
  • If bushy plans are strictly more expressive, why not always search them?
    Because the search space is orders of magnitude larger — about 17 million versus 40,320 shapes at eight tables — and optimization time is itself part of query latency. Engines buy as much of the bushy space as their planning budget allows, then fall back to restricted shapes or heuristics for wide joins.
  • Can a bushy plan ever be worse than the best left-deep one?
    The best bushy plan is never worse than the best left-deep plan under the same cost model, since left-deep is a subset of the bushy space. In practice a bushy plan can still lose because finding it costs more planning time, and because a wrong bushy choice built on bad estimates can materialize a large intermediate that a pipelined chain would have avoided.

Left-deep is an assembly line where each station adds one part; bushy is building two subassemblies in parallel and bolting them together at the end.

saying these in an interview costs you the question

  • Thinking left-deep means 'joins in the order written in the FROM clause'
  • Claiming bushy plans are always faster
  • Saying the search space is the same size for both shapes
  • Confusing tree shape with join algorithm (nested loop / hash / merge) — they are independent choices
  • Assuming left-deep prevents parallelism entirely rather than limiting inter-operator independence

context

resolving links…