Indexes and What They Cost

What a composite index can and cannot serve, when a covering index pays off, and what every extra index costs on write.

Syntax

CREATE INDEX idx ON orders (user_id, status, created_at)  -- serves (user_id), (user_id, status), (user_id, status, created_at)

An index is a second, ordered copy of some of your columns, maintained on every write so reads can search instead of scan. That trade — write cost and storage for read latency — is the whole subject.

Leftmost prefix

A B-tree index on (a, b, c) is sorted by a, then by b within equal a, then by c. It therefore serves a lookup on a, on a and b, on a and b and c, and a range on the last column used. It does not serve a lookup on b alone, because b values are scattered throughout the index. MySQL 8.0.13 added the skip scan access method, which can use such an index by running one range scan per distinct leading value; it requires a single-table query that references only indexed columns, and EXPLAIN reports Using index for skip scan. Treat it as a rescue, not a design.

Covering indexes

When every column a query reads is in the index, the table is never touched. MySQL shows Using index in EXPLAIN's Extra column; PostgreSQL calls it an index-only scan, and since version 11 you can attach non-key payload columns with INCLUDE, so they ride along without widening the search key or a uniqueness constraint.

What it costs

Every index is another structure that each INSERT, each DELETE and each UPDATE of an indexed column must maintain, inside the same transaction and under the same locks. Six indexes turn one row write into roughly seven. InnoDB's change buffer defers part of that cost, but only for secondary indexes that are not unique — a unique index must be checked at write time, which puts a read on the write path.

Example

// Knex migration. One composite index serves several queries; a second index
// that merely repeats a prefix of the first is pure write cost.
exports.up = async function up(knex) {
  await knex.schema.alterTable('orders', (t) => {
    // Leftmost prefix. This single index serves all three of:
    //   WHERE user_id = ?
    //   WHERE user_id = ? AND status = ?
    //   WHERE user_id = ? AND status = ? AND created_at > ?
    // It does NOT serve WHERE status = ? on its own.
    t.index(['user_id', 'status', 'created_at'], 'orders_user_status_created_idx');

    // `t.unique([...])` is shorthand: it creates a UNIQUE *index*, not a
    // separate kind of object. The longhand below is the same thing, and the
    // index it builds is usable for lookups on (provider) alone.
    t.unique(['provider', 'provider_ref'], { indexName: 'orders_provider_ref_uniq' });
    // Longhand equivalent:
    //   CREATE UNIQUE INDEX orders_provider_ref_uniq
    //     ON orders (provider, provider_ref);
  });

  // Covering index for the dashboard query, which reads only these columns.
  // MySQL 8.x reports "Using index" in EXPLAIN's Extra column when the table
  // itself is never visited.
  await knex.raw(`
    CREATE INDEX orders_user_created_total_idx
      ON orders (user_id, created_at, total_minor)
  `);
};

exports.down = async function down(knex) {
  // Dropping an index is fast and reversible; dropping the wrong one shows up
  // as a p99 regression on one endpoint, so name them after their query.
  await knex.raw('DROP INDEX orders_user_created_total_idx ON orders');
  await knex.schema.alterTable('orders', (t) => {
    t.dropUnique(['provider', 'provider_ref'], 'orders_provider_ref_uniq');
    t.dropIndex(['user_id', 'status', 'created_at'], 'orders_user_status_created_idx');
  });
};

When to use it

Working out why a query ignores an existing index because its leading column is not in the WHERE clause.
Turning a slow list endpoint into an index-only scan by adding the one column it still fetches from the table.
Explaining a sudden rise in write latency or replication lag after a release that added several indexes.
Choosing which of five overlapping indexes on a hot table can be dropped without regressing a query.

More examples

PostgreSQL INCLUDE versus a wider search key

Shows the difference between a column being in the key and being payload, and the PostgreSQL-specific catch that an index-only scan still reads the heap for rows whose page is not yet marked all-visible. Reach for INCLUDE when a query needs one extra column returned and you do not want it affecting uniqueness or ordering.

-- Both of these let the dashboard query run index-only. They are not the same.

-- (a) total_minor is part of the search key: it widens every internal B-tree
-- page, and it would participate in any uniqueness constraint on the index.
CREATE INDEX orders_user_created_total_key
  ON orders (user_id, created_at, total_minor);

-- (b) PostgreSQL 11 and later: total_minor is payload only. It lives in leaf
-- pages, keeps internal pages narrow, and cannot be used for ordering or
-- filtering — only returned.
CREATE INDEX orders_user_created_total_incl
  ON orders (user_id, created_at) INCLUDE (total_minor);

-- INCLUDE is what makes a covering *unique* index possible:
CREATE UNIQUE INDEX orders_provider_ref_uniq
  ON orders (provider, provider_ref) INCLUDE (status);

EXPLAIN (ANALYZE, BUFFERS)
SELECT created_at, total_minor FROM orders
WHERE user_id = 42 AND created_at >= now() - interval '30 days';
-- Look for "Index Only Scan" plus a low "Heap Fetches" value. Heap fetches stay
-- above zero until the pages are marked all-visible, which VACUUM does — so a
-- freshly written table can show an index-only scan that still hits the heap.

Deciding whether an index is earning its keep

Every index on the write path has to justify itself with reads, and these two views are where that evidence lives. Reach for this before adding an index to a hot table, and again during any investigation of slow writes or replication lag — unused indexes are the cheapest write-amplification to remove.

-- PostgreSQL: indexes nobody scans, newest-largest first. idx_scan counts
-- scans since the last stats reset, so check how long the counter has been
-- accumulating before you trust a zero.
SELECT s.relname AS table_name,
       s.indexrelname AS index_name,
       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.idx_scan = 0
  AND NOT i.indisunique          -- a unique index enforces a constraint; keep it
  AND NOT i.indisprimary
ORDER BY pg_relation_size(s.indexrelid) DESC;

-- MySQL 8.x: the same question, from sys.
SELECT * FROM sys.schema_unused_indexes;

-- Low selectivity is the other half of the question: an index on a column with
-- three distinct values over 100M rows will be ignored by the planner and still
-- cost you a write on every insert.
SELECT status, count(*) FROM orders GROUP BY status;

Discussion

Be the first to comment on this lesson.

Leftmost prefix

Covering indexes

What it costs

Example

When to use it

More examples

PostgreSQL INCLUDE versus a wider search key

Deciding whether an index is earning its keep

Related

Discussion