Примеры многомерной статистики
Функциональные зависимости
Многомерную корреляцию можно продемонстрировать с помощью очень простого набора данных — таблицы с двумя столбцами, каждый из которых содержит одинаковые значения:
CREATE TABLE t (a INT, b INT);
INSERT INTO t SELECT i % 100, i % 100 FROM generate_series(1, 10000) s(i);
ANALYZE t;
Планировщик может определить мощность t, используя количество страниц и строк, полученных из pg_class:
SELECT relpages, reltuples FROM pg_class WHERE relname = 't';
relpages | reltuples
----------+-----------
45 | 10000
Распределение данных очень простое; в каждом столбце всего 100 различных значений, равномерно распределенных.
В следующем примере показан результат оценки условия WHERE по столбцу:
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a = 1;
QUERY PLAN
--------------------------------------------------------------------------------
Seq Scan on t (cost=0.00..170.00 rows=100 width=8) (actual rows=100 loops=1)
Filter: (a = 1)
Rows Removed by Filter: 9900
Планировщик исследует условие и определяет, что выборка этого предложения составляет 1%. Сравнивая эту оценку с фактическим количеством строк, мы видим, что оценка очень точная (фактически точная, поскольку таблица очень мала). Изменяя условие WHERE, чтобы использовать столбец b, генерируется идентичный план. Но посмотрите, что произойдет, если мы применим одно и то же условие к обоим столбцам, объединив их с AND:
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a = 1 AND b = 1;
QUERY PLAN
------------------------------------------------------------------------------
Seq Scan on t (cost=0.00..195.00 rows=1 width=8) (actual rows=100 loops=1)
Filter: ((a = 1) AND (b = 1))
Rows Removed by Filter: 9900
Планировщик оценивает избирательность каждого условия по отдельности, получая те же 1% оценки, что и выше. Затем он предполагает, что условия независимы, и поэтому он умножает их избирательность, получая окончательную оценку избирательности всего лишь 0.01%.. Это значительная недооценка, поскольку фактическое количество строк, соответствующих условиям (100), на два порядка выше.
Эту проблему можно решить, создав объект статистики, который направляет ANALYZE на вычисление многомерной статистики с функциональной зависимостью по двум столбцам:
CREATE STATISTICS stts (dependencies) ON a, b FROM t;
ANALYZE t;
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a = 1 AND b = 1;
QUERY PLAN
--------------------------------------------------------------------------------
Seq Scan on t (cost=0.00..195.00 rows=100 width=8) (actual rows=100 loops=1)
Filter: ((a = 1) AND (b = 1))
Rows Removed by Filter: 9900
Многомерные N-различия
Аналогичная проблема возникает при оценке мощности наборов из нескольких столбцов, таких как количество групп, которые будут генерироваться предложением GROUP BY. Когда GROUP BY перечисляет один столбец, n-значная оценка (которая видна как предполагаемое количество строк, возвращаемых узлом HashAggregate) очень точна:
EXPLAIN (ANALYZE, TIMING OFF) SELECT COUNT(*) FROM t GROUP BY a;
QUERY PLAN
------------------------------------------------------------------------------------------
HashAggregate (cost=195.00..196.00 rows=100 width=12) (actual rows=100 loops=1)
Group Key: a
-> Seq Scan on t (cost=0.00..145.00 rows=10000 width=4) (actual rows=10000 loops=1)
Но без многомерной статистики оценка количества групп в запросе с двумя столбцами в GROUP BY, как в следующем примере, отклоняется на порядок:
EXPLAIN (ANALYZE, TIMING OFF) SELECT COUNT(*) FROM t GROUP BY a, b;
QUERY PLAN
---------------------------------------------------------------------------------------------
HashAggregate (cost=220.00..230.00 rows=1000 width=16) (actual rows=100 loops=1)
Group Key: a, b
-> Seq Scan on t (cost=0.00..145.00 rows=10000 width=8) (actual rows=10000 loops=1)
Переопределяя объект статистики таким образом, чтобы он включал n-значные числа для двух столбцов, оценка значительно улучшается:
DROP STATISTICS stts;
CREATE STATISTICS stts (dependencies, ndistinct) ON a, b FROM t;
ANALYZE t;
EXPLAIN (ANALYZE, TIMING OFF) SELECT COUNT(*) FROM t GROUP BY a, b;
QUERY PLAN
---------------------------------------------------------------------------------------------
HashAggregate (cost=220.00..221.00 rows=100 width=16) (actual rows=100 loops=1)
Group Key: a, b
-> Seq Scan on t (cost=0.00..145.00 rows=10000 width=8) (actual rows=10000 loops=1)
Списки MCV
Как объясняется в разделе «Функциональные зависимости», функциональные зависимости являются очень дешевым и эффективным типом статистики, но их основным ограничением является их глобальный характер (отслеживание зависимостей осуществляется только на уровне столбцов, а не между значениями отдельных столбцов).
В этом разделе представлены многомерные варианты списков MCV (наиболее распространенных значений), которые являются простым расширением статистики по столбцам, описанной в разделе «Функциональные зависимости». Эта статистика решает эту проблему, храня отдельные значения, но, естественно, она стоит дороже, как с точки зрения построения статистики в ANALYZE, так и с точки зрения времени хранения и планирования.
Давайте снова рассмотрим запрос из раздела «Функциональные зависимости», но на этот раз со списком MCV, созданным на том же наборе столбцов (обязательно удалите функциональные зависимости, чтобы убедиться, что планировщик использует только что созданную статистику).
DROP STATISTICS stts;
CREATE STATISTICS stts2 (mcv) ON a, b FROM t;
ANALYZE t;
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a = 1 AND b = 1;
QUERY PLAN
--------------------------------------------------------------------------------
Seq Scan on t (cost=0.00..195.00 rows=100 width=8) (actual rows=100 loops=1)
Filter: ((a = 1) AND (b = 1))
Rows Removed by Filter: 9900
Оценка так же точна, как и в случае функциональных зависимостей, в основном благодаря тому, что таблица довольно мала и имеет простое распределение с небольшим количеством различных значений. Прежде чем рассматривать второй запрос, который не был особенно хорошо обработан функциональными зависимостями, давайте немного проверим список MCV.
Проверка списка MCV возможна с помощью функции pg_mcv_list_items, возвращающей набор:
SELECT m.* FROM pg_statistic_ext join pg_statistic_ext_data on (oid = stxoid),
pg_mcv_list_items(stxdmcv) m WHERE stxname = 'stts2';
index | values | nulls | frequency | base_frequency
-------+----------+-------+-----------+----------------
0 | {0, 0} | {f,f} | 0.01 | 0.0001
1 | {1, 1} | {f,f} | 0.01 | 0.0001
...
49 | {49, 49} | {f,f} | 0.01 | 0.0001
50 | {50, 50} | {f,f} | 0.01 | 0.0001
...
97 | {97, 97} | {f,f} | 0.01 | 0.0001
98 | {98, 98} | {f,f} | 0.01 | 0.0001
99 | {99, 99} | {f,f} | 0.01 | 0.0001
(100 rows)
Это подтверждает, что в двух столбцах есть 100 различных комбинаций, и все они примерно одинаково вероятны (частота 1% для каждого). Базовая частота — это частота, рассчитанная на основе статистики по столбцам, как если бы не было статистики по нескольким столбцам. Если бы в любой из столбцов были нулевые значения, это было бы определено в столбце нулевых значений.
Оценивая избирательность, планировщик применяет все условия к элементам в списке MCV, а затем суммирует частоты соответствующих элементов. Подробнее см. mcv_clauselist_selectivity в src/backend/statistics/mcv.c.
По сравнению с функциональными зависимостями списки MCV имеют два основных преимущества. Во-первых, список хранит фактические значения, что позволяет решить, какие комбинации совместимы:
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a = 1 AND b = 10;
QUERY PLAN
----------------------------------------------------------------------------
Seq Scan on t (cost=0.00..195.00 rows=1 width=8) (actual rows=0 loops=1)
Filter: ((a = 1) AND (b = 10))
Rows Removed by Filter: 10000
Во-вторых, списки MCV обрабатывают более широкий диапазон типов предложений, а не только предложения равенства, такие как функциональные зависимости. Например, рассмотрим следующий запрос диапазона для одной и той же таблицы:
EXPLAIN (ANALYZE, TIMING OFF) SELECT * FROM t WHERE a <= 49 AND b > 49;
QUERY PLAN
----------------------------------------------------------------------------
Seq Scan on t (cost=0.00..195.00 rows=1 width=8) (actual rows=0 loops=1)
Filter: ((a <= 49) AND (b > 49))
Rows Removed by Filter: 10000