English version: Simple sample for Postgres and ruby.
Что интересного в статье:
- Пример быстрого псевдослучайного семплинга массивов в постгресе и руби.
- Сравнение различных реализаций сэмплирования массивов в постгресе и руби, с предложенным: Для постгреса на массивах в 1000 элементов в 6.5 раз быстрее комбинации order by random() ( в 15 раз на 10К элементах) и в 4 раз быстрее процентной выборки random() < 0.xx ( в 10 раз на 10К элементах ). Для руби на массивах от 2000 элементов и от 11 элементов в выборке — нарастающая разница в пользу предложенного варианта.
- Основной недостаток сэмплирования через TABLESAMPLE SYSTEM и SYSTEM_ROWS и как его преодолеть.
- Пример STABLE функции для построения псевдослучайной последовательности и почему это важно.
Выборка элементов
Задачи получения выборки от множества, встречаются сплошь и рядом в решении как прикладных так и системных задач.
Сэмплирование может быть последовательным — взять из множества M элементов подряд, и рандомизированным — получить из множества M случайных элементов. Пример для последовательного семплирования: разбивка длинных списков на страницы, пример рандомизированной выборки: сбор статистики по таблице для планировщика БД, для того чтобы планировать выполнение запроса нужно периодически проводить рандомизированное сэмплирование и по нему собирать статистику, на основе которой будет строиться план запроса.
Если получаемая выборка выводится пользователю без дополнительной обработки, то ее размеры не должны отклоняться от M, а сама выборка не должна содержать дубликатов.
Зафиксируем N для обозначения количества элементов множества, а M для количества элементов в выборке.
Выборка из M частей
Для создания псевдослучайной выборки из M элементов предлагается вариант, когда множество из N элементов разбивается на M частей и в каждой из этих M частей выбирается один случайный элемент.
Преимущества:
- выборка проходит в один проход, не нужны вложенные циклы для проверки на случай повторных выпаданий, так как M частей гарантировано не пересекаются.
- количество вызовов функции random или ее аналогов меньше количества элементов исходного множества, что очень существенно, если выборка M сильно меньше размеров множества N.
- количество элементов в выборке не может плавать и всегда соответствует указанному.
Недостатки:
- выборка является псевдослучайной и не дает всех возможных комбинаций M элементов из N. Количество комбинаций в случае полностью случайного выбора элементов будет соответствовать биноминальному коэффициенту N!/M!(N-M)!, предложенная псевдослучайная выборка даст нам в общем случае (N/M) в степени M вариантов. Например для случая когда M = 2, полное количество комбинаций = N*(N-1)/2 , для псевдослучайной выборки — N*N/4, т.е. чуть больше половины всех возможных вариантов.
- нужно знать исходные размеры множества, что не является обязательным в ряде реализации случайных выборок. Как-то: random_agg для одного элемента, процентные выборки типа TABLESAMPLE BERNOULLI или ее аналогов ( когда мы для каждого элемента кидаем монетку для определения его вхождения/невхождения в выборку ).
- M должно быть как миниммум не меньше N/2, а еще лучше в несколько раз меньше N, чем больше разница тем лучше.
Ruby
Давайте сравним текущую реализацию метода sample массива в руби и предложенный алгоритм.
Если глянуть в исходники можно вынести следующее: функция sample разбита на несколько частных случаев:M = 1, 2, 3, M ≤10, M=N и последний самый общий случай M > 10. Даже без практической проверки можно предположить, что тягаться с частными оптимизированными случаями, реализованными на языке С бесполезно, поэтому давайте посмотрим на случай “все остальное” т.е. случай когда M > 10, но в несколько раз меньше N.
Анализируя исходный код для этого случая ( см приложение, выделено жирным ), можно увидеть, что, несмотря на всю элегантность решения, происходит полное копирование исходного массива, а затем его обрезка до M нужных для выборки элементов. Ожидаемо, что с определенных размеров массива это будет тормозить исполнение функции и перерасходовать память.
Прикинем на практике чем как это будет соотноситься с такой реализацией:
class Array
def pseudo_random_sample(count)
result = Array.new(count)
piece_size = length / count
reminder = length - piece_size * count
count.times do |i|
result[i] = ( i < count - 1 ?
self[rand(piece_size) + i*piece_size] :
self[rand(piece_size + reminder) + i*piece_size] )
end
result
end
endПо результатам сравнения для 11 элементов рубежом на моей машине выступил размер массива в 2000 integer’ов (что составляет чуть больше 16кб памяти и соответствует 5 страницам памяти), примерно с этого размера нативная реализация сэмпла начинает проигрывать.
Пример сравнения производительности на выборке из 11 элементов на массиве из 100К элементов ( M = 11, N = 100K ).
Warming up --------------------------------------
.......................
Calculating -------------------------------------
classic 3.666k (± 4.8%) i/s - 18.564k in 5.07s
m-partial 192.859k (± 5.9%) i/s - 967.470k in 5.03s
m-partial+shuffle! 177.411k (± 5.2%) i/s - 893.048k in 5.04sComparison:
m-partial: 192859.0 i/s
m-partial+shuffle!: 177410.8 i/s - same-ish
classic: 3666.2 i/s - 52.60x slower
Как видно разница составила скромные 52 раза, конечно с ростом числа M это соотношение будет уменьшаться и для N = 100K сравняется в районе M ~ 700.
Если использовать выборки до 10 элементов включительно или массив меньше 2000 элементов, то разница между оригинальным методом на C и данной реализацией на руби будет ожидаемо не в пользу метода на руби, проигрыш составит где-то 2–3.5 раза в зависимости от размеров массива и выборки.
Если не устраивает, что выбранные элементы сохраняют свою очередность, можно сделать такой финт:
arr.random_sample(sample_size).shuffle!Это дополнительно перемешает полученные элементы, всего лишь за 29.99 :)! На самом деле примерно за ~ 5-10% потерю в производительности в зависимости от размеров выборки M, что и отражено в таблице в строке m-partial+shuffle!.
PostgreSQL sample для массивов.
Последовательная выборка
Напомню, что для получения последовательного семпла массива можно использовать конструкцию: [a:b], где a и b индексы в массиве, удовлетворяющие соотношению a ≤ b и лежащие в пределах индексов массива, по умолчанию нумерация начинается с 1.
Пример получения двух первых элементов массива user_ids:
SELECT user_ids[1:2] FROM docs LIMIT 1; user_ids
---------------
{70049,51869}
Случайная/псевдослучайная выборка
Встроенной функции на извлечение случайного сэмпла у массива нет. Дальше у нас есть два варианта: первый это вызвать unnest на массив и, получив набор записей, использовать подходы, которые используются для обычных таблиц или написать свой аналог такой функций. Давайте реализуем оба подхода и сравним производительность.
Построение случайной выборки для таблиц
Вот достаточно полный список вариантов сэмплирования таблиц, который можно составить поискав решение в интернете:
- TABLESAMPLE ( и его расширение tsm_system_rows)
- ORDER BY random() LIMIT M
- WHERE random() < 0.xx ( аналогично TABLESAMPLE BERNOULLI)
- +1 Indexed random value column
- Вариации на тему: WHERE id IN ( SELECT random() * id_max FROM generate_series(1, M) )
- Адаптация random_agg для выборки не одного, а M элементов ( это придется писать самостоятельно и обосновывать ).
Что для массивов не сработает:
TABLESAMPLE — невозможно использовать для массивов.
+1 Indexed random value column — тоже для работы с массивом не подходит.
Что сработает с массивами
ORDER BY random() LIMIT M Дает гарантированных M элементов, но производит при этом сортировку! Как правило такие решения получаются самыми медленными.
WHERE random() < M/N Не дает гарантированного количества строк, но исключает сортировку. Если необходимо гарантированное колличество строк, метод потребует дополнительного усложнения алгоритма, но он идеально подходит для минимальной оценки производительности алгоритмов, вызывающих функцию random() N раз. Таких как, например, random_agg, который помимо N вызовов random() будет содержать дополнительную логику, что в среднем увеличит время его исполнения.
Адаптация random_agg для варианта M > 1Можно заморочиться и переписать этот алгоритм для варианта с выборкой не одного, а M элементов, но для оценки производительности, как уже было сказано, достаточно ограничиться вышеописанным вариантом (= where random() < M/N), который будет гарантировано быстрее и даст оценку снизу для подобного решения.
SELECT arr[random() * arr_length] FROM generate_series(1, M). В частности его аналог предлагают в статье How To Sample Rows in SQL 273X Faster:
select * from users
where id in (
select round(random() * 21e6)::integer as id
from generate_series(1, 110) -- Preserve duplicates
)
limit 100У такого способа помимо проблемы повторов, которую пытаются вылечить, увеличив выборку на 10%, добавляется другая проблема: в случае неравномерного распределения id, могут быть не только повторы, но и недобор элементов, если было много удалений из таблицы.
Данный способ неплохо подойдет, если полученная выборка будет преобразовываться и анализироваться, но для непосредственной выдачи пользователю не годится, потому что будет скакать размер выборки, если же алгоритм доводить, то требуемое усложнение отрицательно скажется на его производительности и элегантности.
Сравнение производительности
Код функций:
-- order by random
CREATE OR REPLACE FUNCTION random_sample_obr( bigint[], int ) RETURNS TABLE (id bigint) AS $$
SELECT * FROM unnest($1) ORDER BY random() LIMIT $2;
$$ LANGUAGE SQL;-- less than random
CREATE OR REPLACE FUNCTION random_sample_lr( bigint[], int ) RETURNS TABLE (id bigint) AS $$
DECLARE
-- probability is same for all set, so it must be evaluated once
probability float := $2::float / cardinality($1);
BEGIN
RETURN QUERY SELECT * FROM unnest($1) WHERE random() < probability;
END
$$ LANGUAGE plpgsql;--generate series analogue
CREATE OR REPLACE FUNCTION random_sample_gs( arr bigint[], sample_size int ) RETURNS TABLE (id bigint) AS $$
DECLARE
arr_length int := cardinality(arr);
result bigint[];
BEGIN
FOR i IN 1..sample_size LOOP
result[i] = arr[floor(random()*arr_length)];
END LOOP;
END
$$ LANGUAGE plpgsql;--M-partial sample
CREATE OR REPLACE FUNCTION random_sample_mp( arr bigint[], sample_size int ) RETURNS bigint[] AS $$
DECLARE
result bigint[];
piece_size int := cardinality(arr) / sample_size;
reminder int := cardinality(arr) - piece_size * sample_size;
BEGIN
FOR i IN 1..sample_size LOOP
IF i = sample_size THEN
result[i] := arr[floor((piece_size + reminder)*random() + 1) +
(i-1)*piece_size];
ELSE
result[i] := arr[floor(piece_size*random() + 1) +
(i-1)*piece_size];
END IF;
END LOOP;
RETURN result;
END
$$ LANGUAGE plpgsql;
Статистика собрана по результатам 100 случайных запросов типа:
SELECT random_sample_XXX( user_ids, 5 ) as uid
FROM "cards"
-- 10 random ids from cards, generated outside time measurement
WHERE "cards"."id" IN (...)Изначально сравнение проводилось для нескольких размеров массивов (=N), для нескольких элементов из массива ( =M ), для случайно формируемых наборов из K элементов. Ожидаемо, что наибольшая зависимость оказалась от размеров массива: с ростом числа элементов в массивах, все остальные зависимости ушли на второй план, поэтому в результирующей таблице оставлена только зависимость от размеров массива.
Значения данных в колонке: время на получения сэмпла и во сколько раз оно хуже/лучше M-partial выборки для данной размерности.
Как видно только упрощенный до некорректности вариант с рандомным извлечением M элементов ( эквивалент generate_series ), опережает на малых размерах M-partial вариант. При этом с ростом массива разница в производительности между ними стремится к нулю, а вероятность получения совпадения одной и больше пары в выборке при использовании эквивалента generate_series, стремится к 1.
Sample from TABLESAMPLE
TABLESAMPLE SYSTEM и TABLESAMPLE SYSTEM_ROWS рекордсмены по производительности среди всех спобов сэмплирования на таблицах. Но оба эти варианта страдают от одного серьезного недостатка: выборка рандомизирована постранично, а не построково, поэтому при выдаче выборки с малым M легко получить последовательные наборы.
Например для таблицы с 1.1M записями, для такого запроса:
SELECT array_agg(id) FROM docs TABLESAMPLE SYSTEM_ROWS(5);Легко получить такие результаты:
{2083068,2083069,2083070,2083071,2083072}OR{1168539,1168541,1168542,1168547,1168551}
И это не совсем то, что хотелось получить от случайной выборки.
Но это легко исправить используя такой трюк:
SELECT random_sample(array_agg(id), 10)
FROM cards TABLESAMPLE SYSTEM(1);Супербыстрый, никакой пагинации, никаких дубликатов и плавающего размера выборки!
STABLE random_sample
В Postgres есть три способа декларирования функции: STABLE, IMMUTABLE и VOLATILE. По умолчанию функция попадает в категорию VOLATILE. Это означает что ее вызовы не могут быть оптимизированы планировщиком, что может приводить к весьма не ожиданным результатам.
Давайте рассмотрим такой запрос:
SELECT * FROM docs
JOIN users ON users.id = ANY( random_sample(user_ids, M) )
WHERE docs.id = ID;Желаемое и ожидаемое поведение однократный вызов функции random_sample, передача ее результатов для поиска все пользователей с такими ID. Но по умолчанию Postgres будет интерпретировать этот запрос как такой:
SELECT * FROM docs
JOIN users ON random()
WHERE docs.id = ID;И здесь очевидно мы вызовем random_sample для всех строк из таблицы users, все потому что random() объявлена как VOLATILE, что является значением по умолчанию в Postgres.
Можно декларировать VOLATILE функцию как STABLE, и планировщик скорее всего соптимизирует ее вызовы, например приведенный выше запрос сработает так как мы ожидаем: вызов ф-ии random_sample будет однократным. Скорее всего, не значит обязательно! Пытаться обмануть планировщик замаскировав VOLATILE функцию простым декларированием достаточно опасно.
Поэтому было бы удобно построить random() как по-настоящему STABLE функцию. В силу того что нам не нужна здесь криптографическая стойкость, мы можем использовать простой линейный конгруэнтный метод, например в такой реализации:
CREATE FUNCTION random_stable( prev bigint ) RETURNS int AS $$
BEGIN
RETURN (prev * 1103515245 + 12345) / 65536 % 32768;
END;
$$ LANGUAGE plpgsql IMMUTABLE;После этого все вызовы random() придется заменить на:
random_value := random_stable(random_value);Для того чтобы получить первый элемент последовательности воспользуемся другой STABLE функцией: current_timestam. Вот так:
random_value := random_stable( extract( microseconds FROM current_timestamp) );Теперь у нас есть случайная последовательность по-натсоящему стабильная в пределах транзакции и даже, если планировщик примет неожиданное решение конечный результат будет по-прежнему корректен.
Оптимизация на стыке ORM и БД
Есть еще несколько интересных решений для оптимизации на стыке ORM и БД: разворачивание цикла в один запрос для небольших М, прегенерация случайной последовательности на стороне ORM, а также использование исходного алгоритма на руби.
Начнем с последнего, как я уже упоминал: основная проблема сэмплинга, портящая элегантное решение на руби, это полное копирование массива для случая M > 10. Но внутри функции мы уже оперируем именно копией массива, и мы уже потратили время на его копирование и нам его не сэкономить, поэтому мы можем с копией делать что хотим, в том числе преобразовать согласно классическому алгоритму:
CREATE OR REPLACE FUNCTION random_sample_ruby_way( arr bigint[], sample_size int ) RETURNS bigint[] AS $$
DECLARE
current_rand bigint;
j int := 0;
arr_size int := cardinality(arr);
swapper bigint := 0;
BEGIN
current_rand := extract( milliseconds FROM current_timestamp)::int;
FOR i IN 1..sample_size LOOP
current_rand := random_stable(current_rand);
j := current_rand % ( arr_size - i ) + i;
swapper := arr[j];
arr[j] := arr[i];
arr[i] := swapper;
END LOOP;
RETURN arr[:sample_size];
END
$$ LANGUAGE plpgsql STABLE;В итоге у нас есть скорость M-partial решения без его проблем!
Теперь шагнем еще далье и избавимся от вызовов random() внутри функции, просто передав внутрь сгенерированную на стороне ORM псевдослучайную последовательность. Функция выше трансформируется, например, таким образом:
CREATE OR REPLACE FUNCTION random_sample_pregenerated_sequence( arr bigint[], random_arr int[] ) RETURNS bigint[] AS $$
DECLARE
j int := 0;
arr_size int := cardinality(arr);
sample_size int := cardinality(random_arr);
swapper bigint := 0;
BEGIN
FOR i IN 1..sample_size LOOP
j := random_arr[i] % ( arr_size - i ) + i;
swapper := arr[j];
arr[j] := arr[i];
arr[i] := swapper;
END LOOP;
RETURN arr[:sample_size];
END
$$ LANGUAGE plpgsql STABLE;Разворачивание M-Partial алгоритма в строку
Если массив маленький, то строка таблицы не будет “поджариваться” т.е. не становится TOASTed. В доках Postgres’а описаны условия, для которых запись начинает, поджариваться:
The TOAST management code is triggered only when a row value to be stored in a table is wider than
TOAST_TUPLE_THRESHOLDbytes (normally 2 kB).
Для массива данных bigint это ~ 250 элементов, с учетом того, что запись редко состоит только из одного массива и дополнительно содержит еще не только пользовательские данные, но и системные я бы обозначил эффективный рубеж сверхэффективно работы с массивами: 200 элементов.
Для такого случая супер быстро будет работать разворачивание цикла в строку запроса на стороне ORM:
SELECT *, ARRAY[
user_ids[30776 % (cardinality(user_ids)/M)],
user_ids[12021 % (cardinality(user_ids)/M) +
cardinality(user_ids) * i / M]
...
user_ids[5410 % (cardinality(user_ids)/M +
cardinality(user_ids) % M ) +
cardinality(user_ids) * (M-1)/ M]
] as sample
FROM docs;Конечно это будут уже достаточно уродливые запросы, но они вполне автоматизируемы.
Итоговая табличка различных реализаций с переводом главных конкурентов на STABLE реализации* и нормализованная по самому быстрому из них для каждого случая выглядит следующим образом**:
*ORDER BY random() и random() < M/N используют базовую реализацию.
**Вариант generate_series не совсем корректен и используется как маркер производительности.
Как видно для размеров меньше TOASTed разворачивание в строку M-partial алгоритма показывает супер быстрый результат даже на малых размерах массива. В остальном классическое корректное исполнение взятое из руби выглядит отличным компромисом между производительностью и корректностью. Для получения еще +50% ускорения можно использовать M-partial выборку, если полнота не обязательна.
Список литературы
- Return random, no-repeating rows from a table — PostgreSQL
- How To Sample Rows in SQL 273X Faster( не совсем корректный метод выборки случайных записей из таблицы + содержит еще одну маленькую ошибочку: ненужный group by )
- Tablesample In PostgreSQL 9.5 by 2ndQuadrant
- Tablesample and Other Methods for Getting Random Tuples by 2ndQuadrant
- Tablesample PG wiki
- Выборка одного случайного значения из массива в Postgres, answer by Erwin Brandstetter
- Random_agg — пример написания аггрегационной ф-ии для постгреса аггрегирующей одно случайное значение из выборки.
- Sampling in Postgres, answer by Erwin Brandstetter
- Одна из самых полных подборок вариантов построения рандомизированной выборки для Postgres.
- Еще одна мощная подборка с примерами реализаций, так же отличная подборка от Erwin Brandstetter
- Линейный конгруэнтный метод построения случайной последовательности.
- Ruby arr.sample
Приложение
Код реализации метода sample у массивов в руби:
static VALUE
rb_ary_sample(int argc, VALUE *argv, VALUE ary)
{
VALUE nv, result, *ptr;
VALUE opts, randgen = rb_cRandom;
long n, len, i, j, k, idx[10];
long rnds[numberof(idx)];
if (OPTHASH_GIVEN_P(opts)) {
randgen = rb_hash_lookup2(opts, sym_random, randgen);
}
ptr = RARRAY_PTR(ary);
len = RARRAY_LEN(ary);
if (argc == 0) {
if (len == 0) return Qnil;
if (len == 1) {
i = 0;
}
else {
i = RAND_UPTO(len);
if ((len = RARRAY_LEN(ary)) <= i) return Qnil;
ptr = RARRAY_PTR(ary);
}
return ptr[i];
}
rb_scan_args(argc, argv, "1", &nv);
n = NUM2LONG(nv);
if (n < 0) rb_raise(rb_eArgError, "negative sample number");
if (n > len) n = len;
if (n <= numberof(idx)) {
for (i = 0; i < n; ++i) {
rnds[i] = RAND_UPTO(len - i);
}
}
k = len;
len = RARRAY_LEN(ary);
ptr = RARRAY_PTR(ary);
if (len < k) {
if (n <= numberof(idx)) {
for (i = 0; i < n; ++i) {
if (rnds[i] >= len) {
return rb_ary_new2(0);
}
}
}
}
if (n > len) n = len;
switch (n) {
case 0:
return rb_ary_new2(0);
case 1:
i = rnds[0];
return rb_ary_new4(1, &ptr[i]);
case 2:
i = rnds[0];
j = rnds[1];
if (j >= i) j++;
return rb_ary_new3(2, ptr[i], ptr[j]);
case 3:
i = rnds[0];
j = rnds[1];
k = rnds[2];
{
long l = j, g = i;
if (j >= i) l = i, g = ++j;
if (k >= l && (++k >= g)) ++k;
}
return rb_ary_new3(3, ptr[i], ptr[j], ptr[k]);
}
if (n <= numberof(idx)) {
VALUE *ptr_result;
long sorted[numberof(idx)];
sorted[0] = idx[0] = rnds[0];
for (i=1; i<n; i++) {
k = rnds[i];
for (j = 0; j < i; ++j) {
if (k < sorted[j]) break;
++k;
}
memmove(&sorted[j+1], &sorted[j], sizeof(sorted[0])*(i-j));
sorted[j] = idx[i] = k;
}
result = rb_ary_new2(n);
ptr_result = RARRAY_PTR(result);
for (i=0; i<n; i++) {
ptr_result[i] = ptr[idx[i]];
}
}
else {
VALUE *ptr_result;
result = rb_ary_new4(len, ptr);
RBASIC(result)->klass = 0;
ptr_result = RARRAY_PTR(result);
RB_GC_GUARD(ary);
for (i=0; i<n; i++) {
j = RAND_UPTO(len-i) + i;
nv = ptr_result[j];
ptr_result[j] = ptr_result[i];
ptr_result[i] = nv;
}
RBASIC(result)->klass = rb_cArray;
}
ARY_SET_LEN(result, n);
return result;
}