Index Table

Maintain a secondary lookup table that maps a non-primary-key attribute to primary keys, enabling efficient queries that the primary key structure does not support without requiring full-table scans.

The primary key structure of a NoSQL store supports only one access pattern efficiently. Secondary access patterns (lookups by email, customer ID, status) require either full scans or a manually maintained secondary index.

In relational databases, a secondary index provides this functionality natively. In NoSQL systems (DynamoDB, Cassandra, HBase), the primary key determines the physical storage layout and the one access pattern the system is optimized for. Any secondary access pattern requires a manually maintained index table or a costly full-table scan.

Example: a DynamoDB orders table with primary key order_id supports O(1) lookup by order ID. To support "list all orders for customer X", without an index table, you must scan the entire table. An index table customer_orders with partition key customer_id and sort key created_at maps each customer to their order IDs, enabling O(log N) range lookups.

Cassandra example: primary table partitioned by user_id supports "get user profile." An index table email_to_user_id with partition key email enables login-by-email lookups without a full partition scan.

Write-time consistency challenge: every write to the primary table requires a corresponding write to the index table. If the index write fails after the primary write succeeds, the index is inconsistent: it does not reflect the primary table's state. Mitigations: - Outbox pattern: write index update as part of the same transaction (where

supported) or via an outbox event that is idempotently applied.

- Eventually consistent index: accept that the index may lag the primary

table by seconds; use CDC (change data capture) to maintain it.

- Application-layer dual-write with retry: write to both tables, retry on

failure, accept brief inconsistency windows.

DynamoDB Global Secondary Indexes (GSI) automate this at the cost of eventual consistency: DynamoDB maintains the GSI asynchronously, so reads from a GSI may be slightly behind primary table writes. This is usually acceptable and removes the dual-write burden from the application.

Heap table vs clustered primary index: even where a relational database makes an index table unnecessary, how the primary table itself is stored still shapes index behavior. PostgreSQL's default table storage is a heap: rows have no particular physical order, and every index, including the one enforcing the primary key, is a separate B-Tree that points at a heap row via a TID (a row identifier: block number plus offset within the page). A primary-key range scan therefore still requires following TIDs into the heap, and physical row order depends on insert order and VACUUM's row movement, not on key order. InnoDB (MySQL's default and only storage engine for the primary key) instead uses a clustered primary index: the leaf pages of the primary key's own B-Tree are the row data, so there is no separate heap and a primary-key range scan is physically sequential I/O by construction. The cost lands on secondary indexes instead: an InnoDB secondary index stores the primary key value rather than a physical location, so a secondary-index lookup does two B-Tree traversals (secondary index to primary key, then primary key to row), where a PostgreSQL secondary index's stored TID gets there in one. This is a property of which engine was chosen, not something an application opts into the way it opts into an index table.

Local vs global secondary index does not arise on a single, unpartitioned table: one secondary index simply covers the whole table and every write updates it directly. The distinction appears once the base data is sharded (see the sharding pattern) and a secondary index is needed on a column that is not the shard key. A local secondary index is built and maintained independently per shard, indexing only that shard's rows: a write only touches its own shard's index, which is cheap, but a query that filters on the indexed column alone cannot know which shard holds a match and must scatter-gather to every shard. A global secondary index is instead a separate index structure, itself partitioned independently of the base table's shard key, covering rows from every shard: a query on the indexed column hits one place instead of fanning out, but every write must now keep two independently-partitioned structures consistent, which is materially harder. DynamoDB's GSI is exactly this: a global secondary index maintained asynchronously precisely because synchronously updating a separately-partitioned structure on every write is expensive to keep consistent; the eventual-consistency cost described above is not incidental to DynamoDB, it is inherent to any global secondary index over sharded data.