Equivalence Rules

If there's one optimization that has the potential to transform hours-long queries into millisecond responses, it's join ordering—and join ordering is made possible by associativity.

Associativity tells us that (A ⋈ B) ⋈ C is equivalent to A ⋈ (B ⋈ C). Mathematically obvious, but the performance implications are staggering. The choice of which tables to join first can determine whether intermediate results are thousands of rows or billions. The wrong order can crash servers; the right order makes queries fly.

This page explores join associativity in depth: why it holds, how it interacts with join conditions, and most importantly, how optimizers exploit it to find efficient execution plans.

Formal Statement

For natural join:

(R ⋈ S) ⋈ T ≡ R ⋈ (S ⋈ T)

For theta join (with appropriate condition handling):

(R ⋈_{θ₁} S) ⋈_{θ₂} T ≡ R ⋈_{θ₁∧θ₃} (S ⋈_{θ₂} T)

where θ₃ captures conditions between R and T that were implicit.

Why Does This Hold?

Intuitively, the result of joining R, S, and T contains tuples where:

• R's portion matches S's portion on their join attributes, AND
• S's portion matches T's portion on their join attributes, AND
• (if applicable) R's portion matches T's portion on their join attributes

The order in which we perform these pairwise joins doesn't affect which complete (R, S, T) combinations satisfy all conditions.

Proof Sketch:

1. Define the result of R ⋈ S ⋈ T as the set of all (r, s, t) tuples where r∈R, s∈S, t∈T and the relevant join conditions hold.

2. Whether we compute (R ⋈ S) first and then join with T, or compute (S ⋈ T) first and then join with R, we're selecting the same set of (r, s, t) combinations.

3. The intermediate groupings differ, but the final set is identical.

Example: The Power of Reordering

Consider three tables:

• Orders: 10M rows
• Customers: 100K rows
• Products: 1K rows

Query: Find orders with their customer and product details.

Plan 1: (Orders ⋈ Customers) ⋈ Products

• Orders ⋈ Customers: potentially 10M result rows (all orders have customers)
• Result ⋈ Products: 10M × (1K selectivity) depending on join

Plan 2: (Customers ⋈ Orders) ⋈ Products (same as Plan 1, just commuted)

Plan 3: Orders ⋈ (Customers ⋈ Products)

• Customers ⋈ Products: 100K × 1K = unrestricted cross product? Only if no join condition!
• If there IS a condition between Customers and Products, this might work.

The right plan depends on selectivities and join conditions. Associativity gives us the freedom to explore all options.

When joining n tables, associativity generates different join tree shapes. Understanding these shapes is fundamental to join ordering optimization.

Left-Deep Trees

A left-deep tree always joins the next table to the "left" result:

((R₁ ⋈ R₂) ⋈ R₃) ⋈ R₄

        ⋈
       / \
      ⋈   R₄
     / \
    ⋈   R₃
   / \
  R₁  R₂

Characteristics:

• Linear chain structure
• Left child is always the growing intermediate result
• Right children are base tables
• Well-suited for pipelined execution

Right-Deep Trees

Mirror of left-deep:

R₁ ⋈ (R₂ ⋈ (R₃ ⋈ R₄))

      ⋈
     / \
    R₁  ⋈
       / \
      R₂  ⋈
         / \
        R₃  R₄

Characteristics:

• Right child is the growing intermediate
• Less common in practice due to execution model mismatch

Bushy Trees

Balanced or irregular trees with internal joins on both branches:

(R₁ ⋈ R₂) ⋈ (R₃ ⋈ R₄)

       ⋈
      / \
     ⋈   ⋈
    / \ / \
   R₁ R₂ R₃ R₄

Characteristics:

• More complex structure
• Can exploit parallelism (join R₁⋈R₂ and R₃⋈R₄ independently)
• Larger search space
• Sometimes optimal for specific query patterns

