Пользователь
0,0
рейтинг
12 ноября 2014 в 12:45

Разработка → Postgres. Выборка N случайных записей из песочницы

При работе над одним проектом возникла необходимость написать некое подобие тестовой системы. Задача формулировалась примерно так:

  • из N записей в базе необходимо выбрать m (3-5) случайных строк в серии из k выборок (преимущественно k=2).

А теперь то же самое человеческим языком: из таблицы нужно два раза выбрать по 3-5 случайных записей. При этом не должно быть дубликатов и выборка должна происходить случайным образом.

Первое, что приходит в голову:

 SELECT *
  FROM data_set
  WHERE id NOT IN (1,2,3,4, 5)
  ORDER BY random()
  LIMIT 5;

И это даже будет работать. Вот только цена такого решения…

Поэтому пришлось воспользоваться «высшим разумом», который выдал намёк на решение.

WITH RECURSIVE r AS ( 
    WITH b AS (SELECT min(id), max(id) FROM table1) 
    ( 
        SELECT id, min, max, array[]::integer[] AS a, 0 AS n 
        FROM table1, b 
        WHERE id > min + (max - min) * random() 
        LIMIT 1 
    ) UNION ALL ( 
        SELECT t.id, min, max, a || t.id, r.n + 1 AS n 
        FROM table1 AS t, r 
        WHERE 
            t.id > min + (max - min) * random() AND 
            t.id <> all(a) AND 
            r.n + 1 < 10 
        LIMIT 1 
    ) 
) 
SELECT t.id FROM table1 AS t, r WHERE r.id = t.id;

Вот только решение это… «слегка» непонятное. А тащить непонятные решения в проект как-то неохота. Поэтому было решено пойти уже проверенным путём, где удалось найти пояснение сущности рекурсивных запросов.

Что же. Логика в общих чертах стала более-менее понятной: n раз выбираем по одной строке со случайным смещением от минимального значения ID (primary key). Таким образом запрос затрагивает максимум N строк вместо полного перебора содержимого таблицы.

Но «гладко было на бумаге». При попытке использования «как есть» (с поправкой на имена таблицы/полей) всплыли «сюрпризы»:

  1. Массив в строке 4 создаётся пустым. Из-за этого в финальной выборке могут оказываться дубликаты. Скажем, запрос в строчках 4-7 возвращает id==5. После этого отрабатывает запрос в UNION блоке (строчки 9-15) и на каком-то этапе возвращает то же id==5, поскольку предыдущее значение id не попало в массив "а" и проверка в строке 13 «t.id <> all(a)» прошла успешно;
  2. Количество значений на «выходе» было не более чем указано (стр. 14). Но меньше этого — запросто. Даже если оное количество гарантировано было в таблице. Иногда возвращалась пустая выборка (количество значений «0»).

С первой «особенностью» справиться оказалось сравнительно легко — достаточно было чуть поменять строчку с инициализацией массива. Примерно так:

SELECT id, min, max, array[]::integer[] || id AS a, 0 AS n 

А вот второй пункт заставил пораскинуть мозгами. Подвох обнаружился в самом «сердце» алгоритма — выборке записи из диапазона. Действительно, рекурсивный запрос пытается выбрать строчку, для которой выполнялось бы условие:

id > min + (max - min) * random()

Но в случае, когда random() возвращает «1», это условие трансформируется в:

id > max

Естественно, что в этом случае запрос ничего не найдёт и прекратит работу. А ежели такое случится при первом же проходе запроса, то «на выходе» будет пусто. Даже если в базе заведомо присутствуют нужные записи.

Первым побуждением было слегка изменить условие и привести его примерно к такому виду:

id >= min + (max - min) * random()

Это, так сказать, решение позволило получать минимум одну строчку на выходе. Но вовсе не гарантировало получения заданного количества строк в результате. Пришлось думать дальше.

После длительных размышлений, множества попыток, и литров стимулятора появился на свет
такой вот вариант:

код запроса
WITH RECURSIVE r AS (
 WITH b AS (
   SELECT
  min(t.id),
  (
   SELECT t.id
   FROM table1 AS t
   ORDER BY t.id DESC
   LIMIT 1
   OFFSET 9
  ) max
  FROM table1 AS t
 )
 (
  SELECT
    id, min, max, array[]::integer[] || id AS a, 0 AS n
  FROM table1 AS t, b
  WHERE
    id >= min + ((max - min) * random())::int
  LIMIT 1
 ) UNION ALL (
  SELECT t.id, min, max, a || t.id, r.n + 1 AS n
  FROM {table} AS t, r
  WHERE
   t.id >= min + ((max - min) * random())::int AND
   t.id <> all(a) AND
   r.n + 1 < 10
  LIMIT 1
 )
)
SELECT t.* FROM table1 AS t, r WHERE r.id = t.id

