CSE Roadmap

Core tier · about 2 hours · 5 parts

Part 5 of 5 · 4 min read

Exercises

Easy

Easy 1: Name the three join algorithms (15 minutes)

Name the three join algorithms covered on this page.

Done when: nested loop, hash join, and sort-merge join are all correctly named.

Hint

Nested loop join, hash join, sort-merge join.

Easy 2: Name when nested loop works well (15 minutes)

State one condition under which a nested loop join performs well.

Done when: a small outer table, or an indexed inner table's join column, is correctly named.

Hint

A small outer table, or an indexed join column on the inner table.

Easy 3: Name what a hash join builds (15 minutes)

State what a hash join builds from its build side, before scanning the probe side.

Done when: an in-memory hash table, keyed by the join column, is correctly named.

Hint

An in-memory hash table keyed by the join column, built from the build side.

Medium

Medium 1: Match an algorithm to a scenario (25 minutes)

Two very large tables need to be joined, neither sorted nor indexed on the join column. Decide which of the three algorithms is the most natural fit, and explain why.

Done when: hash join is chosen, with the explanation correctly citing the avoidance of repeated scans without relying on existing sort order.

Hint

A hash join, since it avoids repeated scans and does not depend on either table already being sorted.

Medium 2: Match an algorithm to a different scenario (25 minutes)

Both tables being joined are already indexed, and therefore sorted, on the join column. Decide which algorithm is the most natural fit, and explain why.

Done when: sort-merge join is chosen, with the explanation correctly citing the ability to merge directly off the existing sorted order without a separate sort step.

Hint

A sort-merge join, since both sides are already sorted and can be merged directly without an extra sorting step.

Medium 3: Explain why nested loop suits a small outer table (30 minutes)

Explain why a nested loop join performs poorly when the outer table is very large, even if the inner table's join column is indexed.

Done when: the explanation correctly notes the inner lookup, even if cheap individually, repeats once per outer row, so a very large outer table still means a very large number of repeated lookups.

Hint

Each outer row still triggers one lookup, so a very large outer table means a very large number of lookups, even if each individual lookup is cheap.

Hard

Hard 1: Explain why hash join avoids what nested loop repeats (30 minutes)

Explain, in terms of the work each algorithm does, why a hash join can be cheaper than a nested loop join when no index exists on the join column.

Done when: the explanation correctly notes nested loop would need a full inner-table scan repeated once per outer row with no index, while hash join scans each table only once, probing a hash table instead of repeating a scan.

Hint

Without an index, nested loop repeats a full table scan once per outer row; hash join instead scans each table exactly once, using a hash table lookup in place of a repeated scan.

Hard 2: Explain the cost of sort-merge when neither side is sorted (35 minutes)

Explain what additional cost a sort-merge join incurs when neither table is already sorted by the join column.

Done when: the explanation correctly notes both tables must first be sorted, via external sort if they do not fit in memory, before the merge pass can even begin, adding a real cost not present when sorted order already exists.

Hint

Both tables must be sorted first, potentially using an external sort if they exceed memory, adding real cost before the merge pass can begin, unlike the case where sorted order already exists from an index.

Hard 3: Predict which algorithm the optimizer picks given changing conditions (40 minutes)

A query joins two tables that currently have no indexes on the join column. Later, an index is added to one of the two tables on that column. Explain how this change might affect which join algorithm the optimizer picks.

Done when: the explanation correctly notes the optimizer might switch from a hash join to a nested loop join once an index exists, if the indexed table is small enough or selective enough to make repeated indexed lookups cheaper than building and probing a hash table.

Hint

The optimizer might switch to a nested loop join, since the new index could make repeated indexed lookups on the indexed table cheaper overall than building and probing a hash table.