A useful way to visualize join structure is the join graph.

Definition

The join graph has:

• Nodes: Each relation in the query
• Edges: Between relations that have a join condition

Example:

SELECT * FROM A, B, C, D
WHERE A.x = B.x 
  AND B.y = C.y
  AND C.z = D.z;

Join graph:

A --- B --- C --- D
  (x)   (y)   (z)

This is a chain (linear graph). Each table joins only with its neighbors.

Graph Shapes

Chain: Linear sequence of joins

A - B - C - D

Optimization: n! orderings, well-understood.

Star: One central table joins with all others

    B
    |
 A--C--D   (C is the center)
    |
    E

Optimization: Central table often appears early in join order.

Clique: Every table joins with every other (fully connected)

  A---B
  |\ /|
  | X |
  |/ \|
  C---D

Optimization: Maximum flexibility, complex optimization.

Acyclic (tree): No cycles in the join graph

    A
   / \
  B   C
     / \
    D   E

Optimization: Special algorithms exist (Yannakakis, etc.).

Cross Products and Missing Edges

If two tables have no edge (no join condition between them), joining them produces a Cartesian product—typically disastrous for performance.

Example:

SELECT * FROM A, B, C
WHERE A.x = C.x;  -- No condition between A and B or B and C!

Join graph:

A --- C    B (isolated)

Any join involving B before linking through C produces a cross product. Good optimizers:

1. Detect disconnected components
2. Warn about Cartesian products
3. Try to find implicit conditions
4. Order joins to delay cross products until last

When reordering joins, the optimizer must correctly track and apply join predicates.

Predicate Classification

For a query with predicates P:

1. Local predicates: Reference only one table (selection pushdown handles these)
2. Join predicates: Reference exactly two tables (these drive the join graph)
3. Multi-table predicates: Reference 3+ tables (complex; require special handling)

Predicate Migration During Reordering

When we transform (R ⋈_{p1} S) ⋈_{p2} T to R ⋈_{p1'} (S ⋈_{p2'} T), predicates may migrate:

Before:

• p1 applied at R⋈S join
• p2 applied at (R⋈S)⋈T join

After:

