# 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 of a large table is an expensive operation. To find a single row without a map, Postgres must read every page from the disk. > [!NOTE] The Click > **Concept**: An index is not a magical database feature. It is just another table. > **Payoff**: Under the hood, an index is a separate physical relation stored on disk. It contains a sorted list of your indexed column values paired with the 6-byte physical pointer (`ctid`) of the original tuple in the parent table. When you index a column, you are literally writing a helper table to speed up searches. ### 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. Data is scattered across the table due to the "Append-Only" architecture: 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. Each index is a trade-off. While they make reading the table fast, they introduce **Write Amplification**. Every time a tuple is inserted, updated, or deleted, Postgres must also update every associated index entry. If you have ten indexes on one table, a single `INSERT` might trigger ten additional physical writes. To counter this write tax, you can query `pg_stat_user_indexes` to monitor index usage. An index that is never read but frequently updated is a performance liability that should be removed to reclaim write throughput. --- ## 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 does not contain the actual data rows. It only contains the keys and the physical addresses (ctids) of where the real rows 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** In internal (non-leaf) pages, Postgres doesn't need to store the full value to guide the search. If it needs to distinguish between "Capybara" and "Dolphin," it might only store "Capy" and "D." This maximizes **Fan-out**, allowing a shallow tree to index billions of rows. **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] Prediction Checkpoint: Mid-Split Search > 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). Index pages in the B-Tree are physically linked horizontally. Every leaf page contains a special pointer at the end of its block (in the Special Space) pointing directly to its **Right Sibling**: 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] Prediction Checkpoint: The Index Write Tax > 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]]**. ### 🧪 Lab Challenge: The Million-Row Wall **The Request**: "Find the exact delivery record for March 25th at 10:00 AM." #### The Naive Solution Without an index, the engine must perform a **Sequential Scan**. It reads every page of the `supply_deliveries` table from disk into memory, checking the `delivery_time` for every single row. ```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. ```yaml Seq Scan on supply_deliveries (cost=0.00..20.50 rows=1 width=30) (actual time=0.045..0.112 rows=1 loops=1) Filter: (delivery_time = '2024-03-25 10:00:00+00'::timestamp with time zone) Rows Removed by Filter: 999 Buffers: shared read=8 ``` #### 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'; ``` #### The Reward 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. ```yaml Index Scan using idx_deliveries_time on supply_deliveries (cost=0.28..8.29 rows=1 width=30) Index Cond: (delivery_time = '2024-03-25 10:00:00+00'::timestamp with time zone) Buffers: shared hit=3 ``` --- ### 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? ### 🧪 Lab Challenge: The Triple-Play (Index-Only Scans) **The Request**: "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'; ``` #### The Reward 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. ```yaml Index Only Scan using idx_deliveries_covering on supply_deliveries (...) Index Cond: (delivery_time = '2024-03-25 10:00:00+00'::timestamp with time zone) Heap Fetches: 0 Buffers: shared hit=3 ``` > [!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 ``` #### The Observation Look at the sibling link columns: - **`btpo_prev`** points to index page `1`. - **`btpo_next`** points to index page `7`. #### The Payoff 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: ### 🧪 Lab Challenge: The Scent Library (GIN Arrays) **The Request**: "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. ```yaml Seq Scan on flavors (cost=0.00..9.25 rows=1 width=105) (actual time=0.012..0.015 rows=1 loops=1) Filter: (scent_notes @> '{Flowery}'::scent_primary[]) Rows Removed by Filter: 99 Buffers: shared hit=1 ``` #### 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]; ``` #### The Reward 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. ```yaml Bitmap Heap Scan on flavors (...) Recheck Cond: (scent_notes @> '{Flowery}'::scent_primary[]) -> Bitmap Index Scan on idx_flavors_scent (...) Index Cond: (scent_notes @> '{Flowery}'::scent_primary[]) Buffers: shared hit=2 ``` > [!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. ### 🧪 Lab Challenge: The Proximity Puzzle (GiST) **The Request**: "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); ``` #### The Reward 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, the engine summarizes entire sections of the table. It records the **Min/Max boundaries** for contiguous ranges of physical pages. ### 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**: By default, Postgres summarizes every **128 pages** (1MB of data). This makes the index thousands of times smaller than a B-Tree. > > **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: ### 🧪 Lab Challenge: The Industrial Label (BRIN) **The Request**: "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. ```yaml Seq Scan on supply_deliveries (...) (actual time=0.045..12.112 rows=2880 loops=1) Filter: (delivery_time >= '2024-01-01' AND delivery_time <= '2024-01-31') Buffers: shared read=1845 ``` #### 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. ```yaml Bitmap Heap Scan on supply_deliveries (...) -> Bitmap Index Scan on idx_deliveries_brin (...) Buffers: shared hit=12 read=42 ``` --- ### 🧪 Lab Challenge: The Correlation Catastrophe **The Request**: "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:** A BRIN index is only as good as the physical correlation of your data. If your data is physically scrambled, BRIN cannot exclude anything, and it becomes completely useless. **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_cosine_ops); -- Find the 5 ingredients that are most similar to a 'Sweet & Sour' profile SELECT ingredient_id FROM flavors ORDER BY flavor_vector <-> '[8, 8, 2]' 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. ### 🧪 Lab Challenge: The Flavor Vector (HNSW vs IVFFlat) **The Request**: "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. ```yaml Limit (cost=4.91..4.92 rows=5 width=12) (actual time=0.082..0.085 rows=5 loops=1) -> Sort (cost=4.91..5.16 rows=100 width=12) Sort Key: ((flavor_vector <-> '[8,2,1.5]'::vector)) -> Seq Scan on flavors (cost=0.00..3.25 rows=100 width=12) ``` #### 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. ```yaml Index Scan using idx_flavors_vector_hnsw on flavors (...) Order By: (flavor_vector <-> '[8,2,1.5]'::vector) Buffers: shared hit=12 ``` > [!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 rule that is physically integrated into the engine's write loop. Before a record is ever committed to the floor of the table, it must pass a series of integrity checks. If a record violates these rules, Postgres does not attempt to "repair" the transaction; it aborts the operation entirely. Integrity is binary: a database is either perfectly consistent or fundamentally broken. #### 1. Local Verification (`CHECK`, `NOT NULL`) These are the most efficient inspections. The engine only needs to look inside the current tuple to ensure a field isn't empty or that a price is positive. Because these checks happen entirely within the memory buffer for that specific record, their performance overhead is nearly zero. ```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 Scan**: If the table you are referencing (e.g., `species`) does not have an index on those IDs, the engine has to perform a **Sequential Scan** of the entire target table just to verify a single record! This is the most common cause of unexplained "insert slowness" in large systems. #### 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 engine only checks once at the end of the entire operation. This is significantly faster for mass updates where you only need to record that a change happened, rather than reacting to every individual tuple. ```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. Every time a trigger knocks over a domino or a constraint checks a map, a write occurs. And every write must be reflected across every map you’ve built. 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 table grew, the total size of those indexes eventually exceeded the database's cache (`shared_buffers`). To insert a single row, the engine could no longer update the indexes in memory. It had to perform random disk reads to fetch index blocks into memory, write the update, and flush them back. 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. This is the primary trade-off of indexing. Every structure created to speed up reads becomes a permanent tax on every write operation. In the database, an index introduces **synchronous overhead**. If you have indexes on `name`, `price`, and `scent_notes`, the engine must wait for three different physical disk writes to complete before it can confirm the success of a single `INSERT`. ### The Write Latency Tax When a new tuple is inserted or an old one updated, the engine must ensure the maps are consistent. This process is strictly **Synchronous**: the engine cannot confirm the success of your `INSERT` until the B-Tree leaf pages, GIN posting lists, and BRIN summaries are all physically updated on the disk. This is the hidden cost of "helpfulness." The more specialized routes you build to help the engine find data, the more weight you place on its shoulders during every modification. ### 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 entirely. If every column you request is already written on the index map, the engine performs an **Index-Only Scan**. In the context of maintenance, this is the ultimate act of laziness. By avoiding the **Heap** (the table) entirely, the engine spares itself from the overhead of fetching shipping containers and inspecting tuple headers. However, this efficiency relies on the maps being perfectly in sync with the reality of the floor—a task managed by the **Visibility Map**. For an Index-Only Scan to work, the engine must be certain the data has not been modified or deleted. It checks the **[[Manuscript/02 - Physical Storage & MVCC/2.4 - Relation (The Table)|Visibility Map (_vm)]]**; if the target page is marked as "All Visible," the engine skips the table visit entirely, completing the query using only the index. ### 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] Prediction Checkpoint: Bypassing the Index Update > 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 Line Pointer Chain**: It does **not** update the indexes. Instead, it alters the item identifier (the line pointer) of the old tuple to point directly to the line pointer of the new tuple. 3. **The Indirection Hop**: Any index scan looking for the row traverses the B-Tree, reads the old `ctid` (e.g., page 5, slot 3), lands on the page, and follows the chain of line pointers (from slot 3 directly to slot 4) to find the new record. Because the B-Tree continues pointing to the old slot, Postgres bypasses index write maintenance entirely. This eliminates index write amplification, reduces WAL volume, and lets the engine update data at maximum speed. To maximize the chance of HOT updates occurring, you can lower a table's **`FILLFACTOR`** (e.g., to 90 or 80) via `ALTER TABLE`. This reserves empty space on every page for future updates, ensuring they can be written to the same physical page. Without this reserve space, updates eventually spill to other pages, breaking the HOT chain. > [!CAUTION] > **The HOT Breaker**: HOT updates **only** work if the updated column is not indexed and the new tuple fits on the same page. If you modify an indexed column, the logical order of the B-Tree has changed, and Postgres *must* write a new entry to the index. ### 🧪 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 ``` #### The Observation 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 are miracles for reading, but they are heavy weights for writing. Every index you add decreases the throughput of your modifications. --- ### 🧪 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 ``` #### The Observation 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**. Adding eight indexes slowed inserts down by **more than 6x**. #### The Payoff Indexes are not free. Every index on a table forces Postgres to execute a synchronous write write-amplification step. When design patterns demand high insert/update volume, limit indexes to query paths that actively require them. ```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**. * **The Payoff**: 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**. * **The Payoff**: 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**. * **The Payoff**: 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] The Click > **Concept**: An index is a shortcut only when it matches the shape of the question. <div style="page-break-after: always;"></div>