Вся соль в строчках 5-11. Т.е. дабы гарантировать, что на «выходе» будет N элементов нужно исходить из худшего из возможных сценариев. В данном случае — что random N раз подряд вернёт 1. Следовательно нужно знать/иметь N-1 значений перед max. Как этого достичь в запросе? Как вариант — отсортировать все записи по ID в порядке убывания и произвести смещение «вниз» на N строк. А поскольку в строках 19 и 25 используется ">=", то смещение можно указать на единицу меньше (N-1).

Вот и хорошо — основные затруднения решены и остались «мелочи»: запрос в текущем виде мало полезен. Нужно ведь делать выборку с учётом некоторых условий. В простейшем случае — исключать из выборки ID записей, выбранных на предыдущем этапе. Кроме того, нельзя исключать возможность использования каких-то дополнительных условий налагаемых на строки в таблице (is_active = true, is_deleted=false, ...). После некоторых размышлений становится понятно, что условия придётся ставить во все существенные части запроса (практически все подзапросы). Примерно как в следующем шаблоне:

код шаблона
WITH RECURSIVE r AS (
 WITH b AS (
   SELECT
  min(t.{pk}),
  (
   SELECT t.{pk}
   FROM {table} AS t
   WHERE {exclude} t.is_active
   ORDER BY t.{pk} DESC
   LIMIT 1
   OFFSET {limit} - 1
  ) max
  FROM {table} AS t WHERE {exclude} t.is_active
 )
 (
  SELECT
    t.{pk}, min, max, array[]::integer[] || t.{pk} AS a, 0 AS n
  FROM {table} AS t, b
  WHERE
    t.{pk} >= min + ((max - min) * random())::int AND
    {exclude}
    t.is_active
  LIMIT 1
 ) UNION ALL (
  SELECT t.{pk}, min, max, a || t.{pk}, r.n + 1 AS n
  FROM {table} AS t, r
  WHERE
   t.{pk} >= min + ((max - min) * random())::int AND
   t.{pk} <> all(a) AND
   r.n + 1 < {limit} AND
   {exclude}
   t.is_active
  LIMIT 1
 )
)
SELECT {fields} FROM {table} AS t, r WHERE r.{pk} = t.{pk}


Тут в фигурных скобках указаны именованные параметры, подлежащие замене:

  • {table} — название таблицы;
  • {pk} — имя PrimaryKey-поля;
  • {fields} — список полей для выборки (можно указать и "*");
  • {exclude} — условие (набор условий) для исключения записей из выборки. Например «t.id NOT IN (1,2,3,4)»;
  • {limit} — количество записей в финальной выборке


И, наконец, последний в списке, но не по важности вопрос: «стоит ли овчинка выделки»? Каков «профит» от этой мозголомной конструкции? Будем проверять.

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

DROP TABLE IF EXISTS ttbl;
CREATE TABLE IF NOT EXISTS ttbl
(
  id serial NOT NULL,
  is_active BOOL NOT NULL DEFAULT true,
  CONSTRAINT ttbl_pkey PRIMARY KEY (id)
)
WITH (OIDS=FALSE);

Теперь наполним её данными. При этом нужно, чтобы значения id не шли последовательно, а имели «дырки». Т.е. не «1, 2, 3, 4, 5...» а хотя-бы «1, 4, 5, 8....». Для этого набросаем простенький скриптик.
код скрипта
import random

import psycopg2


DB_TABLE = 'ttbl'
PK_NAME = 'id'
DATABASES = {
    'NAME': 'test_db',
    'USER': 'user_test',
    'PASSWORD': 'R#Q9Jw*ZEKWOhBX+EP|3/xGkQn3',
    'HOST': 'localhost',
    'PORT': '',
}

TOTAL = 10000000
current = 0
step = 10000
dev = 8
while current <= TOTAL:
    data = set()
    for x in range(current, current+step, 10):
        data.add(x + int(random.random() * dev))

    x = cur.execute(
        "INSERT INTO {t_table} VALUES {t_items};".format(
                t_table=DB_TABLE,
                t_items='(' + '), ('.join(map(str, data)) + ')'
        )
    )
    current += step
    print(x, current)
    
cur.execute('COMMIT;')



Как видно из кода — каждый запрос вставляет по сотне записей. Значения меняются с шагом примерно «10». Примерно, т.к. каждое из значений может отклоняться на случайную величину в диапазоне 0-dev. Т.е. при двух последовательных значениях x «340» и «350» в таблицу могут быть вставлены любые значения из диапазона 340-348 и 350-358 (342, 347, 340...; 351, 355, 358...).

Итого в таблице оказалось
select count(id) from ttbl;

