Query Optimization
Practice this topic in a realistic system design interview
In this chapter, we'll learn how databases decide to execute a query, how to find and read the plan behind a slow query, and the most common techniques for making queries faster without adding more hardware.
Suppose we're building an e-commerce application. There's a page that shows a customer's recent orders.
When the application launched, the orders table had a few thousand rows, and the page loaded instantly. Two years later, the table has 50 million rows. The same page now takes 2 seconds to load.
Nothing in the code changed. The query is exactly the same as it was on day one. What changed is the amount of data the database has to work through to answer it.
At this point, a common reaction is to move to a bigger database server, add read replicas, or put a cache in front of the database. Those can help. But very often, the real problem is that the query is doing far more work than it needs to.
A query that reads 50 million rows to return 20 of them will stay slow on almost any hardware. And if we fix the query so it reads only the rows it needs, a single database server can often handle a lot more traffic.
That's what query optimization is about. To do it well, we first need to understand how the database runs a query.
1. How a Database Runs a Query
SQL is a declarative language. When we write a query, we describe what data we want, not how to get it.
We say: give me the 20 most recent orders for customer 42.
We don't say which index to use, which table to read first, or how to sort the results. The database figures that out on its own.
When a query arrives, the database goes through a few steps:
- Parse: The database parses the query and checks that it's valid, and that the tables and columns exist.
- Rewrite: It may rewrite the query into an equivalent form that's easier to optimize, for example by simplifying expressions or turning some subqueries into joins.
- Plan: Next comes the most important step. The query planner, also called the query optimizer, decides how the query will actually be executed.
- Execute: Finally, the executor runs that plan and returns the rows.
The same query can be executed in many different ways, and some of those ways are thousands of times faster than others. So the quality of the plan matters a lot.
2. The Cost-Based Optimizer
Most relational databases, including PostgreSQL and MySQL, use a cost-based optimizer. For each query, the optimizer considers several possible plans and estimates how expensive each one would be.
It looks at questions like these:
- Should it read the whole table, or use an index?
- If the query joins three tables, which table should it start with?
- Which join algorithm should it use?
- Should it sort the results, or read them from an index that's already in order?
To answer these questions, the optimizer needs to know something about the data. So the database keeps statistics for each table. These include the number of rows, the number of distinct values in each column, the most common values, and histograms showing how values are distributed.
Using these statistics, the optimizer estimates how many rows each step of the plan will produce. Then it assigns a cost to each plan based on the expected disk reads and CPU work, and picks the cheapest one.
The key point is that these are estimates. If the statistics are accurate, the optimizer usually picks a good plan. If they're wrong, it can pick a plan that's very slow. We'll come back to this later.