Index Theory

Reading Query Execution Plans mentioned an Index Scan node without explaining what makes it fast, or why it is not always the plan the optimizer chooses even when an index exists. This article covers both.

What an index actually is#

A database index is a second data structure, stored alongside the table, holding the indexed column's values in sorted order along with a pointer back to each row. Without one, finding a specific value means scanning every row; with one, finding it means a search through a structure built specifically to make that fast.

Why a B-tree specifically#

The overwhelmingly common structure is a B-tree: a balanced, sorted tree where every lookup takes roughly the same, small number of steps regardless of table size — logarithmic, not linear, in the row count:

                [50]              /      \         [20, 35]    [70, 90]        /   |   \    /   |   \      ...  ...  ... ...  ...  ...

Finding the row with value 72 means comparing against a handful of nodes on the way down — a few dozen comparisons even across a table with millions of rows — rather than checking every row one at a time. This is also why a B-tree suits range queries (WHERE amount BETWEEN 100 AND 200) well: once the starting point is found, the sorted structure makes scanning forward from it cheap.

An index is not free: the write-side cost#

Every INSERT, UPDATE, or DELETE has to update every index on that table, not just the underlying rows — an index makes reads faster at a real, ongoing cost to every write. A table with ten indexes pays that maintenance cost ten times over on every single insert, which is why indexing every column "just in case" is a genuine trade-off, not a free optimization.

Selectivity: why having an index doesn't guarantee it gets used#

Selectivity is the fraction of rows a given value actually matches. A status column with only two values, active and inactive, split roughly 50/50, is not very selective — a query for WHERE status = 'active' would still need to fetch roughly half the table, and randomly accessing half a table's rows through an index is often slower than simply scanning the whole thing sequentially:

High selectivity (order_id = 4021)  -> index finds ~1 row -> index scan is clearly worth it
Low selectivity (status = 'active', matches 50% of rows)  -> index would still need to fetch half the table via     random access -> optimizer often prefers a sequential scan instead

Function-wrapped columns break index usage the same way they break pushdown#

Predicate and Projection Pushdown covered a filter like WHERE UPPER(status) = 'SHIPPED' losing its ability to use a Parquet file's stored statistics, because those statistics describe the raw column, not the transformed value. A standard B-tree index has the identical limitation: it is built on the raw column's values, so WHERE UPPER(status) = 'SHIPPED' cannot use a plain index on status either — the same underlying reason, showing up in a second, unrelated part of the stack.

Composite indexes and column order#

A multicolumn index on (customer_id, order_date) can efficiently serve a filter on customer_id alone, or on customer_id and order_date together — but generally cannot efficiently serve a filter on order_date alone, because the index is sorted by customer_id first. This leftmost-prefix rule means column order in a composite index is a real design decision, not an arbitrary one — put the column most queries filter on first.

Common mistakes#

Indexing every column "just in case"#

Each additional index is ongoing write cost paid whether or not it is ever used to speed up a read. Index the columns actual queries filter or join on, not every column that theoretically could be.

Wrapping the filtered column in a function#

WHERE UPPER(status) = 'SHIPPED' disables a plain index on status the same way it disables Parquet's statistics-based pushdown — filter on the raw column, or build an expression index specifically for that transformed value if the function call cannot be avoided.

Assuming a missing index scan means something is broken#

Low selectivity is frequently the correct reason an index goes unused. Check the actual selectivity of the filtered column before assuming the optimizer made a mistake.

Further reading#

• B-tree — the structure behind the overwhelming majority of database indexes.
• Database index — the general concept, including index types beyond B-trees.
• PostgreSQL: Indexes introduction — a concrete reference for creating and using indexes in a real database.
• Predicate and Projection Pushdown — the file-format-level version of the same function-wrapped-column limitation.

See also#