# Chapter 6 — Indexes & Query Optimization By the end of this chapter you will: - Read EXPLAIN ANALYZE confidently - Choose between B-tree, hash, GIN, and BRIN - Know why an index can make a query slower - Compose multi-column indexes that actually get used --- ## The why > A query on a 10-million-row table without an index: 3 seconds. Same query with the right index: 3 milliseconds. A 1000x difference. Indexes are the closest thing to magic in software engineering — but they come with tradeoffs. Every index you add makes writes slower and takes up disk space. This chapter teaches you to make those tradeoffs intelligently. In a library with 10 million books, finding "the book about penguins" without a catalog means walking every aisle. With a card catalog organized by topic, you walk to one drawer, find "Penguins" → "Aisle 42, Shelf 3," and walk there directly. The card catalog takes up space (a whole room of drawers), and adding a new book means updating the catalog too. But for finding books, it's 1000x faster. A database index is exactly that card catalog. It's a separate data structure that maps values to locations. The tradeoff is the same: faster reads, slower writes, more storage. --- ## Core concepts ### How a B-tree index works The default PostgreSQL index type is a **B-tree** (balanced tree). Each node is one disk page (8 KB). Internal nodes store key ranges and pointers. Leaf nodes store the indexed values and pointers to the actual table rows (TIDs — tuple identifiers). ``` [Root: keys 1–500] / \ [Page: 1–250] [Page: 251–500] / \ / \ [1–125] [126–250] [251–375] [376–500] ``` **To find `email = 'alice@example.com'`:** 1. Read root page (1 disk read) → "alice" is between 1 and 250 → follow left pointer 2. Read page 1–250 (1 read) → "alice" is between 126 and 250 → follow right pointer 3. Read page 126–250 (1 read) → find "alice", get TID → read table row (1 more read) 4. **Total: 4 reads** — regardless of whether the table has 1,000 rows or 1 billion. **Why it's O(log n):** Each level of the tree divides the key space. With 200 keys per page and 4 levels, you can index 200⁴ = 1.6 billion rows. Most indexes are 2–4 levels deep. ### Index types and when to use each | Index Type | How it works | Best for | Worst for | |-----------|-------------|----------|-----------| | **B-tree** (default) | Balanced tree, sorted keys | Equality (=), range (<, >, BETWEEN), sorting (ORDER BY), prefix matching (LIKE 'abc%') | Full-text search, complex JSON queries | | **Hash** | Hash table | Equality only (=) | Range queries, sorting, anything other than = | | **GIN** (Generalized Inverted Index) | Inverted index — maps values to rows | Full-text search (`tsvector`), array containment (`@>`), JSONB queries (`?`, `@>`, `?|`) | Simple equality (use B-tree instead) | | **GiST** (Generalized Search Tree) | Balanced tree, extensible | Geospatial (PostGIS), full-text search (alternative to GIN) | Simple equality | | **BRIN** (Block Range INdex) | Maps value ranges to blocks of pages | Very large tables (100M+ rows) with naturally ordered data (timestamps in append-only tables) | Tables without natural ordering, small tables | | **Partial index** | Indexes only rows matching a WHERE clause | Queries that always filter on the same condition: `WHERE deleted_at IS NULL` | General-purpose queries | | **Covering index** | Index includes extra columns (`INCLUDE`) | Queries that need only the indexed + included columns (no table access needed) | Write-heavy tables (larger index = slower writes) | ```sql -- B-tree: default, the workhorse CREATE INDEX idx_users_email ON users(email); -- GIN: for JSONB queries CREATE INDEX idx_events_payload ON events USING GIN(payload); -- GIN: for full-text search CREATE INDEX idx_posts_search ON posts USING GIN(to_tsvector('english', body)); -- BRIN: for massive time-series tables CREATE INDEX idx_sensor_readings_ts ON sensor_readings USING BRIN(recorded_at); -- Partial: for queries that always filter on a condition CREATE INDEX idx_active_users ON users(email) WHERE deleted_at IS NULL; -- Covering: index-only scans (no trip to the table) CREATE INDEX idx_orders_user_total ON orders(user_id) INCLUDE(total, created_at); ``` Start with B-tree. If you need full-text search → GIN. If you have geospatial data → GiST (PostGIS). If you have append-only time-series data with 500M+ rows → BRIN. Every other index type is for specialized use cases you'll recognize when you hit them. ### Multi-column (composite) indexes The order of columns in a multi-column index is critical. The index can only be used for queries that filter on the **leading column(s)** in order. ```sql -- Index on (user_id, created_at) CREATE INDEX idx_orders_user_created ON orders(user_id, created_at); -- ✅ Uses index: matches leading column SELECT * FROM orders WHERE user_id = 42; -- ✅ Uses index: matches leading column + second column SELECT * FROM orders WHERE user_id = 42 AND created_at > '2025-01-01'; -- ✅ Uses index: matches leading column, sorted by second SELECT * FROM orders WHERE user_id = 42 ORDER BY created_at DESC; -- ❌ Does NOT use index: skips leading column SELECT * FROM orders WHERE created_at > '2025-01-01'; -- ⚠️ May or may not use index: matches leading but filters on second with inequality SELECT * FROM orders WHERE user_id = 42 AND created_at BETWEEN '2025-01-01' AND '2025-12-31'; ``` **The rule:** An index on `(a, b, c)` supports queries on: - `a` - `a, b` - `a, b, c` - NOT: `b` alone, `c` alone, `b, c` (skip leading column), or `a, c` (skip middle — partially usable with a filter on `c`) ### Reading EXPLAIN ANALYZE ```sql EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT) SELECT o.*, u.email FROM orders o JOIN users u ON u.id = o.user_id WHERE o.created_at > '2025-06-01' AND o.status = 'paid' ORDER BY o.created_at DESC LIMIT 50; ``` Key fields to inspect: | Field | What it tells you | Good sign | Bad sign | |-------|-------------------|-----------|----------| | `actual time` | Real execution time (startup..total in ms) | < 5ms | > 100ms | | `rows` vs expected | Planner accuracy | Close match | 1 estimated, 50000 actual (stale stats) | | `Buffers: shared hit` | Pages read from memory cache | High number | — | | `Buffers: shared read` | Pages read from disk | 0 is ideal | High number (cold cache or insufficient memory) | | `Seq Scan` | Full table scan | Acceptable on small tables (< 1000 rows) | On large tables with WHERE clause | | `Index Scan` / `Bitmap Index Scan` | Using an index | ✅ | — | | `Index Only Scan` | Index covers all needed columns — no table access | ✅✅ (fastest) | — | | `Sort Method: external merge` | Sort spilled to disk | — | Increase `work_mem` | ### When indexes make queries SLOWER Indexes are not always faster. The query planner may choose a sequential scan when: 1. **The table is small.** Scanning 50 rows sequentially is faster than 3 random index page reads + 50 random table reads. 2. **The query returns a large fraction of the table.** If `WHERE status = 'active'` matches 90% of rows, an index is useless — scanning sequentially is faster than 90,000 random reads. 3. **The index is bloated.** Dead tuples, excessive page splits, or a `fillfactor` that's too low causes the index to be larger than the table. `REINDEX` fixes this. PostgreSQL's MVCC means UPDATEs and DELETEs create dead tuples in indexes, not just tables. An index that was 50 MB when created can bloat to 500 MB after months of heavy writes. Run `pg_stat_user_indexes` to check index size vs table size. Schedule `REINDEX CONCURRENTLY` on bloated indexes. ### PostgreSQL planner internals (what you need to know) The query planner doesn't try every possible execution strategy — that would take hours for a 12-table JOIN. Instead, it uses: - **Cost-based optimization.** Every operation has a cost (sequential page read = 1.0, random page read = 4.0). The planner picks the plan with the lowest total cost. - **Statistics (`pg_stats`).** The planner knows approximately how many distinct values each column has (`n_distinct`), the most common values (`most_common_vals`), and histograms of value distribution. These are updated by `ANALYZE`. - **Genetic query optimizer (GEQO).** For queries with > 12 JOINs, PostgreSQL switches from exhaustive search to a genetic algorithm. Good enough, not optimal. --- ## Real-world example: How GitHub optimized their database GitHub runs one of the largest MySQL deployments (now partly PostgreSQL). A few index-related lessons: 1. **They index every FK.** GitHub learned this the hard way when a seemingly innocent `DELETE FROM users WHERE id = X` (from a support tool) locked the entire `repositories` table for 30 seconds because `repositories.owner_id` had no index. Every FK now gets an index at creation time. 2. **Partial indexes for soft deletes.** GitHub uses soft deletes extensively. Most queries filter `WHERE deleted_at IS NULL`. Instead of indexing the entire `repositories` table, they use a partial index: `CREATE INDEX idx_active_repos ON repositories(owner_id) WHERE deleted_at IS NULL`. The index is 5x smaller and faster. 3. **Covering indexes for hot queries.** The most frequent query — "show me my repositories sorted by recently updated" — was optimized with: `CREATE INDEX idx_repos_owner_updated ON repositories(owner_id, updated_at DESC) INCLUDE(name, description, language)`. The query never touches the table — index-only scan, ~0.1ms. --- ## Common mistakes | Mistake | Why it's wrong | What to do instead | |---------|---------------|-------------------| | No index on FK columns | Every JOIN, DELETE, UPDATE on the parent table scans the entire child table | Add indexes on all FK columns. Always. | | Wrong column order in composite indexes | Index on `(created_at, user_id)` when queries always filter `WHERE user_id = X AND created_at > Y` — index is unusable for the user_id-only queries | Lead with the most selective / most frequently queried column | | Indexing every column | 20 single-column indexes on a table. Each INSERT/UPDATE/DELETE must update 20 indexes. Writes become 10x slower. | Index only what you query by. Use `pg_stat_user_indexes` to find unused indexes and drop them. | | `LIKE '%search'` without a trigram index | B-tree can't handle leading wildcards — always a full scan | Use `pg_trgm` extension: `CREATE INDEX ON products USING GIN(name gin_trgm_ops)` | | Ignoring index bloat | After months of heavy writes, indexes can be 5x larger than necessary and 3x slower | Monitor with `pg_stat_user_indexes`. `REINDEX CONCURRENTLY` periodically. | | Not running `ANALYZE` after bulk changes | Planner uses stale statistics, makes wrong decisions (seq scan instead of index scan) | `ANALYZE table_name;` after bulk INSERT/UPDATE/DELETE operations | | Adding an index in production during peak hours | `CREATE INDEX` locks the table for writes (though `CONCURRENTLY` avoids this) | Always use `CREATE INDEX CONCURRENTLY` in production. It takes longer but doesn't block writes. | --- ## Production notes - **`CREATE INDEX CONCURRENTLY`** never blocks writes, but takes ~2x longer and can't run inside a transaction. If it fails (server crash), it leaves an invalid index — drop it and retry. - **Monitor unused indexes.** `SELECT * FROM pg_stat_user_indexes WHERE idx_scan = 0;` — indexes with zero scans are pure overhead. Drop them. - **`fillfactor` controls index density.** Default 90 means 10% free space per page for future inserts. For append-only tables (never updated), set `fillfactor = 100`. For heavily updated tables, set `fillfactor = 70`. ## Performance notes - **Index-only scans are the holy grail.** If all columns in the query are in the index (either indexed or `INCLUDE`d), PostgreSQL never touches the table. This is 2–10x faster than a regular index scan. - **B-tree indexes are ~2% of the table size per indexed column.** A composite index on 3 columns might be 5–8% of the table. Plan your storage budget. - **`work_mem` affects index creation.** Building a large index requires sorting. If `work_mem` is too small, the sort spills to disk — hours instead of minutes. Set `maintenance_work_mem` higher than `work_mem` (e.g., 1 GB for index creation). ## Security notes - **Indexes can leak data through timing attacks.** An index makes some queries faster than others. In theory, a determined attacker can infer data by measuring query times. For most applications, this is not a concern — but know it exists. - **Indexes contain copies of your data.** If an attacker gains access to the file system (not just the database), they can read index files directly. Encrypt your storage at rest. --- ## Exercises ### Beginner 1. Create a `products` table with 100,000 rows (use `generate_series`). Run `SELECT * FROM products WHERE price > 50;` — note the time and `EXPLAIN ANALYZE` output. Add an index on `price`. Run the same query. Compare. 2. Create a composite index on `(user_id, created_at)`. Write three queries: one that uses the index fully, one that uses it partially, and one that doesn't use it at all. Verify with `EXPLAIN`. ### Intermediate 1. Create a table with 500,000 rows and a JSONB column. Create a GIN index on the JSONB column. Compare query times for `WHERE payload @> '{"action": "purchase"}'` with and without the index. 2. Use `pg_stat_user_indexes` to find an index on your database that has never been used. Drop it. Measure write throughput before and after. ### Advanced 1. Set up `pg_stat_statements`. Identify the top 5 slowest queries in your application. For each, read the `EXPLAIN (ANALYZE, BUFFERS)` output and determine whether a new index, a different index type, or a query rewrite would help. 2. Simulate index bloat: create a table, add a B-tree index, perform 100,000 UPDATEs that change the indexed column. Measure index size before and after. Run `REINDEX`. Measure again. --- ## Interview questions ### Beginner 1. **What is a database index?** A data structure (usually a B-tree) that maps column values to row locations, enabling O(log n) lookups instead of O(n) full table scans. 2. **Why not index every column?** Each index must be updated on every INSERT, UPDATE, and DELETE. Too many indexes dramatically slow down writes and consume disk space. Index only columns you query by frequently. 3. **What is EXPLAIN ANALYZE?** A PostgreSQL command that shows the query execution plan plus actual timing and row counts. It tells you exactly where time is spent — sequential scans, sorts, hash joins — so you can decide what to optimize. ### Senior 4. **Explain when a composite index can and cannot be used.** A composite index on `(a, b, c)` can be used for queries filtering on `a`, `a AND b`, or `a AND b AND c`. It cannot be used (or is severely limited) for queries filtering on `b` alone, `c` alone, or `b AND c` — these skip the leading column. A query on `a AND c` can use the index for `a` but must filter `c` after. 5. **What causes index bloat and how do you fix it?** PostgreSQL's MVCC creates a new version of a row on every UPDATE, leaving dead tuples in both the table and its indexes. Over time, indexes fill with dead tuples and become larger/slower. Fix: run `REINDEX CONCURRENTLY` to rebuild the index, or use `pg_repack` for live table repacking with minimal locking. 6. **Compare B-tree, GIN, and BRIN indexes — when would you use each?** B-tree for general-purpose equality and range queries (95% of use cases). GIN for full-text search (`tsvector`), JSONB queries, and array containment — where you're searching within a value, not for an exact match. BRIN for very large tables (100M+ rows) with naturally ordered data (timestamps in append-only tables) where the index can be 1000x smaller than a B-tree by storing value ranges per block rather than per row. --- ## Summary Indexes are the single most effective performance optimization available. A B-tree index turns an O(n) scan into an O(log n) lookup — milliseconds instead of seconds. But indexes cost: slower writes, more disk space, maintenance burden. The art is knowing which columns to index (FKs, WHERE columns, sort columns), which type to use (B-tree by default, GIN for text/JSONB, BRIN for massive time-series), and when to let the planner do a sequential scan instead. Read `EXPLAIN ANALYZE` fluently. Monitor index usage and bloat. Drop unused indexes. --- ## Quick recall - B-tree: default, covers 95% of cases. GIN: full-text + JSONB. BRIN: massive time-series. - Composite index column order: lead with the most selective / most queried. - Index every FK. Always. - `EXPLAIN (ANALYZE, BUFFERS)` on every slow query. - `Index Only Scan` > `Index Scan` > `Bitmap Index Scan` > `Seq Scan`. - `CREATE INDEX CONCURRENTLY` in production. Monitor unused indexes. `REINDEX` for bloat. --- ## Quiz 1. What does a B-tree index do to query performance? **Reduces lookup time from O(n) (full table scan) to O(log n) — typically 100–1000x faster for large tables.** 2. Why does column order matter in a composite index? **The index is sorted by the first column, then the second within each first-column value. Queries that skip the leading column cannot use the index efficiently.** 3. What's the difference between Index Scan and Index Only Scan? **Index Scan reads the index, then reads the table for additional columns. Index Only Scan reads everything from the index itself — no table access needed, provided all necessary columns are in the index or INCLUDE columns.** 4. When would a sequential scan be faster than an index scan? **When the table is very small (< 1000 rows), or when the query returns a large fraction of rows (> 10–20%), since random I/O from index lookups costs more than sequential I/O.** 5. What does `CREATE INDEX CONCURRENTLY` do differently? **Builds the index without locking the table for writes. Takes ~2x longer and cannot run inside a transaction. On failure, leaves an invalid index.** 6. How do you find unused indexes? **Query `pg_stat_user_indexes WHERE idx_scan = 0`. Drop indexes with zero scans — they provide no read benefit but slow every write.** 7. What is a partial index? **An index that only includes rows matching a WHERE clause, e.g., `WHERE deleted_at IS NULL`. Smaller, faster, and perfect for queries that always use the same filter.**

Chapter 6 — Indexes & Query Optimization

Part of L2