Производительность ORDER BY RAND() LIMIT
15 мая 2012 MySQL 10 комментариев 11537 просмотров
Для получения нескольких случайных записей из таблицы я всегда использовал всем известную конструкцию ORDER BY RAND() LIMIT. На днях я столкнулся с проблемой в производительности этого запроса. Таблица содержала более миллиона строк. И мне нужно было срочно найти решение. Под катом альтернативный вариант выбора нескольких случайных строк.

Исходные данные.
Создадим таблицу и наполним ее большим количеством случайных чисел. Сущность test_value будет содержать значение php-функции uniqid(). Для этого теста я добавил 1 миллион записей.
CREATE TABLE test_rand(
    test_value VARCHAR (20) NOT NULL
)
ENGINE = MYISAM
Выберем 5 случайных записей первым методом.
SELECT *
FROM test_rand
ORDER BY RAND()
LIMIT 5
При тестировании запрос выполнялся 5 раз. Среднее время выполнения 1.06 с. Теперь попробуем другой вариант, суть его в следующем. Мы не сортируем строки и не обрезаем результат. Это похоже на цикл, для каждой записи мы имеем 2 переменные @count и @limit. @count уменьшается на 1 для каждой просматриваемой строки, @limit уменьшается для каждой выбранной строки.
SELECT test_value
FROM (
    SELECT @count := COUNT(*) + 1, @limit := 5
    FROM test_rand
) AS vars
STRAIGHT_JOIN (
    SELECT r.test_value, @limit := @limit - 1
    FROM test_rand AS r
    WHERE
        (@count := @count - 1)
        AND RAND() < @limit / @count
) AS i
Среднее время выполнения данного запроса 0.27 секунд. Прирост примерно в 4 раза при наших исходных данных. Стоит отметить, что в InnoDB таблицах такой разницы можно не заметить, так как COUNT() работает намного быстрее в MyISAM. Такой вариант лучше использовать для таблиц с большим количеством данных, так как он основан на вероятностном подходе. Как всегда решать вам. Если в таблице 10 строк и вам нужно выбрать 1 случайную, то с этим отлично справится ORDER BY RAND(). Если в таблице несколько миллионов записей, тогда уже стоит подумать.
10 комментариев

Отличное решение оптимизации:) Мне понравилось. Добавил в закладки:)

спасибо, помогло

Здесь мне сложно сказать что-то определенное, но хотелось бы отметить один момент: сложные запросы = проблемы понимания и читабельности кода. Это я к тому, что многое зависит и от уровня программиста, и ставимых ему задач. Безусловно, в случае даже с небольшими проектами на виртуальном хостинге каждая мили-секунда эта минус лимита, но в таком случае лучше вообще не использовать подобные конструкции. Лично я сам писал код своего проекта от начала и до конца, разрабатывал дизайн и верстал. В рамках проекта можно было бы реализовать многое, но вопрос целесообразности эта такая штука, которая ставит многое на свои места... имхо. Однако решение достаточно интересное, тут да :)

@WMAS, согласен, запрос непростой. Но в этом и идея, что нужно его использовать с умом. Он будет очень кстати для большого количества данных, но нецелесообразным для 10 строк в таблице.

Отличная статья. Использовал Ваши примеры запросов в нескольких своих разработках. Очень доволен полученным результатом. Особенно радует относительное быстродействие приведенных запросов. В нескольких мелких блогах использовал RAND. Но вот уже на горизонте замаячил проект под второй метод.

mantyr

Временные таблицы использовать не пробовали?

Нет, расскажите как для выборки случайной строки?

Лёха

Привет!

Метод - действительно оригинальный, ни где такого больше не встречал! И, что самое, главное, - рабочий :)

Сперва расскажу, что я сделал, а потом задам пару вопросов, если можно)

Всё действо происходит в MariaDB, не MySQL. В общем, создал я таблицу с 2мя полями: - id с primary key и автоинкрементом; - test_value типа varchar(255) с fulltext-индексом.

CREATE TABLE `test_rand` ( `id` INT(11) NOT NULL AUTO_INCREMENT, `test_value` VARCHAR(255) NOT NULL DEFAULT '', PRIMARY KEY (`id`), FULLTEXT INDEX `test_value` (`test_value`) ) COLLATE='utf8_general_ci' ENGINE=MyISAM AUTO_INCREMENT=1 ;

