Indexing

A database index is a separate, ordered data structure built over one or more columns of a table. It lets the engine navigate to the rows that satisfy a predicate instead of reading every row. An index trades extra storage and extra work on every write for cheaper reads on the predicates and sort orders it was built for, and for nothing else.

A table with millions of orders can answer WHERE order_id = ? in two ways: scan every row and test it, or descend an access structure to the handful of candidates and fetch only those. Which one the planner picks, and whether that choice is any good, depends on the shape of the index relative to the predicate, the sort order, how many rows match (selectivity) and what the execution plan does with them. An index does not make every query fast; it makes matching queries cheap.

The mental model: an index is a sorted list of keys, each with the address of its row. Sorting is the whole trick. Because the keys are ordered, finding one is a short descent instead of a search, finding a range is a descent plus a walk along neighbours, and getting rows back in order costs nothing extra. Every other behaviour in this lesson follows from that: why column order in a composite index matters, why a function wrapped around a column breaks it, why a predicate matching half the table ignores it, and why every extra copy has to be updated on each write. This lesson is written with PostgreSQL syntax and behaviour unless another engine is named; the concepts transfer, the details (page layout, locking, plan output) do not.

Most relational databases default to a B-tree-family index. Internal pages hold separator keys and pointers to child pages and guide a search downward. Leaf pages hold the indexed keys together with a row locator, or with the row's other columns, depending on the engine. Leaf pages are linked in key order, so the structure supports equality lookups, range scans and ordered traversal with the same machinery.

Read the figure left to right. The scan has no shortcut: its cost is the table size. The descent touches one page per level, and each page holds hundreds of keys, so the tree stays shallow even for very large tables. BETWEEN, <, >, prefix LIKE 'abc%' (with the right operator class or collation) and ORDER BY all reuse the same leaf chain: descend once to the start key, then walk right until the range ends. That is why an index on a timestamp serves both WHERE created_at >= ? and ORDER BY created_at LIMIT 20.

Where the row lives differs by engine, and it changes the cost of a lookup. PostgreSQL stores table rows in an unordered heap; every index entry carries a tuple identifier (page and offset) into the heap, so an index lookup is index pages plus a heap page. InnoDB (MySQL) stores the table itself as a B-tree ordered by the primary key, and a secondary index stores the primary key value as its row locator, so a secondary-index lookup is a descent of the secondary tree followed by a descent of the primary-key tree. In both designs the index hands you a locator and a second hop finishes the job, unless the index already contains every column the query needs (see covering indexes below).

How shallow is shallow?

Height is the number of pages from root to leaf, and it grows with the logarithm of the row count to the base of the fanout, the number of keys that fit in a page. With 8 KB pages and a narrow key such as a bigint, a few hundred entries per page is realistic; wide keys such as long strings give a smaller fanout and a taller tree. Use the calculator to see how little the height moves while the scan cost grows linearly.

With 300 keys per page, 10,000 rows need 2 levels, 10 million need 3 and 50 million need 4. The number of rows grew 5,000-fold and the number of levels on the path doubled, from 2 to 4. The default scenario shows the other side: at 80 rows per heap page, 50 million rows are 625,000 heap pages, roughly 5 GB of reading. The upper levels of the tree are hot, so in practice they sit in the buffer cache and a point lookup usually costs one or two real page misses.

Be careful not to turn this into a latency claim. Counting pages ignores the things that dominate real queries: whether those pages are in cache or need storage reads, the extra heap page per matching row, visibility checks, and the volume of rows returned. You will see the shorthand "O(log n)" for index lookups; the more useful statement is that the index traversal is nearly flat in table size, while everything that scales with the number of matching rows still scales. (A figure of about 23 for 10 million rows is log base 2, the depth of a binary search tree. A B-tree is much shallower, but its unit of work is a page, not a comparison.)

B-tree is the default, not the only index

The index vocabulary maps onto this structure. A primary key index enforces uniqueness and non-nullness and is created for you. A secondary index is any additional index you create for a query pattern. A unique index additionally rejects duplicate keys, which makes it a correctness tool as well as a performance one. A composite index spans several columns, and a partial index covers only some rows. Full-text search, geospatial, JSON containment and nearest-neighbour vector search do not use a plain B-tree: PostgreSQL offers GIN, GiST, BRIN, hash and extension-provided index types for them, and other engines have their own equivalents. Those belong to the specialized data stores lesson; the rest of this one is about B-trees because they carry most OLTP workloads.