• If p2 only involves S and T: p2 can apply at S⋈T
• If p2 involves R and T: must wait until final join (becomes p1')
• p1 still applies between R and the result of S⋈T

The Transitive Closure

Optimizers often compute the transitive closure of equality predicates:

WHERE R.a = S.a AND S.a = T.a
-- Implies: R.a = T.a (transitive)

Adding the implied R.a = T.a edge to the join graph creates more reordering options. This is called predicate inference and is a key optimization technique.

Cartesian Tolerance

Some orderings require temporary Cartesian products:

Join graph: R -- S    T -- U
            (no direct path from left to right)

To join all four, we must either:
1. Create a cross product between {R,S} and {T,U}
2. Or find implicit conditions

Optimizers delay Cartesian products as long as possible, but sometimes they're unavoidable. Associativity still applies; we choose the least costly position for the cross product.

Join ordering is computationally challenging. Let's quantify the problem.

Number of Join Orders

Left-deep trees only:

• n! possible orderings
• n=5: 120 plans
• n=10: 3,628,800 plans
• n=15: ~1.3 trillion plans

Including bushy trees:

• (2n-2)! / (n-1)! possible tree structures
• Much larger than n!

With algorithm selection:

• Multiply by choices per join (e.g., 3 algorithms)
• Multiply again by commutation choices

Dynamic Programming Approach

For small n (typically ≤ 10-15), optimizers use dynamic programming:

1. Enumerate all subsets of tables
2. For each subset, compute optimal join plan
3. Build larger subsets from smaller optimal sub-plans
4. Space complexity: O(2ⁿ)
5. Time complexity: O(3ⁿ) for left-deep, O(4ⁿ) for all shapes

This is the System R algorithm (IBM, 1979), still the foundation of most optimizers.

Heuristic Approaches for Large Queries

When n exceeds ~10-15, exact optimization is impractical. Alternatives:

1. Greedy / Heuristic Algorithms

• Start with smallest table
• Repeatedly join with next best partner
• Fast but potentially suboptimal

2. Genetic Algorithms

• Evolve population of join orders
• Use crossover and mutation
• Find good (not necessarily optimal) solutions

3. Simulated Annealing

• Random walk with cooling schedule
• Accepts worse solutions initially to escape local minima

4. Query Decomposition

• Break query into independently optimizable parts
• Especially for star schemas

5. User Hints

• Allow DBA to specify join order
• /*+ LEADING(a, b, c) */ in Oracle

Unlike inner joins, outer joins have severely limited associativity. This restricts join reordering for queries with outer joins.

Left Outer Join Associativity

Does NOT hold in general:

(R ⟕ S) ⟕ T ≢ R ⟕ (S ⟕ T)

Example showing non-equivalence:

R = {1}
S = {2}
T = {1}

R ⟕ S = {(1, NULL)}  -- 1 in R has no match in S
(R ⟕ S) ⟕ T = {(1, NULL, 1)}  -- matches T on R's attribute

S ⟕ T = {(2, NULL)}  -- 2 in S has no match in T
R ⟕ (S ⟕ T) = {(1, NULL, NULL)}  -- different result!

Valid Outer Join Transformations

Some specific transformations ARE valid:

1. Inner join associates with outer join (sometimes):

(R ⟕ S) ⋈ T ≡ (R ⋈ T) ⟕ S  [if T only joins with R]

2. Outer join converts to inner when possible:

If a WHERE condition rejects NULL values from the outer join:
R ⟕ S WHERE S.a IS NOT NULL ≡ R ⋈ S

This enables normal associativity.

3. Full outer joins with inner:

(R ⟗ S) ⋈ T has limited transformations

Modern query optimizers have evolved sophisticated techniques for join ordering.

Adaptive Query Processing

Rather than committing to a join order before execution, some systems adapt at runtime:

1. Adaptive Join Ordering

• Start with estimated best order
• Monitor actual cardinalities during execution
• Reorder mid-query if estimates were wrong

2. Eddies (Research)

• Route each tuple independently through operators
• Automatically adapts to skewed data
• High overhead but robust to estimation errors

Cardinality Feedback

First execution: Use estimates
Measure actual cardinalities
Second execution: Use measured values for better ordering

SQL Server, PostgreSQL 14+, and Oracle implement forms of this.

Machine Learning for Join Ordering

Recent research applies ML:

1. Learned Cardinality Estimation — Train models on workload queries to predict cardinalities better than histograms
2. Reinforcement Learning for Join Ordering — Learn which orderings work well for similar queries
3. Workload-Aware Optimization — Pre-compute good plans for common query patterns

Practical Implementation: PostgreSQL's GEQO

PostgreSQL uses the Genetic Query Optimizer (GEQO) for queries with 12+ tables:

1. Represent join orders as chromosomes
2. Generate initial random population
3. Evaluate fitness (estimated cost)
4. Crossover: combine good orderings
5. Mutation: random swaps
6. Repeat for N generations
7. Return best ordering found

Configuration: geqo_threshold controls when GEQO kicks in (default: 12 tables).

Join associativity enables the most impactful query transformation: choosing the order in which tables are joined. Let's consolidate the key insights:

Module Complete

With this page, we conclude the Equivalence Rules module. You've learned how relational algebra equivalences—commutativity, associativity, distributivity—empower query optimizers to transform queries into efficient execution plans. Selection pushdown, projection pushdown, join commutativity, and join associativity are the core transformations that make declarative SQL viable for high-performance databases.

These principles remain constant across database systems, from PostgreSQL to Oracle, from MySQL to distributed systems like Snowflake. Master them, and you understand the heart of query optimization.