Distributed Database Indexes: Architecture, Trade-Offs, and Internals

In monolithic relational databases, creating a secondary index is a well-understood operation: the database engine constructs a secondary data structure (typically a B+ Tree) on the specified column. Every index leaf node references the primary key or row offset, and point queries execute in logarithmic time.

However, when data scales beyond a single node and requires horizontal partitioning (sharding), indexing becomes significantly more complex. Secondary attributes no longer align with physical data placement, introducing fundamental trade-offs between write amplification, query latency, cross-network data transfer, and consistency guarantees.

---

1. Partitioning and the Query Alignment Problem

When scaling a distributed data store (such as Amazon DynamoDB, Apache Cassandra, or sharded MongoDB), datasets are partitioned across multiple physical nodes using a partition key (or shard key).

                  ┌──────────────────────┐
                  │    Incoming Write    │
                  │   Author ID: U1      │
                  └──────────┬───────────┘
                             │
                     Hash(Author ID)
                             │
             ┌───────────────┴───────────────┐
             ▼                               ▼
     ┌───────────────┐               ┌───────────────┐
     │    Shard 1    │               │    Shard 2    │
     │  (Author: U1) │               │  (Author: U2) │
     └───────────────┘               └───────────────┘

The Aligned Query Pattern

Consider a blogging platform where articles are sharded by author_id using consistent hashing or modulo hashing:

$\text{Shard ID} = \text{Hash}(\text{author\_id}) \pmod N$

When an application queries:

SELECT * FROM blogs WHERE author_id = 'U1';

The database routing tier (or proxy) hashes author_id = 'U1', immediately determines the target shard, routes the request to that specific node, and retrieves the records via local B+ Trees or SSTables. This operation is isolated, deterministic, and executes in $O(1)$ network hops.

The Misaligned Secondary Attribute Problem

Real-world applications rarely query exclusively by partition key. Suppose each blog also contains a category attribute (MySQL, Nginx, Go), and users need to fetch posts by category:

SELECT * FROM blogs WHERE category = 'MySQL';

Because data was sharded on author_id, records matching category = 'MySQL' are scattered uniformly across arbitrary shards based on who authored them.

Shard 1 (Author: U1)                     Shard 2 (Author: U3)
├── Blog 1 (Category: MySQL)             ├── Blog 2 (Category: Nginx)
└── Blog 9 (Category: Go)                └── Blog 4 (Category: MySQL)

Neither the client nor the database routing proxy knows which node hosts category = 'MySQL' blogs without querying the entire cluster.

---

2. The Naive Approach: Scatter-Gather (Fan-Out)

Without a dedicated secondary indexing strategy, the database routing proxy must perform a Scatter-Gather (Fan-Out) operation:

                         ┌──────────────────┐
                         │  Query: MySQL    │
                         └────────┬─────────┘
                                  │
                          Database Proxy
                                  │
                 ┌────────────────┴────────────────┐
                 ▼                                 ▼
          ┌─────────────┐                   ┌─────────────┐
          │   Shard 1   │                   │   Shard 2   │
          │ Local Scan  │                   │ Local Scan  │
          └──────┬──────┘                   └──────┬──────┘
                 │                                 │
                 └────────────────┬────────────────┘
                                  │ (Merge, Sort, Paginate)
                                  ▼
                           Client Response

1. Scatter: Broadcast the query in parallel to every shard in the cluster.
2. Local Evaluation: Each shard scans its local storage engine for matching records.
3. Gather: Shards return their candidate sets to the proxy.
4. Merge and Filter: The proxy aggregates, sorts, paginates, and returns results to the client.

System Failure Modes of Scatter-Gather

• The Tail-Latency Problem ($P_{99}$ Bottleneck): The total request latency equals the response time of the slowest shard. If one shard experiences GC pauses, disk contention, or CPU spikes, the entire query stalls.
• Partial Failures: If any single shard fails, drops connections, or times out, the database must either abort the query completely or return an incomplete, degraded result set.
• Bandwidth and Memory Exhaustion: Transferring large volumes of candidate records across internal network fabrics only to discard most of them during pagination (e.g., LIMIT 20) severely impacts database proxies and saturates network interfaces.

---

3. Global Secondary Indexes (GSI)

A Global Secondary Index (GSI) decouples the secondary index from the base table’s partition layout by creating an independently sharded data structure partitioned directly on the secondary attribute.

Base Shards (Partitioned by Author ID)
┌────────────────────────────┐    ┌────────────────────────────┐
│ Shard 1 (Author: U1)       │    │ Shard 2 (Author: U3)       │
│ • Blog 1 (Category: MySQL) │    │ • Blog 2 (Category: Nginx) │
│ • Blog 9 (Category: Go)    │    │ • Blog 4 (Category: MySQL) │
└────────────────────────────┘    └────────────────────────────┘
               │                                 │
               └───────────────┬─────────────────┘
                               ▼
