Execution Plan for Joins

Hook: Interviewers love this because a join can look simple in SQL but become expensive or wrong once the optimizer chooses a plan.

Question: What is an execution plan for joins?

Answer: An execution plan is the database's chosen recipe for how it will read tables and combine matching rows. For joins, the optimizer decides the join order, the access path for each table, and the physical join method such as nested loop, hash join, or merge join. The plan matters because two SQL queries that look similar can have very different runtimes.

Interview-Ready Answer: An execution plan for a join is the database's step-by-step strategy for combining rows. I look for the join order, the join algorithm, and the scan type on each table, because those three choices usually explain why a query is fast or slow. If the plan is bad, I check statistics, indexes, and whether an outer-join filter was placed in the wrong clause.

What it is

An execution plan is the database's chosen path from SQL text to result rows. For joins, the plan shows which table is read first, how rows are matched, and whether the engine will loop, hash, or sort and merge the inputs.

How the optimizer thinks

1. Parse and normalize. The database rewrites your SQL into an internal form and separates join conditions from plain filters.
2. Estimate row counts. It uses statistics such as table size, distinct values, and histograms. Selectivity means the fraction of rows a condition keeps; low selectivity usually means fewer rows and cheaper joins.
3. Choose join order. For inner joins, the optimizer can often reorder tables to reduce work. For outer joins, the preserved side must stay logically protected, so the optimizer has fewer freedoms.
4. Pick the physical algorithm. A physical algorithm is the actual method used to combine rows: nested loop, hash join, or merge join.
5. Execute and compare. Tools like EXPLAIN ANALYZE show estimated rows versus actual rows. If the estimate is far off, the planner may have chosen the wrong join method.

Join algorithms

How to read a join plan

1. Start at the root. The top node is the final result. Work downward to see how rows are produced.
2. Find the join node. Look for Nested Loop, Hash Join, or Merge Join. That tells you the algorithm.
3. Check the scan types. Seq Scan means a full table read; Index Scan means the engine is using an index to find rows faster.
4. Compare estimated and actual rows. A big gap, like 100 estimated versus 100000 actual, often explains a bad plan choice.
5. Look for pushdown. If filters are applied before the join, less data flows through the plan, which is usually better.

Performance and complexity notes

Nested loop is great when one side is tiny or the inner side has a good index, but without that index it can behave like O(n*m). Hash join is often close to O(n + m) on average, but it needs memory for the hash table; if the build side is too large, the engine may batch or spill. Merge join is roughly O(n log n + m log m) if sorting is needed, but can be close to linear if both inputs are already ordered.

A very common failure pattern is stale statistics. The optimizer may think a join returns 200 rows when it really returns 2 million, so it picks nested loop and then spends seconds or minutes doing repeated scans.

Important edge cases

• Inner joins can often be reordered; outer joins usually cannot be moved as freely.
• A filter in WHERE after a LEFT JOIN can remove the null-extended rows and change the meaning of the query.
• NULL does not match =, so rows with null join keys do not match by equality.
• An index is not always a win; if most rows match, a scan plus hash join may be cheaper.

Memory hook: nested loop knocks on every door, hash join uses a phonebook, and merge join zips two sorted lines together.

Real-World Story: Imagine a checkout service that joins customers, orders, and payments to build an order summary page. One morning, traffic spikes and the page starts timing out because the planner thinks the join will return only a few hundred rows, so it picks a nested loop and repeatedly scans a much larger table. In the logs you see slow-query warnings, CPU near 100%, and EXPLAIN ANALYZE showing huge gaps between estimated rows and actual rows. The fix is usually a better index, updated statistics, or moving a filter so the database can reduce rows before the join.

There is also a correctness bug version of this story: a developer puts a right-table filter in the WHERE clause after a LEFT JOIN, and suddenly customers with no orders disappear from the report. The dashboard looks clean, but the numbers are wrong, and finance notices that the totals no longer match the source of truth.

Follow-up & Tricky Questions:

• How does the optimizer choose join order? It uses table statistics, selectivity, and estimated cost. For inner joins it may reorder freely, but outer joins constrain the choices because row preservation matters.
• When does a hash join beat a nested loop? Usually when both inputs are large and the join is an equality match. Hash join avoids repeated scans, but it needs enough memory to hold the build side.
• Why does an index sometimes not help a join? If many rows match, the engine may prefer a scan plus hash join because random index lookups would cost more. Bad statistics can also make an index look cheaper or better than it really is.
• What is the difference between ON and WHERE in an outer join? ON decides which rows match while keeping unmatched rows alive in a LEFT JOIN. WHERE filters after the join, so it can remove those unmatched rows.
• How do you tell if the plan is lying? Compare estimated rows to actual rows. If they differ by an order of magnitude or more, the optimizer probably had stale stats, skew, or a correlation it could not model well.
• Does the SQL text order always equal execution order? No. The optimizer can reorder inner joins, so the written order is not the same thing as the physical order.
• Is nested loop always bad? No. It is excellent for tiny outer inputs or highly selective indexed lookups. It only becomes painful when it has to repeat a large scan many times.
• Does LEFT JOIN with a right-table filter in WHERE still behave like a left join? Often not. The null-extended rows get removed, so the result behaves like an inner join for those rows.

Common Mistakes:

• Reading the SQL text order as the execution order. Correction: inspect the plan tree, not the query text.
• Ignoring estimated versus actual rows. Correction: a bad estimate is often the real reason for a slow join.
• Putting outer-join filters in WHERE. Correction: keep row-preserving conditions in ON.
• Assuming an index always wins. Correction: for large joins, a hash or merge join can be cheaper than many index probes.

Memory Hook: Knock, Phonebook, Zipper — nested loop knocks on each door, hash join uses a phonebook to find matches fast, and merge join zips two sorted lists together.

Cheat Sheet:

• Execution plan = the database's chosen recipe.
• For joins, check join order, join algorithm, and scan type.
• Nested loop: best for small or indexed lookups; worst-case O(n*m).
• Hash join: great for large equality joins; may spill if memory is tight.
• Merge join: likes sorted inputs and range-friendly data.
• Outer joins are sensitive to ON versus WHERE.

Practice Tasks:

• Run EXPLAIN on an INNER JOIN and a LEFT JOIN, then note the join type.
• Move a filter from ON to WHERE and compare the result rows.
• Add or remove an index, run ANALYZE, and see how the plan changes.