Indexing and Query Optimisation in Distributed Databases

by
Home » Distributed Systems » Scalability & Performance » Indexing and Query Optimisation in Distributed Databases

Distributed Systems Series — Part 5.7: Scalability & Performance

Why Indexing Is a Scalability Problem, Not Just a Database Problem

Post 5.3 established that partitioning distributes data across nodes so that each node owns a subset of the key space. Partitioning solves the write scalability problem — ten shards means ten independent write paths. But partitioning alone does not solve the query performance problem. A database that stores ten billion rows distributed across a hundred shards still scans all ten billion rows if queries cannot locate relevant rows without examining every one.

Indexing is the mechanism that makes queries fast by creating data structures that allow the database to locate relevant rows without scanning every row. Without indexes, every query is a full table scan — O(N) in the number of rows. With the right index, most queries become O(log N) lookups or O(K) range scans where K is the number of matching rows. At distributed systems scale, the difference between O(N) and O(log N) is the difference between a query that takes seconds and one that takes microseconds.

Indexing in distributed systems is more complex than in single-node databases because indexes must be consistent across partitions, replicas must maintain index consistency during replication, and secondary indexes — indexes on non-partition-key columns — require either per-partition local indexes (fast writes, slow cross-partition reads) or global indexes (fast reads, expensive to maintain). These trade-offs determine query performance, write throughput, and consistency guarantees simultaneously.

This post covers the two dominant index structures (B-trees and LSM-trees), the index trade-off between read and write performance, composite index design and the query alignment requirement, covering indexes, distributed secondary indexes and their consistency challenges, the N+1 query problem at scale, and query execution plan analysis in production distributed databases.

The Two Dominant Index Structures

Every production database index is built on one of two foundational data structures. The choice between them is not arbitrary — each is optimised for a different workload characteristic, and using the wrong structure for your workload produces measurable performance degradation.

B-Trees: Read-Optimised, In-Place Updates

The B-tree (and its variant, the B+ tree) is the dominant index structure in relational databases — PostgreSQL, MySQL InnoDB, SQLite, and Oracle all use B-tree indexes as their primary index type. The structure is a balanced tree where leaf nodes contain the actual indexed data or pointers to the data rows, and internal nodes contain keys that route searches to the correct leaf.

A B-tree with branching factor B has depth O(log_B N) where N is the number of indexed entries. A typical B-tree with a page size of 4KB and 8-byte keys has a branching factor of approximately 500. A B-tree indexing one billion entries has depth log_500(1,000,000,000) ≈ 3.5 — meaning almost every search requires at most 4 page reads regardless of table size. This O(log N) read performance is the B-tree’s primary advantage.

B-tree writes update pages in place. When a row is inserted, the B-tree finds the correct leaf page and inserts the key into that page. If the page is full, it splits into two pages and the split propagates up the tree. This in-place update mechanism produces random I/O — the page to update may be anywhere on disk, requiring a disk seek. On spinning disks, random I/O is dramatically slower than sequential I/O. On SSDs, random I/O is fast but still slower than sequential writes and produces write amplification that reduces SSD longevity.

B-trees are the correct choice for read-heavy workloads, OLTP databases with frequent point lookups and range scans, and workloads where query latency matters more than write throughput.

LSM-Trees: Write-Optimised, Sequential I/O

The Log-Structured Merge-tree (LSM-tree) converts random writes into sequential writes by buffering all writes in an in-memory structure (the MemTable) and flushing to disk in sorted order when the MemTable is full. Cassandra, RocksDB, LevelDB, HBase, and Bigtable all use LSM-tree indexes. The structure consists of multiple levels: an in-memory MemTable at the top and multiple tiers of Sorted String Tables (SSTables) on disk below.

Every write goes to the MemTable — a sorted in-memory data structure (typically a red-black tree or skip list) that keeps entries in sorted key order. Writes are sequential (append to the MemTable) and extremely fast — no disk seek, no random I/O. When the MemTable reaches a configured size (typically 64MB to 512MB), it is flushed to disk as an immutable SSTable file at Level 0.

As SSTables accumulate at Level 0, a background compaction process merges and rewrites them into larger SSTables at Level 1. Further compaction merges Level 1 into Level 2, and so on. This compaction process — merging sorted runs from multiple levels into a single sorted run at the next level — is where LSM-trees get their name and where their write amplification cost comes from. Each record may be written to disk multiple times as it moves through levels during compaction.

