69.1. Ejemplos de estimación de filas

69.1. Ejemplos de estimación de filas
Prev	Up	Chapter 69. Cómo el planificador utiliza las estadísticas	Home	Next

69.1. Ejemplos de estimación de filas #

Los ejemplos que se muestran a continuación utilizan tablas de la base de datos de pruebas de regresión de PostgreSQL. Ten en cuenta también que, dado que ANALYZE utiliza un muestreo aleatorio al producir estadísticas, los resultados cambiarán ligeramente después de cualquier nuevo ANALYZE.

Comencemos con una consulta muy simple:

EXPLAIN SELECT * FROM tenk1;

                         QUERY PLAN
-------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=244)

Cómo determina el planificador la cardinalidad de tenk1 se cubre en la Section 14.2, pero se repite aquí para completitud. El número de páginas y filas se busca en pg_class:

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

 relpages | reltuples
----------+-----------
      358 |     10000

Estos números están actualizados hasta el último VACUUM o ANALYZE en la tabla. El planificador luego obtiene el número actual real de páginas en la tabla (esta es una operación económica, que no requiere un escaneo de la tabla). Si es diferente de relpages, entonces reltuples se escala proporcionalmente para llegar a una estimación del número actual de filas. En el ejemplo anterior, el valor de relpages está al día, por lo que la estimación de filas es la misma que reltuples.

Pasemos a un ejemplo con una condición de rango en su cláusula WHERE:

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000;

                                   QUERY PLAN
--------------------------------------------------------------------------------
 Bitmap Heap Scan on tenk1  (cost=24.06..394.64 rows=1007 width=244)
   Recheck Cond: (unique1 < 1000)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
         Index Cond: (unique1 < 1000)

El planificador examina la condición de la cláusula WHERE y busca la función de selectividad para el operador < en pg_operator. Esta se encuentra en la columna oprrest, y la entrada en este caso es scalarltsel. La función scalarltsel recupera el histograma para unique1 de pg_statistic. Para consultas manuales es más conveniente buscar en la vista más simple pg_stats:

SELECT histogram_bounds FROM pg_stats
WHERE tablename='tenk1' AND attname='unique1';

                   histogram_bounds
------------------------------------------------------
 {0,993,1997,3050,4040,5036,5957,7057,8029,9016,9995}

A continuación, se calcula la fracción del histograma ocupada por “< 1000”. Esta es la selectividad. El histograma divide el rango en cubetas (buckets) de igual frecuencia, por lo que todo lo que tenemos que hacer es localizar la cubeta en la que se encuentra nuestro valor y contar una parte de ella y todas las anteriores. El valor 1000 está claramente en la segunda cubeta (993–1997). Asumiendo una distribución lineal de los valores dentro de cada cubeta, podemos calcular la selectividad como:

selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_buckets
            = (1 + (1000 - 993)/(1997 - 993))/10
            = 0.100697

es decir, una cubeta completa más una fracción lineal de la segunda, dividida por el número de cubetas. El número estimado de filas ahora se puede calcular como el producto de la selectividad y la cardinalidad de tenk1:

rows = rel_cardinality * selectivity
     = 10000 * 0.100697
     = 1007  (redondeando)

A continuación, consideremos un ejemplo con una condición de igualdad en su cláusula WHERE:

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'CRAAAA';

                         QUERY PLAN
----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=30 width=244)
   Filter: (stringu1 = 'CRAAAA'::name)

Nuevamente, el planificador examina la condición de la cláusula WHERE y busca la función de selectividad para =, que es eqsel. Para la estimación de igualdad, el histograma no es útil; en su lugar, se utiliza la lista de los valores más comunes (MCVs) para determinar la selectividad. Echemos un vistazo a los MCVs, con algunas columnas adicionales que serán útiles más adelante:

SELECT null_frac, n_distinct, most_common_vals, most_common_freqs FROM pg_stats
WHERE tablename='tenk1' AND attname='stringu1';

null_frac         | 0
n_distinct        | 676
most_common_vals  | {EJAAAA,BBAAAA,CRAAAA,FCAAAA,FEAAAA,GSAAAA,JOAAAA,MCAAAA,NAAAAA,WGAAAA}
most_common_freqs | {0.00333333,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003}

Dado que CRAAAA aparece en la lista de MCVs, la selectividad es simplemente la entrada correspondiente en la lista de frecuencias más comunes (MCFs):

selectivity = mcf[3]
            = 0.003

Como antes, el número estimado de filas es simplemente el producto de esto con la cardinalidad de tenk1:

rows = 10000 * 0.003
     = 30

Ahora considera la misma consulta, pero con una constante que no está en la lista MCV:

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'xxx';

                         QUERY PLAN
----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=15 width=244)
   Filter: (stringu1 = 'xxx'::name)

