MySQL оптимизация: ORDER BY RAND()

Лирическое вступление:

Довольно часто у нас возникает потребность выборки случайных данных из mysql базы данных. Как правило времени нет и используется самая простая конструкция вида SELECT [что-то] FROM [где-то] WHERE [то и сё] ORDER BY RAND(). Эта конструкция работает на ура. Но вот прототип выезжает на продуктовые сервера и такой милый сердцу запрос вдруг начинает выпадать в топы медленных логов. Ниже будут рассмотрены несколько возможностей для оптимизации этого запроса по нарастанию их эффективности:

В первых примерах мы полагаем что ID стартует с номера 1 и в ID нет разрывов между 1 и максимальным ID.

#1. Передать всю работу в приложение

Мы можем тупо слить всю работу по определению случайного номера в приложение.

SELECT MAX(id) FROM random;
## генерируем случайный ID в приложении
SELECT name FROM random WHERE id = id_из_приложения

Так как MAX(id) == COUNT(id) нам всеголишь нужно сгенерировать случайное число между 1 и MAX(id), передать его в запрос к БД и получить свою случайную строку.

Первый SELECT у нас фактически NO-OP и он оптимизирован по самое “не балуйся”. Второй запрос это eq_ref по константе и он тоже очень быстр.

#2. Делаем всю работу на стороне базы данных

Но настолько ли необходимо делать случайные выборки через приложение? Может стоит вынести “грязную” работу на сторону базы данных (прим. пер.: на самом деле первый способ это практически сферический конь в вакууме – большинство реальных задач будет выходить за рамки его применимости)

# генерируем случайный ID
> SELECT RAND() * MAX(id) FROM random;
+------------------+
| RAND() * MAX(id) |
+------------------+
|  689.37582507297 |
+------------------+

упс, это число типа double, а нам нужен int

> SELECT CEIL(RAND() * MAX(id)) FROM random;
+-------------------------+
| CEIL(RAND() * MAX(id))  |
+-------------------------+
|                1000000  |
+-------------------------+

уже лучше, но что насчет скорости?

> EXPLAIN
SELECT CEIL(RAND() * MAX(id)) FROM random;
+----+-------------+-------+-------+---------+-------------+
| id | select_type | table | type  |   rows  | Extra       |
+----+-------------+-------+-------+---------+-------------+
|  1 | SIMPLE      |random | index | 1000000 | Using index |
+----+-------------+-------+-------+---------+-------------+

index scan? похоже мы потеряли оптимизацию MAX()

> EXPLAIN
SELECT CEIL(RAND() * (SELECT MAX(id) FROM random));
+----+-------------+-------+------+------+------------------------------+
| id | select_type | table | type | rows | Extra                        |
+----+-------------+-------+------+------+------------------------------+
|  1 | PRIMARY     | NULL  | NULL | NULL | No tables used               |
|  2 | SUBQUERY    | NULL  | NULL | NULL | Select tables optimized away |
+----+-------------+-------+------+------+------------------------------+

Ура! Простой подзапрос возвращает нашу потерянную производительность!

Окей, теперь мы знаем как сгенерировать случайный ID, теперь надо получить и соответствующую ему строку:

