Equivalence Rules

At first glance, join commutativity seems trivially obvious: A ⋈ B = B ⋈ A. Of course, the result is the same regardless of which table we list first. But this mathematical equivalence has profound implications for query execution.

The order in which relations appear in a join doesn't just affect notation—it affects how the join is physically executed. In a nested-loop join, the left operand becomes the outer loop and the right operand becomes the inner loop. In a hash join, typically one side builds the hash table and the other probes it. These implementation choices have dramatically different performance characteristics depending on relation sizes, available memory, and index structures.

Join commutativity gives the optimizer freedom to choose the optimal physical arrangement for each join, transforming a potentially slow execution into a fast one without changing the query's meaning.

Formal Statement

For natural join:

R ⋈ S ≡ S ⋈ R

For theta join:

R ⋈_θ S ≡ S ⋈_θ R  (where θ is symmetric or appropriately transformed)

For equi-join:

R ⋈_{R.a=S.b} S ≡ S ⋈_{S.b=R.a} R

Why Does This Hold?

The join operation is defined as selecting tuples from the Cartesian product that satisfy the join condition. Since the Cartesian product itself is commutative (R × S contains the same pairs as S × R, just in different order), and the join condition is applied symmetrically, the result set must be identical.

What About Attribute Order?

Strictly speaking, R ⋈ S and S ⋈ R might have attributes in different orders. In practice:

1. SQL's result column order follows SELECT list, not FROM order
2. Optimizers can add projections to reorder attributes
3. For semantic equivalence, we care about the set of result tuples, not their physical ordering

This means commutativity holds for all practical purposes in query optimization.

The value of commutativity becomes clear when we examine how different join algorithms work.

Nested Loop Join

In a nested loop join:

for each tuple r in R (outer):
    for each tuple s in S (inner):
        if r and s satisfy join condition:
            output (r, s)

The asymmetry: The outer relation R is scanned once. The inner relation S is scanned once for each tuple of R.

• If R has 100 tuples and S has 10,000 tuples: S is scanned 100 times
• If we swap: R is scanned 10,000 times

Optimal choice: Make the smaller relation the outer, or exploit indexes on the inner relation.

Hash Join

In a hash join:

// Build phase
for each tuple r in R (build side):
    insert r into hash table keyed on join attributes

// Probe phase  
for each tuple s in S (probe side):
    look up matching tuples in hash table
    output joined tuples

The asymmetry: The build side constructs an in-memory hash table. If the build side is too large, the table may spill to disk, causing massive slowdown.

Optimal choice: Make the smaller relation the build side. The hash table should fit in memory.

Sort-Merge Join

Sort-merge join is more symmetric:

sort R on join attributes
sort S on join attributes
merge: scan both sorted relations, matching equal keys

Both relations are scanned once during the merge phase. However, sorting costs depend on relation sizes, and if one relation is already sorted (e.g., from an index), commuting might avoid a redundant sort.

Index Nested Loop Join

When an index exists on the join column:

for each tuple r in R (outer):
    use index on S to find matching tuples (inner)

The strong asymmetry: The indexed relation should be the inner. If you swap, you lose the index benefit.

Optimal choice: Non-indexed relation as outer, indexed relation as inner. Commutativity enables this arrangement regardless of how the query was written.

The optimizer uses cost models to decide which commutation is beneficial. Let's examine the cost formulas.

Nested Loop Join Costs

Basic nested loop (no blocking, no index):

Cost(R ⋈ S) = |R| + |R| × |S|  (tuple-at-a-time)
            = P_R + |R| × P_S  (page-at-a-time, worst case)

Where P_R, P_S are page counts. Clearly, having the smaller relation as outer is better.

Block nested loop (using B memory pages for outer):

Cost = P_R + ⌈P_R / (B-2)⌉ × P_S

Fewer outer pages means fewer scans of the inner.

