Я хочу случайный выбор строк в PostgreSQL, я попробовал это:

select * from table where random() < 0.01;

Но некоторые другие рекомендуют это:

select * from table order by random() limit 1000;

У меня очень большая таблица с 500 миллионами строк, я хочу, чтобы она была быстрой.

Какой подход лучше? В чем различия? Каков наилучший способ выбора случайных строк?

Учитывая ваши спецификации (плюс дополнительная информация в комментариях),

• У вас есть столбец с числовым идентификатором (целые числа) с небольшим (или умеренно небольшим) пробелом.
• Очевидно, нет или мало операций записи.
• Ваш столбец ID должен быть проиндексирован! Первичный ключ служит хорошо.

Приведенный ниже запрос не требует последовательного сканирования большой таблицы, только сканирование индекса.

Сначала получите оценки для основного запроса:

SELECT count(*) AS ct              -- optional
     , min(id)  AS min_id
     , max(id)  AS max_id
     , max(id) - min(id) AS id_span
FROM   big;

Единственная, возможно, дорогая часть - это count(*)(для огромных столов). Приведенные выше характеристики вам не нужны. Оценка подойдет просто отлично, доступна практически бесплатно ( подробное объяснение здесь ):

SELECT reltuples AS ct FROM pg_class WHERE oid = 'schema_name.big'::regclass;

Пока этот запрос ctне намного меньше id_span, запрос превзойдет другие подходы.

WITH params AS (
    SELECT 1       AS min_id           -- minimum id <= current min id
         , 5100000 AS id_span          -- rounded up. (max_id - min_id + buffer)
    )
SELECT *
FROM  (
    SELECT p.min_id + trunc(random() * p.id_span)::integer AS id
    FROM   params p
          ,generate_series(1, 1100) g  -- 1000 + buffer
    GROUP  BY 1                        -- trim duplicates
    ) r
JOIN   big USING (id)
LIMIT  1000;                           -- trim surplus

• Генерация случайных чисел в idпространстве. У вас есть «несколько пробелов», поэтому добавьте 10% (достаточно, чтобы легко покрыть пробелы) к числу строк для извлечения.

• Каждый idможет быть выбран несколько раз случайно (хотя очень маловероятно с большим пространством идентификаторов), поэтому сгруппируйте сгенерированные числа (или используйте DISTINCT).

• Присоединяйся idк большому столу. Это должно быть очень быстро с индексом на месте.

• Наконец обрежьте излишки id, которые не были съедены обманщиками и пробелами. Каждый ряд имеет абсолютно равные шансы быть выбранным.

Укороченная версия

Вы можете упростить этот запрос. CTE в запросе выше только для образовательных целей:

SELECT *
FROM  (
    SELECT DISTINCT 1 + trunc(random() * 5100000)::integer AS id
    FROM   generate_series(1, 1100) g
    ) r
JOIN   big USING (id)
LIMIT  1000;

Уточнение с помощью rCTE

Особенно, если вы не уверены в пробелах и оценках.

WITH RECURSIVE random_pick AS (
   SELECT *
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   generate_series(1, 1030)  -- 1000 + few percent - adapt to your needs
      LIMIT  1030                      -- hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss

   UNION                               -- eliminate dupe
   SELECT b.*
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   random_pick r             -- plus 3 percent - adapt to your needs
      LIMIT  999                       -- less than 1000, hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss
   )
SELECT *
FROM   random_pick
LIMIT  1000;  -- actual limit

Мы можем работать с меньшим излишком в базовом запросе. Если пропусков слишком много и мы не находим достаточно строк в первой итерации, rCTE продолжает итерацию с рекурсивным членом. Нам все еще нужно относительно небольшое количество пробелов в пространстве идентификаторов, иначе рекурсия может иссякнуть до того, как будет достигнут предел, или мы должны начать с достаточно большого буфера, который не отвечает цели оптимизации производительности.

Дубликаты устраняются UNIONв rCTE.

Внешнее LIMITзаставляет CTE останавливаться, как только у нас появляется достаточно строк.

Этот запрос тщательно разработан, чтобы использовать доступный индекс, генерировать фактически случайные строки и не останавливаться до тех пор, пока мы не выполним ограничение (если рекурсия не иссякнет). Здесь есть ряд подводных камней, если вы собираетесь переписать его.

Оберните в функцию

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

CREATE OR REPLACE FUNCTION f_random_sample(_limit int = 1000, _gaps real = 1.03)
  RETURNS SETOF big AS
$func$
DECLARE
   _surplus  int := _limit * _gaps;
   _estimate int := (           -- get current estimate from system
      SELECT c.reltuples * _gaps
      FROM   pg_class c
      WHERE  c.oid = 'big'::regclass);
