Indexing a report query that reads the whole orders table

The daily sales report took thirty-eight seconds. It runs against a table of 1.2 million orders, and for most of a year nobody minded, because thirty-eight seconds is survivable when it happens once with a cup of coffee in hand. Then it started being opened per branch, fourteen times in a row, and became the slowest thing anybody did all day. The query is not badly written. It simply had no index it could use, and the two obvious indexes both turned out to be useless.

The symptom

One query, no ORM in the way, no N+1 hiding behind it. This is the whole report:

SELECT o.id, o.reference, o.placed_at, o.total, c.name
  FROM orders o
  JOIN customers c ON c.id = o.customer_id
 WHERE o.placed_at >= '2013-02-01'
   AND o.placed_at <  '2013-03-01'
   AND o.status = 'complete'
 ORDER BY o.total DESC
 LIMIT 200;

February holds a little under nine thousand completed orders and the report shows two hundred of them. EXPLAIN says what finding those two hundred costs:

mysql> EXPLAIN SELECT o.id, o.reference ... G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: o
         type: ALL
possible_keys: NULL
          key: NULL
         rows: 1184506
        Extra: Using where; Using temporary; Using filesort

type: ALL is a full table scan. possible_keys: NULL is the line worth reading twice — MySQL did not weigh an index and decline it, there was no candidate at all. The row count is an estimate, but when the estimate is the entire table the estimate is not the interesting part.

Why it happens

The table carried one index besides the primary key, on customer_id, added the day somebody needed a customer’s order history. Nothing in the report touches customer_id.

The instinct is to index placed_at. The second instinct, after that fails to help, is to index total. Both were tried against a copy of the table and neither took the query below thirty seconds.

-- serves the filter, leaves the sort
ALTER TABLE orders ADD INDEX idx_placed_at (placed_at);

-- serves the sort, leaves the filter
ALTER TABLE orders ADD INDEX idx_total (total);

An index is one ordered structure and it can be read in one order. A B-tree on placed_at finds February in a few page reads, then hands MySQL nine thousand row pointers in date order that still have to be sorted by total — that is the Using filesort. A B-tree on total produces rows already in the right order, and then every one of them has to be fetched to discover whether it is even in February, which is 1.2 million random lookups into the primary key. The optimiser priced that correctly and went back to the table scan.

So the question is not which column to index. It is whether one index can do both jobs at once, and it can, provided the columns sit in the order the query consumes them.

The fix

The ordering rule is equality conditions first, then the range, then the sort. status is an equality, placed_at is a range, total is the sort, and that is the index:

ALTER TABLE orders
  ADD INDEX idx_status_placed_total (status, placed_at, total);

Then EXPLAIN again, before a single line of application code is touched. If the plan has not moved there is nothing to deploy, and finding that out costs one statement instead of one release.

mysql> EXPLAIN SELECT o.id, o.reference ... G
*************************** 1. row ***************************
           id: 1
        table: o
         type: range
possible_keys: idx_status_placed_total
          key: idx_status_placed_total
      key_len: 12
         rows: 8934
        Extra: Using where; Using index; Using filesort

Using filesort is still there, and it should be. A range condition ends the part of an index MySQL can use for ordering, so the sort by total cannot be free no matter how the columns are arranged. What changed is what gets sorted: 8,934 rows rather than 1,184,506, inside sort_buffer_size, with no temporary table on disk. Using index is the other half — total is in the index, so the sort never touches the table at all.

The two answers I did not take

Both were offered by people who had solved real problems with them. Neither addresses a query that reads the whole table.

The first was to cache the report output. Redis is already in this stack, so it would have taken an afternoon — and it would have moved thirty-eight seconds from every request to the first request of the morning, which is a real improvement and not the one being asked for. The report is parameterised by branch and date range, so the miss rate is decided by how inventively somebody uses the date picker. Worse, the fourteen branch reports are opened within about a minute of each other, so a cold cache fires fourteen concurrent full table scans at a server that can comfortably sustain one.

The second was to move the orders into MongoDB, which this year is the suggestion attached to any sentence containing the words slow and reporting. It is worth being precise about what that would fix here: nothing. The query is slow because it reads 1.2 million rows to answer a question about nine thousand, and a collection scan over 1.2 million documents is the same work under a different name. 2.4 has B-tree indexes with the same compound-prefix rules, so the fix would be this index in another syntax — after a migration, a rewrite of every write path, and the loss of the join to customers. The schema was never the problem.

Verifying it worked

The EXPLAIN above is the first check and the cheapest. The second is the report itself. The third is a week of the slow query log, because a plan that is right for one date range can still be wrong for another.

$ time mysql shop < report.sql > /dev/null
real    0m0.412s

# one working week of the slow log, before and after
$ grep -c '^# Query_time' /var/log/mysql/slow-before.log
612
$ grep -c '^# Query_time' /var/log/mysql/slow-after.log
4

The four survivors were the same statement with a twelve-month range, which selects roughly 108,000 rows and is therefore a different question needing a different answer. Nobody had mentioned that report existed.

What this costs

The index is 340 MB, and on a box with 8 GB of RAM that is real money, because it competes with the data for the InnoDB buffer pool.

SELECT ROUND(data_length  / 1048576) AS data_mb,
       ROUND(index_length / 1048576) AS index_mb
  FROM information_schema.tables
 WHERE table_schema = 'shop'
   AND table_name   = 'orders';

It also makes every insert slower. orders is the busiest table in the schema and now maintains a third secondary index on every row, in a random position rather than at the end, because status sorts ahead of placed_at and completed orders land between existing entries. The measured cost was a few percent on a bulk import — small, paid on the write path forever, to make one read fast once a day. That trade is worth saying out loud rather than discovering later.