Indexes & Query Performance

Without an index, a database answers WHERE email = 'asha@example.com' by reading every row in the table: a full or sequential scan. On 10 rows that's instant. On 100 million rows, it's seconds of disk and CPU for each query. An index is a separate, sorted data structure that maps column values to row locations, so the database can jump straight to the matching rows.

Indexes are the single most effective performance tool in databases, and also one of the most commonly misused. Every index speeds up some reads, but slows every write and uses storage.

How a B-tree index works

Most relational indexes (PostgreSQL, MySQL/InnoDB, SQL Server) and MongoDB indexes are B-trees (strictly, B+ trees). They're wide, shallow, balanced trees whose leaves hold keys in sorted order, linked together:

                    [ 40 | 80 ]
             /           |            \
     [10|20|30]     [50|60|70]     [90|100|110]     ← leaves: sorted keys → row locations,
                                                       linked left-to-right for range scans

Each node holds hundreds of keys, so even a billion rows need only about 3–4 levels. A lookup reads a handful of pages, often cached in memory.
Equality lookup: O(log n).
Range scan (BETWEEN, >, <, prefix LIKE 'abc%'): find the start, then walk the leaves. O(log n + k) for k results.
Sorted output for free: ORDER BY on the indexed column can read the index in order, instead of sorting.

Composite indexes and the leftmost-prefix rule

An index on (user_id, created_at) is sorted by user_id, and within each user, by created_at. Like a phone book sorted by last name, then first name:

Query	Uses the index?
`WHERE user_id = 42`	✅ Leftmost column
`WHERE user_id = 42 AND created_at > '2026-01-01'`	✅ Equality, then range: ideal
`WHERE user_id = 42 ORDER BY created_at DESC LIMIT 20`	✅ Filter and sort both come from the index
`WHERE created_at > '2026-01-01'`	❌ Not efficiently: the leading column is missing

Column order guideline: put columns used with equality first, then the column used for sorting or ranges. A range on an earlier column stops later columns from narrowing the search. MongoDB's version of this guideline is the ESR rule: Equality, Sort, Range.

Covering indexes

If every column a query needs is in the index, the database can answer from the index alone, without visiting the table (an "index-only scan"):

CREATE INDEX idx_orders_user_cover ON orders (user_id, created_at) INCLUDE (total, status);

SELECT created_at, total, status FROM orders WHERE user_id = 42 ORDER BY created_at DESC LIMIT 20;

This matters most for hot queries that return many rows.

Other index types

Type	Good for
B-tree (default)	Equality, ranges, sorting, prefix matching
Hash	Equality only
GIN (PostgreSQL)	Values containing many items: JSONB keys, arrays, full-text search
GiST / SP-GiST	Geometric and geographic data, ranges, nearest-neighbour
BRIN	Huge tables whose physical order correlates with the column (append-only timestamps). Tiny index, coarse filtering
Partial index	Indexing only a subset of rows, e.g. `WHERE status = 'PENDING'`
Expression index	Indexing a computed value, e.g. `lower(email)` for case-insensitive lookup

Reading the query plan

Never guess. Ask the database what it does:

EXPLAIN ANALYZE
SELECT * FROM orders WHERE user_id = 42 AND created_at > now() - interval '30 days';

What to look for:

Seq Scan on a large table for a selective query usually means a missing or unusable index.
Index Scan / Index Only Scan means the index is being used.
Estimated vs actual rows: big mismatches mean stale statistics (run ANALYZE), and they lead the planner to bad choices.
Sort or Hash steps spilling to disk suggest a missing index for the ORDER BY, or insufficient memory.

In MongoDB, use .explain("executionStats") and compare totalDocsExamined with nReturned. Ideally they're close.

Why an index might not be used

A function applied to the column: WHERE lower(email) = … or WHERE date(created_at) = … can't use a plain index on that column. Use an expression index, or rewrite it as a range: created_at >= '2026-03-01' AND created_at < '2026-03-02'.
Leading wildcard: LIKE '%smith' can't use a B-tree. Use trigram or full-text indexes.
Type mismatch: comparing a string column to a number can force a conversion on every row.
Low selectivity: if the query matches a large share of the table, a sequential scan really is cheaper, and the planner is right to choose it.
OR across different columns may need separate indexes combined, or a query rewrite.

The cost side

Every INSERT, and every UPDATE of an indexed column, must update every relevant index. Ten indexes can make writes several times slower.
Indexes use disk and, more importantly, memory. Hot indexes should fit in RAM.
Redundant indexes waste both: an index on (a) is usually redundant if (a, b) exists.

