Indexing strategies

TL;DR

• An index is a separate data structure (usually a B-tree) that lets the database find matching rows in O(log N) instead of scanning every row O(N). Without indexes, every query is a full table scan.
• Composite index column order matters enormously: the leftmost prefix rule means an index on (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 reads only the index and never touches the table. This is the single highest-impact read optimization for hot query paths.
• Partial indexes index only a subset of rows (e.g., WHERE status = 'pending'). They are tiny, targeted, and dramatically underused.
• Indexes are not free: every write must update every index on the table. A table with 10 indexes pays 10x the write maintenance cost. Over-indexing kills 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.

I'll often see engineers reach for caching or read replicas at this point, but both miss the real issue. This query is slow because the database is doing 200 million comparisons to find 847 matches. The fix isn't more hardware; it's telling the database where to look.

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

From 4,200ms to 0.8ms. A 5,000x improvement from a single CREATE INDEX statement. That is the power of indexing, and understanding which index to create is one of the most practical skills in system design.

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 is typically 3-4 levels deep. Finding one row requires 3-4 page reads (each ~8 KB). Compare that to a sequential scan: 10 million rows at ~100 bytes each is about 1 GB of data to read from disk.

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 do not support: LIKE '%suffix' (needs full-text or trigram index), != and NOT IN (anti-patterns for index use), and functions applied to indexed columns. WHERE lower(email) = ? won't use an index on email because the engine can't match the function output to the sorted index values. The fix is a functional index: CREATE INDEX idx_email_lower ON users(lower(email)).

Key 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.

The golden rule: equality columns first, range columns last. The engine can narrow down equality filters precisely, then scan the remaining range efficiently.

-- Query: WHERE status = 'active' AND created_at > '2026-01-01'
-- Good index: (status, created_at)
--   status = 'active' narrows to exact leaf nodes, then scan created_at range
-- Bad index:  (created_at, status)
--   range on created_at scans wide, can't efficiently use status filter

For your interview: if someone asks how you'd optimize a slow query, the first thing to check is whether the composite index column order matches the query's filter pattern. This single optimization fixes the majority of slow query problems.

Covering Index (Index-Only Scan)

A covering index includes all columns needed by a query, both the filter columns (WHERE) and the select columns (SELECT). The query engine reads only the index, never touching the table's heap pages. This is called an index-only scan.

-- Query: SELECT user_id, created_at FROM orders WHERE status = 'pending'
-- Regular index on (status):
--   Engine finds matching rows via index, then fetches user_id and created_at
--   from the table heap (random I/O for each row)
-- Covering index on (status, user_id, created_at):
--   Index contains everything. No table heap access at all.
--   For 10,000 matching rows, this can save 10,000 random I/O operations.

Covering indexes are larger (more columns stored in the index) but can eliminate table heap reads entirely on hot query paths. In Postgres, you can also use INCLUDE columns that are stored in the index but not part of the B-tree key:

-- Postgres INCLUDE syntax: key on (status), include user_id and created_at
CREATE INDEX idx_orders_status_covering ON orders(status)
INCLUDE (user_id, created_at);
-- The INCLUDE columns are in the leaf nodes but don't affect sort order

My recommendation: for your top 3 most frequent read queries, check if a covering index can eliminate table heap access. This is the single highest-ROI index optimization.

Partial Index

A partial index indexes only rows matching a condition. It is dramatically smaller than a full-table index when the filtered set is a small fraction of rows.

-- Only 1% of orders are pending. Index just those.
CREATE INDEX idx_orders_pending ON orders(created_at)
WHERE status = 'pending';

-- This index is ~100x smaller than indexing all orders
-- Query: SELECT * FROM orders WHERE status = 'pending' ORDER BY created_at
-- Uses the tiny partial index instead of scanning all orders

Partial indexes are underused. They are ideal for:

• Status-filtered queues (WHERE status = 'pending')
• Soft-delete patterns (WHERE deleted_at IS NULL)
• Feature flags (WHERE is_beta = true)
• Any column where one value is queried 100x more than others

The engine only uses a partial index when the query's WHERE clause matches or implies the index's condition. If your query says WHERE status = 'pending' AND created_at > ?, the partial index on WHERE status = 'pending' applies. If your query says WHERE status = 'shipped', it does not.

GIN and GiST Indexes (Postgres)

GIN (Generalized Inverted Index): Designed for values that contain multiple elements, like arrays, JSONB documents, or full-text search vectors. A GIN index on a tags array column lets you efficiently query WHERE tags @> ARRAY['urgent']. For full-text search, GIN on a tsvector column supports @@ text search operators.

GiST (Generalized Search Tree): Designed for geometric and range data. PostGIS uses GiST for spatial queries (ST_DWithin, ST_Contains). Also used for IP range containment (inet type) and nearest-neighbor searches (ORDER BY point <-> target_point).

In interviews, you rarely need to go deep on GIN/GiST. The important thing to say is: "for full-text search I'd use a GIN index on a tsvector column, and for geospatial queries I'd use a GiST index." That shows awareness without over-explaining.

Comparison

Trade-offs

The fundamental tension: every index speeds up reads but slows down writes. There is no free lunch. You are trading write throughput and storage for read latency.

Write Amplification

Every write to the table must also update every index on that table. A table with 10 indexes has 10x the index write cost.

For high-write tables (event logs, click tracking, time-series data), minimize index count. I have seen production systems drop from 15ms insert latency to 2ms by removing 4 unused indexes.

Index Bloat

Postgres B-tree indexes do not shrink when rows are deleted. The space in leaf pages is marked reusable, but the tree height stays the same. High-churn tables (frequent insert + delete cycles) accumulate dead space.

Monitor bloat and act on it:

-- Postgres: find indexes with zero scans (candidates for removal)
SELECT schemaname, tablename, indexname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0 AND idx_is_unique = false;

Selectivity Matters

An index on a boolean column with 50/50 distribution provides almost no benefit. The engine is better off scanning the table. Low-cardinality columns (status with 3 values) are bad standalone index candidates.

The threshold varies by database, but as a rule of thumb: if the query returns more than 15-20% of the table, the planner usually chooses a sequential scan over the index. The random I/O cost of hopping between index and heap is worse than scanning everything sequentially.

When to Use It / When to Avoid

Use indexing when:

• Read-heavy workloads with known query patterns
• Queries filter on specific columns (WHERE, JOIN ON)
• Latency on hot read paths is critical (p50 under 5ms)
• Table is large enough that sequential scan is painful (more than 100k rows)
• You need to enforce uniqueness constraints

Avoid over-indexing when:

• The table is write-heavy with few reads (event logs, audit trails)
• The table is small enough that sequential scan is fast (under 10k rows)
• You are indexing low-cardinality columns without combining with high-cardinality ones
• You already have more than 5-6 indexes on a single table
• Nobody queries on that column (check pg_stat_user_indexes)

Real-World Examples

Uber: Geospatial Indexing at Scale

Uber processes millions of ride-matching queries per second. Each query asks: "find all available drivers within 2km of this GPS coordinate." Without a spatial index, this requires computing distances to every driver. Uber uses geospatial indexes (R-tree / GiST-equivalent) on driver location data to answer these queries in under 10ms. They also use H3 hexagonal grid cells as a hash-based alternative to spatial indexing, where the hex cell ID becomes a simple equality lookup.

Shopify: Composite Index Optimization

Shopify handles over 10,000 requests per second on their storefront. Their orders table is one of the most queried. They found that changing a composite index from (shop_id, created_at) to (shop_id, status, created_at) eliminated 85% of the table heap reads for their most common dashboard query. The status equality filter (equality-before-range rule) let the engine narrow down to a precise range before scanning dates.

Stack Overflow: Covering Indexes

Stack Overflow famously runs on just two SQL Server instances for all read traffic. A major reason this works: aggressive use of covering indexes on hot query paths. The question listing page (their most hit endpoint) uses a covering index that includes the title, score, view count, and creation date. The query never touches the full question row. This lets them serve 6,000 requests per second per server.

How This Shows Up in Interviews

When to Bring It Up

Mention indexing anytime a design discussion involves:

• A database with more than trivial read volume
• A query that filters, sorts, or joins on specific columns
• A requirement for sub-10ms read latency
• Trade-offs between read and write performance

Depth to Demonstrate

• Know the difference between B-tree and hash indexes
• Know how composite index column order affects query performance
• Know what a covering index is and when to use one
• Know that indexes hurt writes and how to quantify the trade-off
• Mention EXPLAIN ANALYZE as the tool for validating index effectiveness
• Know partial indexes exist for filtering rare values

Common Interview Questions

Test Your Understanding

Each scenario simulates a real design decision. Think through your answer before expanding.

1. The Slow Dashboard Query

Your analytics dashboard shows the top 50 orders by revenue for a given merchant in the last 30 days. The query takes 12 seconds on a table with 200M rows. EXPLAIN ANALYZE shows a Seq Scan. What index would you create, and in what column order?

2. Write Latency Spikes

Your order service processes 5,000 inserts per second. After a new feature launch, insert latency jumped from 3ms to 18ms. You discover the orders table now has 12 indexes. Three of those indexes have zero scans in pg_stat_user_indexes. What do you do?

3. The Full-Text Search Problem

Your e-commerce site needs product search. Users type "wireless bluetooth headphones noise cancelling" and expect relevant results in under 100ms. The products table has 5M rows with a name and description column. A LIKE '%bluetooth%' query takes 8 seconds. What do you recommend?

4. Multi-Tenant Index Strategy

You are building a SaaS platform where each tenant has their own orders, customers, and products. All tenants share the same database tables. A large tenant with 10M orders complains their dashboard is slow. Small tenants (1k orders) are fine. How do you structure your indexes?

5. Partial Index vs Full Index

Your notification service has a notifications table with 500M rows. 99.5% of notifications are status = 'sent'. Only 0.5% are status = 'pending' (2.5M rows). The background worker polls for pending notifications every second. Should you use a full index or partial index on status?

6. Index-Only Scan Validation

A colleague creates a covering index (user_id, product_id, quantity, created_at) to optimize a query. They run EXPLAIN ANALYZE and see "Index Scan" instead of "Index Only Scan." What went wrong?

7. Choosing Between Database Indexing and External Search

Your application needs to search across user profiles by name, bio, location, and skills (stored as a JSONB array). The table has 20M rows. Should you use database indexes or an external search engine like Elasticsearch?

Quick Recap

1. B-tree indexes support equality, range, and prefix operations in O(log n) time. They do not help for suffix-match LIKE, functions applied to indexed columns, or queries returning more than 15-20% of rows.
2. Composite index column order follows the leftmost prefix rule. Put equality columns first, range predicates last. The order of columns in the index determines which queries it can serve.
3. Covering indexes include the SELECT columns alongside the filter columns. The engine reads only the index, never the table heap. This is the highest-impact optimization for read-heavy hot paths.
4. Partial indexes index only rows matching a condition. Use them for queue patterns, soft deletes, and rare-value filtering. They are tiny and have minimal write overhead.
5. GIN indexes serve full-text search and JSONB containment queries. GiST indexes serve geospatial and range queries. Know when to mention each.
6. Every index slows writes. A table with 10 indexes pays 10x the maintenance cost per write. Audit with pg_stat_user_indexes and drop unused indexes.
7. Start with no indexes (beyond the primary key). Add them one at a time based on actual slow query logs and EXPLAIN ANALYZE output.

Related Concepts

• Databases: the storage engines that implement these index structures
• Sharding: when a single database with perfect indexes still cannot handle the load, you partition data across servers
• Caching: caching sits in front of the database and reduces the number of queries that hit indexes at all
• Data Partitioning: table-level partitioning works alongside indexing; each partition has its own local indexes