How a Database Executes a Query: Parsing, Planning, and Optimization from SQL String to Result Set

Most engineers use SQL every day and have a rough mental model of what happens when a query runs: the database “finds” the rows and returns them. That model is good enough until the day a query that should be fast is slow, an index you added does nothing, or EXPLAIN ANALYZE output looks completely different from what you expected. At that point, the rough model fails.

This article walks through the complete lifecycle of a SQL query in PostgreSQL, from the raw text string to the final result set. Understanding each stage gives you a concrete mental model for reading execution plans, writing queries that the optimizer can actually help with, and debugging performance problems that are otherwise opaque.

Stage 1: Lexing and Parsing

When you call client.query("SELECT ...") from a TypeScript application, the database receives a byte string over the wire. The first thing that happens is lexical analysis: the query string is tokenized into a flat list of lexemes. Keywords (SELECT, FROM, WHERE), identifiers (table names, column names), operators, literals, and punctuation are each assigned a token type.

The token stream is then fed into a parser, which uses a grammar to build an abstract syntax tree (AST). The AST represents the grammatical structure of the query as a tree of nodes. For a simple query like SELECT u.name FROM users u WHERE u.id = $1, the tree has a SelectStmt node at the root, with child nodes for the target list (u.name), the from clause (users u), and the where clause (u.id = $1).

PostgreSQL’s parser is a modified version of the standard bison grammar. It rejects queries that are syntactically invalid at this stage, but it has no knowledge of your schema: it does not yet know whether users is a real table or whether name is a column on it.

The parser operates in roughly O(N) time relative to query string length. For all practical application queries, this phase is negligible.

Stage 2: Semantic Analysis and Catalog Binding

The parse tree is passed to the analyzer (sometimes called the semantic analysis phase), which resolves names against the catalog, PostgreSQL’s metadata store. The catalog holds definitions for tables, columns, types, functions, indexes, constraints, and statistics.

During this phase:

• Table references are resolved to concrete OIDs (object identifiers). users becomes OID 16384 or whatever it is in your database.
• Column references are bound to specific table columns with their data types. Ambiguous column names raise an error here.
• Function calls are resolved to specific implementations (important for overloaded functions).
• Type coercions are inserted where needed. If you compare an integer column to a string literal, a cast is added to the tree.

The output of the analyzer is a query tree: the same structure as the parse tree, but with all symbolic names replaced by catalog-resolved references. This tree is what gets passed to the optimizer.

This stage also applies rewrite rules. PostgreSQL supports view expansion here: if a table reference is actually a view, the view’s definition is substituted in-place before planning. This is why queries against views look more complex in EXPLAIN output than you might expect.

Stage 3: Query Planning and Optimization

This is where most of the interesting work happens. The planner’s job is to take the query tree and produce a plan tree: a tree of physical operator nodes that, when executed, produce the correct result rows. The same query can be executed by many different physical plans, and the difference in cost between the worst plan and the best plan can be orders of magnitude.

PostgreSQL’s planner operates in two phases: rule-based transformation first, then cost-based selection.

Rule-Based Transformations

Before estimating costs, the planner applies algebraic equivalences that are always beneficial:

• Predicate pushdown: move WHERE conditions as close to the data source as possible. A filter on users.created_at > '2025-01-01' should be evaluated at the table scan level, not after joining with three other tables.
• Subquery flattening: uncorrelated subqueries in WHERE clauses (WHERE id IN (SELECT user_id FROM orders)) are often converted to joins, which the cost-based optimizer can reason about more effectively.
• Constant folding: expressions like WHERE price * 100 > 5000 that can be simplified at plan time are simplified.

Cost-Based Optimization

After transformations, the planner enumerates candidate plans and estimates the cost of each using statistics stored in pg_statistic. These statistics are collected by ANALYZE (or autovacuum) and include:

• Row counts per table
• Column value histograms showing the distribution of values
• Most-common values and their frequencies
• Correlation between column order and physical storage order

