Ускоряем выборку произвольных записей MySQL

[TimTowdy]

В принципе вполне очевидное решение, с не менее очевидными минусами:
1. Необходимость введения дополнительного стобца и дополнительного индекса
2. Необходимость периодического обновления этот столбца, притом f надо постоянно увеличивать с ростом таблицы
3. Неравномерное распределение, даже если в таблице нет дырок
4. Теоретически возможна ситуация, когда LIMIT 10 вернёт меньше 10 записей

Единственное преимущество по сравнению с habrahabr.ru/blogs/mysql/54176/#comment_1444785
это то, что делается один запрос, но подозреваю что он работает медленнее чем 10 моих в сумме, т.к. мой запрос не сортирует временные таблицы в памяти.

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

[tshaoni]

Отличная, на самом деле, идея.

Чтобы в «ручную не менять f при каждом пуске»
можно немножко модифицировать запрос:

SELECT * FROM `a` WHERE `f` = RAND()*1000 ORDER BY RAND() LIMIT 10;

[miami]

К сожалению это запустит смену `f` на каждом новом ряду. Увы, не верное решение, но рад что вы стали мыслить вместе со мной )

[tshaoni]

Да. Сбойнул. Случайное число надо получить до селекта. И уж потом вставить его в запрос.

[SaveTheRbtz]

Может везде `f` = x заменить на `f` >= x, тогда по идее выборок менее чем с десятью элементами станет меньше.

[metaball]

тогда вся затея теряет смысл

[SaveTheRbtz]

Да, мой косяк. Написал не продумав.

[SaveTheRbtz]

Попытаюсь исправится, ибо утром был ещё сонным(можете заминусовать его, чтоб скрылся =)).

mysql> EXPLAIN SELECT * FROM a WHERE id >= RAND()*(SELECT MAX(id) FROM a) LIMIT 1 \G;

Слегка переработанный вариант предложенный TimTowdy. Учитывая, что MAX(id) мы можем закешировать, будет выполнятся очень быстро.
Из минусов такого подхода — работает только при хорошей кучности id. При проверке на таблице phpbb_privmsgs результат оказался довольно удручающим.

Из предложений: Не делать поле id auto_increment, а при добавлении приравнивать его значение к RAND*MAXINT; Тогда дисперсия будет равномерной, но появятся проблемы с добавлением при сильной заполненности таблицы.

А вообще подход автора весьма интересен.

[SaveTheRbtz]

Ещё немного подумав о подходе предложенном miami
К сожалению он добавляет некую дольку «псевдослучайности». То есть фактически, в приведённом примере, при запросе десяти записей по одному и тому же `f` у нас есть всего ~16 непересекающихся вариантов выборок, также отсутствует даже теоретическая возможность попадания в эту выборку записей с другим значением `f`

[miami]

Значение f — это не критерий поиска, это всего лишь ускорение прохода по таблице. Смысл не в том, чтобы выбрать из различных f ;))) Хотя да, эсли внезапно понадобилось более 10 случайных результатов, а индекс перестраивать не хочется, то подойдёт такой вариант:
SELECT * FROM `a` WHERE `f` IN (100,500,x5,x25,... ) ORDER BY RAND() LIMIT 10;

[TimTowdy]

Это я и имел виду под пунктом 3. Хотя если f часто обновлять то это не существенно.

[miami]

Имеется 1000 (максимальный f) абсолютно непересекающихся «рандомов» которые в свою очередь перетасовываются ORDER BY RAND(), а из полученного уже берётся 10 верхних записей. Если перегенеривать значения колонки f каждые, скажем 1000 запросов… или 100… то где здесь псевдослучайность? ;) Если вам не нравится функция RAND() можете использовать посложнее:

UPDATE `a` SET `f` = HEX(MID(MD5(RAND()),3,2)); -> 163072 row(s) affected. ( Query took 4.5446 sec )

Проверяем качество разброса:

SELECT `f`, COUNT(1) C FROM `a` GROUP BY `f` LIMIT 10; ->

Имеем примерно по 650 записей на каждый f, всего 255 вариантов f. Для быборок будет чуть сложнее генерить f, но псевдослучайность мы убили, думается, на корню ;)

SET @rnd = HEX(MID(MD5(RAND()),3,2));
SELECT * FROM `a` WHERE `f` = @rnd ORDER BY RAND() LIMIT 10;

[SaveTheRbtz]

Да, так псевдослучайность убирается.
Есть предложение использовать такой алгоритм для `f`:

SELECT CONV(MID(MD5(RAND()),-2),16,10);
Из минусов: `f` завязывается на степенях 16ти

Остался только вопрос в сравнении скорости алгоритмов предложенных Вами и TimTowdy на разных объёмах выборки(1,10,100,1000 например).

[miami]

На всё той же своей таблице тестирую метод TimTowdy, тот же комп, те же мощности софт- и хардвара.

