Источник фотографии

Все умеют считать, но не все умеют считать быстро. В этой статье мы подробно рассмотрим методы оптимизации count в PostgreSQL. Существуют приемы, которые могут позволить ускорить подсчет количества строк на порядки.

Если подходить к вопросу со всей серьезностью, необходимо выделить несколько вариантов count, у каждого из которых есть собственные методы. С чем нужно будет определиться:

• требуется ли точное количество строк или оценочного значения будет достаточно;
• следует ли учитывать дубликаты или интересуют только уникальные значения;
• нужно ли посчитать все строки таблицы или необходимо выбрать только удовлетворяющие определенному условию.

Мы проанализируем решения для каждой конкретной ситуации, а также сравним их скорость и потребление ресурсов. Разобрав ситуацию с централизованной БД, мы воспользуемся Citus, чтобы продемонстрировать параллельное выполнение count в распределенной базе данных.

Содержание

• Подготовка БД
• Count с дубликатами
  
  • Точный подсчет
  • Оценка
    
    • Оценка по всей таблице
    • Оценка для выборки
• Distinct сount (без дубликатов)
  
  • Точный подсчет
    
    • Поведение по умолчанию при нехватке памяти
    • Специализированное агрегирование
    • HashAggregate
    • Index-Only Scan
  • Оценка
    
    • HyperLogLog
• Распараллеливание
  
  • Настройка кластера
  • Точный подсчет
    
    • С дубликатами
    • Distinct (без дубликатов)
  • Оценка без дубликатов
• Итоги

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

Для тестов мы будем использовать базу данных под названием count, для которой инициализирован pgbench:

[user@comp ~]$ pgbench -i count

Создадим тестовую таблицу:

-- создаем миллион случайных чисел и строк
CREATE TABLE items AS
  SELECT
    (random()*1000000)::integer AS 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 BEFORE INSERT OR DELETE ON items
  FOR EACH ROW EXECUTE PROCEDURE adjust_count();

COMMIT;

Скорость чтения и обновления кешированных значений в этом случае не зависит от размера таблицы, и получение значения количества строк выполняется очень быстро. Однако эта техника увеличивает накладные расходы на операции вставки и удаления. Без триггера следующая команда выполняется 4,7 секунды, когда как вставка с триггером в пятьдесят раз медленнее:

INSERT INTO items (n, s)
  SELECT
    (random()*1000000)::integer AS 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) FROM items;" | 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 FROM items;

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) FROM items;" | 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 FROM items;

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 ON items USING btree (n);
CREATE INDEX items_s_idx ON items USING btree (s);

Для выбора уникальных значений из этих колонок теперь используется другая стратегия:

EXPLAIN SELECT DISTINCT n FROM items;

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) FROM items не станет использовать индекс, несмотря на то что SELECT DISTINCT n делает это по умолчанию. Следуя советам в блогах («Трюк, который ускорит ваш postgres в 50x раз!»), можно дать подсказку планировщику, переписав count distinct в виде count по подзапросу:

-- SELECT COUNT(DISTINCT n) FROM items;
-- должен быть переписан в виде

EXPLAIN SELECT COUNT(*)
  FROM (SELECT DISTINCT n FROM items) 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)) FROM items;

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)::integer AS 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) FROM items;

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) в реальном времени на огромных объемах данных.