ORDER BY RAND() LIMIT 1 on a hot endpoint melted our MySQL primary

At 08:05 on a Tuesday our MySQL primary hit 100 percent CPU and stayed there. API p99 latency went from 120 ms to 9 seconds, and the connection pool started throwing:

SQLSTATE[HY000] [1040] Too many connections

Nothing had been deployed that morning. The spike lined up with the start of the working day in our largest region, when users open the app and land on the home screen. The home screen shows a "tip of the day" card for a learning product, picked at random from published tips in the user's language.

Reproducing it

The slow query log, with long_query_time = 0.5, was dominated by one statement:

# Query_time: 2.913507  Lock_time: 0.000004 Rows_sent: 1  Rows_examined: 1402311
SET timestamp=1770797112;
SELECT id, title, body FROM tips
WHERE status = 'published' AND lang = 'en'
ORDER BY RAND() LIMIT 1;

Rows sent: 1. Rows examined: 1.4 million. Running it by hand on a replica took 2.4 to 3.1 seconds every time, so it was not intermittent; the home screen simply got busier than the database could absorb at that cost.

What we ruled out

• Missing index. There was an index on (status, lang). EXPLAIN showed it in possible_keys, but the optimizer chose a full scan because the filter matched most of the table.
• Lock contention. Lock_time was microseconds and performance_schema.data_lock_waits was empty.
• A bad deploy. The query had not changed in two years. What changed was the table: a content import in January took tips from about 40,000 rows to 1.4 million, most of them English.

Root cause

ORDER BY RAND() cannot use an index for ordering, because the sort key is a new random value generated per row. MySQL must read every row that passes the WHERE clause, compute RAND() for each, and sort them (or keep a top-1 heap) before returning one. Cost grows linearly with the matching rows. At 40,000 rows it took 60 ms and nobody noticed. At 1.4 million rows with 300 home screen loads per second, it consumed all cores.

What is happening under the hood

EXPLAIN makes the plan obvious:

mysql> EXPLAIN SELECT id, title, body FROM tips
    ->  WHERE status = 'published' AND lang = 'en' ORDER BY RAND() LIMIT 1\G
           id: 1
  select_type: SIMPLE
        table: tips
         type: ALL
possible_keys: idx_status_lang
          key: NULL
         rows: 1398870
     filtered: 45.00
        Extra: Using where; Using temporary; Using filesort

Using temporary; Using filesort means every candidate row (including the body column, which is TEXT) is copied into a temporary structure and sorted. With LIMIT 1 the server can keep only the current minimum, which saves memory, but it still has to read and evaluate every row. Wide rows make it worse because the scan reads the full clustered index pages.

The same pattern exists in PostgreSQL as ORDER BY random(), with the same linear cost.

Environment

Minimal reproduction

CREATE TABLE tips (
  id     BIGINT UNSIGNED AUTO_INCREMENT PRIMARY KEY,
  status VARCHAR(16) NOT NULL,
  lang   CHAR(2) NOT NULL,
  title  VARCHAR(200) NOT NULL,
  body   TEXT NOT NULL,
  KEY idx_status_lang (status, lang)
);

-- load about 1M rows
SET SESSION cte_max_recursion_depth = 1000000;
INSERT INTO tips (status, lang, title, body)
WITH RECURSIVE seq (n) AS (SELECT 1 UNION ALL SELECT n + 1 FROM seq WHERE n < 1000000)
SELECT IF(n % 10 = 0, 'draft', 'published'), IF(n % 3 = 0, 'de', 'en'),
       CONCAT('Tip ', n), REPEAT('lorem ipsum ', 250)
FROM seq;

SELECT id FROM tips WHERE status = 'published' AND lang = 'en'
ORDER BY RAND() LIMIT 1;

On a laptop this takes around a second; time grows in a straight line as you add rows.

Who is affected

Any query that orders by a per-row random value on a large or growing result set: MySQL and MariaDB RAND(), PostgreSQL random(), SQLite RANDOM(), and ORMs that generate them (Laravel inRandomOrder(), Django order_by('?'), Rails order('RANDOM()')). It is harmless on small, bounded tables and dangerous on anything that grows.

The fix

We picked the approach that fits "random published tip in a language" and keeps every request to a couple of index lookups. No schema change was needed: an InnoDB secondary index stores the primary key at the end of every entry, so idx_status_lang is already ordered by (status, lang, id) and can serve a range seek on id within one status and language.

Then pick a random point in the id range and seek to the next matching row:

-- 1. id bounds for this filter (two index dives, cached in the app for 5 minutes)
SELECT MIN(id), MAX(id) FROM tips WHERE status = 'published' AND lang = 'en';

-- 2. seek to the first row at or after a random id
SELECT id, title, body FROM tips
WHERE status = 'published' AND lang = 'en' AND id >= ?
ORDER BY id
LIMIT 1;

