Query execution - System Design Guide

Overview

When a database receives SQL, it parses it, rewrites it, and the query planner (optimizer) estimates the cost of many possible execution plans using table statistics, then runs the cheapest. The plan decides whether to scan a table or use an index, which join algorithm to use, the join order, and whether to sort or aggregate in memory or on disk.

Reading execution plans with EXPLAIN is the core skill for database performance. Most slow queries come from a few causes: missing indexes, outdated statistics causing bad estimates, functions that prevent index use, or joins that explode row counts.

A GPS planning a route

You say where you want to go (declarative SQL). The GPS considers many routes and picks the fastest based on its map and traffic data (statistics). If the map is outdated, it might send you through a closed road.

When to use it

Diagnosing slow queries.
Validating that new indexes are used.
Understanding why a query got slower after data grew.
Interview deep dives on database performance.

Where it shows up in interviews

Slow query diagnosis

Recognize it when: this query takes seconds; why?

Optimize a dashboard query
Fix a report that times out

Where it is used in real software

EXPLAIN ANALYZE

PostgreSQL shows estimated vs actual rows and time per plan node; big mismatches reveal bad statistics.

Query plan regressions

A plan change after data growth or a statistics update can suddenly make a fast query slow; tools like pg_hint_plan and SQL Server Query Store help control it.

Columnar engines

Analytical databases (BigQuery, Snowflake) use vectorized execution and column pruning for fast scans of billions of rows.

Key terms

Seq scan: Read the whole table.
Index scan / index-only scan: Use an index to find rows; index-only avoids the table.
Nested loop / hash / merge join: Three join algorithms suited to different sizes and orderings.
Cardinality estimate: The planner's guess of how many rows each step returns.
Statistics: Histograms of column values collected by ANALYZE.

How it works, step by step

1
Parse
Check syntax and build a parse tree.
2
Rewrite
Expand views and apply rules.
3
Plan
Enumerate plans, estimate costs from statistics, pick the cheapest.
4
Execute
Run plan nodes (scans, joins, sorts), streaming rows upward.
5
Return results
Send rows to the client.

Execution of a join query

Parse SQL

Planner

Index scan orders

Hash join customers

Sort + limit

Result

STEP 1SELECT ... FROM orders JOIN customers ... WHERE orders.created_at > now() - 1 day ORDER BY total DESC LIMIT 10.

Join algorithms

The planner picks based on sizes and indexes

Algorithm	How it works	Best when
Nested loop	For each outer row, look up matches (often via index)	Small outer side, indexed inner side
Hash join	Build a hash table on the smaller input, probe with the larger	Large unsorted inputs, equality joins
Merge join	Walk two sorted inputs together	Both inputs already sorted on the join key

NOWAlgorithm: Nested loop | How it works: For each outer row, look up matches (often via index) | Best when: Small outer side, indexed inner side

A nested loop over two large tables without an index is the classic disaster: O(n x m). Estimates drive the choice, so stale statistics can pick the wrong algorithm.

Implementation

1EXPLAIN (ANALYZE, BUFFERS)2SELECT c.name, o.total_cents3FROM orders o4JOIN customers c ON c.id = o.customer_id5WHERE o.created_at > now() - interval '1 day'6ORDER BY o.total_cents DESC7LIMIT 10;8 9-- Read the output bottom-up:10-- Limit11--   -> Sort (top-N heapsort)12--        -> Hash Join (cond: c.id = o.customer_id)13--             -> Index Scan using idx_orders_created on orders  (rows=19850 actual=20112)14--             -> Hash -> Seq Scan on customers15-- Estimated vs actual rows close: statistics are healthy.16 17-- If estimates are far off, refresh statistics18ANALYZE orders;

Complexity and performance

Nested loop (no index)O(n x m)

Avoid on large inputs.

Hash joinO(n + m)

Needs memory for the hash table.

Merge joinO(n + m)

Plus sort cost if unsorted.

Trade-offs

Optimizer autonomy vs control

The planner usually knows best, but hints or query rewrites are sometimes needed for stable performance.

Memory vs disk

Sorts and hashes that exceed work memory spill to disk and become much slower.

Variants and related techniques

Prepared statements

Parse and plan once, execute many times with parameters.

Parallel query

Split scans and aggregations across CPU workers.

Common mistakes

SELECT * everywhere.
Fix: Selecting only needed columns enables index-only scans and less I/O.
Functions on indexed columns in WHERE.
Fix: Rewrite or add an expression index.
OFFSET for deep pagination.
Fix: OFFSET 1,000,000 still reads a million rows; use keyset pagination.

Interview questions

How do you read an execution plan?

Bottom-up: identify scans (seq vs index), join types, and sorts; compare estimated and actual row counts; find the node with the most time. Big estimate errors indicate stale statistics or correlated columns.

Why is OFFSET pagination slow for deep pages?

The database must still read and discard all skipped rows. Keyset pagination (WHERE created_at < last_seen ORDER BY created_at DESC LIMIT 20) seeks directly using an index.

Practice problems

Problem	Difficulty	What it trains
Read 3 EXPLAIN outputs and find the problem	Medium	Plan reading.
Replace OFFSET pagination with keyset	Easy	Seek method.