GSI Shards (Partitioned by Category)
┌────────────────────────────┐    ┌────────────────────────────┐
│ GSI Shard A (Key: MySQL)   │    │ GSI Shard B (Key: Go, Nginx│
│ • Ref: (Blog 1, Shard 1)   │    │ • Ref: (Blog 9, Shard 1)   │
│ • Ref: (Blog 4, Shard 2)   │    │ • Ref: (Blog 2, Shard 2)   │
└────────────────────────────┘    └────────────────────────────┘

When a query searches for WHERE category = 'MySQL':

1. Hash the secondary key: $\text{Hash}(\text{'MySQL'}) \pmod K$.
2. Route directly to GSI Shard A.
3. Eliminate cluster-wide scatter-gather entirely; the lookup touches only the designated GSI partition.

Architectural Note: GSI storage can be physically isolated on dedicated compute nodes or logically co-located on existing base shards using separate local storage partitions. Regardless of physical layout, the data remains logically re-partitioned.

Data Projection Trade-Offs in GSIs

When creating a GSI, distributed databases allow engineers to choose what data gets projected into the index:

Projection Strategy	Storage Footprint	Read Path Efficiency	Network Overhead
Keys-Only (Primary Key References)	Minimal (stores only indexed attribute + base primary key).	Requires a two-phase read: fetch IDs from GSI, then fetch row attributes from base shards.	Higher network hop count ($1\text{ GSI hop} + N\text{ base shard fetches}$).
Full Document Projection	High index bloat (entire row is duplicated and re-partitioned).	Optimal single-hop query: GSI directly satisfies queries without touching base shards.	Minimal query overhead, but significant storage and write amplification.
Covering/Selected Attributes	Balanced (includes only frequently queried projection columns).	High for queries hitting covered attributes; degrades to two-phase if non-projected columns are requested.	Predictable, balanced profile.

Consistency and Write Amplification

Maintaining a GSI introduces significant overhead on base table mutations (INSERT, UPDATE, DELETE):

• Every write to a base table record requires a secondary write to the corresponding GSI shard.
• Because base records and GSI records rarely reside on the same physical server, cross-node consensus or distributed transactions (such as Two-Phase Commit) are needed if strong consistency is enforced across the index.
• To protect cluster availability and write throughput, many distributed systems (e.g., AWS DynamoDB) update GSIs asynchronously, offering eventual consistency for index reads.
• Due to write amplification and consistency cost, production distributed databases strictly enforce hard quotas on GSI creation (commonly capped between 5 and 20 per table).

---

4. Local Secondary Indexes (LSI)

A Local Secondary Index (LSI) restricts secondary indexing strictly within the boundaries of a single base partition.

Shard 1 (Partition Key: Author U1)
├── Base Table Data (Row Store / SSTable)
│   ├── Blog 1: { Category: MySQL, Title: ... }
│   └── Blog 9: { Category: Go,    Title: ... }
└── Local Secondary Index (Local B+ Tree on Category)
    ├── Go    ──► Blog 9
    └── MySQL ──► Blog 1

In an LSI, the index shares the exact same partition key as the underlying table data, but maintains an internal index (such as an embedded B+ Tree or LSM index) sorted by an alternate secondary attribute.

The Restrictive Query Requirement

An LSI requires the base table’s partition key in the query clause:

-- Supported efficiently by LSI (Single-Node Point Query):
SELECT * FROM blogs WHERE author_id = 'U1' AND category = 'MySQL';

-- CANNOT be answered by LSI without full cluster scatter-gather:
SELECT * FROM blogs WHERE category = 'MySQL';

Because the secondary index data resides locally on the exact same physical node as the primary data, LSIs offer distinct structural advantages:

• Strict Consistency Without Distributed Overhead: The database updates the primary row and the LSI atomically within a single local transaction (same memory space, single disk/WAL write). Distributed 2PC is not required.
• Zero Cross-Shard Network Hops: Read requests targeting both the partition key and secondary index column are completely fulfilled by a single shard.

---

5. Architectural Comparison: GSI vs. LSI vs. Scatter-Gather

Query Type               Partition Key Present?     Recommended Strategy
─────────────────────────────────────────────────────────────────────────
Point / Range Query      YES                        Base Partition Lookup
Secondary Attr Query     YES                        Local Secondary Index (LSI)
Secondary Attr Query     NO                         Global Secondary Index (GSI)
Ad-hoc Multi-Filter      NO (Low Frequency)         Scatter-Gather (Batch/Analytics)

Architectural Attribute	Scatter-Gather	Global Secondary Index (GSI)	Local Secondary Index (LSI)
Query Pattern	Arbitrary secondary filters without partition key.	High-frequency secondary filters without partition key.	Secondary filters paired with the partition key.
Partitioning Strategy	No dedicated index partitioning.	Re-partitioned by the secondary attribute.	Partitioned by the base table’s partition key.
Fan-Out Factor	Total cluster size ($N$ shards).	Single shard ($1$ GSI partition).	Single shard ($1$ base partition).
Consistency Level	Shard-dependent (often inconsistent reads).	Commonly eventual (strong consistency incurs heavy 2PC penalties).	Strong consistency natively supported at low cost.
Write Amplification	Lowest (no secondary index to maintain).	High (requires cross-node writes and updates).	Moderate (confined to local node writes).
Storage Overhead	None.	Substantial (duplicated keys or fully projected rows).	Low to moderate (local index structures).

---

Summary

Designing distributed database schemas requires modeling tables directly around query access patterns:

1. Base Table Partitioning handles lookups aligned with the primary distribution key.
2. Global Secondary Indexes (GSIs) transform cross-shard scatter-gather operations into targeted single-partition lookups at the expense of storage, write amplification, and cross-node consistency overhead.
3. Local Secondary Indexes (LSIs) optimize compound queries containing the partition key, offering ACID-compliant local index maintenance without multi-node coordination.