Design tables for your queries

After the entities step, the interviewer looks at your tables and asks: "This screen needs data from five tables. Will it be fast?" Or: "Would you store the restaurant name inside the order?"

A weak answer has two forms. One never looks at the queries. The other copies everything "for speed" and does not say what it costs. A strong answer lists the queries with numbers first. Then it counts how many rows each query reads, and it copies a fact only where the count is too high. It also says how each copy stays right.

At SDE-1 level, explain one copy and why it makes a read faster. At SDE-2 level, count rows read and extra writes. At SDE-3 level, also say who keeps each copy right, and what happens when a write fails half way.

Remember the school office of lesson 18. Teacher names live in one short list, and each fee line holds only a teacher number. The data is clean. But all day, parents come to the window and ask: "Who is my child's class teacher, and what is the phone number?" Each time, the clerk opens the register. Then the clerk opens the teacher list and matches the two.

So the clerk writes the teacher name on each child's card. A parent now gets the answer from one card. The cost is that the name now lives in two places. If a teacher changes, two places need a fix.

This lesson makes that choice with numbers.

Start with the queries

In lesson 17 you met the access pattern: how the app uses its data. Here it becomes the first step of the table design. A query is a request to a database to read or change data.

1. List the main queries. For each one, write how often it runs per second at the busiest time.
2. Start from the clean tables of lesson 18. They are the source of truth: the one place where each fact is kept and where it is correct.
3. For each query, count the rows it reads.
4. Fix only the queries that read too many rows.

Count the rows read

A join combines rows from two tables (lesson 17). The time of a query grows with the number of rows the database must read. So count them. Suppose a screen shows 20 orders. Each order needs the restaurant name, which is in another table. That is 20 order rows plus 20 restaurant rows. If it also needs a total, the database must read the order's items and add up the prices. That is more rows again.

Many rows read many times a second is expensive. Nine rows read a few hundred times a second is not worth any trouble.

Copy on purpose

Denormalisation means copying a fact into more than one place on purpose, so that a read needs fewer rows. Lesson 18 gave you the rule to keep each fact in one place. Here you break the rule on purpose, for a query that you counted. There are five kinds of copy:

1. A snapshot. You copy a fact as it was at one moment, and you never update it. The price paid in an order line (lesson 18) is one. So is the restaurant name on a receipt. The restaurant may change its name later, but an old receipt must keep the old name. A snapshot is history, so it needs no update, and nothing has to keep it equal to its source.
2. A live copy. You copy a fact that must follow its source. The customer's phone number inside each order is one. When the number changes, you must change every copy.
3. A stored result. You work out an answer once, when the data changes, and keep it. The order total is one: add up the items when the order is made, and save the total. An average rating is another. Save the sum of the stars and the count of reviews, and divide when you show it. If you save only a rounded average, each new review adds a small rounding error.
4. A second table for one question. The same facts are written into a new table that is built for one query.
5. A whole record in one piece. In a document database (lesson 17), the items of an order sit inside the order document.

What a copy costs

• More writes. One change may need several writes. A snapshot costs no extra write, because you already know the value when the row is made.
• More space. Each copy takes bytes.
• Copies can disagree. This is the update anomaly of lesson 18 again. If one write succeeds and the other fails, two places show two answers.

Keeping copies right

1. Name one source of truth. If two copies disagree, the source wins, and you can rebuild the copy from it.
2. Write the copy and the source together. If both are in one database, use a transaction (lesson 17). It applies a group of changes all together or not at all.
3. If the copies are in different databases, one write can fail. Then run a repair job. It compares each copy with the source and fixes the difference.
4. Update every copy from one piece of code. If four screens each update their own copy, one of them will be forgotten.

In a wide-column store

Lesson 17 said that a wide-column store has no joins, and that you make one table for each question. This is the same idea, taken to the end. Each table has a partition key, the value that the question looks things up by. Its rows are sorted by a second key. For "my 20 newest orders", the table is partitioned by customer, with rows sorted by time, newest first. The query reads the first 20 rows of one partition. For "the last 50 orders of one restaurant", you make a second table, partitioned by restaurant. Every new order is written into both.

SwadKart, the food app of lessons 17 and 18. The clean tables are customers, restaurants, orders and order_items. order_items holds quantity and price_paid.

Assumptions (made up to teach with):

• 1,000,000 orders a day (lesson 17), and 3 items in each order (lesson 18). The peak is 10 times the average of about 12 orders a second, which is 120 orders a second.
• Each order changes status 4 times after it is made: accepted, ready, picked up, delivered.
• One review for every 10 orders. A restaurant has 2,000 reviews on average.
• At the peak, four queries run. Their rates are in the table below.

Step 1: count the rows, before any copy.

