A query joins two large tables on the condition that one table's timestamp falls between two columns of the other, and the plan will not use a hash join no matter how the query is written. Explain why a hash join can only implement equality join conditions.
answer
- hash scatters ⇒ ordering destroyed
- bucket answers "exactly this key?" only
- range needs order: sort or B-tree
- mixed predicate: hash the equality, filter the range
- discretize time into buckets to create an equality
basics
~20 sA hash function maps a value to a bucket and destroys ordering and locality: values that are close numerically land in unrelated buckets. So a hash table can answer "which rows have exactly this key?" but never "which rows are less than, or within a range of, this key." Range joins need other algorithms.
solid answer
~60 sHashing is a **one-way scattering** of values into buckets. Two values that are adjacent in sort order — 100 and 101 — are deliberately placed in unrelated buckets, because uniform scattering is what makes hash lookups O(1). The consequence is that a hash table supports exactly one question: *which entries have this exact key?* Answering "less than X" or "between X and Y" would require scanning every bucket, which is just a full scan of the build side per probe row — no better than a nested loop. So a hash join can implement only **equi-join** predicates. For a `BETWEEN`-style range join the engine's real options are: a nested loop (ideally with a range-capable index such as a B-tree or an interval/range index on the inner side), or a merge-style algorithm that exploits sort order on both inputs. A practical middle ground: if the predicate contains *both* an equality and a range component — say equal tenant plus a timestamp range — the engine can hash-join on the equality and apply the range as a **residual filter** on matched pairs, which usually restores acceptable performance.
code
sql · 4 linesSELECT e.id, v.version
FROM events e
JOIN versions v
ON e.occurred_at BETWEEN v.valid_from AND v.valid_to;go deeper
State plainly that hashing scatters values so only exact-match lookups work, and that ranges need sorted structures.
Explain why scanning all buckets per probe row degenerates to a nested loop, and name the alternatives: index nested loop and sort/merge-based algorithms.
Focus on the practical rescue — surface an equality component, index the inner side for range access, or discretize the range into buckets — and mention type/collation mismatches that silently disable hashing.
Discuss modelling choices that avoid pure range joins entirely, such as materializing resolved keys or choosing a bucketing grain, and the cost/accuracy tradeoffs each implies.
## What a hash table actually offers A hash table stores entries in buckets chosen by `bucket = hash(key) mod n`. The point of a good hash function is **uniform scattering**: it deliberately destroys any relationship between the input value and where it lands, so that entries spread evenly and collisions stay rare. That is precisely what gives constant-time lookups. That property has a hard corollary. Because the mapping is scattering, adjacency is destroyed: `2024-01-01` and `2024-01-02` are as unrelated in bucket space as `2024-01-01` and `1970-06-17`. There is no way to enumerate "all keys between A and B" without visiting every bucket. A hash table answers one question and one only — **exact match**. ## Why that forbids range joins A hash join's probe step is "take this probe row's key, hash it, go to that bucket, compare". To satisfy a predicate like `probe.ts BETWEEN build.from_ts AND build.to_ts`, the engine would need, per probe row, all build rows whose interval contains a value — an unbounded set spread across every bucket. Doing that means scanning the whole hash table for each probe row, which is exactly O(M × N): a nested loop with extra steps. So the optimizer will never produce it, no matter how the SQL is phrased. This is a structural limitation of the algorithm, not a missing feature or a tuning knob. ## What ordering-based algorithms do instead Compare with the other physical joins: - **Merge join** works on *sorted* inputs and advances two cursors. Sorting preserves adjacency, so a merge-style algorithm can naturally handle ordered comparisons and, in engines that implement it, band or range joins — the cursor over one side only has to move forward as the other advances. - **Nested loop with an index** works because ordered index structures (B-trees) support range access: descend to the start of the range and walk the leaf level. For interval containment, specialized structures (interval trees, or range-capable index types in engines that offer them) can answer overlap queries directly. The pattern: **range predicates need order-preserving structures**; hashing is the one common structure that throws order away. ## The mixed-predicate case, which is what usually saves you Most real "range join" queries are not pure ranges. A temporal lookup is typically *equal entity* **and** *timestamp within validity window* — for example matching an event to the version of a record that was in effect at the time, scoped by an id. When the predicate has an equality component, the engine can: 1. hash-join on the equality columns, which cuts the candidate set from N to the small group sharing that key, and 2. apply the range condition as a **residual filter** (sometimes called a join filter or extra qualification) on the matched pairs. This is normally the fix for a slow range join: make sure the equality part exists and is expressed in the query, so the engine has something to hash on. If the entity id is genuinely absent from the predicate, you are asking for a cross-product filtered by a range, and the engine's honest options are a nested loop with a suitable index or a sort-merge-style band join. ## Practical remedies for a pure range join - **Index the inner side for range access** so a nested loop becomes cheap: an ordered index on the boundary column, or a range/interval index where the engine supports containment and overlap operators. - **Add or expose an equality component** — very often a tenant, account, or entity id belongs in the predicate and was simply omitted, or can be derived. - **Discretize the range** — bucket time into fixed grains (e.g. day) and join on the bucket equality, then filter precisely. This deliberately converts part of a range predicate into an equality predicate the hash join can use; it trades a little redundancy for a workable algorithm. - **Reduce the probe side first** — filter and aggregate before the join so even an expensive algorithm has less to chew. - **Pre-materialize** — if the range mapping is stable, resolve it once into an explicit key column and join by equality thereafter. ## Related gotcha: equality that isn't hashable Equality alone is not always sufficient. The engine must be able to hash the values consistently with the comparison semantics: mismatched types with implicit conversion, collation-sensitive text comparison, or a user-defined equality without a matching hash function can all block a hash join even though the predicate looks like `=`. If a plan refuses a hash join on an apparently equal predicate, check whether both sides are the same type and comparison semantics, since an implicit cast on one side can also disable index use at the same time. ## The one-sentence answer Hash joins are equality-only because hashing scatters values to destroy ordering — the very property that makes lookup constant-time — and range predicates fundamentally require order to be preserved.
- What join methods can implement a range join?A nested loop over an order-capable index on the inner side — a B-tree for boundary comparisons, or an interval/range index where the engine supports containment operators. Sort-based merge algorithms can also handle band or range joins in engines that implement them, because sorted input preserves adjacency and lets a cursor advance monotonically. Both rely on order, which is exactly what hashing discards.
- A predicate has both an equality and a range component. What does the engine do?It typically hash-joins on the equality columns, which reduces candidates to the small group sharing that key, then applies the range condition as a residual filter on the matched pairs. This is why adding a legitimate equality column — an entity or tenant id — usually rescues a slow range join. The range is still evaluated, but over a tiny candidate set instead of the whole table.
- A predicate is written with '=' but the plan still refuses a hash join. What would you check?Whether the two sides are really comparable in a way the engine can hash consistently: mismatched data types forcing an implicit conversion, different text collations, or a user-defined equality operator without a corresponding hash function. Type mismatches are the usual culprit and often disable index usage at the same time. Aligning the column types on both sides commonly restores both the hash join and index access.
A hash table is a coat check: your ticket number takes you straight to your coat, instantly. But nobody can ask the coat check for "all coats belonging to tickets 400–500" — the numbers were assigned to scatter, not to group. A shelf of coats hung in ticket order (a sorted index) answers that question easily.
saying these in an interview costs you the question
- Claiming a hash join could support ranges "with a better hash function"
- Saying the engine simply chose not to use a hash join and a hint would fix it
- Confusing hash indexes on a column with the hash table built at join time
- Not recognising that a mixed equality-plus-range predicate can still hash on the equality part
- Assuming any predicate written with '=' is automatically hashable regardless of type or collation