Free lesson · System Design Fundamentals

Indexing Strategy

Medium7 min readsystem-designhlddistributed-systems

Lesson 15.1 - Indexing Strategy

The first lesson of Module 15.

If there's one database optimization that delivers the most value for the least effort, it's indexing. A missing index turns a 5ms query into a 45-second full table scan. Adding the right index brings it back to 5ms - one CREATE INDEX statement, applied in minutes, delivering a 9,000x improvement. Most database performance problems are indexing problems, not database-choice problems, not hardware problems, not architecture problems. Before you migrate databases, add replicas, denormalize, or cache aggressively - check your indexes.

Lesson 14.1 covered how B+ trees work internally. This lesson covers the strategy of indexing - which columns to index, the types of indexes available, composite index design, partial indexes, and the costs of over-indexing.

How Indexes Accelerate Queries

Without an index, a query like SELECT * FROM orders WHERE user_id = 42 must perform a sequential scan - reading every row in the table to find matches. For a table with 10 million rows, that's 10 million row comparisons - regardless of how many rows match.

With a B+ tree index on user_id, the database navigates the tree in 3-4 steps (O(log N)) directly to user 42's rows. If user 42 has 15 orders, the database reads exactly 15 rows - not 10 million.

The improvement grows with table size because the B+ tree depth grows logarithmically (3-4 levels for billions of rows) while sequential scan grows linearly.

Index Types

Primary Index (Clustered)

