Tables From Query Patterns

The problem: a table built from the entity

In a relational database you usually start from the entities, one table each, and let joins and indexes answer whatever the app asks later. Stores that spread data over many nodes, such as Cassandra or DynamoDB, don't join tables, and a query is only fast when it goes to one key or one partition. There the key decides which questions are cheap, so you design the tables from the questions.

Take a chat app's message history. The obvious table has one row per message, keyed by message_id. Opening a chat asks for its 50 newest messages, about 20,000 times a second, but rows are placed on nodes by message id, so a chat's messages sit on every node, mixed with all the others. Every chat open reads the whole table.

Start from the access patterns

Before choosing any key, list the questions the app asks the store, its access patterns, each with how often it runs:

query                                         how often
Q1  the 50 newest messages of a chat          20,000 a second
Q2  a user's chats, newest message first      5,000 a second
Q3  one message, from a reply or a link       rare
Q4  everything a user sent in 2024 (export)   once a month

Each busy query needs a key that serves it from one partition; the rare ones can reuse a key or be slow.

How it works: partition key and sort key

A key in these stores has two parts. The partition key decides which partition a row joins: rows that share it are stored together, on one node and its copies. The sort key (Cassandra calls it a clustering key) keeps the rows inside a partition in order, so the store can read a range of them and stop. Together they form the row's primary key, which must be unique.

For Q1, the partition key is conversation_id and the sort key is message_id, newest first. Ids that grow with time, such as Snowflake-style ids, make id order time order and keep two messages sent in the same millisecond apart. Here is Q1 on a small table, 12 messages in 3 chats on 3 nodes, asking for chat c2's 3 newest:

design                          nodes asked   rows read
A: key message_id               3             12
B: partition conversation_id    1             3

In design A, c2's 5 messages sit on all three nodes, so each node reads every row to find them. In design B they form one partition, already newest first, and the store reads the first 3 rows. At full size, design B reads 50 rows from one partition however big the table grows.

A second busy query gets a second table

Q2 lists a user's chats, newest message first. If Ana is in 200 chats, the messages table holds them in 200 partitions, and 5,000 Q2s a second would be 1 million partition reads a second. So add a second table, chat lists, with partition key user_id and sort key last_message_at: one row per chat the user is in, already in the order Q2 shows them.

The chat list is denormalized: it repeats facts from the messages table, like the time of each chat's last message. So every new message writes one message row plus one chat-list row per member: 3 rows for a chat of two, 7 for a group of 6, 101 for a group of 100. A sort key can't be changed in place in Cassandra or DynamoDB, so moving a chat to the top is a delete plus an insert. The write also needs the chat's members: one more small table, keyed by conversation_id.

Q2 now reads one partition instead of 200; the price is keeping the copies in step. Write them in a batch the store applies in full (Cassandra's logged batches, DynamoDB's transactions) or from a queue that retries.

Rare queries: reuse a key or run a batch job

Q3 opens one message from a reply or a link. If the link carries the chat's id as well as the message's, it's one row in one partition of the messages table: no new table. If links carried only the message id, you would need a small lookup table from message id to chat.

Q4 names no key at all. A table for it would add a write to every message to serve one monthly export. Instead, a batch job scans every partition once a month, often from a copy kept for analytics. It can take hours; nobody is waiting.

When one partition grows too big

A public group with 50,000 members might get about 500,000 messages a month. At about 100 bytes each, its partition grows 50 MB a month: 1.2 GB after 2 years, 12 times the 100 MB or so that a common rule of thumb for Cassandra allows. A partition sits whole on one node and its copies, so adding nodes doesn't split it.

The fix is a time bucket in the partition key: (conversation_id, month). Each month of a chat is its own partition, about 50 MB for the big group, and old months spread over other nodes. The month comes from the message id, so the app always knows where to read. The price: early in a month, Q1 finds fewer than 50 messages in this month's partition and reads last month's too, 2 partitions, and a quiet chat may step back through several months. Discord's engineering blog described this shape for its messages in 2017: Cassandra, partitioned by channel and a bucket of about 10 days, sorted by message id.

A bucket caps a partition's size, not its traffic: this month's partition still takes all of the chat's new messages, and a chat that thousands read at once needs a cache in front.

The order of work

1. List the queries the app must answer, each with how often it runs.
2. Pick a partition key for the busiest query, so it reads one partition.
3. Pick the sort key, so its rows come back in the order it needs.
4. Add a table, a copy of the data, for each other busy query.
5. Let the rare queries reuse a key, or run them as a batch scan.

Where it shows up in design interviews

This is the Data step of the interview framework. Once you've named the entities, say: "These are my access patterns, and this is the key that serves each." Name the busy queries with their rates, each table's partition and sort key, what's left to a batch job, and the cost in writes. That answers "how is that one partition?" before it's asked.

Common interview questions

Why not one table with secondary indexes?

In Cassandra a secondary index is stored on each node next to that node's rows, so a query by it alone still asks every node. In DynamoDB a global secondary index is in effect a second table with another key, which the store updates a moment after each write.

Is a partition key the same as a shard key?

Nearly. The store hashes the partition key to pick the nodes that hold the partition, as a shard key picks a shard, so a query that names it goes to one place. The sort key adds order inside the partition.

What happens when a new query comes along later?

If it names an existing partition key and reads in its sort order, or a range of it, it needs nothing new. Otherwise you add a table shaped for it and fill it from the existing data with a batch job: unplanned questions cost more than in SQL.

Isn't storing the same data twice risky?

It costs writes and space, and the copies can disagree for a moment. Keep one table as the source of truth: the chat lists can be rebuilt from the messages.

Summary

• List the access patterns with their rates before choosing any key.
• The partition key is what the busy query names; the sort key is the order it reads in.
• Each other busy query gets its own table, a denormalized copy, at extra writes per message.
• Rare queries reuse a key or run as a batch scan.
• A partition that grows without limit gets a time bucket; a query may then read 2 partitions.