Query Execution: Joins, Plans, and Optimization

When you submit a SQL query, the database does not run it literally as written. A query optimizer rewrites it into an efficient execution plan — a tree of physical operators — and the engine executes that plan. Interviewers use this topic to see whether you can read a plan, understand join algorithms, and reason about why a query is slow. It is the most practical database skill you can demonstrate.

The journey of a query

1. Parse: check syntax and resolve table/column names.
2. Rewrite: apply logical transformations — flatten subqueries, push down predicates, simplify expressions.
3. Optimize: the cost-based optimizer enumerates candidate plans (different join orders, join algorithms, index choices) and estimates each one's cost using statistics (row counts, value distributions, histograms). It picks the cheapest.
4. Execute: run the chosen physical plan operator by operator.

The optimizer's decisions are only as good as its statistics. Stale statistics — after a big data load, say — are the number-one cause of a good query suddenly choosing a terrible plan. Running ANALYZE (Postgres) or updating statistics refreshes them.

The three join algorithms

Every relational engine implements three physical joins, and knowing when each wins is core interview material.

Nested loop join

For each row of the outer table, scan the inner table for matches. Naively O(n·m), but with an index on the inner join column it becomes O(n·log m) and is excellent when the outer side is small. This is the go-to join for small result sets and indexed lookups (OLTP point queries).

Hash join

Build a hash table on the join key of the smaller ("build") input, then probe it with each row of the larger input. Cost is roughly O(n + m) — linear — and it is the champion for joining two large unsorted tables on an equality condition. Its weakness: it only works for equijoins, and the build side must fit in memory (or it spills to disk in partitions).

Sort-merge join

Sort both inputs on the join key, then walk them together like merging two sorted lists. Cost is dominated by the sort, O(n log n + m log m), but if the inputs are already sorted (e.g., coming from a B+ tree index in order), the sort is free and it becomes linear. Sort-merge also handles range join conditions and produces sorted output, which can feed a later ORDER BY for free.

| Join | Best when | Handles non-equi? | Output sorted? | |------|-----------|-------------------|----------------| | Nested loop | Small outer + indexed inner | Yes | No | | Hash join | Two large tables, equijoin | No | No | | Sort-merge | Inputs pre-sorted, or range join | Yes (range) | Yes |

Reading an execution plan

EXPLAIN shows the plan the optimizer chose; EXPLAIN ANALYZE actually runs it and shows real timings and row counts.

EXPLAIN ANALYZE
SELECT c.name, SUM(o.total)
FROM customers c
JOIN orders o ON o.customer_id = c.id
WHERE c.country = 'IN'
GROUP BY c.name;

When reading the output, watch for a few tells:

• Seq Scan on a large table where you expected an index — a missing or unusable index, or the filter isn't selective enough.
• A large gap between estimated and actual rows — stale statistics; the optimizer is planning blind.
• A nested loop over a huge inner table — the optimizer misjudged cardinality and should have hashed.
• An expensive Sort feeding a merge join or ORDER BY — a covering ordered index could remove it.

Predicate pushdown and other rewrites

The optimizer tries to filter early so later operators handle fewer rows. Predicate pushdown moves a WHERE condition as close to the scan as possible, even through joins and into subqueries. Projection pushdown drops unneeded columns early. Join reordering picks the order that keeps intermediate results smallest — joining the two tables that produce the fewest rows first. You benefit from these automatically, but writing sargable predicates helps the optimizer help you.

Sargability: let the index do its job

A predicate is sargable (Search ARGument-able) if it can use an index. WHERE created_at >= '2020-01-01' is sargable; WHERE YEAR(created_at) = 2020 is not, because the function hides the raw column from the index. Likewise, a leading wildcard LIKE '%abc' cannot use a normal B+ tree index, while LIKE 'abc%' can. Implicit type casts (comparing a string column to a number) also defeat indexes. Making predicates sargable is often the single highest-impact query fix.

Cardinality estimation: the hard part

Everything hinges on cardinality estimation — guessing how many rows each operator produces. Errors compound: underestimate an intermediate result and the optimizer might pick a nested loop that then runs billions of times. This is why correlated columns (e.g., city and zip), missing statistics, and complex predicates cause bad plans. Extended statistics, histograms, and occasionally query hints exist to correct the optimizer when its independence assumptions fail.

A practical tuning checklist

1. Run EXPLAIN ANALYZE and find the operator consuming the most time.
2. Look for a full scan on a large table; add or fix an index, ensuring the predicate is sargable.
3. Check estimated vs actual rows; if far off, refresh statistics.
4. For a slow join, ask whether the algorithm fits the data sizes (hash for big/big, nested loop for small/indexed).
5. Consider a covering index so the query is answered index-only.
6. Reduce the data touched: filter earlier, select fewer columns, paginate with keyset pagination instead of large OFFSET.

What interviewers actually probe

1. "Explain the three join algorithms and when each is chosen." Nested loop for small/indexed, hash for large equijoins, sort-merge for sorted inputs or range joins.
2. "This query is slow — walk me through debugging it." Reach for EXPLAIN ANALYZE, find the hot operator, check indexes, sargability, and statistics.
3. "Why did the optimizer ignore my index?" Low selectivity, non-sargable predicate, or stale stats making a scan look cheaper.
4. "What is a covering index?" One that contains every column the query needs, enabling an index-only scan.

The mindset that impresses: treat the optimizer as a cost-minimizing planner that depends entirely on accurate statistics and index availability, and treat tuning as removing whatever forces it to touch more rows than necessary.