Як змусити PostgreSQL вважати швидше


Джерело фотографії
Всі вміють рахувати, але не всі вміють рахувати швидко. У цій статті ми детально розглянемо методи оптимізації count PostgreSQL. Існують прийоми, які можуть дозволити прискорити підрахунок кількості рядків на порядки.
Якщо підходити до питання з усією серйозністю, необхідно виділити кілька варіантів count, у кожного з яких є власні методи. З чим потрібно буде визначитися:
  • чи потрібна точна кількість рядків або оцінного значення буде достатньо;
  • слід враховувати дублікати або цікавлять тільки унікальні значення;
  • потрібно порахувати всі рядки таблиці або необхідно вибрати тільки задовольняють певній умові.
Ми проаналізуємо рішення для кожної конкретної ситуації, а також порівняємо їх швидкість і споживання ресурсів. Розібравши ситуацію з централізованої БД, ми скористаємося Citus, щоб продемонструвати паралельне виконання count в розподіленій базі даних.
Зміст

Підготовка БД

Для тестів ми будемо використовувати базу даних під назвою count, для якої ініціалізований pgbench:
[user@comp ~]$ pgbench -i count

Створимо тестову таблицю:
-- створюємо мільйон випадкових чисел і рядків
CREATE TABLE items AS
SELECT
(random()*1000000)::AS integer n,
md5(random()::text) AS s
FROM
generate_series(1,1000000);

-- інформуємо планувальник про зміну розміру великий таблиці
VACUUM ANALYZE;

Count з дублікатами

Точний підрахунок
Отже, почнемо з початку: розглянемо отримання точної кількості рядків всієї таблиці або її частини з дублікатами — старий добрий
count(*)
. Час виконання цієї команди дасть нам базис для оцінки швидкості роботи інших методів підрахунку кількості рядків.
Pgbench — зручний інструмент для багаторазового виконання запиту і збору статистики продуктивності.
# Усі приклади виконувалися на PostgreSQL 9.5.4

echo "SELECT count(*) FROM items;" | pgbench -d count -t 50 -P 1 -f -

# average 84.915 ms
# stddev 5.251 ms

Зауваження з приводу
count(1)
vs
count(*)
. Можна подумати, що
count(1)
швидше, оскільки
count(*)
має обробити значення всіх стовпчиків поточного рядка. Насправді вірно зворотне. На відміну від конструкції
SELECT *
, символ «зірочка» в
count(*)
нічого не означає. PostgreSQL обробляє вираз
count(*)
як особливий випадок count без аргументів. (Правильно було б записувати цей вираз у вигляді
count()
). З іншого боку,
count(1)
приймає один аргумент, і PostgreSQL має для кожного рядка переконатися, що цей аргумент (1) і справді не є NULL.
Попередній тест з
count(1)
видав наступні результати:
# average 98.896 ms
# stddev 7.280 ms

У будь-якому випадку і
count(1)
та
count(*)
за визначенням повільні. Щоб забезпечити несуперечність одночасно виконуваних транзакцій, PostgreSQL використовує управління паралельним доступом за допомогою мультиверсионности (MVCC, Multiversion Concurrency Control). Це означає, що кожна транзакція може бачити різні рядки і навіть різну кількість рядків таблиці. Тому не існує єдино правильного значення кількості рядків, яке СУБД могла б помістити в кеш, і систему доведеться сканувати всі рядки, щоб підрахувати, які з них видно окремої транзакції. Час виконання точного (exact) count лінійно зростає слідом за збільшенням розміру таблиці.
EXPLAIN SELECT count(*) FROM items;

Aggregate (cost=20834.00..20834.01 rows=1 width=0)
-> Seq Scan on items (cost=0.00..18334.00 rows=1000000 width=0)

