Database Indexing

A database index is a separate data structure that gives the query planner another way to find rows. Without a useful index, the database may inspect every row in a table. With one, it can navigate to a smaller set of candidates.

Think of an index as an ordered map from selected values to row locations. The map helps only when its structure matches the question. It also occupies space and must change when indexed data changes.

Why indexes exist

Tables are optimized to store complete rows. Queries often need a narrow slice of those rows:

one account by email address;
recent orders for one customer;
rows joined through a key;
the first ten events in a requested order;
values that must remain unique.

An index can reduce the work needed for those access patterns. It can support filtering, joins, ordering, and uniqueness enforcement. It does not make every query fast.

The query planner chooses an execution plan from the available access paths. An index is an option, not an instruction. The planner may prefer a table scan when a condition matches much of the table or when the estimated index work costs more.

The B-tree mental model

A B-tree is the default and most common index type in many relational databases. It keeps keys in order and supports equality, range, and ordered retrieval.

Imagine an index on orders.created_at. The database navigates through upper levels of the tree to a leaf range containing the requested dates. Leaf entries identify candidate rows. The database may then fetch full rows from the table.

This explains several behaviors:

equality can locate one key or a narrow key range;
range conditions can scan adjacent keys;
matching order can avoid a separate sort;
reading many scattered table rows can cost more than one sequential scan.

Other index structures serve other operators and data shapes. PostgreSQL, for example, documents hash, GiST, SP-GiST, GIN, and BRIN alongside B-tree. Full-text, spatial, array, and block-range searches need structures designed for their operators.

Selectivity changes the value

Selectivity is the fraction of rows a condition matches. A selective condition matches a small fraction. An index on a nearly unique email address is often useful because one lookup returns very few rows.

A low-selectivity condition can be different. If most rows have status = 'active', an index on status may identify nearly the whole table. Fetching those rows through the index can require more work than scanning the table.

Cardinality is the number of distinct values in a column or value combination. High cardinality can support selective predicates, but cardinality alone does not justify an index. Start from real queries, result sizes, ordering, and update costs.

Composite indexes are ordered tuples

A composite index stores more than one key column. Column order defines the ordering of the stored tuples.

For an index on (customer_id, created_at), entries are ordered first by customer, then by time within each customer. This arrangement fits queries that select one customer and then restrict or order that customer's dates.

The leading columns matter. MySQL describes the usable lookup prefixes of (a, b, c) as (a), (a, b), and (a, b, c). PostgreSQL can sometimes use later columns through skip scan, but it still says multicolumn B-tree indexes are most efficient with constraints on leading columns.

Choose composite order from the workload:

identify the filters and joins used together;
note equality and range conditions;
include required ordering;
compare the index against its actual execution plans.

Do not reduce this to “put the most selective column first.” A useful index order must match the full access pattern.

Covering, partial, and expression indexes

A covering index stores every column a query needs. The database may then answer from the index without fetching full table rows. PostgreSQL calls this an index-only scan and allows non-key payload columns through INCLUDE.

Coverage has a price. Extra columns make the index larger. Larger indexes consume more storage and cache, take more work to maintain, and can approach engine-specific size limits.

A partial index contains only rows satisfying a predicate. It can focus storage and maintenance on a useful subset, such as unbilled orders. The query condition must imply the index predicate for the planner to use it. Partial-index rules and syntax vary by database.

An expression index stores a computed value, such as lowercase email. It can support queries that use the matching expression. The expression adds maintenance work because the stored result must be computed when affected rows change.

Unique indexes protect data

A unique index rejects duplicate indexed values or value combinations according to the database's null rules. In PostgreSQL, a primary key or unique constraint automatically creates the unique index used to enforce it.

This is more than a performance feature. It protects an invariant under concurrent writes. A prior application check cannot provide the same guarantee because another transaction can insert a conflicting row between the check and the write.

Prefer a primary-key or unique constraint when you mean to express a data rule. Treat the supporting index as its enforcement mechanism, not merely a tuning trick.

Statistics connect indexes to plans

The planner estimates how many rows each operation will produce. It uses statistics about table size, distinct values, common values, and value distributions. Those estimates influence whether it chooses an index scan, a table scan, and particular join strategies.

Stale or insufficient statistics can produce poor estimates. Correlated columns can also mislead a planner that treats their conditions as independent. PostgreSQL supports extended statistics for selected column groups and gathers them with ANALYZE.

An unused index is not automatically broken. The planner may correctly decide that another plan costs less. First compare estimated rows with actual rows and inspect the workload and statistics.

Read the execution plan

Use the database's plan tool before and after an index change. PostgreSQL and MySQL both provide EXPLAIN; their fields and execution options differ.

Ask these questions:

Which access path did the planner choose?
Which predicates became index conditions, and which remained filters?
How many rows did the planner estimate?
How many rows were actually processed when measured execution is safe?
Did the index avoid a sort or table lookup?
Did total latency improve across representative inputs?

One fast example is weak evidence. Test common values, rare values, realistic table sizes, and the write workload. Cache state and concurrent activity can affect measurements.

Indexes charge every write

Each additional index consumes storage and adds maintenance to inserts, deletes, and updates of indexed values. Wide keys and payload columns increase that cost. Index creation can also consume time, I/O, and locks, although engines provide different online or concurrent build options.

Over-indexing often appears as overlapping indexes created for individual slow queries. Review whether a composite index already serves a shorter prefix, whether an index enforces a constraint, and whether usage evidence justifies continued maintenance.

Removing an index also needs evidence. It may serve an infrequent critical report or a uniqueness rule. Use engine-specific usage data, inspect constraints, and test the effect before removal.

A disciplined indexing loop

Treat indexing as an evidence loop:

capture a slow or important query with representative parameters;
inspect its current plan and row estimates;
form a hypothesis about the missing or mismatched access path;
design the smallest index that matches the query shape;
update statistics when required;
compare plans, latency, resource use, and write cost;
keep, revise, or remove the index based on evidence.

The goal is not maximum index coverage. The goal is a small, purposeful index set that supports the workload while keeping writes and operations healthy.

Limits of this course

Index syntax, optimizer behavior, concurrency options, and monitoring views differ across database engines and versions. This course gives you a portable mental model, not a production prescription for one system.

Use the official documentation for your database. Test with production-like data and load. Treat plan evidence as specific to the query, statistics, schema, configuration, and version you measured.