Indexing strategies

Introduction

Indexing is an access-path decision: the database stores an additional structure so a known query shape can find a small set of rows without scanning the whole table. Mental model: an index spends storage and write work to buy cheaper reads. The right index follows the predicates, joins, sort order, and columns returned by real queries, and the query plan is the evidence that it helps.

TL;DR

• An index is a separate data structure (usually a B-tree) that can help the database find matching rows in O(log N) instead of scanning every row O(N). Without a useful index, the planner may choose a full table scan.
• Composite index column order matters enormously: the leftmost prefix rule means an index ordered as a, b, c helps queries filtering on a, a+b, or a+b+c, but not b alone or c alone. Put equality columns first, range columns last.
• Covering indexes include all columns a query needs, so the engine may read only the index and avoid table access. This can be a high-impact read optimization for hot query paths.
• Partial indexes index only a subset of rows (for example, rows with status equal to pending). They are small, targeted, and useful when the filtered set is rare.
• Indexes are not free: every affected write usually has one maintenance path per index. A table with 10 indexes can pay roughly 10 index-maintenance costs, depending on the columns changed. Over-indexing can reduce write throughput.

The Problem It Solves

Your SaaS application has been in production for two years. The events table has grown to 200 million rows. The dashboard page loads a list of recent events for the current user:

SELECT event_id, event_type, created_at
FROM events
WHERE user_id = 'usr_8374'
ORDER BY created_at DESC
LIMIT 50;

This query used to return in 3ms. Last week it started taking 4 seconds. Your monitoring shows the database CPU pegged at 95% during business hours, and this query is the top consumer.

You run EXPLAIN ANALYZE and see the problem:

Seq Scan on events  (cost=0.00..4521890.00 rows=847 width=64)
  Filter: (user_id = 'usr_8374')
  Rows Removed by Filter: 199999153
  Planning Time: 0.1 ms
  Execution Time: 4200 ms

A sequential scan. The database is reading all 200 million rows, checking the user_id predicate on each one, and throwing away 199,999,153 rows to return just 847 matches. Four seconds of CPU and I/O to find 847 rows in 200 million.

Caching or read replicas can help other bottlenecks, but this query is slow because the database is doing 200 million comparisons to find 847 matches. The first fix is to give the planner an access path that matches the query.

CREATE INDEX idx_events_user_created ON events(user_id, created_at DESC);

After the index, the same query:

Index Scan using idx_events_user_created on events (cost=0.56..42.15 rows=847 width=64)
  Index Cond: (user_id = 'usr_8374')
  Planning Time: 0.1 ms
  Execution Time: 0.8 ms

In this measured example, the index changes execution from 4,200ms to 0.8ms — about a 5,000x improvement. The result is workload- and cache-dependent, so validate it with the plan and production-like measurements.

What Is It?

A database index is a separate data structure (most commonly a B-tree) that the query engine consults before touching the main table. It maps column values to the physical locations of matching rows, letting the engine jump directly to the data it needs instead of scanning every row.

Analogy: Think of the index at the back of a textbook. Without it, finding every mention of "B-tree" requires reading all 500 pages. With it, you flip to the index, find "B-tree: pages 42, 87, 203" and go directly there. The index is smaller than the book, sorted alphabetically, and maps keywords to page numbers.

A database index works the same way. It is sorted by the indexed column's value and stores pointers to the corresponding table rows. The tradeoff: the index takes up disk space and must be updated on every write, but it turns O(N) scans into O(log N) lookups.

The cost model is straightforward: index reads are O(log N) + K, where K is the number of matching rows. Sequential scans are O(N). For large tables and selective queries (small K relative to N), indexes win by orders of magnitude. For small tables (under 1,000 rows) or queries returning most of the table (more than 20-30% of rows), a sequential scan is actually faster because it avoids the overhead of tree traversal and random I/O.

How It Works

Here's what happens step by step when the query engine uses a B-tree index:

1. Parse the query. The planner looks at the WHERE clause and checks which indexes exist on the referenced columns.
2. Walk the B-tree root to leaf. The B-tree is a balanced tree (typically 3-4 levels deep for millions of rows). Starting at the root, the engine follows pointers down the tree, comparing the search key at each level. Each level halves the search space.
3. Scan the leaf nodes. The leaf level contains the indexed values in sorted order, each with a pointer (ctid in Postgres, row ID in MySQL) to the corresponding table row. For range queries, the engine scans consecutive leaf nodes.
4. Fetch table rows. For each matching leaf entry, the engine follows the pointer to the table heap to read the full row. This is a random I/O operation (the rows may be scattered on disk).
5. Return results. If the index covers all required columns (a covering index), step 4 is skipped entirely, making the query even faster.

For a table with 10 million rows, a B-tree may be 3-4 levels deep. Finding one row may require a few page reads (often around 8 KB per page in this example). Compare that to a sequential scan: 10 million rows at ~100 bytes each is about 1 GB of data to read from disk. Actual I/O depends on the engine, storage, cache, and row layout.

B-tree indexes (the default in Postgres and MySQL) support these operations efficiently: =, <, >, <=, >=, BETWEEN, IN, LIKE 'prefix%' (prefix matches only), and ORDER BY on the indexed column.

Operations they may not support efficiently include a leading-wildcard LIKE pattern (often a fit for full-text or trigram search), broad not-equal or NOT IN predicates, and functions applied to indexed columns. A predicate such as WHERE lower(email) = ? may not use a plain index on email because the engine cannot match the function output to the sorted index values. A functional index such as CREATE INDEX idx_email_lower ON users(lower(email)) can provide a matching access path.

Key Vocabulary and Components

Types / Variations

Composite Index Column Order

A composite index on (a, b, c) is useful for queries on:

• a alone
• a and b
• a, b, and c

But not directly useful for:

• b alone
• c alone
• b and c together

This is the leftmost prefix rule. The engine walks the B-tree from the first column. If you can't filter on the first column, the tree walk starts at the root and scans everything.