Indexes & Access Paths

A B+tree is a balanced tree of page-sized nodes. Internal nodes store only separator keys and child pointers used to route a search downward. Leaf nodes store every indexed key in sorted order with a pointer to the row. A lookup descends root to leaf.

Fanout is how many children one node points to, roughly page size divided by entry size — often several hundred. Height is about log-base-fanout of the row count, so with fanout ~500 three levels index ~125 million keys and four levels index billions.

In a classic B-tree, payload lives in every node; in a B+tree, only leaves carry keys with row pointers and internal nodes hold pure separators. That keeps branch entries tiny, so fanout is higher and the tree shallower, and all data sits in one sorted, linked leaf level.

Wider entries mean fewer per page, so fanout drops several fold. The tree grows taller and, more importantly, the index occupies far more pages, so much less of it fits in cache. Result: more page reads per lookup and more memory pressure.

Four levels means four logical page accesses, but the root and upper internal levels are tiny and stay cached, so typically only the leaf access — and then the row fetch — can be physical. Expect roughly zero to two real reads on a warm cache.

All entries live in leaf pages, sorted by key, and the leaves are chained to their neighbours in key order. So the engine descends once to the first matching key and then walks the chain until the range ends, reading entries already in order.

It allocates a new page, moves roughly half the entries into it, links it into the leaf chain, and pushes a separator key up to the parent. If the parent is also full it splits too, and splitting the root adds a level to the tree.

Increasing keys always land at the rightmost leaf, so engines split it lopsidedly (nearly all entries stay), pages fill densely, and writes stay concentrated and sequential. Random keys split pages all over the index, settling near two-thirds density with scattered, cache-hostile writes — but they avoid the rightmost-page contention hot spot.

An index scan emits entries in key order, so the planner can drop the sort. Descending output comes from walking the leaf chain backwards, which requires backward sibling links (or an equivalent). The engine sorts anyway when the ordering does not match the index, or when a full scan plus sort is cheaper.

Textbook B+trees merge or redistribute when a page drops below half full, removing a separator from the parent and possibly shrinking the tree. Real engines mostly defer: entries are marked dead, only fully empty pages are recycled, because merging needs multi-page locking and MVCC forbids early removal.

A hash function turns the key into a bucket number. The engine reads that one bucket, compares the stored keys against the search key (different keys can collide), and follows the matching entry's row pointer. Roughly constant cost, equality lookups only.

A hash function deliberately scatters keys: values that are adjacent in sort order land in unrelated buckets, and a prefix hashes to something unrelated to the whole value. The index stores no ordering, so ranges, prefixes, and sorted output are impossible without reading every bucket.

Colliding keys simply share a bucket; the engine stores both and resolves it by comparing actual keys on read. When a bucket fills it chains an overflow page, or the index splits buckets to spread entries. Long chains turn constant-cost probes into linear scans.

Choose hash only for high-cardinality columns queried exclusively by exact equality, especially with long keys where hash entries are much smaller. B+trees win by default because an equality probe is already near-free once upper levels are cached, and the same index also serves ranges, ordering, prefixes, and uniqueness.

Use (status, created_at). Equality columns come first, the range column last. A range predicate on a leading column scatters the columns after it, so only one range column can be used for the seek and it must be the final key column used.

The index is sorted by a, then by b within equal a, then by c. It helps when the filter pins a leading prefix: a alone, a and b, or all three. Filters on only b, only c, or b and c cannot seek in it.

No. The optimizer normalizes the conjunction, so the order you type conditions in does not matter. What matters is which columns are constrained and how (equality vs range) versus the index key order, which is fixed at creation.

Put the equality-filtered columns first and the sort columns immediately after, in the same order as the ORDER BY. Inside the pinned block the index is already in sort order, so the engine walks it and stops early. Mixed ASC/DESC only works if the index directions match or are exactly reversed.

Collect the real query shapes, design one key per shape family with equality columns first and the range or sort column last, then drop any index whose key is a leftmost prefix of another. Verify with index usage counters and roll the drops out one at a time behind a quick rollback.

An index covers a query when every column the query needs — filters, joins, output, sorting — is present in the index. The engine then answers from the index alone and skips fetching the table rows, avoiding one random read per matching row.

Payload columns are stored only in leaf entries: they can be returned but never used for seeking, ordering or uniqueness. Key columns are stored in internal nodes too and can do all three. Use payload for columns you only need to output, key columns when you must filter or sort by them.

Index entries carry no transaction visibility information, so the engine cannot always tell whether an entry points at a row version this transaction may see. When it cannot, it fetches the row to check. Keeping table maintenance current — so pages are marked all-visible — removes most of those fetches.

Weigh the read saving — eliminated per-row table fetches times the query rate — against the write cost: every insert, delete and update of those columns now maintains a wider entry, plus extra space and cache pressure. Measure query latency, write latency, index size and cache hit rate before and after.