Reads in an LSM-tree must check the MemTable and all SSTable levels for the most recent version of a key. In the worst case, this requires checking every level — O(number of levels) disk reads plus the O(log N) binary search within each SSTable. Bloom filters (probabilistic data structures that can determine with high probability whether a key exists in an SSTable) are used at each level to skip levels that definitely do not contain the key, reducing average read latency significantly.

LSM-trees are the correct choice for write-heavy workloads, time-series data, event sourcing and audit logs, and any workload where write throughput matters more than read latency. Cassandra’s write performance at scale — millions of writes per second across a cluster — is fundamentally enabled by its LSM-tree storage engine.

The Index Trade-off: Read Performance vs Write Overhead

Every index improves read performance and degrades write performance. This is not a limitation of specific implementations — it is a fundamental property of indexing that must inform every indexing decision.

When a row is inserted, updated, or deleted, every index on that table must be updated to reflect the change. A table with five indexes requires six write operations for every insert — one to the primary data structure and one to each index. The write overhead scales linearly with the number of indexes. For a write-heavy table, each additional index directly reduces write throughput.

The practical implication: index what is queried, not everything that could possibly be queried. A table with 20 columns does not need 20 indexes. Start with the indexes that the most frequent and most latency-sensitive queries require. Add indexes when query performance measurements show they are needed. Remove indexes when write performance measurements show they are too expensive.

In distributed databases, this trade-off is amplified. Replication means that each write must be replicated to multiple nodes, and each replica must update each index. A table with five indexes in a three-replica cluster requires eighteen write operations for each insert — six per replica across three replicas. Index design directly affects replication throughput and replication lag.

Composite Indexes: The Query Alignment Requirement

A composite index covers multiple columns. A composite index on (last_name, first_name, birth_year) stores entries sorted first by last_name, then by first_name within each last_name, then by birth_year within each first_name. This sorting order is what makes composite indexes both powerful and constraining.

Composite indexes follow the leftmost prefix rule: a query can efficiently use the index only if it specifies the leftmost columns of the index in order. The index (last_name, first_name, birth_year) efficiently serves:

Queries that specify last_name only — the index is sorted by last_name, so a range scan on last_name is efficient. Queries that specify last_name and first_name — the secondary sort within each last_name allows first_name to be searched efficiently. Queries that specify all three columns — full index lookup. The index does not efficiently serve queries that specify first_name only (without last_name) or birth_year only — because these columns are not the leftmost prefix of the index sort order, a full index scan is required.

This leftmost prefix constraint is the most commonly violated index design principle in production systems. Engineers add composite indexes to cover observed query patterns, then new queries are added that skip the leftmost column, and the index provides no benefit while still imposing write overhead. The fix is either to add a separate index on the non-leftmost column or to reorder the composite index to match the actual query patterns.

The column order in a composite index should be determined by two factors: selectivity (higher-selectivity columns first — columns that filter to a small result set — reduce the search space faster) and query patterns (the leftmost prefix must match the columns specified in the most frequent queries). When these two factors conflict, query patterns win — an index that is not used provides no benefit.

Covering Indexes: Eliminating Table Lookups

A covering index includes all the columns a query needs, so the query can be answered entirely from the index without accessing the underlying table. This eliminates the table lookup step — the most expensive operation for queries that return many rows from a large table.

Consider a query that selects email and created_at for users with last_name = ‘Smith’. Without a covering index, the database uses the index on last_name to find the matching rows, then reads each row from the table to retrieve the email and created_at columns. With a covering index on (last_name, email, created_at), all three columns are stored in the index. The query is answered entirely from the index — no table access required.

PostgreSQL calls this an index-only scan and displays it as such in query execution plans. MySQL calls it a covering index and shows “Using index” in the Extra column of EXPLAIN output. The performance difference can be an order of magnitude for queries that return many rows from a large table — because index pages are more compact than table pages (they contain only indexed columns, not the full row), a covering index scan reads fewer pages and produces lower I/O than a table scan.

