Join algorithms
Joins are often the most expensive part of a query. Databases implement them with several algorithms suited to different sizes, indexes, and orderings.
Nested-loop join
The simplest join takes each row of the outer table and scans the inner table for matches. With tables of sizes M and N, that is M x N comparisons, fine if both are small but disastrous if both are large. Block nested-loop joins compare whole pages at a time, reducing the number of times the inner table is read.
Index nested-loop join
If the inner table has an index on the join column, each outer row can look up its matches directly, costing about M x (index lookup cost). This is excellent when the outer side is small after filtering, such as joining 50 selected orders to customers by primary key: 50 quick lookups instead of scanning the customer table.
Hash join
A hash join builds an in-memory hash table on the smaller input's join key (build phase), then scans the larger input and probes the hash table for each row (probe phase). It costs roughly M + N and is usually the best choice for large equality joins without useful indexes. If the build side does not fit in memory, both inputs are partitioned by hash to disk and joined partition by partition (Grace hash join).
Sort-merge join
A sort-merge join sorts both inputs on the join key, then merges them in one pass, advancing whichever side has the smaller key, much like merging sorted lists. Sorting costs O(n log n), but if inputs are already sorted, for example by an index or an earlier operator, the merge is linear. It handles range-based join conditions and produces sorted output useful for ORDER BY.
Choosing a join algorithm
Index nested-loop suits a small outer input and an indexed inner table. Hash join suits large, unsorted inputs joined by equality. Sort-merge suits inputs already sorted on the key, inequality joins, or when sorted output is needed. Plain nested loops remain useful for tiny inputs and for arbitrary join conditions that no other algorithm handles.
Semi-joins and anti-joins
Queries with EXISTS or IN become semi-joins, which return each outer row at most once if it has any match, stopping the search early. NOT EXISTS becomes an anti-join, returning outer rows with no match. Optimisers rewrite many subqueries into these join forms, which can use hash or merge algorithms rather than running the subquery once per row.
Joins in distributed systems
When tables are spread across machines, joins may need data movement. A broadcast join sends a small table to every machine holding parts of a large one. A shuffle join repartitions both tables by join key so matching rows meet on the same machine. Network transfer often dominates the cost, so systems try to place related data together.
Worked example
Join orders (10,000,000 rows) with customers (100,000 rows) on customer_id, with no filter. Nested loops: up to 10^12 comparisons. Hash join: build a hash table on the 100,000 customers, then probe once for each of the 10,000,000 orders, about 10.1 million operations. If a query instead filters to 20 orders first, an index nested-loop join doing 20 primary-key lookups on customers is best.
Key takeaways
Nested-loop joins compare every pair, M x N, and suit tiny inputs or arbitrary conditions; block versions read pages at a time. Index nested-loop joins look up matches through an index, ideal for small outer inputs. Hash joins build on the smaller input and probe with the larger, costing about M + N, spilling partitions to disk when needed. Sort-merge joins merge sorted inputs and handle ranges and ordered output. EXISTS and NOT EXISTS become semi-joins and anti-joins. Distributed joins broadcast small tables or shuffle both sides by key.
Flashcard
Compare every outer row with every inner row
Check your understanding
Two large, unsorted tables with no useful indexes are joined on equal customer IDs. Which algorithm is usually best?