scan припадає 88% вартості запиту. Якщо подвоїти розмір таблиці, то і час виконання запиту збільшиться приблизно в два рази при пропорційному зростанні вартості scan і aggregate.
Кількість рядків Середній час
1 млн 85 мс
2 млн 161 мс
4 млн 343 мс
Як це прискорити? Є два варіанти: вирішити, що нам достатньо оцінного значення, або самостійно поміщати в кеш кількість рядків. У другому випадку нам доведеться окремо зберігати значення для кожної таблиці і кожного виразу WHERE, для яких ми хочемо швидко виконувати count.
Давайте розглянемо приклад ручного кешування значення
count(*)
для таблиці
items
. Наступне засноване на тригерах рішення є адаптацією методу, запропонованого A. Elein Mustain. Механізм MVCC PostgreSQL буде підтримувати узгодженість між
items
та таблицею, що містить значення кількості рядків.
BEGIN;

CREATE TABLE row_counts (
relname text PRIMARY KEY,
reltuples bigint
);

-- проинициализируем таблицю поточним значенням кількості рядків
INSERT INTO row_counts (relname, reltuples)
VALUES ('items', (SELECT count(*) from items));

CREATE OR REPLACE FUNCTION adjust_count()
RETURNS TRIGGER AS
$$
DECLARE
BEGIN
IF TG_OP = 'INSERT' THEN
EXECUTE 'UPDATE row_counts set reltuples=reltuples +1 where relname = "' || TG_RELNAME || "";
RETURN NEW;
ELSIF TG_OP = 'DELETE' THEN
EXECUTE 'UPDATE row_counts set reltuples=reltuples -1 where relname = "' || TG_RELNAME || "";
RETURN OLD;
END IF;
END;
$$
LANGUAGE 'plpgsql';

CREATE TRIGGER items_count INSERT BEFORE OR DELETE items ON
FOR EACH ROW EXECUTE PROCEDURE adjust_count();

COMMIT;

Швидкість читання і оновлення кешированных значень в цьому випадку не залежить від розміру таблиці, і отримання значення кількості рядків виконується дуже швидко. Проте ця техніка збільшує накладні витрати на операції вставки та видалення. Без тригера наступна команда виконується 4,7 секунди, коли вставка з тригером п'ятдесят разів повільніше:
INSERT INTO items (n, s)
SELECT
(random()*1000000)::AS integer n,
md5(random()::text) AS s
FROM generate_series(1,1000000);

Оцінка
Оцінка всієї таблиці
Підхід, при якому ми кешируем кількість рядків таблиці, уповільнює операції вставки. Якщо замість точного числа ми готові задовольнятися оцінним значенням, то є можливість отримати швидкі операції читання без погіршення часу роботи вставки. Для цього ми можемо використовувати зібрані PostgreSQL службові дані. Їх джерелами є stats collector і autovacuum daemon.
Варіанти отримання оціночних значень:
-- Запитуємо у "stats collector"
SELECT n_live_tup
FROM pg_stat_all_tables
WHERE relname = 'items';

-- Оновлено VACUUM і ANALYZE
SELECT reltuples
FROM pg_class
WHERE relname = 'items';

Але є і більш надійний джерело, дані в якому оновлюються частіше. Andrew Gierth (RhodiumToad) радить:
Пам'ятайте: планувальник насправді не використовує reltuples; він примножує відношення reltuples/relpages на поточний кількість сторінок.
Логіка тут така: у міру збільшення обсягу даних у таблиці середня кількість рядків, що поміщуються у фізичну сторінку, в загальному випадку змінюватиметься не так сильно, як їх загальна кількість. Щоб отримати більш точну оцінку поточного кількості рядків, ми можемо помножити середню кількість рядків на актуальну інформацію про поточний кількості займаних таблицею сторінок.
-- pg_relation_size і block_size містять найсвіжішу інформацію,
-- тому їх можна використовувати разом з оцінкою
-- середньої кількості рядків на сторінку
SELECT
(reltuples/relpages) * (
pg_relation_size('items') /
(current_setting('block_size')::integer)
)
FROM pg_class where relname = 'items';

