Все подряд О чем здесь

Выбор случайных записей из больших таблиц MySQL

Проблематика

Довольно часто при разработке различных сервисов мы сталкиваемся с необходимостью получить случайную запись из базы данных. С обывательской точки зрения это выглядит весьма несложно - у базы данных есть, например, Primary Key, можно было бы выбрать любую рандомную запись из этого столбца и достать строчку по ключу. Проблема в том что в MySQL нет никакой команды типа "Достать случайную запись". Способа который бы обеспечил нам одновременно и высокую производительность, высокое качество (равномерность случайных значений), а так же неповторяемость не существует, поэтому приходится идти на компромисы и выбирать способ, максимально подходящий под текущие задачи.

Все что нам доступно из "рандомности" - это обычная функция RAND(), возвращающая случайное FLOAT-значение от 0 до 1. Так же в качестве функции, которая позволяет получить равномерное случайное значение с привязкой к конкретному идентификатору, можно использовать md5. В случае использования md5(id) можно для каждой таблицы получить равномерно распределенное случайное значение.

Вообще в рунете есть довольно много статей где описыны способы решения данной задачи (например, на хабре - 1, 2, 3), но хочется собрать всё в один пост, показать плюсы и минусы различных решений и провести краткий сравнительный скоростной тест на типовой таблице.

Методика тестирования

Тестовый стенд на MySQL 5.5 работающий на ненагруженном сервере с ОС Centos 6 на базе двух процессоров Intel Quad-Core Xeon 5620, 32Gb RAM и 4 SSD диска в Raid 10. Тестировать будем на типовой таблице хранящей изображения для галерии. Таблица имеет такой формат:

CREATE TABLE `image` ( `id` bigint(20) unsigned NOT NULL, `src` varchar(2048) NOT NULL, `page_src` varchar(2048) NOT NULL DEFAULT '', `title` varchar(160) NOT NULL, `width` mediumint(8) unsigned NOT NULL DEFAULT '0', `height` mediumint(8) unsigned NOT NULL DEFAULT '0', `size` varchar(32) NOT NULL DEFAULT '', PRIMARY KEY (`id`) ) ENGINE=MyISAM DEFAULT CHARSET=utf8$$

Количество строк: ~ 48 400 000
Общий объем данных: ~ 11.3 Gb
Средняя длина строки таблицы: 234 байта
Размер индекса: ~ 814.5 Mb
Общий объем данных в таблице довольно большой, поэтому, я надеюсь, кешироваться в памяти файл не будет и это не повлияет на результаты работы запросов, в результате которых файл с данными считывается с диска повторно. Разумеется, для полноты эксперимента так же берем меньшую таблицу аналогичной структуры с в 10 раз меньшим количеством строк. Так мы сможем понять насколько качество рассматриваемых способов зависит от размеров таблиц. Далее по тексту большая таблица будет именована как image_big, а маленькая как image_small.

Использование ORDER BY rand()

В лоб

Самый простой и очевидный способ "в лоб". MySQL считывает всю таблицу, для каждой строки вычисляет значение rand(), далее все их сортирует, потом выбирает то количество которое указано в части запроса в LIMIT. Поэтому скорость выполнения зависит от скорости считывания таблицы с диска и от скорости сортировки, т.е. время выполнения запроса прямо порционально количеству строк, а так же зависит и от размера каждой строки, но зато почти не зависит от количества выбираемых за каждый запрос строк. Отсюда и очень долгое выполнение запроса. Для таблиц в несколько сотен строк скорость выполнения еще терпимая, дальше все очень очень плохо. Пример запроса:

SELECT id, title, src FROM image ORDER BY rand() LIMIT 100;

Результаты:
image_big ORDER BY rand() LIMIT 1 - 294,8 сек
image_small ORDER BY rand() LIMIT 1 - 26,9 сек
image_big ORDER BY rand() LIMIT 100 - 293,6 сек
image_small ORDER BY rand() LIMIT 100 - 26,7 сек

Вердикт: хорош для совсем небольших таблиц. Отличное качество работы - всегда идеально равномерный рандом. Совсем не подходит для больших таблиц.

Хак с TEMPORARY TABLE

Встроенный оптимизатор MySQL хоть и хорош, но не всегда до конца. Если для операции сортировки мы будем считать только индекс, не открывая файл с данными, то получим выигрыш в скорости.