Costs are expressed in arbitrary units, where 1.0 represents the cost of fetching one page from disk sequentially. seq_page_cost defaults to 1.0; random_page_cost defaults to 4.0, reflecting the higher cost of random I/O (though on SSDs you often want to lower this to 1.1 or 1.5 with SET random_page_cost = 1.1).

The total cost of a plan node is (startup_cost, total_cost). Startup cost is the cost before the first row can be returned (a sort node has high startup cost because it must consume all input before producing output). Total cost covers the full result.

For a query joining two tables, the planner considers:

• Which table to scan first (the “outer” relation)
• Which join algorithm to use
• Whether to use indexes, and which ones

For queries joining many tables, exhaustive enumeration becomes combinatorially expensive. PostgreSQL uses dynamic programming for up to join_collapse_limit tables (default: 8), and switches to a genetic algorithm (GEQO) for larger queries.

Stage 4: Join Algorithm Selection

The planner selects the join algorithm based on cost estimates. There are three main algorithms, each with different characteristics.

Nested Loop Join

For each row in the outer (driving) relation, scan the inner relation and find matching rows. If the inner relation has an index on the join key, each lookup is an index scan rather than a full sequential scan.

// ORM query that maps to a nested loop
const orders = await db
  .select()
  .from(ordersTable)
  .innerJoin(usersTable, eq(ordersTable.userId, usersTable.id))
  .where(eq(usersTable.email, 'alice@example.com'));

// PostgreSQL plan (EXPLAIN output):
// Nested Loop
//   -> Index Scan on users (email = 'alice@example.com')  [outer, 1 row]
//   -> Index Scan on orders using orders_user_id_idx      [inner, seek per outer row]

When the outer relation is very small (filtered down to a handful of rows), nested loop with an inner index scan is the fastest possible plan. The inner index is seeked once per outer row, and each seek is O(log N).

Hash Join

The smaller relation is scanned once to build an in-memory hash table keyed on the join column. The larger relation is then scanned once, and each row is probed against the hash table.

// ORM query likely to produce a hash join
const result = await db
  .select({ userName: usersTable.name, totalSpend: sum(ordersTable.amount) })
  .from(ordersTable)
  .innerJoin(usersTable, eq(ordersTable.userId, usersTable.id))
  .groupBy(usersTable.name);

// PostgreSQL plan:
// Hash Aggregate
//   -> Hash Join (hash cond: orders.user_id = users.id)
//         -> Seq Scan on orders    [probe side, larger]
//         -> Hash
//              -> Seq Scan on users [build side, smaller]

Hash join is preferred when both relations are large and neither has a useful index on the join key. Startup cost is non-trivial (must build the hash table), but total cost scales with O(N + M) rather than O(N * M).

The hash table must fit in work_mem. If it spills to disk (a “batched” hash join), performance degrades significantly. You can observe this in EXPLAIN ANALYZE via Batches: N where N > 1. Increasing work_mem per session before expensive joins is a standard tuning technique.

Merge Join

Both relations are sorted on the join key, then a single linear pass merges them. If both inputs are already sorted (via an index scan in sorted order, or because a sort was already needed for ORDER BY), merge join can be very efficient.

// Force merge join visibility in EXPLAIN
// SET enable_hashjoin = off; SET enable_nestloop = off;
// Then re-run and observe Merge Join node

// Typical scenario: both sides already ordered
const result = await db
  .select()
  .from(eventsTable)
  .innerJoin(sessionsTable, eq(eventsTable.sessionId, sessionsTable.id))
  .orderBy(eventsTable.sessionId); // same key as join

Algorithm	Best Case	Worst Case	Memory	Requires Index	Sort Input
Nested Loop	Small outer + indexed inner	Large cross product	O(1)	Preferred on inner	No
Hash Join	Large unsorted relations	Hash spills to disk	O(min(N,M))	Not required	No
Merge Join	Pre-sorted inputs	Explicit sort of both inputs	O(1) after sort	Not required	Yes

Stage 5: Scan Type Selection

For each table in the query, the planner decides how to access the rows.

Sequential Scan

