Window functions replace a habit

The query that produced the top three products per category read the sales table four times and took eleven seconds. It had been written that way because there was no other way to write it in MySQL, and the habit had outlived the constraint by about a decade in other databases and by two months here — 8.0 went GA in April.

The symptom

-- the shape everybody writes when there are no window functions
SELECT s.category, s.sku, s.sales
FROM sales s
WHERE (
    SELECT COUNT(*) FROM sales s2
    WHERE s2.category = s.category AND s2.sales > s.sales
) < 3
ORDER BY s.category, s.sales DESC;

-- 5.7
+----+--------------------+-------+---------+----------+
| id | select_type        | table | rows    | Extra    |
+----+--------------------+-------+---------+----------+
|  1 | PRIMARY            | s     | 218440  | filesort |
|  2 | DEPENDENT SUBQUERY | s2    | 218440  | ...      |
+----+--------------------+-------+---------+----------+

11.4 sec

The DEPENDENT SUBQUERY line is the whole problem: it runs once per row of the outer query. Two hundred thousand rows, each triggering a scan of two hundred thousand rows, and the only reason it completes at all is that the optimiser stops early.

Why it happens

Ranking within a group requires comparing each row with its peers, and without a window function the only way to express that in SQL is to correlate a subquery on the grouping key. The alternative — a self join with a GROUP BY and a HAVING — has the same problem in a different shape.

MySQL was the last of the major databases to add them. PostgreSQL had them in 8.4, in 2009. That nine-year gap is why so much application code carries a loop that fetches rows and computes the ranking in PHP, which works and moves the cost to the wrong place.

The fix

ROW_NUMBER and the frame that decides everything

SELECT category, sku, sales FROM (
  SELECT category, sku, sales,
         ROW_NUMBER() OVER (
           PARTITION BY category
           ORDER BY sales DESC, sku          -- the tiebreak matters
         ) AS rn
  FROM sales
) ranked
WHERE rn <= 3;

-- 8.0
+----+-------------+------------+--------+---------------------------+
| id | select_type | table      | rows   | Extra                     |
+----+-------------+------------+--------+---------------------------+
|  1 | PRIMARY     | <derived2> | 218440 | Using where               |
|  2 | DERIVED     | sales      | 218440 | Using temporary; Window   |
+----+-------------+------------+--------+---------------------------+

0.31 sec

One pass instead of a scan per row. The tiebreaker on sku is not decoration — without it, two products with identical sales come out in an order MySQL is free to change between executions, so the report is non-deterministic in a way that only shows up when somebody compares two runs.

The three ranking functions disagree about ties and the difference is invisible in test data. ROW_NUMBER gives 1,2,3,4 and picks arbitrarily among equals; RANK gives 1,2,2,4; DENSE_RANK gives 1,2,2,3. “Top three products” means ROW_NUMBER, “top three price tiers” means DENSE_RANK, and choosing the wrong one produces a report that is quietly incorrect rather than obviously broken.

The frame clause, which has a default you did not intend

-- running total. probably not what was wanted.
SUM(amount) OVER (PARTITION BY customer_id ORDER BY placed_at)

-- partition total
SUM(amount) OVER (PARTITION BY customer_id)

-- explicit, and worth writing even when it is the default
SUM(amount) OVER (
  PARTITION BY customer_id ORDER BY placed_at
  ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
)

Adding ORDER BY to a window changes what the aggregate means, which is not what ordering does anywhere else in SQL. The default frame becomes everything from the start of the partition to the current row, so a SUM that looked like a total is a running total. ROWS counts rows and RANGE counts values, so with ties they give different answers.

LAG and LEAD, which delete application code

SELECT
  placed_at,
  total,
  LAG(total, 1, 0) OVER w AS previous,
  total - LAG(total, 1, 0) OVER w AS delta,
  TIMESTAMPDIFF(DAY, LAG(placed_at) OVER w, placed_at) AS days_since
FROM orders
WHERE customer_id = 4471
WINDOW w AS (ORDER BY placed_at);

This is the one that most often replaces a loop in PHP rather than a subquery — the loop that kept the previous row in a variable to compute a difference. The third argument to LAG is the default when there is no previous row, which saves wrapping the whole expression in a COALESCE. Naming the window once with WINDOW w AS and referring to it is worth doing as soon as the same specification appears twice.

Common table expressions, including the recursive one

WITH RECURSIVE tree AS (
  SELECT id, parent_id, name, 0 AS depth
  FROM categories WHERE id = 12

  UNION ALL

  SELECT c.id, c.parent_id, c.name, t.depth + 1
  FROM categories c JOIN tree t ON c.parent_id = t.id
  WHERE t.depth < 10          -- the guard that must be there
)
SELECT * FROM tree ORDER BY depth, name;

The depth guard is not optional. A cycle in the data — which happens the first time somebody sets a category as its own ancestor through the admin — recurses until cte_max_recursion_depth stops it with an error, and the default is 1,000. An explicit limit turns an error into a bounded result.

The version this replaced was a query per level in a loop, so the number of round trips depended on the data and nobody could say what the worst case was. One query, one round trip, and it stays one as the tree grows.

Where they do not help, and the index that still decides

A window function is computed after the rows have been selected, so it cannot use an index to avoid reading them. Filtering on a window result means the filter happens after the whole partition has been materialised, which is why the derived-table wrapper exists and why it cannot be pushed down.