In PHP:

$bounds = Cache::remember("tips:bounds:{$lang}", 300, fn () => DB::selectOne(
    'SELECT MIN(id) AS lo, MAX(id) AS hi FROM tips WHERE status = ? AND lang = ?',
    ['published', $lang],
));

$pivot = random_int($bounds->lo, $bounds->hi);

$tip = DB::selectOne(
    'SELECT id, title, body FROM tips
     WHERE status = ? AND lang = ? AND id >= ?
     ORDER BY id LIMIT 1',
    ['published', $lang, $pivot],
) ?? DB::selectOne(
    'SELECT id, title, body FROM tips WHERE status = ? AND lang = ? ORDER BY id LIMIT 1',
    ['published', $lang],
);

The fallback query handles the rare case where the pivot lands past the last matching row.

- $tip = Tip::published()->where('lang', $lang)->inRandomOrder()->first();
+ $tip = $this->randomTips->pick($lang);

Alternatives and trade-offs

• Random pivot plus seek (what we shipped). Two index lookups. The catch is bias: a row that follows a large gap in ids is picked more often. Our ids were dense, so the bias was small; we measured that the most frequent tip was chosen 1.9 times as often as the least frequent over a million draws. Fine for a tip widget, not fine for a lottery.
• Stored random column. Add rand_key DOUBLE NOT NULL DEFAULT (RAND()) with an index on (status, lang, rand_key), then WHERE rand_key >= RAND() ORDER BY rand_key LIMIT 1. Uniform enough, still index-only, costs one extra column and index. Use it when ids are sparse.
• Pick in the application. Cache the list of eligible ids per language (a few MB at most) and choose with random_int, then fetch by primary key. Perfectly uniform and the cheapest per request, but the list must be refreshed when content changes.
• PostgreSQL TABLESAMPLE SYSTEM. Reads only a sample of pages and is fast, but it samples blocks, not rows, and does not combine well with selective filters.

How to test the fix

# compare plans
mysql -e "EXPLAIN FORMAT=TREE SELECT id FROM tips WHERE status='published' AND lang='en' AND id >= 712345 ORDER BY id LIMIT 1" app

# load test the endpoint
k6 run --vus 200 --duration 2m scripts/home.js

The new plan reads one index range with rows: 1, and the query runs in under a millisecond. We also wrote a unit test that draws 10,000 tips from a seeded table with known gaps and asserts that every published tip appears and no draft or wrong-language tip ever does.

Confirming in production

We shipped behind a feature flag at 10 percent, then 100 percent. On the slow log the statement vanished. Performance Schema confirmed the change in examined rows:

SELECT DIGEST_TEXT, COUNT_STAR,
       ROUND(SUM_TIMER_WAIT / COUNT_STAR / 1e9, 2) AS avg_ms,
       ROUND(SUM_ROWS_EXAMINED / COUNT_STAR) AS rows_per_call
FROM performance_schema.events_statements_summary_by_digest
WHERE DIGEST_TEXT LIKE '%FROM `tips`%'
ORDER BY SUM_TIMER_WAIT DESC LIMIT 5;

Rows examined per call dropped from about 1.4 million to 1, average time from 2,700 ms to 0.3 ms, and primary CPU at the morning peak went from 100 percent to 31 percent.

Regression guard

We added a static check in CI that fails on inRandomOrder(, RAND() or random() inside an ORDER BY in application code, with an allowlist comment for small lookup tables. We also enabled log_queries_not_using_indexes on one replica that receives mirrored read traffic, with an alert when Rows_examined exceeds 100,000 for any single query.

Security implications

Unbounded per-request cost is a denial-of-service lever: any unauthenticated page that runs a full scan lets an attacker exhaust the database with ordinary traffic. The fix reduces that risk. The new code uses random_int, which is a cryptographically secure generator; that is not needed for tips, but we avoid weaker generators by default in case the pattern is copied somewhere selection must be unpredictable.

Prevention checklist

• Treat ORDER BY RAND() and its ORM wrappers as a code smell on any table that grows.
• Check Rows_examined versus Rows_sent in the slow log, not only query time.
• Re-run EXPLAIN on hot queries after large data imports.
• Cache bounds or id lists for random selection and refresh them on content change.
• Keep a mirrored replica with aggressive slow logging to catch scans before peak.

References

• MySQL 8.4 Reference Manual, ORDER BY Optimization: https://dev.mysql.com/doc/refman/8.4/en/order-by-optimization.html
• MySQL 8.4 Reference Manual, The Slow Query Log: https://dev.mysql.com/doc/refman/8.4/en/slow-query-log.html
• MySQL 8.4 Reference Manual, EXPLAIN Output Format: https://dev.mysql.com/doc/refman/8.4/en/explain-output.html
• PostgreSQL docs, SELECT, TABLESAMPLE: https://www.postgresql.org/docs/current/sql-select.html