Read every page of the table from start to finish. PostgreSQL uses a ring buffer for sequential scans so they do not pollute the buffer pool. Sequential I/O is fast (the OS can read-ahead), and for queries returning a large fraction of a table, sequential scan is almost always faster than index scan.

Index Scan

Use a B-tree (or other index type) to find matching row pointers, then fetch the heap pages for those rows. Each heap fetch is a random I/O. For highly selective predicates (fetching 0.1% of rows), index scan wins decisively. For low-selectivity predicates (fetching 30% of rows), the random I/O cost of following many heap pointers exceeds the cost of a sequential scan.

The threshold in PostgreSQL is roughly 5-15% of rows, depending on random_page_cost, the correlation statistic for the column, and actual data layout. The planner uses the histogram and most-common-values statistics to estimate selectivity.

Index-Only Scan

If all columns referenced by the query (both in SELECT and WHERE) are covered by the index, PostgreSQL can return rows directly from the index without fetching heap pages at all. This requires the visibility map to confirm that all pages are all-visible (i.e., no dead tuples that might affect MVCC visibility). VACUUM keeps the visibility map current.

// This query can use an index-only scan if there is a covering index on (user_id, amount)
const total = await db
  .select({ total: sum(ordersTable.amount) })
  .from(ordersTable)
  .where(eq(ordersTable.userId, userId));

// CREATE INDEX orders_user_id_amount_idx ON orders(user_id, amount);
// EXPLAIN output: Index Only Scan using orders_user_id_amount_idx

Bitmap Index Scan

A middle path between index scan and sequential scan. PostgreSQL first uses the index to build a bitmap of heap pages that contain matching rows, then reads those pages in order (converting random I/O to near-sequential I/O). For medium-selectivity predicates or queries using multiple indexes combined with AND/OR logic, bitmap scan is often the winner.

Scan Type	Selectivity Sweet Spot	Heap Fetches	I/O Pattern	Visibility Map Required
Sequential Scan	>15% of rows, or no index	All pages	Sequential	No
Index Scan	<5% of rows	One per matching row	Random	No
Index-Only Scan	<5% of rows	None (when possible)	Index sequential	Yes
Bitmap Scan	5-20% of rows	Batched by page	Near-sequential	No

Stage 6: The Volcano Iterator Execution Model

Once the planner produces a plan tree, the executor evaluates it using the Volcano model (also called the iterator model or pipeline model). Each operator node in the plan implements three methods: Init(), GetNext(), and Close().

GetNext() is called on the root node by the executor. Each node calls GetNext() on its children to pull the next tuple. This propagates down the tree until a leaf node (a scan) reads a row from disk or the buffer pool and returns it upward. Operators like filters, projections, and aggregates transform or buffer tuples as they flow up.

Hash Aggregate (GetNext: drain hash table)
  └─ Hash Join (GetNext: probe hash table)
        ├─ Seq Scan on orders (GetNext: next heap page row)   [probe side]
        └─ Hash (Init: build hash table from child)
              └─ Seq Scan on users (GetNext: fully consumed during Hash Init)

The key property of the Volcano model is pull-based pipelining: rows flow one at a time from producers to consumers without materializing full intermediate results. This keeps memory usage low for most queries.

There are exceptions. Sort nodes must consume their entire input before returning the first row (high startup cost). Hash join must build the full hash table before probing. These are called pipeline-breaking operators, and they are visible in EXPLAIN output as nodes with non-zero startup cost.

PostgreSQL also supports parallel query execution via parallel workers. The planner can insert Gather or Gather Merge nodes that collect rows from multiple parallel workers, each executing a portion of the plan on a subset of heap pages.

Stage 7: Buffer Pool I/O

No row read by any scan actually comes directly from disk during execution. All I/O goes through the shared buffer pool (shared_buffers, default 128MB, typically set to 25% of RAM in production). The buffer pool is a fixed-size cache of 8KB pages, managed with a clock-sweep eviction algorithm.

When a scan needs a page:

1. The buffer pool manager checks whether the page is already in the pool.
2. If it is (a cache hit), the page is pinned and returned immediately.
3. If it is not (a cache miss), a free buffer frame is selected (evicting an unpinned page if necessary), the page is read from disk into the frame, and then returned.

