# 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:** A heap B-tree is a separate relation. Its leaf tuples contain indexed key values and heap TID references; they may also carry `INCLUDE` columns, and deduplication can represent many TIDs with a posting list. The authoritative heap tuple and its MVCC header still live in the heap.
#### 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%.
### 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.
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]]**.
### 🧪 Find One Row in a Million — Lab
**Find the March 25 Delivery**: "Find the exact delivery record for March 25th at 10:00 AM."
#### The Naive Solution
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';
```
#### The Fallout
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.
#### The Lazy Fix
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."
#### The Naive Solution
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';
```
#### The Fallout
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`. This is the engine consulting the **Visibility Map** to confirm that the data in the index is visible to your transaction without needing to check the heap headers. If the page is "dirty," the engine might still visit the heap to be safe.
---
> [!NOTE]
> **Logical Ordering (B+ Tree Sibling Links)**:
> Although Postgres refers to this structure as a B-Tree, it is technically a **B+ Tree**. This distinction is critical for **Range Queries** (e.g., `WHERE age BETWEEN 10 AND 20`).
>
> Instead of traversing up and down the tree for every single value in the range, the engine climbs the tree once to find the leaf page holding the starting key (`10`). It then walks horizontally across the leaf pages using the **right-sibling pointers** (links connecting each leaf page directly to the next) until it encounters a key larger than `20`. This horizontal traversal bypasses the internal nodes entirely, minimizing CPU and memory-bus overhead.
---
### 🧪 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.
#### The Setup
Ensure `pageinspect` is installed in your database:
```sql
CREATE EXTENSION IF NOT EXISTS pageinspect;
```
#### The Task
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.
#### Deep Dive: The GIN Access Method
![[Structures/Index/GIN]]
### Implementing a GIN Index
Let's build a GIN index on our ingredient scent notes:
```sql
-- Index every unique element in the array
CREATE INDEX idx_flavors_scent ON flavors USING gin(scent_notes);
-- Searching for all 'Flowery' ingredients
SELECT ingredient_id FROM flavors
WHERE scent_notes @> '{"Flowery"}';
```
The **`@>`** operator is the primary tool for this search—it means "Does this array *contain* these specific elements?"
### Measuring the Inverted Search
Let's observe the speed of this inverted lookup:
### 🧪 Find Every Flowery Ingredient with GIN — Lab
**Match the “Flowery” Array Element**: "Find all ingredients that have a 'Flowery' scent profile."
#### The Naive Solution
Searching inside an array using the containment operator (`@>`) is a complex operation. Without a specialized index, Postgres must perform a **Sequential Scan**. It opens every row in the `flavors` table and inspects the `scent_notes` array manually.
```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM flavors
WHERE scent_notes @> ARRAY['Flowery'::scent_primary];
```
#### The Fallout
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.
#### The Lazy Fix
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 engine uses a **Bitmap Index Scan**. It consults the GIN index to find the entry for "Flowery," retrieves the list of physical addresses (TIDs), and visits only the pages containing matches.
> [!NOTE]
> **The Bitmap Shortcut**: A **Bitmap Scan** is the engine's method of creating a bitmask of matching pages. It sorts these pages by physical address and visits them in order. This ensures Postgres visits every page only once, maximizing I/O efficiency.
> [!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**.
---
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."
#### The Naive Solution
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.
#### The Lazy Fix
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]]
For the gritty details on how these collections are managed, check out the **[[Structures/Index/GIN|GIN Reference]]** and the **[[Structures/Index/GiST|GiST Reference]]**.
---
## 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**: To find the summary for a specific page instantly, BRIN uses a **[[Structures/Index/BRIN|Range Entry Variable Map]]**. This mapping structure tells the engine exactly where to find the Min/Max notes for any given physical page range.
BRIN relies entirely on **Physical Correlation**. For the summary to be useful, nearby physical pages must contain nearby logical values. This is ideal for time-series data or auto-incrementing IDs where data is appended in a predictable order.
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 range query on our large `supply_deliveries` table:
### 🧪 Prune January with BRIN — Lab
**Find Every January Delivery**: "Show me every delivery that arrived in January 2024."
#### The Baseline Strategy
On a table with millions of rows, a Sequential Scan is slow. A B-Tree index would work, but it might consume 20% of the table's disk space.
```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) FROM supply_deliveries
WHERE delivery_time BETWEEN '2024-01-01' AND '2024-01-31';
```
#### The Resource Tax
The engine spends significant CPU cycles reading every page, even though January data only lives in a specific physical section of the file.
#### The Strategic Fix
Create a **BRIN Index**. This summarizes every 128 pages of the table with a single "Min/Max" note.
```sql
CREATE INDEX idx_deliveries_brin ON supply_deliveries
USING brin(delivery_time);
ANALYZE supply_deliveries;
EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) FROM supply_deliveries
WHERE delivery_time BETWEEN '2024-01-01' AND '2024-01-31';
```
#### The Performance Dividend
The engine uses a **Bitmap Index Scan**. It quickly checks the BRIN summaries and skips every 128-page block that doesn't overlap with January. The index size is negligible, but the I/O reduction is dramatic.
---
### 🧪 Break BRIN with an Uncorrelated Column — Lab
**Find Every 5.25 kg Delivery**: "Find all deliveries where the `quantity_kg` was exactly 5.25."
#### The Naive Solution
The `quantity_kg` values are distributed randomly throughout the table. They have **low correlation** with the physical storage order.
#### The Fallout
Even if you create a BRIN index on `quantity_kg`, the planner might ignore it. Why? Because if the quantities are random, every 128-page block will likely have a `Min` of 0.1 and a `Max` of 100.0. The summary "summarizes" nothing—it excludes zero blocks.
```sql
CREATE INDEX idx_deliveries_qty_brin ON supply_deliveries USING brin(quantity_kg);
EXPLAIN ANALYZE SELECT * FROM supply_deliveries WHERE quantity_kg = 5.25;
```
#### The Lesson
BRIN is a tool of **Physical Order**. If your data isn't sorted by the indexed column (e.g., timestamps or serial IDs), the index is ineffective. To fix this, you would need to cluster the table by that column—but in a high-volume environment, maintaining that order introduces significant performance overhead.
**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:** Ensure the `autosummarize` parameter is enabled for BRIN indexes. This ensures that new page ranges are summarized automatically as data is appended to the table.
#### 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.
### The Navigational Leap
When queried with a target Vector, the engine performs an **Approximate Nearest Neighbor (ANN)** search. It starts at a high-level entry point in the graph and "hops" between nodes, repeatedly moving toward neighbors that more closely mirror the target vector. This process continues until it identifies the nearest available matches.
### The Vector Index
To find the perfect flavor match, we create our HNSW index:
```sql
-- Creating the HNSW graph
CREATE INDEX idx_flavors_vector ON flavors
USING hnsw (flavor_vector vector_l2_ops);
-- Find the 5 ingredients that are most similar to a 'Sweet & Sour' profile
SELECT ingredient_id FROM flavors
ORDER BY flavor_vector <-> '[8.0, 2.0, 1.5]'
LIMIT 5;
```
The **`<->`** operator is the engine's similarity metric—it measures the physical "distance" between two conceptual coordinates.
### 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.
### 🧪 Compare HNSW with IVFFlat — Lab
**Find the Five Nearest Flavors**: "Find the 5 ingredients that smell most like a 'Sweet & Sour' profile: `[8.0, 2.0, 1.5]`."
#### 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.
#### The Setup
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);
```
#### The Task
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.
#### The Setup
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);
```
#### The Task
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 database workloads from the Elephant Cafe.
As the Lead Architect, you must select the most appropriate index type for each scenario. Choose from: **B-Tree**, **GIN**, **GiST**, **BRIN**, **HNSW**, or **None**.
---
#### Scenario A: The Scent Profiler
* **The Table**: `flavors(ingredient_id INT, scent_notes scent_primary[])`
* **The Query**: Finding ingredients that contain a specific array of scents (e.g. `'Spicy'` and `'Fruity'`).
```sql
SELECT ingredient_id FROM flavors WHERE scent_notes @> ARRAY['Spicy', 'Fruity']::scent_primary[];
```
* **Your Selection**: **GIN**.
* **GIN Maps Each Element Back to Its Rows**: GIN (Generalized Inverted Index) is designed for composite values. It maps individual array elements (scents) back to their corresponding physical row locations, allowing Postgres to retrieve matched records using bitmap scans without a full table walk.
---
#### Scenario B: The Infinite Ledger
* **The Table**: `supply_deliveries(id BIGINT, delivery_time TIMESTAMPTZ, quantity_kg NUMERIC)`
* **The Scale**: 500 million rows. Data is appended strictly in chronological order (`delivery_time` is physically correlated with page ordering on disk).
* **The Query**: Summarizing quantities over narrow time windows (e.g. a specific week).
```sql
SELECT SUM(quantity_kg) FROM supply_deliveries
WHERE delivery_time BETWEEN '2026-06-01' AND '2026-06-08';
```
* **Your Selection**: **BRIN**.
* **One Megabyte Can Prune 500 Million Rows**: A B-Tree index on 500 million rows would occupy tens of gigabytes of RAM. Because the data is physically sorted by date on disk, a BRIN (Block Range Index) can summarize 128-page blocks using only minimum and maximum date coordinates, requiring less than 1MB of storage while matching B-Tree scan speeds via block pruning.
---
#### Scenario C: The VIP Patron Search
* **The Table**: `animals(id INT PRIMARY KEY, name TEXT, species_id INT)`
* **The Scale**: 10,000 rows. High volume of concurrent point updates on names and species memberships.
* **The Query**: Looking up individual animals by their name.
```sql
SELECT * FROM animals WHERE name = 'Babu';
```
* **Your Selection**: **B-Tree**.
* **Logarithmic Lookup Remains the General-Purpose Default**: B-Tree is the default, high-performance general-purpose index. It supports high concurrency, fits easily in `shared_buffers`, and executes equality matches in $O(\log N)$ search steps.
---
### 📝 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.
### Sources & Further Reading
- [PostgreSQL 18: Index Types](https://www.postgresql.org/docs/18/indexes-types.html)
- [PostgreSQL 18: Multicolumn and Partial Indexes](https://www.postgresql.org/docs/18/indexes-multicolumn.html)
- [PostgreSQL 18: BRIN](https://www.postgresql.org/docs/18/brin.html)
- [pgvector: distance operators and index operator classes](https://github.com/pgvector/pgvector/blob/master/README.md)
- Source trail: `src/backend/access/nbtree/`, `src/backend/access/gin/`, `src/backend/access/gist/`, and `src/backend/access/brin/`.
<div style="page-break-after: always;"></div>