The table's primary key automatically gets a clustered index - the table data is physically sorted by the primary key. In PostgreSQL, this is the heap's default ordering (though PostgreSQL doesn't maintain strict clustering after the initial CLUSTER command). In MySQL InnoDB, the primary key IS the clustered index - the table data is stored in the B+ tree leaf nodes, sorted by primary key.

Implication: queries by primary key are the fastest possible - the index IS the data. Range queries on the primary key (WHERE id BETWEEN 1000 AND 2000) read consecutive disk pages - sequential I/O.

Secondary Index (Non-Clustered)

An index on any non-primary-key column. The B+ tree leaf nodes contain the indexed column value AND a pointer back to the table row (the heap tuple ID in PostgreSQL, the primary key in MySQL InnoDB). Lookups require two steps: navigate the secondary index B+ tree → find the row pointer → follow the pointer to the table row (a "heap fetch" or "bookmark lookup").

-- Secondary index on user_id
CREATE INDEX idx_orders_user ON orders (user_id);

-- This query uses the index:
SELECT * FROM orders WHERE user_id = 42;
-- 1. Navigate B+ tree for user_id=42 → find row pointers
-- 2. Follow each pointer to fetch the full row from the heap

Composite Index (Multi-Column)

An index on multiple columns, sorted by the first column, then the second within each first-column value, then the third, etc.:

CREATE INDEX idx_orders_user_date ON orders (user_id, created_at DESC);

This index efficiently serves:

• WHERE user_id = 42 - uses the first column ✅
• WHERE user_id = 42 AND created_at > '2026-01-01' - uses both columns ✅
• WHERE user_id = 42 ORDER BY created_at DESC - uses both for filter AND sort ✅
• WHERE created_at > '2026-01-01' - CANNOT use this index efficiently ❌ (the first column isn't filtered - the index isn't sorted by created_at alone)

The leftmost prefix rule: a composite index (A, B, C) efficiently serves queries filtering on A, A+B, or A+B+C - but NOT B alone, C alone, or B+C. The index is sorted by A first; within each A value, sorted by B; within each A+B, sorted by C. Skipping the leftmost column breaks the sort order.

Which Columns to Index

Index columns that appear in: WHERE clauses (filter), JOIN conditions, ORDER BY (sort), and GROUP BY (aggregation). Specifically:

The equality-before-range rule: in a composite index, put equality-filtered columns first and range-filtered columns last. (status, created_at) is better than (created_at, status) for WHERE status = 'active' AND created_at > '2026-01-01' because the B+ tree can narrow to status = 'active' entries first (a tight range), then scan the created_at range within that subset.

Covering Indexes (Index-Only Scans)

If the index contains ALL columns the query needs, the database can satisfy the query entirely from the index - without fetching the table row (no heap fetch). This is a covering index (or index-only scan):

-- Covering index: includes user_id AND created_at AND total
CREATE INDEX idx_orders_covering ON orders (user_id, created_at DESC) INCLUDE (total);

-- This query is satisfied entirely from the index:
SELECT created_at, total FROM orders WHERE user_id = 42 ORDER BY created_at DESC LIMIT 10;
-- No heap fetch needed - all columns are in the index

PostgreSQL's INCLUDE clause adds non-key columns to the index leaf nodes without including them in the sort order. The included columns make the index a covering index for queries that SELECT those columns, eliminating the heap fetch - typically a 2-5x speedup for queries returning few columns.

Partial Indexes

An index on a subset of rows - only rows matching a WHERE condition:

-- Index only active orders (90% are completed - don't waste index space on them)
CREATE INDEX idx_active_orders ON orders (user_id, created_at)
WHERE status = 'active';

This index is smaller (only active orders, not all orders), faster to maintain (completed orders don't affect it), and just as effective for queries that filter on status = 'active'. If 10% of orders are active, the partial index is 10x smaller than a full index - less storage, faster scans, less write amplification.

When to use partial indexes: when queries consistently filter to a subset (active users, recent orders, unpaid invoices, pending tasks) and the subset is much smaller than the full table.

The Cost of Indexes

Indexes aren't free. Every index has costs:

1. Write amplification. Every INSERT updates the table AND every index. Every UPDATE that changes an indexed column updates the relevant index. Every DELETE removes entries from every index. A table with 8 indexes has 9x the write overhead of an unindexed table (1 table + 8 index writes).

2. Storage. Each index consumes disk space. A 100-million-row table might have 5 indexes consuming 3x the table's own storage. Monitor with pg_total_relation_size().

3. Planner confusion. Too many indexes can confuse the query planner - it has more choices, which increases planning time and occasionally leads to suboptimal plan selection.

The rule: create indexes for queries you run frequently. Don't create indexes "just in case." Monitor slow queries (pg_stat_statements), identify which queries lack indexes, and add indexes specifically for those queries.

A Brandon Story: The Query That Didn't Use the Index

A team I'd advised had a users table with 20 million rows and an index on email:

CREATE INDEX idx_users_email ON users (email);

But the query SELECT * FROM users WHERE LOWER(email) = 'alice@example.com' was doing a full table scan - 3 seconds instead of 2ms. Why? The index was on email, but the query filtered on LOWER(email) - a function applied to the column. The B+ tree is sorted by email (case-sensitive), not by LOWER(email). The database can't use the index because the sort order doesn't match the function's output.

The fix: an expression index (also called a functional index):

CREATE INDEX idx_users_email_lower ON users (LOWER(email));

This B+ tree is sorted by LOWER(email) - matching the query's filter exactly. Query time: 3 seconds → 1.5ms.

Other common "index not used" scenarios:

• WHERE phone LIKE '%1234' - leading wildcard prevents index use. Workaround: trigram index (pg_trgm).
• WHERE EXTRACT(YEAR FROM created_at) = 2026 - function on column. Fix: WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01' (range query on the raw column - index-friendly).
• WHERE user_id = 42 OR status = 'active' - OR conditions often prevent single-index use. Fix: two separate indexes + bitmap OR.
• Implicit type casting: WHERE string_column = 123 - integer 123 is cast to string, preventing index use. Fix: WHERE string_column = '123'.

Lessons:

• Functions applied to indexed columns prevent index use. Use expression indexes or rewrite the query to filter on the raw column.
• Always check EXPLAIN ANALYZE to verify the index is actually used.
• The most common cause of "the index doesn't help" is a mismatch between the index's sort key and the query's filter expression.

Six Takeaways from This Lesson

1. Indexing is the #1 read optimization. A missing index turns millisecond queries into multi-second table scans. Add indexes before considering any other scaling technique.

2. Composite indexes serve queries matching the leftmost prefix: (A, B, C) serves A, A+B, A+B+C - but not B alone. Order columns by selectivity and equality-before-range.

3. Covering indexes include all columns a query needs - eliminating the heap fetch for a 2-5x speedup. Use PostgreSQL's INCLUDE clause.

4. Partial indexes cover only a subset of rows - smaller, faster, and less write amplification. Use for queries that consistently filter to a subset.

5. Functions on indexed columns prevent index use. LOWER(email), EXTRACT(YEAR FROM date), LIKE '%suffix' - all break index usage. Use expression indexes or rewrite the query.

6. Every index costs writes. N indexes = N+1 writes per INSERT. Create indexes for queries you actually run, not speculatively.

What's Next

Lesson 15.2 covers vertical partitioning - splitting wide tables by columns to reduce I/O for queries that only need a subset of columns.

Back to System Design Fundamentals