Оцінка для вибірки
У попередньому розділі ми розглянули отримання оціночної кількості рядків для цілої таблиці, а чи можна зробити те ж саме, але тільки для підходящих під умову
WHERE
рядків? Michael Fuhr придумав цікавий спосіб: запустити
EXPLAIN
для запиту і проаналізувати отриманий результат.
CREATE FUNCTION count_estimate(query text) RETURNS integer AS $$
DECLARE
rec record;
rows integer;
BEGIN
FOR rec IN EXECUTE 'EXPLAIN' || query LOOP
rows := substring(rec."QUERY PLAN" FROM ' rows=([[:digit:]]+)');
EXIT WHEN rows IS NOT NULL;
END LOOP;
RETURN rows;
END;
$$ LANGUAGE plpgsql VOLATILE STRICT;

Цю функцію можна використовувати наступним чином:
SELECT count_estimate('SELECT 1 FROM items WHERE n < 1000');

Точність цього методу залежить від планувальника, який використовує різні способи для оцінки вибірковості вираження
WHERE
, і від того, звідки може бути отримано кількість повернутих запитом рядків.

Distinct сount (без дублікатів)

Точний підрахунок
Поведінка за умовчанням при нестачі пам'яті
Count з дублікатами може виконуватись повільно, але count distinct набагато гірше. З обмеженою робочої пам'яттю і без індексів PostgreSQL не здатна виконувати оптимізацію ефективно. У конфігурації за замовчуванням СУБД накладає жорсткий ліміт на кожен паралельний запит (
work_mem
). На комп'ютері, який я використовую для розробки, це значення за замовчуванням було встановлено в 4 мегабайта.
Давайте оцінимо продуктивність роботи з мільйоном рядків на заводських налаштуваннях
work_mem
.
echo "SELECT count(DISTINCT n) items FROM;" | pgbench -d count -t 50 -P 1 -f -

# average 742.855 ms
# stddev 21.907 ms

echo "SELECT count(DISTINCT s) FROM items;" | pgbench -d count -t 5 -P 1 -f -

# average 31747.337 ms
# stddev 267.183 ms

Запуск
EXPLAIN
показує, що більша частина часу виконання запиту пішла на агрегування. Також відзначимо, що підрахунок кількості рядків по колонці типу text ведеться значно повільніше, ніж на цілочисельний:

-- план для колонки типу "integer", n

Aggregate (cost=20834.00..20834.01 rows=1 width=4) (actual time=860.620..860.620 rows=1 loops=1)
Output: count(DISTINCT n)
Buffers: shared hit=3904 read=4430, temp read=1467 written=1467
-> Seq Scan on public.items (cost=0.00..18334.00 rows=1000000 width=4) (actual time=0.005..107.702 rows=1000000 loops=1)
Output: n, s
Buffers: shared hit=3904 read=4430

-- план для колонки типу "text", s

Aggregate (cost=20834.00..20834.01 rows=1 width=33) (actual time=31172.340..31172.340 rows=1 loops=1)
Output: count(DISTINCT s)
Buffers: shared hit=3936 read=4398, temp read=5111 written=5111
-> Seq Scan on public.items (cost=0.00..18334.00 rows=1000000 width=33) (actual time=0.005..142.276 rows=1000000 loops=1)
Output: n, s
Buffers: shared hit=3936 read=4398

Що ж відбувається всередині "aggregate"? Опис цієї процедури виведення
EXPLAIN
непрозоро. Розібратися в ситуації допомагає аналіз схожого запиту. Замінимо
count distinct
на
select distinct
.

EXPLAIN (ANALYZE, VERBOSE) SELECT DISTINCT n items FROM;

Unique (cost=131666.34..136666.34 rows=498824 width=4) (actual time=766.775..1229.040 rows=631846 loops=1)
Output: n
-> Sort (cost=131666.34..134166.34 rows=1000000 width=4) (actual time=766.774..1075.712 rows=1000000 loops=1)
Output: n
Sort Key: items.n
Sort Method: external merge Disk: 13632kB
-> Seq Scan on public.items (cost=0.00..18334.00 rows=1000000 width=4) (actual time=0.006..178.153 rows=1000000 loops=1)
Output: n