1001000 записей

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

Сначала простой запрос
select t.*
from ttbl t
where 
  t.id not in (1, 3, 10, 89, 99, 22, 24, 25, 28, 30) 
  AND t.is_active
order by random()
limit 5;

Результаты:
№ п/п время, ms
1 697
2 605
3 624
4 593
5 611

Как видно, среднее время выполнения запроса около* 600ms.

А сейчас — «монстр».
смотреть монстра
WITH RECURSIVE r AS (
  WITH b AS (
    SELECT
    min(t.id),
    (
      SELECT t.id
      FROM ttbl AS t
      WHERE
        t.id NOT IN (1, 3, 10, 89, 99, 22, 24, 25, 28, 30)
        AND t.is_active
      ORDER BY t.id DESC
      LIMIT 1
      OFFSET 5 - 1
    ) max
    FROM ttbl AS t
    WHERE 
      t.id NOT IN (1, 3, 10, 89, 99, 22, 24, 25, 28, 30)
      AND t.is_active
  )
  (
    SELECT
      id, min, max, array[]::integer[] || id AS a, 0 AS n
    FROM ttbl AS t, b
    WHERE
      id >= min + ((max - min) * random())::int AND
      t.id NOT IN (1, 3, 10, 89, 99, 22, 24, 25, 28, 30) AND
      t.is_active
    LIMIT 1
  ) UNION ALL (
    SELECT t.id, min, max, a || t.id, r.n + 1 AS n
    FROM ttbl AS t, r
    WHERE
      t.id > min + ((max - min) * random())::int AND
      t.id <> all( a ) AND
      r.n + 1 < 5 AND
      t.id NOT IN (1, 3, 10, 89, 99, 22, 24, 25, 28, 30) AND
      t.is_active
    LIMIT 1
  )
)
SELECT t.* FROM ttbl AS t, r WHERE r.id = t.id


Результаты:
№ п/п время, ms
1 15
2 17
3 8
4 12
5 12

Среднее время около* 15ms.

Итого разница примерно на полтора порядка (в 40-50 раз). Оно таки того стоило.

Запросы проверялись в т.ч. и при «холодном» старте (после перезапуска машины/демона). И хотя время выполнения в абсолютном выражении менялось, но соотношение оставалось постоянным (насколько это возможно). Т.е. рекурсивный запрос всегда в несколько десятков раз был быстрее решения «в лоб».

Примечания


