How do you query 10B records under 100ms?

Question

IT Interview Practice · Accepted Answer

Design for the **access pattern first**, then pick partitioning + the right index/PK so any single query touches a small, bounded slice — never scans 10B rows. Sub-100ms over 10 billion records is not about a faster disk; it's about making the working set tiny.

```text
Query ─▶ Router ──▶ Partition (by tenant/time) ──▶ Index/PK lookup ─▶ ~thousands of rows
   │                    (prune 99.9% of data)         (B-tree / sort key)
   └─▶ Cache (Redis) ─▶ hit? return in <5ms
                        miss ▼
                   Columnar store (ClickHouse) for aggregates / scans
```

## Access patterns drive everything

Before choosing tech, ask: **point lookup or range/aggregate?** "Get user X's last 20 orders" is a point/range query — you want the partition and sort key to match it exactly. "Sum revenue by region this month" is an analytical scan — a row store is the wrong tool. Modeling the query first is what separates a design that works from one that looks reasonable but full-scans.

## Partitioning prunes the search space

Split the table by a key that appears in every query — usually **tenant_id + time**. With time partitions, a query for "last 7 days" reads 7 partitions and ignores the other 3 years. This is *partition pruning*: the router eliminates 99.9% of data before any index is consulted.

## Right index / PK design

Within a partition, the **primary key must front-load the query's filter columns**. In DynamoDB: partition key = `tenant`, sort key = `timestamp` → range queries are O(log n) + sequential read. In a columnar store like **ClickHouse**, the sorting key (`ORDER BY (tenant, ts)`) lets the engine skip granules and read only matching blocks. A covering index avoids the extra row fetch entirely.

## Store choice

- **Point lookups, high write:** NoSQL key-value (DynamoDB, Cassandra) — O(1)-ish by key, scales horizontally.
- **Analytics/aggregates:** columnar (ClickHouse, BigQuery) — reads only needed columns, vectorized.
- **Cache the hot 1%:** Redis in front absorbs repeated reads at <5ms; 10B rows but a few million hot keys.

## Interview perspective

The interviewer wants to see you say **"what are the queries?" before "what database?"**. Good candidates reach for indexes; great ones note that an index on 10B rows is itself huge — so you *partition first to shrink what the index covers*. Naming the row-vs-columnar split and the cache tier signals real scale experience.

**Common trap:** proposing one giant B-tree index as the answer. It helps point lookups but does nothing for the analytical scans, and its writes bottleneck ingestion.

## Trade-offs & failure modes

- **Wrong partition key** = cross-partition scatter-gather, latency balloons. Pick a key present in queries.
- **Hot partition:** a celebrity tenant overwhelms one shard — add a salting suffix.
- **Cache staleness:** invalidate on write or accept TTL lag.
- **Denormalization cost:** you often duplicate data per access pattern; storage is cheap, a 10-second query is not.

Access patterns drive everything

Partitioning prunes the search space

Right index / PK design

Store choice

Interview perspective

Trade-offs & failure modes

Related questions