Joining a large table with a small one

WHAT THIS TESTS The interviewer checks that you reason about join strategy from input sizes and memory, a core optimizer concept.

A GOOD ANSWER COVERS When joining a very large table with a very small one, the optimizer commonly picks a hash join, because the small table fits comfortably in memory. A hash join has two phases. In the build phase it reads the small table fully and constructs an in-memory hash table keyed on the join column. In the probe phase it scans the large table once, and for each row computes the hash of its join key and looks it up in the hash table, emitting a joined row for each match. The key win is that the large table is read exactly once with constant-time lookups, giving roughly linear cost in the size of the inputs and avoiding any per-row rescans. An alternative is an index nested loop join: if the large table has an index on the join column, the engine can iterate the small table and probe that index for each row, which is also efficient. A naive nested loop without an index, rescanning the large table for every small-table row, would be quadratic and is what you must avoid.

COMMON WRONG ANSWERS Defaulting to a plain nested loop that rescans the big table, which is catastrophically slow. Building the hash table on the large side instead of the small one. Forgetting that a sort-merge join needs sorting both inputs, less ideal here. Ignoring memory as the deciding factor.

LIKELY FOLLOW-UPS Why build on the small side; what if the small table does not fit in memory; when is an index nested loop better; how does a hash join handle no available index.

ONE CONCRETE EXAMPLE Joining a billion-row events table to a fifty-row event_types lookup: the engine builds a hash table on the fifty types in microseconds, then streams the billion events once, hashing each event's type id to find its name. The big table is read a single time, versus a naive nested loop that would scan the lookup, or worse the events, billions of times.