Join two tables without comparing every pair

The join lesson described the result we want. Now we need an algorithm to produce it. A physical operator is an implementation of an operation such as scanning, filtering, or joining rows.

Take three orders referring to products 27, 12, and 27. The product table contains IDs 12, 27, and 46. Our equality join returns each order with its matching product name.

Begin with the obvious algorithm

For every order, scan every product and compare the IDs. This nested-loop join examines nine pairs in the simple full-scan version: three orders times three products. It is easy to implement and provides a useful correctness reference.

For larger inputs, we can avoid repeating the same product scan. A hash table groups entries into locations selected by a hash function, a deterministic calculation from a key. Different keys may share a location, so equality must still be checked.

Build once, then probe

Build from products
Store 12 → Notebook, 27 → Canvas tote, and 46 → Desk lamp in the lookup structure.
Probe for order 501
Its product key is 27. Find that key and emit 501 · Canvas tote.
Probe the remaining orders
502 matches 12. 503 matches 27. Emit both matching pairs.

One input supplies retained lookup state. The other input consults that state one row at a time.

This is a hash join. With suitable hashing and enough memory, building and probing can take work roughly proportional to the input sizes, plus the number of result rows. That is not a guarantee for every distribution or hash function.

Our product key is unique, so each order matches at most one product. If the build-side key were not unique, the lookup structure would need to retain every matching row. Returning only the first would change SQL’s result multiplicity, meaning how many copies of a result the query produces.

The memory limit changes the implementation

The build input may exceed the available memory. A larger-than-memory hash join can partition both inputs into temporary files using the same hash rule, then join corresponding partitions. Spilling means moving intermediate work to storage. It adds I/O and still needs handling for an oversized or heavily repeated key.

For a small outer input with an indexed inner key, repeated index lookups may be simpler and cheaper. Algorithms are choices under assumptions, not a ranking from slow to fast.

Count repeated matches

Two orders refer to 27, and two build-side rows share key 27. How many matching pairs must an ordinary inner equality join emit for that key?

Match each row with every qualifying partner

Four: each of the two orders matches both build-side rows. The output size itself requires work. A hash table may locate those rows efficiently, but it cannot eliminate required results without changing the query.

We have chosen an algorithm and identified its retained state. The execution engine must now decide how rows flow between that operator and the rest of the plan.

PostgreSQL’s planner overview describes nested-loop, merge, and hash join choices. The example here isolates a small inner equality join.

Extended reference

The extended chapter preserves the original technical coverage, additional examples, and citations. The explanation above supplies the concepts needed for this page; the reference develops the specialist cases.

Find a section from the original chapter