Cardinality is a row count: how many distinct values a column holds, or how many rows a plan step returns. Selectivity is the fraction of rows a predicate keeps. Indexes pay off when that fraction is tiny, because each match costs a separate row lookup.

Typically: row count, page count, per-column distinct values, null fraction, min/max, most-common values with frequencies, and a histogram. A distinct-value count only supports an averaged estimate assuming even distribution; a histogram records the actual shape of the data, so skewed values and range predicates are estimated correctly.

Get an execution plan with both estimated and actual row counts, then walk it bottom-up looking for the first step where estimate and actual diverge by orders of magnitude. If the leaf estimates are wrong, refresh statistics on those tables, re-check the plan, and if it still misestimates, add deeper histograms or multi-column statistics.

It depends on which value you query. Searching 'COMPLETED' matches ~49.5 million rows, so the optimizer will scan and ignore the index. Searching 'PENDING' or 'FAILED' is highly selective and the index helps a lot. Skewed low-cardinality columns are worth indexing only for their rare values.

The optimizer assumes predicates on different columns are independent and multiplies their selectivities. City and postal code are almost perfectly correlated, so the true combined selectivity is roughly the postal code's alone, not the product. Fix it with multi-column/extended statistics, or by removing the redundant predicate.

A partial index indexes only rows matching a predicate, so it is smaller, cheaper to maintain, and better cached. It pays off when queries always target a small slice of the table — for example only unprocessed jobs in a queue table where most rows are already done.

An index stores the column's raw values, so it can only match predicates on those raw values. Wrapping the column in a function produces values the index never stored. An expression index stores the computed results instead, and the planner uses it when the query's expression matches the indexed one.

Create a unique index on user_id restricted by a predicate matching only active rows. Uniqueness is then enforced within that subset only, so many inactive rows per user are fine. Limits: it enforces one condition on one subset, and swapping the active row can conflict mid-transaction.

The optimiser must prove the query's own conditions imply the index predicate, using only planning-time information. It reasons about constants and simple comparisons, not runtime parameter values, so a predicate compared against a bind parameter often cannot be proven and the index is skipped.

The result is computed once at write time and stored as the index key. If the expression's output later changes for the same row, the key no longer matches the row, so lookups silently miss rows or return wrong ones. Only deterministic, row-only expressions are safe.

In clustered storage the table IS the index: rows live in the leaves of a B+tree ordered by the clustering key. In a heap, rows sit in unordered pages and are addressed by a physical row id, with every index a separate structure pointing at those ids.

An increasing key always inserts at the rightmost leaf: pages fill in order, few splits, compact table, small write set. A random key inserts everywhere, so many leaf pages are touched and split, pages end up half full, the table bloats and writes scatter across memory and storage.

Cluster when one key dominates access, especially range or parent-child locality, and inserts arrive roughly in key order — you get no-row-fetch lookups and sequential ranges. Prefer a heap when access spreads across many columns, the key is wide, or inserts are random with respect to it.

A heap identifies rows by physical address, stable until the row is relocated, at which point engines leave a forwarding pointer or update index entries. A clustered table identifies rows logically by primary key, so rows may move between pages freely, but changing the key value physically relocates the row.

Every insert targets the same rightmost leaf page, so concurrent writers serialize on that one page's latch. Options: partition or shard the key space so there are several insert points, add a leading discriminator to spread writes, or accept it and scale out by table or node.

It searches the secondary index to find the matching entries, and each entry carries a pointer to the row - either a physical row address or the primary key. For every match it then reads the actual row from the table to get the missing columns. Two lookups per row.

A physical address makes each lookup a single direct page read, but any row move must be repaired - either by updating every secondary index or by leaving a forwarding pointer. A primary-key locator survives row movement untouched, but every lookup costs a full B+Tree descent and entries are larger.

Correlation between the index key order and the physical order of rows. Well-correlated keys make consecutive lookups land on the same few pages, so they are cache hits or sequential reads; uncorrelated keys scatter 50,000 lookups across 50,000 different pages, each a random read. Confirm with the clustering statistic and buffer hit counts.

Every secondary-index entry embeds the primary key as its row locator, so a 60-byte key adds roughly 60 bytes per entry across all six indexes. Entries get wider, fanout drops, indexes grow, less of them fits in cache, and lookups and writes cost more. Prefer a narrow surrogate key plus a unique constraint on the natural key.

Indexes are separate ordered structures that must stay consistent with the table, so every write also writes to each affected index — in its own sorted position, on a different page, inside the same transaction and its log. One insert into a table with five indexes is six structures updated, not one.

Read the engine's per-index usage counters over a full business cycle to find never-scanned indexes, and compare definitions to find ones whose columns are a leading prefix of another index. Before dropping: confirm the counters cover all replicas and periodic jobs, check the index does not back a constraint, and make it reversible.