The buffer cache, page size and write-ahead log that sit under these pages are covered in Database Foundations.

An index on (a, b, c) is one sorted list ordered by a, then by b within equal a, then by c within equal (a, b). A predicate is efficient when it describes one contiguous slice of that order. For WHERE tenant_id = ? AND created_at >= ? ORDER BY created_at DESC, an index on (tenant_id, created_at DESC) is the natural candidate: the equality on the leading column selects one tenant's block, inside which entries are already sorted by time. An index on (created_at, tenant_id) sorts by time first, so the same tenant's entries are scattered across the whole time range and the scan reads and discards other tenants' entries.

-- PostgreSQL. Keyset-paginated order history for one tenant.
CREATE INDEX idx_orders_tenant_created
ON orders (tenant_id, created_at DESC, id DESC);

SELECT id, created_at, status
FROM orders
WHERE tenant_id = 17
  AND (created_at, id) < (TIMESTAMPTZ '2026-10-01 12:00:00+00', 9000)
ORDER BY created_at DESC, id DESC
LIMIT 50;

In the left panel the seek lands directly on the first entry below (17, 2026-10-01 12:00, 9000). The entry (17, 12:00, 9100) shares the timestamp but is excluded by the tuple comparison, because 9100 < 9000 is false; the engine never even visits it. Four entries come back in exactly the requested order with no sort step, and with LIMIT 50 the scan stops the moment it has 50. The right panel can also start at the timestamp bound, but it has to examine every other tenant's entries in that range. It still "uses the index", which is why the sentence "the index is used" is a poor health check. What matters is how many index entries are examined per row returned.

That gives a practical rule for column order: put columns compared with equality first, then the column used for range filtering or ordering, and place a column last when it only needs to be stored or filtered after the range. It is a rule for your queries, not a universal formula. The folklore of putting the most selective column first works only when queries actually lead with that column. Order matters when predicates differ in kind: with equalities on both columns, (status, user_id) and (user_id, status) serve WHERE user_id = 7 AND status = 'active' equally well, but only the second also serves WHERE user_id = 7 alone, and only an index with the range or sort column last serves a range on that column. Choose the order from the set of queries the index has to serve, not from a formula.

The simple form of the leading-column rule, "a query can only use the leftmost prefix", is a good default and not a law. A query that skips the leading column can still scan the whole index in order and filter it, which is cheaper than scanning the table when the index is narrower but is a full pass nonetheless. Some engines add skip-scan strategies that probe each distinct value of the leading column: Oracle, MySQL 8.0.13 and later in some cases, and PostgreSQL 18 for suitable queries. SQLite 3.51 can do this too: with statistics gathered by ANALYZE, its planner can report SEARCH orders USING COVERING INDEX idx (ANY(tenant_id) AND created_at>?) for a query that ignored tenant_id. Which of these happens, and whether it is faster than a plain scan, depends on how many distinct leading values exist. Always check the plan on the target engine and version.

Three details in the SQL above deserve care. First, the tuple comparison (created_at, id) < (…, 9000) and the index ordering created_at DESC, id DESC have to agree in direction; if the query sorted by created_at DESC, id ASC the single index above could not serve it as one ordered walk. Mixed-direction sorts need an index declared with the same mix. Second, the example assumes created_at is NOT NULL; in PostgreSQL, DESC puts nulls first by default, and tuple comparisons involving NULL evaluate to unknown, so null handling has to be designed rather than assumed. Third, the trailing id is what makes the ordering unique, which is what lets the next page resume exactly where this one ended; the Pagination lesson covers the cursor contract. This example is PostgreSQL-oriented; other engines support row-value comparison with different optimizer behaviour, and some need the expanded form created_at < ? OR (created_at = ? AND id < ?) to use the index well.

Selectivity decides whether the index is worth using

