Database Indexing, in depth: choosing a strategy from access patterns, primary keys, tenants, pagination, time series and engine architecture

Engine architecture sets the price list

The same logical index costs different things in different engines, so start by knowing which of three architectures you are on. PostgreSQL stores rows in an unordered heap; every index, including the primary key, maps keys to a tuple identifier, a page and slot. A lookup descends the index and then fetches the heap page. Because an update usually writes a new row version at a new location, it must add entries to every index unless the update qualifies as heap-only, which requires that no indexed column changed and that the page has room.

InnoDB, the default MySQL engine, clusters the table on its primary key: the primary key B-tree's leaves contain the rows. A secondary index stores the indexed columns plus the primary key value, so a secondary lookup is two tree descents, and every secondary index carries a copy of the primary key. LSM engines such as RocksDB and Cassandra's storage never update in place; writes go to a memtable and are flushed into sorted runs that are merged later. Writes are cheap, and a read may consult several runs, with Bloom filters skipping most of them. The tree structure underneath the first two is described in B-tree Indexes, in depth and the third in LSM trees.

Choosing the primary key

In a clustered engine the primary key decides the physical order of the table and the width of every secondary index, which makes it the single most consequential indexing decision. Three choices dominate. A sequential integer from an auto-increment or sequence is narrow (8 bytes as a bigint), and inserts always land on the rightmost leaf, so the buffer pool keeps a small hot working set and pages fill completely. It leaks row counts and creation order to anyone who sees the ids, and it needs a central allocator.

A random UUID (version 4) is 16 bytes and can be generated anywhere, but inserts land on random leaves. Once the index is larger than memory, many inserts read a page from disk, and pages split half-full, so the index ends up larger than its sequential equivalent with more random I/O. A time-ordered UUID (version 7) puts a millisecond timestamp in its leading bits, so inserts are nearly sequential again while ids remain globally unique and generated without coordination. PostgreSQL 18 added a built-in uuidv7() function; on earlier versions or other engines generate it in the application.

The width cost is easy to underestimate in InnoDB. With 500 million rows and three secondary indexes, moving the primary key from an 8-byte bigint to a 16-byte UUID adds 8 bytes to each of 1.5 billion secondary entries: 12 GB of extra index data before page overhead, all of which competes for the buffer pool. In PostgreSQL the secondaries store a fixed-size tuple identifier instead, so the width cost is confined to the primary key index and foreign keys. A useful default: bigint or UUIDv7 as the key, with any public, unguessable identifier stored as a separate uniquely indexed column if you need one.

Multi-tenant tables: lead with the tenant

In a shared-schema multi-tenant system almost every query filters on the tenant. Put tenant_id first in nearly every index, including unique constraints, which should usually be unique per tenant rather than globally: UNIQUE (tenant_id, external_ref). With the tenant leading, each tenant's entries are contiguous, a query for one tenant touches only its own range, and one large tenant's data does not dilute another's cache locality.

Watch the skew. A tenant with a thousand times the median row count produces plans and latencies nobody sees in staging; test with a production-shaped largest tenant. If one tenant dominates, partitioning by tenant or moving it to its own shard may matter more than any index. Sharding choices are compared in Sharding strategies compared.

Pagination: keyset beats offset

Offset pagination asks the database to produce and discard every row before the page. Page 5,000 of a 20-row listing reads 100,000 index entries to return 20, and the cost grows with depth; rows inserted between requests also shift pages, so users see duplicates or gaps. Keyset pagination, also called seek pagination, remembers the sort key of the last row shown and asks for rows after it. With an index matching the filter and the full sort order, every page costs the same: one descent and 20 entries.

-- Offset pagination: page 5,000 reads and discards 100,000 index entries first.
SELECT id, created_at, subject FROM tickets
WHERE tenant_id = $1
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 100000;

-- Keyset pagination: seek to the last row of the previous page.
CREATE INDEX tickets_tenant_created_id ON tickets (tenant_id, created_at DESC, id DESC);

SELECT id, created_at, subject FROM tickets
WHERE tenant_id = $1
  AND (created_at, id) < ($2, $3)      -- values from the last row already shown
ORDER BY created_at DESC, id DESC
LIMIT 20;

-- Expanded form for engines that plan row-value comparisons poorly:
--   AND (created_at < $2 OR (created_at = $2 AND id < $3))

Two details make it correct. The sort must be total, so add the primary key as a tiebreaker; sorting on created_at alone skips rows that share a timestamp at a page boundary. And the index must match the sort order or its exact reverse, since B-trees can be scanned backwards; only mixed directions, one column ascending and another descending, need an index declared that way. The cost is that users cannot jump to page 5,000 directly, which is rarely a real requirement; offer filters instead.

Time series and append-only data

Tables that grow by timestamp, such as events, metrics and audit logs, are mostly appended and mostly queried by recent time ranges. A B-tree on the timestamp works, but on a billion-row table it is large. PostgreSQL's BRIN index stores only the minimum and maximum value per range of heap pages, which makes it orders of magnitude smaller than a B-tree and effective exactly when the physical order follows the timestamp, as it does for append-only inserts. It is useless after updates or bulk loads scramble that order.