*Около, т.к. точное значение роли не играет из-за отклонений, вызванных кешем Postgres-а, влиянием операционной системы, железа, остального софта и т.д.
@murminathor
карма
9,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (47)

  • +1
    Великолепно! Схоронил себе, на случай, когда понадобится делать рандомные выборки.

    Только я не понял почему Рекурсивный запрос с 2мя селектами внутри быстрее простого селекта. Order by такой тяжелый?
    • 0
      Здесь есть более подробное рассмотрение данной ситуации, приём достаточно распостранённый: pgday.ru/files/pgmaster14/max.boguk.query.optimization.pdf
    • 0
      Если посмотреть план первого запроса, то становится все понятно.

      'Limit (cost=4663.25..4663.26 rows=5 width=75)'
      ' -> Sort (cost=4663.25..4911.37 rows=99249 width=75)'
      ' Sort Key: (random())'
      ' -> Seq Scan on location (cost=0.00..3014.76 rows=99249 width=75)'
      ' Filter: (id<> ALL ('{2,3}'::text[]))'

      С начало выполняется извлечение данных из таблицы, затем их сортировка, только потом выбираются первые 5 строк.
  • +3
    А почему нельзя просто получить максимальный id, сгенерить 5 значений меньше этого значения и сделать 5 запросов вида:

    SELECT * FROM ttbl WHERE id < my_generated_n LIMIT 1

    и условия дополнительные легче вешать и запросов получиться на 1 больше но в разы более лёгких?

    Или если есть возможность запихать всё в redis в виде множества idшников и выбирать с SRANDMEMBER? (так вообще очень быстро получится)
    • 0
      много нюансов.

      например при случае когда мы сгенерировали ..., 25, 29,…
      а в базе есть только id = 24 в промежутке 20… 30 мы 2 раза получим одинаковое значение
      + если нам понадобится больше чем 5 значений время на получение данных будет расти.
      • 0
        Как вариант создать таблицу в памяти из всех подходящих под условие id(id,t.id), а затем в ней чистым рандомом от размера выбирать. Достаточно лишь хранить где-то уже выбранные айдишники и в цикле получать новый пока он не будет не входящим в уже выбранные
      • 0
        А можно план выполнения вашего запроса посмотреть?
        • 0
          Да, конечно.

          План запроса
          Nested Loop  (cost=2.42..95.38 rows=11 width=5) (actual time=4.633..11.737 rows=5 loops=1)
            Buffers: shared hit=26 read=23
            CTE r
              ->  Recursive Union  (cost=0.29..2.42 rows=11 width=48) (actual time=4.184..10.575 rows=5 loops=1)
                    Buffers: shared hit=10 read=19
                    CTE b
                      ->  Result  (cost=0.28..0.29 rows=1 width=0) (actual time=2.340..2.340 rows=1 loops=1)
                            Buffers: shared hit=2 read=9
                            InitPlan 1 (returns $1)
                              ->  Limit  (cost=0.19..0.24 rows=1 width=4) (actual time=1.121..1.122 rows=1 loops=1)
                                    Buffers: shared hit=2 read=4
                                    ->  Index Scan Backward using ttbl_pkey on ttbl t  (cost=0.00..47048.93 rows=1000990 width=4) (actual time=0.830..1.116 rows=5 loops=1)
                                          Filter: (is_active AND (id <> ALL ('{1,3,10,89,99,22,24,25,28,30}'::integer[])))
                                          Buffers: shared hit=2 read=4
                            InitPlan 2 (returns $2)
                              ->  Limit  (cost=0.00..0.05 rows=1 width=4) (actual time=1.207..1.207 rows=1 loops=1)
                                    Buffers: shared read=5
                                    ->  Index Scan using ttbl_pkey on ttbl t  (cost=0.00..49551.43 rows=1000990 width=4) (actual time=1.205..1.205 rows=1 loops=1)
                                          Index Cond: (id IS NOT NULL)
                                          Filter: (is_active AND (id <> ALL ('{1,3,10,89,99,22,24,25,28,30}'::integer[])))
                                          Buffers: shared read=5
                    ->  Subquery Scan on "*SELECT* 1"  (cost=0.00..0.18 rows=1 width=12) (actual time=4.179..4.181 rows=1 loops=1)
                          Buffers: shared hit=3 read=15
                          ->  Limit  (cost=0.00..0.17 rows=1 width=12) (actual time=4.178..4.179 rows=1 loops=1)
                                Buffers: shared hit=3 read=15
                                ->  Nested Loop  (cost=0.00..55313.90 rows=333663 width=12) (actual time=4.175..4.175 rows=1 loops=1)
                                      Join Filter: (t.id >= (b.min + ((((b.max - b.min))::double precision * random()))::integer))
                                      Buffers: shared hit=3 read=15
                                      ->  CTE Scan on b  (cost=0.00..0.02 rows=1 width=8) (actual time=2.342..2.342 rows=1 loops=1)
                                            Buffers: shared hit=2 read=9
                                      ->  Seq Scan on ttbl t  (cost=0.00..26952.50 rows=1000990 width=4) (actual time=0.015..0.907 rows=1368 loops=1)
                                            Filter: (is_active AND (id <> ALL ('{1,3,10,89,99,22,24,25,28,30}'::integer[])))
                                            Buffers: shared hit=1 read=6
                    ->  Limit  (cost=0.00..0.17 rows=1 width=48) (actual time=1.273..1.274 rows=1 loops=5)
                          Buffers: shared hit=7 read=4
                          ->  Nested Loop  (cost=0.00..173819.35 rows=1000980 width=48) (actual time=1.272..1.272 rows=1 loops=5)
                                Join Filter: ((t.id <> ALL (r.a)) AND (t.id > (r.min + ((((r.max - r.min))::double precision * random()))::integer)))
                                Buffers: shared hit=7 read=4
                                ->  WorkTable Scan on r  (cost=0.00..0.25 rows=3 width=44) (actual time=0.005..0.005 rows=1 loops=5)
                                      Filter: ((n + 1) < 5)
                                ->  Materialize  (cost=0.00..35868.45 rows=1000990 width=4) (actual time=0.007..0.740 rows=1012 loops=4)
                                      Buffers: shared hit=7 read=4
                                      ->  Seq Scan on ttbl t  (cost=0.00..26952.50 rows=1000990 width=4) (actual time=0.019..1.442 rows=2335 loops=1)
                                            Filter: (is_active AND (id <> ALL ('{1,3,10,89,99,22,24,25,28,30}'::integer[])))
                                            Buffers: shared hit=7 read=4
            ->  CTE Scan on r  (cost=0.00..0.22 rows=11 width=4) (actual time=4.189..10.591 rows=5 loops=1)
                  Buffers: shared hit=10 read=19
            ->  Index Scan using ttbl_pkey on ttbl t  (cost=0.00..8.42 rows=1 width=5) (actual time=0.221..0.223 rows=1 loops=5)
                  Index Cond: (id = r.id)
                  Buffers: shared hit=16 read=4
          Total runtime: 12.185 ms
          


          Правда план запроса под стать запросу. Я пытался его «раскурить», но потом решил что проще будет проверить экспериментально.
  • 0
    В MSSQL насколько я знаю делают select top 100 * from [Table] order by NEWID()
    Где NEWID() генерит новый случайный guid. Может и тут можно что-то такое сделать?
    • 0
      А здесь разве не та же проблема? Выбрать все строки, отсортировать по случайному значению, вернуть 100 первых.
    • 0
      проще уж способ наподобие:

      select * from table where random() < 0.01;

      использовать
      • 0
        Кстати да. Этот вариант хотя бы не заставляет сортировать всю таблицу.
        Но подходит только для больших таблиц. И то, если сильно не повезет, то этот запрос может не вернуть значений даже на таблице в миллион записей.
        • 0
          + на больших таблицах работает медленнее, чем монстр из поста.

          execution time: 203 ms; total time: 437 ms
    • 0
      В MSSQL есть забавная конструкция TABLESAMPLE (вообще-то это ANSI SQL синтаксис):

      SELECT FirstName, LastName
      FROM Person
      TABLESAMPLE (100 ROWS) ;
      


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

      TABLESAMPLE (10 PERCENT)
      
  • 0
    А не проще сгенерировать некоторое ко-во случайный непересекающихся индексов и потом выбрать эти элементы из таблицы по порядковому номеру? Это же будет самое быстрое решение.
    • 0
      Это возможно если только индексы идут по порядку, без промежутков. У Оракла, например, по умолчанию включенно кеширование сиквенсов, поэтому индексы там обычно имеют вид 1, 11, 21, 31,… и т.д.
  • +1
    На 5+ миллионах записей еще интереснее.

    random() — 12+ секунд
    «монстр» — 62 мс
  • +1
    А если 5 раз
    SELECT * FROM table WHERE id not in(X1...Xn-1) LIMIT Xn,1?
    Где Xn это случайное число от 1 до count(1)-n
    n номер случайного числа.
    • 0
      Только что проверил.
      SELECT * 
      FROM ttbl 
      WHERE id not in(1, 3, 10, 89, 99, 22, 24, 25, 28, 30) 
      OFFSET (random()* 1000)::int
      LIMIT 1

      Время выполнения одного запроса 2-14ms. Нужно их 10. При этом нужно учесть, что это только время на выполнения запроса в базе. Но будут ещё накладные расходы на доставку каждого ответа в приложение, обработку, формирование нового запроса…
  • 0
    А что-то типа

    select * from my_table where id = random() limit 10

    (с поправкой на синтаксис, конечно) в постгресе разве нельзя сделать? Спрашиваю, потому что не знаком с этой СУБД.
  • 0
    А если индекс по рандому сделать, и выбирать каждый раз следующую «страницу». Дошли до конца — пересчитали индекс. Ну или пересчитывать по расписанию.
    Хотя тут конечно тоже нюансы есть. Если паре юзеров пришел одинаковый «рандомный» результат, — плохо ли это. Если так важны миллисекунды, значит запросов много, и такой вариант, имхо, не самый плохой. И, я полагаю, будет быстро.
  • 0
    Из любопытства попробовал взять с запасом случайных id и выбрать по ним из базы.
    Профит: простой SQL, и не сложный код.
    Вот решение на groovy:
    @GrabConfig(systemClassLoader=true)
    @Grab('postgresql:postgresql:9.0-801.jdbc4')
    import groovy.sql.Sql
    
    def sql = Sql.newInstance('jdbc:postgresql://localhost/test', 'postgres', '123', 'org.postgresql.Driver')
    def random = new Random()
    
    def t0 = System.currentTimeMillis()
    def v = []
    def (min, max) = sql.firstRow("select min(id), max(id) from ttbl")
    def nums = (0..100).collect { (min + random.nextInt(max - min + 1)) as String }
    def strNums = nums.join(',')
    
    sql.eachRow("select id from ttbl where id in ($strNums)".toString()) {
        v += it.id
    }
    println v
    def t1 = System.currentTimeMillis()
    println "Time: ${t1 - t0}"
    


    Недостаток этого решения, может ничего не найти, особенно на сильно разряженных таблицах.
    • 0
      А, вот еще идея.
      Взять количество строк, взять случайные номера строк, и выполнить такой запрос:
      SELECT id FROM (
      	SELECT id, rank() OVER (ORDER BY id) as row_number FROM ttbl
      ) AS X
      WHERE X.row_number IN (707, 32220, 102503)
      
  • 0
    Выборка случайных записей рациональным(!) способом — в любой СУБД несколько нетривиальная проблема.

    Спасибо за пост!
  • +3
    • 0
      Спасибо за линк. Возможно в той ветке форума и найдут лучшее решение. На это позволяет надеяться хотя бы тот факт, что один из вариантов решения уже упомянули.
      Вот эта версия работает на совершенно любом распределении и работает корректно.
      Но на сильно разреженных таблицах конечно не быстрая:

      тело запроса
      WITH RECURSIVE
      range AS (
        SELECT min(id) AS min, max(id) AS max FROM table1
      ), 
      r AS (
          SELECT array[]::integer[] AS res
        UNION ALL
          SELECT CASE WHEN (id IS NULL) THEN res ELSE res||id END 
          FROM (SELECT (min + (max - min) * random())::int AS rnd,res FROM r JOIN range ON true) AS _r
          LEFT JOIN table1 ON id=rnd AND id <> all(res) 
          WHERE 
            id IS NULL OR coalesce(array_length(res,1),0)<=10 
      ) 
      SELECT unnest(res) FROM (
        SELECT res FROM r ORDER BY array_length(res,1) DESC NULLS LAST LIMIT 1
      ) AS t;
      

      Вот только приведённое решение нестабильно — зацикливается поскольку. Только что проверил на таблице с 4 строчками указав выбрать 3.
      Но само направление поиска довольно интересное. Вероятно если вдумчиво «раскурить» приведённый запрос проблему с зацикливанием удастся обойти.
  • +3
    При неравномерном распределении значений ID результирующая выборка также будет неравномерной
    Что вернет «монстр» на маленькой таблице с ID вида (1,2,3,10000000,10000001, 10000002, 10000003)?
    • +1
      Промоделировал на firebird
      Т.к. в Firebird нет массивов, заменил их строками с разделителем "~"
      По-моему похоже
      WITH RECURSIVE
          minID AS (SELECT min(id) minId FROM table1),
          maxID AS (SELECT max(id) maxId FROM table1),
          r as (
            select first 1 id, minId, maxId, cast('~'||id||'~' as varchar(100)) a, 0 n from table1, minID, maxId
            where id > minId + (maxId - minId) * rand()
              union all
            select first 1 m.id, minId, maxId, a||m.id||'~', n + 1 from table1 m, r
            where m.id > minId + (maxId - minId) * rand() and r.a not containing '~'||m.id||'~' and r.n + 1 < 3
          )
      SELECT t.id FROM table1 t, r WHERE r.id = t.id;
      


      Проблемы этого метода очень хорошо видны на маленькой таблице

      1) Если есть на пример ID = (1, 1000000000, 1000000001, 1000000002, 1000000003, 100000004) строки почти всегда в одном и том же порядке
      2) Не инициализируется массив «а» он должен быть равен первому ID
    • 0
      Спасибо, что указали на этот момент. Действительно при больших «дырках» в распределении значений ID время от времени будет возвращаться одна и та же последовательность. И хотя сейчас для моего случая это не критично, но вскоре нужно будет как-то этот вопрос решить.
      Пока что хороших идей по этому поводу у меня нет. Из остальных — разве что разделить «primary key» и «sort key». После чего хранимыми процедурами поддерживать приемлемый уровень разрежённости «sort key».
      Если бы дело было только в «primary key» — фиг бы с ним. Но нужно учитывать ещё и условия на остальных столбцах. А это уже дублирование логики приложения в СУБД, со всеми последствиями такого шага.
  • –1
    В свое время подобную задачу в mySQL решил следующим образом. Сначала на PHP сгенерировал необходимое количество случайных чисел:
    // Сгенерировать $number случайных чисел от 1 до $count (количеств записей в таблице)
    $random = array();
    while (count($random) < $number ) {
        $r = rand(1, $count);
        if(array_search($r, $random) === false) $random[] = $r;
    }
    $random = implode(',', $random);
    

    И использовал их в запросе вот так:
    SET @r=0;
    SELECT *, @r:=@r+1 AS r FROM table1 HAVING r IN ($random)
    

    Выборка из 200 тис. записей у меня на ноуте проходит за 0.15 сек.
    • 0
      Этот способ вряд ли подойдёт если есть «дырки» в id (удалили, например)
      • 0
        А нельзя ли запросить у СУБД список всех ID и сформировать список случайных чисел с учётом этих дырок?
        Хотя по хорошему «монстр» это и делает, просто в СУБД, а не на стороне клиента.
      • 0
        Видимо вы не заметили, что выборка не по id, а по сгенерированным последовательным номерам.
        • 0
          да, точно
      • 0
        Ну, а что если его чуть дополнить? Берем, получаем айдишки отобранных записей. Если их меньше, чем нужное количество, то попали на дырки. Тогда передаем в функцию снова некие рендомные, но не равные отобранным, отобранные ранее в отборе уже не участвуют. И так до той поры, пока не наберем нужное число.
        • 0
          Когда будет происходить отбор id, все равно будет проход по таблице. Да и память для них придется выделить. В предложенном мной варианте всего один проход по таблице. Улучшить можно добавив LIMIT n, чтобы перебор прервался по достижению нужного количества записей.
    • 0
      Вопрос к тому, кто минусанул мой коммент с использованием последовательного счетчика и предварительно сгенерированных случайных номеров: можно узнать что именно вам не понравилось в таком решении?
  • 0
    Вся эта сложность связана с тем, что в PostgreSQL унифицирован процесс написания функций. И встроенные функции ни чем не отличаются в этом плане от пользовательских.
    Это не для всех очевидно, но следует отметить, что в данном способе происходит полная выборка из таблицы!
    И от этого, в принципе, уйти нельзя. Дело в том, что для выборки минимума и максимума СУБД выбирает все записи из таблицы, сравнивает их и определяет максимальную и минимальную. Да, — ему безразлично наличие индексов!
    И так со всеми агрегатными функциями.
    Поэтому в критичных местах, порою, выгоднее написать монструозные запросы, а порою и к information_schema, нежели писать «по-старинке».
    Те кто использует другие СУБД этого не поймут… как я им порою завидую… ))
    • 0
      ндааа, хабр конечно еще то болотце, читать надо сильно условного всё тут

      explain analyze
      select min(item_id), max(item_id) from items

      «Result (cost=0.29..0.29 rows=1 width=0) (actual time=0.045..0.046 rows=1 loops=1)»
      " InitPlan 1 (returns $0)"
      " -> Limit (cost=0.00..0.15 rows=1 width=8) (actual time=0.020..0.020 rows=1 loops=1)"
      " -> Index Only Scan using items_item_ux1_080914 on items (cost=0.00..61820478.54 rows=422748256 width=8) (actual time=0.018..0.018 rows=1 loops=1)"
      " Index Cond: (item_id IS NOT NULL)"
      " Heap Fetches: 0"
      " InitPlan 2 (returns $1)"
      " -> Limit (cost=0.00..0.15 rows=1 width=8) (actual time=0.018..0.019 rows=1 loops=1)"
      " -> Index Only Scan Backward using items_item_ux1_080914 on items (cost=0.00..61820478.54 rows=422748256 width=8) (actual time=0.016..0.016 rows=1 loops=1)"
      " Index Cond: (item_id IS NOT NULL)"
      " Heap Fetches: 1"
      «Total runtime: 0.071 ms»

      71 микросекунда

      100 микросекунд — можно 10 000 раз в секунду на одно ядре делать такой min max
    • 0
      www.sql.ru/forum/1126127/ocherednoy-velosipedist всем еще раз прочитать до конца!
      • 0
        Любопытное решение. Но обратите, пожалуйста, внимание на вот этот фрагмент
        WHERE id=(SELECT (min+range*random())::int) AND NOT id=ANY(res))

        или его аналог для оптимизированного случая
        WHERE id IN (SELECT (min+range*random())::int FROM generate_series(1,1000)) AND NOT id=ANY(res))

        Фактически это генерация id-шек для определённого диапазона (min-max). При упомянутом подходе существует только вероятность, но не гарантия, что полученное значение присутствует в таблице.

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

        Для некоторого класса задач такой подход оправдан. В моём случае, к сожалению, нет. Я скорее готов смириться с некоторой долей предопределённых и/или повторяющихся результатов, нежели с отсутствием оного результата.
        • 0
          там «зацикливание» сходится по четкой мат модели, для «больших» таблиц — попросту говоря его нет. посмотрите цифры по ссылке в примерах
          • +1
            Признаться, я в затруднении. Конечно же, со студенческих времён забылось многое (в т.ч. и по «вышке»), но почему-то думалось мне, что сходимость-то я могу обнаружить. Ан-нет. Вы утверждаете, что алгоритм сходится, т.е. имеет предел по времени выполнения и/или количеству итераций. Но, к стыду своему, я не вижу этого. Помогите, пожалуйста, найти ошибку в моих рассуждениях.

            Рассуждал же я следующим образом.

            Берём код запроса и строчка за строчкой смотрим, что происходит.
            смотреть код
            WITH RECURSIVE
            r AS (
                SELECT array[]::integer[] AS res,min(id) AS min, max(id)-min(id) AS range FROM table1
              UNION ALL
                SELECT res||ARRAY(SELECT id FROM table1 WHERE id IN (SELECT (min+range*random())::int FROM generate_series(1,1000)) AND NOT id=ANY(res)), min, range
                FROM r
                WHERE
                  coalesce(array_length(res,1),0)<1000
            )
            SELECT unnest(res) FROM (
              SELECT res FROM r ORDER BY array_length(res,1) DESC NULLS LAST LIMIT 1
            ) AS t LIMIT 1000;
            

            • Рекурсивный запрос — без этого никуда;
            • инициализируем переменные: под хранение результата, минимального и максимального значений а также, для удобства видимо, переменную хранящую диапазон между min-max значениями;
            • union — соединяем инициализацию и поиск значений;
            • собственно рабочий запрос (подробнее о нём ниже);
            • и, конечно-же, «выдача» результата;


            Суть алгоритма заключена в рабочем запросе. Т.е. вот в этом
            SELECT res||ARRAY(SELECT id FROM table1 WHERE id IN (SELECT (min+range*random())::int FROM generate_series(1,1000)) AND NOT id=ANY(res)), min, range
            FROM r
            WHERE coalesce(array_length(res,1),0)<1000
            

            Тут сказано следующее:
            1. случайным образом генерируем 1000 id в диапазоне min-max (generate_series(1,1000));
            2. из нужной таблицы (table1) выбираем id при условии, что эти id принадлежат последовательности, созданной на предыдущем этапе и их ещё не выбирали прежде;
            3. найденный результат поместить в переменную res;
            4. повторить, пока в res не наберётся 1000 записей.

            Если не ошибаюсь, то на шаге 3 в переменную res не будет помещено ничего (размер массива не изменится) если на шаге 2 ничего не было найдено.

            Поскольку мы имеем дело тут с непредсказуемым фактором (random()) то нужно рассматривать два сценария — оптимистический (он же позитивный) и пессимистический (он же негативный).

            Оптимистический
            На каждом шаге запрос находит минимум одну запись (в пределе — все записи находятся за один проход). Отлично, имеем упомянутые цифры
            … версия которая на коротких списках работает приблизительно так же как и предыдущая а вот на списках в 1000 случайных работает в 3 раза быстрее и главное требует на 3 порядка меньше памяти для работы (предыдущая версия требовала на 1000 случайных значений при 0.01 заполнении больше 200MB текущая в 1MB влезает и работает за 150ms)

            Пессимистический
            Что может пойти не так? Это же всё-таки случайность, random. Он может несколько раз (в пределе — постоянно в течении неограниченного времени) выдавать результат (генерировать id-шки), которых нет в таблице.

            Как такое может произойти? Очевидный ответ — лакуны, «дырки» в последовательности id. И это могут быть как дырки «естественного» (нет физически записей с такими-то значениями) или «искусственного» происхождения (дополнительные условия, которые накладываются на строки, подлежащие выборке).

            Всё? Не совсем. Запрос не «запоминает» ошибок, промахов. Т.е. вполне возможна ситуация, когда запрос начнёт «ходить кругами» (random будет генерировать повторяющиеся последовательности). В сочетании с вышеупомянутой особенностью это может привести к тому, что использование этого запроса, с точки зрения скорости выполнения, будет хуже решения «в лоб».

            Да, вероятность реализации худшего сценария очень низка. Но она не нулевая. При этом с увеличением частоты запросов всё чаще этот худший сценарий будет реализовываться. И мне очень не хочется, чтобы эта «особенность» («фича») всплыла на демонстрации продукта начальству/инвесторам/заказчикам/важному пользователю (нужное подчеркнуть).

            Выводы:
            • упомянутый алгоритм не имеет предела по времени выполнения/количеству итераций. Он работает за разумное/приемлемое/ограниченное время только с определённой, хотя и довольно большой, вероятностью;
            • при добавлении ограничения на количество итераций (времени выполнения) запрос не гарантирует возвращение какого-либо результата;
            • запрос не применим, для задач где нужно гарантировать получение результата за ограниченное количество времени, пусть и в ущерб равномерности распределения и/или неповторяемости;
            • запрос не применим для случаев, когда количество записей в таблице меньше требуемого (дополнительными условиями на получаемые строчки этого более чем просто получить);
  • 0
    На всякий случай оставлю это тут: различные способы выборки случайных данных в MySQL jan.kneschke.de/projects/mysql/order-by-rand/

    В своё время очень помогло.
  • 0
    www.sql.ru/forum/1126127/ocherednoy-velosipedist всем еще раз прочитать до конца!
    • 0
      А за что минус mtyurin? За пафос сообщения? Дык суть-то ссылки интересна! Вроде все взрослые люди, оставили бы на его совести) А вот энергию лучше направить на приглашение пользователя Maxim Boguk на Хабр — было бы больше пользы для дискуссии и всех заинтересованных темой.

      Ушел писать статью, чтобы заработать на инвайт))

      PS: на всякий случай — ничего, ни у кого не выпрашиваю
      • +2
        положительный рейтинг тут — это более подозрительно, чем наоборот. imho

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