2026-08-26·FREE·10 min read

Database Internals — What Happens Behind a Single Line of SQL

Between hitting Enter on a SELECT and getting rows back, five stages run inside the database: parser, rewriter, planner, executor, storage. Here is why two plans returning identical rows can differ by orders of magnitude, and why stale statistics make a fast query go slow overnight — from zero background to the knobs you actually turn.

#database #sql #query-optimizer #execution-engine #storage-engine #systems

ModalitytextTasksystems

An analogy: the order ticket and the kitchen

When you order "the special, mild please," you have stated what you want and nothing else. Which pan gets used, which ingredient is chopped first, whether two orders are batched together — the kitchen decides, and it decides differently depending on what is already prepped.

SQL is that order ticket. Write SELECT name FROM users WHERE age > 30 and you have said "give me the names of people over 30." Whether the database scans every row from the top or walks an index on age is not specified anywhere in what you wrote. Something inside the database decides that.

That something is five stages:

Parser — turn text into a tree
Rewriter — reshape the tree without changing its meaning
Planner — pick the cheapest way to compute it
Executor — actually run that way
Storage — move data between disk and memory

"The same query was fast yesterday and is slow today" almost always happens at stage 3. To get there, we build up from stage 1.

SQL declares, it does not command

Ordinary programming languages are procedural: write a for loop and it runs in the order you wrote it. SQL is declarative. You describe the properties of the result you want and say nothing about steps. That means several execution plans can produce the same answer — and the fast one and the slow one can differ by orders of magnitude while returning byte-identical rows.

That freedom is what gives the database room to optimize, and it is also the source of "I have no idea why this is slow." Since no human wrote the steps, the only way to find out is to ask the database which steps it chose. That tool is EXPLAIN, which we get to at the end.

Stage 1: the parser turns text into a tree

What arrives is a string. Lexing chops it into meaningful pieces — SELECT, name, FROM, users, and so on — and parsing assembles those pieces into a tree according to the grammar.

        SelectStmt
        /    |     \
  targets  from   where
     |       |       \
   name    users   (age > 30)

Once it is a tree, no later stage has to touch text again. Getting "the contents of the WHERE clause" becomes following a branch rather than slicing a string.

At this point the database still has not checked whether users exists. That is the job of semantic analysis. A database keeps its own structure — what tables exist, what columns and types they have, what indexes are defined — in internal tables called the catalog. Semantic analysis looks names up there, replaces the table name with an internal ID and the column name with a position, and checks that the types line up. This is where the familiar "column does not exist" error comes from.

Stage 2: the rewriter reshapes without changing meaning

Next come transformations that change the shape but never the answer. The classic one is view expansion: if active_users is a view, its definition is inlined so the tree looks as if you had written it out by hand.

The important part is that the rewriter does not judge which form is faster. That is the planner's job. The rewriter only guarantees "both forms produce the same rows." Because the responsibilities are split, the planner can focus entirely on cost and never worry about correctness of meaning.

Stage 3: the planner picks the cheapest recipe

This is the heart of it. The planner builds many plans that all return the same rows, assigns each an estimated cost, and picks the cheapest.

Cost is not seconds. It is a relative score where "read one page sequentially from disk" equals 1. In PostgreSQL it looks roughly like this:

C = c_{\text{seq}} \cdot P_{\text{seq}} + c_{\text{rand}} \cdot P_{\text{rand}} + c_{\text{cpu}} \cdot N

(1)

In plain words: take the number of pages read in order, the number read by jumping around, and the number of rows processed, multiply each by its unit price, and add them up. The unit prices $c$ are settings; the defaults are seq_page_cost = 1.0 for sequential reads, random_page_cost = 4.0 for random ones, and cpu_tuple_cost = 0.01 per row. Random reads cost four times as much because the default assumes a spinning platter where moving the head is expensive. On SSDs that gap is far smaller, so lowering this value is standard practice. This single number decides whether the planner walks an index or reads the whole table.

Guessing how many rows come back — selectivity

The formula needs $N$ , the number of rows processed, but the planner does not know it before running. So it keeps statistics on each column — a histogram of the value distribution, a list of most-common values, the number of distinct values — and uses them to estimate selectivity: the fraction of rows a condition lets through.

\hat{N} = N_{\text{total}} \times s_1 \times s_2 \times \cdots

(2)

That is: start from the total row count and multiply by each condition's pass-through rate. Each $s_i$ is the selectivity of the $i$ -th condition, between 0 and 1.

Multiplying means assuming the conditions are independent of one another. When they are strongly correlated — state = 'NY' and city = 'Brooklyn' — the product wildly underestimates the row count. The planner picks an index expecting a handful of rows, hundreds of thousands come back, and every one of them costs a random read. This is the single most common shape of a slow query.

Join orders explode combinatorially

Adding tables makes the problem hard fast. For $n$ tables, the number of possible orders in which to combine them grows on the order of $n!$ — six ways for three tables, over three million for ten.

FIG 1Every table you add multiplies the number of candidate join orders. Past about ten, simply trying them all stops being an option

And order alone changes runtime by orders of magnitude. Joining a 10-row table with a 10-million-row table, narrowing first and then continuing is nothing like joining the two large tables first — the number of rows carried through the middle is completely different.

Avoiding the full search — dynamic programming

