Во время работы над одним проектом возникла необходимость написать какую-то тестовую систему.
Задача была сформулирована примерно так:
- из N записей в базе данных необходимо выбрать m (3-5) случайных строк в серии из k выборок (чаще всего k=2).
Дубликатов быть не должно, выборка должна быть случайной.
Первое, что приходит на ум:
И это даже сработает. Вот только цена такого решения.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 (первичного ключа).
Таким образом, запрос затрагивает максимум N строк вместо полного перечисления содержимого таблицы.
Но «на бумаге все было гладко».
Когда я попытался использовать его «как есть» (с поправкой на имена таблиц/полей), всплыли «сюрпризы»:
- Массив в строке 4 создается пустым.
Из-за этого в окончательной выборке могут быть дубликаты.
Допустим, запрос в строках 4–7 возвращает id==5. После этого он обрабатывает запрос в СОЮЗ блок (строки 9-15) и на каком-то этапе возвращает тот же id==5, так как предыдущее значение id не было включено в массив " А " и проверка в строке 13 "t.id <> все(а)» прошло успешно;
- Количество выходных значений было не более заданного (п.
14).
Но легко меньше, чем это.
Даже если это количество было гарантировано в таблице.
Иногда возвращалась пустая выборка (количество значений «0»).
Как это: SELECT id, min, max, array[]::integer[] || id AS a, 0 AS n
Но второй момент заставил меня задуматься дважды.
Подвох был обнаружен в самом «сердце» алгоритма — выборке записи из диапазона.
Действительно, рекурсивный запрос пытается выбрать строку, для которой условие будет выполнено: id > min + (max - min) * 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 элементов, нужно исходить из наихудшего возможного сценария.
В данном случае это означает, что случайное N раз подряд вернет 1. Следовательно, вам необходимо знать/иметь N-1 значений до макс.
Как этого добиться в запросе? Альтернативный вариант — отсортировать все записи по идентификатору в порядке убывания и сдвинуть «вниз» на N строк.
А поскольку в строках 19 и 25 используется «> =", смещение можно указать на единицу меньше (N-1).
Это хорошо – основные трудности решены, а «мелочи» остались: запрос в нынешнем виде малопригоден.
Необходимо делать выбор с учетом определенных условий.
В простейшем случае исключить из выборки идентификаторы записей, выбранных на предыдущем этапе.
Кроме того, мы не можем исключить возможность использования каких-то дополнительных условий, налагаемых на строки таблицы (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}
Здесь в фигурных скобках указаны именованные параметры, подлежащие замене:
- {стол} — имя таблицы;
- {пк} — имя поля PrimaryKey;
- {поля} — список полей для выбора (также можно указать «*»);
- {исключать} — условие (совокупность условий) исключения записей из выборки.
Например, «t.id NOT IN (1,2,3,4)»;
- {предел} — количество записей в итоговой выборке
Для начала создадим таблицу, в которой будут проводиться эксперименты.
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;
Полученные результаты:
| Нет. | время, мс |
|---|---|
| 1 | 697 |
| 2 | 605 |
| 3 | 624 |
| 4 | 593 |
| 5 | 611 |
И вот – «монстр».
наблюдай за монстром 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
Полученные результаты:
| Нет. | время, мс |
|---|---|
| 1 | 15 |
| 2 | 17 |
| 3 | 8 |
| 4 | 12 |
| 5 | 12 |
* 15 мс.
В общей сложности разница составляет около полутора порядков (в 40-50 раз).
Оно того стоило.
Запросы проверялись, в том числе: и при «холодном» старте (после перезапуска машины/демона).
И хотя время выполнения в абсолютном выражении изменилось, соотношение осталось постоянным (насколько это возможно).
Те.
рекурсивный запрос всегда выполнялся в несколько десятков раз быстрее, чем прямое решение.
Примечания
*Примерно, поскольку точное значение не имеет значения из-за отклонений, вызванных кешем Postgres, влиянием операционной системы, оборудования, другого программного обеспечения и т. д. Теги: #postgres #случайная выборка #рекурсивные запросы #Высокая производительность #postgresql #программирование-
73% Американцев Не Слышали О Google Docs.
19 Oct, 24 -
Курс Интернет-Маркетинга Джереми Шумейкера
19 Oct, 24 -
Яндекс Научился Считать Деньги
19 Oct, 24
