OLAP – Phase 7 Hash Join
Analytical queries rarely touch a single table. “Revenue by region” needs to join orders with regions. “Sales by product category” needs to join sales with products with categories. The hash join is the standard OLAP join algorithm — it builds a hash table from one table (the smaller one), then probes it with the other (the larger one), achieving O(n + m) complexity instead of nested-loop’s O(n x m).
This phase implements the HashJoinOperator with support for INNER and LEFT joins, including NULL key handling.
In DuckDB, this is PhysicalHashJoin (src/execution/operator/join/physical_hash_join.cpp) and JoinHashTable (src/execution/join_hashtable.cpp).
Here is the roadmap for the phases to come:
- Phase 7: Hash join
- Phase 8: SQL parser
- Phase 9: Query planner and optimizer
- Phase 10: Sorting, parallel execution, REPL, and server
Full Source Code
The code referenced in this post can be found in https://gitlab.com/kimserey.lam/olap-learn.
Build and Probe
The hash join has two phases:
- Build: scan the smaller table (build side), insert every row into a hash table keyed by the join columns
- Probe: stream the larger table (probe side), look up each row’s join key in the hash table, emit combined rows for matches
1
2
3
4
5
6
7
8
9
10
type HashJoinOperator struct {
buildChild PhysicalOperator
probeChild PhysicalOperator
buildKeyExprs []Expression
probeKeyExprs []Expression
joinType JoinType // JoinInner or JoinLeft
buildTypes []vector.LogicalType
ht *JoinHashTable
built bool
}
Why Smaller Table on Build Side?
The build side’s hash table must fit in memory. If you build from the larger table, you waste memory. If you build from the smaller table, the hash table is small, and the larger table streams through without buffering.
Build Phase
Scan all chunks from the build child, extract join keys, and insert the full row (all columns) into the hash table:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func (op *HashJoinOperator) build() {
for {
chunk := op.buildChild.Next()
if chunk == nil {
return
}
var keyVecs []*vector.Vector
for _, expr := range op.buildKeyExprs {
keyVecs = append(keyVecs, expr.Execute(chunk))
}
for row := 0; row < chunk.Count(); row++ {
hasNull := false
for k, kv := range keyVecs {
ki := vecIdx(kv, row)
if !kv.IsValid(ki) {
hasNull = true
break
}
keys[k] = readValue(kv, ki)
}
if hasNull {
continue // NULL keys never match (SQL standard)
}
payload := make([]any, chunk.ColumnCount())
for col := 0; col < chunk.ColumnCount(); col++ {
v := chunk.Column(col)
if !v.IsValid(row) {
payload[col] = nil
} else {
payload[col] = readValue(v, row)
}
}
op.ht.Insert(keys, payload)
}
}
}
NULL Key Handling
Per the SQL standard, NULL = NULL is false (not true). This means rows with NULL join keys never match — the build phase skips them entirely, and the probe phase treats NULL keys as unmatched.
Probe Phase
For each probe chunk, evaluate the probe key expressions, look up each key in the hash table, and emit combined rows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func (op *HashJoinOperator) probe(probeChunk *vector.DataChunk) *vector.DataChunk {
// evaluate probe keys
// ...
for row := 0; row < count; row++ {
// extract keys, check for NULLs
matches := op.ht.Probe(keys)
if len(matches) == 0 {
if op.joinType == JoinLeft {
op.emitLeftUnmatched(probeChunk, row, result)
}
continue
}
for _, match := range matches {
outRow := make([]any, len(outTypes))
// copy probe columns
for col := 0; col < probeChunk.ColumnCount(); col++ {
outRow[col] = readValue(probeChunk.Column(col), row)
}
// copy build columns from match
offset := probeChunk.ColumnCount()
for col := 0; col < len(op.buildTypes); col++ {
outRow[offset+col] = match.payload[col]
}
result.Append(outRow)
}
}
return result
}
Duplicate Keys
A join key might match multiple build-side rows. The JoinHashTable uses chaining (linked list of entries with the same key) to handle duplicates — Probe returns all matches, and the operator emits one output row per match.
LEFT JOIN
A LEFT JOIN keeps all probe-side rows, even when there’s no match on the build side. Unmatched rows get NULLs for the build columns:
1
2
3
4
5
6
7
8
9
10
11
12
13
func (op *HashJoinOperator) emitLeftUnmatched(probeChunk *vector.DataChunk, row int, result *vector.DataChunk) {
outRow := make([]any, probeChunk.ColumnCount()+len(op.buildTypes))
for col := 0; col < probeChunk.ColumnCount(); col++ {
v := probeChunk.Column(col)
if !v.IsValid(row) {
outRow[col] = nil
} else {
outRow[col] = readValue(v, row)
}
}
// build columns remain nil (NULL)
result.Append(outRow)
}
Example
1
2
3
4
5
6
7
Build (departments): Probe (employees):
id | dept_name name | dept_id
1 | Engineering Alice | 1
2 | Sales Bob | 2
3 | Marketing Carol | 1
Dave | 4 (no match)
Eve | 2
INNER JOIN on dept_id = id:
1
2
3
4
Alice | 1 | 1 | Engineering
Bob | 2 | 2 | Sales
Carol | 1 | 1 | Engineering
Eve | 2 | 2 | Sales
Dave (dept_id=4) has no match, so he’s excluded.
LEFT JOIN on dept_id = id:
1
2
3
4
5
Alice | 1 | 1 | Engineering
Bob | 2 | 2 | Sales
Carol | 1 | 1 | Engineering
Dave | 4 | NULL | NULL
Eve | 2 | 2 | Sales
Dave is kept, with NULLs for the build columns.
Operator Lifecycle
The complete flow:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func (op *HashJoinOperator) Next() *vector.DataChunk {
if !op.built {
op.build() // consume all build input → hash table
op.built = true
}
for {
probeChunk := op.probeChild.Next()
if probeChunk == nil {
return nil
}
result := op.probe(probeChunk)
if result != nil && result.Count() > 0 {
return result
}
}
}
The build phase is a pipeline breaker (must see all build input), but the probe phase streams — each probe chunk is processed independently.
Summary
The hash join is O(n + m) — build an in-memory hash table from the smaller table, then stream through the larger table probing for matches. NULL keys never match. LEFT JOIN keeps unmatched probe rows with NULL build columns. Duplicate keys are handled via chaining in the hash table, emitting one output row per match.