В умовах недостатнього значення work_mem і відсутності зовнішніх структур даних (наприклад, індексів) PostgreSQL виконує merge-sort таблиці між пам'яттю і диском, а потім пробігає по результату, видаляючи дублікати, тобто діючи в чому аналогічно класичній Unix-комбінації
sort | uniq
.
Більшу частину часу виконання запиту займає сортування, особливо коли ми використовуємо не цілочисельну колонку
n
, а строкову
s
. Видалення дублікатів (unique filter) в обох випадках виконується приблизно з однаковою швидкістю.
Спеціалізоване агрегування
Для підрахунку кількості унікальних значень Thomas Vondra створив спеціалізований метод агрегування, що працює з типами обмеженої довжини (не повинна перевищувати 64 біта). Цей спосіб навіть без збільшення робочої пам'яті або створення індексів виявляється швидше за промовчанням методу, заснованого на сортування. Для установки виконайте наступні кроки:
  1. Створіть копію проекту tvondra/count_distinct.
  2. Перейдіть на стабільну гілку:
    git checkout REL2_0_STABLE
    .
  3. Запустіть
    make install
    .
  4. У вашій базі даних виконайте:
    CREATE EXTENSION. count_distinct;
    .
статті Томас пояснює, як працює агрегування. Коротко скажу лише, що його метод створює в пам'яті відсортований масив унікальних елементів, ущільнюючи його в процесі.
echo "SELECT COUNT_DISTINCT(n) items FROM;" | pgbench -d count -t 50 -P 1 -f -

# average 434.726 ms
# stddev 19.955 ms

Це працює швидше стандартного count distinct, який на наших тестових даних виконується в середньому 742 мс. Слід враховувати, що написані на C розширення, такі як count_distinct, не обмежені параметром work_mem, тому створений у процесі масив може зайняти більше пам'яті в розрахунку на з'єднання, ніж ви планували спочатку.
HashAggregate
Якщо всі пересчитываемые стовпці вміщаються в work_mem, для отримання унікальних значень PostgreSQL застосує хеш-таблицю:

SET work_mem='1GB';

EXPLAIN SELECT DISTINCT n items FROM;

HashAggregate (cost=20834.00..25822.24 rows=498824 width=4)
Group Key: n
-> Seq Scan on items (cost=0.00..18334.00 rows=1000000 width=4)

Це самий швидкий з розглянутих нами методів. Він виконується в середньому 372 мс
n
і 23 секунди для
s
. Запити
select distinct n
та
select count(distinct n)
будуть працювати приблизно однакову кількість часу за умови, що агрегування
count distinct
також застосує HashAggregate.
Будьте обережні: установка високого ліміту робочої пам'яті може призвести до неприємних наслідків, так як
work_mem
відноситься до кожного паралельного запитом. Крім того, ми можемо придумати і дещо краще.
Index-Only Scan
Ця можливість з'явилася в PostgreSQL 9.2. Якщо індекс містить всі необхідні для запиту дані, система може використовувати тільки його, не чіпаючи саму таблицю («the heap»). Тип індексу повинен підтримувати index-only scan (наприклад, btree). Індекси GiST і SP-GiST підтримують index-only scan лише для деяких класів операторів.
Створимо за btree-індексу для колонок
n
та
s
:
CREATE INDEX items_n_idx items ON USING btree (n);
CREATE INDEX items_s_idx items ON USING btree (s);

Для вибору унікальних значень цих колонок тепер використовується інша стратегія:

EXPLAIN SELECT DISTINCT n items FROM;

Unique (cost=0.42..28480.42 rows=491891 width=4)
-> Index Only Scan using items_n_idx on items (cost=0.42..25980.42 rows=1000000 width=4)

