Database indexing.

An index turns an O(n) scan into an O(log n) lookup. The wrong one slows every write and silently doubles your storage. The right one is invisible.

Even a perfectly sharded database is slow if every query has to scan every row. Indexes are the data structures that prevent that scan, at the cost of disk space, write amplification, and a planner that can be tricked into ignoring them. This page covers the index types, the trade-offs each imposes, and the queries you can predict will hit them. By the end: you can read an EXPLAIN plan, justify each index in a schema, and recognise the cases where adding one will make things worse.

How an index actually works

A database index is the same idea as the index at the back of a textbook: instead of reading every page to find "B-Tree," you look up the term in a sorted side-list, jump straight to page 142, and read just that page. Without an index a query for WHERE email = 'x@y.com' against a 10M-row table reads every row — a sequential scan. With a B-tree index the engine descends three or four levels, hits a leaf, and follows a single pointer. Roughly: 10,000,000 page reads becomes 4.

Every index has a cost. It typically uses 10-30% of the table's storage for itself. It must be updated on every INSERT, UPDATE, and DELETE — write throughput drops as you add indexes. And the planner now has to choose between them, which is sometimes worse than having only one. Indexes are not free; they are bought.

What you buy

Logarithmic point lookups, ordered range scans, fast sorts on indexed columns, fast joins on indexed keys, primary-key uniqueness enforcement.

What you pay

Storage (often 20% per index), write amplification (each write touches all indexes on the table), planner complexity (the optimiser sometimes picks the wrong one), maintenance windows (large index builds block writes on some engines).

Decision rule

Add an index when a query that runs frequently has a selective predicate on a column that does not already lead an existing index. Read EXPLAIN before and after — the plan must change to confirm the index is being used.

The index types — and where each one wins

"Add an index" usually means "add a B-tree index" because B-trees are the default in Postgres, MySQL, SQL Server and Oracle. But there are at least five distinct index structures in mainstream databases, and each maps to a different access pattern. Pick by the query, not by habit.

Composite indexes and the leftmost-prefix rule

A single-column index on email answers WHERE email = ?. A composite index on (country, city, last_name) answers more — but only certain shapes. The rule is leftmost-prefix: the planner can use the index for any query that uses a prefix of the columns in declared order.

Order the columns by selectivity and predicate shape: equality columns first, then the column you range on, then the column you sort by. (user_id, created_at) is the canonical pattern for "give me this user's recent activity" — equality on user, range on time, leaf walk to the most recent rows.

Covering indexes — when the index is the table

A query that needs columns not in the index has to do a second lookup: index → row pointer → heap fetch → return columns. A covering index includes every column the query reads, so the engine never touches the heap. This is the standard latency optimisation for hot read paths.

-- Postgres: INCLUDE adds non-key columns to the leaf.
CREATE INDEX idx_orders_user_recent
  ON orders (user_id, created_at DESC)
  INCLUDE (status, total_cents);

-- This query is now satisfied entirely from the index:
SELECT status, total_cents
FROM orders
WHERE user_id = 42
ORDER BY created_at DESC
LIMIT 20;

Covering an index roughly halves the I/O for a hot query. The cost is leaf bloat — each leaf page holds fewer rows because each entry is bigger, so the tree gets taller. Worth it for the top three or four queries; not worth it for everything.

Partial and functional indexes

If most of your rows are uninteresting, index only the interesting ones. A partial index covers a slice defined by a WHERE clause; it's smaller, faster to update, and only used when the query's predicate matches.

-- Only 3% of orders are pending; the index covers only those.
CREATE INDEX idx_orders_pending
  ON orders (created_at)
  WHERE status = 'pending';

-- Functional: index lower(email) so case-insensitive lookups hit it.
CREATE INDEX idx_users_email_lower
  ON users (lower(email));

-- Then the query must match the function shape:
SELECT * FROM users WHERE lower(email) = lower('Alice@example.com');

Functional indexes are how case-insensitive search, computed columns, and JSON path lookups become fast. The expression in the query must match the indexed expression exactly — lower(email) is indexed, plain email is not.

Reading EXPLAIN — the only way to verify

The planner picks an access path based on table statistics. Adding an index does not guarantee the planner will use it; EXPLAIN ANALYZE is the only way to know. Look for these access paths and roughly what they mean:

Seq Scan

Reads every row. Acceptable on small tables (a few thousand rows) or when the predicate matches more than ~20% of rows. A red flag on a 10M-row table with a selective predicate.

Index Scan

Walks the B-tree, fetches matching rows from the heap. The good case for selective queries.

Index Only Scan

The index covers all required columns; no heap fetches at all. The fastest path. Aim for this on hot reads.

Bitmap Heap Scan

Builds a bitmap of matching pages, then visits them in physical order. Wins on medium-selectivity queries that match many rows scattered across the heap.

Nested Loop / Hash / Merge Join

The three join algorithms. Nested loop is fast for small driving sides with an indexed inner; hash is the workhorse; merge requires both inputs sorted.

The hard cases

The cases below are the ones that send queries from "OK" to "page during peak."

Practical defaults to start with

1. Index every foreign key. Joins use them; deletes need them to avoid full scans on the child table.
2. Index (tenant_id, ...) as the leftmost column on multi-tenant tables. Almost every query has it.
3. For "user's recent X" patterns, use (user_id, created_at DESC) with INCLUDE for hot read columns.
4. Use partial indexes for "only X% of rows are interesting" — pending jobs, unread messages, active subscriptions.
5. Don't index columns with two or three distinct values unless the table is read-mostly and a bitmap index is available.
6. Set up pg_stat_statements (or equivalent) and review the top 10 queries by total time monthly. That list is your indexing backlog.