Practical approach: index primary keys, foreign keys used in joins, and the columns in your most frequent and most expensive WHERE/ORDER BY clauses. Verify with EXPLAIN. Periodically find and drop unused indexes (PostgreSQL's pg_stat_user_indexes shows usage counts).

Clustered vs secondary indexes

In a clustered index (InnoDB's primary key, SQL Server's clustered index), the table rows are stored in the index's order. There's one per table, and primary key range scans are very fast.
Secondary indexes point to rows. In InnoDB they store the primary key, so a secondary lookup is two B-tree searches. That's one reason a short primary key helps InnoDB.
PostgreSQL stores rows in a heap, and all indexes point into it.

Follow-up questions this topic invites — and their answers

Q: Why not index every column? A: Every index slows inserts and updates, uses storage and memory, and gives the planner more options to consider. Unused indexes are pure cost. Index for the queries you actually run.

Q: How do you choose column order in a composite index? A: Equality-filtered columns first, then the column used for sorting, then the range-filtered column. Also check which queries share a prefix, so one index can serve several of them.

Q: What is index selectivity? A: The fraction of rows a value matches. A nearly unique column such as email is highly selective, and an index on it is very effective. A boolean or status column with few values is low-selectivity, unless you're querying a rare value, which a partial index handles well.

Q: Why is the database doing a sequential scan when I have an index? A: The query may not match the index (a function on the column, a missing leading column, a type mismatch), the statistics may be stale, or the query may match so many rows that a scan really is cheaper. EXPLAIN ANALYZE tells you which.

Q: How do you speed up OFFSET-based pagination on deep pages? A: OFFSET 100000 still reads and discards 100,000 rows. Use keyset (cursor) pagination instead: WHERE (created_at, id) < (:lastCreatedAt, :lastId) ORDER BY created_at DESC, id DESC LIMIT 20, backed by an index on (created_at, id).

How a B-tree index works

                    [ 40 | 80 ]
             /           |            \
     [10|20|30]     [50|60|70]     [90|100|110]     ← leaves: sorted keys → row locations,
                                                       linked left-to-right for range scans

Each node holds hundreds of keys, so even a billion rows need only about 3–4 levels. A lookup reads a handful of pages, often cached in memory.
Equality lookup: O(log n).
Range scan (BETWEEN, >, <, prefix LIKE 'abc%'): find the start, then walk the leaves. O(log n + k) for k results.
Sorted output for free: ORDER BY on the indexed column can read the index in order, instead of sorting.

Composite indexes and the leftmost-prefix rule

An index on (user_id, created_at) is sorted by user_id, and within each user, by created_at. Like a phone book sorted by last name, then first name:

Query	Uses the index?
`WHERE user_id = 42`	✅ Leftmost column
`WHERE user_id = 42 AND created_at > '2026-01-01'`	✅ Equality, then range: ideal
`WHERE user_id = 42 ORDER BY created_at DESC LIMIT 20`	✅ Filter and sort both come from the index
`WHERE created_at > '2026-01-01'`	❌ Not efficiently: the leading column is missing

Covering indexes

If every column a query needs is in the index, the database can answer from the index alone, without visiting the table (an "index-only scan"):

CREATE INDEX idx_orders_user_cover ON orders (user_id, created_at) INCLUDE (total, status);

SELECT created_at, total, status FROM orders WHERE user_id = 42 ORDER BY created_at DESC LIMIT 20;

This matters most for hot queries that return many rows.

Other index types

Type	Good for
B-tree (default)	Equality, ranges, sorting, prefix matching
Hash	Equality only
GIN (PostgreSQL)	Values containing many items: JSONB keys, arrays, full-text search
GiST / SP-GiST	Geometric and geographic data, ranges, nearest-neighbour
BRIN	Huge tables whose physical order correlates with the column (append-only timestamps). Tiny index, coarse filtering
Partial index	Indexing only a subset of rows, e.g. `WHERE status = 'PENDING'`
Expression index	Indexing a computed value, e.g. `lower(email)` for case-insensitive lookup

Reading the query plan

Never guess. Ask the database what it does:

EXPLAIN ANALYZE
SELECT * FROM orders WHERE user_id = 42 AND created_at > now() - interval '30 days';

What to look for:

Seq Scan on a large table for a selective query usually means a missing or unusable index.
Index Scan / Index Only Scan means the index is being used.
Estimated vs actual rows: big mismatches mean stale statistics (run ANALYZE), and they lead the planner to bad choices.
Sort or Hash steps spilling to disk suggest a missing index for the ORDER BY, or insufficient memory.

In MongoDB, use .explain("executionStats") and compare totalDocsExamined with nReturned. Ideally they're close.

Why an index might not be used

A function applied to the column: WHERE lower(email) = … or WHERE date(created_at) = … can't use a plain index on that column. Use an expression index, or rewrite it as a range: created_at >= '2026-03-01' AND created_at < '2026-03-02'.
Leading wildcard: LIKE '%smith' can't use a B-tree. Use trigram or full-text indexes.
Type mismatch: comparing a string column to a number can force a conversion on every row.
Low selectivity: if the query matches a large share of the table, a sequential scan really is cheaper, and the planner is right to choose it.
OR across different columns may need separate indexes combined, or a query rewrite.

The cost side

Every INSERT, and every UPDATE of an indexed column, must update every relevant index. Ten indexes can make writes several times slower.
Indexes use disk and, more importantly, memory. Hot indexes should fit in RAM.
Redundant indexes waste both: an index on (a) is usually redundant if (a, b) exists.

Clustered vs secondary indexes

In a clustered index (InnoDB's primary key, SQL Server's clustered index), the table rows are stored in the index's order. There's one per table, and primary key range scans are very fast.
Secondary indexes point to rows. In InnoDB they store the primary key, so a secondary lookup is two B-tree searches. That's one reason a short primary key helps InnoDB.
PostgreSQL stores rows in a heap, and all indexes point into it.