La correlación multivariante se puede demostrar con un conjunto de datos muy simple — una tabla con dos columnas, ambas con los mismos valores:

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

Como se explica en la Section 14.2, el planificador puede determinar la cardinalidad de t utilizando el número de páginas y filas obtenidas de pg_class:

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

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

La distribución de los datos es muy simple; solo hay 100 valores distintos en cada columna, distribuidos uniformemente.

El siguiente ejemplo muestra el resultado de estimar una condición WHERE en la columna a:

EXPLAIN (ANALYZE, TIMING OFF, BUFFERS 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.00 loops=1)
   Filter: (a = 1)
   Rows Removed by Filter: 9900

El planificador examina la condición y determina que la selectividad de esta cláusula es del 1%. Al comparar esta estimación con el número real de filas, vemos que la estimación es muy precisa (de hecho exacta, ya que la tabla es muy pequeña). Al cambiar la condición WHERE para usar la columna b, se genera un plan idéntico. Pero observa qué sucede si aplicamos la misma condición en ambas columnas, combinándolas con AND:

EXPLAIN (ANALYZE, TIMING OFF, BUFFERS 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.00 loops=1)
   Filter: ((a = 1) AND (b = 1))
   Rows Removed by Filter: 9900

El planificador estima la selectividad para cada condición individualmente, llegando a las mismas estimaciones del 1% que arriba. Luego asume que las condiciones son independientes y, por lo tanto, multiplica sus selectividades, produciendo una estimación de selectividad final de solo el 0.01%. Esta es una subestimación significativa, ya que el número real de filas que coinciden con las condiciones (100) es dos órdenes de magnitud mayor.

Este problema se puede solucionar creando un objeto de estadísticas que indique a ANALYZE que calcule estadísticas multivariantes de dependencia funcional en las dos columnas:

CREATE STATISTICS stts (dependencies) ON a, b FROM t;
ANALYZE t;
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS 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.00 loops=1)
   Filter: ((a = 1) AND (b = 1))
   Rows Removed by Filter: 9900

Un problema similar ocurre con la estimación de la cardinalidad de conjuntos de múltiples columnas, como el número de grupos que se generarían por una cláusula GROUP BY. Cuando GROUP BY enumera una sola columna, la estimación del número de valores distintos (que es visible como el número estimado de filas devueltas por el nodo HashAggregate) es muy precisa:

EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT COUNT(*) FROM t GROUP BY a;
                                       QUERY PLAN
-----------------------------------------------------------------------------------------
 HashAggregate  (cost=195.00..196.00 rows=100 width=12) (actual rows=100.00 loops=1)
   Group Key: a
   ->  Seq Scan on t  (cost=0.00..145.00 rows=10000 width=4) (actual rows=10000.00 loops=1)

Pero sin estadísticas multivariantes, la estimación para el número de grupos en una consulta con dos columnas en GROUP BY, como en el siguiente ejemplo, tiene un error de un orden de magnitud:

EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT COUNT(*) FROM t GROUP BY a, b;
                                       QUERY PLAN
--------------------------------------------------------------------------------------------
 HashAggregate  (cost=220.00..230.00 rows=1000 width=16) (actual rows=100.00 loops=1)
   Group Key: a, b
   ->  Seq Scan on t  (cost=0.00..145.00 rows=10000 width=8) (actual rows=10000.00 loops=1)

Al redefinir el objeto de estadísticas para incluir recuentos de valores distintos (ndistinct) para las dos columnas, la estimación mejora considerablemente:

DROP STATISTICS stts;
CREATE STATISTICS stts (dependencies, ndistinct) ON a, b FROM t;
ANALYZE t;
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT COUNT(*) FROM t GROUP BY a, b;
                                       QUERY PLAN
--------------------------------------------------------------------------------------------
 HashAggregate  (cost=220.00..221.00 rows=100 width=16) (actual rows=100.00 loops=1)
   Group Key: a, b
   ->  Seq Scan on t  (cost=0.00..145.00 rows=10000 width=8) (actual rows=10000.00 loops=1)

Como se explica en la Section 69.2.1, las dependencias funcionales son un tipo de estadísticas muy económico y eficiente, pero su principal limitación es su naturaleza global (solo rastrean dependencias a nivel de columna, no entre valores individuales de columna).

Esta sección introduce la variante multivariante de las listas MCV (valores más comunes), una extensión directa de las estadísticas por columna descritas en la Section 69.1. Estas estadísticas abordan la limitación almacenando valores individuales, pero es naturalmente más costoso, tanto en términos de construcción de las estadísticas en ANALYZE, como en almacenamiento y tiempo de planificación.

Echemos un vistazo a la consulta de la Section 69.2.1 nuevamente, pero esta vez con una lista MCV creada en el mismo conjunto de columnas (asegúrate de eliminar las dependencias funcionales, para asegurar que el planificador use las estadísticas recién creadas).

DROP STATISTICS stts;
CREATE STATISTICS stts2 (mcv) ON a, b FROM t;
ANALYZE t;
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS 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.00 loops=1)
   Filter: ((a = 1) AND (b = 1))
   Rows Removed by Filter: 9900

La estimación es tan precisa como con las dependencias funcionales, principalmente gracias a que la tabla es bastante pequeña y tiene una distribución simple con un bajo número de valores distintos. Antes de mirar la segunda consulta, que no fue manejada particularmente bien por las dependencias funcionales, inspeccionemos un poco la lista MCV.

La inspección de la lista MCV es posible utilizando la función que devuelve un conjunto 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)

Esto confirma que hay 100 combinaciones distintas en las dos columnas, y todas ellas son aproximadamente igual de probables (1% de frecuencia para cada una). La frecuencia base es la frecuencia calculada a partir de las estadísticas por columna, como si no hubiera estadísticas multicolumna. Si hubiera habido valores nulos en cualquiera de las columnas, esto se identificaría en la columna nulls.

Al estimar la selectividad, el planificador aplica todas las condiciones a los elementos en la lista MCV, y luego suma las frecuencias de los que coinciden. Consulta mcv_clauselist_selectivity en src/backend/statistics/mcv.c for details.

En comparación con las dependencias funcionales, las listas MCV tienen dos ventajas principales. En primer lugar, la lista almacena valores reales, lo que hace posible decidir qué combinaciones son compatibles.

EXPLAIN (ANALYZE, TIMING OFF, BUFFERS 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.00 loops=1)
   Filter: ((a = 1) AND (b = 10))
   Rows Removed by Filter: 10000

En segundo lugar, las listas MCV manejan un rango más amplio de tipos de cláusulas, no solo cláusulas de igualdad como las dependencias funcionales. Por ejemplo, considera la siguiente consulta de rango para la misma tabla:

EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF) SELECT * FROM t WHERE a <= 49 AND b > 49;
                                text PLAN
---------------------------------------------------------------------------
 Seq Scan on t  (cost=0.00..195.00 rows=1 width=8) (actual rows=0.00 loops=1)
   Filter: ((a <= 49) AND (b > 49))
   Rows Removed by Filter: 10000