Але тут ми натрапляємо на дивну проблему:
SELECT COUNT(DISTINCT n) items FROM
не стане використовувати індекс, незважаючи на те, що
SELECT DISTINCT n
робить це за замовчуванням. Слідуючи радам у блогах («Трюк, який прискорить ваш postgres в 50x раз!»), можна дати підказку планувальником, переписавши
count distinct
у вигляді
count
подзапросу:
-- SELECT COUNT(DISTINCT n) items FROM;
-- повинен бути переписаний у вигляді

EXPLAIN SELECT COUNT(*)
FROM (SELECT DISTINCT n items FROM) t;

Aggregate (cost=34629.06..34629.07 rows=1 width=0)
-> Unique (cost=0.42..28480.42 rows=491891 width=4)
-> Index Only Scan using items_n_idx on items (cost=0.42..25980.42 rows=1000000 width=4)

Симетричний (in-order) обхід бінарного дерева виконується швидко. Цей запит займає в середньому 177 мс (270 мс для колонки
s
).
Примітка. Якщо значення work_mem достатньо для розміщення таблиці, PostgreSQL навіть при наявності індексу вибере HashAggregate. Виходить парадокс: виділення системі більшої кількості пам'яті може призвести до вибору гіршого плану запиту. Є можливість форсувати вибір index-only scan, встановивши
SET enable_hashagg=false;
, тільки не забудьте повернути його назад true, щоб не зіпсувати плани інших запитів.
Оцінка
HyperLogLog
Розглянуті раніше методи залежать від індексів, хеш-таблиць, відсортованих масивів у пам'яті або звертаються до статистичних таблиць централізованої бази даних. Коли даних стає по-справжньому багато і/або вони розділяються між декількома вузлами розподіленої бази даних, ці методи перестають нас влаштовувати.
В цьому випадку на допомогу приходять імовірнісні структури даних, які здатні давати швидкі приблизні оцінки і добре розпаралелюються. Давайте випробуємо одну з таких структур на count distinct. Розглянемо механізм оцінки кількості елементів (cardinality estimator) під назвою HyperLogLog (HLL). Для представлення набору елементів він використовує невелику кількість пам'яті. Операція об'єднання в цьому механізмі працює без втрат, що дозволяє об'єднувати в довільні значення HLL, не втрачаючи точності оцінки кількості.
HLL використовує властивості «хороших» хеш-функцій, зокрема дистанцію між хешірованнимі значеннями. Функція, що рівномірно розподіляє значення, прагне розносити їх на максимально можливу відстань. У міру додавання нових хешів вільного місця стає менше, і елементи починають притискатися один до одного. Аналізуючи найменші відстані між хешірованнимі значеннями, алгоритм може оцінити найбільш ймовірна кількість вихідних елементів.
Давайте виміряємо швидкість. Спочатку встановимо розширення для PostgreSQL.
  1. Створіть копію проекту postgresql-hll.
  2. Запустіть
    make install
    .
  3. Створіть розширення hll у вашій базі даних:
    CREATE EXTENSION hll;
    .
HLL виконує швидке агрегування даних при послідовному скануванні таблиць (sequential scan):
EXPLAIN SELECT #hll_add_agg(hll_hash_integer(n)) items FROM;

Aggregate (cost=23334.00..23334.01 rows=1 width=4)
-> Seq Scan on items (cost=0.00..18334.00 rows=1000000 width=4)

Середня швидкість HLL при виконанні
count distinct
склала 239 мс по колонці
n
і 284 мс
s
. Вийшло трохи повільніше, ніж index-only scan на одному мільйоні записів. Справжня сила HLL проявляється за рахунок її асоціативних і комутативних операцій об'єднання, які проходять без втрат. Це означає, що вони можуть виконуватися паралельно і бути об'єднані для обчислення підсумкового результату.

Розпаралелювання