The cost of covering indexes is additional write overhead — every indexed column must be updated in the index when the row changes — and additional storage. Include only the columns that are frequently queried together in covering indexes. Do not include all columns of a large table in an index to cover every possible query — the write overhead and storage cost would exceed the read benefit.

Distributed Secondary Indexes: Local vs Global

In a partitioned database, the primary index routes queries to the correct shard based on the partition key. Secondary indexes — indexes on non-partition-key columns — require a different design because the data they index is distributed across shards with no relationship to the secondary index column.

Two design choices exist, each with fundamentally different performance characteristics.

Local secondary indexes (per-partition indexes) maintain a separate index on each shard that covers only the data on that shard. A local secondary index on email in a user table partitioned by user_id means each shard has an index of email → user_id mappings for the users on that shard.

Write performance is excellent — a write to a shard updates only that shard’s local index, with no cross-shard coordination. Read performance for queries that specify the partition key is excellent — the query routes to the correct shard and the local index is used. Read performance for queries that specify only the secondary index column is poor — the query must scatter to all shards (asking every shard “do you have a user with email = X?”) and collect results. This scatter-gather pattern has the tail latency amplification problem from Post 5.2 — the query is as slow as the slowest shard.

Cassandra uses local secondary indexes. DynamoDB’s Local Secondary Indexes (LSIs) are similarly per-partition. Both provide fast writes and fast reads when the partition key is specified, at the cost of scatter-gather for queries that use only the secondary index.

Global secondary indexes maintain a single index that spans all shards. The global index is itself partitioned, but by the secondary index key rather than the primary partition key. A global secondary index on email stores all email → user_id mappings in a separate index partition, distributed across nodes by email value.

Read performance for queries on the secondary index column is excellent — the query routes to the correct global index partition and retrieves the result in one hop, with no scatter-gather. Write performance is more expensive — a write must update both the primary shard and the global index partition, which may be on a different node. This cross-shard write introduces coordination overhead and consistency challenges.

DynamoDB’s Global Secondary Indexes (GSIs) are eventually consistent — writes to the primary table propagate asynchronously to the GSI. A read from a GSI may return data that does not reflect the most recent write. Spanner’s secondary indexes are strongly consistent — writes to the primary and secondary index are transactional — at the cost of the distributed transaction overhead that Spanner’s TrueTime mechanism enables.

The choice between local and global secondary indexes maps directly to the CAP theorem trade-off from Post 3.4: local indexes favour availability and write performance (each shard operates independently) at the cost of read consistency for cross-shard queries. Global indexes favour read consistency and performance (single-hop reads) at the cost of write coordination and potential consistency lag.

The N+1 Query Problem at Scale

The N+1 query problem is the most common and most expensive application-level query performance failure. It occurs when code fetches N parent objects and then issues one additional query per parent to fetch associated child objects — N+1 queries total instead of one or two.

The classic example: fetching a list of 100 orders and then fetching the customer details for each order separately. The application issues one query to fetch 100 orders, then 100 individual queries to fetch the customer for each order — 101 queries total instead of two (one join or one additional query with IN clause). At 5ms per query, this is 505ms of total query time instead of 10ms. At scale, with 1,000 concurrent users each triggering a list view, this is 101,000 database queries per second for work that requires 2,000 queries per second with correct query design.

N+1 problems are invisible in development and testing because the dataset is small and query latency is low — 101 queries at 0.1ms each is 10ms, which appears acceptable. In production with a large dataset, latency increases, the problem becomes visible, and fixing it requires changing application code that may have been shipped and relied upon by many callers.

The solutions are batch loading (replace the N individual queries with one query that retrieves all N results using an IN clause or JOIN) and eager loading (in ORM frameworks, configure relationships to be loaded in a single query with JOIN rather than lazy-loaded individually). Both require the query to be aware of which related data will be needed — a decision that must be made at the code level, not at the database level.

In distributed databases, the N+1 problem is compounded by the fact that individual queries may scatter across shards. 100 queries for customer data where customer IDs are distributed across 10 shards may produce 1,000 network round trips in the worst case. Batching the 100 customer IDs into a single IN clause query allows the database to route each shard’s subset of IDs to the correct shard in parallel — 10 parallel shard queries instead of 100 sequential single-row queries.

Query Execution Plan Analysis