SELECT r1.`id`, `md5`
FROM a AS r1 JOIN
(SELECT (RAND() *
(SELECT MAX(`id`) FROM `a`)) AS `id`
) AS r2
WHERE r1.id >= r2.id
ORDER BY r1.id ASC
LIMIT 1; -> (1 rows total, Query took 0.0318 sec)

Таких выборок должно быть 10. Проверив выборку через EXPLAIN SELECT узнаю что скан идёт по 15000 рядам. Мда, ну ладно пусть так. Думается, что быстрее всего получится запустить это 10 раз одной командой, объединяя результат командой UNION. Возможны другие способы, увы, в голову не приходят (если что кидайте, проверим). Итак:

(SELECT r1.`id`, `md5` FROM a AS r1 JOIN
(SELECT (RAND() * (SELECT MAX(`id`) FROM `a`)) AS `id` ) AS r2
WHERE r1.id >= r2.id ORDER BY r1.id ASC LIMIT 1)
UNION (SELECT r1.`id`, `md5` FROM a AS ... и так 10 раз подряд-> (10 rows total, Query took 0.3303 sec)

Вызов полученного много-много раз дал самое быстрое — 0.0959 sec, среднее 0.2900. О качестве рандома судить сложно… Испробовал что будет если удалить из середины большой кусок записей и вставить их, например, в конец таблицы…

DELETE FROM `a` WHERE `id` > 1000 LIMIT 3000;
INSERT INTO `a` (md5) SELECT md5 FROM `a` LIMIT 3000;

Случайные выборки по-прежнему от 0.3 до 0.1 секунды.
Теперь самое интересное — удваиваю оъём таблицы.

INSERT INTO `a` (md5) SELECT md5 FROM `a`;
UPDATE `a` SET md5 = MD5(`id`), f = RAND()*2000;

Сначала с f-индексом, затем методом TimTowdy:

SET @rnd = RAND()*2000;
SELECT * FROM `a` WHERE `f` = @rnd ORDER BY RAND() LIMIT 10; -> 0.0021 sec - 0.0023 sec - 0.0133 sec

(SELECT r1.`id`, `md5` FROM a AS r1 JOIN
(SELECT (RAND() * (SELECT MAX(`id`) FROM `a`)) AS `id` ) AS r2
WHERE r1.id >= r2.id ORDER BY r1.id ASC LIMIT 1)
UNION (SELECT r1.`id`, `md5` FROM a AS ... -> 0.0927 sec - 0.1218 sec - 0.3964 sec.

Согласен, неплохой результат для выборки без лишней колонки и лишнего индекса. Экономным must use, а тем кто предпочитает иметь скорость и контролировать её понравится индекс. Я понимаю что у всех нас разные требования к приложениям, от этого и количество вариантов и я лично за! За то, чтобы усовершенствование продолжалось, чтобы мысль в эту сторону направлена была, чтобы мы не забывали полюбившуюся нам базу данных и учились для себя из неё-родимой выжимать максимум )

[Holden]

«хотя знаете, можно воспользоваться первыми знаками MD5(`id`) и перевести его в INT, равномернее некуда»

Откуда такая информация?

[miami]

Экспериментировал…: Р

[freeOne]

Хорошая идея. Лишнее подтверждение, что чаще всего быстродействие достигается за счет расхода дополнительной памяти.

[miami]

Вы имеете ввиду индекс?
Ну да, для получения одного приходится жертвовать другим…

[phoinixrw]

ORDER BY RAND() — зло по определению, и придумывать финты ушами можно бесконечно.

Проще от него отказаться.

Готовый пример случайного offset на чистом SQL:

SET @limit := 10;
SET @r := (SELECT COUNT(*) FROM test);
SET @offset := CEILING(RAND() * @r) — @limit;
SET @sql := CONCAT('SELECT * FROM test LIMIT ', @limit, ' OFFSET ', @offset);
PREPARE stmt1 FROM @sql;
EXECUTE stmt1;

[miami]

Случайный офсет не помогает сократить пробег по таблице. Это объясняет
EXPLAIN SELECT * FROM `test` LIMIT 1 OFFSET 1234

И даже это звучит как-то не внушительно:
EXPLAIN SELECT `id` FROM `test` LIMIT 1 OFFSET 1234

Но за ваш вариант спасибо… )

[phoinixrw]

Не вижу связи между пробегом по таблице и ORDER BY RAND()
EXPLAIN ничего интересного и не даст в данном случае.
И что примечательно, выборка по индексу у меня прошла в 2 раза медленней чем без него.

[miami]

EXPLAIN SELECT * FROM `a` WHERE `f` = число ORDER BY RAND() LIMIT 10;
здесь ORDER BY RAND() происходит только среди 164 рядов (всего было 163712),
от лишних мы избавились с помошью WHERE на индексированной колонке. В этом и есть основная мысль этого поста.