• Q1, "My orders": 20 order rows + 20 restaurant rows (for the names) + 60 item rows (20 x 3, for the totals) = 100 rows. This answers the predict box.
• Q2, "last 50 orders of one restaurant", with the customer name and the total: 50 order rows + 50 customer rows + 150 item rows (50 x 3) = 250 rows.
• Q3, "one order in full", with the current phone and the dish names: 1 order + 1 customer + 1 restaurant + 3 items + 3 dishes = 9 rows.
• Q4, "restaurant page", with the average rating: the 2,000 review rows, to add up the stars. Count 2,000 rows.

Step 2: choose a copy for each.

• Q1: copy restaurant_name (a snapshot) and total (a stored result) into the orders row. Now Q1 reads only the 20 order rows.
• Q2: copy customer_name (a snapshot) into the orders row. Now Q2 reads 50 rows. The total is already there.
• Q3: leave it. It needs the current phone, and it reads only 9 rows. A copy would save little and would need updates.
• Q4: store rating_sum and rating_count in the restaurants row (a stored result). Now Q4 reads 1 row. Example: 8,400 stars over 2,000 reviews is 4.2. A new 5-star review makes it 8,405 over 2,001, which is 4.2004.

Step 3: the reads each second.

The total before is 300,000 + 50,000 + 4,500 + 600,000 = 954,500 rows a second. After: 60,000 + 10,000 + 4,500 + 300 = 74,800. That is 954,500 / 74,800 = 12.8 times fewer rows (rounded).

Step 4: the writes.

• A new order is 1 order row + 3 item rows = 4 writes. The copies cost no extra write, because the name and total are known when the row is made. A status change is 1 write.
• At the peak: 120 x 4 = 480 writes a second for new orders, and 120 x 4 = 480 for status changes. That is 960.
• Reviews: 120 / 10 = 12 a second. Each one writes the review row. With the stored rating, the same transaction also updates the restaurant row: 12 extra writes a second, so the writes grow from 972 to 984. That is 12 / 972 = 1.2% more.
• The extra writes of 12 a second remove 600,000 - 300 = 599,700 reads a second. That is about 50,000 reads saved for each extra write.

Step 5: the space. The copies add three things to each order row. The restaurant name takes at most 50 bytes (lesson 18 gives 50 for name and area together). The customer name takes 30 bytes (assumed). The total takes 8 bytes. That is at most 50 + 30 + 8 = 88 bytes. 1,000,000 x 88 = 88,000,000 bytes = 88 MB a day. In a year, 88 MB x 365 = 32,120 MB, about 32 GB.

Step 6: a live copy, for contrast. A restaurant has 1,000,000 / 100,000 = 10 orders a day, which is 3,650 a year. If the name were a live copy, one rename would mean 3,650 writes. Old receipts would show the new name. The snapshot is the right choice.

Step 7: the same design in a wide-column store. There are no joins, so Q1 and Q2 each need their own table. A new order is written to 2 tables + 3 item rows = 5 writes. A status change must update both tables: 2 writes. At the peak: 120 x 5 = 600 writes for new orders, plus 120 x 4 x 2 = 960 for status changes. That is 1,560 writes a second. Before, it was 960 (reviews left out). That is 1,560 / 960 = 1.6 times more writes, and it buys reads that never join.

• Copying solves a query that reads too many rows: here Q1 went from 100 rows to 20, and all four queries from 954,500 to 74,800 rows a second. It costs a little more space (32 GB a year here), some extra writes (12 a second for the rating), and copies that can disagree. I would change my choice when the copied fact starts to change often, or when the query becomes rare.
• Snapshots solve history, and cost nothing to keep right. Live copies cost one write for each copy, each time the fact changes. I would use a live copy only for a fact that changes rarely and is read very often.
• One table for each question solves reads in a store with no joins. It costs more writes, here 1.6 times. I would choose it when the reads are many more than the writes.

"Copying data is always bad design." You make it after the clean design, for a query that you counted. In the example, 12 extra writes a second saved about 600,000 reads a second.

"Put everything in one big table, so every query reads one row." Different queries need different sort orders and different parts of the data. One table cannot suit all of them.

"Every copy must be updated when its source changes." A snapshot must not be updated. The restaurant name on an old receipt, and the price paid, are history.

1. Name three of the five kinds of copy. Which one is never updated, and why?
2. A product page shows 30 reviews, each with the author's name. The database reads the 30 review rows and the 30 user rows, and the page opens 1,000 times a second. (a) How many rows a second? (b) How many if the author name is copied into the review row? (c) Each user wrote 40 reviews on average, and 500 users rename themselves each day. If the copy follows the rename, how many extra writes a second?
3. A team copies the order status into four tables. Four pieces of code update them. A customer sees "delivered" on one screen and "on the way" on another. What went wrong? What do you change?