Este es un problema bastante diferente: cómo estimar la selectividad cuando el valor no está en la lista MCV. El enfoque consiste en utilizar el hecho de que el valor no está en la lista, combinado con el conocimiento de las frecuencias de todos los MCVs:

selectivity = (1 - sum(mcv_freqs))/(num_distinct - num_mcv)
            = (1 - (0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 +
                    0.003 + 0.003 + 0.003 + 0.003))/(676 - 10)
            = 0.0014559

Es decir, suma todas las frecuencias de los MCVs y réstalas de uno, luego divide por el número de los otros valores distintos. Esto equivale a asumir que la fracción de la columna que no es ninguno de los MCVs se distribuye uniformemente entre todos los demás valores distintos. Ten en cuenta que no hay valores nulos, por lo que no tenemos que preocuparnos por ellos (de lo contrario, también restaríamos la fracción de nulos del numerador). El número estimado de filas se calcula de la manera habitual:

rows = 10000 * 0.0014559
     = 15  (redondeando)

El ejemplo anterior con unique1 < 1000 era una simplificación excesiva de lo que scalarltsel realmente hace; ahora que hemos visto un ejemplo del uso de MCVs, podemos agregar algunos detalles más. El ejemplo era correcto en la medida en que avanzó, porque dado que unique1 es una columna única, no tiene MCVs (obviamente, ningún valor es más común que cualquier otro valor). Para una columna que no es única, normalmente habrá tanto un histograma como una lista de MCVs, y el histograma no incluye la parte de la población de la columna representada por los MCVs. Hacemos las cosas de esta manera porque permite una estimación más precisa. En esta situación, scalarltsel aplica directamente la condición (por ejemplo, “< 1000”) a cada valor de la lista de MCVs, y suma las frecuencias de los MCVs para los cuales la condición es verdadera. Esto da una estimación exacta de la selectividad dentro de la parte de la tabla que son MCVs. El histograma luego se usa de la misma manera que arriba para estimar la selectividad en la parte de la tabla que no son MCVs, y luego los dos números se combinan para estimar la selectividad general. Por ejemplo, considera:

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 < 'IAAAAA';

                          QUERY PLAN
------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=3077 width=244)
   Filter: (stringu1 < 'IAAAAA'::name)

Ya vimos la información de MCVs para stringu1, y aquí está su histograma:

SELECT histogram_bounds FROM pg_stats
WHERE tablename='tenk1' AND attname='stringu1';

                                histogram_bounds
--------------------------------------------------------------------------------
 {AAAAAA,CQAAAA,FRAAAA,IBAAAA,KRAAAA,NFAAAA,PSAAAA,SGAAAA,VAAAAA,XLAAAA,ZZAAAA}

Revisando la lista de MCVs, encontramos que la condición stringu1 < 'IAAAAA' se satisface por las primeras seis entradas y no por las últimas cuatro, por lo que la selectividad dentro de la parte MCV de la población es:

selectivity = sum(relevant mvfs)
            = 0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003
            = 0.01833333

Sumar todas las MCFs también nos dice que la fracción total de la población representada por MCVs es 0.03033333, y por lo tanto la fracción representada por el histograma es 0.96966667 (nuevamente, no hay nulos, de lo contrario tendríamos que excluirlos aquí). Podemos ver que el valor IAAAAA cae casi al final de la tercera cubeta del histograma. Utilizando algunas suposiciones bastante imprecisas sobre la frecuencia de los diferentes caracteres, el planificador llega a la estimación de 0.298387 para la parte de la población del histograma que es menor que IAAAAA. Luego combinamos las estimaciones para las poblaciones MCV y no MCV:

selectivity = mcv_selectivity + histogram_selectivity * histogram_fraction
            = 0.01833333 + 0.298387 * 0.96966667
            = 0.307669

rows        = 10000 * 0.307669
            = 3077  (redondeando)

En este ejemplo particular, la corrección de la lista de MCVs es bastante pequeña, porque la distribución de la columna es en realidad bastante plana (las estadísticas que muestran estos valores particulares como más comunes que otros se deben principalmente a errores de muestreo). En un caso más típico donde algunos valores son significativamente más comunes que otros, este proceso complicado proporciona una mejora útil en la precisión porque la selectividad para los valores más comunes se determina exactamente.

Ahora consideremos un caso con más de una condición en la cláusula WHERE:

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000 AND stringu1 = 'xxx';

                                   QUERY PLAN
--------------------------------------------------------------------------------
 Bitmap Heap Scan on tenk1  (cost=23.80..396.91 rows=1 width=244)
   Recheck Cond: (unique1 < 1000)
   Filter: (stringu1 = 'xxx'::name)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
         Index Cond: (unique1 < 1000)