#для получения одной строки SET @a = (SELECT id FROM image ORDER BY rand() LIMIT 1); SELECT id, title, src FROM image WHERE id = @a; #для мульти выборки CREATE TEMPORARY TABLE tmp SELECT id FROM image ORDER BY rand() LIMIT 100; SELECT i.id, i.title, i.src FROM image i, tmp t WHERE t.id = i.id;

image_big ORDER BY rand() LIMIT 1 - 151,0 сек
image_small ORDER BY rand() LIMIT 1 - 13,6 сек
image_big ORDER BY rand() LIMIT 100 - 151,6 сек
image_small ORDER BY rand() LIMIT 100 - 13,7 сек

Разница почти в два раза. При том что разрыв между способами "в лоб" и "с хаком" будет расти с ростом средней длины строки в таблице. Данный метод особенно хорош для улучшения показателей случайной выборки из очень широких таблиц, при том что он не добавляет никаких минусов - выборка основана всегда на полных данных, а качество выборки остается идеальным.

Хак с дополнительным индексом

Уже понятно, что основная проблема способа с ORDER BY rand() - это чтение большого количества данных с диска и их сортировка. Этим же способом мы можем подробить таблицу горизонтально и выбирать сначала случайный горизонтальный сегмент, а затем из него выбирать случайный набор данных. 256 горизонтальных сегментов можно получить с помощью дополнительного индекса, например так:

ALTER TABLE image ADD COLUMN sortcol UNSIGNED TINYINT; UPDATE image SET sorcol = floor(rand()*256);

Получаем случайные значения:

SELECT id, title, src FROM image WHERE sortcol = floor(rand()*256) ORDER BY rand() LIMIT 100;
image_big ORDER BY rand() LIMIT 1 - 31,37 сек
image_small ORDER BY rand() LIMIT 1 - 3,07 сек
image_big ORDER BY rand() LIMIT 100 - 34,71 сек
image_small ORDER BY rand() LIMIT 100 - 3,15 сек

Из существенных недостатков данного метода можно отметить разве что "сегментность" выборок - т.е. многие значения никогда не выпадут в паре с другими значениями. Впрочем, в зависимости от поставленных, задач метод можно доработать (например, периодическим обновлением индекса).

Начиная с MySQL версии 5.6 появилась возможность делать SELECT-запросы из определенной партиции. Поэтому очень вероятно что этот способ горизонтального разбиения на части будет более интересен чем введение дополнительного столбца и индекса по нему. Но не стоит забывать что partitioning несет с собой как серию плюсов так и серию минусов. Перед его использованием лучше подробнее изучить документацию и провести серию на типичных для проекта задачах.

Комбинация хаков

Использование комбинации хаков на тестовой таблице помогло улучшить временные показатели примерно на 10% по сравнению с хаком "с дополнительным индексом". Если вместо индекса по sortcol использовать индекс по паре столбцов (sortcol, id), то дополнительно скорость увеличилась еще на 30% (на тестовых данных).

SET @a = (select id from image WHERE sortcol = floor(rand()*256) ORDER BY rand() LIMIT 1); SELECT id, title, src FROM image WHERE id = @a;

Использование индекса

Последовательный индекс

Если структура вашей таблицы имеет последовательный автоинкрементный primary key и не все данные актуальные и не используется удаление - идеальным вариантом будет использовать такой код:

SET @a = floor((SELECT max(id) FROM imag)*rand()); SELECT id, title, src FROM image WHERE id = @a;

Суммрное время выполнения таких запросов менее 10 мсек. В этом случае в первом запросе мы получаем из основного ключа таблицы максимальное значение - это очень быстрая операция, во втором запросе у нас идет доступ к таблице по основному ключу, что тоже весьма быстро, при том что от размера таблицы скорость выполнения никак на зависит.

Для выборки нескольких уникальных значений можно воспользоваться выражением WHERE id IN (...). либо используя. Например, если не заботиться об значений в одной выборке то на голом SQL получить требуемую случайную выборку в 100 записей можно таким спомобом:

SET @a = (SELECT max(id) FROM image); CREATE TEMPORARY TABLE tmp SELECT floor(@a*rand()) id FROM imag LIMIT 100; SELECT i.id, i.title, i.src FROM imag i, tmp WHERE tmp.id = i.id;

