SQL-Engineering-Handbook

Join Optimization

Module 16 · Query Optimization Home · Engineering Guide · Cheatsheet · Decision Trees

Lesson 04 of 12 · ← SARGability · Next: Subqueries → · SQL Lab

Introduction

You already know how to write a JOIN. This lesson covers what the optimizer does with it — which of three join algorithms it picks, why, and when you can influence that choice.

Learning Objectives

Why This Exists

JOIN syntax is one line of SQL, but the optimizer’s choice of how to execute it can be the single biggest factor in a query’s runtime — the same join written the same way can run a hundred times faster or slower purely based on table sizes and indexes, with no SQL changes at all.

Business Motivation

An e-commerce reporting query joins orders (200M rows) against a small promotions lookup table (40 rows) to tag which orders used a promo code. The optimizer’s choice here — probably a hash join or even a broadcast-style join of the tiny table — is completely different from joining two similarly-huge tables, where a merge or hash join on indexed/sorted keys dominates. Understanding why the optimizer picks differently for these two shapes is what separates “I can write a JOIN” from “I understand joins.”

The Three Join Algorithms

Nested Loop vs Hash vs Merge

Nested Loop Join

for each row in outer_table:
    for each matching row in inner_table (often via an index):
        emit joined row

Efficient when the outer table is small and the inner table has a usable index on the join column — the classic case of joining a small departments table against a large employes table filtered down to a small subset. Becomes very expensive if the outer table is large and there’s no index to speed up the inner lookup, since it degrades toward comparing every row against every row.

Hash Join

1. Build a hash table from the smaller input, keyed on the join column
2. Probe the hash table with each row of the larger input

The default choice for joining two large tables with no useful index on the join column — no ordering or index required, and it scales well as long as the smaller (build) side fits comfortably in memory.

Merge Join

1. Ensure both inputs are sorted on the join column (via index or explicit sort)
2. Walk both sorted inputs together, like merging two sorted lists

Very efficient when both inputs are already sorted on the join column — typically because both have an index on it — since it avoids building any in-memory structure. Expensive if the engine has to sort one or both sides first just to enable the merge.

How the Optimizer Chooses

flowchart TD
    A[Join Required] --> B{Outer table small<br/>+ index on inner join column?}
    B -->|Yes| C[Nested Loop Join]
    B -->|No| D{Both inputs large<br/>+ no useful index?}
    D -->|Yes| E[Hash Join]
    D -->|No| F{Both inputs sorted<br/>on join column?}
    F -->|Yes| G[Merge Join]
    F -->|No| H[Optimizer cost model<br/>chooses cheapest]
    H --> C
    H --> E
    H --> G

The optimizer estimates the cost of each algorithm for the specific tables, sizes, and available indexes involved, and picks the lowest estimated cost. This is why the same JOIN syntax in your query can compile to different physical algorithms depending on: table sizes, whether either join column is indexed, and current statistics.

Predicate Pushdown (recap in a join context)

Predicate Pushdown

SELECT e.emp_name, d.dept_name
FROM employes e
JOIN departments d ON e.dept_id = d.dept_id
WHERE d.location_id = 3;

The optimizer typically filters departments down to location_id = 3 before performing the join — pushing the WHERE predicate down past the join boundary — rather than joining everything first and filtering after. This dramatically shrinks the join’s build/probe side.

Join Elimination

If a query joins a table but never actually references any of its columns in SELECT, WHERE, or elsewhere, and a foreign key guarantees the join can’t change the row count or filter anything, a sufficiently smart optimizer can eliminate the join entirely. This mostly benefits auto-generated ORM SQL that joins defensively; it’s worth knowing this exists so you don’t manually “optimize away” a join the optimizer would have removed anyway.

Engineering Notes

MySQL / PostgreSQL / SQL Server Notes

Common Mistakes

Anti-patterns

Interview Questions

Edge Cases

Troubleshooting Guidance

Scalability Considerations

In distributed/MPP engines (Redshift, Snowflake, BigQuery), join cost includes a data shuffle step to co-locate matching rows across nodes — a dimension that doesn’t exist in single-node engines. Joining on a poorly-distributed key can dominate query time even when the same join would be trivial on a single-node database.

Additional Dialect Notes

Summary

The optimizer picks a join algorithm based on table sizes, available indexes, and estimated cost — not based on how you wrote the SQL. Your job is to give it good indexes and accurate statistics; its job is to pick nested loop, hash, or merge accordingly.

Practice Challenges

  1. For a join between a 50-row locations table and a 40-million-row employes-derived table, predict the likely join algorithm and explain why.
  2. Find a query in Module 03 that joins three tables and predict, before running EXPLAIN, which join is likely to be the most expensive.

Real Company Usage

Production Applications

These scenarios are illustrative case studies inspired by common production failure modes; specific figures are illustrative unless an external source is cited in PRODUCTION_INCIDENTS.md. See its disclaimer for the full explanation.

Performance Notes

Optimization Notes

Interview Insight

“Which join algorithm would you expect here?” is a classic systems-design question. Interviewers give table sizes and index availability, then expect you to predict nested loop (small outer + indexed inner), hash join (two large unindexed tables), or merge join (both sides pre-sorted). Mentioning hash join spill-to-disk and predicate pushdown separates senior candidates from those who only know the three names.

Further Experiments

  1. Join departments (small) to employes (large) with and without an index on employes.dept_id — compare nested loop vs. hash join in EXPLAIN ANALYZE.
  2. Create a multi-table query joining three tables and predict join order before running EXPLAIN — check whether the optimizer’s order matches your prediction.
  3. Add a restrictive WHERE clause and observe whether the optimizer pushes it below the join node (predicate pushdown) in the plan tree.

Continue Learning

03_SARGability · 05_Subquery Optimization · 03_Joins

Further Reading

This site is open source. Improve this page.