Выбор случайных строк: методы для эффективного поиска

Получение случайных строк из таблицы (за пределами ORDER BY RAND())

Проблема

Желательно использовать «SELECT ... ORDER BY RAND() LIMIT 10», чтобы получить 10 случайных строк. Но это медленно. Оптимизатор делает

• Чтение всех строк — это дорого
• Добавление RAND() к строкам
• Сортировка строк — тоже дорого
• Выбор первых 10.

Все алгоритмы, представленные ниже, «быстрые», но большинство из них имеют недостатки:

• Смещение — некоторые строки имеют больше шансов быть выбранными, чем другие.
• Повторения — если два случайных набора содержат одну и ту же строку, они, скорее всего, будут содержать и другие дубликаты.
• Иногда не удается получить нужное количество строк.

«Быстро» означает избегание чтения всех строк. Существует множество методов, требующих полного сканирования таблицы или, по крайней мере, сканирования индекса. Они неприемлемы для этого списка. Существует даже метод, который в среднем сканирует половину таблицы; он переведен в сноску.

Метрики

Вот способ измерения производительности без большой таблицы.

    FLUSH STATUS;
    SELECT ...;
    SHOW SESSION STATUS LIKE 'Handler%';

Если некоторые значения «Обработчик» похожи на количество строк в таблице, то это было сканирование таблицы.

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

Практически все опубликованные алгоритмы включают сканирование таблицы. Предыдущая версия этого блога содержала, к сожалению, несколько алгоритмов со сканированием таблицы.

Иногда сканирование можно избежать с помощью подзапроса. Например, первый из них выполнит сканирование таблицы; второй — нет.

SELECT *  FROM RandTest AS a
  WHERE id = FLOOR(@min + (@max - @min + 1) * RAND());  -- BAD: table scan
SELECT *
 FROM RandTest AS a
 JOIN (
   SELECT FLOOR(@min + (@max - @min + 1) * RAND()) AS id -- Good; single eval.
      ) b  USING (id);

Случай: последовательные AUTO_INCREMENT без пробелов, возвращается 1 строка

• Требование: AUTO_INCREMENT id
• Требование: Нет пробелов в id

  SELECT r.*
      FROM (
          SELECT FLOOR(mm.min_id + (mm.max_id - mm.min_id + 1) * RAND()) AS id
              FROM (
                  SELECT MIN(id) AS min_id,
                         MAX(id) AS max_id
                      FROM RandTest
                   ) AS mm
           ) AS init
      JOIN  RandTest AS r  ON r.id = init.id;

(Конечно, вы можете упростить это. Например, min_id, скорее всего, равен 1. Или предварительно рассчитать пределы в @min и @max.)

Случай: последовательные AUTO_INCREMENT без пробелов, 10 строк

• Требование: AUTO_INCREMENT id
• Требование: Нет пробелов в id
• Недостаток: Иногда возвращает меньше 10 строк

  -- First select is one-time:
  SELECT @min := MIN(id),
         @max := MAX(id)
      FROM RandTest;
  SELECT DISTINCT *
      FROM RandTest AS a
      JOIN (
          SELECT FLOOR(@min + (@max - @min + 1) * RAND()) AS id
              FROM RandTest
              LIMIT 11    -- more than 10 (to compensate for dups)
           ) b  USING (id)
      LIMIT 10;           -- the desired number of rows

Функция FLOOR может привести к дубликатам, поэтому внутренний LIMIT увеличен. Возможно (редко), что дубликатов будет так много, что увеличенный LIMIT приведет к меньшему количеству желаемых 10 различных строк. Одним из способов решения этой проблемы является повторное выполнение запроса, если он возвращает слишком мало строк.

Вариант:

  SELECT r.*
      FROM (
          SELECT FLOOR(mm.min_id + (mm.max_id - mm.min_id + 1) * RAND()) AS id
              FROM (
                  SELECT MIN(id) AS min_id,
                         MAX(id) AS max_id
                      FROM RandTest
                   ) AS mm
              JOIN ( SELECT id dummy FROM RandTest LIMIT 11 ) z
           ) AS init
      JOIN  RandTest AS r  ON r.id = init.id
      LIMIT 10;