El planificador asume que las dos condiciones son independientes, por lo que las selectividades individuales de las cláusulas se pueden multiplicar:

selectivity = selectivity(unique1 < 1000) * selectivity(stringu1 = 'xxx')
            = 0.100697 * 0.0014559
            = 0.0001466

rows        = 10000 * 0.0001466
            = 1  (redondeando)

Ten en cuenta que el número de filas estimado a devolver por el escaneo de índice de mapa de bits (bitmap index scan) refleja solo la condición utilizada con el índice; esto es importante ya que afecta la estimación del costo para las búsquedas posteriores en el heap (heap fetches).

Finalmente examinaremos una consulta que involucra una unión (join):

EXPLAIN SELECT * FROM tenk1 t1, tenk2 t2
WHERE t1.unique1 < 50 AND t1.unique2 = t2.unique2;

                                       QUERY PLAN
--------------------------------------------------------------------------------------
 Nested Loop  (cost=4.64..456.23 rows=50 width=488)
   ->  Bitmap Heap Scan on tenk1 t1  (cost=4.64..142.17 rows=50 width=244)
         Recheck Cond: (unique1 < 50)
         ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..4.63 rows=50 width=0)
               Index Cond: (unique1 < 50)
   ->  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.00..6.27 rows=1 width=244)
         Index Cond: (unique2 = t1.unique2)

La restricción en tenk1, unique1 < 50, se evalúa antes de la unión por bucle anidado (nested-loop join). Esto se maneja de manera análoga al ejemplo de rango anterior. Esta vez, el valor 50 cae en la primera cubeta del histograma de unique1:

selectivity = (0 + (50 - bucket[1].min)/(bucket[1].max - bucket[1].min))/num_buckets
            = (0 + (50 - 0)/(993 - 0))/10
            = 0.005035

rows        = 10000 * 0.005035
            = 50  (redondeando)

La restricción para la unión es t2.unique2 = t1.unique2. El operador es simplemente nuestro conocido =, sin embargo, la función de selectividad se obtiene de la columna oprjoin de pg_operator, y es eqjoinsel. eqjoinsel busca la información estadística tanto para tenk2 como para tenk1:

SELECT tablename, null_frac,n_distinct, most_common_vals FROM pg_stats
WHERE tablename IN ('tenk1', 'tenk2') AND attname='unique2';

tablename  | null_frac | n_distinct | most_common_vals
-----------+-----------+------------+------------------
 tenk1     |         0 |         -1 | 
 tenk2     |         0 |         -1 |

En este caso no hay información de MCV para unique2 y todos los valores seem ser únicos (n_distinct = -1), por lo que usamos un algoritmo que se basa en las estimaciones del recuento de filas para ambas relaciones (num_rows, no mostrado, pero es «tenk») junto con las fracciones de nulos de la columna (cero para ambas):

selectivity = (1 - null_frac1) * (1 - null_frac2) / max(num_rows1, num_rows2)
            = (1 - 0) * (1 - 0) / max(10000, 10000)
            = 0.0001

Esto es, restar la fracción de nulos de uno para cada una de las relaciones, y dividir por el recuento de filas de la relación más grande (este valor se escala en el caso no único). El número de filas que la unión probablemente emitirá se calcula como la cardinalidad del producto cartesiano de las dos entradas, multiplicado por la selectividad:

rows = (outer_cardinality * inner_cardinality) * selectivity
     = (50 * 10000) * 0.0001
     = 50

Si hubiera habido listas de MCVs para las dos columnas, eqjoinsel habría utilizado la comparación directa de las listas de MCVs para determinar la selectividad de la unión dentro de la parte de las poblaciones de columnas representadas por los MCVs. La estimación para el resto de las poblaciones sigue el mismo enfoque que se muestra aquí.

Ten en cuenta que mostramos la inner_cardinality como 10000, es decir, el tamaño no modificado de tenk2. Podría parecer, a partir de la inspección de la salida de EXPLAIN, que la estimación de las filas de la unión proviene de 50 * 1, es decir, el número de filas externas por el número estimado de filas obtenido por cada escaneo de índice interno en tenk2. Pero este no es el caso: el tamaño de la relación de unión se estima antes de que se haya considerado cualquier plan de unión particular. Si todo funciona bien, las dos formas de estimar el tamaño de la unión producirán aproximadamente la misma respuesta, pero debido al error de redondeo y otros factores, a veces divergen significativamente.

Para aquellos interesados en más detalles, la estimación del tamaño de una tabla (antes de cualquier cláusula WHERE) se realiza en src/backend/optimizer/util/plancat.c. La lógica genérica para las selectividades de las cláusulas está en src/backend/optimizer/path/clausesel.c. Las funciones de selectividad específicas de los operadores se encuentran principalmente en src/backend/utils/adt/selfuncs.c.