Index nested loop (index on inner's join column):

Cost = P_R + |R| × (index lookup cost + tuple fetch cost)

Index lookup is ~3–4 I/Os for B-tree. If the outer is after selection pushdown (fewer tuples), cost is very low.

Hash Join Costs

Cost = 3 × (P_R + P_S)  (for partitioned hash join)

Symmetric in pages, but:

• Memory pressure from build side hash table
• If build side fits in memory: Cost = P_R + P_S
• If build side exceeds memory: multiple passes needed

Optimal: Build on the smaller relation to maximize chance of in-memory build.

When a query joins three or more tables, commutativity at each join step compounds with associativity to create a large search space of equivalent plans.

Example: Three-Way Join

For query: R ⋈ S ⋈ T

Consider just binary join orderings:

1. (R ⋈ S) ⋈ T with R outer for first join
2. (R ⋈ S) ⋈ T with S outer for first join
3. (S ⋈ R) ⋈ T with S outer for first join (same as 2 after commuting)
4. R ⋈ (S ⋈ T) with R outer for second join ... and so on

Each intermediate join can have its operands commuted. The optimizer explores combinations to find the overall best plan.

The Explosion

For n tables:

• Number of join orders (tree shapes): Catalan number C_{n-1}
• Number of commutations per join: 2
• Total plans: O(4^n / n^{1.5}) without algorithm selection

Optimizers use dynamic programming (for small n) or heuristics (for large n) to search this space efficiently.

Why Commutativity Matters Even More in Multi-Way Joins

In multi-way joins, an early poor commutation decision propagates:

• If the first join produces a huge intermediate result (wrong operand order), subsequent joins process more data
• Conversely, optimal commutation at each stage keeps intermediate results small

The optimizer evaluates costs for promising combinations, applying commutativity where it helps reduce intermediate result sizes or enables index usage.

Commutativity has limitations for certain join variants. Understanding these limitations is crucial for correct optimization.

Outer Join Non-Commutativity

LEFT OUTER JOIN (⟕)

R ⟕ S ≢ S ⟕ R

Why? LEFT JOIN preserves all rows from R, padding with NULLs when no match exists in S. Swapping changes which table is preserved.

Example:

R = {1, 2, 3}
S = {2, 3, 4}

R ⟕ S = {(1, NULL), (2, 2), (3, 3)}
S ⟕ R = {(2, 2), (3, 3), (4, NULL)}  -- DIFFERENT!

Implication: The optimizer cannot commute outer joins freely. The SQL author's intent (which side to preserve) must be honored.

RIGHT OUTER JOIN

Similarly non-commutative:

R ⟖ S ≢ S ⟖ R

However, there's a useful transformation:

R ⟕ S ≡ S ⟖ R  (converting between LEFT and RIGHT)

This isn't commutativity but a different equivalence that can help normalize plans.

FULL OUTER JOIN

R ⟗ S ≡ S ⟗ R  (IS commutative)

Full outer join preserves unmatched rows from both sides, so it doesn't matter which is listed first.

Semi-Joins and Anti-Joins

Semi-join (⋉): Returns tuples from R that have at least one match in S. No S columns appear in output.

R ⋉ S ≢ S ⋉ R (NOT commutative in result schema)

However, for EXISTS subqueries:

SELECT * FROM R WHERE EXISTS (SELECT 1 FROM S WHERE R.a = S.a)

The semi-join implementation can choose which table to scan first, as long as the output is correctly R's tuples.

Anti-join (▷): Returns tuples from R with no match in S (NOT EXISTS pattern).

R ▷ S ≢ S ▷ R (NOT commutative)

Anti-joins have even more restricted transformation options.

When commuting a theta join, the join condition may need to be transformed to remain semantically correct.

Symmetric Conditions

Equality conditions are naturally symmetric:

R.a = S.b ⟺ S.b = R.a

The optimizer can commute freely.

Asymmetric Conditions

Inequality conditions must be inverted:

R.a < S.b when commuted becomes S.b > R.a

Transformation table:

Complex Conditions

Conjunctions and disjunctions transform component-wise:

(R.a = S.b) AND (R.c > S.d) 
⟺ (S.b = R.a) AND (S.d < R.c)

The optimizer applies these transformations automatically when considering commutation.

Cross Joins Require Special Care

A cross join (Cartesian product) has no join condition:

R × S ≡ S × R

Completely commutative, but:

• Should rarely appear in well-written queries
• Often indicates a missing WHERE clause
• Optimizer may try to find implied join conditions from WHERE to convert to a proper join

When a cross join is intentional (generating combinations), commutation chooses optimal scan order.

Let's examine how commutativity affects real query plans.

Example 2: Index Nested Loop

SELECT e.name, d.dept_name
FROM Departments d    -- 100 rows, no index on id
JOIN Employees e ON e.dept_id = d.id;  -- 100K rows, index on dept_id

Optimal plan:

• Departments as outer (100 iterations)
• For each department, use index on Employees.dept_id
• ~100 index lookups vs. 100K full scans

The optimizer commutes to put Departments as the driving (outer) table.

Join commutativity gives the optimizer essential flexibility in choosing how to execute joins physically. Let's consolidate the key insights:

What's Next

We've covered how to swap operands within a single join. Next, we'll explore join associativity—the ability to regroup joins in multi-table queries. This is the foundation of join ordering optimization, one of the most impactful aspects of query optimization.