-- reads every row in the table, ranks all of them, then keeps 147
SELECT * FROM (
  SELECT *, ROW_NUMBER() OVER (PARTITION BY category ORDER BY sales DESC) rn
  FROM sales
) x WHERE rn <= 3;

-- restrict FIRST, so the window operates on less
SELECT * FROM (
  SELECT *, ROW_NUMBER() OVER (PARTITION BY category ORDER BY sales DESC) rn
  FROM sales
  WHERE placed_at >= '2018-01-01'      -- uses the index
) x WHERE rn <= 3;

-- and the index that makes the window's sort disappear entirely
CREATE INDEX idx_win ON sales (category, sales DESC, placed_at);

That index is the descending one 8.0 made real, and it matters here specifically: a window partitioned by category and ordered by sales DESC can read the index in order and skip the sort. EXPLAIN showing Using temporary against the window step is the sign that it did not, and the difference on a large table was another factor of four.

The general rule is that predicates the optimiser can push into the inner query belong there and predicates on the window result cannot be pushed at all. Writing the restriction inside the derived table rather than outside is a one-line change that people leave out because both versions return the same rows.

The upgrade itself, and the collation nobody expects

Getting to 8.0 is the prerequisite and it is not a drop-in. Two changes will affect any existing application.

-- the default character set changed
SHOW VARIABLES LIKE 'character_set_server';
character_set_server  utf8mb4          -- was latin1

-- and the default collation with it
SHOW VARIABLES LIKE 'collation_server';
collation_server      utf8mb4_0900_ai_ci   -- was utf8mb4_general_ci

-- which means a new table cannot index-join an old one:
-- EXPLAIN: Using where; Using join buffer (Block Nested Loop)

The block nested loop in a plan that used to use an index is the symptom, and the cause is a table created after the upgrade joining one converted from 5.7. Both sides have to agree on the collation. Setting it explicitly in every CREATE TABLE rather than relying on the server default is the discipline that prevents it, and auditing the whole schema afterwards is one query against information_schema.

The other change worth knowing before it bites is that GROUP BY no longer implies a sort. Queries that relied on that — and there are more of them than anyone admits — return rows in a different order, silently, which is a behavioural change in exactly the reports most likely to be compared against last month’s.

The reports that were computing this in PHP

The larger win on that codebase was not the eleven-second query. It was the four report classes that fetched every row and computed rankings, running totals and period-over-period deltas in application code, because that had been the only option.

// what it was: 218,440 rows into PHP, ranked in memory
$rows = $db->query('SELECT category, sku, sales FROM sales')->fetchAll();

$byCategory = [];
foreach ($rows as $row) {
    $byCategory[$row['category']][] = $row;
}

foreach ($byCategory as &$group) {
    usort($group, function ($a, $b) {
        return [$b['sales'], $a['sku']] <=> [$a['sales'], $b['sku']];
    });

    $group = array_slice($group, 0, 3);
}
unset($group);

That version needed 380 megabytes of memory, which is why the report ran as a nightly job rather than on demand — and why the numbers on the dashboard were up to a day old. Moving the ranking into the query took the memory to under a megabyte and made the page live, which was a product change disguised as a performance fix.

The tiebreaker detail matters here too, and in the PHP version it was already correct because usort is unstable and somebody had been bitten by it. Translating it faithfully to ORDER BY sales DESC, sku is what kept the two result sets identical, and it is exactly the kind of subtlety that gets dropped when a query is rewritten from a description rather than from the code.

Verifying it worked

$ mysql -e 'EXPLAIN ANALYZE ...' < top-three.sql
-> Filter: (rn <= 3)  (cost=48210 rows=72813)
     (actual time=0.14..318 rows=147 loops=1)
   -> Window aggregate  (actual time=0.13..291 rows=218440 loops=1)

# before  11.4s   218,440 rows examined per outer row
# after    0.31s  218,440 rows examined once

$ diff <(mysql -Nse "$(cat old.sql)") <(mysql -Nse "$(cat new.sql)")
# no output — identical result sets

Diffing the two result sets is the assertion that matters and is easy to skip once the new query is thirty times faster. It caught a real difference on the first attempt: the old subquery used > and therefore included four rows where three tied, and the window version with a tiebreaker returned exactly three. Both are defensible; only one of them was what the report had been showing for two years.

The gap between the estimated and actual row counts in EXPLAIN ANALYZE is the other thing to read. A large discrepancy means the statistics are stale or the predicate is one the optimiser cannot estimate, and both have known fixes — it is the diagnosis that plain EXPLAIN cannot give you, because plain EXPLAIN only ever shows the guess.

What this costs

MySQL and MariaDB have diverged, and portable SQL is now a choice rather than a default. MariaDB 10.3 has window functions and CTEs, and it also has system-versioned tables and sequences that MySQL does not, and its ANALYZE output is a different shape. Code that has to run on both is code written to the intersection, which is a real constraint on a product shipped to customers who choose their own database and no constraint at all on an application you deploy yourself.

The subtler cost is that these queries are harder to read for anyone who has not used them, and a team where one person writes window functions and nobody else can modify them has traded a performance problem for a maintenance one. Reviewing the first few together, and writing the frame clause out explicitly even when it is the default, is most of what makes them a shared tool rather than a private one.