Програми, що збирають аналітику в реальному часі, такі як, наприклад, Google Analytics, активно використовують count, і ця операція добре распараллеливается. У цьому розділі ми виміряємо продуктивність декількох методів підрахунку кількості рядків на базі невеликого кластера Citus, розгорнутого в Citus Cloud.
Ідея в тому, щоб розгорнути вузли розподіленої бази даних на декількох машинах. На сайтах буде однакова схема, і кожен з них буде містити частину загального набору даних (shard). Підрахунок кількості рядків буде виконуватися паралельно, тобто одночасно на різних машинах.
Налаштування кластера
Для тесту ми зробимо лише невеликий кластер, оскільки наша мета — оцінити порівняльну продуктивність, а не отримати максимальну швидкість.
У Citus Cloud я зробив кластер з восьми машин, вибравши для кожної з них найслабшу з можливих конфігурацій. При бажанні відтворити цей приклад самостійно зареєструйтесь ось тут.
Після створення кластера я підключаюся до координуючої ноде для виконання SQL-запитів. Першим ділом створимо таблицю.
CREATE TABLE items (
n integer,
s text
);

В даний момент таблиця існує тільки в БД координатора. Нам потрібно розбити таблицю і розмістити її частини на робочих сайтах. Citus приписує кожен рядок до певного сегмента (shard) шляхом обробки значень у вибраній нами колонці для розподілу (distribution column). У прикладі нижче ми ставимо завдання розподілити майбутні рядки в таблиці items, використовуючи хеш-значень в колонці
n
для визначення приналежності до того або іншого сегменту.
SELECT master_create_distributed_table('items', 'n', 'hash');
SELECT master_create_worker_shards('items', 32, 1);

З допомогою координуючої ноди ми завантажимо випадкові дані сегменти БД. (Citus також підтримує MX, режим "без майстра" (masterless mode), який використовується для швидкого завантаження даних, але зараз він нас не цікавить).
Після отримання URL бази даних координатора кластера виконайте наступний код на комп'ютері з швидким мережевим з'єднанням. (Всі генеруються дані будуть передаватися по мережі з цієї машини, тому потрібна хороша швидкість.)
cat << EOF > randgen.sql
COPY (
SELECT
(random()*100000000)::AS integer n,
md5(random()::text) AS s
FROM
generate_series(1,100000000)
) TO STDOUT;
EOF

psql $CITUS_URL -q -f randgen.sql | \
psql $CITUS_URL -c "COPY items (n, s) FROM STDIN"

У прикладі з централізованою базою даних ми використовували мільйон рядків. На цей раз давайте візьмемо сто мільйонів.
Точний підрахунок
З дублікатами
Звичайний count (без дублікатів) проблем не доставляє. Координатор виконує запит на всіх вузлах, а потім підсумовує результати. Висновок
EXPLAIN
показує план, обраний на одному з робочих вузлів («Distributed Query») і план, обраний на координаторові («Master Query»).
EXPLAIN VERBOSE SELECT count(*) FROM items;

Distributed Query into pg_merge_job_0003
Executor: Real-Time
Task Count: 32
Tasks Shown: One of 32
-> Task
Node: host=*** port=5432 dbname=citus
-> Aggregate (cost=65159.34..65159.35 rows=1 width=0)
Output: count(*)
-> Seq Scan on public.items_102009 items (cost=0.00..57340.27 rows=3127627 width=0)
Output: n, s
Master Query
-> Aggregate (cost=0.00..0.02 rows=1 width=0)
Output: (sum(intermediate_column_3_0))::bigint
-> Seq Scan on pg_temp_2.pg_merge_job_0003 (cost=0.00..0.00 rows=0 width=0)
Output: intermediate_column_3_0

Для довідки: на нашому кластері цей запит виконується 1,2 секунди. Distinct count представляє серйозну проблему при роботі з розподіленої БД.
Distinct (без дублікатів)
Трудність у підрахунку унікальних значень колонки в розподіленій базі даних полягає в тому, що дублікати треба шукати на різних вузлах. Однак це проблема, якщо вважати значення у колонці для розподілу (distribution column). Рядки з однаковими значеннями в цій колонці потраплять в один сегмент, що дозволить уникнути міжсегментного дублювання.
Citus знає, що для підрахунку унікальних значень в колонці розподілу (distribution column) потрібно виконати запит
count distinct
на кожному вузлі і скласти результати. Наш кластер виконує цю задачу за 3,4 секунди.
Знайти кількість унікальних значень у звичайній колонці (non-distribution) виявляється більш складним завданням. Логічно можна виділити дві можливості:
  1. Копіювати всі рядки на координуючий вузол і порахувати там.
  2. Перерозподілити рядки між робочими вузлами, не допускаючи попадання однакових значень у різні сегменти, і після цього виконувати підрахунок унікальних значень так само, як і для колонки, по якій ведеться розподіл.
