Многомерная корреляция может быть продемонстрирована с помощью очень простого набора данных — таблицы с двумя столбцами, содержащими одинаковые значения:

CREATE TABLE t (a INT, b INT);
INSERT INTO t SELECT i % 100, i % 100 FROM generate_series(1, 10000) s(i);
ANALYZE t;

Как объясняется в Раздел 14.2, планировщик может определить кардинальность t с использованием количества страниц и строк, полученных из pg_class:

SELECT relpages, reltuples FROM pg_class WHERE relname = 't';

 relpages | reltuples
----------+-----------
       45 |     10000

Распределение данных очень простое; в каждом столбце всего 100 различных значений, равномерно распределенных.

Следующий пример показывает результат оценки условия WHERE на столбце a:

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

Подобная проблема возникает при оценке кардинальности наборов из нескольких столбцов, таких как количество групп, которые будут сгенерированы с помощью 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)

Путем переопределения объекта статистики для включения подсчета количества уникальных значений для двух столбцов, оценка значительно улучшается:

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)

Как объясняется в Раздел 73.2.1, функциональные зависимости являются очень дешевым и эффективным типом статистики, но их основное ограничение заключается в их глобальной природе (отслеживание зависимостей только на уровне столбца, а не между отдельными значениями столбцов).

Этот раздел представляет многомерную вариацию списков MCV (наиболее часто встречающихся значений), простое расширение описанных в Раздел 73.1 статистик по столбцам. Эти статистики решают ограничение, храня индивидуальные значения, но это естественно более затратно, как с точки зрения построения статистики в ANALYZE, так и с точки зрения затрат на хранение и планирование.

Давайте рассмотрим запрос из Раздел 73.2.1 снова, но на этот раз с созданным списком 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% для каждой из них). Базовая частота - это частота, вычисленная на основе статистики по столбцам, как если бы не было многоколоночной статистики. Если бы в одном из столбцов были какие-либо пустые значения, это было бы указано в столбце nulls.

При оценке селективности планировщик применяет все условия к элементам списка 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