Section 3: Physical Join Implementations

Nested-Loop Join

Default join method scanning the entire inner table for each outer record[cite: 2]

Outer Relation Rule

Smaller relation (fewer disk blocks) must always be outer to minimize I/O[cite: 2]

Indexed Nested-Loop

Outer records drive direct index or hash lookups into the inner relation[cite: 2]

Sort-Merge Join

Join requiring both relations to be physically sorted on the join attribute[cite: 2]

Hash Join

Builds an in-memory hash table on smaller table, then probes with second[cite: 2]

Partitioning Phase

First hash join phase dividing the smaller relation into hash buckets[cite: 2]

Probing Phase

Second hash join phase scanning second table and matching against buckets[cite: 2]

Minimum Hash Buffers

Partitioning into M buckets requires at least M + 1 memory buffer blocks[cite: 2]