Using a secondary index to fetch rows means jumping to the heap for each match. Those jumps are random page reads, which are more expensive per page than the sequential reads of a scan, and a scan reads each page once however many rows on it match. As the matched fraction grows, a point is reached where reading the whole table sequentially is cheaper than following thousands of pointers, and a sane planner switches. That is not a bug and adding hints is rarely the right response.

The model is deliberately simple: one unit per sequential page, random_page_cost units per random page (PostgreSQL's default is 4; values near 1.1 are common on SSD storage), and one heap page per matching row up to a cap of one visit per page. It is not the planner's real formula, which also considers correlation between index order and heap order, bitmap scans that sort page visits to make them more sequential, and CPU costs. But it makes the right point about magnitude. With 80 rows per page and the default random cost, the crossover is at 1 ÷ (80 × 4), about 0.3% of the table; at 1.1 it is about 1.1%. A predicate matching half the table is nowhere near the crossover, and a low-cardinality column such as a boolean or a five-valued status is a poor stand-alone index candidate unless one value is rare and that value is the one you query.

Covering indexes

When every column a query needs lives inside the index, the engine can answer from the index alone and skip the second hop. PostgreSQL calls this an index-only scan and lets you add non-key columns with INCLUDE. The caveat is visibility: PostgreSQL's MVCC keeps row-version visibility in the heap, so an index-only scan consults the visibility map and falls back to heap fetches for pages not yet marked all-visible. A write-heavy table that vacuum cannot keep up with gets little benefit. A wider index is also bigger, slower to update and less cache-friendly, so cover the queries that matter, not every query.

-- PostgreSQL 11+. status is stored in the leaf entries but is not part of the search key.
CREATE INDEX idx_orders_tenant_created_cov
ON orders (tenant_id, created_at DESC, id DESC) INCLUDE (status);

-- Can now be answered by an Index Only Scan. EXPLAIN (ANALYZE) reports "Heap Fetches: N";
-- N stays near zero only while VACUUM keeps the visibility map current.
SELECT id, created_at, status
FROM orders
WHERE tenant_id = 17
ORDER BY created_at DESC, id DESC
LIMIT 50;

Partial indexes

A partial index stores entries only for rows matching a predicate. If 2% of orders are pending and workers constantly ask for the oldest pending ones, an index over just those rows is a fraction of the size of a full index, cheaper to maintain (rows that are not pending are never written into it) and more likely to stay in cache. The planner can use it only when it can prove that the query's condition implies the index predicate, so the query has to state the same condition, with a literal.

-- PostgreSQL. Indexes only the rows a work-queue style query cares about.
CREATE INDEX idx_orders_pending
ON orders (created_at)
WHERE status = 'pending';

-- Usable: the query's WHERE clause implies the index predicate.
SELECT id FROM orders
WHERE status = 'pending' AND created_at < now() - interval '1 hour'
ORDER BY created_at
LIMIT 100;

-- With a bind parameter (status = $1) the planner can only use the partial index
-- when it plans for the literal value. A cached generic plan cannot prove $1 = 'pending'.

Expression indexes and sargable predicates

An index over lower(email) supports case-insensitive lookups, but only for queries that repeat that exact expression; a plain index on email is invisible to WHERE lower(email) = ?, because the index is ordered by email, not by its lowercase form. The same holds for casts and arithmetic on the indexed column. The fix is either an index on the expression that the query actually uses, or rewriting the predicate so that the bare column is compared with a computed value, as the date range in the example below does. Collation matters too: "lowercase" and "equal" are defined by locale rules, and an index only agrees with a query that uses the same collation. In MySQL, comparing a string column with a numeric literal converts the column side row by row and silently defeats the index; PostgreSQL would reject the mismatched comparison, but a cast written by an ORM can produce the same effect. A related PostgreSQL detail: in a non-C locale a plain B-tree does not support LIKE 'abc%' prefix searches unless it is built with text_pattern_ops. A pattern with a leading wildcard, LIKE '%abc', cannot use any ordinary B-tree.

-- PostgreSQL. The query must repeat the indexed expression.
CREATE UNIQUE INDEX users_email_lower_uq ON users (lower(email));

SELECT id FROM users WHERE lower(email) = lower('John@Example.com');   -- can use the index
SELECT id FROM users WHERE email ILIKE 'john@example.com';              -- cannot use it

-- Wrapping a column in a function or cast hides it from a plain index:
SELECT id FROM orders WHERE created_at::date = DATE '2026-10-01';       -- not index-friendly
SELECT id FROM orders                                                    -- same rows, index-friendly
WHERE created_at >= TIMESTAMPTZ '2026-10-01 00:00:00+00'
  AND created_at <  TIMESTAMPTZ '2026-10-02 00:00:00+00';

The optimizer does not run your query to choose a plan. It estimates how many rows each step will produce using table statistics (row counts, distinct counts, most-common values and histograms) plus assumptions, such as independence between predicates, and then picks the cheapest-looking plan under its cost model. When the estimates are right it usually chooses well. It goes wrong in predictable ways: skewed data where one tenant owns most of the table, statistics that were gathered before the data changed, predicates on correlated columns (city and postal code) that the planner multiplies as if independent, and parameter-sensitive queries where a plan cached for a rare value is reused for a common one. Prepared statements in PostgreSQL may switch to a generic plan after several executions, which is built without the actual parameter value.

The three plans are hand-written illustrations of one query, not captured output. The first is the happy case. The second is the usual regression: the estimate is off by about a thousandfold, the plan is a bitmap scan plus a sort sized for a small result, about 1.85 million rows are read and sorted to keep 50, and most heap pages are read from storage. The third shows an index that delivers rows in the requested order, so the plan has no sort node and the limit stops the scan early. In that plan the child node reports far fewer actual rows than estimated, which looks alarming and is not. Row estimates under a Limit describe the full result the node could produce; the actual count is how many it produced before it was stopped.

Diagnose with the actual plan, not the estimated one. Compare estimated and actual rows at each node, loop counts (a nested loop executed 400,000 times is a different query from one executed once), buffer counts split into hits and reads, sort methods and whether they spilled to disk, and timing. In PostgreSQL that is EXPLAIN (ANALYZE, BUFFERS); other engines have equivalents (EXPLAIN ANALYZE in MySQL 8.0.18+, actual execution plans in SQL Server). Remember that EXPLAIN ANALYZE executes the statement. A SELECT is only expensive; an UPDATE or DELETE really changes data unless wrapped in a transaction that you roll back, and rolling back does not undo side effects outside the transaction.

-- PostgreSQL. EXPLAIN ANALYZE executes the statement.
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, created_at, status
FROM orders
WHERE tenant_id = 17 AND status = 'shipped'
ORDER BY created_at DESC
LIMIT 50;

-- For INSERT/UPDATE/DELETE, roll back. Side effects that escape the transaction
-- (trigger-driven calls, sequence advances, locks held until rollback) still happen.
BEGIN;
EXPLAIN (ANALYZE, BUFFERS)
UPDATE orders SET status = 'archived' WHERE created_at < now() - interval '2 years';
ROLLBACK;

When the estimate is the problem, fix the estimate. Refresh statistics with ANALYZE; raise the statistics target for skewed columns; declare extended statistics for correlated columns so the planner stops multiplying selectivities that are not independent. If it is parameter sensitivity, test the query with both the common and the rare value and consider whether the plan should differ for them. If the plan is right but slow, the answer is usually a better index or a different query, not a planner hint.

-- PostgreSQL. Refresh statistics, then teach the planner about correlated columns.
ANALYZE orders;

CREATE STATISTICS orders_tenant_region (dependencies)
  ON tenant_id, region FROM orders;
ANALYZE orders;

-- Finer histogram for a skewed column (default statistics target is 100).
ALTER TABLE orders ALTER COLUMN status SET STATISTICS 500;
ANALYZE orders;

Every index you add must be updated when rows are inserted, deleted, or when an indexed column changes. An insert into a table with eight secondary indexes writes one table row and eight index entries; at 10,000 inserts per second that is 80,000 index insertions per second on top of 10,000 table writes. Each of those may split a leaf page, dirty a buffer, and emit write-ahead-log records that replication has to ship. Indexes also take disk, compete with table data for cache, add vacuum or cleanup work and lengthen every schema migration and restore. The count in the figure is exact; the cost per entry is not constant, so treat the figure as a way to see the multiplier, not as a throughput prediction.

Updates are more nuanced than inserts and engine-specific. PostgreSQL can avoid touching any index for an update that changes no indexed column and fits on the same heap page (a heap-only tuple), so adding an index on a frequently updated column removes that fast path for every update of that column. InnoDB secondary indexes hold primary key values, so a non-indexed column update leaves them alone, while an update to the indexed column removes and re-adds an entry. Deletes are usually deferred cleanup: entries are marked dead and reclaimed later by vacuum or purge. On a heavily updated table B-tree pages are reused after cleanup but rarely returned to the operating system, so an index can end up larger than its live data warrants (bloat). Periodic rebuilds, such as REINDEX CONCURRENTLY in PostgreSQL 12 and later, fix it, and measuring index size against live row counts tells you when to bother.

Unique indexes are special: they are also concurrency control. Two transactions inserting the same key cannot both succeed; in PostgreSQL the second waits for the first to commit or abort, then fails with a unique violation or proceeds. That is why a unique constraint is the dependable tool for preventing duplicate claims, and why it is discussed with isolation in Transactions and Concurrency and with constraint design in Data Modeling. It also means a unique index cannot be dropped on cost grounds alone: it is enforcing an invariant.

Finding indexes that cost more than they earn

Measure the workload before adding an index for every column, and measure again before removing one. The statistics view below lists how often each index has been scanned since counters were last reset, with size. Treat a zero as a lead, not a verdict: statistics reset on some operations, counters are per server so an index used only on a read replica shows no scans on the primary, and a quarterly report may be the only thing that needs it. Also exclude indexes that back unique or primary key constraints, as the query does.

-- PostgreSQL. Which non-unique indexes on orders are never scanned, and what do they cost?
SELECT s.indexrelname,
       s.idx_scan,
       pg_size_pretty(pg_relation_size(s.indexrelid)) AS size
FROM pg_stat_user_indexes s
JOIN pg_index i ON i.indexrelid = s.indexrelid
WHERE s.relname = 'orders'
  AND NOT i.indisunique
ORDER BY s.idx_scan ASC;

Building an index on a live table

A plain CREATE INDEX on a large table blocks writes for the duration of the build. Most engines have an online alternative, and its exact behaviour is database-specific. In PostgreSQL, CREATE INDEX CONCURRENTLY allows writes during the build at the price of scanning the table twice, waiting for older transactions to finish, using more I/O and running longer. It cannot run inside a transaction block, and if it fails it leaves an invalid index that is still maintained on every write until you drop it. Build during a quiet period, watch replication lag and I/O, and for how a migration fits into a deployment see the schema-change discussion in Data Modeling.

-- PostgreSQL. Builds without blocking writes; cannot run inside a transaction block.
CREATE INDEX CONCURRENTLY idx_orders_tenant_created
ON orders (tenant_id, created_at DESC, id DESC);

-- A failed concurrent build leaves an INVALID index that still taxes every write.
SELECT indexrelid::regclass AS broken_index
FROM pg_index
WHERE NOT indisvalid;
-- then: DROP INDEX CONCURRENTLY <name>; and retry.

-- Rebuild a bloated index without a long write lock (PostgreSQL 12+):
REINDEX INDEX CONCURRENTLY idx_orders_tenant_created;

Indexes optimize access to rows, not the shape of the request. SELECT * pulls every column from the heap, defeating covering indexes and moving wide values (large text and JSON) through the network for a screen that shows four fields. Deep OFFSET pagination is the classic case: even with a perfect index, the engine must walk and discard the skipped entries, so page 2,000 costs 2,000 times more than page 1. The cost is one more reason, besides drift and duplicates when rows are inserted mid-pagination, to prefer keyset (cursor) pagination for large or growing result sets.

-- Anti-pattern: cost is proportional to the offset.
SELECT id, created_at, status
FROM orders
WHERE tenant_id = 17
ORDER BY created_at DESC, id DESC
LIMIT 50 OFFSET 100000;

-- Keyset: cost is independent of how deep the reader is. The two values come
-- from the last row of the previous page (same query as the composite-index example).

Keyset pagination trades random access for constant cost: you can step forward and back but cannot jump to an arbitrary page, and the sort key has to be total, which is why the examples carry id as a tiebreaker. The Pagination lesson covers cursor encoding and API design.

Other problems stay put however perfect the index is. An application that issues one query per row of a list (N+1) pays network round trips and per-query overhead that no index removes; batch or join instead. Lock contention on hot rows is a concurrency problem solved by transaction design, not by an access path. An unbounded result set of two million rows is expensive to produce, transfer and hold in memory with any index. A predicate with a function or implicit cast on the column from the previous section sidesteps the index outright. And once the table is partitioned or sharded, whether a query touches one partition or all of them matters more than any single-node index; see Scaling Databases. Look at the entire request path before reaching for CREATE INDEX.

The query from Figure 4 was written when the table held 10,000 rows. It filters by tenant and status, sorts by time and returns the first 50 rows, and it used a simple index on tenant_id. Fifty million rows later it takes seconds, p99 for the endpoint has tripled, and the database CPU graph has a new plateau. Nothing in the code changed. What changed is that one tenant's slice went from hundreds of rows to millions, and the plan that was fine for hundreds is a poor one for millions.

In the second plan of the comparison above the planner expects a broad range, reads the matching heap pages, then sorts everything to discard all but 50. Both the page fetches and the sort work scale with the number of rows that match, not with the 50 the caller wanted. This is the right shape of the investigation, in order:

1. Capture the actual plan with buffers for the slow parameter values, not for a typical tenant. Compare estimated and actual rows at every node and look for a sort that spills or a heap scan that reads far more pages than the output rows justify.
2. If the estimate is far from the actual count, refresh statistics and look for skew or correlated columns. That may be the whole fix.
3. If the estimate is accurate and the work is simply large, change the work. An index on (tenant_id, status, created_at DESC) returns matching rows in the requested order, so the sort disappears and LIMIT 50 terminates the scan after 50 entries (third plan).
4. Check the query itself: does the endpoint really need SELECT *, is deep OFFSET hiding behind the page parameter, are there results nobody reads? Rewriting the query or changing the pagination strategy is sometimes a larger win than any index.
5. Before shipping a new index, estimate its write cost from Figure 5, build it with the online method, verify the new plan on production-sized data and check that an older, now redundant index (here the one on tenant_id alone, since the new one has it as a prefix) can be dropped.

Prevention is mostly habit: keep a staging dataset that resembles production in size and skew, run EXPLAIN on every new query that touches a large table, and alert on slow-query patterns instead of waiting for the table to cross a size at which they become visible.

An index is the right tool when a frequent or latency-sensitive query selects a small fraction of a large table by columns you can order, and when the write cost is acceptable for the table's change rate. The clearest cases are lookups on high-cardinality columns (login by email, order by id), foreign-key columns used in joins and cascading deletes (PostgreSQL does not index referencing columns automatically, so deleting a parent row scans the child table without one), and filter-plus-sort queries served by a composite index. It is the wrong tool for columns almost never queried, for low-cardinality columns with no skew to exploit, for predicates matching most of the table, and for tables so write-heavy that every additional structure costs real throughput. Full-text, geospatial and vector search need their own index types rather than B-trees, as the specialized data lesson explains.

What to measure to know it is working, not just that it exists:

• Per-query latency percentiles and call counts (in PostgreSQL via pg_stat_statements), so a regression shows up as a query, not as a general feeling of slowness.
• Estimated versus actual rows, rows removed by filter, heap fetches in index-only scans, sort spills and buffers read versus hit in plans for the queries that matter.
• Per-index scan counts and size against live row counts, to find unused and bloated indexes before they cost a write-heavy table its throughput.
• Write latency, WAL volume and replication lag after any index change, since the cost of an index shows up on the write path and on replicas, not on the read you were optimizing.
• Duration and I/O of the build itself for any index on a large table, and the fraction of cache your hot indexes occupy.

Anything that depends on how an index supports a guarantee, such as unique claims against double-booking or the validity of a cursor under concurrent writes, is a transaction-semantics question rather than a performance one; start with Transactions and Concurrency.