На тестовом стенде этот набор запросов выполнялся 30мсек, что вполне примерно соответствует скорости 100 операций случайного доступа к SSD диску. На HDD-диске аналогичный запрос будет выполняться примерно на 1-2 порядка дольше.

SELECT-запрос можно было бы построить в виде SELECT i.id, i.title, i.src FROM imag i WHERE i.id IN (SELECT id FROM tmp);, но тесты на 10000 записях показали совершенно одинаковые результаты обоих вариантов, притом что независимо от порядка выполнения запросов второй запрос выполняется намного быстрее, а это значит что для MySQL эти запросы идентичны и оптимизатор приводит их к единому виду.

Если скорость выполнения критичнее чем качество выборки, можно использовать способ при котором будет выбираться целый сегмент значений, используя ограничение по id с двух сторон. В случае если таблица на диске не дефрагментирована, то чтение будет производиться быстрее, чем в случае WHERE id IN. Из явных минусов - по факту на выходе получаем не случайне записи, а случайный сегмент таблицы.

SET @a = floor((SELECT max(id)-100 FROM image)*rand()); SELECT id, title, src FROM image WHERE id >= @a AND id < (@a+100);

Этот способ при указанных условиях быстрее еще на порядок (например, на тестовом стенде выборка в 10000 записей выполняется за 40 мсек).

Создание последовательного уникального индекса

Если в таблице отсутствует последовательный индекс - его можно создать, просто добавив индексный столбец и пронумеровав строки таблицы. Как это сделать описано в другой статье. Разумеется, при частом изменении таблицы нужно будет следить чтбо нумерация не слетала, это можно с помощью триггеров или, если актуальность случайных значений не критична - по крону.

Использование индекса на основе хеш-функции

Альтернативным путем может быть ипсользование уникального индекса на основе хеш-функции в качестве primary key или в дополнительном столбце. Например исходная тестовая таблица в одном из моих проектов использует в качестве id преобразование hex2int от первых 16 символов md5-функции от src. Этим мы гарантируем равномерное распределение ключей по всему 8-байтовому целочисленному диапазону и легко можем использовать это для правильных равномерных рандомных выборок.

Создать индекс можно так:

UPDATE image SET hashid = conv(substring(md5(src), 1, 16), 16, 10);

В данном случае поле hashid должно быть unsigned bigint. Использование 8-байтового числа позволяет с достаточно высокой долей вероятности говорить о том что у нас не произойдет коллизий когда для разных src получится одинаковый hashid. Использованиее более узких типов повысит вероятность возникновения коллизий. Но если количество данных небольшое - то можно брать более узкие типы, так как это позволит уменьшить размер индексного файла.

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

SET @mval = (SELECT id FROM image_big ORDER BY id DESC LIMIT 100,1); SET @a = cast(@mval as unsigned) * rand(); SELECT id, title, src FROM image_big WHERE id > @a ORDER BY id LIMIT 100;

Суммарное время выполнения этого запроса на большой тестовой таблице - около 150 мсек. 95% времени приходится на последний SELECT.

Альтернативные методы

Если данных в таблице много и они неизменяемые, например, это какой-то словарь, то ее можно ускорить в целом. Как это сделать можно прочитать в статье про сжатие MySQL-таблиц.

Если скорости или качества всех описанных методов недостаточно, то можно воспользоваться in-memory решением, например с помощью srandmember в key-value хранилище Redis. Из минусов - больший расход памяти, необходимость использования дополнительного софта и пакетов (конечно, если на проекте они еще не использовались). Из плюсов - мгновенная работа независимо от количества строк в БД (конечно, если на сервере достаточно памяти и софт не залазит в свап).

Выводы

Способы на основе ORDER BY rand() органично впишутся там где не используются таблицы большие чем несколько сотен строк. С хаками по горизонтальному разбиению можно легко увеличить количество строк в десяток-сотню раз. Если нужна еще большая производительность, а таблицы растут - то без использования тех или иных индексов уже не обойтись. Индекс на основе хеш функции идеально подойдет для любого размера таблиц, а особенно удобно его использовать на постоянной основе как замену строковому индексу. В случае же если проект highload, таблицы большие, а производительность нужна мгновенная - правильене всего использовать Redis или аналоги, к тому же, в любом случае, для highload проекта без in-memory key-value хранилища сейчас сложно.