Sequential scans use a smaller ring buffer (256KB by default) rather than the main shared buffer pool. This prevents large sequential scans from evicting hot pages that other queries need, a property called scan resistance.

Writes go through the buffer pool too. Modified pages are marked dirty and flushed to disk by background writer processes and during checkpoints. WAL (Write-Ahead Log) ensures durability before any dirty page is flushed.

The hit rate of your buffer pool is visible via pg_stat_bgwriter and pg_statio_user_tables. A hit rate below 95% on a production system usually indicates shared_buffers is too small for your working set.

Reading EXPLAIN ANALYZE

Putting it together, here is how you trace a TypeScript ORM query through the execution stages using EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT):

// Raw EXPLAIN for a Drizzle query
const explained = await db.execute(sql`
  EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
  SELECT u.name, COUNT(o.id) AS order_count
  FROM users u
  INNER JOIN orders o ON o.user_id = u.id
  WHERE u.created_at > '2025-01-01'
  GROUP BY u.name
`);

console.log(explained.rows[0]['QUERY PLAN']);

The output reads bottom-up (leaf nodes first). For each node, pay attention to:

• actual rows vs estimated rows: a large discrepancy (10x or more) means stale statistics. Run ANALYZE users or ANALYZE orders.
• actual time: per-loop execution time. Multiply by loops to get total time for inner nodes.
• Buffers hit / read: hit = buffer pool; read = disk. High read counts on hot paths indicate the working set exceeds shared_buffers.
• rows removed by filter: a large number here means the scan is reading far more rows than it needs, often curable with an index.

Production Considerations

Statistics freshness: The cost-based optimizer is only as good as its statistics. Default autovacuum settings are conservative. For high-write tables, consider ALTER TABLE orders SET (autovacuum_analyze_scale_factor = 0.01) to trigger ANALYZE after 1% row changes rather than the default 20%.

work_mem tuning: Each sort or hash operation per query per connection can use up to work_mem. On a server with 200 connections each running complex queries, the total memory can reach 200 * N * work_mem where N is the number of pipeline-breaking operators. Set work_mem conservatively globally and increase it per session for known-expensive queries.

random_page_cost on SSDs: The default value of 4.0 causes the planner to systematically over-prefer sequential scans and under-prefer index scans on SSD storage where random I/O cost is close to sequential. Setting random_page_cost = 1.1 gives the optimizer an accurate picture of actual I/O costs and often fixes mysterious missing-index plans.

Partial and covering indexes: If your most common query pattern filters on status = 'pending' and only a small fraction of rows are in that state, a partial index (CREATE INDEX ON orders(created_at) WHERE status = 'pending') is far smaller and more cache-efficient than a full index. Covering indexes (using INCLUDE to add non-key columns) enable index-only scans for common projection patterns without bloating the key.

Cardinality estimation for multi-column predicates: The planner estimates selectivity for multiple WHERE conditions independently and multiplies the estimates, which underestimates selectivity when columns are correlated. Extended statistics (CREATE STATISTICS orders_stats (dependencies) ON user_id, status FROM orders) teach the optimizer about column correlations and dramatically improve estimates for queries that filter on correlated columns.

The Full Picture

A SQL query travels through six distinct processing stages before a single row is returned to your application:

1. Lexing and parsing: string to AST
2. Semantic analysis: AST to catalog-bound query tree, with view expansion
3. Rule-based transformation: predicate pushdown, subquery flattening
4. Cost-based planning: join order, join algorithm, scan type selection using statistics
5. Volcano execution: pull-based row iteration through the plan tree
6. Buffer pool I/O: all page access mediated through the shared buffer cache

When a query is slow, the failure is almost always in stage 4 (bad plan due to stale statistics or missing statistics for correlated columns) or in stage 6 (insufficient buffer pool, excessive disk reads, or a hash join spilling to disk). EXPLAIN ANALYZE exposes both. Understanding what each number in that output corresponds to in the execution pipeline is what separates engineers who can debug query performance from those who just add indexes and hope.