Phase 04: Indexing & Query Optimization¶
Chapter 16: B-Tree Internals (High Concurrency & Page Splits)¶
16.1 Physical B-Tree Anatomy (Lehman & Yao Algorithm)¶
PostgreSQL implements high-concurrency B-Trees based on the Lehman & Yao algorithm. In standard textbook B-Trees, modifying a node requires acquiring locks on parent nodes all the way up to the root. In Lehman & Yao: * Every node on the same level has a Right Link pointer to its immediate sibling page on the right. * Every page has a High Key representing the maximum possible value that can exist in that page. * Concurrency Impact: Readers and writers can traverse downwards without holding read locks on parent pages. If a concurrent writer splits a page, the reader simply follows the Right Link to find the relocated key.
+-------------------+
| Root Page |
+---------+---------+
/ \
+------------+ +------------+
| Internal A |-->| Internal B | (Right Link)
+-----+------+ +------+-----+
/ \ / \
+--------+ +--------+ +--------+ +--------+
| Leaf 1 |--->| Leaf 2 |--->| Leaf 3 |--->| Leaf 4 | (Doubly-linked)
+--------+ +--------+ +--------+ +--------+
16.2 Anatomy of a Page Split¶
Every B-Tree page is 8KB. When an insert occurs on a leaf page that is 100% full: 1. Postgres must allocate a new 8KB index page. 2. Roughly 50% of the tuples from the existing page are moved to the new page. 3. The parent internal page must be updated with the new child pointer. 4. If the parent page is also full, it splits as well (cascading split). * The Performance Penalty: Page splits acquire exclusive locks on index pages, stall concurrent inserts, generate substantial WAL volume, and cause physical index fragmentation.
16.3 B-Tree Deduplication (PostgreSQL 13+)¶
In previous versions, if an index on status contained 1,000,000 occurrences of 'PENDING', the index stored 1,000,000 complete index tuples (Value + 6-byte CTID pointer).
In PostgreSQL 13+:
* Postgres deduplicates duplicate keys into a single index entry containing an array of CTIDs (Posting List).
* Reduces non-unique B-Tree index size by 40% to 75%, dramatically saving memory in shared_buffers.
Chapter 17: Advanced Index Types (GiST, SP-GiST, GIN, BRIN, Hash)¶
17.1 Comparative Matrix: When to Use What¶
| Index Type | Underlying Data Structure | Primary Use Cases | Supported Operators | Storage Size |
|---|---|---|---|---|
| B-Tree | Balanced Multi-way Tree | Equality, range, sorting, unique | <, <=, =, >=, >, BETWEEN |
Medium |
| Hash | Hash bucket array | High-throughput equality | = |
Small–Medium |
| BRIN | Block Range Min/Max | Massive append-only logs/timestamps | <, <=, =, >=, > |
Microscopic (0.1% of B-Tree) |
| GIN | Generalized Inverted Index | JSONB, Full Text Search, Arrays | @>, ?, &&, @@ |
Large (can exceed table) |
| GiST | Generalized Search Tree | Geospatial, geometric, ranges, nearest neighbor | && (overlap), <<, &<, <-> (distance) |
Medium–Large |
| SP-GiST | Space-Partitioned GiST | Non-balanced data (Quadtrees, Trie, IP prefixes) | Geometric, text prefixes, inet | Medium |
17.2 The Magic of BRIN (Block Range Index)¶
Consider a table with 500 million records of server logs with an append-only created_at timestamp:
* A standard B-Tree index will consume ~15 GB of RAM/disk.
* A BRIN index divides the table into physical block ranges (e.g., 128 pages = 1MB on disk). It only records two values per block:
[Min Timestamp, Max Timestamp].
* Size of BRIN index: ~4 MB (3,750x smaller!).
Chapter 18: Index Optimization & Advanced Techniques¶
18.1 Partial Indexes¶
Only index the subset of rows your application actually queries:
-- 99% of orders are 'COMPLETED', only 1% are 'PENDING' or 'PROCESSING':
CREATE INDEX idx_orders_active ON orders (customer_id, created_at)
WHERE status IN ('PENDING', 'PROCESSING');
18.2 Covering Indexes (INCLUDE Clause)¶
An Index-Only Scan occurs when Postgres satisfies an entire query directly from the index without reading the heap table pages at all.
* Pre-PG 11: You had to add extra columns into the B-Tree search key: CREATE INDEX idx ON orders (user_id, total_amount). This unnecessarily grew the B-Tree search space and sorting keys.
* PG 11+: Use INCLUDE:
user_id is stored in the balanced B-Tree tree nodes for searching.
* total_amount and status are only stored as payload on the leaf pages.
* Queries like SELECT total_amount, status FROM orders WHERE user_id = 42; run as pure Index-Only Scans without touching heap pages.
18.3 Multi-Column Index Ordering (Left-to-Right Rule)¶
An index on (A, B, C) can accelerate:
* WHERE A = 1
* WHERE A = 1 AND B = 2
* WHERE A = 1 AND B = 2 AND C = 3
It cannot effectively accelerate:
* WHERE B = 2 (without A)
* WHERE C = 3 (without A)
* Rule: Place high-cardinality equality filter columns first, followed by range/ordering filter columns.
Chapter 19: The Query Planner & Optimizer¶
19.1 Cost Model Fundamentals¶
The planner calculates the estimated "cost" of every possible execution plan (in arbitrary units relative to 1 sequential page read):
* seq_page_cost = 1.0 (Cost to read 1 page sequentially from disk).
* random_page_cost = 4.0 (Default cost for non-sequential seek).
* cpu_tuple_cost = 0.01 (CPU cost to process 1 row).
* cpu_operator_cost = 0.0025 (CPU cost to evaluate an operator/function).
The Modern NVMe SSD Tuning Gotcha:¶
- On magnetic spinning rust (HDD), a random read was 4x slower than sequential read (
random_page_cost = 4.0made sense). - On modern NVMe SSDs, random reads have near-zero seek latency.
- If
random_page_costremains at 4.0, the planner will avoid perfectly valid index scans and foolishly choose sequential scans! - Fix: Set
random_page_cost = 1.1on SSD environments.
19.2 Reading EXPLAIN (ANALYZE, BUFFERS, TIMING)¶
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Index Scan using idx_users_email on users (cost=0.43..8.45 rows=1 width=32) (actual time=0.034..0.035 rows=1)
Index Cond: (email = 'john@example.com'::text)
Buffers: shared hit=3 read=1
Planning Time: 0.124 ms
Execution Time: 0.052 ms
Deciphering Key Metrics:¶
cost=0.43..8.45:0.43: Startup cost (estimated time to return the very first row).8.45: Total cost (estimated time to return all rows).rows=1: Planner's estimate of returned row count.(actual time=0.034..0.035 rows=1): Real wall-clock time in milliseconds and actual rows returned.Buffers: shared hit=3 read=1(CRITICAL):hit=3: 3 pages (24KB) were already inshared_buffersRAM.read=1: 1 page (8KB) was not in memory and required a physical OS read.dirtied=X: Pages modified in memory by this query.written=X: Pages physically flushed to disk during execution.
Chapter 20: Statistics, Histograms & Planner Misestimations¶
20.1 How the Planner Predicts the Future (pg_statistic)¶
When you run ANALYZE, Postgres samples a fraction of table pages (default 30,000 rows determined by default_statistics_target = 100) and populates pg_statistic (accessible via pg_stats):
* n_distinct: Estimated number of unique values in the column.
* most_common_vals (MCV): The most frequently occurring values.
* most_common_freqs (MCF): Frequency percentages of the MCVs.
* histogram_bounds: Divides the remaining data into equal-frequency buckets.
20.2 The Multi-Column Correlation Trap¶
Postgres assumes that column values are statistically independent: $\(P(A \land B) = P(A) \times P(B)\)$
The Real-World Failure:¶
Consider an automobile database:
WHERE make = 'Audi' AND model = 'A4'
* If 1% of cars are Audi (\(P = 0.01\)) and 1% of cars are model A4 (\(P = 0.01\)).
* Postgres calculates estimated rows: \(0.01 \times 0.01 = 0.0001\) (0.01% of table).
* In reality, almost every A4 is an Audi! The actual row count is 100x higher than estimated.
* The planner chooses a Nested Loop Join (believing 1 row will return). In reality, 10,000 rows return, turning the query from 5ms into a 60-second catastrophe.
The Fix: Extended Statistics (PostgreSQL 10+)¶
Postgres now tracks functional dependencies betweenmake and model, ensuring accurate row estimation and fast hash join plans.