ProjekinAja. Software Engineering Stage 3 · Systems Lesson 3.5
● Stage 3 · Lesson 3.5

Databases II: Queries, Indexes, and the Planner

B-trees pay for everything — joins, EXPLAIN, and why TraceLab's "metrics by run" query goes from 4 seconds to 4 milliseconds here.

⏱ ~22 min read 🗃 Query internals ⚡ TraceLab v2

🎯 By the end you'll understand

Why thinking in sets — not loops — is the mental model that unlocks SQL; how the query planner picks a plan and what EXPLAIN actually shows you; why indexes are just Lesson 1-7's B-trees wearing a costume; the write amplification tax every index levies; the N+1 query problem (the classic ORM ambush); and how adding two indexes turns TraceLab's 4-second dashboard query into a 4-millisecond one.

KEY INSIGHTB-trees pay for everything

An index is not magic and not free. It is a B-tree the database maintains for you — and every write to the table rewrites a path through that tree.

The gap between a query that returns in 4 milliseconds and one that returns in 4 seconds is almost always an index. Not a rewrite of the query logic, not a hardware upgrade, not a caching layer — a single CREATE INDEX line that tells the planner it no longer needs to read every row. You have already studied this data structure in Lesson 1.7. This lesson shows you it in production clothes, with real costs attached to both sides of the ledger.

🔑 Hold onto this

The query planner's job is to find the cheapest plan that produces correct results. "Cheapest" means fewest page reads — disk I/O, not CPU, is almost always the bottleneck. An index eliminates rows before the planner touches them. But the planner also has to maintain every index on every INSERT, UPDATE, and DELETE, which is why the question "should I add an index?" is never purely about reads. Understanding the planner makes the tradeoff legible. Ignoring it is how you turn a telemetry table into a pager alert.

CORE CONCEPTThinking in sets: the mental model that changes everything

Most programmers come to SQL from Python, and their instinct is to think procedurally: "loop over the runs, then for each run loop over its metrics." SQL was designed to resist that instinct. It thinks in sets: describe the shape of the answer, and let the engine figure out how to produce it. This distinction is not aesthetic — it is the reason the planner can optimize at all.

A Python approach to "find all runs with average loss below 0.5" might look like this:

tracelab_query.pyprocedural
# reading every metric row in Python — the wrong shape of thought
results = []
for run in db.query("SELECT * FROM runs"):
    metrics = db.query("SELECT * FROM metrics WHERE run_id = ?", run.id)
    avg_loss = sum(m.value for m in metrics if m.name == "loss") / len(metrics)
    if avg_loss < 0.5:
        results.append(run)

The SQL version describes the same result as a declaration, not a procedure:

-- SQLset-based
SELECT r.id, r.name, AVG(m.value) AS avg_loss
FROM   runs r
JOIN   metrics m ON m.run_id = r.id
WHERE  m.name = 'loss'
GROUP BY r.id, r.name
HAVING AVG(m.value) < 0.5;

The Python code is O(N) queries against the database — one per run. The SQL is O(1) queries. It is not just more compact; it hands the engine an entire specification, which the planner can translate into a single hash join or index scan that the Python loop structurally cannot produce.

💡 SQL's logical evaluation order is not its execution order

You write SELECT … FROM … WHERE … GROUP BY … HAVING … ORDER BY … but the planner is free to reorder everything. It may filter before joining, hash before sorting, or scan an index instead of the table. The clause order in your SQL is a logical specification; the physical execution is the planner's business. EXPLAIN is how you peek at what it decided.

HOW IT WORKSJoins, aggregation, and what the planner does with them

A join is a set-theoretic operation that produces a new relation by matching rows from two (or more) tables on a predicate. The three physical strategies a planner uses — and that matter to your query performance — are:

1

Nested-loop join

For each row in the outer table, scan the inner table looking for matches. Cost: O(N × M) — catastrophic without an index on the inner join key. Great when the outer side is tiny (a few rows) and the inner has an index. This is the shape your Python loop above was implementing, accidentally.

2

Hash join

Build a hash table from the smaller table (the "build" side), then probe it with each row from the larger (the "probe" side). Cost: O(N + M) — fast for large equi-joins when neither side has a useful index. The hash table has to fit in work_mem; spill to disk and performance craters.

3

Merge join

Both sides must be pre-sorted on the join key (or have a usable index). Then a single O(N + M) linear pass merges them, like the merge in merge-sort. Great for large sorted tables; terrible if you pay the sort cost yourself first.

The planner chooses by estimating costs: it has statistics about the table (row count, column cardinality, histogram buckets) and multiplies those estimates through the plan tree. A wildly wrong estimate — say, after a massive INSERT before ANALYZE runs — causes the planner to pick the wrong strategy and your 4-millisecond query becomes a 4-second one again, without any code change.