The bigger strategic lever is partitioning by time. Each partition carries small local indexes, queries prune to the relevant partitions, and retention becomes dropping a partition instead of a DELETE that bloats every index. Composite indexes inside partitions should lead with the entity you filter by, such as (device_id, ts), since the partition already narrows the time.

Skip scan and leading columns

The classic rule says a composite index on (a, b) cannot serve a query that filters only on b. Skip scan relaxes it: if a has few distinct values, the engine can descend once per value of a and search for b within each. MySQL 8.0 has a skip-scan range access method, and PostgreSQL 18 added skip scan for multicolumn B-tree indexes, applied when a query omits an equality condition on one or more prefix columns.

Treat skip scan as a safety net, not a design tool. It helps when the skipped leading column has low cardinality, such as a status or region, and degrades towards a full index scan as cardinality grows. If a query on b alone is hot, give it its own index; if it is rare, skip scan may make an extra index unnecessary. Check with the plan, not intuition.

Queues, soft deletes and other narrow predicates

Many tables contain a small, hot subset: pending jobs among millions of completed ones, live users among soft-deleted ones. PostgreSQL partial indexes index only rows matching a predicate, so the pending-jobs index stays tiny however large the table grows, and a partial unique index enforces uniqueness only among live rows. MySQL has no partial indexes; the usual substitutes are moving completed rows to an archive table or indexing a generated column that is NULL for rows you want excluded, since NULLs do not collide in a unique index.

-- PostgreSQL: index only the rows a worker can pick up.
CREATE INDEX jobs_pending ON jobs (run_at) WHERE status = 'pending';

-- Claim work without workers blocking each other.
SELECT id FROM jobs
WHERE status = 'pending' AND run_at <= now()
ORDER BY run_at
LIMIT 10
FOR UPDATE SKIP LOCKED;

-- Soft deletes: uniqueness only among live rows.
CREATE UNIQUE INDEX users_email_live ON users (lower(email)) WHERE deleted_at IS NULL;

For queues, the index matters less than the claiming pattern. FOR UPDATE SKIP LOCKED lets several workers claim different rows concurrently instead of serializing on the first unlocked row. Keep the queue table small by deleting or archiving completed jobs, or the index and the table bloat with dead entries.

Secondary indexes in LSM and distributed stores

In distributed databases an index has a location as well as a shape. Cassandra's secondary indexes, including the Storage-Attached Indexes added in Cassandra 5.0, are local to each node: they index the data that node holds. A query that supplies the partition key goes to one replica set and uses the local index efficiently; a query without it must ask every node, and its latency is set by the slowest. For high-volume lookups by a non-key attribute, the standard strategy remains a second table keyed by that attribute, written alongside the first, which trades extra writes and application-maintained consistency for single-partition reads.

Global secondary indexes, as offered by some distributed SQL and key-value services, are partitioned by the indexed value instead, so lookups go to one place, but every write to the base table becomes a distributed write, often updated asynchronously, so a read through the index can briefly miss a recent write. Know which kind you have before you promise read-your-writes semantics.

Rolling indexes in and out

Every index has to be built on a live table and eventually removed. In PostgreSQL, CREATE INDEX CONCURRENTLY builds without blocking writes, at the cost of two table scans; if it fails it leaves an invalid index that must be dropped and retried. MySQL 8.0's online DDL builds most secondary indexes in place while allowing concurrent writes. Neither is free: a build reads the whole table and competes for I/O, so schedule large builds off-peak and watch replication lag.

Removal deserves the same care, because an index that looks unused may serve a monthly report or a uniqueness constraint. Query the statistics for unused indexes, then trial the removal: MySQL can mark an index invisible so the planner ignores it while it is still maintained, and making it visible again is instant. PostgreSQL has no built-in equivalent, so check usage over a full business cycle before dropping, and keep the definition to recreate it.

-- PostgreSQL: indexes never scanned since statistics were last reset, largest first.
SELECT s.schemaname, s.relname AS table_name, s.indexrelname AS index_name,
       pg_size_pretty(pg_relation_size(s.indexrelid)) AS size, s.idx_scan
FROM pg_stat_user_indexes s
JOIN pg_index i ON i.indexrelid = s.indexrelid
WHERE s.idx_scan = 0 AND NOT i.indisunique
ORDER BY pg_relation_size(s.indexrelid) DESC;

-- MySQL 8.0: the sys schema has a ready-made view, and invisible indexes allow a safe trial drop.
SELECT * FROM sys.schema_unused_indexes;
ALTER TABLE orders ALTER INDEX idx_orders_note INVISIBLE;   -- planner ignores it, data still maintained

Failure modes

What to do next

1. Write down your engine's architecture (heap, clustered or LSM) and, for clustered engines, the primary key width of your three largest tables.
2. For new tables, choose bigint or UUIDv7 primary keys; avoid UUIDv4 as a clustered key on large tables.
3. In multi-tenant schemas, check that every index used by request traffic leads with the tenant column and that unique constraints are per tenant.
4. Replace offset pagination on any endpoint whose users can page deep with keyset pagination over an index matching the full sort order.
5. Partition time-ordered tables that have retention policies, and drop partitions instead of deleting rows.
6. Run the unused-index query, trial removals over a full business cycle, and record each index's owner and justifying query.