> EXPLAIN
SELECT name
FROM random
WHERE id = (SELECT CEIL(RAND() *
(SELECT MAX(id)
FROM random));
+----+-------------+--------+------+---------------+------+---------+------+---------+------------------------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows    | Extra                        |
+----+-------------+--------+------+---------------+------+---------+------+---------+------------------------------+
|  1 | PRIMARY     | random | ALL  | NULL          | NULL | NULL    | NULL | 1000000 | Using where                  |
|  3 | SUBQUERY    | NULL   | NULL | NULL          | NULL | NULL    | NULL |    NULL | Select tables optimized away |
+----+-------------+--------+------+---------------+------+---------+------+---------+------------------------------+
> show warnings;
+-------+------+------------------------------------------+
| Level | Code | Message                                  |
+-------+------+------------------------------------------+
| Note  | 1249 | Select 2 was reduced during optimization |
+-------+------+------------------------------------------+

Нет нет нет! Не идите этим путем! Это самый очевидный, но также самый неверный способ! Почему? А вот почему: SELECT в условии WHERE будет выполняться для каждой строки! А это число может составлять от 0 до 4091 строки, в зависимости от того насколько вы будете удачливы.

Нам нужен такой способ выборки, при котором мы будем уверены что случайный номер генерируется только однажды:

SELECT name
FROM random
JOIN
(
  SELECT CEIL(RAND() * (SELECT MAX(id) FROM random)) AS id
) AS r2
USING (id);
+----+-------------+------------+--------+------+------------------------------+
| id | select_type | table      | type   | rows | Extra                        |
+----+-------------+------------+--------+------+------------------------------+
|  1 | PRIMARY     |            | system |    1 |                              |
|  1 | PRIMARY     | random     | const  |    1 |                              |
|  2 | DERIVED     | NULL       | NULL   | NULL | No tables used               |
|  3 | SUBQUERY    | NULL       | NULL   | NULL | Select tables optimized away |
+----+-------------+------------+--------+------+------------------------------+

Внутренний SELECT генерирует константу в TEMPORARY таблицу и JOIN выбирает одну строку. Великолепно! Нет сортировок, нет вмешательства приложения. Все части запроса оптимизированы.

#3. Добавляем “дыры” в primary key

Для того чтобы сделать наше предыдущее решение более универсальным, нам нужно учесть возможность “дыр” в ID (как если бы вы удалили некоторые строки).

SELECT name
FROM random AS r1 JOIN
(
 SELECT (RAND() * (SELECT MAX(id) FROM random)) AS id
)
AS r2
WHERE r1.id >= r2.id
ORDER BY r1.id ASC
LIMIT 1;
+----+-------------+------------+--------+------+------------------------------+
| id | select_type | table      | type   | rows | Extra                        |
+----+-------------+------------+--------+------+------------------------------+
|  1 | PRIMARY     |            | system |    1 |                              |
|  1 | PRIMARY     | r1         | range  |  689 | Using where                  |
|  2 | DERIVED     | NULL       | NULL   | NULL | No tables used               |
|  3 | SUBQUERY    | NULL       | NULL   | NULL | Select tables optimized away |
+----+-------------+------------+--------+------+------------------------------+

Теперь JOIN добавляет все ID который больше или равны нашему случайному значению и мы выбираем ближайшего соседа, если равенство не возможно. НО как только одна строка найдена мы останавливаемся (LIMIT 1). И мы читаем строки в соответствии с индексом (ORDER BY id ASC). Так как мы используем знак “>=” вместо строгого равенства “=” мы можем избавиться от CEIL и получить тот же резудьтат при немного меньших затратах.

#4. Равномерное распределение

Поскольку распределение ID не равномерно, наша выборка на самом деле стала не совсем случайной (прим. пер.: насколько я понимаю, чем больше “больших” дыр в ID тем менее равномерно распределение и тем “менее случайной” будет выборка).

> select * from holes;
+----+----------------------------------+----------+
| id | name                             | accesses |
+----+----------------------------------+----------+
|  1 | d12b2551c6cb7d7a64e40221569a8571 |      107 |
|  2 | f82ad6f29c9a680d7873d1bef822e3e9 |       50 |
|  4 | 9da1ed7dbbdcc6ec90d6cb139521f14a |      132 |
|  8 | 677a196206d93cdf18c3744905b94f73 |      230 |
| 16 | b7556d8ed40587a33dc5c449ae0345aa |      481 |
+----+----------------------------------+----------+

Функция RAND генерирует ID от 9 до 15, которые попадают в “дыру” перед 16 и как следствие, 16 выбирается намного чаще чем остальные.

Для этой проблемы не существует нормального решения, но если ваши данные более-менее постоянны, вы можете добавить таблицу для маппинга номера строки с ее ID:

> create table holes_map (
>   row_id int not NULL primary key,
>   random_id int not null
> );
> SET @id = 0;
> INSERT INTO holes_map SELECT @id := @id + 1, id FROM holes;
> select * from holes_map;
+--------+-----------+
| row_id | random_id |
+--------+-----------+
|      1 |         1 |
|      2 |         2 |
|      3 |         4 |
|      4 |         8 |
|      5 |        16 |
+--------+-----------+

Идентификатор row_id теперь не содержит дыр и мы опять можем воспользоваться нашим запросом:

SELECT name
FROM holes
JOIN (
  SELECT r1.random_id
  FROM holes_map AS r1
  JOIN (
    SELECT (RAND() * (SELECT MAX(row_id) FROM holes_map)
  ) AS row_id
) AS r2
WHERE r1.row_id >= r2.row_id
ORDER BY r1.row_id ASC
LIMIT 1) as rows ON (id = random_id);

После 1000 попыток опять имеем равномерное распределение:

> select * from holes;
+----+----------------------------------+----------+
| id | name                             | accesses |
+----+----------------------------------+----------+
|  1 | d12b2551c6cb7d7a64e40221569a8571 |      222 |
|  2 | f82ad6f29c9a680d7873d1bef822e3e9 |      187 |
|  4 | 9da1ed7dbbdcc6ec90d6cb139521f14a |      195 |
|  8 | 677a196206d93cdf18c3744905b94f73 |      207 |
| 16 | b7556d8ed40587a33dc5c449ae0345aa |      189 |
+----+----------------------------------+----------+

#5. Обслуживание таблицы Holes при помощи триггеров

Давайте подготовим таблицы как описано ниже:

DROP TABLE IF EXISTS r2;
CREATE TABLE r2 (
  id SERIAL,
  name VARCHAR(32) NOT NULL UNIQUE
);

DROP TABLE IF EXISTS r2_equi_dist;
CREATE TABLE r2_equi_dist (
  id SERIAL,
  r2_id bigint unsigned NOT NULL UNIQUE
);

Когда мы что-то меняем в r2, мы хотим чтобы r2_equi_dist также изменялась.

DELIMITER $$
DROP TRIGGER IF EXISTS tai_r2$$
CREATE TRIGGER tai_r2
AFTER INSERT ON r2 FOR EACH ROW
BEGIN
DECLARE m BIGINT UNSIGNED DEFAULT 1;

SELECT MAX(id) + 1 FROM r2_equi_dist INTO m;
SELECT IFNULL(m, 1) INTO m;
INSERT INTO r2_equi_dist (id, r2_id) VALUES (m, NEW.id);
END$$
DELIMITER ;

DELETE FROM r2;

INSERT INTO r2 VALUES ( NULL, MD5(RAND()) );
INSERT INTO r2 VALUES ( NULL, MD5(RAND()) );
INSERT INTO r2 VALUES ( NULL, MD5(RAND()) );
INSERT INTO r2 VALUES ( NULL, MD5(RAND()) );

SELECT * FROM r2;
+----+----------------------------------+
| id | name                             |
+----+----------------------------------+
|  1 | 8b4cf277a3343cdefbe19aa4dabc40e1 |
|  2 | a09a3959d68187ce48f4fe7e388926a9 |
|  3 | 4e1897cd6d326f8079108292376fa7d5 |
|  4 | 29a5e3ed838db497aa330878920ec01b |
+----+----------------------------------+
SELECT * FROM r2_equi_dist;
+----+-------+
| id | r2_id |
+----+-------+
|  1 |     1 |
|  2 |     2 |
|  3 |     3 |
|  4 |     4 |
+----+-------+

INSERT весьма прост. При DELETE же мы хотим поддерживать equi-dist-id в состоянии “без дыр”:

DELIMITER $$
DROP TRIGGER IF EXISTS tad_r2$$
CREATE TRIGGER tad_r2
AFTER DELETE ON r2 FOR EACH ROW
BEGIN
DELETE FROM r2_equi_dist WHERE r2_id = OLD.id;
UPDATE r2_equi_dist SET id = id - 1 WHERE r2_id > OLD.id;
END$$
DELIMITER ;

DELETE FROM r2 WHERE id = 2;

SELECT * FROM r2;
+----+----------------------------------+
| id | name                             |
+----+----------------------------------+
|  1 | 8b4cf277a3343cdefbe19aa4dabc40e1 |
|  3 | 4e1897cd6d326f8079108292376fa7d5 |
|  4 | 29a5e3ed838db497aa330878920ec01b |
+----+----------------------------------+
SELECT * FROM r2_equi_dist;
+----+-------+
| id | r2_id |
+----+-------+
|  1 |     1 |
|  2 |     3 |
|  3 |     4 |
+----+-------+

UPDATE также прост. Мы должны обслужить лишь Foreign Key constraint:

DELIMITER $$
DROP TRIGGER IF EXISTS tau_r2$$
CREATE TRIGGER tau_r2
AFTER UPDATE ON r2 FOR EACH ROW
BEGIN
UPDATE r2_equi_dist SET r2_id = NEW.id WHERE r2_id = OLD.id;
END$$
DELIMITER ;

UPDATE r2 SET id = 25 WHERE id = 4;

SELECT * FROM r2;
+----+----------------------------------+
| id | name                             |
+----+----------------------------------+
|  1 | 8b4cf277a3343cdefbe19aa4dabc40e1 |
|  3 | 4e1897cd6d326f8079108292376fa7d5 |
| 25 | 29a5e3ed838db497aa330878920ec01b |
+----+----------------------------------+
SELECT * FROM r2_equi_dist;
+----+-------+
| id | r2_id |
+----+-------+
|  1 |     1 |
|  2 |     3 |
|  3 |    25 |
+----+-------+

#6. Несколько случайных строк за один раз

Если вы хотите получить более одной случайной строки за раз вы можете:

1. Выполнить запрос несколько раз
2. Написать хранимую процедуру, которая выполняет запрос и хранит результат во временной таблице
3. Выполнить UNION наконец

Хранимая процедура:

Хранимая процедура позволяет вам использовать структуры, известные в любом популярном языке программирования:

1. Циклы
2. Управляющие конструкции
3. Процедуры
4. …

Для нашей задачи нам нужен только цикл LOOP:

DELIMITER $$
DROP PROCEDURE IF EXISTS get_rands$$
CREATE PROCEDURE get_rands(IN cnt INT)
BEGIN
DROP TEMPORARY TABLE IF EXISTS rands;
CREATE TEMPORARY TABLE rands ( rand_id INT );

loop_me: LOOP
IF cnt < 1
  THEN LEAVE loop_me;
END IF;
INSERT INTO rands
  SELECT r1.id
  FROM random AS r1
  JOIN (
    SELECT (RAND() * (SELECT MAX(id) FROM random)) AS id
  ) AS r2
  WHERE r1.id >= r2.id
ORDER BY r1.id ASC
LIMIT 1;

SET cnt = cnt - 1;
END LOOP loop_me;
END$$
DELIMITER ;

CALL get_rands(4);
SELECT * FROM rands;
+---------+
| rand_id |
+---------+
|  133716 |
|  702643 |
|  112066 |
|  452400 |
+---------+

Оставляю в качестве заданий читателю следующие задачки:

1. Динамически составлять запрос, генерируя название временной таблицы (спасибо 2 Evgeny Babin)
2. Используя UNIQUE index отлавливать нарушения UNIQUE key для удаления возможных дублей.

#7. Быстродействие

Чтоже стало с быстродействием? У нас есть 3 различные запроса, решающие нашу проблему:

1. Q1. ORDER BY RAND()
2. Q2. RAND() * MAX(ID)
3. Q3. RAND() * MAX(ID) + ORDER BY ID

Q1 можно оценить как N * log2(N), Q2 и Q3 что-то около константы.

Чтобы получить реальные значения мы провели несколько тестов с числом строк от 100 до миллиона и выполнили каждый запрос 1000 раз.

    100        1.000      10.000     100.000    1.000.000
Q1  0:00.718s  0:02.092s  0:18.684s  2:59.081s  58:20.000s
Q2  0:00.519s  0:00.607s  0:00.614s  0:00.628s   0:00.637s
Q3  0:00.570s  0:00.607s  0:00.614s  0:00.628s   0:00.637s

Как вы можете видеть, простой ORDER BY RAND() оптимизирован для выполнения при количестве строк не более 100.

По мотивам http://jan.kneschke.de/projects/mysql/order-by-rand/

Coding with fun!

P.S. Сам я на практике использовал пока лишь 3е решение ))