BEGIN

   RETURN QUERY
   WITH RECURSIVE random_pick AS (
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   generate_series(1, _surplus) g
         LIMIT  _surplus           -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses

      UNION                        -- eliminate dupes
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   random_pick        -- just to make it recursive
         LIMIT  _limit             -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses
   )
   SELECT *
   FROM   random_pick
   LIMIT  _limit;
END
$func$  LANGUAGE plpgsql VOLATILE ROWS 1000;

Вызов:

SELECT * FROM f_random_sample();
SELECT * FROM f_random_sample(500, 1.05);

Вы могли бы даже сделать это универсальным для работы с любой таблицей: возьмите имя столбца PK и таблицы как полиморфный тип и используйте EXECUTE... Но это выходит за рамки этого вопроса. Видеть:

• Рефакторинг функции PL / pgSQL для возврата результатов различных запросов SELECT

Возможная альтернатива

Если ваши требования позволяют идентичные наборы для повторных вызовов (и мы говорим о повторных вызовах), я бы рассмотрел материализованное представление . Выполните вышеуказанный запрос один раз и запишите результат в таблицу. Пользователи получают квази-случайный выбор со скоростью молнии. Обновите ваш случайный выбор через интервалы или события по вашему выбору.

Postgres 9.5 представляет TABLESAMPLE SYSTEM (n)

Где nпроцент. Руководство:

BERNOULLIИ SYSTEMметоды отбора проб каждый принимают один аргумент , который является частью таблицы в образец, выраженная в процентах от 0 до 100 . Этот аргумент может быть любым real-значным выражением.

Жирный акцент мой. Это очень быстро , но результат не совсем случайный . Руководство снова:

Этот SYSTEMметод значительно быстрее, чем BERNOULLIметод, когда задан небольшой процент выборки, но он может вернуть менее случайную выборку таблицы в результате эффектов кластеризации.

Количество возвращаемых строк может сильно отличаться. Для нашего примера, чтобы получить примерно 1000 строк:

SELECT * FROM big TABLESAMPLE SYSTEM ((1000 * 100) / 5100000.0);

Связанный:

• Быстрый способ узнать количество строк таблицы в PostgreSQL

Или установите дополнительный модуль tsm_system_rows, чтобы точно получить количество запрошенных строк (если их достаточно) и учесть более удобный синтаксис:

SELECT * FROM big TABLESAMPLE SYSTEM_ROWS(1000);

Смотрите ответ Эвана для деталей.

Но это все еще не совсем случайно.

Вы можете изучить и сравнить план выполнения обоих с помощью

EXPLAIN select * from table where random() < 0.01;
EXPLAIN select * from table order by random() limit 1000;

Быстрый тест на большой таблице ¹ показывает, что ORDER BYпервая сортирует полную таблицу, а затем выбирает первые 1000 элементов. Сортировка большой таблицы не только читает эту таблицу, но также включает чтение и запись временных файлов. where random() < 0.1Сканирует только полную таблицу один раз.

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

Третье предложение будет

select * from table where random() < 0.01 limit 1000;

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

Изменить: Помимо этого соображения, вы можете проверить уже заданные вопросы для этого. Использование запроса [postgresql] randomвозвращает довольно много хитов.

• быстрый случайный выбор строк в Postgres
• Как получить рандомизированные строки данных из таблицы postgreSQL?
• postgres: получить случайные записи из таблицы - слишком медленно

И связанная статья зависимость с изложением еще нескольких подходов:

• http://www.depesz.com/index.php/2007/09/16/my-thoughts-on-getting-random-row/

¹ «большой», как в «полная таблица не помещается в память».

postgresql order by random (), выберите строки в случайном порядке:

select your_columns from your_table ORDER BY random()

порядок postgresql методом random () с

select * from 
  (select distinct your_columns from your_table) table_alias
ORDER BY random()

postgresql порядок случайного ограничения одной строкой:

select your_columns from your_table ORDER BY random() limit 1

Начиная с PostgreSQL 9.5, появился новый синтаксис, предназначенный для получения случайных элементов из таблицы:

SELECT * FROM mytable TABLESAMPLE SYSTEM (5);

Этот пример даст вам 5% элементов из mytable.

Более подробное объяснение см. В этом сообщении в блоге: http://www.postgresql.org/docs/current/static/sql-select.html.

Тот, у которого ORDER BY, будет медленнее.

select * from table where random() < 0.01;идет запись за записью, и решает случайным образом отфильтровать его или нет. Это произойдет O(N)потому, что нужно проверять каждую запись только один раз.

select * from table order by random() limit 1000;собирается отсортировать всю таблицу, а затем выбрать первые 1000. Помимо магии вуду за кулисами, порядок по O(N * log N).

Недостатком random() < 0.01является то, что вы получите переменное количество выходных записей.

Обратите внимание, что есть лучший способ перетасовки набора данных , чем сортировка случайные: The Fisher-Yates Перемешать , которая проходит в O(N). Однако реализация shuffle в SQL кажется довольно сложной задачей.