A query execution plan is the database’s internal description of how it will execute a query — which indexes it will use, in what order it will join tables, whether it will perform index scans or full table scans, and how it will filter and aggregate results. Understanding execution plans is the primary skill for diagnosing and fixing query performance problems.

In PostgreSQL, EXPLAIN ANALYZE executes the query and shows the actual execution plan with timing information for each step. The key indicators to look for are sequential scans on large tables (indicating a missing or unused index), nested loop joins on large result sets (indicating a join that would benefit from a hash join or merge join), and high row estimates that differ significantly from actual row counts (indicating stale statistics that cause the planner to choose suboptimal plans).

A sequential scan on a large table — shown as Seq Scan on users with a high actual rows count — almost always indicates a missing index. The fix is to add an index on the column in the WHERE clause. However, if the query returns a large fraction of the table’s rows, a sequential scan may actually be faster than an index scan — the database’s query planner makes this determination based on table statistics, and overriding it with a forced index hint is usually counterproductive.

In Cassandra, the TRACING ON command before a query shows the execution trace — which coordinator and replica nodes were involved, how long each step took, and whether the query used an index or required a full partition scan. Cassandra’s query planner is simpler than PostgreSQL’s — it does not automatically choose between index and full scan based on selectivity. Instead, Cassandra requires the partition key in every query and uses secondary indexes only when explicitly available. Queries that do not specify the partition key produce ALLOW FILTERING warnings — full cluster scans that are explicitly disallowed in production by default.

In DynamoDB, the explain parameter on query operations (available through the PartiQL interface) shows whether the query used the primary key, a Local Secondary Index, or a Global Secondary Index. DynamoDB’s execution model is simpler than relational databases — each query either uses an index (fast, predictable) or scans (slow, should be avoided). The primary performance analysis question for DynamoDB is: does this access pattern have a matching index?

Index Maintenance: The Operational Cost

Indexes are not free after creation — they require continuous maintenance as data changes and as the index structures become fragmented over time.

B-tree index fragmentation occurs as pages fill and split. A freshly built B-tree has pages that are close to full and sequential on disk. After many inserts and deletes, pages may be partially empty (from deletions) and non-sequential on disk (from splits and rewrites). Fragmentation increases I/O for range scans — pages that should be sequential are scattered across disk, requiring more seeks. PostgreSQL’s VACUUM and REINDEX commands reclaim space from deleted rows and rebuild fragmented indexes. MySQL’s OPTIMIZE TABLE performs equivalent maintenance.

LSM-tree compaction is the equivalent maintenance operation. The compaction process merges SSTables from upper levels into larger SSTables at lower levels, reclaiming space from deleted and overwritten entries (tombstone records) and maintaining the sorted order that enables efficient reads. Compaction is CPU and I/O intensive — a Cassandra node performing major compaction can saturate its disk I/O, increasing read and write latency for foreground traffic. Compaction scheduling — running compaction during low-traffic periods and throttling its I/O rate — is a critical operational concern for LSM-tree databases.

Index bloat from deleted rows is a common production problem in both B-tree and LSM-tree databases. PostgreSQL tables with high delete rates accumulate dead tuples that occupy space but do not contribute to query results. Without regular VACUUM, table and index sizes grow beyond the actual live data size, increasing I/O for all queries. Autovacuum handles this automatically but must be tuned for high-delete-rate tables.

Key Takeaways

  1. B-trees are read-optimised — O(log N) reads with in-place random I/O writes — and are the correct choice for read-heavy OLTP workloads; LSM-trees are write-optimised — sequential writes buffered in MemTable — and are the correct choice for write-heavy workloads like time-series and event logging
  2. Every index improves read performance and degrades write performance — index what is actually queried, start with the minimum necessary indexes, and add only when query performance measurements justify the write overhead cost
  3. Composite indexes follow the leftmost prefix rule — a query must specify the leftmost columns of the composite index to use it efficiently; column order should match query patterns first and selectivity second
  4. Covering indexes eliminate table lookups by storing all query-needed columns in the index — they can reduce query I/O by an order of magnitude for queries that return many rows from large tables
  5. Local secondary indexes provide fast writes and fast partition-scoped reads at the cost of scatter-gather for cross-partition reads; global secondary indexes provide fast cross-partition reads at the cost of write coordination and potential consistency lag
  6. The N+1 query problem converts one or two queries into N+1 queries through lazy loading of related objects — at production scale this multiplies database load by 50-100× and must be addressed with batch loading or eager loading
  7. Query execution plan analysis — EXPLAIN ANALYZE in PostgreSQL, TRACING ON in Cassandra — is the primary tool for diagnosing index usage and identifying sequential scans, suboptimal joins, and stale statistics that cause the planner to make poor decisions

Frequently Asked Questions (FAQ)

What is the difference between a B-tree and an LSM-tree index?

B-trees update data in place — writes locate the correct page in the tree and update it directly, producing random I/O. They provide O(log N) reads and are read-optimised. LSM-trees buffer all writes in an in-memory structure (MemTable) and flush to sequential disk files (SSTables), converting random writes to sequential writes. Reads must check multiple levels, making them slower than B-trees for point lookups. B-trees are used by PostgreSQL, MySQL, and SQLite. LSM-trees are used by Cassandra, RocksDB, HBase, and LevelDB. Choose B-trees for read-heavy OLTP workloads and LSM-trees for write-heavy append-oriented workloads.

What is the leftmost prefix rule for composite indexes?

A composite index on (A, B, C) is sorted first by A, then by B within each A value, then by C within each B value. A query can efficiently use this index only if it specifies columns from the left of the index in order — a query on A alone, A and B together, or A, B, and C together can all use the index efficiently. A query on B alone or C alone cannot use the index efficiently because B and C are not the leftmost columns — the index is not sorted by B or C independently. The practical implication: composite index column order must match the most frequent query patterns, with the most frequently filtered columns placed leftmost.

What is a covering index and when should I use one?

A covering index includes all columns a query needs to return results without accessing the underlying table. When the query planner determines that all required columns are in the index, it performs an index-only scan — reading only index pages, which are more compact than table pages and require less I/O. Use covering indexes for queries that run frequently, return many rows, and read a small, predictable set of columns. The cost is additional write overhead (every write must update the index) and storage. Do not create covering indexes that include all table columns — the overhead defeats the purpose.

What is the difference between local and global secondary indexes in distributed databases?

Local secondary indexes maintain a separate index per partition, covering only the data on that partition. Writes are fast (update one partition’s index), reads for queries that include the partition key are fast, and reads for queries on only the secondary index column require scatter-gather across all partitions. Global secondary indexes span all partitions and are partitioned by the secondary index key. Reads for queries on the secondary index column are fast (route to the correct index partition), writes require cross-partition coordination and may produce eventual consistency lag. DynamoDB’s Local Secondary Indexes are local; its Global Secondary Indexes are global with eventual consistency. Spanner’s secondary indexes are global with strong consistency.

What is the N+1 query problem and how do I fix it?

The N+1 query problem occurs when code fetches N parent objects and then issues one query per parent to fetch associated child objects — N+1 queries total. Fetching 100 orders and then fetching the customer for each order individually is 101 queries instead of 2. The fix is batch loading: replace the N individual queries with one query that fetches all needed child objects using an IN clause or JOIN. In ORM frameworks, this is called eager loading — configuring the relationship to load in a single query rather than lazily on access. In distributed databases, batching is especially important because individual queries may scatter across shards — batching multiple single-row lookups into one IN clause allows the database to execute shard queries in parallel.

How do I read a query execution plan to find missing indexes?

In PostgreSQL, run EXPLAIN ANALYZE before the query. Look for Seq Scan on large tables — this indicates no usable index exists for the WHERE clause column. The actual rows count shows how many rows were scanned; if this is large and the query’s filter is selective (returning few rows), an index on the filter column would significantly improve performance. Look for estimated vs actual row counts — large discrepancies indicate stale statistics that cause poor plan choices; running ANALYZE updates statistics. In Cassandra, run TRACING ON and look for full partition scans, which indicate that the query cannot route to a specific partition and is scanning the entire dataset.

Continue the Series

Series home: Distributed Systems — Concepts, Design & Real-World Engineering

Part 5 — Scalability & Performance

Previous: ← 5.6 — Backpressure and Overload Management

Next: 5.8 — Autoscaling Distributed Systems →

Related posts from earlier in the series:

Discover more from Rahul Suryawanshi

Subscribe now to keep reading and get access to the full archive.

Continue reading