Перший варіант нічим не краще підрахунку в централізованої БД. Фактично це в точності те ж саме плюс значні накладні витрати на передачу даних по мережі.
Другий варіант називається «перерозподіл» (repartitioning). Ідея полягає в тому, щоб, використовуючи колонку для розподілу, створити на робочих вузлах тимчасові таблиці. Робочі вузли посилають один одному рядки для запису в тимчасові таблиці, виконують запит і видаляють ці таблиці. У кожній СУБД своя логіка реалізації перерозподілу. Деталі цієї системи в Citus виходять за рамки даної статті, тому ми не будемо в них заглиблюватися.
Оцінка без дублікатів
Механізми оцінки потужності, такі як HLL, незамінні в розподілених базах даних. Вони дозволяють виконувати підрахунок унікальних значень навіть за звичайним колонках (non-distribution), створюючи при цьому лише невелику додаткову навантаження на мережу. Тип даних HLL має невеликий розмір в байтах і може швидко пересилатися від робочих вузлів координатору. Оскільки операція об'єднання в HLL виконується без втрат, немає необхідності хвилюватися, що кількість сегментів бази може вплинути на точність.
У Citus немає необхідності явно викликати функції postgresql-hll. Просто встановіть citus.count_distinct_error_rate ненульове значення, і Citus перепише плани запитів count distinct з використанням HLL. Наприклад:
SET citus.count_distinct_error_rate = 0.005;
EXPLAIN VERBOSE SELECT count(DISTINCT n) items FROM;

Distributed Query into pg_merge_job_0090
Executor: Real-Time
Task Count: 32
Tasks Shown: One of 32
-> Task
Node: host=*** port=5432 dbname=citus
-> Aggregate (cost=72978.41..72978.42 rows=1 width=4)
Output: hll_add_agg(hll_hash_integer(n, 0), 15)
-> Seq Scan on public.items_102009 items (cost=0.00..57340.27 rows=3127627 width=4)
Output: n, s
Master Query
-> Aggregate (cost=0.00..0.02 rows=1 width=0)
Output: (hll_cardinality(hll_union_agg(intermediate_column_90_0)))::bigint
-> Seq Scan on pg_temp_2.pg_merge_job_0090 (cost=0.00..0.00 rows=0 width=0)
Output: intermediate_column_90_0

Запит відпрацював швидко: 3,2 секунди для колонки
n
і 3,8 секунди для рядковій
s
. І це на 100 мільйонів записів і звичайних (non-distribution) колонках! HLL — відмінний інструмент для горизонтального масштабування процедури підрахунку унікальних значень в розподіленій базі даних.

Підсумки

Метод Час/1 млн рядків Точні Фильтруемости Унікальні
PG Stats 0,3 мс
Парсинг EXPLAIN 0,3 мс +
Ручне кешування 2 мс (але повільна вставка) +
count(*) 85 мс + +
count(1) 99 мс + +
Index Only Scan 177 мс + + +
HLL 239 мс + +
HashAgg 372 мс + + +
Custom Agg 435 мс (колонка 64-bit) + + +
Mergesort 742 мм + + +
Трохи програючи index-only scan в централізованій базі даних на таблиці з мільйоном рядків, HyperLogLog (HLL) виривається вперед на великих обсягах даних (> 100 Гб). Цей метод також незамінний в розподілених БД, дозволяючи отримати оцінку кількості унікальних елементів (distinct count) у реальному часі на величезних обсягів даних.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.