[Без оффтопа] Развлекаемся с SQL

[Rooslan Khayrov]

array_push($sql, "('" . mysql_real_escape_string($this->randText(120)) . "', '" . mysql_real_escape_string($this->randText()) . "', " . $this->randNum(0, 10000) . ", " . $this->randNum(0, 10000) . ", " . $time . ", " . $time . ")");

Мои глаза... Генерация SQL конкатенацией строк до сих пор в моде?

Поднял для экспериментов облачный сервер на selectel.ru: 8 GB RAM, 8 потоков (Xeon E5-2630@2.3 GHz), Debian 7 amd64, MySQL 5.5.31.

В my.cnf поправил следующее:

key_buffer_size = 128M
sort_buffer_size = 64M
query_cache_limit = 4M
query_cache_size = 512M
innodb_file_per_table
innodb_buffer_pool_size = 4G
innodb_log_file_size = 512M

Скриптом Дениса сгенерил базу на миллион записей, погонял запросы, чтобы поднять таблицу в кэш, и попробовал самый простой вариант:

SELECT * FROM test ORDER BY RAND() LIMIT 10;

Время выполнения 9-11 сек.
Попробовал помочь планировщику, чтобы не сортировал строки целиком:

SELECT test.* FROM test JOIN
(SELECT id FROM test ORDER BY RAND() LIMIT 10) sub
ON test.id = sub.id;

800-1000 мс, куда лучше.

Погасил MySQL, поднял PostgreSQL. Версия 9.1.9, в конфиге поправил только:

shared_buffers = 4G
work_mem = 64M
maintenance_work_mem = 64MB

Создал базу с такой же схемой и залил те же самые данные, что и в MySQL.

SELECT * FROM test ORDER BY random() LIMIT 10;

1200-1300 мс.

SELECT test.* FROM test JOIN
(SELECT id FROM test ORDER BY random() LIMIT 10)
sub ON test.id = sub.id;

600-650 мс
Кто интересовался, чем постгрес лучше — в частности вот.

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

QUERY PLAN                                                           
-----------
 Limit  (cost=308654.61..308654.63 rows=10 width=1060) (actual time=2989.145..2989.171 rows=10 loops=1)
   ->  Sort  (cost=308654.61..311154.60 rows=999999 width=1060) (actual time=2989.141..2989.150 rows=10 loops=1)
         Sort Key: (random())
         Sort Method: top-N heapsort  Memory: 38kB
         ->  Seq Scan on test  (cost=0.00..287044.99 rows=999999 width=1060) (actual time=81.551..1435.582 rows=999999 loops=1)

Для запросов вида ORDER BY ... LIMIT N, где N << count(*) постгрес использует потоковый алгоритм с приоритетной очередью (bounded heap), в результате чего в плане доминируют затраты на sequential scan, а сортировка обходится минимальной памятью.

При достаточно равномерном распределении автоинкрементного ключа способ с выборкой N случайных ID в диапазоне min..max, наверное, самый практичный.
Если с ключом проблемы, а запросы на N случайных записей ну очень важны, я бы попробовал материализовать это так:

ALTER TABLE test ADD COLUMN rndkey double precision NOT NULL DEFAULT random();
CREATE INDEX test_rndkey ON test(rndkey);

Выбор одной случайной записи:

SELECT * FROM test WHERE rndkey > random() ORDER BY rndkey LIMIT 1;

(Не LIMIT N потому что в таком случае в выборке рядом всегда будут оказываться одни и те же записи. В принципе, решаемо регулярным обновлением колонки с перестройкой индекса — смотря что нам важнее).
Цена такого запроса — один проход по хорошо сбалансированному индексу. На «горячих» данных — единицы миллисекунд в любой базе. Запрос с некоторой вероятностью может не вернуть данных вообще, поэтому его нужно повторять, пока не наберётся N строк. Все равно дешевле, чем full scan. Для минимизации накладных расходов по общению с базой можно завернуть в хранимку.

Самый эффективный способ, пожалуй, должен быть реализован напрямую в базе, как TABLESAMPLE в SQL Server: имея карту данных на диске, выбрать некоторое количество случайных страниц указанной таблицы, и вытянуть строки оттуда — минуя индексы и всё остальное.

[shumbola]

Сообщение от Rooslan Khayrov

Самый эффективный способ, пожалуй, должен быть реализован напрямую в базе, как TABLESAMPLE в SQL Server: имея карту данных на диске, выбрать некоторое количество случайных страниц указанной таблицы, и вытянуть строки оттуда — минуя индексы и всё остальное.

Зависит от задачи, TABLESAMPLE не дает действительно случайных результатов. Прежде чем использовать TABLESAMPLE, изучайте область применения.
Думаю Rooslan Khayrov знает об этом, и мое сообщение не ему адресовано. ;-)