Take a 50M-row jobs table joined to a 10K-row users table to show each job's
owner name, filtered by owner_id and status, sorted newest first, LIMIT 50.
Should you denormalize the owner name onto jobs to avoid the join?
Start with the simplest join, a nested loop: for each job, scan users for the
matching user_id. Worst case that's 50M × 10K comparisons. An index on
users.user_id makes each lookup cheap, about four page reads instead of a
scan, but it's still one lookup per job row: 50M × 4. Driving the loop from the
10K users instead cuts the lookups, but if 50M jobs match you still produce 50M
rows.
None of that matters for this query, because every condition in it, owner_id,
status, the sort and the LIMIT, is on jobs alone. The database can apply
all of it first and join afterwards. At most 50 rows reach the join: 50
primary-key lookups into a small table that sits in memory. The join is nearly
free, so there's no reason to denormalize.
Denormalizing pays when the filter can't run first because it needs the join's
output. Say the query is WHERE u.display_name LIKE 'Ali%'. You can't know which
jobs qualify until you've joined them to users, so the cheap order is gone.
Copying the name onto jobs and indexing it there helps, and the point isn't
avoiding the join: it's letting the filter run before it. Applying filters as
early as possible is called predicate pushdown.
I first thought an index on users would shrink the join to 10K operations, and
I needed a nudge to see that filtering before joining is what saves the query;
the case where denormalizing pays is the part I worked out from there.
Markus Winand's Use The Index, Luke has a good chapter on how join algorithms and indexes interact.