# Chapter 4: Query Planning & Execution
## 4.0 - Query Planning & Operations (The Strategy of Execution)
<img src="assets/arch_chap_3_lunch_rush_chef.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
When a query arrives, Postgres transforms from a storage engine into a processing pipeline. The engine translates parsed SQL into a physical execution plan. This plan is a sequence of low-level operators—scans, joins, and aggregations—that retrieve the requested data.
The transition from declarative intent to imperative execution is the most critical phase of query performance. A well-chosen plan minimizes I/O and CPU usage.
### What You'll Learn
- Why the **Plan Search Space** explodes combinatorially with query complexity
- How the **Query Optimizer** evaluates join orderings, scan types, and index choices
- The difference between a declarative SQL request and its imperative execution plan
- Why sub-optimal plan selection is the single most common source of production-query slowness
### The Chapter Map
Because this is the most complex machine in the engine, we will approach it in three phases. The chapter teaches a representative set of nodes on the narrative path; exhaustive node cards remain available through the linked **Operations Field Guide** and are optional on a first reading.
1. **Phase 1: The Decision (4.1–4.2)** — How the Planner calculates cost and builds an algebraic execution tree ("How Postgres decides").
2. **Phase 2: Representative Operators (4.3–4.6)** — The physical mechanics of the scans, joins, aggregates, and memory operations needed to reason about unfamiliar plans ("What Postgres does").
3. **Phase 3: Special Cases (4.7–4.10)** — Mutation paths, Parallelism, CTEs, and the art of Sargability ("How Postgres handles complexity").
In **[[Manuscript/03 - Access Paths & Indexing/3.0 - Indexes (The Mighty Indexes)|Chapter 3]]**, we built a library of access paths. Now, the engine must choose between multiple execution strategies. Having a hundred shortcuts is useless if you don't know which one to take.
### The Declarative Riddle
SQL is a **Declarative** language. Unlike imperative programming, the client provides an **Intent** rather than a recipe.
When a user submits a complex query—like finding the names of all animals who are waiting for a 'Pending' order—they are stating a **"What"**:
```sql
SELECT DISTINCT a.name
FROM animals a
JOIN orders o ON a.id = o.animal_id
JOIN animal_favorites af ON a.id = af.animal_id
JOIN dish_ingredients di ON af.ingredient_id = di.ingredient_id
JOIN dishes d ON di.dish_id = d.id
WHERE d.name = 'Capybara''s Delight'
AND o.status = 'Pending';
```
The user does not say, "Consult the index for 'Capybara's Delight' or 'Join these tables first'." That would be **Imperative** instruction. Because the user only specifies the result, the engine must navigate a complex search space of execution plans to fulfill the request.
### The Plan Search Space
As queries grow more complex, the number of ways to fulfill the order explodes. For the five-table join above, the engine must solve several crucial decisions:
1. **The Entry Point (Selectivity)**: Do we start with the singular "Capybara's Delight" dish (high selectivity) or the 'Pending' orders (potentially millions)?
2. **The Join Order**: In a 5-table join, there are **120 possible permutations** ($5!$) of join orders. Some might take 1 millisecond; others might take 1 hour.
3. **The Join Type**: Should we use a **Hash Join** (building an in-memory hash table), a **Merge Join** (sorting both lists first), or a **Nested Loop** (walking one list for every item in the other)?
In a high-concurrency environment, a sub-optimal plan can lead to a system-wide stall. A plan that takes 1 hour instead of 1 millisecond is an $O(N^2)$ disaster.
This is why Postgres employs the **Query Optimizer (The Planner)**. It analyzes the declarative "What" of the request and calculates the most efficient imperative "How." Its goal is to find the lowest-cost execution path through the **Plan Search Space**.
> [!TIP]
> The **`EXPLAIN`** command is your primary window into the planner's mind. It reveals the chosen plan nodes, estimated costs, and row counts before the query is actually executed.
---
## 4.1 - Query Planner (The Blueprint of Execution)
<img src="assets/arch_planning_ledger.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
Before execution begins, the **Query Planner** selects the most efficient physical path for the query. Whether it chooses a **[[Operations/Table/SeqScan|Sequential Scan]]** or an **[[Manuscript/03 - Access Paths & Indexing/3.1 - B-Tree (The Balanced Bookshelf)|Index Scan]]**, the planner relies on an internal **Cost Model** grounded in the physical reality of system resources.
The planner evaluates potential plans based on their total estimated cost—a dimensionless value representing the resource consumption required to retrieve the data.
> [!NOTE] The Planner Writes the Executor's Work Order
> **Concept**: The planner does not execute your SQL. It writes a C-struct tree of execution instructions.
> **Payoff**: When you run `EXPLAIN`, you aren't running the query; you are looking at the raw instruction node tree generated by the planner. The executor simply takes this tree, walks it node by node, and asks each node: *"Give me the next tuple."*
The query planner operates as part of a multi-stage translation pipeline:
$\text{SQL Query} \longrightarrow \text{\textbf{Parser}} \text{ (Syntax Check)} \longrightarrow \text{\textbf{Analyzer}} \text{ (Catalog Resolution)} \longrightarrow \text{\textbf{Planner}} \text{ (Path Costing)} \longrightarrow \text{\textbf{Executor}} \text{ (Tuple Retrieval)}$
### The Hierarchy of Slowness
The planner optimizes for execution time by minimizing I/O and CPU cycles. To understand its decisions, you must understand the performance characteristics of modern hardware.
If we scale a single **L1 Cache Reference (1.5 nanoseconds)** to **1.5 seconds**, the physical hierarchy looks like this:
| Action | Latency (Physics) | Human Scale (1ns = 1s) | Planner Cost |
| :--- | :--- | :--- | :--- |
| **L1 Cache Reference** | 1.5 ns | 1.5 Seconds | `0.01` (`cpu_tuple_cost`, default) |
| **Branch Mispredict** | 5 ns | 5 Seconds | — |
| **L2 Cache Reference** | 7 ns | 7 Seconds | — |
| **Main Memory Reference** | 100 ns | **2.6 Minutes** | `1.0` (`seq_page_cost`, default)* |
| **SSD Random Read** | 150,000 ns | **2.7 Days** | `2.1` (Tuned SSD) |
| **Disk Seek (HDD)** | 10,000,000 ns | **115 Days** | `4.0` (`random_page_cost`, default) |
| **WAN (CA to Netherlands)** | 150,000,000 ns | **5.7 Years** | — |
*\*Note: In Postgres, `seq_page_cost` includes the memory trip plus the CPU overhead of requesting the page from the OS.*
### The Planner's Cost Model
In the physical world, a disk seek is significantly slower than a CPU cycle. The Planner’s **Cost Model** uses several tunable constants to estimate query overhead:
- **`cpu_tuple_cost` (0.01)**: The default cost of processing one row in memory.
- **`seq_page_cost` (1.0)**: The cost of reading an adjacent page from disk.
- **`random_page_cost` (4.0)**: The cost of a non-sequential seek.
> [!TIP]
> **Tuning for the Modern Era**: The default `4.0` for random reads is conservative for modern NVMe SSDs. A measured setting such as `random_page_cost = 2.1` tells the planner that random access is less punitive and can unlock more aggressive indexing strategies. Treat the number as a hardware hypothesis to benchmark, not a universal SSD constant.
> [!CAUTION] Planner Experiments Are Not Runtime Simulation
> Three different laboratory techniques appear in this book. Cost constants such as `random_page_cost` alter the planner's **hardware assumptions**. `enable_*` settings discourage a plan family so that one operator can be isolated for teaching. Synthetic `pg_class.reltuples` and `relpages` values alter the planner's **belief about scale** without creating real rows or latency. Every forced example is labeled, uses session-local settings where possible, and should be reset before interpreting ordinary plans.
The planner relies on table statistics to generate accurate cost estimates. If these statistics are outdated, the engine might select a sub-optimal access method—such as scanning a large table to retrieve a single row.
### Table Statistics (`ANALYZE`)
Postgres periodically gathers statistics about the data in each table. You can trigger this process manually to ensure the planner has up-to-date information:
```sql
-- Updating the planner's statistics
ANALYZE animals;
-- Inspecting Selectivity and Correlation
SELECT n_distinct, correlation, most_common_vals, most_common_freqs
FROM pg_stats
WHERE tablename = 'animals' AND attname = 'species_id';
```
### The Math of Selectivity ($s$)
The planner uses these statistics to calculate **Selectivity ($s$)**—the fraction of rows expected to pass a filter ($0 \le s \le 1$).
- **Low Selectivity ($s \approx 0.9$)**: If Postgres knows 90% of your animals are 'Capybaras', the plan for `WHERE species_id = 5` will likely be a **Sequential Scan**. Why? Because reading nearly every page sequentially is cheaper than jumping back and forth with an index (Random I/O).
- **High Selectivity ($s \approx 0.001$)**: A search for a rare species results in a tiny **Cardinality**. For a small number of rows, the Index Scan's random I/O penalty is worth the shortcut.
> [!NOTE]
> **A note on terminology**: some texts flip "high" and "low" selectivity. We use the convention that *high selectivity* means the predicate selects a small fraction of rows (a highly selective filter is a strict one); *low selectivity* means it lets most rows through.
### Physical Correlation
The most subtle variable in the planner's ledger is **Correlation**. This represents the relationship between the physical storage order on disk and the logical value of the column. Postgres records it in `pg_stats.correlation` as a value between $-1.0$ and $+1.0$.
> [!IMPORTANT]
> **The Index Decision**: If data is physically ordered by the index key (correlation $\approx +1.0$), an Index Scan is fast. Consecutive index entries point to physically adjacent heap pages. If the correlation is near $0.0$, an Index Scan becomes a high-latency random I/O operation. In this case, the planner may prefer a Sequential Scan even for a small number of rows.
For the deep mathematical specs on these cost constants, see **[[Manuscript/06 - Resource Management & Processes/6.0 - Memory & Disk (The Hierarchy of Inertia)|Chapter 6 - The Hunger of Resources]]**.
---
### 🧪 Manipulation Lab: Planner Lies (Skewed Data)
We will create a table with highly skewed data, observe the planner make a wrong estimate due to missing statistics, and then run `ANALYZE` to see the estimate corrected.
#### The Setup
Connect to the database and create a table. Disable autovacuum on it so Postgres does not automatically analyze it in the background:
```sql
CREATE TABLE skew_test (val INT);
ALTER TABLE skew_test SET (autovacuum_enabled = false);
-- Insert 10,000 rows: 9,990 of value 1, and 10 of value 2
INSERT INTO skew_test SELECT 1 FROM generate_series(1, 9990);
INSERT INTO skew_test SELECT 2 FROM generate_series(1, 10);
```
#### The Task
1. Query the execution plan for the rare value `2` before gathering statistics:
```sql
EXPLAIN SELECT * FROM skew_test WHERE val = 2;
```
The table has never been analyzed. Postgres knows the table size from the operating system files but has no details about column value distributions. It uses a default heuristic estimate, assuming there are `57` rows of value `2`.
2. Run `ANALYZE` to build the statistics profile:
```sql
ANALYZE skew_test;
```
3. Query the plan again:
```sql
EXPLAIN SELECT * FROM skew_test WHERE val = 2;
```
#### ANALYZE Corrects 57 Rows to 10
Notice that after running `ANALYZE`, the planner's estimate corrected from `rows=57` to the exact value of `rows=10`. The cost calculation updated accordingly (from `188.44` to `170.00`).
#### Fresh Statistics Prevent Blind Scan Choices
The query planner is a statistician, not a fortune-teller. It relies on up-to-date data distributions stored in `pg_statistic`. If your table has stale statistics, the planner's estimates will be wrong, leading to catastrophic physical scan decisions in production.
```sql
-- Clean up
DROP TABLE skew_test;
```
---
## 4.2 - Query Algebra (The Execution Tree)
<img src="assets/arch_plan_algebra_summary.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
The Query Optimizer has finalized the plan—it has performed its economic calculus and selected the cheapest path. But a cost estimate is not a result set. To turn a blueprint into reality, Postgres must translate those mathematical expectations into physical execution.
Execution is performed by a tree of specialized **Plan Nodes**. Leaf and intermediate nodes can fetch, filter, join, sort, aggregate, modify, or reshape tuples under the executor's demand-driven interface.
### The Demand-Driven Iterator Model (The Pull Model)
To understand the Execution Engine, you must understand the **Demand-Driven Iterator Model**. Every node in the tree implements a standard interface with a single critical method: `ExecProcNode()` (commonly thought of as `GetNext()`).
The parent node (the root) calls this method on its child. That child, in turn, calls it on its own children. This demand-driven "Pull" mechanism ensures that no record is processed until it is requested by the node above it.
> [!IMPORTANT]
> **The Execution Checkpoint**: Think **pull**. A parent requests a tuple and its child performs enough work to answer. Some nodes—such as a full sort or hash build—must consume substantial input before returning their first row, and initialization plans can run before the main tree produces output.
This demand model is visible with **[[Operations/ResultSet/Limit|LIMIT]]**. Once `Limit` has enough rows, it requests no more. A streaming child may therefore stop early; a blocking child such as `Sort` may already have consumed all of its input, so `LIMIT` does not guarantee little work.
```sql
EXPLAIN (COSTS OFF)
SELECT a.name, o.order_time
FROM orders o
JOIN animals a ON a.id = o.animal_id
WHERE o.status = 'Pending'
ORDER BY o.order_time DESC
LIMIT 5;
```
A simplified form of the resulting node tree is both an execution plan and a chain of requests:
```text
Limit
-> Nested Loop
-> Index Scan Backward using idx_orders_order_time on orders o
Filter: (status = 'Pending')
-> Index Scan using animals_pkey on animals a
Index Cond: (id = o.animal_id)
```
Read downward to follow demand: `Limit` asks the `Nested Loop` for a row, which asks the order index for the newest pending order and then looks up its animal. Read upward to follow results: the two scans supply a joined tuple to the loop, and the loop returns it to `Limit`. Once five tuples arrive, `Limit` makes no sixth request, so the index scan does not walk the rest of `orders`.
The execution tree is composed of three primary node categories:
1. **[[Manuscript/04 - Query Planning & Execution/4.3 - Scans (The Full Table Walk)|Scans]]**: The source operators that fetch tuple from the tables.
2. **[[Manuscript/04 - Query Planning & Execution/4.4 - Joins (The Pairing Dance)|Joins]]**: The operators who cross-reference data between different tables.
3. **[[Manuscript/04 - Query Planning & Execution/4.5 - Aggregations (The Running Receipt)|Aggregations]]**: The operators who sort, group, and summarize the results.
### Performance Economics
Every execution node has costs, but only certain memory-intensive operations use **`work_mem`** as a base limit. Sorts, hashes, materialization, and related nodes may spill to temporary files when their effective budget is insufficient; scans use the shared buffer and operating-system cache path described in Chapter 6.
> [!TIP]
> **The Tuple Table Slot**: Moving data between millions of nodes is expensive. To avoid unnecessary memory copying, Postgres uses a **Tuple Table Slot**. This is a unified memory structure that carries a single "tuple" (tuple) between nodes, allowing different operations to examine the same data without relocating it in memory.
Furthermore, even the best-organized plan runs into concurrency bottlenecks. In **[[Manuscript/07 - Wait Events & Concurrency/7.0 - Why Slow Queries Lie (The Waiting Game)|Chapter 7]]**, we will observe nodes competing for the same resources (Locks) or waiting for data to return from the storage layer (I/O Wait).
`EXPLAIN (ANALYZE, BUFFERS)` produces a **Service Receipt** with estimates, actual rows, loops, elapsed node timing, and buffer/temp activity. It does not directly decompose each node into exact CPU and wait time; Chapter 7 adds operating-system and wait evidence for that question.
---
## 4.3 - Scans (The Full Table Walk)
<img src="assets/ex_scan_raccoon_flashlight.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
Before processing can occur, Postgres must fetch raw data from physical storage. This is the responsibility of the **Scan Nodes**.
With the planner's decision framework established, we can now examine the individual operators it chooses from. We start with the most fundamental: how does Postgres physically retrieve rows from a table?
**Scan Nodes** are the usual entry points to heap, index, foreign, or function-produced rows. Heap and index access uses **[[Manuscript/06 - Resource Management & Processes/6.2 - Shared Buffers (The Page Cache)|Shared Buffers]]** and the operating-system cache; a miss may reach storage. Other nodes can also perform I/O—for example, a sort or hash can spill to temporary files, and modification nodes dirty relation pages.
### The Universal Scan Interface (`ExecScan`)
Despite the difference between walking a table heap and traversing a B-Tree, every Scan Node in Postgres shares a common internal blueprint: **`ExecScan`**.
This standardized interface allows the Query Algebra to operate consistently regardless of the underlying access method. This abstraction is extended by the **Table Access Method (Table AM)** API, which allows the storage layer to be pluggable.
### Sequential Scan: Linear Page Access
The **[[Operations/Table/SeqScan|Sequential Scan]]** is the base case of data retrieval. Postgres performs a linear walk of the entire table heap, read-ahead buffer-by-buffer, to ensure 100% visibility of all qualifying tuples.
> [!TIP]
> **Synchronized Sequential Scans**: If multiple queries perform a sequential scan on the same large table, Postgres avoids redundant I/O. A new query can share the scan state of an existing one, looping back to the beginning once the end of the table is reached.
### Index Scan: Non-Linear Point Access
The **[[Operations/Index/IndexScan|Index Scan]]** utilizes the maps created in Chapter 3 to bypass the linear scan. Postgres traverses the B-Tree to find the exact coordinates of the required tuples and performs a direct, non-linear fetch from the table heap.
### 🧪 Index the Child-Side Foreign Key — Lab
**Count Orders Containing Dish #5**: "Count every order that contains Dish #5."
#### The Naive Assumption
Foreign keys ensure integrity, but PostgreSQL does **not** automatically create an index on the referencing columns. The `order_items` table has a composite primary key `(order_id, dish_id)`. It is naturally ordered for “everything in order N,” while `dish_id` alone is a poor match for a conventional leading-key probe. PostgreSQL 18 can sometimes use B-tree skip scan on a later column when the leading column has few distinct values, but a dedicated `dish_id` index remains the predictable access path for this workload.
```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) FROM order_items WHERE dish_id = 5;
```
#### The Fallout
With no usable index for `dish_id`, the planner falls back to a **Parallel Seq Scan**, sweeping all 300,000 rows across multiple workers:
#### The Lazy Fix
Add the missing index on the foreign-key column. The query collapses to an **Index Only Scan**, reading only 29 buffers instead of 1,622.
```sql
CREATE INDEX idx_order_items_dish_id ON order_items(dish_id);
```
### Bitmap Scan: The Reservation Map
Suppose the engine needs to fetch 50 rows scattered across different pages of a massive table.
An **Index Scan** may perform many scattered index and heap-buffer accesses. A **Sequential Scan** visits the table's heap pages in physical order. Which path performs less real I/O depends on correlation, visibility, cache state, selectivity, and storage—not merely on the number of matching rows.
The **Bitmap Scan** is a two-phase middle ground:
1. **[[Operations/Index/BitmapIndexScan|Bitmap Index Scan]]**: Postgres first scans the index and builds a **Bitmap**—an in-memory bitmask of all pages that contain matching records.
2. **[[Operations/Index/BitmapAndBitmapOr|Bitmap And / Or]]**: If the query has multiple filters, Postgres can combine these bitmaps using bitwise logic.
3. **[[Operations/Page/BitmapHeapScan|Bitmap Heap Scan]]**: The engine then visits the matching pages in physical order. By retrieving pages sequentially, it avoids the overhead of random I/O.
### EXPLAIN: The Smart Lap
When you see a Bitmap Scan in your execution plan, you are seeing Postgres transition from "Point Searching" to "Bulk Retrieval."
> [!NOTE]
> **The Small Table Paradox**: For tiny tables, the planner often prefers a **Sequential Scan** because reading a few heap pages and filtering can cost less than traversing an index plus visiting the heap. Statistics, cache assumptions, ordering requirements, and query shape can still change that choice.
```sql
-- Searching for all animals in two specific species
-- (Forced Index Scan for demonstration)
SET enable_seqscan = off;
EXPLAIN SELECT * FROM animals WHERE species_id = 1 OR species_id = 5;
```
> [!NOTE]
> **The Recheck Condition**: Bitmaps are stored in **`work_mem`**. If the target set is too large to fit in memory, the bitmap becomes "Lossy" and marks whole pages instead of individual rows. Postgres must then "Recheck" the condition for every row on those pages to confirm they match the query criteria.
### 🧪 Combine Broad Predicates with a Bitmap Scan — Lab
**Count Recent Pending or Cancelled Orders**: "Count all orders that are either Pending or Cancelled, placed since 2021."
#### The Naive Solution
When you use an `OR` condition across multiple values, the engine cannot rely on a single, clean B-tree traversal. It reverts to its "in-memory scratchpad" strategy.
```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) FROM orders
WHERE status IN ('Pending', 'Cancelled')
AND order_time >= '2021-01-01';
```
#### The Fallout
Postgres builds an in-memory checklist (a bitmap) of matching rows before visiting the heap.
1. **`Bitmap Index Scan`**: Postgres builds an in-memory checklist (1s and 0s) of matching rows.
2. **`Bitmap Heap Scan`**: The engine visits the table heap in physical disk order, following the checklist. This is faster than random I/O but more flexible than a sequential scan.
### Efficiency Planning
To understand the Planner's decisions, we must look at the **Estimated Cost**. The planner assigns a cost value to every operation.
**The Sequential Fetch (The Default Walk):**
```sql
EXPLAIN SELECT * FROM ingredients WHERE category = 'Herb';
```
**The Index Fetch (The Point Search):**
```sql
-- Forced Index Scan
SET enable_seqscan = off;
EXPLAIN SELECT * FROM ingredients WHERE id = 12;
```
**State 3: Index-Only Scan (Heap Avoidance)**
If the index map already contains all the data requested, Postgres avoids visiting the table heap entirely.
```sql
-- Forced Index Only Scan
SET enable_seqscan = off;
SET enable_bitmapscan = off;
EXPLAIN SELECT id FROM ingredients WHERE id < 100;
```
> [!IMPORTANT]
> **The Visibility Map (VM)**: An Index-Only Scan is not a guarantee. Because indexes do not store **MVCC (Visibility)** information, the engine must consult the **Visibility Map**. If the VM confirms the page is "clean," the fetch is successful. Otherwise, it must visit the heap.
Notice that for our tiny `ingredients` table, the **Seq Scan (cost=2.40)** is actually "cheaper" than the **Index Scan (cost=9.17)**! Postgres is smart—it knows that for a small table, it doesn't need a map to find data.
### 🧪 Avoid Heap Visits with a Covering Index — Lab
**Count Orders for the First 50 Animals**: "For the first 50 animals, show their name and how many orders each has placed."
#### The Naive Solution
The default index contains only the `animal_id`. The engine uses it to find the orders, but it must then visit the heap to retrieve the `id` for the count—triggering thousands of random heap fetches.
```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT a.name, count(o.id)
FROM animals a
JOIN orders o ON a.id = o.animal_id
WHERE a.id < 50
GROUP BY a.name;
```
#### The Fallout
The inner `Index Scan` visits the heap for every matching order, consuming 588 buffers:
#### The Lazy Fix
A **Covering Index** uses the `INCLUDE` clause to carry extra columns in index leaf tuples. It can enable an **Index Only Scan**; pages not marked all-visible still require heap visibility checks.
```sql
CREATE INDEX idx_orders_animal_covering
ON orders(animal_id) INCLUDE (id);
```
The buffer count drops from 588 to 148, and the scan becomes `Index Only Scan` with `Heap Fetches: 0`. The question was answered without ever opening the heap.
### Core Scan Cards
These five cards are the main-road vocabulary: whole-table scan, ordinary index lookup, covering lookup, bitmap construction, and batched heap access. The companion **Grand Operations Field Guide** (`Operations/_Operations.md`) retains the specialist cards for CTE, function, subquery, foreign/custom, table-function, TID, sample, and values scans without turning this chapter into a catalog.
![[Operations/Table/SeqScan]]
![[Operations/Index/IndexScan]]
![[Operations/Index/IndexOnlyScan]]
![[Operations/Index/BitmapIndexScan]]
![[Operations/Page/BitmapHeapScan]]
---
## 4.4 - Joins (The Pairing Dance)
<img src="assets/arch_sous_chefs_joins.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
After fetching tuples, the engine must **Join** them. Join Nodes cross-reference two distinct streams of data to produce a single result set.
Postgres utilizes three primary Join algorithms: **Nested Loop**, **Hash Join**, and **Merge Join**. The planner selects the algorithm based on row counts, index availability, and the sorted state of the data.
> [!IMPORTANT]
> **The Join Pull**: Remember the **[[Manuscript/04 - Query Planning & Execution/4.2 - Query Algebra (The Execution Tree)|Pull Model]]**! The join node doesn't just start mashing rows. It waits for the station above it to request a partner. Only then does it reach into its child nodes.
The **[[Operations/ResultSet/NestedLoop|Nested Loop Join]]** requests matching inner rows for each outer row. The inner side may be a full scan, a parameterized index probe, a materialized result, or another subtree; “scan the whole inner table every time” is only its worst shape.
This algorithm has a worst-case complexity of $O(N \times M)$. The planner typically selects it when the Outer relation is small or the Inner relation has an index that allows for fast point lookups.
### 🧪 Fetch Each Animal's Top Three Items — Lab
**Return Three Items per Frequent Animal**: "Show me the top 3 items for every animal that has placed more than 15 orders."
#### The Naive Solution
A global window-function formulation may rank a much larger candidate set before filtering. A `LATERAL` formulation can instead make the “top N” lookup parameterized by each animal, provided a matching index and selective outer input exist.
#### The Lazy Fix
Use a **LATERAL Join**. This allows Postgres to iterate over the animals and, for each one, perform a surgical, indexed-backed lookup of exactly three items.
```sql
SELECT a.name, top_dishes.dish_id
FROM animals a
CROSS JOIN LATERAL (
SELECT oi.dish_id
FROM orders o
JOIN order_items oi ON o.id = oi.order_id
WHERE o.animal_id = a.id
LIMIT 3
) top_dishes
WHERE (SELECT count(*) FROM orders WHERE animal_id = a.id) > 15;
```
**A Bounded Nested Loop**: The plan shifts to a **Nested Loop**. Instead of a massive sort, Postgres fetches exactly what it needs for each animal and stops.
### The Hash Join
Imagine you need to join a tiny lookup table of just 10 species records to a massive, completely unindexed table of 10 million animal patron check-ins. If the database executes a Nested Loop Join, it will have to loop through the 10 species and scan the 10-million-row table sequentially 10 times—amounting to 100 million rows read. If it tries to sort the 10 million rows to align them, the sort will spill to disk and take minutes. Yet, Postgres executes this query in under a second. How does the engine resolve a join across millions of unindexed records in a single, fast pass?
> [!IMPORTANT] Predict How to Join Without an Index
> If you have no indexes, how can you compare 10 rows to 10 million rows without scanning the 10 million rows multiple times or sorting them? Pause and formulate a guess.
You might expect that Postgres must build a temporary B-Tree index on the fly, or load both tables entirely into memory to match them. Creating an index on 10 million records is slow, and reading 10 million rows into memory can exceed the buffer cache and cause out-of-memory crashes.
Instead, Postgres resolves this using a **Hash Join** (referencing the internal **[[Operations/ResultSet/HashJoin|Hash Join]]** algorithm).
Rather than searching or sorting the massive table, the engine builds a lookup shortcut on the fly:
1. **The Build Phase**: Postgres reads the tiny 10-row table (the "Inner" relation) and constructs a **Hash Table** in its private working memory (`work_mem`).
2. **The Probe Phase**: It streams rows from the other input and hashes each join key to find candidate buckets. Average in-memory bucket lookup is close to constant time, but collisions, batches, expression cost, and result multiplicity still matter.
In this example the build side is small, so the hash table fits comfortably. The probe side is consumed once by this join node, but its child may serve rows from memory, storage, or another operation. If the build state exceeds its effective memory budget (`work_mem × hash_mem_multiplier`), PostgreSQL can batch through temporary files.
### 🧪 Follow the Join Cascade — Lab
**Count Deliveries Feeding Dish 5**: "Count all deliveries for ingredients used in 'Dish 5'."
#### The Fallout
A non-sargable predicate (like `lower(name)`) at the top of a join chain can poison the planner's choice of join order all the way down.
```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*)
FROM dishes d
JOIN dish_ingredients di ON d.id = di.dish_id
JOIN ingredients i ON di.ingredient_id = i.id
JOIN supply_deliveries sd ON i.id = sd.ingredient_id
WHERE lower(d.name) = 'dish 5';
```
An ordinary index on the unmodified column cannot directly support a `lower(column)` equality. Depending on statistics and available paths, the planner may choose hashes or other joins over a broad candidate set. A matching expression index or normalized/case-insensitive data design can restore an indexed path where it is useful.
#### The Lazy Fix
By using a sargable predicate (`WHERE d.name = 'Dish 5'`), the planner is willing to push that filter into an index scan. The join order flips: Postgres starts with the single dish and walks the index "conveyor belt" to find the ingredients and deliveries, avoiding the heavy hash tables entirely.
> [!IMPORTANT]
> **Multi-batch Hash Joins**: If the Hash Table exceeds the available **[[Manuscript/06 - Resource Management & Processes/6.3 - Work Mem (Private Working Memory)|work_mem]]**, Postgres partitions the data into **Batches** on disk. It processes one batch at a time, spilling the rest to temporary files. This ensures query completion at the cost of high Disk I/O.
If both data streams are pre-sorted by the join key, Postgres deploys the **[[Operations/ResultSet/MergeJoin|Merge Join]]**.
Two cursors move through sorted inputs in join-key order. Duplicate-key groups can require mark/restore or materialization behavior. Once inputs are in the required order, the merge phase is linear in the input rows plus emitted matches; obtaining that order may require indexes or expensive sorts, and memory usage is workload-dependent.
### 🧪 Reconcile Deliveries and Orders by Date — Lab
**Count Dates Shared by Deliveries and Orders**: "Count how many days we received a delivery on the exact same day an order was placed."
#### The Fallout
Joining 100,000 orders to deliveries is massive. If you use `to_char()` to join by date string, you destroy any inherent ordering in the data. Postgres must materialize and sort millions of derived strings into temporary files on disk.
#### The Lazy Fix
Using native datetime geometry (`date_trunc`) allows the engine to compare physical bits. If the data is indexed, the engine can deploy a **Merge Join**.
Postgres marches down the two sorted lists, counting matches as it goes, without ever building a monolithic hash table.
### 🧪 Find Animals with No Orders — Lab
**Count Animals That Never Ordered**: "Find the count of animals who have never placed an order."
#### The Naive Solution
The `NOT IN` trap is a classic. If the subquery returns even a single `NULL`, the entire query returns zero results. Because of these semantics, Postgres often falls back to a slow **Sequential Scan** with a subplan filter.
#### The Lazy Fix
Use `NOT EXISTS`. It has cleaner semantics and allows Postgres to use a **Hash Anti Join** or an **Index Anti Join**.
```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) FROM animals a
WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.animal_id = a.id);
```
**A One-Pass Anti-Join**: Postgres uses a **Hash Right Anti Join**, scanning the orders table once to build a hash table, and then checking animals against it in a single pass.
### The Decision: Selecting a Join Type
Let's observe how the planner chooses a Join algorithm based on table scale and statistics.
##### 1. Small Result Set Join (Nested Loop)
When joining a single record to a small set of related entities, a Nested Loop makes the repeated inner lookup explicit. This controlled example narrows the request to two relations so the complete plan remains legible:
```sql
BEGIN;
SET LOCAL enable_hashjoin = off;
SET LOCAL enable_mergejoin = off;
SET LOCAL enable_bitmapscan = off;
-- Planner-only synthetic scale for the indexed inner relation.
-- The transaction rollback restores the real catalog statistics.
UPDATE pg_class
SET reltuples = 100000, relpages = 5000
WHERE oid = 'dish_ingredients'::regclass;
EXPLAIN (ANALYZE, COSTS, BUFFERS, VERBOSE)
SELECT d.name, di.quantity_grams
FROM dishes d
JOIN dish_ingredients di ON d.id = di.dish_id
WHERE d.id = 5;
ROLLBACK;
```
> [!TIP]
> **Minimal Iteration Overhead**: The cost is low because the Outer relation (Dishes) is filtered to a single row. The Join is effectively reduced to a few pointer dereferences.
> [!NOTE] Synthetic Scale + Controlled Operator Demonstration
> The catalog update makes the tiny fixture *look* like a large inner relation to the planner; it creates no rows or latency. The three `enable_*` settings then isolate the ordinary `Nested Loop → Index Scan` silhouette. Everything is transaction-local and rolled back immediately. Because `EXPLAIN ANALYZE` still executes the real 2,000-row table, its estimated and actual rows intentionally disagree. Never update `pg_class` this way outside a disposable planner lab.
##### 2. The Strategy Shift (Hash Join vs. Nested Loop Join)
When joining a large table like `supply_deliveries`, the planner's choice depends on the availability of indexes and the estimated output volume.
###### Plan 1: Unindexed Join (Hash Join)
Without a specific index on the join key in a large table, Postgres must construct an in-memory Hash Table to avoid a Cartesian product explosion.
```sql
EXPLAIN SELECT ingredients.name, supply_deliveries.delivery_time
FROM ingredients
JOIN supply_deliveries ON ingredients.id = supply_deliveries.ingredient_id
WHERE ingredients.id < 10;
```
###### Plan 2: Indexed Join (Nested Loop)
Once an index is added (`CREATE INDEX idx_supply_ingredient ON supply_deliveries(ingredient_id);`), the plan shifts. Postgres can now iterate through `ingredients` and perform a fast index lookup for each match in `supply_deliveries`.
```sql
CREATE INDEX IF NOT EXISTS idx_supply_ingredient ON supply_deliveries(ingredient_id);
BEGIN;
SET LOCAL enable_hashjoin = off;
SET LOCAL enable_mergejoin = off;
SET LOCAL enable_bitmapscan = off;
EXPLAIN (ANALYZE, COSTS, BUFFERS, VERBOSE)
SELECT ingredients.name, supply_deliveries.delivery_time
FROM ingredients
JOIN supply_deliveries ON ingredients.id = supply_deliveries.ingredient_id
WHERE ingredients.id < 10;
ROLLBACK;
```
> [!NOTE] Why Disable Bitmap Scans Here?
> With many deliveries per ingredient, PostgreSQL may organically batch the heap visits as a `Bitmap Heap Scan`. This lab disables bitmap scans only to expose the repeated ordinary B-Tree probe performed by the inner side of a Nested Loop. The audit preserves both the forcing settings and the literal resulting plan.
##### 3. The Sorted Join (Merge Join)
If both input streams are pre-sorted (typically by an Index Scan on a B-Tree), the planner selects a Merge Join for $O(N+M)$ efficiency.
```sql
BEGIN;
SET LOCAL enable_hashjoin = off;
SET LOCAL enable_nestloop = off;
EXPLAIN (ANALYZE, COSTS, BUFFERS, VERBOSE)
SELECT ingredients.id, supply_deliveries.id
FROM ingredients
JOIN supply_deliveries ON ingredients.id = supply_deliveries.ingredient_id
ORDER BY ingredients.id;
ROLLBACK;
```
Here both B-Trees already supply join-key order, so the literal plan needs no explicit `Sort`: an `Index Only Scan` and an `Index Scan` feed the `Merge Join` directly. The disabled alternatives are transaction-local teaching constraints.
### Core Join Cards
These three strategies are the core join vocabulary. Read each card as a diagnostic reference after learning the decision: nested loops favor cheap repeated probes, hash joins build an equality lookup, and merge joins consume compatible order.
![[Operations/ResultSet/NestedLoop]]
![[Operations/ResultSet/HashJoin]]
![[Operations/ResultSet/MergeJoin]]
---
## 4.5 - Aggregations (The Running Receipt)
<img src="assets/arch_prep_station.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
Once raw tuples have been fetched and joined, a later stage of the query algebra may summarize the resulting stream. In PostgreSQL, this is the responsibility of **aggregate nodes**.
These nodes are the "summarizers" of the database—responsible for the `SUM`, `COUNT`, and `GROUP BY` logic. They work by iteratively applying a **Transition Function ($S_{func}$)** to a **Transition State ($S_{trans}$)** in memory until every tuple in the group has been processed.
Let's see how the aggregation node summarizes our data.
#### 1. HashAggregate: The Memory-Intensive Lookup
If the incoming data is unsorted, Postgres utilizes a **HashAggregate** node. It builds a **Hash Table** in memory where every unique grouping key becomes a bucket. Each bucket stores the current **Transition State** for that group. As tuple stream through, $S_{func}$ is executed to update the state in the corresponding bucket.
```sql
-- Squashing 10 million individual deliveries into totals per ingredient
EXPLAIN SELECT ingredient_id, sum(quantity_kg)
FROM supply_deliveries
GROUP BY ingredient_id;
```
> [!TIP]
> **The Memory Limit**: the success of a HashAggregate depends entirely on **[[Manuscript/06 - Resource Management & Processes/6.3 - Work Mem (Private Working Memory)|work_mem]]**. If the number of unique groups is so large that the Hash Table exceeds the allocated memory, the engine must "spill to disk"—writing intermediate buckets to temporary files, which dramatically increases execution time.
#### 2. GroupAggregate: The Streaming Summary
If the data arrives in grouping-key order (from a Sort or a compatible index path), PostgreSQL can use a **GroupAggregate**. It can maintain the current group's transition state and emit a group when its key changes. Whether this wins overall depends on the cost of obtaining that order, group count, aggregate state size, and possible parallel paths; it is not inherently faster than `HashAggregate`.
```sql
-- The ingredients arrive already prepped (sorted)
CREATE INDEX idx_supply_ingredient ON supply_deliveries(ingredient_id);
EXPLAIN SELECT ingredient_id, sum(quantity_kg)
FROM supply_deliveries
GROUP BY ingredient_id;
```
> [!TIP]
> **Streaming Efficiency**: A **GroupAggregate** can avoid a hash table with one entry per group, but aggregate transition states and upstream sorting can still consume significant memory. `EXPLAIN (ANALYZE, BUFFERS)` shows which bargain the chosen plan made.
#### 3. WindowAgg: The Peer Review
A **Window Function** allows you to perform calculations across a set of rows that are related to the current row, without collapsing them into a single group. The **WindowAgg** node is responsible for this logic.
### 🧪 Rank the Three Largest Deliveries per Quarter — Lab
**Return the Quarterly Top Three**: "Give me the top 3 largest deliveries per quarter."
#### The Naive Solution
Using `row_number() OVER (PARTITION BY ...)` is standard, but the partition key determines how the engine groups data.
```sql
SELECT id, quantity_kg,
row_number() OVER (PARTITION BY extract(quarter from delivery_time) ORDER BY quantity_kg DESC) as rank
FROM supply_deliveries
ORDER BY rank LIMIT 3;
```
#### The Fallout
Because `EXTRACT` is dynamic, the **WindowAgg** node forces an expensive **Sort** of all deliveries in memory. If your `work_mem` is small, this will spill to disk.
#### The Lazy Fix
Replacing `extract(quarter ...)` with `date_trunc('quarter', ...)` changes calendar semantics—not the fundamental need to order rows for this window. A useful repair is to index an immutable expression that matches the partition and ordering keys, restrict the date range, or materialize a quarter key when the workload justifies it. Confirm the resulting path with `EXPLAIN`; a syntactic rewrite alone does not remove the sort.
#### 3. The Execution Stop (Limit)
This is Postgres's most effective method for resource conservation. If the query only requires a subset of the data, the **Limit** node halts the upward flow of tuples once the threshold is met.
```sql
EXPLAIN SELECT * FROM supply_deliveries LIMIT 1;
```
Notice the **Estimated Cost**. Even though the child node (the Sequential Scan) has a total cost of 1,845 points, the **Limit** node knows it only needs the first tuple. Because of the **Volcano Model**, Postgres pulls exactly one record and then terminates the downstream requests, resulting in a negligible execution cost.
### Core Aggregate Cards
![[Operations/ResultSet/Aggregate]]
![[Operations/ResultSet/WindowAgg]]
---
## 4.6 - Memory Operations (Sort, Hash, and Spill)
<img src="assets/ex_memory_ops_frog_sort.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
Once the raw ingredients have been gathered (Scans), paired (Joins), and perhaps summarized (Aggregations), the engine still has to prepare the final presentation. This is the memory-bound stage of the query algebra—the stage where the engine organizes, truncates, and combines intermediate results into the final set returned to the client.
Operations in this layer deal with ordering, truncation, and set math. Unlike relation scans, they consume data streams passed up from lower nodes. They can still perform I/O: sorts, hashes, materialization, and related nodes may read and write temporary files when their working data exceeds memory.
> [!WARNING]
> **The Memory Limit (Spill to Disk)**: Nodes such as `Sort` and `Hash` are common consumers of **`work_mem`**. This setting is a base limit per operation, not one allocation per connection or even one allocation per query. If an operation exceeds its effective limit, PostgreSQL may use temporary files, adding I/O to a node that never reads a heap relation directly.
You can observe the distinction with `EXPLAIN (ANALYZE, BUFFERS)`: relation access appears as shared or local blocks, while a spill reports temporary blocks and, for sorts, a disk-based sort method. Scan nodes are the usual entry points to table and index data; they are not the only nodes capable of storage I/O.
### Ordering and Truncation
The most common logistical operations are `ORDER BY` and `LIMIT`. These tell the engine to organize the results into a specific sequence and to stop processing once a certain count is reached.
![[Operations/ResultSet/Sort]]
![[Operations/ResultSet/Limit]]
> [!TIP]
> **The Top-N Sort Optimization**: If you ask for `ORDER BY price DESC LIMIT 10`, Postgres doesn't sort the entire multi-million row table. It uses a specialized memory structure called a "Top-N Heapsort" to keep track of only the top 10 items as it scans, saving massive amounts of `work_mem` and time.
### Set Operations and Unions
Sometimes a query brings together separate logic trees—for instance, a `UNION` combining two menu searches. `Append`, `Merge Append`, and `SetOp` concatenate, preserve order across, or perform set semantics on those inputs. Their detailed cards live in the companion **Grand Operations Field Guide**.
### Materialization and Uniqueness
When a complex subquery result needs to be referenced multiple times, the engine will "plate" it in a temporary memory space so it doesn't have to be recalculated. Similarly, if the query requires `DISTINCT` results, the engine must filter out identical rows.
![[Operations/ResultSet/Materialize]]
![[Operations/ResultSet/Hash]]
`Unique` and `ProjectSet` remain in the field guide. These operations may be fast, but large `Sort`, `Hash`, and materialization work can spill to temporary files, generating I/O and extending execution time.
---
## 4.7 - Mutation Path (The Write Pipeline)
<img src="assets/ex_mutation_axolotl_stamp.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
Everything we have discussed so far in the query algebra—Scans, Joins, Aggregations, and Memory operations—has been purely observant. The engine has been reading indices, scanning heap pages, and organizing results without altering the source data.
Everything above described the read path — how Postgres finds and combines data. The write path is a different machine with different constraints.
But databases are not just read-only archives. Eventually, the application must **Modify the State** of the system.
In Postgres, mutation is handled as just another node at the very top of the execution tree. The lower nodes figure out *which* tuple need to be updated or deleted, and they pass those physical addresses up to the **ModifyTable** node, which actually applies MVCC visibility system (MVCC) rules.
### The ModifyTable Node
This is the workhorse of all `INSERT`, `UPDATE`, and `DELETE` operations. It takes the result set from the children and applies the changes to the physical pages.
![[Operations/Tuple/ModifyTable]]
> [!IMPORTANT]
> **The Hidden Reads**: An `UPDATE` or `DELETE` must first identify target rows, so scan and join paths can dominate. The mutation itself can also be expensive through row locking, constraint checks, triggers, index maintenance, WAL generation, and dirty-page work. Diagnose both halves instead of assuming the scan is always responsible.
>
> **Index Your Writes**: Just like a `SELECT`, an `UPDATE` that searches by a function will trigger a full Sequential Scan. You can use **Functional Indexes** to create high-speed shortcuts for your mutation queries.
### 🧪 Make the Cleanup Predicate Sargable — Lab
**Unblock the Nightly Cleanup Job**: "The nightly cleanup job is taking too long and locking up the system."
#### The Naive Solution
Every `UPDATE` is a hidden `SELECT`. If the application wraps the filter in a function, the engine loses its shortcut and falls back to a full Seq Scan, holding row locks for far too long.
```sql
UPDATE orders
SET status = 'Cancelled'
WHERE extract(year from order_time AT TIME ZONE 'UTC') = 2025;
```
#### The Fallout
Wrapped in `extract()`, the index is useless. The planner reads the entire 100K-row `orders` table just to find the few rows it needs to update.
#### The Lazy Fix
Build a map shaped exactly like the application's blind spot: a **Functional Index**.
```sql
CREATE INDEX idx_orders_year
ON orders( (EXTRACT(year FROM order_time AT TIME ZONE 'UTC')) );
```
### Concurrency and Locking
What happens if two backend processes try to update the exact same ingredient tuple at the exact same time? The engine must orchestrate a queue so they don't overwrite each other. Before a mutation can occur, the engine may need to acquire a lock on the specific row.
### 🧪 Trace Locks Through a Bulk Price Update — Lab
**Mark Up Every Spiced Dish by 10%**: "Apply a 10% price markup to all dishes that contain 'Spice'."
#### The Fallout
Because `lower()` forces a full pass to find matching dishes, the **ModifyTable** node is fed a fat, slow pipeline of rows. This operation will lock rows unpredictably and block other concurrent writes.
```sql
UPDATE dishes SET price = price * 1.10
WHERE id IN (
SELECT d.id FROM dishes d
JOIN dish_ingredients di ON d.id = di.dish_id
JOIN ingredients i ON di.ingredient_id = i.id
WHERE lower(i.category::text) = 'spice'
);
```
#### The Lazy Fix
Remove the unnecessary `lower()` cast and compare the enum directly. This makes the category predicate compatible with a suitable access path, but the final plan depends on table sizes and available indexes. PostgreSQL locks rows it actually updates; lock duration lasts until transaction end, not merely for a microscopic executor moment.
![[Operations/Tuple/LockRows]]
### The Result Node (Simple Inserts)
Sometimes, there is no need to scan anything. A simple `INSERT INTO ingredients VALUES ('Saffron')` does not have a child scan node because there's nothing to search for. Instead, the planner generates a trivial `Result` node that hands the hardcoded values directly to `ModifyTable`.
![[Operations/Tuple/Result]]
When mutations occur, PostgreSQL may create tuple versions, maintain affected indexes, check constraints and triggers, generate WAL, and dirty buffers. The cost depends on the changed columns, index set, tuple layout, and transaction context; mutation is not one universal "heaviest" operation.
While a single backend process can meticulously update every record in a shipment, some tasks are simply too large for one worker. When the scale of the scan or the weight of the mutation becomes a mountain, Postgres calls for reinforcements.
---
## 4.8 - Parallel & Distributed (The Worker Pool)
<img src="assets/ex_parallel_pigeon_team.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
Every client query has a leader backend, and many plans run entirely there. When a plan is parallel-safe and the planner expects the benefit to exceed coordination cost, PostgreSQL can request parallel workers for eligible portions of the tree.
To speed this up, Postgres can split the work. The planner decides the scan is large enough to justify coordination overhead, so the primary backend (the **leader**) spawns several **Parallel Workers** to divide the labor.
### Gathering the Results
Workers return tuples to the leader through shared-memory queues. A `Gather` node may accept rows in arbitrary worker order; `Gather Merge` preserves a required sort order while merging worker streams. The card below covers the latter.
![[Operations/ResultSet/GatherMerge]]
> [!TIP]
> **Parallel Overheads**: Worker setup, tuple transfer, memory, and leader participation all cost time. `min_parallel_table_scan_size` contributes to path eligibility, but no single threshold decides the plan, and requested workers may be unavailable at execution time. Measure the actual plan and worker counts.
### Optional Extension Track: Distributed Architectures
Multi-node extensions and services can spread data across servers, but their plan nodes and semantics are not PostgreSQL-core contracts. The examples below describe Citus-style concepts and depend on the tested extension version.
A query might need to read from several nodes simultaneously. Instead of passing data through shared memory, nodes exchange tuples over the network. The planner introduces specific distributed operations to route the data efficiently.
The companion **Grand Operations Field Guide** contains the versioned `Broadcast`, `Redistribute`, and distributed `Gather` cards. Keep those distinct from PostgreSQL core's `Gather` and `Gather Merge` nodes.
Both local parallelism and distributed execution divide work, but their failure, transaction, network, placement, and consistency costs differ. Treat the similarity as a visual analogy, not an implementation equivalence.
---
## 4.9 - Common Table Expressions (The Temporary Station)
<img src="assets/arch_cte_station.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
A **Common Table Expression (CTE)** names an auxiliary statement that can be referenced by a larger SQL statement. A CTE does not imply one universal execution strategy: PostgreSQL can fold eligible CTEs into the parent query or execute them separately and expose the result through a **CTE Scan**.
The syntax creates a logical unit. The planner decides whether that boundary remains physical, subject to the CTE's contents, reference count, and explicit `MATERIALIZED` or `NOT MATERIALIZED` instruction.
### Folding or Materializing in PostgreSQL 18
In PostgreSQL 18, a non-recursive, side-effect-free CTE is normally **folded into the parent query when referenced once**. That allows joint optimization and predicate pushdown. When such a CTE is referenced more than once, PostgreSQL normally materializes it so repeated references can share one result.
You can request separate evaluation with `MATERIALIZED`, or request folding with `NOT MATERIALIZED` when semantics allow it. Materialization can serve as an **optimization fence**, but it can also prevent a selective parent filter from reaching the underlying scan. `NOT MATERIALIZED` may duplicate expensive computation when the CTE is referenced repeatedly, so neither choice is a universal optimization.
```sql
-- Normally folded because it is side-effect-free and referenced once.
EXPLAIN (COSTS OFF)
WITH recent AS (
SELECT * FROM supply_deliveries
)
SELECT * FROM recent WHERE id = 1;
-- A deliberate physical boundary that produces a CTE Scan.
EXPLAIN (COSTS OFF)
WITH recent AS MATERIALIZED (
SELECT * FROM supply_deliveries
)
SELECT * FROM recent WHERE id = 1;
```
### 🧪 Trace Ingredient Lineage Recursively — Lab
**Follow a Dish Through Its Supply Chain**: "Trace a dish's ingredient lineage all the way down the supply chain."
#### The Naive Solution
Using `WITH RECURSIVE` enables graph traversal. Recursive CTEs are evaluated through a working table and are not folded like an eligible one-use `SELECT` CTE. Adding a non-sargable string cast outside the recursion also prevents the base relation from using a normal integer-key condition.
```sql
WITH RECURSIVE supply_chain AS (
SELECT id, ingredient_id FROM supply_deliveries
UNION ALL
SELECT sd.id, sd.ingredient_id FROM supply_deliveries sd
JOIN supply_chain sc ON sd.id = sc.id + 1
)
SELECT * FROM supply_chain sc
WHERE sc.id::text = '1';
```
#### The Fallout
PostgreSQL can generate the broad recursive result before the outer filter discards most of it. You will see a **`WorkTable Scan`**—the executor reading the intermediate working table to feed another recursion step. Depending on size and memory pressure, intermediate work can also use temporary storage; “in memory” is not guaranteed.
#### The Lazy Fix
Push the exact filter directly into the base case (the "anchor" query) of the CTE.
```sql
WITH RECURSIVE supply_chain AS (
SELECT id, ingredient_id FROM supply_deliveries WHERE id = 1
UNION ALL
-- ...
```
By filtering early, the engine only ever prepares the specific slice of data it needs, keeping the CTE scan clean and fast.
### Operation Ledger
![[Operations/Other/CTEScan]]
---
## 4.10 - Sargability (The Art of Not Opening Every Box)
<img src="assets/arch_sargability_safe_map.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
### The Disabled Index
Imagine a B-tree index on `name`. `WHERE name = 'Saffron'` can become an index condition when the operator and collation match. `WHERE lower(name) = 'saffron'` asks about a derived value that the plain index does not store, so that index usually cannot supply the condition. PostgreSQL may choose a sequential scan and evaluate the function for candidate rows; blocks can come from cache or storage. Why did the expression change the usable access path?
> [!IMPORTANT] Predict Whether the Index Can See the Expression
> If the B-Tree index on `name` is physically present on disk, why can't the engine use it to find `lower(name)`? Pause and formulate a guess.
You might expect that Postgres should be smart enough to convert the index search automatically, or that wrapping the column in a function doesn't change the underlying sorting order of the tree. But a function can transform values arbitrarily (e.g. `hash(name)` or `length(name)`), scrambling their physical order.
Instead, Postgres B-Trees are sorted by raw, physical column values using specific **Operator Classes** (`opclass`). For example, a B-Tree on a `TEXT` column uses the standard `text_ops` class, which defines how to evaluate `<`, `>`, and `=`.
When you query `WHERE lower(name) = 'saffron'`:
1. The engine is no longer comparing raw name strings; it is comparing derived results.
2. The index does not store `lower(name)`; it stores `name`.
3. Without a matching expression index or another usable predicate, the plain `name` index cannot directly position the scan by `lower(name)`. The planner compares the remaining paths and may choose a sequential scan.
We call predicates that can become useful index conditions **sargable** (Search ARGument-ABLE). A function does not doom a predicate forever: a matching expression index and compatible operator can make the derived value searchable. The real question is whether an available access method can turn the predicate into a scan key.
Sargability earns the planner an option, not an order. It will still choose the index only when the avoided work is worth the traversal and heap visits. A predicate can also be pushed close to its base relation and filter early without becoming an index condition. For repeated searches on a stable function result, an expression index such as `CREATE INDEX ON dishes (lower(name))` stores the value the query is asking for.
### The Decision Chain: Selectivity and Join Order
Selectivity and available access paths both influence plan construction. The **[[Manuscript/04 - Query Planning & Execution/4.1 - Query Planner (The Blueprint of Execution)|Planner]]** estimates rows so it can compare candidate trees.
- **Direct or statistically represented expression**: PostgreSQL can use column statistics, expression-index statistics, or extended statistics on supported expressions to improve its estimate. It may still prefer another path.
- **Unrepresented expression**: The planner falls back to the selectivity information available to the operator or function, sometimes including a default estimate. Errors here can flow into join order and algorithm choices; the join type alone is not the diagnosis.
There is no secret "play it safe with a sequential scan" switch. PostgreSQL costs the paths it can construct using the beliefs it has.
---
The index path wins only when its avoided work exceeds tree traversal and heap-access costs.
### 🧪 Move Arithmetic Off the Indexed Column — Lab
**Find Deliveries Due Before 2024**: "Show all deliveries that were technically due before New Year's 2024, after accounting for a one-day processing buffer."
#### The Fallout
Math on the column side prevents the index from being used. Adding an interval to the column forces Postgres to compute a new value for every row before it can compare anything.
```sql
SELECT count(*) FROM supply_deliveries
WHERE delivery_time + interval '1 day' < '2024-01-01';
```
The planner reverts to a **Seq Scan** because the engine cannot push arithmetic into the B-Tree map.
#### The Lazy Fix
Isolate the column. Move the arithmetic to the constant on the right-hand side. The planner now has a sargable predicate it can hand straight to the index.
```sql
SELECT count(*) FROM supply_deliveries
WHERE delivery_time < '2024-01-01'::timestamptz - interval '1 day';
```
---
### Optimization: Predicate Pushdown
Sargability is the fuel for **Predicate Pushdown**. When the Planner identifies a sargable filter, it can "push" that logic as deep as possible into the execution tree. This minimizes the volume of data that must be joined and sorted by higher-level nodes.
**Scenario**: Find all ingredients used in "Dish 5".
#### State 1: The Express Assembly (Sargable Pushdown)
If we use a sargable filter (`WHERE d.id = 5`), the Query Optimizer pushes the ID filter down to the lowest level.
```sql
-- ✅ The Express Assembly
EXPLAIN SELECT * FROM ingredients i
JOIN dish_ingredients di ON i.id = di.ingredient_id
JOIN dishes d ON di.dish_id = d.id
WHERE d.id = 5;
```
The illustration is a **focused excerpt**, not the complete three-table tree. It shows the decisive access-path change: the equality predicate reaches the composite primary key as a `Bitmap Index Scan`, and the heap fetch consumes only the matching `dish_ingredients` pages. The complete literal plan—including the enclosing joins and the tiny-table sequential scans—is attached in the plan audit.
#### State 2: No Pushdown (Non-Sargable)
With only a plain index on `d.name`, the expression `lower(d.name)` cannot use that index as a matching scan key. In the audited fixture, the chosen alternative includes hash joins and sequential scans:
```sql
-- ❌ Non-sargable filter
EXPLAIN SELECT * FROM ingredients i
JOIN dish_ingredients di ON i.id = di.ingredient_id
JOIN dishes d ON di.dish_id = d.id
WHERE lower(d.name) = 'dish 5';
```
In this fixture, the engine builds hash tables and scans the small relations. The expression can still be evaluated at the `dishes` relation; what is missing is a matching expression-index access condition. Keep predicate placement, selectivity estimation, and index searchability as separate concepts.
> [!TIP]
> If you must query using a function, create an **Expression Index**. For example, `CREATE INDEX idx_dishes_lower_name ON dishes (lower(name))` allows Postgres to index the *result* of the function, restoring sargability.
### 🧪 Match a Compound Predicate with a Multicolumn Index — Lab
**Find Supplier #3's March Deliveries**: "Show all deliveries from Supplier #3 that arrived in March 2024."
#### The Naive Solution
With only a single-column index on `delivery_time`, the planner walks the time range and then filters by supplier as a row-level check. Every row inside the date range is fetched from the heap before the supplier is checked.
#### The Lazy Fix
A **Multicolumn Index** gives the engine a single B-Tree that orders rows first by supplier, then by time.
```sql
CREATE INDEX idx_supply_supplier_time
ON supply_deliveries(supplier_id, delivery_time);
```
> [!IMPORTANT]
> **Column Order Matters**: `(supplier_id, delivery_time)` directly supports equality on supplier followed by a time range. PostgreSQL 18 may still reach later columns through skip scan or other usable constraints, so the reversed workload is not locked out—but a time-leading index is often cheaper for time-only searches. Equality-leading/range-second is a useful map, not a law.
---
### Common Non-Sargable Anti-Patterns
| Anti-Pattern | Technical Limitation | Sargable Alternative |
| :--- | :--- | :--- |
| `WHERE lower(name) = 'saffron'` | Function result is missing from index. | Use an **Expression Index**. |
| `WHERE date + '1 day' > now()` | Predicate math breaks boundary checks. | `WHERE date > now() - '1 day'`. |
| `WHERE coalesce(status, 'P') = 'P'` | Null-handling masks physical values. | Use a **Partial Index**. |
| `WHERE name LIKE '%spice%'` | A normal B-tree cannot position a scan from a leading wildcard. | Consider a `pg_trgm` GIN or GiST index and its supported operators. |
---
### Recap: The Sargability Rules
> [!IMPORTANT]
> - Match the indexed column or indexed expression to an operator supported by its access method/opclass.
> - When algebra and types preserve semantics, moving math to the constant side can expose a simple range condition.
> - Give important expressions statistics when estimate quality matters.
> - Sargability enables candidate index paths. Index-only scans additionally require all referenced columns in the index and favorable visibility-map state.
---
## 4.11 - Summary: Reading the Work Order
### Chapter 4 Capstone: Why is PostgreSQL Ignoring My Index?
You are paged because database CPU usage has hit 100%. A critical dashboard query has suddenly slowed down, and you discover it is performing a **Sequential Scan** even though there is a B-Tree index on the filtered column.
Below are three diagnostic cases. For each, determine **why** the planner discarded the index and **how** to resolve it.
---
#### Case A: The Function Wrap
* **The Index**: `CREATE INDEX idx_orders_time ON orders(order_time);`
* **The Query**:
```sql
SELECT count(*) FROM orders WHERE date_trunc('day', order_time) = '2026-06-11';
```
* **The Culprit**: **Non-sargable predicate**. The index stores sorted raw values of `order_time`, but wrapping the column in `date_trunc` prevents Postgres from binary-searching the B-Tree. It must evaluate the function for every row in the table via a sequential scan.
* **Restore Sargability**: Rewrite the query to filter on raw ranges, keeping the column bare:
```sql
SELECT count(*) FROM orders
WHERE order_time >= '2026-06-11 00:00:00+00'
AND order_time < '2026-06-12 00:00:00+00';
```
---
#### Case B: The Popular Species
* **The Index**: `CREATE INDEX idx_animals_species ON animals(species_id);`
* **The Query**:
```sql
SELECT * FROM animals WHERE species_id = 1;
```
* **The Culprit**: **Low Selectivity**. Species `1` (Capybaras) accounts for 90% of the rows in the table. Because the filter is not selective, an index scan would require loading almost every page anyway, executing random I/O hops. The planner correctly calculates that scanning the table sequentially (Seq Scan) is cheaper than random index accesses.
* **Trust the Sequential Scan**: **Do nothing**. The planner made the physically correct decision. If this table grows massive and you only query specific time windows, consider partitioning or a covering index, but here a Seq Scan is optimal.
---
#### Case C: The Invisible Bulk Insert
* **The Index**: `CREATE INDEX idx_deliveries_qty ON supply_deliveries(quantity_kg);`
* **The Context**: You just bulk-inserted 500,000 deliveries of exactly `10.0` kg into the table (which contains a total of 1,000,000 rows).
* **The Query**: Filtering for a rare quantity that represents only 10 rows.
```sql
SELECT * FROM supply_deliveries WHERE quantity_kg = 999.0;
```
* **The Culprit**: **Stale statistics**. Because the bulk insert occurred within a single transaction or autovacuum hasn't triggered yet, `pg_class.reltuples` and the data distribution in `pg_statistic` are completely outdated. The planner doesn't know the table contains 1,000,000 rows or that `999.0` is extremely rare; it assumes average selectivity and selects a Seq Scan.
* **Refresh the Statistics**: Run `ANALYZE supply_deliveries;` to update the catalog statistics.
---
### 📝 Summary: Reading the Work Order
You began with SQL text.
You now know that Postgres does not execute that text as a script. It turns the request into a tree of physical operations: scans, joins, sorts, hashes, aggregates, mutations, and memory decisions.
That changes how you debug performance. You no longer ask only, “Why is this query slow?” For any unfamiliar node, ask five questions:
1. How many rows did the planner expect, and how many arrived at execution time?
2. How many times did the node loop, and therefore how much total work did it perform?
3. Did it touch heap or index buffers, spill to temporary files, or wait on another resource?
4. Which child supplied its rows, and which parent amplified or discarded them?
5. Would a schema, statistics, query, memory, or concurrency change remove work—or merely move it elsewhere?
When a plan contains a specialist node that this chapter does not cover, the companion repository's [Grand Operations Field Guide](https://github.com/AesaKamar/LearnYouAPostgres/blob/main/Operations/_Operations.md) provides the deeper reference cards. It is a field guide, not a checklist of nodes to memorize.
The main achievement is plan literacy. When Postgres ignores an index, you can now look for the real reason: poor selectivity, stale statistics, non-sargable predicates, misleading cost settings, or a cheaper sequential path.
> [!NOTE] SQL Requests; EXPLAIN Reveals the Work
> **Concept**: SQL is the request. EXPLAIN is the work order.
### Sources & Further Reading
- [PostgreSQL 18: Using `EXPLAIN`](https://www.postgresql.org/docs/18/using-explain.html)
- [PostgreSQL 18: Planner Statistics](https://www.postgresql.org/docs/18/planner-stats.html)
- [PostgreSQL 18: Planner Cost Constants](https://www.postgresql.org/docs/18/runtime-config-query.html#RUNTIME-CONFIG-QUERY-CONSTANTS)
- [PostgreSQL 18: `WITH` Queries](https://www.postgresql.org/docs/18/queries-with.html)
- Source trail: `src/backend/optimizer/` and `src/backend/executor/`.
<div style="page-break-after: always;"></div>