Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 47
Великолепно! Схоронил себе, на случай, когда понадобится делать рандомные выборки.
Только я не понял почему Рекурсивный запрос с 2мя селектами внутри быстрее простого селекта. Order by такой тяжелый?
Только я не понял почему Рекурсивный запрос с 2мя селектами внутри быстрее простого селекта. Order by такой тяжелый?
Здесь есть более подробное рассмотрение данной ситуации, приём достаточно распостранённый: pgday.ru/files/pgmaster14/max.boguk.query.optimization.pdf
Если посмотреть план первого запроса, то становится все понятно.
'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 строк.
'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 строк.
А почему нельзя просто получить максимальный id, сгенерить 5 значений меньше этого значения и сделать 5 запросов вида:
SELECT * FROM ttbl WHERE id < my_generated_n LIMIT 1
и условия дополнительные легче вешать и запросов получиться на 1 больше но в разы более лёгких?
Или если есть возможность запихать всё в redis в виде множества idшников и выбирать с SRANDMEMBER? (так вообще очень быстро получится)
SELECT * FROM ttbl WHERE id < my_generated_n LIMIT 1
и условия дополнительные легче вешать и запросов получиться на 1 больше но в разы более лёгких?
Или если есть возможность запихать всё в redis в виде множества idшников и выбирать с SRANDMEMBER? (так вообще очень быстро получится)
много нюансов.
например при случае когда мы сгенерировали ..., 25, 29,…
а в базе есть только id = 24 в промежутке 20… 30 мы 2 раза получим одинаковое значение
+ если нам понадобится больше чем 5 значений время на получение данных будет расти.
например при случае когда мы сгенерировали ..., 25, 29,…
а в базе есть только id = 24 в промежутке 20… 30 мы 2 раза получим одинаковое значение
+ если нам понадобится больше чем 5 значений время на получение данных будет расти.
Как вариант создать таблицу в памяти из всех подходящих под условие id(id,t.id), а затем в ней чистым рандомом от размера выбирать. Достаточно лишь хранить где-то уже выбранные айдишники и в цикле получать новый пока он не будет не входящим в уже выбранные
А можно план выполнения вашего запроса посмотреть?
Да, конечно.
Правда план запроса под стать запросу. Я пытался его «раскурить», но потом решил что проще будет проверить экспериментально.
План запроса
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
Правда план запроса под стать запросу. Я пытался его «раскурить», но потом решил что проще будет проверить экспериментально.
В MSSQL насколько я знаю делают select top 100 * from [Table] order by NEWID()
Где NEWID() генерит новый случайный guid. Может и тут можно что-то такое сделать?
Где NEWID() генерит новый случайный guid. Может и тут можно что-то такое сделать?
А здесь разве не та же проблема? Выбрать все строки, отсортировать по случайному значению, вернуть 100 первых.
проще уж способ наподобие:
select * from table where random() < 0.01;
использовать
select * from table where random() < 0.01;
использовать
В MSSQL есть забавная конструкция TABLESAMPLE (вообще-то это ANSI SQL синтаксис):
Она выбирает случайные страницы данных (каждая по 8 Kb) и возвращает все строки с них, стараясь, чтобы всего получилось указанное число строк (ведь среднее число строк на странице сервер знает). Строки на страницах обычно упорядочены, в таком виде они и выводятся. Работает быстро, но результат удовлетворительный только на больших значениях — удобно задавать значения в процентах.
SELECT FirstName, LastName
FROM Person
TABLESAMPLE (100 ROWS) ;
Она выбирает случайные страницы данных (каждая по 8 Kb) и возвращает все строки с них, стараясь, чтобы всего получилось указанное число строк (ведь среднее число строк на странице сервер знает). Строки на страницах обычно упорядочены, в таком виде они и выводятся. Работает быстро, но результат удовлетворительный только на больших значениях — удобно задавать значения в процентах.
TABLESAMPLE (10 PERCENT)
А не проще сгенерировать некоторое ко-во случайный непересекающихся индексов и потом выбрать эти элементы из таблицы по порядковому номеру? Это же будет самое быстрое решение.
На 5+ миллионах записей еще интереснее.
random() — 12+ секунд
«монстр» — 62 мс
random() — 12+ секунд
«монстр» — 62 мс
А если 5 раз
SELECT * FROM table WHERE id not in(X1...Xn-1) LIMIT Xn,1?
Где Xn это случайное число от 1 до count(1)-n
n номер случайного числа.
SELECT * FROM table WHERE id not in(X1...Xn-1) LIMIT Xn,1?
Где Xn это случайное число от 1 до count(1)-n
n номер случайного числа.
Только что проверил.
Время выполнения одного запроса 2-14ms. Нужно их 10. При этом нужно учесть, что это только время на выполнения запроса в базе. Но будут ещё накладные расходы на доставку каждого ответа в приложение, обработку, формирование нового запроса…
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. При этом нужно учесть, что это только время на выполнения запроса в базе. Но будут ещё накладные расходы на доставку каждого ответа в приложение, обработку, формирование нового запроса…
А что-то типа
select * from my_table where id = random() limit 10
(с поправкой на синтаксис, конечно) в постгресе разве нельзя сделать? Спрашиваю, потому что не знаком с этой СУБД.
select * from my_table where id = random() limit 10
(с поправкой на синтаксис, конечно) в постгресе разве нельзя сделать? Спрашиваю, потому что не знаком с этой СУБД.
Из любопытства попробовал взять с запасом случайных id и выбрать по ним из базы.
Профит: простой SQL, и не сложный код.
Вот решение на groovy:
Недостаток этого решения, может ничего не найти, особенно на сильно разряженных таблицах.
Профит: простой 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}"
Недостаток этого решения, может ничего не найти, особенно на сильно разряженных таблицах.
Выборка случайных записей рациональным(!) способом — в любой СУБД несколько нетривиальная проблема.
Спасибо за пост!
Спасибо за пост!
Спасибо за линк. Возможно в той ветке форума и найдут лучшее решение. На это позволяет надеяться хотя бы тот факт, что один из вариантов решения уже упомянули.
Вот только приведённое решение нестабильно — зацикливается поскольку. Только что проверил на таблице с 4 строчками указав выбрать 3.
Но само направление поиска довольно интересное. Вероятно если вдумчиво «раскурить» приведённый запрос проблему с зацикливанием удастся обойти.
Вот эта версия работает на совершенно любом распределении и работает корректно.
Но на сильно разреженных таблицах конечно не быстрая:
тело запроса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.
Но само направление поиска довольно интересное. Вероятно если вдумчиво «раскурить» приведённый запрос проблему с зацикливанием удастся обойти.
При неравномерном распределении значений ID результирующая выборка также будет неравномерной
Что вернет «монстр» на маленькой таблице с ID вида (1,2,3,10000000,10000001, 10000002, 10000003)?
Что вернет «монстр» на маленькой таблице с ID вида (1,2,3,10000000,10000001, 10000002, 10000003)?
Промоделировал на firebird
Т.к. в Firebird нет массивов, заменил их строками с разделителем "~"
По-моему похоже
Проблемы этого метода очень хорошо видны на маленькой таблице
1) Если есть на пример ID = (1, 1000000000, 1000000001, 1000000002, 1000000003, 100000004) строки почти всегда в одном и том же порядке
2) Не инициализируется массив «а» он должен быть равен первому ID
Т.к. в 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
Спасибо, что указали на этот момент. Действительно при больших «дырках» в распределении значений ID время от времени будет возвращаться одна и та же последовательность. И хотя сейчас для моего случая это не критично, но вскоре нужно будет как-то этот вопрос решить.
Пока что хороших идей по этому поводу у меня нет. Из остальных — разве что разделить «primary key» и «sort key». После чего хранимыми процедурами поддерживать приемлемый уровень разрежённости «sort key».
Если бы дело было только в «primary key» — фиг бы с ним. Но нужно учитывать ещё и условия на остальных столбцах. А это уже дублирование логики приложения в СУБД, со всеми последствиями такого шага.
Пока что хороших идей по этому поводу у меня нет. Из остальных — разве что разделить «primary key» и «sort key». После чего хранимыми процедурами поддерживать приемлемый уровень разрежённости «sort key».
Если бы дело было только в «primary key» — фиг бы с ним. Но нужно учитывать ещё и условия на остальных столбцах. А это уже дублирование логики приложения в СУБД, со всеми последствиями такого шага.
В свое время подобную задачу в mySQL решил следующим образом. Сначала на PHP сгенерировал необходимое количество случайных чисел:
И использовал их в запросе вот так:
Выборка из 200 тис. записей у меня на ноуте проходит за 0.15 сек.
// Сгенерировать $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 сек.
Этот способ вряд ли подойдёт если есть «дырки» в id (удалили, например)
А нельзя ли запросить у СУБД список всех ID и сформировать список случайных чисел с учётом этих дырок?
Хотя по хорошему «монстр» это и делает, просто в СУБД, а не на стороне клиента.
Хотя по хорошему «монстр» это и делает, просто в СУБД, а не на стороне клиента.
Видимо вы не заметили, что выборка не по id, а по сгенерированным последовательным номерам.
Ну, а что если его чуть дополнить? Берем, получаем айдишки отобранных записей. Если их меньше, чем нужное количество, то попали на дырки. Тогда передаем в функцию снова некие рендомные, но не равные отобранным, отобранные ранее в отборе уже не участвуют. И так до той поры, пока не наберем нужное число.
Вопрос к тому, кто минусанул мой коммент с использованием последовательного счетчика и предварительно сгенерированных случайных номеров: можно узнать что именно вам не понравилось в таком решении?
Вся эта сложность связана с тем, что в PostgreSQL унифицирован процесс написания функций. И встроенные функции ни чем не отличаются в этом плане от пользовательских.
Это не для всех очевидно, но следует отметить, что в данном способе происходит полная выборка из таблицы!
И от этого, в принципе, уйти нельзя. Дело в том, что для выборки минимума и максимума СУБД выбирает все записи из таблицы, сравнивает их и определяет максимальную и минимальную. Да, — ему безразлично наличие индексов!
И так со всеми агрегатными функциями.
Поэтому в критичных местах, порою, выгоднее написать монструозные запросы, а порою и к information_schema, нежели писать «по-старинке».
Те кто использует другие СУБД этого не поймут… как я им порою завидую… ))
Это не для всех очевидно, но следует отметить, что в данном способе происходит полная выборка из таблицы!
И от этого, в принципе, уйти нельзя. Дело в том, что для выборки минимума и максимума СУБД выбирает все записи из таблицы, сравнивает их и определяет максимальную и минимальную. Да, — ему безразлично наличие индексов!
И так со всеми агрегатными функциями.
Поэтому в критичных местах, порою, выгоднее написать монструозные запросы, а порою и к information_schema, нежели писать «по-старинке».
Те кто использует другие СУБД этого не поймут… как я им порою завидую… ))
ндааа, хабр конечно еще то болотце, читать надо сильно условного всё тут
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
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
www.sql.ru/forum/1126127/ocherednoy-velosipedist всем еще раз прочитать до конца!
Любопытное решение. Но обратите, пожалуйста, внимание на вот этот фрагмент
или его аналог для оптимизированного случая
Фактически это генерация id-шек для определённого диапазона (min-max). При упомянутом подходе существует только вероятность, но не гарантия, что полученное значение присутствует в таблице.
Кроме того, в указанном примере отсутствует ограничение на количество итераций и, следовательно, сохраняется риск «зацикливания». Да, добавить ограничение не составляет проблемы. Однако при ограничении количества попыток «угадать ответ» существует не нулевой шанс, что этот запрос ничего не найдёт или найдёт меньше нужного количества записей.
Для некоторого класса задач такой подход оправдан. В моём случае, к сожалению, нет. Я скорее готов смириться с некоторой долей предопределённых и/или повторяющихся результатов, нежели с отсутствием оного результата.
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). При упомянутом подходе существует только вероятность, но не гарантия, что полученное значение присутствует в таблице.
Кроме того, в указанном примере отсутствует ограничение на количество итераций и, следовательно, сохраняется риск «зацикливания». Да, добавить ограничение не составляет проблемы. Однако при ограничении количества попыток «угадать ответ» существует не нулевой шанс, что этот запрос ничего не найдёт или найдёт меньше нужного количества записей.
Для некоторого класса задач такой подход оправдан. В моём случае, к сожалению, нет. Я скорее готов смириться с некоторой долей предопределённых и/или повторяющихся результатов, нежели с отсутствием оного результата.
там «зацикливание» сходится по четкой мат модели, для «больших» таблиц — попросту говоря его нет. посмотрите цифры по ссылке в примерах
Признаться, я в затруднении. Конечно же, со студенческих времён забылось многое (в т.ч. и по «вышке»), но почему-то думалось мне, что сходимость-то я могу обнаружить. Ан-нет. Вы утверждаете, что алгоритм сходится, т.е. имеет предел по времени выполнения и/или количеству итераций. Но, к стыду своему, я не вижу этого. Помогите, пожалуйста, найти ошибку в моих рассуждениях.
Рассуждал же я следующим образом.
Берём код запроса и строчка за строчкой смотрим, что происходит.
Суть алгоритма заключена в рабочем запросе. Т.е. вот в этом
Тут сказано следующее:
Если не ошибаюсь, то на шаге 3 в переменную res не будет помещено ничего (размер массива не изменится) если на шаге 2 ничего не было найдено.
Поскольку мы имеем дело тут с непредсказуемым фактором (random()) то нужно рассматривать два сценария — оптимистический (он же позитивный) и пессимистический (он же негативный).
Оптимистический
На каждом шаге запрос находит минимум одну запись (в пределе — все записи находятся за один проход). Отлично, имеем упомянутые цифры
Пессимистический
Что может пойти не так? Это же всё-таки случайность, random. Он может несколько раз (в пределе — постоянно в течении неограниченного времени) выдавать результат (генерировать id-шки), которых нет в таблице.
Как такое может произойти? Очевидный ответ — лакуны, «дырки» в последовательности id. И это могут быть как дырки «естественного» (нет физически записей с такими-то значениями) или «искусственного» происхождения (дополнительные условия, которые накладываются на строки, подлежащие выборке).
Всё? Не совсем. Запрос не «запоминает» ошибок, промахов. Т.е. вполне возможна ситуация, когда запрос начнёт «ходить кругами» (random будет генерировать повторяющиеся последовательности). В сочетании с вышеупомянутой особенностью это может привести к тому, что использование этого запроса, с точки зрения скорости выполнения, будет хуже решения «в лоб».
Да, вероятность реализации худшего сценария очень низка. Но она не нулевая. При этом с увеличением частоты запросов всё чаще этот худший сценарий будет реализовываться. И мне очень не хочется, чтобы эта «особенность» («фича») всплыла на демонстрации продукта начальству/инвесторам/заказчикам/важному пользователю (нужное подчеркнуть).
Выводы:
Рассуждал же я следующим образом.
Берём код запроса и строчка за строчкой смотрим, что происходит.
смотреть код
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
Тут сказано следующее:
- случайным образом генерируем 1000 id в диапазоне min-max (generate_series(1,1000));
- из нужной таблицы (table1) выбираем id при условии, что эти id принадлежат последовательности, созданной на предыдущем этапе и их ещё не выбирали прежде;
- найденный результат поместить в переменную res;
- повторить, пока в res не наберётся 1000 записей.
Если не ошибаюсь, то на шаге 3 в переменную res не будет помещено ничего (размер массива не изменится) если на шаге 2 ничего не было найдено.
Поскольку мы имеем дело тут с непредсказуемым фактором (random()) то нужно рассматривать два сценария — оптимистический (он же позитивный) и пессимистический (он же негативный).
Оптимистический
На каждом шаге запрос находит минимум одну запись (в пределе — все записи находятся за один проход). Отлично, имеем упомянутые цифры
… версия которая на коротких списках работает приблизительно так же как и предыдущая а вот на списках в 1000 случайных работает в 3 раза быстрее и главное требует на 3 порядка меньше памяти для работы (предыдущая версия требовала на 1000 случайных значений при 0.01 заполнении больше 200MB текущая в 1MB влезает и работает за 150ms)
Пессимистический
Что может пойти не так? Это же всё-таки случайность, random. Он может несколько раз (в пределе — постоянно в течении неограниченного времени) выдавать результат (генерировать id-шки), которых нет в таблице.
Как такое может произойти? Очевидный ответ — лакуны, «дырки» в последовательности id. И это могут быть как дырки «естественного» (нет физически записей с такими-то значениями) или «искусственного» происхождения (дополнительные условия, которые накладываются на строки, подлежащие выборке).
Всё? Не совсем. Запрос не «запоминает» ошибок, промахов. Т.е. вполне возможна ситуация, когда запрос начнёт «ходить кругами» (random будет генерировать повторяющиеся последовательности). В сочетании с вышеупомянутой особенностью это может привести к тому, что использование этого запроса, с точки зрения скорости выполнения, будет хуже решения «в лоб».
Да, вероятность реализации худшего сценария очень низка. Но она не нулевая. При этом с увеличением частоты запросов всё чаще этот худший сценарий будет реализовываться. И мне очень не хочется, чтобы эта «особенность» («фича») всплыла на демонстрации продукта начальству/инвесторам/заказчикам/важному пользователю (нужное подчеркнуть).
Выводы:
- упомянутый алгоритм не имеет предела по времени выполнения/количеству итераций. Он работает за разумное/приемлемое/ограниченное время только с определённой, хотя и довольно большой, вероятностью;
- при добавлении ограничения на количество итераций (времени выполнения) запрос не гарантирует возвращение какого-либо результата;
- запрос не применим, для задач где нужно гарантировать получение результата за ограниченное количество времени, пусть и в ущерб равномерности распределения и/или неповторяемости;
- запрос не применим для случаев, когда количество записей в таблице меньше требуемого (дополнительными условиями на получаемые строчки этого более чем просто получить);
На всякий случай оставлю это тут: различные способы выборки случайных данных в MySQL jan.kneschke.de/projects/mysql/order-by-rand/
В своё время очень помогло.
В своё время очень помогло.
www.sql.ru/forum/1126127/ocherednoy-velosipedist всем еще раз прочитать до конца!
А за что минус mtyurin? За пафос сообщения? Дык суть-то ссылки интересна! Вроде все взрослые люди, оставили бы на его совести) А вот энергию лучше направить на приглашение пользователя Maxim Boguk на Хабр — было бы больше пользы для дискуссии и всех заинтересованных темой.
Ушел писать статью, чтобы заработать на инвайт))
PS: на всякий случай — ничего, ни у кого не выпрашиваю
Ушел писать статью, чтобы заработать на инвайт))
PS: на всякий случай — ничего, ни у кого не выпрашиваю
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Postgres. Выборка N случайных записей