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

    Последнее время оживилась публика с вопросом случайной выборки из таблицы. Решений по оптимизации полно, и нового сейчас я вам наверное ничего не покажу, просто напомню про основные методы оптимизации — упрощение запроса и индексацию. Без предисловий про фриленсеров, сразу к делу ;)

    Создаю таблицу:
    CREATE TABLE `a` (
    `id` int(8) unsigned NOT NULL AUTO_INCREMENT,
    `md5` char(32) NOT NULL
    PRIMARY KEY (`id`)
    )
    INSERT INTO `a` (`id`) VALUES (null),(null),(null),(null)... и так 163712 раза ;)
    UPDATE `a` SET md5 = MD5(`id`);

    Такой таблицы на моём допотопном компьютере достаточно, чтобы проверить эффективность.
    Вот простая выборка ORDER BY RAND:
    SELECT * FROM `a` ORDER BY RAND() LIMIT 10; -> (10 rows, Query took 0.3345 sec)
    SELECT * FROM `a` ORDER BY RAND() LIMIT 10; -> (10 rows, Query took 0.2538 sec)
    SELECT * FROM `a` ORDER BY RAND() LIMIT 10; -> (10 rows, Query took 0.2299 sec)

    Создаю индексированное поле для того чтобы не делать full-scan всей таблицы:
    ALTER TABLE `a` ADD `f` SMALLINT(3) UNSIGNED NOT NULL, ADD INDEX (`f`);
    UPDATE `a` SET `f` = RAND()*1000;
    Число 1000 — это основной «ускоряющий» фактор. Им я уменьшаю таблицу в которой будет проходить обыкновенный ORDER BY RAND в 1000 раз. При таблице 163712 рядов должно получится примерно 164 ряда на один f. Проверяем:
    SELECT COUNT(1) FROM `a` WHERE `f` = 123; -> 169

    Рандом есть рандом, равномерное распределение было бы хорошо, но это фантастика (хотя знаете, можно воспользоваться первыми знаками MD5(`id`) и перевести его в INT, равномернее некуда). Итак, сейчас на один f мне попадались и по 200 рядов и по 100. Если этот показатель со временем становится неэффективным, то всегда можно увеличить фактор и получить, скажем, по 25-75 рядов на индекс. Главное чтобы там было как минимум столько рядов, сколько нам нужно вытаскивать рандомно. Колонку f можно перегенерировать периодически, или после 1000 обращений к таблице. При вставке новые ряды получают значение f = 0, что на качество выборок сильно не повлияет, либо задавайте рандомные значения при вставках тоже.

    Делаю тестовую выборку 10 рядов используя то что наиндексировал:
    SELECT * FROM `a` WHERE `f` = 231 ORDER BY RAND() LIMIT 10; -> (10 rows, Query took 0.0801 sec)
    SELECT * FROM `a` WHERE `f` = 231 ORDER BY RAND() LIMIT 10; -> (10 rows, Query took 0.0017 sec)
    Ага, второй раз получилась пересортированная выборка из кэша mysql. Если повторение результатов не сильно страшно, то сгодится и такой более шустрый результат, но лучше менять число f при каждом запросе.

    Повторяю тест, изменяя f:
    SELECT * FROM `a` WHERE `f` = 396 ORDER BY RAND() LIMIT 10; -> (10 rows, Query took 0.0147 sec)
    SELECT * FROM `a` WHERE `f` = 753 ORDER BY RAND() LIMIT 10; -> (10 rows, Query took 0.0020 sec)
    SELECT * FROM `a` WHERE `f` = 189 ORDER BY RAND() LIMIT 10; -> (10 rows, Query took 0.0019 sec)
    SELECT * FROM `a` WHERE `f` = 945 ORDER BY RAND() LIMIT 10; -> (10 rows, Query took 0.0235 sec)

    В общем производительность выборки поднялась в 120 раз и это без всякого рода усложнений. Я вижу в таком решении массу удобств:
    • не нужно лазить далеко в дебри и ломать голову «блин как эта у меня была… ах да процедура».
    • простая интеграция ;) код запроса был усложнён всего одним условием.
    • ну и третье назовём расширяемостью: добавь свои условия и ты ещё уменьшишь размер скана, увеличив тем самым скорость выборки.
    Если одного промежутка 160 рядов нам не достаточно, то можно включить столько промежутков сколько угодно:
    SELECT * FROM `a` WHERE `f` IN (100,500) ORDER BY RAND() LIMIT 10;

    Более жизненный пример


    Для такого примера возьмём верхний комментарий из соседнего поста, который решается так. Эмитируем таблицу RSS-фидов, добавив поле feed содержащее номер фида:
    ALTER TABLE `a` ADD `feed` TINYINT(1) UNSIGNED NOT NULL, ADD INDEX (`feed`);
    UPDATE `a` SET feed = RAND()*9;
    А теперь, собственно, финт ушами:
    (SELECT * FROM `a` WHERE `f` = 283 AND `feed` = 0 ORDER BY RAND() LIMIT 10)
    UNION (SELECT * FROM `a` WHERE `f` = 283 AND `feed` = 1 ORDER BY RAND() LIMIT 10)
    UNION (SELECT * FROM `a` WHERE `f` = 283 AND `feed` = 2 ORDER BY RAND() LIMIT 10)
    UNION (SELECT * FROM `a` WHERE `f` = 283 AND `feed` = 3 ORDER BY RAND() LIMIT 10)
    UNION (SELECT * FROM `a` WHERE `f` = 283 AND `feed` = 4 ORDER BY RAND() LIMIT 10)
    UNION (SELECT * FROM `a` WHERE `f` = 283 AND `feed` = 5 ORDER BY RAND() LIMIT 10)
    UNION (SELECT * FROM `a` WHERE `f` = 283 AND `feed` = 6 ORDER BY RAND() LIMIT 10)
    UNION (SELECT * FROM `a` WHERE `f` = 283 AND `feed` = 7 ORDER BY RAND() LIMIT 10)
    UNION (SELECT * FROM `a` WHERE `f` = 283 AND `feed` = 8 ORDER BY RAND() LIMIT 10)
    UNION (SELECT * FROM `a` WHERE `f` = 283 AND `feed` = 9 ORDER BY RAND() LIMIT 10)
    ORDER BY feed; -> (97 rows, Query took 0.7973 sec)
    С другим f -> (99 rows, Query took 0.0093 sec)
    С другим f -> (98 rows, Query took 0.0197 sec)
    Тут желательно выбирать больше чем 10 рядов для верности ;) и фильтровать лишнее на PHP.

    На PHP также желательно задавать число f, чтобы не делать по два запроса к MySQL серверу. Хотя, это не критично. Такое тоже будет работать очень быстро:
    SET @rnd = RAND(); SELECT * FROM `a` WHERE `f` = @rnd ORDER BY RAND() LIMIT 10;

    Как вы видите, не только лишь усложнением можно добитсья оптимизации (в данной статье я оптимизировал скорость). Теперь вопрос вам на подумать, а мне в будущей статье изложить. Как можно оптимизировать качество произвольных выборок, прежде всего избавится от повторений? ;)

    С уважением,
    Маям.
    Поделиться публикацией

    Похожие публикации

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

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

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

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

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

          +1
          К сожалению это запустит смену `f` на каждом новом ряду. Увы, не верное решение, но рад что вы стали мыслить вместе со мной )
            0
            Да. Сбойнул. Случайное число надо получить до селекта. И уж потом вставить его в запрос.
          0
          Может везде `f` = x заменить на `f` >= x, тогда по идее выборок менее чем с десятью элементами станет меньше.
            +1
            тогда вся затея теряет смысл
              0
              Да, мой косяк. Написал не продумав.
            0
            Попытаюсь исправится, ибо утром был ещё сонным(можете заминусовать его, чтоб скрылся =)).

            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; Тогда дисперсия будет равномерной, но появятся проблемы с добавлением при сильной заполненности таблицы.

            А вообще подход автора весьма интересен.
              0
              Ещё немного подумав о подходе предложенном miami
              К сожалению он добавляет некую дольку «псевдослучайности». То есть фактически, в приведённом примере, при запросе десяти записей по одному и тому же `f` у нас есть всего ~16 непересекающихся вариантов выборок, также отсутствует даже теоретическая возможность попадания в эту выборку записей с другим значением `f`
                +2
                Значение f — это не критерий поиска, это всего лишь ускорение прохода по таблице. Смысл не в том, чтобы выбрать из различных f ;))) Хотя да, эсли внезапно понадобилось более 10 случайных результатов, а индекс перестраивать не хочется, то подойдёт такой вариант:
                SELECT * FROM `a` WHERE `f` IN (100,500,x5,x25,... ) ORDER BY RAND() LIMIT 10;
                  0
                  Это я и имел виду под пунктом 3. Хотя если f часто обновлять то это не существенно.
                    0
                    Имеется 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;

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

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

                      Остался только вопрос в сравнении скорости алгоритмов предложенных Вами и TimTowdy на разных объёмах выборки(1,10,100,1000 например).
                        0
                        На всё той же своей таблице тестирую метод 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, а тем кто предпочитает иметь скорость и контролировать её понравится индекс. Я понимаю что у всех нас разные требования к приложениям, от этого и количество вариантов и я лично за! За то, чтобы усовершенствование продолжалось, чтобы мысль в эту сторону направлена была, чтобы мы не забывали полюбившуюся нам базу данных и учились для себя из неё-родимой выжимать максимум )

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

                  Откуда такая информация?
                    0
                    Экспериментировал…: Р
                    0
                    Хорошая идея. Лишнее подтверждение, что чаще всего быстродействие достигается за счет расхода дополнительной памяти.
                      0
                      Вы имеете ввиду индекс?
                      Ну да, для получения одного приходится жертвовать другим…
                      0
                      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;
                        0
                        Случайный офсет не помогает сократить пробег по таблице. Это объясняет
                        EXPLAIN SELECT * FROM `test` LIMIT 1 OFFSET 1234

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

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

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое