Join Algorithms

Every time you write SELECT ... FROM orders JOIN customers ON ..., a database engine has to make a decision you never see: which algorithm should it use to combine those two tables?

There are three classic answers — nested-loop join, hash join, and sort-merge join — and each one is the right choice in a different situation. Pick the wrong one and a query that could finish in milliseconds might grind through minutes instead.

The core problem is always the same: given two sets of rows, $R$ and $S$, find every pair $(r, s)$ where $r.key = s.key$. The three algorithms solve it with very different strategies, and the cost gap between them can be enormous.

Drag the sliders to change the table sizes, then hit Race to watch all three algorithms work through the same data and count how many row comparisons each one makes.

<!-- {{c_html_intro}} -->
<div class="controls">
  <label>{{lbl_r}} <span id="rVal">8</span>
    <input type="range" id="rSize" min="2" max="20" value="8">
  </label>
  <label>{{lbl_s}} <span id="sVal">10</span>
    <input type="range" id="sSize" min="2" max="20" value="10">
  </label>
  <button id="runBtn" type="button">{{btn_race}}</button>
</div>
<div class="bars" id="bars">
  <div class="bar-group">
    <div class="bar-label">{{lbl_nested}}</div>
    <div class="bar-wrap"><div class="bar bar-nl" id="barNl"></div></div>
    <div class="bar-count" id="cntNl">–</div>
  </div>
  <div class="bar-group">
    <div class="bar-label">{{lbl_hash}}</div>
    <div class="bar-wrap"><div class="bar bar-hj" id="barHj"></div></div>
    <div class="bar-count" id="cntHj">–</div>
  </div>
  <div class="bar-group">
    <div class="bar-label">{{lbl_sort}}</div>
    <div class="bar-wrap"><div class="bar bar-sm" id="barSm"></div></div>
    <div class="bar-count" id="cntSm">–</div>
  </div>
</div>
<div class="winner" id="winner"></div>
<p class="note" id="note">{{note_initial}}</p>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.controls { display: flex; flex-wrap: wrap; gap: .6rem; align-items: center; margin-bottom: .8rem; }
label { display: flex; flex-direction: column; font-size: .85rem; font-weight: 600; gap: .2rem; }
input[type=range] { width: 120px; accent-color: #1d3557; }
button { font: 600 14px system-ui; padding: .45rem 1rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:hover { background: #163048; }
/* {{c_css_bars}} */
.bars { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .6rem; }
.bar-group { display: grid; grid-template-columns: 100px 1fr 80px; align-items: center; gap: .4rem; }
.bar-label { font-size: .8rem; font-weight: 700; }
.bar-wrap { background: #e8eef3; border-radius: 4px; height: 22px; overflow: hidden; }
.bar { height: 100%; width: 0%; border-radius: 4px; transition: width .6s ease; }
.bar-nl { background: #e63946; }
.bar-hj { background: #2a9d8f; }
.bar-sm { background: #e9c46a; }
.bar-count { font-size: .85rem; font-weight: 700; text-align: right; }
.winner { font-weight: 700; font-size: 1rem; min-height: 1.3em; color: #1d3557; }
.note { font-size: .82rem; color: #555; line-height: 1.45; margin-top: .4rem; }

// Code not found

Notice the pattern: nested-loop scales with $|R| \times |S|$ and dominates when both tables are tiny. Hash join pays a flat build cost then scans once — it wins as soon as the data gets large. Sort-merge earns its place when the data is already sorted or when you need ordered output anyway; otherwise sorting up-front costs extra passes.

Each algorithm has a precise cost model, and the differences matter at scale.

Nested-loop join is the brute force approach: for every row in $R$, scan all of $S$ looking for matches. Cost: $O(|R| \cdot |S|)$ comparisons. With two tables of 10,000 rows that is 100,000,000 probes. With indexes it degrades gracefully to $O(|R| \cdot \log |S|)$, which is why small driving tables with indexed inner relations are the textbook nested-loop sweet spot.

Hash join (invented independently by DeWitt and Shapiro in the 1980s) works in two phases:

1. Build: hash every row of the smaller relation $R$ into an in-memory hash table — cost $O(|R|)$.
2. Probe: for each row of $S$, look up its key — cost $O(|S|)$ expected.

Total: $O(|R| + |S|)$ — linear. The catch is memory: if $R$ doesn't fit in RAM, you need a Grace hash join that partitions both tables to disk first, adding I/O passes.

Sort-merge join sorts both relations on the join key (cost $O(|R| \log |R| + |S| \log |S|)$), then merges them in a single linear pass. Total: $O((|R| + |S|) \log(|R| + |S|))$. It shines when the data arrives pre-sorted (from an index scan or a prior ORDER BY) — in that case the sort cost vanishes and you're left with the pure $O(|R| + |S|)$ merge.

The theoretical lower bound for a general equijoin is $\Omega(|R| + |S| + |output|)$ — you must read every input row at least once. Hash join and sort-merge (given sorted input) both achieve this bound.

The choice of join algorithm is one of the most consequential decisions a query optimizer makes, and the same three ideas appear everywhere data needs to be combined:

• OLTP databases (PostgreSQL, MySQL): the optimizer picks nested-loop for small indexed lookups and hash join for larger unindexed scans. Getting it wrong is a classic cause of "the query was fast, then suddenly slow after the table grew."
• Analytical warehouses (Snowflake, BigQuery, Redshift): columnar storage and massive parallelism favor hash join for large fact-dimension joins; broadcast joins send the smaller table to every worker to avoid shuffling the big one.
• Distributed systems (Spark, Flink): a shuffle hash join repartitions both tables by key across the cluster — the same idea as Grace hash join, but the "disk" is the network. Sort-merge is preferred when input is already range-partitioned.
• Stream processing: joining a fast event stream against a slowly changing table is a windowed nested-loop in disguise — bounded by how much history you can keep in memory.

Understanding these three algorithms also unlocks sorting intuition: sort-merge join is the merge step of merge sort, applied to two streams instead of one. And the hash-table trick behind hash join is the same idea powering hash maps.

Three algorithms, one problem, wildly different costs. Nested-loop is simple and unbeatable on tiny data; hash join is the general-purpose workhorse once rows number in the thousands; sort-merge earns its keep when order is already there or when you can reuse it downstream.

The real lesson is that context determines cost. Table sizes, available memory, existing sort order, the presence of indexes, the need for ordered output — each factor tips the scale. Query optimizers spend enormous effort estimating these quantities precisely because a wrong join choice can turn a sub-second query into a minutes-long scan.

The next time a database query runs unexpectedly slow, check the query plan — the join algorithm choice is often the culprit, and understanding sorting and hash tables gives you the vocabulary to fix it.