Maintaining indexes row by row means a random page touch per index per row, with splits and logging. Building an index once afterwards reads the data in bulk, sorts it, and writes packed leaf pages sequentially. It is wrong when the table stays online, when constraints must hold during the load, or when the existing data dwarfs the new rows.

Logically, only indexes containing a changed column need their keys updated. Physically, it depends on whether the row stays in place: if the storage engine writes a new row version elsewhere, every index pointing at that row must be updated too, even for untouched columns.

There is no magic number. Derive it from the table's write service level: measure the per-index write cost, attribute each index to a named query with a business owner, drop what nothing claims, consolidate overlapping ones, and move report-only access to a replica or a separate model.

Deletes and updates leave dead entries and half-empty pages behind. The same live keys end up spread over more pages, so scans read more pages and each cached page carries less useful data. That is index bloat.

Compare the index's physical size against an estimate of what its live entries need: live row count times average entry width, divided by page capacity. A large ratio, plus falling page density and rising scan I/O over time, indicates bloat.

Options: an offline rebuild (fast, needs an exclusive lock), an online/concurrent rebuild (builds a shadow copy while writes continue — slower, needs space for both copies, can fail and leave an unusable index), an in-place reorganize (no full copy, less thorough), or dropping the index if unused.

Fill factor is how full a leaf page is packed when the index is built. Leaving free space lets later entries land in place instead of forcing new pages. Random churn drives density down; append-only keys keep it high.

Rebuilding indiscriminately burns I/O, log and replication bandwidth on indexes that are healthy, and it treats a symptom. Replace it with measurement-driven, targeted maintenance plus structural fixes: drop unused indexes, unblock reclamation, partition delete-heavy tables.

Storage grows with distinct values because each value needs its own bit vector, and the benefit comes from each value matching many rows. At very high cardinality the bitmaps become extremely sparse, per-value overhead dominates, and each value matches so few rows that a B+Tree does the job better.

Bitmaps are stored as compressed chunks covering ranges of rows, so changing one row means decompressing, editing and rewriting a whole chunk, and the lock covers every row in it. Two transactions updating unrelated rows in the same chunk block each other, producing serialization and deadlocks.

A bitmap index stores one bit vector per distinct column value, with one bit per row: bit set means that row has that value. Answering a predicate means fetching one bitmap and turning its set bits back into row locations, and combining predicates is bitwise AND or OR.

The engine gets a bitmap of matching rows for each predicate, then bitwise ANDs them — 64 rows per machine word — producing the final row set before touching the table. Only surviving rows are fetched, and in physical order, instead of fetching everything one predicate matched.

It scans the index and collects matching row locations into an in-memory bitmap instead of fetching each row immediately. That lets it visit table pages once each in physical order instead of randomly, and lets it combine several indexes with bitwise AND or OR before touching data.

A full scan reads every page of the table in order and discards rows that do not match. An index scan descends the index to the matching keys, then follows each key's pointer to fetch that row's table page. Fewer rows touched, but scattered reads.

The index path pays roughly one random page read per matching row, on top of index reads. A full scan pays one cheap sequential read per table page, no matter how many rows match. Past a few percent of rows matched, the scan wins.

Every column the query touches, in the output and in the predicates, must exist in the index. Then the engine skips the per-row table fetch entirely, eliminating the random I/O and reading only narrow index leaf pages in order.

Convert rows to pages. With 50 rows per page the table is 200,000 pages, read sequentially. The index path costs a few index pages plus up to 200,000 random row fetches, each several times more expensive. The scan wins by roughly an order of magnitude.

A B+Tree is sorted by the raw column value, so it can only seek ranges of that value. A function or an implicit cast on the column produces a different value per row, forcing the engine to compute it for every row. Move the transformation to the constant, or index the expression.

Either the index cannot be used (a function or cast wraps the column, a leading wildcard, wrong leading column) or the optimizer decided it is not worth it (the filter matches a large fraction of rows, the table is tiny, or row estimates are wrong from stale statistics). Read the actual plan.

The optimizer estimates matching rows from sampled statistics - histograms, distinct-value counts, common values - then costs plans. Stale or out-of-range statistics make the estimate wrong, so it prices the index badly. Diagnose by comparing estimated with actual rows in the plan, then refresh statistics and add multi-column ones for correlated predicates.

B+Tree entries are sorted by the whole string from the first character, so a known prefix defines one contiguous key range. A pattern that can start anywhere has matches scattered across the whole index, so the engine must read every value. Infix search needs a different index type.

Index access costs one random page fetch per matched row on top of walking the index; a scan reads pages sequentially with read-ahead and touches each page once. Past a few percent of the table the index path reads more pages than the table has, so scanning wins.