Опять же, некрасиво, но быстро, независимо от размера таблицы.

Случай: AUTO_INCREMENT с пробелами, возвращено 1 или более строк

• Требование: AUTO_INCREMENT, возможно, с пробелами из-за DELETE и т. д.
• Недостаток: Только частично случайный (строки не имеют равной вероятности выбора), но частично компенсирует пробелы
• Недостаток: Первые и последние несколько строк таблицы выбираются реже.

Этот метод получает 50 «последовательных» id (возможно, с пробелами), а затем случайным образом выбирает 10 из них.

-- First select is one-time:
SELECT @min := MIN(id),
       @max := MAX(id)
    FROM RandTest;
SELECT a.*
    FROM RandTest a
    JOIN ( SELECT id FROM
            ( SELECT id
                FROM ( SELECT @min + (@max - @min + 1 - 50) * RAND() 
                  AS start FROM DUAL ) AS init
                JOIN RandTest y
                WHERE    y.id > init.start
                ORDER BY y.id
                LIMIT 50         -- Inflated to deal with gaps
            ) z ORDER BY RAND()
           LIMIT 10              -- number of rows desired (change to 1 if looking for a single row)
         ) r ON a.id = r.id;

Да, он сложный, но да, он быстрый, независимо от размера таблицы.

Случай: дополнительный столбец FLOAT для рандомизации

(Незавершенный: необходимо проверить эти данные.)

Предполагая, что `rnd` — это FLOAT (или DOUBLE), заполненный RAND(), и он индексирован:

• Требование: дополнительный, индексированный столбец FLOAT
• Недостаток: Возвращает 10 смежных строк (согласно `rnd`), поэтому случайность не очень хорошая
• Недостаток: Вблизи «конца» таблицы нельзя найти 10 строк.

  SELECT r.*
      FROM ( SELECT RAND() AS start FROM DUAL ) init
      JOIN RandTest r
      WHERE r.rnd >= init.start
      ORDER BY r.rnd
      LIMIT 10;

• Эти два варианта пытаются решить проблему с концом таблицы:

  SELECT r.*
      FROM ( SELECT RAND() * ( SELECT rnd
                        FROM RandTest
                        ORDER BY rnd DESC
                        LIMIT 10,1 ) AS start
           ) AS init
      JOIN RandTest r
      WHERE r.rnd > init.start
      ORDER BY r.rnd
      LIMIT 10;


  SELECT @start := RAND(),
         @cutoff := CAST(1.1 * 10 + 5 AS DECIMAL(20,8)) / TABLE_ROWS
      FROM information_schema.TABLES
      WHERE TABLE_SCHEMA = 'dbname'
        AND TABLE_NAME = 'RandTest'; -- 0.0030
  SELECT d.*
      FROM (
          SELECT a.id
              FROM RandTest a
              WHERE rnd BETWEEN @start AND @start + @cutoff
           ) sample
      JOIN RandTest d USING (id)
      ORDER BY rand()
      LIMIT 10;

Случай: столбец UUID или MD5

• Требование: столбец UUID/GUID/MD5/SHA1 существует и индексирован.
• Аналогичный код/преимущества/недостатки для AUTO_INCREMENT с пробелами.
• Требуются 7 случайных шестнадцатеричных цифр:

RIGHT( HEX( (1<<24) * (1+RAND()) ), 6)

может использоваться в качестве `start` для адаптации случая AUTO_INCREMENT с пробелами. Если поле — BINARY вместо шестнадцатеричного, то

UNHEX(RIGHT( HEX( (1<<24) * (1+RAND()) ), 6))

См. также

Рик Джеймс любезно разрешил нам использовать эту статью в базе знаний.

Сайт Рика Джеймса содержит другие полезные советы, пошаговые инструкции, оптимизации и рекомендации по отладке.

Исходный источник: http://mysql.rjweb.org/doc.php/random