# Chapter 3: Access Paths & Indexing
## 3.0 - Indexes (The Mighty Indexes)
<img src="assets/chap_2_indexes.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
A sequential scan examines the relation's relevant blocks. On a large table that can be expensive, although many blocks may already be cached and a scan can still be cheaper than scattered index probes for an unselective predicate.
> [!NOTE] An Index Is Another Physical Relation
> **Concept**: An index is not magic. It is a separate physical relation maintained by an access method.
> **Payoff**: A B-tree stores key data and heap tuple identifiers in an ordered structure; other access methods organize entries differently and may be lossy. In every case, PostgreSQL maintains extra storage so qualifying reads can avoid broader heap work.
### The Illusion of Order
Imagine searching for the ingredient "Saffron." Without an index, the engine must start at page one and read every tuple. This brute-force path is a **Sequential Scan** ($O(n)$).
You might expect to jump halfway into a file to find a record by ID. However, as established in **[[Manuscript/02 - Physical Storage & MVCC/2.4 - Relation (The Table)|2.4 Relation (The Table)]]**, a Postgres table is a **Heap**. It is an unordered collection of data where tuples are stored wherever space is available.
Heap tuple versions can be physically scattered because PostgreSQL uses available space rather than maintaining key order:
1. **Random Arrival**: Tuples are persisted in the first available gap.
2. **Update Overhead**: MVCC updates create fresh versions in new locations, leaving the old ones behind.
3. **Vacuuming**: Housekeeping creates holes throughout the file that are constantly backfilled.
Because tuples are disordered, the engine cannot "guess" a row's location. Finding a single needle requires sifting through every piece of hay.
To avoid this, we use **Indexes**: separate, sorted storage structures that map a value (like 'Saffron') to a 6-byte physical pointer—the **`ctid`**.
> [!IMPORTANT]
> **The Performance Payoff**: An Index lookup (typically $O(\log n)$) scales logarithmically. In a million-row table, a Sequential Scan might read 10,000 pages; an Index lookup might read only a handful.
### The Gallery of Shortcuts
Because there are many different ways to be lazy, Postgres maintains a collection of different index architectures. Each is optimized for a specific mathematical search space.
#### 1. The General Standard: B-Tree
The **[[Manuscript/03 - Access Paths & Indexing/3.1 - B-Tree (The Balanced Bookshelf)|B-Tree]]** is the foundational index of the Cafe. It is a balanced search tree designed for "greater than," "less than," or "equal to" queries. It helps ensure that finding any record takes a predictable, logarithmic amount of effort.
#### 2. The Spatial Sieve: GiST
When searching through abstract coordinates—like finding an animal "nearby" or checking overlapping geographic zones—the **[[Structures/Index/GiST|GiST]]** index acts as a sieve. It uses a tree of bounding boxes to quickly discard entire regions of space that couldn't possibly contain your answer.
#### 3. The Multi-Value Map: GIN
If a single record contains many distinct elements (like a JSON document or an array of scent notes), the **[[Structures/Index/GIN|GIN]]** (Generalized Inverted Index) acts as a reverse-map. It maps a single grain of "Salt" back to every tuple that requires it.
#### 4. The Industrial Label: BRIN
**[[Manuscript/03 - Access Paths & Indexing/3.3 - BRIN (The Industrial Label)|BRIN]]** (Block Range Index) is designed for large tables. Instead of tracking individual records, it summarizes large blocks of data (e.g., "Prices between $10 and $50 are in this 1MB range"). It is tiny and efficient for large, chronologically ordered datasets.
#### 5. The Advanced Snout: Vector Search
Postgres can navigate by similarity. When searching through multidimensional flavor profiles—like finding an ingredient that is similar to Saffron—**[[Manuscript/03 - Access Paths & Indexing/3.4 - HNSW & IVFFlat (The Similarity Map)|3.4 HNSW & IVFFlat (The Similarity Map)]]** uses geometric graphs (HNSW) to find the nearest neighbor in vector space.
> [!NOTE]
> **Specialized Access Methods**: Postgres also supports **Hash** indexes (for exact-match equality only) and **Bloom** indexes (probabilistic filters for multi-column queries). These are niche tools reserved for specific high-scale access patterns where the general-purpose power of a B-Tree is not required.
Every shortcut charges rent. An index adds CPU, buffer coordination, WAL, dirty pages, storage, vacuum, and cache pressure to relevant writes. An INSERT generally creates an entry in each applicable index; an UPDATE can sometimes avoid new entries through HOT, or in a partial index whose predicate excludes the row. The dirty index pages can reach storage later—COMMIT does not wait for each one to be physically flushed.
Use `pg_stat_user_indexes` as one clue when reviewing index usage, not as an eviction notice. A quiet index may enforce a constraint, protect a rare critical query, have recently reset statistics, or serve reads on a standby. Learn its job before removing it.
---
## 3.1 - B-Tree (The Balanced Bookshelf)
<img src="assets/arch_index_btree.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
When a table grows beyond a few megabytes, the cost of a **Sequential Scan** becomes prohibitive. To optimize retrieval, Postgres utilizes the **B-Tree**: a self-balancing, tree-based data structure optimized for disk-based storage.
The B-Tree maintains data in sorted order. It allows the engine to perform a balanced search, discarding the vast majority of the search space at every step. This results in **$O(\log n)$** search complexity.
### The Index Page Mechanics
In the physical file system, the B-Tree is composed of standard 8KB pages.
- **The Root Page**: A single entry-point page that contains pointers to the next level down.
- **The Internal Pages**: These act as traffic controllers, directing the engine toward specific value ranges.
- **The Leaf Pages**: The bottom level of the tree. These contain the **Index Tuples**: a mapping of the column value to the physical address (`ctid`) of the record in the table.
**The important idea:** The index is a separate relation. Its leaf entries point into the heap; the row and its MVCC header still live there. The bookshelf holds the map, not the animal.
### The Numeric Search
Imagine you’re looking for **Invoice #150**. The engine starts at the Root:
1. **The Root**: "The value 150 falls between 100 and 200. Follow the pointer to the **Center Internal Page**."
2. **The Internal Page**: "Within this page, 150 falls in the range 126-150. Follow the pointer to **Leaf Page A**."
3. **The Leaf Page**: "The entry for 150 exists here. It points to the physical address **Page 42, Offset 5** (`(42,5)`)."
```text
[ ROOT ]
/ | \
<100 100-200 >200
|
[ INTERNAL ]
/ | \
100-125 126-150 151-200
|
[ LEAF A ] -> (42,5), (42,6)...
```
The B-Tree is **Perfectly Balanced**. This balance ensures that retrieval time remains predictable. Whether you search for the first item or the last, the number of page reads (the depth of the tree) is identical.
### 🧪 Find One Row in a Million — Lab
**Find the March 25 Delivery**: "Find the exact delivery record for March 25th at 10:00 AM."
#### No Index Means a Full Heap Walk
Without a usable index or other selective path, the planner may choose a **Sequential Scan**. It visits heap pages through PostgreSQL and operating-system caches—reaching storage only on cache misses—and checks qualifying tuples.
```sql
-- Disable existing indexes for demonstration
DROP INDEX IF EXISTS idx_supply_delivery_time;
ANALYZE supply_deliveries;
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM supply_deliveries
WHERE delivery_time = '2024-03-25 10:00:00';
```
#### Table Growth Makes the Walk Linear
The cost scales linearly with the size of the table. In a small Cafe, this is a millisecond. In a global franchise with millions of deliveries, the "Wall" of data becomes a multi-second bottleneck that consumes massive I/O bandwidth.
#### A B-Tree Narrows the Search
Create a **B-Tree Index**. This allows the engine to skip 99.9% of the data by traversing the tree structure.
```sql
CREATE INDEX idx_deliveries_time ON supply_deliveries(delivery_time);
ANALYZE supply_deliveries;
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM supply_deliveries
WHERE delivery_time = '2024-03-25 10:00:00';
```
#### A Stable, Narrow Lookup
The cost drops significantly, and more importantly, it stays low as the table grows. The engine now only reads a handful of index pages and one specific heap page.
---
### X-Ray Vision: Index-Only Scans (The Covering Shortcut)
Even with an Index Scan, the engine usually has to perform two steps:
1. Find the `ctid` (the physical address) in the index.
2. Visit the **Heap** (the table) to fetch the other columns.
But what if every column you needed was already in the index?
### 🧪 Skip the Heap with a Covering Index — Lab
**Return the Delivery from the Index Alone**: "Show me the `delivery_time` and `quantity_kg` for a specific delivery."
#### A Narrow Index Still Needs the Heap
A standard index on `delivery_time` forces a trip to the heap to get the `quantity_kg` column.
```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT delivery_time, quantity_kg
FROM supply_deliveries
WHERE delivery_time = '2024-03-25 10:00:00';
```
#### Every Match Pays a Heap Visit
You see an **Index Scan**. The `Buffers` line shows it had to read the index AND the heap page. If you are doing this for millions of rows, those extra heap hits add up.
Use a **Covering Index** with the `INCLUDE` clause. This stores non-key columns in the leaf nodes. While these columns are not used for sorting, they are available for the engine to retrieve directly from the index.
```sql
DROP INDEX IF EXISTS idx_deliveries_time;
CREATE INDEX idx_deliveries_covering
ON supply_deliveries(delivery_time)
INCLUDE (quantity_kg);
ANALYZE supply_deliveries;
EXPLAIN (ANALYZE, BUFFERS)
SELECT delivery_time, quantity_kg
FROM supply_deliveries
WHERE delivery_time = '2024-03-25 10:00:00';
```
#### Zero Heap Fetches
You will see an **Index Only Scan**. The engine never touched the heap. It found the time, grabbed the quantity right next to it in the leaf page, and returned the result immediately.
> [!NOTE]
> **Heap Fetches**: You might see `Heap Fetches: 0`. The engine consulted the **Visibility Map** and found the corresponding heap pages marked **all-visible**, so it did not need to inspect their tuple headers. If a page's all-visible bit is not set—often because its rows changed recently—the scan must visit the heap to check visibility. Whether the buffer is dirty is a separate question.
---
#### Deep Dive: Packing the Tree (Compression & Deduplication)
To keep the tree shallow, Postgres must fit as many pointers as possible into each 8KB page. It employs two physical optimizations:
**1. Suffix Compression**
PostgreSQL can truncate suffix attributes and, where the data type permits it, shorten a separator key while preserving a valid boundary between neighboring leaf ranges. This **suffix truncation** increases fan-out without changing the logical ordering contract; it should not be modeled as arbitrary string abbreviation.
**2. B-Tree Deduplication**
In modern versions (v13+), if an index contains many identical keys (e.g., thousands of rows with the same `species_id`), Postgres does not store the key 1,000 times. It stores the key once, followed by a **Posting List** of pointers. This can shrink index size by 40-70%.
### Growing the Bookshelf: Page Splits and Right-Links
To maintain this perfect balance, if a leaf page becomes completely full of index entries, Postgres must perform a **Page Split**. It allocates a brand new page, shifts half of the keys from the full page onto the new page, and inserts a pointer to the new page in the parent index page.
```mermaid
graph LR
subgraph beforeSplit [Before split]
ParentB["Internal page<br/>126-200 → Leaf A"]
LeafA["Leaf A<br/>keys 126-150"]
end
subgraph afterSplit [After split]
ParentA["Internal page<br/>126-150 → Leaf A<br/>151-200 → Leaf B"]
LeafA2["Leaf A<br/>126-137"]
LeafB["Leaf B<br/>138-150"]
LeafA2 -->|"right-link"| LeafB
end
beforeSplit -.-> afterSplit
```
But index reads do not hold heavyweight locks on the tree. If a page splits while a concurrent reader is mid-scan on that page, searching for a key that just got migrated to the new sibling page, how does the reader avoid getting lost or returning incomplete results without blocking write operations?
> [!IMPORTANT] Predict How a Search Survives a Page Split
> If a leaf page is split under your feet, and the key you are searching for is moved to a new page, how does your search query find it without restarting the search from the root node? Pause and formulate a guess.
You might expect that the reader must abort its scan and restart the entire search from the Root node of the B-Tree, or that Postgres holds an exclusive read lock on the entire index branch to prevent any splits while reads are active. However, locking would kill concurrent throughput, and restarting scans would waste massive CPU and I/O cycles.
Instead, Postgres resolves this using **Right-Links** (a feature of Lehmann & Yao's B-link tree algorithm).
B-tree pages carry sibling links in their special space. A non-rightmost leaf page links to its **right sibling**, which supports ordered range traversal and concurrent page splits:
1. When a page splits, the engine creates the new page and links the old page's Right-Link to point to it.
2. If a concurrent reader is looking for a key on the old page and realizes the key is greater than the page's new maximum key limit (indicating a split just happened), the reader does not panic.
3. Instead of returning to the Root, the reader simply traverses the horizontal **Right-Link** to the right-sibling page and continues scanning.
Because of Right-Links, readers do not need to hold locks on parent pages when descending the tree, nor do they need to lock pages for long. They can read and write concurrently with minimal synchronization, achieving immense read concurrency while writing at speed.
> [!NOTE]
> **In PostgreSQL Terms**
> * **B-Tree**: The default balanced search tree structure.
> * **Leaf Page**: The lowest level of the index containing the `ctid` pointer.
> * **Page Split**: The engine's method for keeping the tree perfectly balanced.
> [!IMPORTANT] Predict Whether Every Index Must Change
> When you update a column in the heap that is *not* indexed, the row's physical address (ctid) still changes under MVCC. Does every single B-Tree index on that table still have to write a new entry pointing to the new ctid? Pause and think. We resolve this mystery in **[[Manuscript/03 - Access Paths & Indexing/3.6 - Index Maintenance (The Cost of Fame)|Chapter 3.6]]**.
Range queries use those sibling links too. Find the first matching leaf, then walk sideways until the range ends. Let's inspect the links themselves.
### 🧪 Observation Lab: Traversing B-Tree Sibling Links
To prove that a B-Tree is technically a B+ Tree with horizontal page links, we will use the `pageinspect` extension to inspect the internal metadata and traverse leaf page siblings directly.
#### Enable `pageinspect` for the B-Tree
Ensure `pageinspect` is installed in your database:
```sql
CREATE EXTENSION IF NOT EXISTS pageinspect;
```
#### Walk from the Meta-Page to Right Siblings
1. Read the meta-page of the index on `animals(species_id)` to locate the root page and structure levels:
```sql
SELECT magic, version, root, level, fastroot
FROM bt_metap('idx_animals_species_id');
```
Output:
```
magic | version | root | level | fastroot
--------+---------+------+-------+----------
340322 | 4 | 3 | 1 | 3
```
Here, page `3` is the root node of the index, and the tree has a `level` of 1 (meaning the root points directly to leaf pages).
2. Query the leaf pointers inside the root page:
```sql
SELECT itemoffset, ctid FROM bt_page_items('idx_animals_species_id', 3) LIMIT 3;
```
Output:
```
itemoffset | ctid | data
------------+-----------+-------------------------
1 | (1,0) |
2 | (10,4097) | 01 00 00 00 00 00 00 00
3 | (5,1) | 02 00 00 00 00 00 00 00
```
The `ctid` column indicates that key `1` lives on index page `1` (via `(1,0)`), key `2` starts on index page `5` (via `(5,1)`), and so on.
3. Inspect index page `5` to view the sibling pointers using `bt_page_stats()`:
```sql
SELECT blkno, type, live_items, btpo_prev, btpo_next
FROM bt_page_stats('idx_animals_species_id', 5);
```
Output:
```
blkno | type | live_items | btpo_prev | btpo_next
-------+------+------------+-----------+-----------
5 | l | 2000 | 1 | 7
```
#### Leaf Pages Point to Their Neighbors
Look at the sibling link columns:
- **`btpo_prev`** points to index page `1`.
- **`btpo_next`** points to index page `7`.
#### Range Scans Walk the Leaves Sideways
When running a query like `WHERE species_id BETWEEN 1 AND 3`, Postgres does not traverse the tree nodes from root down for each value. Instead, it locates key `1` on page `1`, then follows the `btpo_next` pointer directly to page `5`, and then to page `7` horizontally. The horizontal traversal links are what turn a hierarchical tree into a highly performant range-query engine.
#### Deep Dive: The B-Tree Access Method
![[Structures/Index/BTree]]
---
## 3.2 - GIN & GiST (The Word Scavenger)
<img src="assets/arch_index_gin.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
Sometimes Postgres needs to find something more complex than a simple primary key. It may need to locate every document containing a specific word, or every row with a specific array element.
To search **inside** the data, Postgres utilizes specialized index types like **GIN** and **GiST**. These structures are designed for multi-valued data types like arrays, JSONB blobs, and geometric shapes. They index the *contents* of the record rather than the record itself.
Imagine a **Corkboard** where every unique value (a word, a scent, or a key) is pinned. Each pin has a collection of strings leading back to every record where that specific value appears. This is an **Inverted Index**.
When you query for a specific item, Postgres finds the entry for that value in the index and follows the **Posting List** directly to the matching records. It is a reversed map where the data tells you which tuple to fetch.
### 🧪 Find Every Flowery Ingredient with GIN — Lab
**Match the “Flowery” Array Element**: "Find all ingredients that have a 'Flowery' scent profile."
#### Array Containment Without an Inverted Index
The **`@>`** operator asks, "Does this array contain these elements?" Without an index for that question, Postgres walks the `flavors` table and inspects each `scent_notes` array.
```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM flavors
WHERE scent_notes @> ARRAY['Flowery'::scent_primary];
```
#### Every Row Pays an Array Inspection
For a small cafe, this is fine. But as your library of flavors grows into the thousands, the engine spends more and more time deserializing arrays just to check a single value.
#### GIN Maps Each Scent to Its Rows
Create a **GIN Index**. This builds the "Corkboard" where every scent is pinned to its corresponding records.
```sql
CREATE INDEX idx_flavors_scent ON flavors USING GIN (scent_notes);
ANALYZE flavors;
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM flavors
WHERE scent_notes @> ARRAY['Flowery'::scent_primary];
```
#### Visit Only the Matching Pages
The GIN lookup feeds a **Bitmap Heap Scan**: find the matching locations, then visit their pages. Keep that two-part shape in mind. We unpack the reservation map in **[[Manuscript/04 - Query Planning & Execution/4.3 - Scans (The Full Table Walk)#Bitmap Scan: The Reservation Map|Chapter 4.3]]**.
> [!WARNING]
> **The GIN Tax**: While GIN is exceptionally fast for reading, it is expensive to maintain. Because one tuple can be indexed by dozens of "pins" (keys), a single `INSERT` triggers many small, scattered writes to the index. This results in significant **Write Amplification**.
#### Deep Dive: The GIN Access Method
![[Structures/Index/GIN]]
---
GiST is a **Generalized Search Tree**. Unlike the B-Tree, which works on rigid order, GiST organizes complex objects into a hierarchy of **Bounding Boxes**.
Is a point inside this circle? Does this box overlap that box? GiST uses these signatures to narrow the search space before performing a final check on the actual data.
### 🧪 Narrow the Sweet-and-Sour Range with GiST — Lab
**Intersect the Sweetness and Sourness Ranges**: "Find all ingredients with a sweetness level between 7 and 9 AND a sourness level between 1 and 3."
#### Two B-Trees See Two Separate Dimensions
You could use two separate B-Trees on `sweetness_1_to_10` and `sourness_1_to_10`. The engine would pick one, scan it, and then filter the results by the other. Or it might perform a Bitmap AND of both indexes—better, but still two separate traversals.
#### GiST Searches the Sweet-and-Sour Region
Use **GiST** with the `btree_gist` extension (or just use GiST on geometric types). In the Cafe, we can represent these flavor profiles as a 2D coordinate: `(sweetness, sourness)`.
```sql
-- Enable btree_gist extension to support standard types in GiST indexes
CREATE EXTENSION IF NOT EXISTS btree_gist;
-- Using GiST to index multiple range dimensions at once
CREATE INDEX idx_flavors_profile_gist ON flavors USING gist(sweetness_1_to_10, sourness_1_to_10);
```
#### Prune the Search Space
GiST organizes the search space into "Bounding Boxes." Instead of scanning a line, the engine narrows down a region. It quickly discards entire boxes of ingredients that do not match the criteria, finding the intersection in a single tree traversal.
**Range Efficiency**: GiST is exceptionally effective for data with "ranges"—such as time windows or price brackets. It can identify overlapping intervals without scanning the entire table.
**The k-NN Queue**: For "nearest neighbor" searches (using the `<->` operator), GiST uses a **Priority Queue** to explore the tree. It checks the bounding boxes closest to the target first, skipping regions that are mathematically too far away to contain a better match.
#### Deep Dive: The GiST Access Method
![[Structures/Index/GiST]]
### The SP-GiST Tree (Space-Partitioned GiST)
For data that doesn't overlap perfectly—like phone numbers, name prefixes, or IP addresses—Postgres reaches for **SP-GiST**. This structure partitions the search space into perfectly non-overlapping regions, allowing for high-speed prefix matching and spatial searches.
#### Deep Dive: The SP-GiST Access Method
![[Structures/Index/SPGiST]]
---
## 3.3 - BRIN (The Industrial Label)
<img src="assets/arch_index_brin.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
At extreme scale, even an efficient B-Tree can become a liability. Its storage footprint can grow to be a significant percentage of the table size.
For high-volume scenarios, Postgres utilizes **BRIN** (Block Range Index).
Instead of indexing every tuple, BRIN stores summaries for ranges of heap pages. The common `minmax` operator class records lower and upper values; PostgreSQL also offers other BRIN operator classes, such as `minmax-multi`, inclusion, bloom, and specialized types.
### The Boundary Summary
BRIN is a tool of exclusion. It doesn't tell the engine where something *is*; it only identifies where a value definitely **is not**. This allows the engine to skip large sections of the table during a scan.
> [!NOTE]
> **The Block Range**: The default `pages_per_range` is **128 pages**—1MB in a standard 8KB-block build. BRIN is commonly far smaller than a tuple-level B-tree, but the ratio depends on table size, range size, operator class, and summary tuples.
>
> **The REVMAP**: BRIN's **[[Structures/Index/BRIN|reverse map]]** links each heap page range to the index tuple that stores its summary. For the default `minmax` operator class, that summary contains lower and upper values; another operator class may store different evidence.
The common `minmax` BRIN lives or dies by **Physical Correlation**. It is most useful when nearby physical pages contain nearby logical values, as often happens with append-heavy timestamps or increasing IDs. Other BRIN operator classes summarize other properties and do not all obey the same min/max story.
If the table storage is "scrambled"—with values tossed randomly into any available container—the BRIN summaries become too broad to be useful. If every 128-page block contains the full range of possible values, the index can never exclude any section. The engine will be forced to perform a full sequential scan anyway.
> [!NOTE]
> **In PostgreSQL Terms**
> * **BRIN**: Block Range Index, used for massive tables.
> * **Block Range**: A contiguous set of physical pages (default 128) summarized together.
> * **Bitmap Index Scan**: The execution node used to skip the excluded blocks during a query.
### Measuring the BRIN Advantage
Let's look at a large delivery fixture modeled on `supply_deliveries`:
### 🧪 Prune January with BRIN — Lab
**Find Every January Delivery**: "Show me every delivery that arrived in January 2024."
#### The Disposable Fixture
The starter `supply_deliveries` table is deliberately small and already has a B-Tree on `delivery_time`, so it cannot honestly demonstrate this comparison. Build a session-local, append-ordered fixture large enough for the planner to care:
```sql
CREATE TEMP TABLE delivery_brin_lab AS
SELECT g AS id,
TIMESTAMPTZ '2024-01-01 00:00:00+00'
+ g * INTERVAL '1 minute' AS delivery_time,
(((g::bigint * 7919) % 10000) / 100.0)::numeric(8,2) AS quantity_kg
FROM generate_series(0, 499999) AS g;
ANALYZE delivery_brin_lab;
```
The timestamps advance with physical insertion order. The quantities cycle through a wide domain and are intentionally uncorrelated with that order. One fixture will therefore show both where `minmax` BRIN works and where it politely accomplishes very little.
#### A Sequential Scan Reads Every Range
On a large table without another useful index for this predicate, a Sequential Scan reads every heap page. A B-Tree can answer the range precisely, but it stores entries at tuple granularity and therefore costs much more space and write maintenance than a range summary.
```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) FROM delivery_brin_lab
WHERE delivery_time >= TIMESTAMPTZ '2024-01-01 00:00:00+00'
AND delivery_time < TIMESTAMPTZ '2024-02-01 00:00:00+00';
```
#### January Locality Cannot Rescue a Sequential Scan
In the captured fixture, January rows occupy a narrow physical span, but the sequential scan still reads the whole table. That locality is a property of how this fixture was loaded, not a promise attached to timestamps.
#### Summarize Correlated Time Ranges
Create a **BRIN Index** using the common `minmax` operator class. With the default range size, it records one summary tuple for each 128-page range.
```sql
CREATE INDEX delivery_brin_lab_time_idx ON delivery_brin_lab
USING brin(delivery_time);
ANALYZE delivery_brin_lab;
EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) FROM delivery_brin_lab
WHERE delivery_time >= TIMESTAMPTZ '2024-01-01 00:00:00+00'
AND delivery_time < TIMESTAMPTZ '2024-02-01 00:00:00+00';
```
#### BRIN Rejects Most Non-January Ranges
In the captured, correlated fixture, the engine uses a **Bitmap Index Scan** to reject ranges whose summaries cannot overlap January. The BRIN index is tiny relative to a tuple-level B-tree, and the I/O reduction is large because most ranges can be excluded. Broader summaries or weaker correlation would reduce that dividend.
---
### 🧪 Break BRIN with an Uncorrelated Column — Lab
**Find Every 5.25 kg Delivery**: "Find all deliveries where the `quantity_kg` was exactly 5.25."
#### Scattered Quantities Defeat Physical Locality
The `quantity_kg` values are deliberately scattered throughout the table. They have **low correlation** with the physical storage order.
#### Every Range Looks Plausible
Even if you create a BRIN index on `quantity_kg`, the planner might ignore it. Why? In this fixture, each 128-page range spans nearly the full `0.00` to `99.99` domain. The summary "summarizes" almost nothing, so it excludes almost no blocks.
```sql
CREATE INDEX delivery_brin_lab_qty_idx ON delivery_brin_lab USING brin(quantity_kg);
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM delivery_brin_lab WHERE quantity_kg = 5.25;
```
#### BRIN Wins Only When Ranges Can Be Excluded
`minmax` BRIN is a tool of **Physical Locality**, not a requirement for perfect sorting. If each range spans nearly the column's full value domain, it excludes little and the planner may prefer a sequential scan. Reordering the table can narrow the summaries, but `CLUSTER` rewrites the table under a strong lock and later writes can gradually weaken that order.
**The rule of thumb for `minmax`:** Its usefulness rises when page ranges have narrow value bounds and falls as those bounds overlap. Low correlation can make this min/max BRIN ineffective for a predicate, but other BRIN operator classes summarize different properties and the planner will choose the index only when its cost model expects useful exclusion.
**Operational Note:** `autosummarize` is **off by default**. Enable it deliberately for append-heavy indexes, or monitor unsummarized ranges and call `brin_summarize_new_values()` from maintenance. Autosummarization requests work through autovacuum; it does not make summary freshness instantaneous.
```sql
-- Optional cleanup; the table also disappears when this session ends.
DROP TABLE delivery_brin_lab;
```
#### Deep Dive: The Block Range Index
![[Structures/Index/BRIN]]
---
## 3.4 - HNSW & IVFFlat (The Similarity Map)
### (Vector Search)
<img src="assets/arch_index_vector_v4_axolotl_1776816298964.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
Postgres is increasingly used for queries that defy exact matching. Instead of searching for a specific ID, users might ask for records that conceptually "feel" like another.
This is the domain of **Vector Search** and **Embeddings**. These technologies allow the engine to navigate proximity in a high-dimensional space.
Think of it as following a **Similarity Map**. Instead of exact character matches, the engine follows the proximity of an idea across a multidimensional space.
### The Translation (Embeddings)
How do you translate an ingredient into a set of numbers? This task is delegated to an external **Embedding Model**. When a new ingredient arrives, the model analyzes its features and produces a precise set of coordinates: **`[1.8, -1.2, 1.5]`**.
These numbers represent the ingredient's position in a **vector space**. A higher value in the first dimension might represent "Earthiness," while a lower value in the second represents "Sweetness." By projecting complex qualities onto a multi-dimensional map, we allow Postgres to use geometric distance to calculate similarity, referencing the [[Manuscript/01 - Foundations & Data Modeling/1.0 - Relations & Normalization (The Cafe Layout)|architectural blueprints]] established at the Cafe's entrance.
### The HNSW Index
To find a "similar" item, Postgres doesn't perform a linear scan. Instead, it can use a **Hierarchical Navigable Small World (HNSW)** index. This structure builds a multi-layered graph where each node connects to its nearest conceptual neighbors.
HNSW works across multiple layers to locate nodes:
1. **Sparse Top Layer**: Navigation begins at the top with a few "landmark" tuples. Postgres makes large navigational leaps across the vector space.
2. **Dense Mid Layers**: As the engine nears the target neighborhood, it drops to lower levels with more detailed connections.
3. **Leaf Layer**: Finally, the engine reaches the bottom layer for a fine-grained proximity search.
### The IVFFlat Index
If the HNSW index takes too long to build, the engine might use **IVFFlat** (Inverted File with Flat Compression).
Instead of a graph, the engine divides the vector space into **Clusters**. It picks several "Centroids" (central landmarks) and assigns every tuple to the nearest one.
- **The Search**: When querying, Postgres identifies the nearest clusters.
- **The Proximity**: The engine then only searches tuples inside those specific clusters, ignoring the rest of the vector space.
> [!WARNING]
> **The Recall Trade-off**: Unlike a B-Tree, Vector indexes are **Approximate**. To gain speed, you sacrifice a tiny bit of "Recall" (accuracy). A B-Tree search is deterministic; in a Vector Index, the engine typically finds the tuple that is most likely the closest match.
### Letters vs. Ideas
To understand why this is special, compare it to a traditional search:
| The Letter-Seeker (`LIKE`) | The Idea-Tracker (`<->`) |
| :--- | :--- |
| Looks for the characters **'p-e-a-n-u-t'**. | Looks for the **concept** of a peanut. |
| Finds: "salted peanuts," "peanut butter." | Finds: "legumes," "earthy snacks," "hazelnuts." |
| Fails: If you misspell it or use a synonym. | Succeeds: Even if the words never match! |
This is not "exact matching"—it is **proximity in the dark**. The engine ignores the characters on the label; it only cares about the geometric distance between two concepts in the vector space.
> [!NOTE]
> **In PostgreSQL Terms**
> * **Vector Search**: Finding tuples based on mathematical proximity in high-dimensional space.
> * **HNSW**: Hierarchical Navigable Small World, a graph-based index for fast approximate search.
> * **IVFFlat**: Inverted File with Flat Compression, a clustering-based index.
> * **ANN Search**: Approximate Nearest Neighbor. Vector indexes trade perfect accuracy for massive speed gains.
### 🧪 Find Nearby Flavors with HNSW — Lab
**Find the Five Nearest Flavors**: "Find the 5 ingredients that smell most like a 'Sweet & Sour' profile: `[8.0, 2.0, 1.5]`."
Here, **`<->`** measures Euclidean (L2) distance. The index's `vector_l2_ops` must match that operator: a map is only useful if it measures the journey you asked for.
#### The Unindexed Reality
Without a vector index, Postgres must perform a **Sequential Scan**. It calculates the "Euclidean Distance" between your target vector and every row in the `flavors` table, then sorts the entire result set.
```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT ingredient_id FROM flavors
ORDER BY flavor_vector <-> '[8.0, 2.0, 1.5]' LIMIT 5;
```
#### The CPU Bottleneck
As the `flavors` table grows, this calculation becomes a significant resource bottleneck.
#### The Graph Path
Create an **HNSW Index**. This constructs a graph of conceptual neighbors, allowing the engine to "hop" toward the result instead of calculating every distance.
```sql
CREATE INDEX idx_flavors_vector_hnsw ON flavors
USING hnsw (flavor_vector vector_l2_ops)
WITH (m = 16, ef_construction = 64);
ANALYZE flavors;
-- Force index usage for demonstration on small data
SET enable_seqscan = OFF;
EXPLAIN (ANALYZE, BUFFERS)
SELECT ingredient_id FROM flavors
ORDER BY flavor_vector <-> '[8.0, 2.0, 1.5]' LIMIT 5;
```
#### The Vector Shortcut
The engine uses an **Index Scan**. It performs a few graph hops, identifies the nearest neighborhood, and returns the top matches with minimal effort.
> [!IMPORTANT]
> **Recall vs. Precision**: Vector indexes are "Approximate." If you use **IVFFlat** with too few clusters (lists), or **HNSW** with low `ef_search` parameters, you might miss the absolute closest match in exchange for incredible speed. In the Cafe, this is usually acceptable—finding a "very similar" scent is better than waiting 10 seconds for the "perfect" one.
### HNSW vs IVFFlat
Choosing between the two primary vector index types is a matter of resource allocation:
- **HNSW** is faster for queries and offers better recall. However, it is slower to build and consumes more memory for the graph structure.
- **IVFFlat** is fast to build and lighter on memory. It requires a "training" phase and its query performance can degrade as data distribution shifts.
In the AI age, this is how Postgres helps you find "related products" or "similar concepts" by calculating the geometric distance between two concepts in a multi-dimensional space.
#### Deep Dive: The Vector Access Methods
![[Structures/Index/HNSW]]
![[Structures/Index/IVFFLAT]]
---
## 3.5 - Constraints & Triggers (The Integrity Layer and the Chain Reaction)
<img src="assets/arch_beavers_dominoes.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
When you look at a slow database service, your first instinct is usually to blame the Query Optimizer (**[[Manuscript/04 - Query Planning & Execution/4.0 - Query Planning & Operations (The Strategy of Execution)|The Optimizer]]**) or a missing map (an Index). But sometimes, the slowness isn't coming from the search. It's coming from **Quality Control**.
Postgres treats every write operation as a guarantee of **Declarative Integrity**. To the engine, a map is only useful if the territory it describes follows the rules. It is not enough for a tuple (**[[Manuscript/02 - Physical Storage & MVCC/2.2 - Tuple (The Suitcase)|Tuple]]**) to contain valid bits; it must also obey the logic of the Cafe. To ensure this, Postgres employs a strict **Validation Loop**—a process that often uses those very same maps to verify that reality matches the rules.
### Declarative Integrity (Constraints)
A constraint is a database rule enforced during the relevant statement—or, when eligible and deliberately deferred, at the chosen constraint-check or commit boundary.
If a statement violates a constraint, PostgreSQL raises an error and the transaction remains aborted until you roll it back, possibly to a savepoint. Constraints enforce the rules you actually wrote down; they cannot invent missing business rules or protect data changed outside the normal SQL path.
#### 1. Local Verification (`CHECK`, `NOT NULL`)
These checks usually inspect the candidate row without searching another relation. Their cost is often small, although a complex expression or user-defined function can turn Quality Control into real work. Measure the write path that you actually run.
```sql
-- Enforcing price integrity at the hardware boundary
ALTER TABLE dishes ADD CONSTRAINT check_price_positive
CHECK (price > 0);
```
#### 2. Global Verification (`UNIQUE`, `PRIMARY KEY`)
These are significantly more expensive. To ensure a name is unique across the entire Cafe, the validation mechanism must leave the current tuple and consult the **[[Manuscript/03 - Access Paths & Indexing/3.1 - B-Tree (The Balanced Bookshelf)|Index Bookshelf]]**. Every `UNIQUE` constraint is essentially a hidden Index Tax on every insert and update.
#### 3. Relational Verification (`FOREIGN KEY`)
This is where complexity enters the system. Postgres must verify that a referenced ID actually exists in a different table.
> [!WARNING]
> **The Foreign Key Index Trap**: PostgreSQL requires the referenced columns—such as `species.id`—to be a primary key, a unique constraint, or a suitable non-partial unique index. Parent existence checks therefore have an indexed candidate key. PostgreSQL does **not** automatically index the referencing columns—such as `animals.species_id`. Deleting a parent row or updating its referenced key may have to search the child table for matches, so an index on the child key is often essential.
#### Predict → Observe → Explain → Repair → Generalize
1. **Predict**: Which operation becomes expensive when a large child table lacks an index on its foreign-key column: inserting a child, or deleting a referenced parent?
2. **Observe**: In a disposable lab, create many child rows, run `EXPLAIN (ANALYZE, BUFFERS) DELETE FROM parent WHERE id = ...`, then roll the transaction back.
3. **Explain**: The parent key already has a unique index. PostgreSQL is searching the child table to prove that the parent change is allowed.
4. **Repair**: Add a B-tree index to the referencing child column and repeat the plan.
5. **Generalize**: A child index is often useful, not universally free; account for its write and storage cost when parent keys are immutable and parent deletes are rare.
#### 4. Deferred Verification (The Commit Boundary)
Sometimes, relational rules must be broken temporarily during a massive shipment where two tuple reference each other. By marking a constraint as **`DEFERRABLE INITIALLY DEFERRED`**, you tell the engine to wait until the "End of the Shift" (the `COMMIT`) before performing the final check. If the integrity is not restored by then, the entire shipment is rejected.
### Functional Chain Reactions (Triggers)
What if you need a specific action to happen automatically the moment tuple is packed? For that, Postgres uses the **Chain Reaction**: the **Trigger**.
A Trigger is a function that is invoked by the engine in response to a specific event (`INSERT`, `UPDATE`, `DELETE`). It is the mechanism by which one event knocks over a series of others across the database.
### Timing: `BEFORE` vs `AFTER`
The timing of a trigger determines whether the validation mechanism handles it *before* the tuple is written or *after* it has already been persisted to the heap.
- **`BEFORE` Triggers**: These allow you to "polish" the data before it is written. If you want to automatically set an `updated_at` timestamp or sanitize a string, you do it here while the record is still in a mutable state.
- **`AFTER` Triggers**: Used to set off other machines. Once the record is locked in, the event can trigger operations in different tables, such as logging a change or updating an audit ledger.
### Granularity: Row vs. Statement
- **`FOR EACH ROW`**: The dominoes fall for every single tuple. If you modify 10,000 rows, the trigger function is invoked 10,000 times, incurring massive **Function Evaluation Overhead**.
- **`FOR EACH STATEMENT`**: The trigger fires once per triggering statement, even when the statement affects zero rows. It can avoid per-row invocation when statement-level semantics are sufficient, but its function can still perform expensive work.
```sql
-- Sanitizing the timestamp via a Row-level Trigger
CREATE OR REPLACE FUNCTION set_updated_at()
RETURNS TRIGGER AS $
BEGIN
NEW.updated_at = NOW(); -- Stamper logic before the tuple is latched
RETURN NEW;
END;
$ LANGUAGE plpgsql;
CREATE TRIGGER animals_update_timestamp
BEFORE UPDATE ON animals
FOR EACH ROW
EXECUTE FUNCTION set_updated_at();
```
While Triggers are a powerful way to keep the Cafe synchronized, they hide the **True Cost** of an action. Every event requires CPU and I/O to execute. If your chain reaction is too long, a simple `UPDATE` operation can escalate into a chaotic sequence of secondary writes that grinds the database to a halt.
Triggers and constraints add work to the write path; they do not necessarily perform secondary writes. When they do change rows, those changes pay their own applicable constraint, index, buffer, and WAL costs. This is the Cost of Fame.
---
## 3.6 - Index Maintenance (The Cost of Fame)
<img src="assets/arch_index_maintenance.png" width="250" style="float: left; margin: 0 20px 20px 0;" />
> [!NOTE] Production Story: Friday at 4:55 PM (The Random I/O Cliff)
> "We deployed a high-frequency write service. CPU utilization was flat at 5%, but the database was dying. Storage IOPS had saturated, and insert queries that once took 1 millisecond were now taking 80 milliseconds. What happened?
>
> The table had 12 indexes. As the working set grew beyond useful cache, inserts increasingly needed page reads, page splits, WAL generation, and dirty-buffer turnover across many structures. Storage latency and IOPS climbed even though CPU remained low. The database had fallen off the **Random I/O Cliff**."
Committing a tuple is a complex operation involving **Declarative Integrity** checks and **Trigger** execution.
If your table is over-indexed, the work has only just begun. Inserts maintain all applicable indexes; deletes create future index cleanup; updates maintain indexes unless HOT can preserve their references. This is the primary trade-off of indexing.
In the database, each index introduces **synchronous logical work**. If you have indexes on `name`, `price`, and `scent_notes`, PostgreSQL must update the relevant in-memory index structures consistently, coordinate access, and generate the necessary WAL before the transaction can commit durably.
### The Write Latency Tax
When a new tuple is inserted or an old one updated, PostgreSQL performs the required index maintenance as part of the statement. That adds CPU, buffer, lock/latch, WAL, and dirty-page work. The heap and index pages do **not** each need to be flushed to durable storage before `COMMIT`: Write-Ahead Logging makes it safe to flush those pages later as long as the required WAL reaches durable storage first.
This is the hidden cost of “helpfulness.” The more specialized routes you build, the more structures a write may have to coordinate and later maintain. The exact tax depends on the command, changed columns, predicates, and HOT eligibility.
### Index-Only Scans
As we saw in **[[Manuscript/03 - Access Paths & Indexing/3.1 - B-Tree (The Balanced Bookshelf)|3.1 B-Tree]]**, the engine can sometimes skip the trip to the table. If every required value is available from the index, the planner can consider an **Index-Only Scan**.
The visibility map lets an index-only scan avoid a heap visit for an all-visible page. For a page whose bit is not set, the executor visits the heap to check tuple visibility even though the requested values are available in the index. “Index Only” describes the node's capability, not a guarantee of zero heap fetches.
### Heap-Only Tuples (HOT)
Under MVCC, every `UPDATE` is physically written as an `INSERT` of a new tuple at a new physical address (`ctid`). This means that even if you change a column that is *not* indexed—like changing an animal's name from 'Gilly' to 'Glowy' when you only have an index on their `species_id`—the row moves to a new location. Intuitively, the index on `species_id` must now be updated to point to this new `ctid`. If a table has 10 indexes, updating a single non-indexed column should force Postgres to update all 10 indexes with the new address.
Yet, under high-write workloads, Postgres often updates rows without touching the index maps at all. How does the engine direct queries from the index to the new physical address without updating the B-Tree?
> [!IMPORTANT] Predict How an Index Finds a HOT Successor
> If the row's physical location changes, but we do not update the index pointers, how does an index scan find the new row version? Pause and formulate a guess.
You might expect that Postgres performs a background sweep to update index pointers asynchronously, or that it does a page-wide scan to locate the row. But background sweeps would lag behind, leading to temporary data inconsistency, and page scans would be too slow.
Instead, Postgres resolves this using an optimization called **HOT (Heap-Only Tuples)**.
When you update a row, and the changed column is not indexed:
1. **Same-Page Check**: If there is enough free space on the *same physical 8KB page* (the shipping container), Postgres writes the new tuple version to that same page.
2. **The Tuple Chain**: It does **not** add new index entries. The old tuple's `t_ctid` links to the new same-page tuple version; pruning can later turn the root line pointer into a redirect.
3. **The Indirection Hop**: An index scan follows the existing heap TID to the page and walks the HOT chain until it finds the version visible to its snapshot.
Because existing index entries remain usable, a qualifying HOT update avoids new entries in the table's indexes. Heap tuple/header changes and WAL still exist, but index write and later cleanup work are reduced.
To increase the chance of HOT updates, you can lower a table's **`FILLFACTOR`** (for example, to 90 or 80). New pages leave more room for future versions, but row growth, update distribution, pruning, and concurrency still decide whether same-page space is available.
> [!CAUTION]
> **The HOT Gate**: The new tuple must fit on the same heap page, and the update must not require new entries in indexes that reference the changed values (including relevant expressions and predicates). Modern PostgreSQL has additional treatment for summarizing indexes; verify with the actual schema and `n_tup_hot_upd` rather than reducing the rule to one B-tree column.
### 🧪 Observation Lab: Heap-Only Tuple Updates (HOT)
We can observe HOT updates by updating indexed versus unindexed columns and reading the statistics table.
#### Reserve Page Room for HOT Updates
Connect to the database and create a table with a custom `FILLFACTOR` to reserve page space, and add a single index:
```sql
-- Reserve 20% of the page for updates
CREATE TABLE hot_test (
id INT PRIMARY KEY,
indexed_col INT,
unindexed_col INT
) WITH (fillfactor = 80);
CREATE INDEX idx_hot_test_indexed ON hot_test(indexed_col);
-- Insert a test record
INSERT INTO hot_test VALUES (1, 100, 200);
```
#### Update Indexed and Unindexed Columns
1. Run an update against the **indexed** column. Note that Postgres statistics are reported asynchronously, so we run a second connection or query `pg_stat_force_next_flush()` if we want to see them immediately:
```sql
UPDATE hot_test SET indexed_col = 101 WHERE id = 1;
SELECT pg_stat_force_next_flush();
SELECT n_tup_upd, n_tup_hot_upd
FROM pg_stat_user_tables
WHERE relname = 'hot_test';
```
Output:
```
n_tup_upd | n_tup_hot_upd
-----------+---------------
1 | 0
```
Because we modified an indexed column, Postgres was forced to update the B-Tree index map. `n_tup_hot_upd` remains `0`.
2. Run an update against the **unindexed** column:
```sql
UPDATE hot_test SET unindexed_col = 201 WHERE id = 1;
SELECT pg_stat_force_next_flush();
SELECT n_tup_upd, n_tup_hot_upd
FROM pg_stat_user_tables
WHERE relname = 'hot_test';
```
Output:
```
n_tup_upd | n_tup_hot_upd
-----------+---------------
2 | 1
```
#### A Same-Page Update Skips Every Index
Notice that `n_tup_upd` is now `2`, and `n_tup_hot_upd` has incremented to `1`. The second update bypassed the index map completely, pointing the old slot to the new slot using same-page line pointer redirection.
```sql
-- Clean up
DROP TABLE hot_test;
```
Indexes can transform reads, but they add write-path and maintenance work. Whether another index measurably reduces modification throughput depends on command mix, HOT eligibility, cache, WAL, and concurrency.
---
### 🧪 Manipulation Lab: Write Amplification (The Cost of Indexes)
We will compare the insert speed of a table with zero indexes against a table with eight indexes to measure the write tax directly.
#### Build Indexed and Unindexed Bench Tables
Connect to your database. We will use the `\timing` command inside `psql` to measure statement execution times. Run the following setup blocks:
```sql
CREATE TABLE bench_none (id INT, name TEXT, val INT);
CREATE TABLE bench_many (id INT, name TEXT, val INT);
CREATE INDEX idx_m1 ON bench_many(id);
CREATE INDEX idx_m2 ON bench_many(name);
CREATE INDEX idx_m3 ON bench_many(val);
CREATE INDEX idx_m4 ON bench_many((id + val));
CREATE INDEX idx_m5 ON bench_many(lower(name));
CREATE INDEX idx_m6 ON bench_many(id, val);
CREATE INDEX idx_m7 ON bench_many(val, id);
CREATE INDEX idx_m8 ON bench_many(id, name);
```
#### Time Identical Inserts with Zero and Eight Indexes
Enable statement timing and run identical bulk insert queries of 50,000 rows into both tables:
```sql
\timing on
-- Insert 50k rows into the table with zero indexes
INSERT INTO bench_none
SELECT i, 'Name ' || i, i
FROM generate_series(1, 50000) i;
-- Insert 50k rows into the table with eight indexes
INSERT INTO bench_many
SELECT i, 'Name ' || i, i
FROM generate_series(1, 50000) i;
\timing off
```
#### Eight Indexes Make Inserts Six Times Slower
Examine the execution times. While exact values depend on system hardware, the difference is stark:
- `bench_none` completes in approximately **50 milliseconds**.
- `bench_many` completes in approximately **340 milliseconds**.
On one reference run, eight indexes slowed this insert by **more than 6x**. Your ratio will vary with hardware, cache state, PostgreSQL settings, and extension versions; the durable observation is that every maintained index adds work to the write path.
#### Every Extra Index Taxes Every Write
Indexes are not free. Every maintained index adds synchronous work and usually more WAL and dirty pages to the write path. When a workload demands high insert/update volume, retain indexes whose read, integrity, or operational value justifies that tax.
```sql
-- Clean up
DROP TABLE bench_none;
DROP TABLE bench_many;
```
---
### Summary: The Maintenance Ledger
To help you decide which index structures to build, here is a final ledger of the trade-offs:
| Index Type | Read Speed | Write Cost | Storage Size | Best For... |
| :--- | :--- | :--- | :--- | :--- |
| **B-Tree** | Lightning Fast ($O(\log N)$) | Low-Medium | Medium-High | Primary keys, unique keys, range scans, equality matching |
| **GIN** | Fast (Bitmap scans on sets) | High | High | Arrays, JSONB documents, full-text search terms |
| **GiST** | Fast (Bounding box intersections) | Medium-High | Medium-High | Geometric coordinates, ranges (time windows), k-NN queries |
| **HNSW** | Extremely Fast (Graph hops) | Very High | Very High | High-dimensional vector embeddings and similarity matching |
| **BRIN** | Medium (Prunes block ranges) | Negligible | Negligible | Massive tables (100GB+) physically correlated by key (dates/IDs) |
### Chapter 3 Appendix: The Grand Index Decision Tree
1. **Standard value (ID, Name, Date)?** -> Use **B-Tree**.
2. **Collection (Array, JSONB)?** -> Use **GIN**.
3. **Shape or Range (GPS, Circles, Time windows)?** -> Use **GiST**.
4. **Embeddings (Vector Search)?** -> Use **HNSW**.
5. **100GB+ and physically ordered?** -> Use **BRIN**.
---
## 3.7 - Summary: The Cost of a Shortcut
### Chapter 3 Capstone: Design the Right Index
Below are three workloads from the Elephant Cafe. Choose from **B-Tree**, **GIN**, **GiST**, **BRIN**, **HNSW**, **IVFFlat**, or **None**—then defend the bill that arrives with your choice.
---
#### Scenario A: The Scent Profiler
- **Table**: `flavors(ingredient_id INT, scent_notes scent_primary[])`
- **Scale**: 20 million rows, loaded nightly; read hundreds of times per minute.
- **Question**: Find ingredients containing both `'Spicy'` and `'Fruity'`.
```sql
SELECT ingredient_id
FROM flavors
WHERE scent_notes @> ARRAY['Spicy', 'Fruity']::scent_primary[];
```
The operations team mentions that the database has plenty of RAM. Treat that as context, not an index strategy.
---
#### Scenario B: The Infinite Ledger
- **Table**: `supply_deliveries(id BIGINT, delivery_time TIMESTAMPTZ, quantity_kg NUMERIC)`
- **Scale**: 500 million rows, appended in delivery-time order.
- **Question**: Summarize one week at a time.
- **Constraint**: The index must remain small enough to make ingestion and maintenance inexpensive. A few extra heap pages are acceptable.
```sql
SELECT sum(quantity_kg)
FROM supply_deliveries
WHERE delivery_time >= TIMESTAMPTZ '2026-06-01 00:00:00+00'
AND delivery_time < TIMESTAMPTZ '2026-06-08 00:00:00+00';
```
The table is large, but size alone does not choose the access method. The useful clue is the relationship between value order and physical page order.
---
#### Scenario C: The Busy Little Registry
- **Table**: `animals(id INT PRIMARY KEY, name TEXT, species_id INT)`
- **Scale**: 10,000 rows, usually resident in memory.
- **Workload**: 20 name searches per minute and a synthetic event feed that changes names thousands of times per second.
- **Question**: Look up animals by a non-unique `name`.
```sql
SELECT * FROM animals WHERE name = 'Babu';
```
The product manager says every searchable field deserves an index. Product managers are allowed hobbies; the write path is allowed evidence.
#### Make the Bargain
For each workload, record:
1. your chosen access path;
2. the strongest rejected alternative;
3. the observation you would collect before creating it;
4. its write, storage, or accuracy cost;
5. how you would verify that it improved the real workload.
> [!IMPORTANT] Choose Before the Bill Arrives
> “Add an index” is not a complete answer. Name the work it avoids and the work it creates.
<div style="page-break-after: always;"></div>
### Index Debrief: Three Different Bargains
#### The Scent Profiler: GIN
A **GIN** index with the array's supported operator class is the leading choice for the containment predicate. It indexes components of the composite value so PostgreSQL can find candidate rows without walking all 20 million arrays. A B-Tree orders whole array values and does not answer this containment question in the same way.
Before creating it, measure predicate frequency and selectivity, then compare `EXPLAIN (ANALYZE, BUFFERS)` under representative data. The price is a larger and more expensive write path, including pending-list and maintenance behavior. Verify read latency and nightly-load cost together; a triumphant read benchmark that quietly doubles ingestion time has merely moved the queue.
#### The Infinite Ledger: BRIN
**BRIN** is the leading choice because `delivery_time` remains physically correlated with heap order and the workload tolerates reading the summarized ranges that overlap a week. It can remain dramatically smaller than a B-Tree while pruning most of the table.
A B-Tree is the strongest alternative when the latency target demands tighter tuple location, the requested ranges are extremely narrow, or correlation deteriorates. Measure `pg_stats.correlation`, index size, lossy rechecks, heap blocks visited, and ingestion cost. BRIN is a page-range map, not a promise to match B-Tree latency.
#### The Busy Little Registry: None—Until Measurement Objects
**None** is the defensible opening choice. Ten thousand in-memory rows are cheap to scan, name searches are rare, and the proposed index would join every qualifying update's maintenance bill. The existing primary-key B-Tree already serves identity lookups.
A name B-Tree becomes reasonable if measured search latency or concurrency makes the scan material, or if a business rule requires uniqueness. Verify with representative concurrent load rather than one isolated query. “Small table” and “write-heavy” are clues, not eternal laws; the decision should change when the workload does.
---
### 📝 Summary: The Cost of a Shortcut
Before this chapter, "add an index" may have sounded like the obvious fix for a slow query.
Now you know an index is not free speed. It is a physical bargain: Postgres accepts extra write cost, storage cost, and maintenance cost so future reads can avoid larger work.
The new skill is choosing the right bargain:
- **B-Tree** helps when values need ordering, equality, or range lookup.
- **GIN** helps when a row contains many searchable things.
- **GiST** helps when the notion of "near," "overlaps," or "contains" matters.
- **BRIN** helps when massive tables are physically correlated.
- **Vector indexes** help when exact equality is not the question at all.
The mature move is also knowing when not to index. If the table is small, the predicate is unselective, or the workload is write-heavy, the sequential scan may be the honest answer.
> [!NOTE] Match the Index to the Question
> **Concept**: An index is a shortcut only when it matches the shape of the question.
<div style="page-break-after: always;"></div>