Exponential Possibilities

Here's a question that seems simple but has profound implications: How many different ways can you order 10 table joins?

If your intuition says '10 factorial' or about 3.6 million, you're underestimating by several orders of magnitude. The actual number of distinct join orderings for 10 tables exceeds 17.6 trillion—more than 4 million times larger than a simple permutation count.

This exponential explosion lies at the heart of query optimization complexity. It explains why optimizers can't simply try all possibilities, why heuristics are essential, and why even sophisticated search algorithms must make difficult tradeoffs. Understanding this combinatorial landscape is crucial for anyone who wants to comprehend how database systems approach the join ordering problem.

To understand why join orderings are so numerous, we first need to recognize what we're actually counting. A join ordering isn't just a sequence of tables—it's a binary tree structure where:

• Each leaf node is a base table
• Each internal node represents a join operation
• The tree structure defines the order of join execution (bottom-up)

This tree perspective is essential because joins are binary operations—each join takes exactly two inputs. When joining 4 tables (A, B, C, D), we don't simply specify 'join A, then B, then C, then D.' We specify a particular tree structure, such as:

       ⋈           or          ⋈
      / \                      / 
     ⋈   D                    ⋈   ⋈
    / \                      / \ / 
   ⋈   C                    A  B C  D
  / 
 A   B

These two structures represent fundamentally different join plans—the left is a left-deep tree, while the right is a bushy tree.

The components of join ordering:

When counting distinct join orderings for n tables, we must account for:

1. Tree topology — The shape of the binary tree (how operations are grouped)
2. Leaf assignment — Which table goes where in the tree
3. Join commutativity — Left and right inputs to each join can be swapped

Each of these multiplies the search space. Let's examine them in detail.

The number of distinct binary tree topologies with n leaves is given by the (n-1)th Catalan number, denoted C_{n-1}:

C_n = (2n)! / ((n+1)! × n!)

Alternatively, using the binomial coefficient:

C_n = C(2n, n) / (n + 1)

The Catalan numbers grow rapidly but are themselves just one component of the total ordering count.

Asymptotic behavior:

The Catalan numbers grow roughly as:

C_n ∼ 4^n / (n^{3/2} × √π)

This means tree topologies alone contribute exponential growth of approximately 4^n. But we're not done—we still need to assign tables to leaves.

Now let's assemble the complete formula. For n tables:

Total orderings = Tree topologies × Leaf assignments × Commutativity options

• Tree topologies: C_{n-1} (Catalan number)
• Leaf assignments: n! (permutation of tables across leaves)
• Commutativity: 2^{n-1} (each of n-1 joins can swap inputs)

Combining these:

Total orderings = C_{n-1} × n! × 2^{n-1}
                = C_{n-1} × n! × 2^{n-1}

Using the Catalan formula:

= [(2n-2)! / (n! × (n-1)!)] × n! × 2^{n-1}
= (2n-2)! × 2^{n-1} / (n-1)!

This simplifies to the product of all odd numbers from 1 to 2n-3, multiplied by n!, which grows extremely fast.

Practical interpretation:

With modern hardware evaluating roughly 1 million orderings per second:

• 5 tables: Exhaustive search completes in ~1.7 milliseconds ✓
• 8 tables: Exhaustive search takes ~17 seconds — borderline acceptable
• 10 tables: Exhaustive search takes ~5 hours — unacceptable
• 12 tables: Exhaustive search would take months — impossible

Since analytical queries commonly join 10-20+ tables, exhaustive enumeration is fundamentally infeasible for real-world workloads.

One of the most important techniques for taming the combinatorial explosion is restricting the search space to specific tree shapes. The most common restriction is to consider only left-deep trees.

Why restrict to left-deep?

The reduction from O((2n-2)!/((n-1)!)) to O(n!) is dramatic—often several orders of magnitude for queries joining 8+ tables. But is this restriction safe? What do we lose?

Advantages of left-deep restriction:

1. Pipelining — Left-deep plans enable streaming execution; intermediate results flow directly to the next join without materialization
2. Memory efficiency — Only one intermediate result exists at a time; no need to hold multiple partial results
3. Index nested-loop compatibility — Outer relation always comes from intermediate results, inner from base tables with indexes
4. Implementation simplicity — Easier to generate, compare, and execute

Disadvantages:

1. Lost parallelism — Bushy trees can execute independent subtrees in parallel
2. Potentially suboptimal — The globally optimal plan may be bushy; left-deep restriction may miss it
3. Large intermediate results — Some query shapes naturally favor bushy plans

While left-deep trees are the most common restriction, other tree shapes have specific use cases and trade-offs.

The hash join connection:

Right-deep trees have an interesting property for hash joins. In a hash join:

1. Build phase: Construct hash table from 'build' (inner) relation
2. Probe phase: Stream through 'probe' (outer) relation, matching against hash table

In a right-deep tree with all base tables on the left, all hash tables are built first (on base tables), then a single probe pass streams an intermediate result through the entire cascade. This can be very efficient when:

• Hash tables fit in memory
• Base tables are the smaller relations
• Probe relations (intermediates) are large

However, this requires knowing which tables are small enough to build hash tables—which again depends on accurate cardinality estimates.

Beyond tree shape restrictions, optimizers employ several additional techniques to manage the exponential search space:

Join graph topology effects:

The structure of join predicates critically affects search space size:

• Star schema: One central fact table joined to multiple dimension tables. The central table must be joined early, drastically limiting orderings.
• Chain topology: Tables form a linear chain of joins (A-B-C-D). Only O(n) fundamentally different orderings exist.
• Clique topology: Every table joins with every other table (rare in practice). This is the worst case—full exponential search space.
• Snowflake schema: Multiple chains branching from a center. Search space is polynomial in chain lengths.

Most real-world schemas fall between these extremes, with partial connectivity that significantly constrains the effective search space.

To develop intuition for the scale of the join ordering problem, let's visualize how quickly it explodes.

The pruning imperative:

Given these numbers, effective optimization requires pruning the search space by many orders of magnitude. Consider a 12-table query:

• Total orderings: ~26 trillion
• Evaluations possible in 1 second: ~1 million
• Evaluation needed for coverage: 26 billion seconds (800+ years)

Yet real optimizers handle such queries in under a second. This is only possible through:

1. Dynamic programming — Each subproblem solved once, not re-evaluated per occurrence
2. Aggressive pruning — Most orderings never evaluated; known-worse options discarded early
3. Heuristic filtering — Orderings violating rules of thumb rejected without costing
4. Search limits — Hard caps on enumeration, accepting potentially suboptimal plans

The next pages will explore how optimizers achieve this remarkable efficiency.