# 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. It does not execute the SQL; it produces the executor's tree of instructions. `EXPLAIN` reveals that work order without running it, while the executor later walks the tree and asks each node for its 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 weighing I/O and CPU work. To understand its instincts, first look at the physical hierarchy it is trying to model.
If we scale a single **L1 Cache Reference (1.5 nanoseconds)** to **1.5 seconds**, the physical hierarchy looks like this:
| Action | Illustrative Latency | Human Scale (`1 ns = 1 s`) | At the Elephant Cafe |
| :--- | :--- | :--- | :--- |
| **L1 Cache Reference** | 1.5 ns | 1.5 seconds | Pluck a sugar cube from the bowl beside your cup. |
| **Branch Mispredict** | 5 ns | 5 seconds | Notice you grabbed the wrong order pad and swap it. |
| **L2 Cache Reference** | 7 ns | 7 seconds | Reach for the saucers on the shelf above the machine. |
| **Main Memory Reference** | 100 ns | 1 minute, 40 seconds | Walk to the back pantry and find the tea tin. |
| **SSD Random Read** | 150,000 ns | 1 day, 17 hours, 40 minutes | Order a rare spice and wait through tomorrow's lunch. |
| **Disk Seek (HDD)** | 10,000,000 ns | about 116 days | Close the Cafe for a season while someone hunts through the warehouse. |
| **WAN Round Trip** | 150,000,000 ns | about 4.8 years | Plant the coffee, harvest the beans, and train another barista. |
These are illustrative orders of magnitude, not promises about a particular machine. The point is the cliff: a trip down the hierarchy can turn a blink into a geological era.
### The Planner's Cost Model
The planner does not carry a stopwatch. It carries a ledger. Its **Cost Model** uses dimensionless, tunable units whose relationships matter more than their absolute values. By convention, one sequential page fetch costs `1.0`; the remaining constants are priced relative to that baseline:
- **`cpu_tuple_cost` (0.01)**: The default cost of processing one row in memory.
- **`seq_page_cost` (1.0)**: The default cost of fetching a page as part of a sequential series.
- **`random_page_cost` (4.0)**: The default cost of fetching a non-sequential page.
The values encode a workload hypothesis, including the expected effect of caching. They are not nanoseconds wearing tiny fake moustaches.
> [!TIP]
> **Tuning the Ledger**: On a heavily cached workload or storage with inexpensive random access, a measured lower `random_page_cost` relative to `seq_page_cost` can make index-driven plans look more attractive. Do not tune it because the box says NVMe. Benchmark the workload, change the hypothesis, and verify the plans it buys.
> [!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 **relative resource 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$). This book calls a strict predicate that selects a small fraction of rows *highly selective*; some texts reverse the high/low labels, so follow the fraction when terminology differs.
- **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.
### 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.
#### Create Skew Without Statistics
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);
```
#### Estimate the Rare Value Before and After `ANALYZE`
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."
#### Foreign Keys Do Not Index the Child Side
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 Missing FK Index Forces a Full Sweep
With no usable index for `dish_id`, the planner falls back to a **Parallel Seq Scan**, sweeping all 300,000 rows across multiple workers:
#### Index `dish_id` to Collapse the Scan
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
Chapter 3's GIN lookup found matching locations first, then fetched their rows. Here is why that separation matters.
An **Index Scan** follows index entries to heap tuples. When many matches share heap pages, visiting those pages together can be cheaper. A **Bitmap Scan** makes a reservation map before taking the tour:
1. **Mark the seats.** A **[[Operations/Index/BitmapIndexScan|Bitmap Index Scan]]** records matching tuple locations in memory.
2. **Combine reservations, if needed.** **[[Operations/Index/BitmapAndBitmapOr|BitmapAnd / BitmapOr]]** intersects or merges maps from multiple index scans. The same index can serve more than one branch.
3. **Visit the rooms.** A **[[Operations/Page/BitmapHeapScan|Bitmap Heap Scan]]** visits the selected heap pages in physical order and retrieves the qualifying rows.
The map costs memory and startup work. It also loses the index's ordering, so an `ORDER BY` may still need a sort. A tiny lookup may favor an ordinary Index Scan; a broad search may favor a Sequential Scan. The reservation desk is not free.
**When the map gets crowded:** within its `work_mem` budget, a bitmap may become **lossy**, recording whole pages instead of exact tuple locations. Those pages require rechecking the condition against their tuples. A printed `Recheck Cond` alone does not prove lossiness; inspect `Heap Blocks: lossy` and any rows removed by recheck.
### 🧪 Trace Two Reservations Through One Bitmap — Lab
**Invite a Species and the Founding Members**: The Cafe wants every animal in species 1, plus every animal with `id < 50`. There is an index on `species_id` and a primary-key index on `id`. Some guests qualify twice; the invitation list must not.
Before running, sketch where the two result sets should meet and which node must fetch the animal names.
```sql
BEGIN;
SET LOCAL enable_seqscan = off; -- discourage a full walk for this demonstration
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM animals WHERE species_id = 1 OR id < 50;
ROLLBACK; -- restore the planner setting
```
This is the captured fixture's plan, not a promise of identical timings or node choices on every dataset. The setting discourages a sequential scan; it does not command a bitmap.
1. **Follow the work.** Identify the index probes, the combining node, and the heap visit. Which produces locations, and which produces rows? Why does a guest matching both predicates appear only once?
2. **Check the map's precision.** Does your output show exact or lossy heap blocks? What evidence would show that rechecking rejected tuples?
3. **Change the request.** Repeat the query with only `id < 50`, then compare both queries without the planner override. Explain any changed plan using the number of matches and pages visited.
4. **Price the shortcut.** Would this path satisfy `ORDER BY name` by itself? When might its map-building work cost more than it saves?
Keep the plans and your explanation. The **[[Manuscript/04 - Query Planning & Execution/4.11 - Summary (Query Planning & Execution)#Bitmap Debrief: One Map, One Heap Tour|bitmap debrief]]** is at the end of the chapter.
### 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
-- Discourage a sequential scan for this comparison
BEGIN;
SET LOCAL enable_seqscan = off;
EXPLAIN SELECT * FROM ingredients WHERE id = 12;
```
**State 3: Index-Only Scan (Heap Avoidance)**
If the index contains all the requested columns, an Index-Only Scan becomes possible. Chapter 3's visibility rule still applies.
```sql
-- Keep the comparison focused on an index-only path
SET LOCAL enable_bitmapscan = off;
EXPLAIN SELECT id FROM ingredients WHERE id < 100;
ROLLBACK; -- restore both settings
```
> [!IMPORTANT]
> **Covering is not visibility.** The index can supply the columns; the Visibility Map decides whether a heap visibility check is still needed. Watch `Heap Fetches`, not just the node's name.
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.
### 🧪 Make the Join Skip Heap Visits — Transfer Challenge
Chapter 3 put a delivery's payload beside its search key. Now apply that trick inside a join: for animals with `id < 50`, return each name and its order count.
Start with the ordinary `orders(animal_id)` index and collect a baseline:
```sql
DROP INDEX IF EXISTS idx_orders_animal_covering;
VACUUM (ANALYZE) orders;
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;
```
Do not change the query yet. Make the index earn its keep.
1. **Locate the missing payload.** Which relation needs a different index? Separate the search key from the extra column the query needs.
2. **Predict the payoff.** Propose the index, then name the scan change you expect. If the join repeats that scan, how do `loops` magnify the work?
3. **Build and verify.** Test your proposal. Compare scan type, heap fetches, and buffer work, not just elapsed time. What joining and grouping work remains?
4. **Test the limits.** Would fresh writes let the same index avoid every heap visit? What storage and write cost did you add?
A smaller Cafe may choose another join shape. If it does, explain that choice rather than forcing the illustration. The **[[Manuscript/04 - Query Planning & Execution/4.11 - Summary (Query Planning & Execution)#Covering Debrief: Less Work Inside Every Loop|covering debrief]]** keeps the solution and visual proof until you have made your case.
### Core Scan Cards
These two cards put the basic choice side by side: walk the table or follow an index. The bitmap lesson and covering challenge above handle their variations. Full cards for those and the specialist scans remain in the companion **[[Operations/_Operations|Grand Operations Field Guide]]**.
![[Operations/Table/SeqScan]]
![[Operations/Index/IndexScan]]
---
## 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 Three Most Recent Items — Lab
**Return Three Recent Items per Frequent Animal**: "Show me the three most recently ordered items for every animal that has placed more than 15 orders."
#### A Global Window Ranks the Whole Candidate Set
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.
#### `LATERAL` Fetches Three Rows per Animal
Use a **LATERAL Join** with an explicit ordering rule. The matching index lets Postgres enter each animal's newest orders first, while the final tie-breakers make the result deterministic.
```sql
CREATE INDEX IF NOT EXISTS idx_orders_animal_recent
ON orders (animal_id, order_time DESC, id DESC);
SELECT a.name, recent_items.dish_id, recent_items.order_time
FROM animals a
CROSS JOIN LATERAL (
SELECT oi.dish_id, o.order_time
FROM orders o
JOIN order_items oi ON o.id = oi.order_id
WHERE o.animal_id = a.id
ORDER BY o.order_time DESC, o.id DESC, oi.dish_id
LIMIT 3
) recent_items
WHERE (SELECT count(*) FROM orders WHERE animal_id = a.id) > 15;
```
**A Bounded Nested Loop**: The plan can use a parameterized index scan for each animal, walk recent orders in index order, and stop once the lateral branch emits three items. `LIMIT 3` now means something: without `ORDER BY`, it would merely mean “whichever three arrived first.”
### 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'."
#### `lower(name)` Blocks the Indexed Starting Point
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.
#### A Sargable Name Flips the Join Order
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."
#### Stringified Dates Destroy Useful Order
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.
#### Native Dates Keep Both Streams Mergeable
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."
#### One `NULL` Can Poison `NOT IN`
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.
#### `NOT EXISTS` Unlocks an Anti-Join
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**: This captured plan uses a **Hash 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.
**Controlled fixture:** 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 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;
```
This lab disables bitmap scans because many deliveries per ingredient may naturally produce a `Bitmap Heap Scan`. The controlled setting exposes 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."
#### A Global `LIMIT` Cannot Rank Each Quarter
Using `row_number() OVER (PARTITION BY ...)` is standard, but the rank must be filtered *after* the window is calculated. A bare `LIMIT 3` would limit the entire result, not each quarter.
```sql
EXPLAIN (ANALYZE, BUFFERS)
WITH ranked_deliveries AS (
SELECT
id,
date_trunc('quarter', delivery_time) AS quarter_start,
quantity_kg,
row_number() OVER (
PARTITION BY date_trunc('quarter', delivery_time)
ORDER BY quantity_kg DESC, id
) AS delivery_rank
FROM supply_deliveries
)
SELECT id, quarter_start, quantity_kg, delivery_rank
FROM ranked_deliveries
WHERE delivery_rank <= 3
ORDER BY quarter_start, delivery_rank;
```
#### Three Rows from Every Quarter
`date_trunc('quarter', ...)` produces a year-and-quarter bucket, so Q1 of different years does not collapse into one partition. The `WindowAgg` needs rows grouped by that bucket and ordered by `quantity_kg DESC, id`; satisfying that required order is why a `Sort` commonly appears. If it exceeds `work_mem`, the sort can spill to temporary files.
#### Filter the Rank After the Window
The outer `WHERE delivery_rank <= 3` is the correctness fix. For performance, restrict the date range when the request allows it, or store and index a quarter key with the ordering columns when this is a frequent workload. The window still requires correctly ordered input; a syntactic change alone does not make that work disappear.
#### 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**. The displayed Sequential Scan has a total cost of **2,603**, but the Limit node estimates only `0.02` because this streaming child can produce a row immediately. In the captured run, the first heap page supplies the requested tuple and the Limit stops pulling. A Limit cannot rescue a blocking child—such as a Sort that must consume all input before returning its first row—so always read the subtree below it.
### 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."
#### `extract()` Hides the Indexed Timestamp
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 Cleanup Job Scans Every Order
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.
#### Index the Expression the Job Actually Uses
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'."
#### `lower()` Feeds `ModifyTable` a Broad Pipeline
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'
);
```
#### Compare the Enum Directly
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 Outer Cast Filters Too Late
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 WorkTable Builds the Broad Result
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.
#### Anchor the Recursion at `id = 1`
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."
#### Column-Side Arithmetic Hides the B-Tree
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.
#### Move the Arithmetic to the Constant
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."
#### A Time-Only Index Fetches Every March Row
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.
#### Lead with Supplier, Then Range by Time
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 has hit 100%. Three dashboard queries use sequential scans despite apparently relevant B-Tree indexes. The scans look alike; their causes do not.
For each case, name the leading explanation, one plausible alternative, the next discriminating measurement, the immediate response, the structural repair, and the repair's secondary cost.
---
#### Case A: The Function Wrap
```sql
CREATE INDEX idx_orders_time ON orders(order_time);
SELECT count(*)
FROM orders
WHERE date_trunc('day', order_time) = TIMESTAMPTZ '2026-06-11 00:00:00+00';
```
```text
Aggregate (actual rows=1)
-> Seq Scan on orders (estimated rows=8,100; actual rows=8,347)
Filter: date_trunc('day', order_time) = '2026-06-11 00:00:00+00'
Rows Removed by Filter: 2,991,653
```
The estimates are respectable. The index is valid. Someone recently doubled `work_mem`, but the plan did not change.
---
#### Case B: The Popular Species
```sql
CREATE INDEX idx_animals_species ON animals(species_id);
SELECT *
FROM animals
WHERE species_id = 1;
```
```text
Seq Scan on animals (estimated rows=901,000; actual rows=900,412)
Filter: species_id = 1
Rows Removed by Filter: 99,588
Buffers: shared hit=9,411
```
The table is hot in memory, the estimate matches reality, and the index passes `amcheck`. A colleague proposes `SET enable_seqscan = off` because “an index should be used if we paid to build it.”
---
#### Case C: The Invisible Bulk Insert
Yesterday, `quantity_kg = 999.0` described roughly 40% of `supply_deliveries`. A correction job rewrote almost all of those values, leaving ten matches, but no analyze has completed.
```sql
CREATE INDEX idx_deliveries_qty ON supply_deliveries(quantity_kg);
SELECT *
FROM supply_deliveries
WHERE quantity_kg = 999.0;
```
```text
Seq Scan on supply_deliveries (estimated rows=398,000; actual rows=10)
Filter: quantity_kg = 999.0
Rows Removed by Filter: 999,990
```
The query became slow immediately after the correction job. The deployment also upgraded the application driver, which is exciting but not yet causal.
> [!IMPORTANT] Diagnose Before You Hint
> Explain why each sequential scan exists. At least one correct response is to leave the scan alone.
<div style="page-break-after: always;"></div>
### Planner Debrief: Same Node, Three Causes
#### Case A: Give the B-Tree a Boundary
The plain index stores `order_time`, not `date_trunc('day', order_time)`. The expression cannot become an index condition on that plain B-Tree, so the executor evaluates it as a filter. The close row estimate argues against cardinality error as the leading cause; `work_mem` prices sorts and hashes, not the search key this scan lacks.
Confirm the absence of an `Index Cond` and inspect the available index definitions. Then expose a raw half-open range:
```sql
SELECT count(*)
FROM orders
WHERE order_time >= TIMESTAMPTZ '2026-06-11 00:00:00+00'
AND order_time < TIMESTAMPTZ '2026-06-12 00:00:00+00';
```
A matching expression index is another option when that expression is the stable workload. Either repair adds code or index maintenance; verify semantics around time zones as well as plan shape.
#### Case B: Trust the Honest Walk
The predicate returns roughly 90% of the table, and `SELECT *` requires the heap columns. An index path would locate almost every matching tuple and visit most heap pages anyway. The planner's estimate is accurate, and the sequential scan reads those pages directly. Forcing the index suppresses a choice; it does not make the choice cheap.
Confirm the distribution in `pg_stats` and compare representative execution with buffers and elapsed time. The immediate and structural response may both be **do nothing**. If the product needs a narrower question, change the workload or physical design for that question—not the planner's honesty.
#### Case C: Refresh the Planner's Memory
The estimate still describes yesterday's distribution. The query now returns ten rows, but the planner prices a path for nearly 400,000. Inspect `pg_stats`, modification counts, and the last analyze time, then run:
```sql
ANALYZE supply_deliveries;
```
The existing B-Tree should become competitive once the catalog describes the new distribution. For recurring correction jobs, schedule or trigger analysis at the right point and tune per-column statistics only when distribution detail requires it. Analysis consumes resources, and higher statistics targets add planning and maintenance work; measure rather than prescribing them globally.
---
### Bitmap Debrief: One Map, One Heap Tour
In the captured plan, `idx_animals_species_id` and `animals_pkey` feed **BitmapOr**. They produce locations, not animal rows. A location present in both maps remains one location after the merge. The **Bitmap Heap Scan** makes the heap tour and supplies those rows. Two reservations, one map.
The illustrated run reports exact heap blocks. A `Recheck Cond` is not proof that memory ran out; lossy blocks and rows removed by recheck are the evidence to inspect. Keeping only `id < 50` removes the need to merge two maps and makes a narrow ordinary Index Scan attractive. With the override gone, a Sequential Scan may still win for a sufficiently broad request.
Finally, physical page order is not name order. Sorting remains separate work. Judge the bitmap by the heap work it saves after paying for the map, not by whether it looks more sophisticated than a full walk.
### Covering Debrief: Less Work Inside Every Loop
The join searches `orders` by `animal_id`, but `count(o.id)` also needs `id`. Carry that payload in the index:
```sql
CREATE INDEX idx_orders_animal_covering
ON orders(animal_id) INCLUDE (id);
VACUUM (ANALYZE) orders;
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 captured fixture uses an **Index Only Scan** inside the nested loop, with `Heap Fetches: 0`. The shortcut now pays off on each inner probe. Compare `loops` as well as scan type; the inner node's buffer totals already cover its executions, so do not multiply those totals again. The join still pairs rows, and the aggregate still counts them. We removed heap visits, not the rest of the kitchen.
`VACUUM` lets this stable table's pages become all-visible. Fresh writes can clear those bits, bringing heap visibility checks back even though the index still covers the query. Extra index payload also costs space and write maintenance. That is the bargain to verify under the real workload.
When finished, remove the extra teaching index to restore the baseline:
```sql
DROP INDEX idx_orders_animal_covering;
```
---
### 📝 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. SQL is the request; `EXPLAIN` reveals the work order. 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.
<div style="page-break-after: always;"></div>