Classic planners (the lineage starts with IBM's System R) use dynamic programming. Find the best way to read each single table; then the best plan for each pair; then use those to build the best plan for each triple, and so on. The key property is that the best plan for a large set can be assembled from the best plans of its subsets. No subproblem gets solved twice, so $n!$ collapses into filling in $2^n$ subsets once each.

FIG 2Dynamic programming — leaving subproblem answers in a table and reusing them. The figure shows edit distance, but the fill order, building bigger answers out of smaller optimal ones, is exactly what the planner does over join orders

The idea itself is covered in Dynamic Programming From Scratch. Even so, $2^n$ is exponential, so once the number of tables being joined reaches geqo_threshold (default 12), PostgreSQL gives up on the exact answer and switches to a genetic search. Past that line, the plan can differ from run to run.

Stage 4: the executor pulls from the top

The chosen plan is a tree of operators: table reads at the leaves, filters, joins, aggregates and sorts stacked above, the final result at the root. In the classic iterator model, every operator exposes the same three entry points: open, next, close.

class Filter:
    def __init__(self, child, pred):
        self.child, self.pred = child, pred

    def next(self):
        while (row := self.child.next()) is not None:
            if self.pred(row):
                return row          # hand up one qualifying row
        return None                 # child exhausted

Calling next() on the root calls next() on its child, which calls its own child, and a single row travels back up. Because rows are pulled from below only as needed, a LIMIT 10 does not force a read of ten million rows, and no stage has to hold its entire intermediate result in memory.

The weakness is that every row pays for a chain of function calls. At a hundred million rows that is a hundred million calls per level, and the call overhead outweighs the real work. Modern engines therefore pass batches of a thousand rows instead of one, or compile the plan to machine code on the fly. Both are after the same thing: the cache- and branch-friendly shapes described in When Big-O and Your Benchmarks Disagree.

The three ways to join

Nested loop join — for each row on the left, search the right side. Fastest when the right side has an index and the left side is a few rows. Catastrophic when the left side is large
Hash join — build an in-memory hash table from the smaller side, then stream the larger side through once. Strong for equality joins when one side fits in memory
Merge join — sort both sides on the join key and walk them in step. Cheap when the inputs already arrive sorted

Most "it suddenly got slow" incidents are a row estimate drifting until a hash join turns into a nested loop. A loop written for a handful of rows now runs hundreds of thousands of times.

Stage 5: storage, pages, and the log

At the bottom, data lives in pages — fixed-size blocks, commonly 8 KB or 16 KB. Even to read one byte you read the whole page, because that is the granularity the disk works in. Pages you read stay in the buffer pool, an in-memory cache (shared_buffers in PostgreSQL), so the next access skips the disk entirely. Most of a database's performance comes down to whether the pages you need are already sitting there.

Writes have an ordering problem: lose power midway through rewriting a page and the data is corrupt. The fix is write-ahead logging (WAL) — record what you are about to do in an append-only log and make that durable first, then update the real pages later. After a crash, replaying the log restores consistency, and because the log is only ever appended, it is cheap compared to scattered writes.

For readers racing writers, most databases use MVCC (multi-version concurrency control): instead of overwriting a row, write a new version of it. Readers keep seeing the version that was current when their transaction started, so readers and writers never wait on each other. The price is accumulated dead versions, which need a collector (VACUUM in PostgreSQL).

How pages are organized into trees and updated is the subject of the companion article, B-Trees and LSM-Trees.

How this shows up on the job

Who needs it, and when. An application developer told that "one screen is weirdly slow." An SRE chasing a spike in database CPU. A data engineer whose nightly batch no longer finishes by morning. The shared insight is that the query is not slow — the plan is.

The first command to run. In PostgreSQL, EXPLAIN (ANALYZE, BUFFERS) <query>. Adding ANALYZE actually executes it and prints both the estimated and the actual row counts. Look for exactly one thing: an order-of-magnitude gap, like rows=1000 next to actual rows=800000. Every operator above the one that is off is built on that error. The equivalents are EXPLAIN ANALYZE in MySQL and the execution plan display in SQL Server.

Knobs you actually turn. work_mem (memory available for sorts and hash tables; too little spills to disk), random_page_cost (lowering the 4.0 default is routine on SSD), shared_buffers, default_statistics_target (histogram granularity, default 100), effective_cache_size. Refresh statistics with ANALYZE; find the slow queries with pg_stat_statements.

Traps that cause real incidents.

work_mem is not per query. It is allocated per sort or hash operator, and again per parallel worker. Raise it and then let connections pile up, and you exhaust memory
Wrapping a column in a function disables its index. WHERE date(created_at) = '2026-08-26' cannot use an index on created_at. Rewrite it as a range condition, or build an index on the expression
Stale statistics cause overnight slowdowns. Right after a bulk load or a mass delete, the planner still believes the old distribution. Run ANALYZE explicitly after batch jobs
A deep OFFSET still reads everything it throws away. OFFSET 100000 LIMIT 20 reads 100,000 rows and discards them. Switch to keyset pagination: "20 rows with a key greater than the last one on the previous page"
The N+1 problem is not fixable by the planner. Ten thousand single-row queries are ten thousand round trips no matter which plan each one gets. That is an application design issue

The interview version. "Why isn't my index being used?" There are four paths: the predicate transforms the column so it no longer matches the index's shape; selectivity is high enough that a full scan is genuinely cheaper; statistics are stale and the selectivity estimate is wrong; or a type mismatch is forcing an implicit conversion. You separate them by comparing estimated and actual rows in EXPLAIN.

Summary

SQL is an order ticket. The recipe is not written down, so the database chooses it
The parser builds a tree, the rewriter reshapes it safely, the planner picks by cost, the executor runs it, storage does the reading and writing
Cost is estimated rows times unit prices — and when the row estimate is wrong, every plan decision above it is wrong too
When something is slow, look for the order-of-magnitude gap between estimated and actual rows

Next we go inside stage 5 — how pages are arranged into trees so that lookups and updates can both be fast — in B-Trees and LSM-Trees.