Hash Join ON m.run_id = r.id Seq Scan: runs cost=0..18 rows=950 Index Scan: metrics on metrics_run_id_idx Plan tree (from EXPLAIN). Execution flows leaf → root. Operator cost = subtree cost + local cost.
A simplified EXPLAIN output rendered as a plan tree. The planner chose a Hash Join because the left side (runs) fits in memory. The right side uses an index scan on run_id — without that index, this becomes a 1M-row Seq Scan per join.

Aggregation is the other common operation: GROUP BY partitions rows into buckets and applies aggregate functions (AVG, COUNT, SUM, MAX) to each. It can be implemented as a hash aggregation (build a hash table keyed on the group columns) or a sort-based aggregation (sort first, then scan linearly). Postgres uses statistics to choose; a covering index that already returns rows in sorted order can turn a sort + aggregate into a near-free incremental pass.

📖 Reading EXPLAIN (ANALYZE)

Run EXPLAIN (ANALYZE, BUFFERS) your_query. The output is a plan tree in indented text. Each node shows cost=startup..total (planner estimate, in arbitrary cost units), rows=N (estimated), and — because of ANALYZE — actual time=Xms rows=M (real). The delta between estimated and actual rows is your canary: a large discrepancy means stale statistics. BUFFERS adds page hits and misses — the true cost. "Seq Scan" means full table read; "Index Scan" means tree traversal; "Bitmap Index Scan + Heap Fetch" is the in-between case for larger result sets.

SEE ITSQL index cost visualizer

The TraceLab dashboard runs three queries against the metrics table. Pick a query, toggle indexes on and off, and watch the plan shape (scan vs. index seek), estimated row reads, latency, and write amplification move in real time. The ORM mode reveals what happens when the ORM fires a separate query per run — the N+1 ambush.

⚙ Interactive · SQL Index Cost Visualizer — 1 M simulated rows

Deterministic model: latency and row-read estimates based on B-tree height log₂(N) and typical 8KB page arithmetic. Not a real database, but the ratios are accurate.

Plan type
—
Rows read
—
Est. latency
—
Query count
—
Write overhead
—
⏳Select a configuration above…

Toggle indexes and query to see the plan change.

Write amplification — active indexes
0 indexes (1× write)3 indexes (1.8× write)

Three things to notice. First: the dashboard query with no indexes reads all 1,000,000 metrics rows — a sequential scan pays for every missing index. Second: adding the run_id index turns the join from a hash over the full table into a set of index seeks; the row count drops to only the rows you asked for. Third: ORM mode with no index fires 1,001 queries (one per run plus one to list runs) — the N+1 problem in live action. The query count does not shrink when you add indexes, only latency drops; the structural fix is to rewrite the ORM call to use a join (Django's select_related, SQLAlchemy's joinedload).

CORE CONCEPTIndexes are Lesson 1-7's B-trees wearing a costume

A database index and a B-tree from Lesson 1.7 are the same structure — a balanced tree of (key, pointer) pairs that keeps data sorted so that range and equality queries need only traverse O(log N) nodes. In Postgres, a B-tree index leaf page holds pairs of (indexed column value, TID) — the table row's physical location (file block number + offset). A lookup walks from root to leaf in log₂(N) steps, then follows the TID directly to the heap page. On a 1M-row table with 8KB pages, the tree is 3–4 levels tall. The index scan visits 3–4 pages; the sequential scan visits ~7,800 pages (1M rows × 64 bytes ÷ 8,192 bytes/page).

B-tree index (metrics.run_id) Root key ranges: [1..500K | 500K..1M] Internal page run_id 1..500K Internal page run_id 500K..1M Leaf page (run_id=42, TID) → heap Heap (table file) 8KB pages, rows stored in insertion order. Seq scan reads every page (~7,800 pages). Index scan follows TID → 1 page fetch. TID → heap fetch 3–4 levels for 1M rows (8KB pages) · O(log N) page reads
The B-tree index maps sorted key values to TIDs (heap row pointers). An index scan touches 3–4 tree pages then one heap page. A sequential scan reads all ~7,800 heap pages. The root-to-leaf path is exactly what Lesson 1.7 called O(log N) search.

Two common index variants you will encounter in Postgres:

⚠ Every index is a write tax

Adding an index means every INSERT, UPDATE (of indexed columns), and DELETE must also update the B-tree: find the right leaf, insert or delete the entry, possibly split or merge pages, update parent pointers. Postgres's MVCC model writes a new heap tuple on update and must invalidate the old index entry — a dead index tuple that HOT (Heap-Only-Tuple) optimization sometimes avoids, but not always. On a write-heavy telemetry table (TraceLab's raw event ingestor, say), adding three indexes to a 100K-row-per-minute table is not free. Measure write throughput before and after.

WEAKNESSWhere queries bite — the three failure modes

✗ The N+1 query problem — the classic ORM ambush

An ORM returns a list of Run objects; then your template or view code accesses run.metrics on each one. The ORM silently fires a separate SELECT per run. With 1,000 runs: 1 query to list runs + 1,000 queries to load metrics = 1,001 round trips. Each round trip has a minimum overhead of ~1ms (network + parse + plan). The page that "should" load in 50ms takes 1,050ms. The fix is always the same: force the ORM to emit a single join. In Django: Run.objects.prefetch_related('metrics'). In SQLAlchemy: options(joinedload(Run.metrics)). The problem is invisible in development with a 10-row fixture database; it announces itself in production with the first real dataset.

✗ The unindexed telemetry table that brings a product to its knees

This is not hypothetical — it is the standard incident. A startup ships a product with a events table. It has no indexes beyond the primary key because the team said "we'll add them when we need them." The table grows to 50M rows. A dashboard query does a full sequential scan: 50M row evaluations, 60 GB of table data touching the buffer pool, evicting cached pages for everything else, 40-second query time. The emergency CREATE INDEX CONCURRENTLY runs for 2 hours and temporarily doubles write latency while it builds. The lesson: design your index set at schema design time, not post-incident. The write overhead of three sane indexes on a 50-row-per-second table is noise; the read latency of a missing index on a 50M-row table is a P1 incident.

✗ Stale statistics making the planner pick the wrong plan

The planner's cost model is only as good as its statistics. Postgres runs AUTOVACUUM to update them, but autovacuum has limits: it has a cost budget per round, it cannot keep up with bulk loads, and it is often disabled on cloud-hosted databases by operators trying to reduce noise. After a large data migration that triples a table's row count, the planner may still estimate 1M rows when there are 3M, and choose a nested-loop join that made sense for the old data but is catastrophic for the new. The fix is manual: ANALYZE table_name; after any bulk operation. This is why your staging → production migration should include a post-load ANALYZE in the runbook.

TRACELABPaying the metrics query debt — TraceLab v2

In Stage 1, TraceLab v0 had find_run doing a full file scan. We noted the debt: "lookups go O(n²) across a workflow." In Stage 3, TraceLab v2 has graduated to Postgres — but it shipped its first version of the metrics table without indexes, exactly like the incident above. Here is what the schema looks like, and what we change this lesson.

migrations/003_add_indexes.sqlv2 · paying the index debt
-- metrics: 1M+ rows, queried by run_id constantly
CREATE INDEX CONCURRENTLY metrics_run_id_idx
    ON metrics (run_id);

-- composite index: dashboard aggregates by (run_id, name) together
CREATE INDEX CONCURRENTLY metrics_run_id_name_idx
    ON metrics (run_id, name);

-- runs: dashboard filters to last 30 days constantly
CREATE INDEX CONCURRENTLY runs_created_at_idx
    ON runs (created_at DESC);

-- ANALYZE so the planner knows about the new structure immediately
ANALYZE metrics;
ANALYZE runs;

The dashboard query that was producing a full sequential scan now looks like this in the EXPLAIN output:

-- EXPLAIN (ANALYZE) result after indexestrimmed
HashAggregate  (cost=820..880 rows=950) (actual time=3.2..3.8 ms)
  -- aggregation over the join result
  -> Hash Join  (cost=100..720) (actual time=0.8..2.9 ms)
        Hash Cond: (m.run_id = r.id)
        -> Index Scan using metrics_run_id_name_idx on metrics
               Index Cond: (name = 'loss')
               actual time=0.3..1.4 ms  rows=47,900
               Buffers: shared hit=562 (was: 10,218 before index)
        -> Seq Scan on runs  (cost=0..18)  rows=950
               actual time=0.1..0.3 ms

The highlighted line is the payoff: 562 buffer hits versus 10,218 before. The query went from ~4 seconds (cold sequential scan of a 1M-row table on a shared database) to ~4 milliseconds. The TraceLab dashboard, which runs this query on page load, becomes interactive. The write overhead? With a 50-runs-per-day TraceLab workload (robotics experiments, not a traffic-heavy SaaS), two index B-tree updates per metrics insert adds microseconds. The tradeoff is trivially in favor of the indexes.

The Python side of the TraceLab v2 API now uses the ORM correctly — select_related where we need joined data, raw SQL or explicit annotate() for the aggregation dashboard. The v0 file-scan debt, the relational debt from Lesson 3-4, and the index debt all settle in the same migration.