Затем, с помощью процедуры, забил в неё 5 миллионов строк. Поле id набивал с пропусками, через один. Т.е. в таблице 5 миллионов строк, а конечный автоинкремент равен 10 миллионам. Вот процедура (копирую целиком, для удобства копипасты): CREATE DEFINER=`root`@`localhost` PROCEDURE `dorepeat`(IN `p1` INT) LANGUAGE SQL NOT DETERMINISTIC CONTAINS SQL SQL SECURITY DEFINER COMMENT '' BEGIN SET @x = 0; REPEAT INSERT INTO test_rand SET `id` = @x, `test_value`= MD5(@x); SET @x = @x + 2; UNTIL @x > p1 END REPEAT; END

При вызове процедурки вбиваю число "10000000" и получаю 5 млн. строк. Вот в общем-то и всё.

Теперь о результатах. Вот такой вот запрос, с лимитом 10: SELECT SQL_NO_CACHE id, test_value FROM ( SELECT @count := COUNT(*) + 1, @limit := 10 FROM test_rand ) AS vars STRAIGHT_JOIN ( SELECT r.id, r.test_value, @limit := @limit - 1 FROM test_rand AS r WHERE (@count := @count - 1) AND RAND() < @limit / @count ) AS i отрабатывает в среднем за 2.9-3 секунды. С лимитом в 100 среднее время увеличивается до 3.01. С лимитом в 1000 - до 3.04.

И это, блин, реально круто, потому что обычный некешированный ORDER BY RAND() при тех же лимитах в среднем отрабатывает за 20 секунд (+- 0.1-0.3 в рамках погрешности).

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

Но у меня вопрос возник - а как задавать дополнительные условия выборки? Чтобы в лимитный рандом попадало не всё подряд, а только строки, соответствующие определённым критериям? Я ничего умнее вот этого не придумал: SELECT SQL_NO_CACHE id, test_value FROM ( SELECT @count := COUNT(*) + 1, @limit := 10 FROM test_rand -- where <здесь какие-то условия> ) AS vars STRAIGHT_JOIN ( SELECT r.id, r.test_value, @limit := @limit - 1 FROM ( -- делаем вложенный запрос SELECT id, test_value FROM test_rand -- where <здесь полностью дублируем условия выше> ) AS r WHERE (@count := @count - 1) AND RAND() < @limit / @count ) AS i

Т.е. приходится использовать одинаковые условия - первый раз, чтобы правильно подсчитать количество строк, участвующих в выборке, и второй - чтобы, собссна, эти строки выбрать. И только потом по этим отфильтрованным строкам проходимся рандомом. И всё бы ничего, но: 1. Дублировать условия как-то.. некрасиво чтоли. Понятное дело, что в управляющем коде можно подставлять эти условия из переменной, но всё-равно это неправильно. Может быть есть какая-то возможность обойтись без копипасты? 2. Explain показывает, что при таком подходе (с вложенной таблицой), получается целый набор ночных кошмаров sql-разработчиков:


| id | selecttype | table | type | possiblekeys | key | keylen | ref | rows | Extra | | -: | - | - | - | - | - | - | - | -: | - | | 1 | PRIMARY | | ALL | NULL | NULL | NULL | NULL | 5000001 | Using temporary; Using filesort | | 1 | PRIMARY | | ALL | NULL | NULL | NULL | NULL | 5000001 | Using join buffer (flat, BNL join) | | 3 | DERIVED | testrand | ALL | NULL | NULL | NULL | NULL | 5000001 | Using where | | 2 | DERIVED | test_rand | index | NULL | PRIMARY | 4 | NULL | 5000001 | Using index |

В принципе, на скорости выборки тестовых данных это не сказывается. Наоборот - чем больше данных отфильтровывается условиями, тем быстрее выполняется запрос. Но как-то меня это смущает. Тестовые данные более-менее равномерны и всё работает хорошо. Но не всплывут ли на боевых задачах какие-нибудь гадости, когда и primary key будет не равномерным, и столбцов в выборке будет куда больше.. Не знаю, если честно.

Вот такие вот вопросы. Если будут какие-то мысли и идеи - буду рад выслушать :)

Лёха

Что-то вся разметка побилась(

Александр

Можно это как-то перевести в запрос для SQLite и PHP?