Вот решение, которое работает для меня. Я думаю, это очень просто понять и выполнить.

SELECT 
  field_1, 
  field_2, 
  field_2, 
  random() as ordering
FROM 
  big_table
WHERE 
  some_conditions
ORDER BY
  ordering 
LIMIT 1000;

select * from table order by random() limit 1000;

Если вы знаете, сколько строк вы хотите, проверьте tsm_system_rows.

tsm_system_rows

Модуль предоставляет метод выборки таблицы SYSTEM_ROWS, который можно использовать в предложении TABLESAMPLE команды SELECT.

Этот метод выборки таблицы принимает один целочисленный аргумент, который является максимальным числом строк для чтения. Полученный образец всегда будет содержать ровно столько строк, если в таблице недостаточно строк, и в этом случае будет выбрана вся таблица. Как и встроенный метод выборки SYSTEM, SYSTEM_ROWS выполняет выборку на уровне блоков, так что выборка не является полностью случайной, но может подвергаться эффектам кластеризации, особенно если запрашивается только небольшое количество строк.

Сначала установите расширение

CREATE EXTENSION tsm_system_rows;

Тогда ваш запрос,

SELECT *
FROM table
TABLESAMPLE SYSTEM_ROWS(1000);

Если вам нужна только одна строка, вы можете использовать вычисленную offsetпроизводную от count.

select * from table_name limit 1
offset floor(random() * (select count(*) from table_name));

Возможно изменение материализованного представления «Возможная альтернатива», намеченного Эрвином Брандштеттером .

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

Предполагая, что это входная таблица:

id_values  id  |   used
           ----+--------
           1   |   FALSE
           2   |   FALSE
           3   |   FALSE
           4   |   FALSE
           5   |   FALSE
           ...

Заполните ID_VALUESтаблицу по мере необходимости. Затем, как описано Эрвином, создайте материализованное представление, которое рандомизирует ID_VALUESтаблицу один раз:

CREATE MATERIALIZED VIEW id_values_randomized AS
  SELECT id
  FROM id_values
  ORDER BY random();

Обратите внимание, что материализованное представление не содержит используемый столбец, поскольку он быстро устареет. Представление также не должно содержать другие столбцы, которые могут находиться в id_valuesтаблице.

Для того чтобы получить (и «потреблять») случайные значения, использовать обновленную-Возвратившись id_values, выбирая id_valuesиз id_values_randomizedс объединением, и применяя требуемые критерии для получения только соответствующие возможности. Например:

UPDATE id_values
SET used = TRUE
WHERE id_values.id IN 
  (SELECT i.id
    FROM id_values_randomized r INNER JOIN id_values i ON i.id = r.id
    WHERE (NOT i.used)
    LIMIT 5)
RETURNING id;

При LIMITнеобходимости измените - если вам нужно только одно случайное значение за раз, измените LIMITна 1.

id_valuesЯ считаю, что при правильных индексах UPDATE-RETURNING должен выполняться очень быстро с небольшой нагрузкой. Возвращает рандомизированные значения с одним обращением к базе данных. Критерии для «приемлемых» строк могут быть настолько сложными, насколько это необходимо. Новые строки могут быть добавлены в id_valuesтаблицу в любое время, и они станут доступны приложению, как только обновится материализованное представление (которое, вероятно, может быть запущено в непиковое время). Создание и обновление материализованного представления будет медленным, но его нужно выполнять только при добавлении новых идентификаторов в id_valuesтаблицу.

Один урок из моего опыта:

offset floor(random() * N) limit 1не быстрее чем order by random() limit 1.

Я думал, что такой offsetподход будет быстрее, потому что он сэкономит время сортировки в Postgres. Оказывается, это не так.

Добавьте столбец rс типом serial. Индекс r.

Предположим, у нас есть 200 000 строк, мы собираемся сгенерировать случайное число n, где 0 n<<= 200 000.

Выделите строки с помощью r > n, отсортируйте их ASCи выберите самую маленькую.

Код:

select * from YOUR_TABLE 
where r > (
    select (
        select reltuples::bigint AS estimate
        from   pg_class
        where  oid = 'public.YOUR_TABLE'::regclass) * random()
    )
order by r asc limit(1);

Код не требует пояснений. Подзапрос в середине используется для быстрой оценки количества строк таблицы по адресу https://stackoverflow.com/a/7945274/1271094 .

На уровне приложения вам нужно выполнить инструкцию еще раз, если n> количество строк или нужно выбрать несколько строк.

Я знаю, что немного опоздал на вечеринку, но я нашел этот замечательный инструмент под названием pg_sample :

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

Я попробовал это с базой данных на 350 миллионов строк, и это было действительно быстро, не знаю, что такое случайность .

./pg_sample --limit="small_table = *" --limit="large_table = 100000" -U postgres source_db | psql -U postgres target_db