api/dashboard.pyv2 · avoiding N+1 (illustrative Django ORM — TraceLab uses SQLAlchemy; the pattern is equivalent)
from django.db.models import Avg, Max, Count

def dashboard_summary(days=30):
    # ONE query — aggregation pushed into the database, not Python
    cutoff = timezone.now() - timedelta(days=days)
    return (
        Run.objects
        .filter(created_at__gte=cutoff)
        .annotate(
            avg_loss=Avg("metrics__value", filter=Q(metrics__name="loss")),
            best_reward=Max("metrics__value", filter=Q(metrics__name="reward")),
            metric_count=Count("metrics"),
        )
        .order_by("-created_at")
    )
    # Emits one SQL with a Hash Join + HashAggregate.
    # Without annotate(): 1 + N queries (N+1 problem).

KEY INSIGHTHow this connects

The theme of Stage 3 is systems you treat as magic until they page you. The query planner is a perfect example: when it works, it's invisible; when it breaks (wrong estimate, missing index, N+1 query), it is the most visible thing in your logs. Every layer you have learned to see clearly is a layer you no longer fear at 2 a.m.

GLOSSARYKey terms

Query planner (optimizer)
The database subsystem that translates a SQL query into a physical execution plan by estimating and comparing costs for possible join strategies, scan methods, and aggregation approaches.
Sequential scan (Seq Scan)
Reading every page of a heap table from first to last, evaluating each row against the query predicate. O(N) page reads; unavoidable when no useful index exists or the result set is large enough that index overhead exceeds page-scan cost.
Index scan
Traversing the B-tree index from root to matching leaf pages (O(log N)), then fetching the corresponding heap rows via their TIDs. Optimal when the result set is a small fraction of the table.
TID (Tuple Identifier)
Postgres's physical row address: (block number, item offset within block). Index leaf entries contain TIDs so an index scan can fetch exactly the right heap page.
Write amplification
The extra work a storage system (database, SSD controller, log-structured store) must do beyond the logical write. Each indexed column adds one B-tree update per row insert, update, or delete.
N+1 query problem
A pattern where code issues one query to fetch a list of N objects, then N additional queries to fetch associated data for each object — instead of one joined query. Named for the total query count: N+1.
EXPLAIN (ANALYZE)
Postgres command that shows both the planner's estimated execution plan and — with ANALYZE — the actual measured execution, including row count estimates vs. actuals and buffer hit/miss statistics.
Composite index
An index spanning multiple columns (e.g., (run_id, name)). Satisfies queries filtering on the leftmost prefix; column order determines which queries benefit.

ACTIVE RECALLCheck your understanding

Answer in your own words first, then reveal.

1Why is thinking in sets more powerful than thinking in loops when writing SQL?›

A set-based query hands the engine a complete specification — all the tables involved, all the predicates, all the aggregations — before any execution begins. The planner can then choose the optimal physical strategy: the right join algorithm, the right index, the right aggregation method. A loop forces one physical strategy (row-by-row processing) at the application level, making the engine's optimizer irrelevant. The N+1 query problem is a loop masquerading as SQL.

2What does EXPLAIN (ANALYZE) tell you that EXPLAIN alone does not?›

EXPLAIN alone shows the planner's estimated plan with estimated costs and row counts. EXPLAIN (ANALYZE) actually runs the query and reports actual execution times and actual row counts alongside the estimates. The gap between estimated and actual rows is the key diagnostic: a large discrepancy means stale statistics, which causes the planner to choose the wrong strategy. The BUFFERS option adds page hit and miss counts, which reveal whether the bottleneck is truly I/O.

3A colleague says: "Just add indexes to every column — more indexes can only help reads." What is wrong with this advice?›

Every index levies a write tax: each INSERT, UPDATE, and DELETE must also update every B-tree. On a write-heavy table (a telemetry ingestor, an event log), unnecessary indexes can double or triple write latency and bloat WAL. The planner also has overhead choosing among many indexes. The right approach: identify the specific queries that need acceleration, add targeted indexes, measure write throughput before and after.

4Describe the N+1 query problem and the structural fix at the ORM level.›

N+1 happens when you fetch N objects and then access a relationship on each one, causing the ORM to fire N additional queries — one per object. With 1,000 runs, that's 1,001 queries instead of 1. The structural fix is to tell the ORM to eagerly load the relationship in the initial query using a join: Django's select_related() (for foreign-key relationships, a SQL JOIN) or prefetch_related() (for many-to-many, a second query with IN). SQLAlchemy uses joinedload() or selectinload(). The result is 1 or 2 queries regardless of N.

Next: how concurrent writers race on these same rows — transactions, isolation, and lost updates →