Introduccion

Esta serie de artículos se ocupa en gran medida de los índices en PostgreSQL.

Cualquier tema puede ser considerado desde diferentes perspectivas. Discutiremos asuntos que deberían interesar a un desarrollador de aplicaciones que usa DBMS: qué índices están disponibles, por qué hay tantos tipos diferentes de ellos y cómo usarlos para acelerar las consultas. El tema probablemente se puede cubrir en menos palabras, pero en secreto esperamos un desarrollador curioso, que también esté interesado en los detalles de las partes internas, especialmente porque la comprensión de dichos detalles le permite no solo diferir el juicio de los demás, sino también sacar conclusiones de los tuyos

El desarrollo de nuevos tipos de índices está fuera del alcance. Esto requiere conocimiento del lenguaje de programación C y pertenece a la experiencia de un programador de sistemas en lugar de un desarrollador de aplicaciones. Por la misma razón, casi no discutiremos las interfaces de programación, sino que nos centraremos solo en lo que importa para trabajar con índices listos para usar.

En este artículo discutiremos la distribución de responsabilidades entre el motor de indexación general relacionado con el núcleo DBMS y los métodos de acceso al índice individual, que PostgreSQL nos permite agregar como extensiones. En el próximo artículo discutiremos la interfaz del método de acceso y conceptos críticos como clases y familias de operadores. Después de esa introducción larga pero necesaria, consideraremos los detalles de la estructura y la aplicación de diferentes tipos de índices: Hash , B-tree , GiST , SP-GiST , GIN y RUM , BRIN y Bloom .

Antes de comenzar, me gustaría agradecer a Elena Indrupskaya por traducir los artículos al inglés.
Las cosas han cambiado un poco desde la publicación original. Mis comentarios sobre el estado actual de las cosas se indican así.

Índices

En PostgreSQL, los índices son objetos especiales de la base de datos diseñados principalmente para acelerar el acceso a los datos. Son estructuras auxiliares: cada índice se puede eliminar y volver a crear a partir de la información de la tabla. Es posible que a veces escuche que un DBMS puede funcionar sin índices, aunque lentamente. Sin embargo, este no es el caso, ya que los índices también sirven para imponer algunas restricciones de integridad.

Actualmente, seis tipos diferentes de índices están integrados en PostgreSQL 9.6, y un índice más está disponible como una extensión, gracias a cambios significativos en la versión 9.6. Entonces, espere nuevos tipos de índices en un futuro cercano.

A pesar de todas las diferencias entre los tipos de índices (también llamados métodos de acceso), cada uno de ellos finalmente asocia una clave (por ejemplo, el valor de la columna indexada) con las filas de la tabla que contienen esta clave. Cada fila se identifica por TID (tuple id), que consiste en el número de bloque en el archivo y la posición de la fila dentro del bloque. Dicho esto, con la clave conocida o alguna información al respecto, podemos leer rápidamente esas filas que pueden contener la información de nuestro interés sin escanear toda la tabla.

Es importante comprender que un índice acelera el acceso a los datos a un costo de mantenimiento determinado. Para cada operación en datos indexados, ya sea inserción, eliminación o actualización de filas de la tabla, los índices para esa tabla también deben actualizarse y en la misma transacción. Tenga en cuenta que la actualización de los campos de la tabla para los que no se han creado índices no da como resultado la actualización del índice; Esta técnica se llama HOT (Tuplas de solo almacenamiento dinámico).

La extensibilidad conlleva algunas implicaciones. Para permitir la adición fácil de un nuevo método de acceso al sistema, se implementó una interfaz del motor de indexación general. Su tarea principal es obtener los TID del método de acceso y trabajar con ellos:

• Lea los datos de las versiones correspondientes de las filas de la tabla.
• Obtenga versiones de fila TID por TID o en un lote utilizando un mapa de bits preconstruido.
• Verifique la visibilidad de las versiones de fila para la transacción actual teniendo en cuenta su nivel de aislamiento.

El motor de indexación participa en la realización de consultas. Se llama de acuerdo con un plan creado en la etapa de optimización. El optimizador, clasificando y evaluando diferentes formas de realizar la consulta, debe comprender las capacidades de todos los métodos de acceso que son potencialmente aplicables. ¿El método podrá devolver datos en el orden necesario o deberíamos anticipar la clasificación? ¿Podemos usar este método para buscar NULL? Estos son problemas que el optimizador está resolviendo regularmente.

No solo el optimizador necesita información sobre el método de acceso. Al crear un índice, el sistema debe decidir si el índice se puede construir en varias columnas y si este índice garantiza la unicidad.

Por lo tanto, cada método de acceso debe proporcionar toda la información necesaria sobre sí mismo. Las versiones inferiores a 9.6 usaban la tabla "pg_am" para esto, mientras que a partir de la versión 9.6 los datos se movían a niveles más profundos, dentro de funciones especiales. Nos familiarizaremos con esta interfaz un poco más.

Todo lo demás es tarea del método de acceso:

• Implemente un algoritmo para construir el índice y mapear los datos en páginas (para que el administrador de caché de búfer procese uniformemente cada índice).
• Busque información en el índice por un predicado en la forma " expresión de operador de campo indexado ".
• Evaluar el costo de uso del índice.
• Manipule los bloqueos necesarios para el correcto procesamiento paralelo.
• Generar registros de escritura anticipada (WAL).

Primero consideraremos las capacidades del motor de indexación general y luego consideraremos diferentes métodos de acceso.

Motor de indexación

El motor de indexación permite a PostgreSQL trabajar con varios métodos de acceso de manera uniforme, pero teniendo en cuenta sus características.

Principales técnicas de escaneo

Exploración de índice

Podemos trabajar de manera diferente con los TID proporcionados por un índice. Consideremos un ejemplo:

postgres=# create table t(a integer, b text, c boolean); postgres=# insert into t(a,b,c) select s.id, chr((32+random()*94)::integer), random() < 0.01 from generate_series(1,100000) as s(id) order by random(); postgres=# create index on t(a); postgres=# analyze t; 

Creamos una tabla de tres campos. El primer campo contiene números del 1 al 100.000, y se crea un índice (sin importar el tipo) en este campo. El segundo campo contiene varios caracteres ASCII, excepto los no imprimibles. Finalmente, el tercer campo contiene un valor lógico que es verdadero para aproximadamente el 1% de las filas y falso para el resto. Las filas se insertan en la tabla en un orden aleatorio.

Intentemos seleccionar un valor por la condición "a = 1". Tenga en cuenta que la condición se ve como " expresión de operador de campo indexado ", donde el operador es "igual" y la expresión (clave de búsqueda) es "1". En la mayoría de los casos, la condición debe verse así para que se utilice el índice.

 postgres=# explain (costs off) select * from t where a = 1; 

  QUERY PLAN ------------------------------- Index Scan using t_a_idx on t Index Cond: (a = 1) (2 rows) 

En este caso, el optimizador decidió usar el escaneo de índice . Con el escaneo de índice, el método de acceso devuelve los valores TID uno por uno hasta que se alcanza la última fila coincidente. El motor de indexación accede a las filas de la tabla indicadas por TID a su vez, obtiene la versión de la fila, verifica su visibilidad con respecto a las reglas de concurrencia multiversion y devuelve los datos obtenidos.

Escaneo de mapa de bits

El escaneo de índice funciona bien cuando tratamos solo con unos pocos valores. Sin embargo, a medida que aumenta el número de filas recuperadas, es más probable que vuelva a la misma página de la tabla varias veces. Por lo tanto, el optimizador cambia al escaneo de mapa de bits .

 postgres=# explain (costs off) select * from t where a <= 100; 

  QUERY PLAN ------------------------------------ Bitmap Heap Scan on t Recheck Cond: (a <= 100) -> Bitmap Index Scan on t_a_idx Index Cond: (a <= 100) (4 rows) 

El método de acceso primero devuelve todos los TID que coinciden con la condición (nodo de exploración de índice de mapa de bits), y el mapa de bits de las versiones de fila se crea a partir de estos TID. Las versiones de fila se leen de la tabla (Análisis de montón de mapa de bits), y cada página se lee solo una vez.

Tenga en cuenta que en el segundo paso, la condición puede volver a comprobarse (Volver a comprobar Cond). El número de filas recuperadas puede ser demasiado grande para que el mapa de bits de las versiones de fila se ajuste completamente a la RAM (limitado por el parámetro "work_mem"). En este caso, el mapa de bits solo se crea para páginas que contienen al menos una versión de fila coincidente. Este mapa de bits "con pérdida" requiere menos espacio, pero al leer una página, debemos volver a verificar las condiciones para cada fila contenida allí. Tenga en cuenta que incluso para un pequeño número de filas recuperadas y, por lo tanto, mapa de bits "exacto" (como en nuestro ejemplo), el paso "Recheck Cond" está representado en el plan de todos modos, aunque en realidad no se realiza.

Si se imponen condiciones en varios campos de la tabla y estos campos están indexados, el escaneo de mapa de bits permite el uso de varios índices simultáneamente (si el optimizador lo considera eficiente). Para cada índice, se crean mapas de bits de versiones de fila, para lo cual se realiza la multiplicación booleana a nivel de bit (si las expresiones están unidas por AND) o la suma booleana (si las expresiones están unidas por OR). Por ejemplo:

 postgres=# create index on t(b); postgres=# analyze t; postgres=# explain (costs off) select * from t where a <= 100 and b = 'a'; 

  QUERY PLAN -------------------------------------------------- Bitmap Heap Scan on t Recheck Cond: ((a <= 100) AND (b = 'a'::text)) -> BitmapAnd -> Bitmap Index Scan on t_a_idx Index Cond: (a <= 100) -> Bitmap Index Scan on t_b_idx Index Cond: (b = 'a'::text) (7 rows) 

Aquí el nodo BitmapAnd une dos mapas de bits mediante la operación bit a bit "y".

El escaneo de mapa de bits nos permite evitar accesos repetidos a la misma página de datos. Pero, ¿qué pasa si los datos en las páginas de la tabla se ordenan físicamente exactamente de la misma manera que los registros de índice? Es indudable que no podemos confiar plenamente en el orden físico de los datos en las páginas. Si se necesitan datos ordenados, debemos especificar explícitamente la cláusula ORDER BY en la consulta. Pero es probable que haya situaciones en las que realmente se ordenan "casi todos" los datos: por ejemplo, si se agregan filas en el orden necesario y no cambian después de eso o después de ejecutar el comando CLUSTER. En casos como este, construir un mapa de bits es un paso excesivo, y un escaneo de índice regular será igual de bueno (a menos que tengamos en cuenta la posibilidad de unir varios índices). Por lo tanto, al elegir un método de acceso, el planificador examina una estadística especial que muestra la correlación entre el orden físico de las filas y el orden lógico de los valores de las columnas:

 postgres=# select attname, correlation from pg_stats where tablename = 't'; 

  attname | correlation ---------+------------- b | 0.533512 c | 0.942365 a | -0.00768816 (3 rows) 

Los valores absolutos cercanos a uno indican una alta correlación (como para la columna "c"), mientras que los valores cercanos a cero, por el contrario, indican una distribución caótica (columna "a").

Exploración secuencial

Para completar la imagen, debemos tener en cuenta que con una condición no selectiva, el optimizador tendrá razón al preferir el escaneo secuencial de toda la tabla al uso del índice:

 postgres=# explain (costs off) select * from t where a <= 40000; 

  QUERY PLAN ------------------------ Seq Scan on t Filter: (a <= 40000) (2 rows) 

La cuestión es que los índices funcionan mejor cuanto mayor sea la selectividad de la condición, es decir, menos filas coinciden. El crecimiento del número de filas recuperadas aumenta los costos generales de la lectura de las páginas de índice.

Los escaneos secuenciales son más rápidos que los escaneos aleatorios agravan la situación. Esto se aplica especialmente a los discos duros, donde la operación mecánica de llevar un cabezal magnético a una pista lleva mucho más tiempo que la lectura de datos. Este efecto es menos notable para SSD. Hay dos parámetros disponibles para tener en cuenta las diferencias en los costos de acceso, "seq_page_cost" y "random_page_cost", que podemos establecer no solo globalmente, sino a nivel de espacios de tabla, de esta forma ajustándonos a las características de los diferentes subsistemas de disco.

Cubriendo índices

Como regla general, la tarea principal de un método de acceso es devolver los identificadores de las filas de la tabla coincidentes para que el motor de indexación lea los datos necesarios de estas filas. Pero, ¿qué sucede si el índice ya contiene todos los datos necesarios para la consulta? Tal índice se llama cobertura , y en este caso, el optimizador puede aplicar el escaneo de solo índice :

 postgres=# vacuum t; postgres=# explain (costs off) select a from t where a < 100; 

  QUERY PLAN ------------------------------------ Index Only Scan using t_a_idx on t Index Cond: (a < 100) (2 rows) 

Este nombre puede dar una idea de que el motor de indexación no accede a la tabla y obtiene toda la información necesaria solo del método de acceso. Pero este no es exactamente el caso, ya que los índices en PostgreSQL no almacenan información que nos permita juzgar la visibilidad de la fila. Por lo tanto, un método de acceso devuelve versiones de filas que coinciden con la condición de búsqueda, independientemente de su visibilidad en la transacción actual.

Sin embargo, si el motor de indexación necesitara mirar la tabla para ver la visibilidad cada vez, este método de escaneo no habría sido diferente de un escaneo de índice regular.

Para resolver el problema, para las tablas PostgreSQL mantiene un denominado mapa de visibilidad en el que el vacío marca las páginas donde los datos no se modificaron lo suficiente como para que todas las transacciones puedan ver estos datos, independientemente de la hora de inicio y el nivel de aislamiento. Si el identificador de una fila devuelta por el índice se relaciona con dicha página, se puede evitar la verificación de visibilidad.

Por lo tanto, la aspiración regular aumenta la eficiencia de los índices de cobertura. Además, el optimizador tiene en cuenta la cantidad de tuplas muertas y puede decidir no utilizar el escaneo de solo índice si predice altos costos generales para la verificación de visibilidad.

Podemos aprender el número de accesos forzados a una tabla usando el comando EXPLAIN ANALYZE:

 postgres=# explain (analyze, costs off) select a from t where a < 100; 

  QUERY PLAN ------------------------------------------------------------------------------- Index Only Scan using t_a_idx on t (actual time=0.025..0.036 rows=99 loops=1) Index Cond: (a < 100) Heap Fetches: 0 Planning time: 0.092 ms Execution time: 0.059 ms (5 rows) 

En este caso, no era necesario acceder a la tabla (Heap Fetches: 0), ya que se acaba de pasar la aspiradora. En general, cuanto más cercano sea este número a cero, mejor.

No todos los índices almacenan valores indexados junto con identificadores de fila. Si el método de acceso no puede devolver los datos, no puede usarse para escaneos de solo índice.

PostgreSQL 11 ha introducido una nueva característica: INCLUDE-indexes. ¿Qué sucede si hay un índice único que carece de algunas columnas para ser utilizado como índice de cobertura para alguna consulta? No puede simplemente agregar las columnas al índice, ya que romperá su singularidad. La función permite incluir columnas sin clave que no afectan la unicidad y no pueden usarse en predicados de búsqueda, pero aún pueden servir escaneos de solo índice. El parche fue desarrollado por mi colega Anastasia Lubennikova.

Nulo

Los NULL juegan un papel importante en las bases de datos relacionales como una forma conveniente de representar un valor inexistente o desconocido.

Pero un valor especial es especial para tratar. Un álgebra booleana regular se vuelve ternaria; no está claro si NULL debería ser más pequeño o más grande que los valores regulares (esto requiere construcciones especiales para la clasificación, NULLS FIRST y NULLS LAST); no es evidente si las funciones agregadas deberían considerar NULL o no; Se necesita una estadística especial para el planificador ...

Desde la perspectiva del índice de soporte, tampoco está claro si necesitamos indexar estos valores o no. Si los NULL no están indexados, el índice puede ser más compacto. Pero si los NULL están indexados, podremos usar el índice para condiciones como " el campo indexado IS [NOT] NULL" y también como un índice de cobertura cuando no se especifican condiciones para la tabla (ya que en este caso, el index debe devolver los datos de todas las filas de la tabla, incluidas aquellas con NULL).

Para cada método de acceso, los desarrolladores toman una decisión individual de indexar NULL o no. Pero, por regla general, se indexan.

Índices en varios campos

Para admitir condiciones para varios campos, se pueden usar índices de varias columnas . Por ejemplo, podríamos construir un índice en dos campos de nuestra tabla:

 postgres=# create index on t(a,b); postgres=# analyze t; 

Lo más probable es que el optimizador prefiera este índice a unirse a los mapas de bits, ya que aquí obtenemos fácilmente los TID necesarios sin ninguna operación auxiliar:

 postgres=# explain (costs off) select * from t where a <= 100 and b = 'a'; 

  QUERY PLAN ------------------------------------------------ Index Scan using t_a_b_idx on t Index Cond: ((a <= 100) AND (b = 'a'::text)) (2 rows) 

Un índice de varias columnas también se puede utilizar para acelerar la recuperación de datos por una condición para algunos de los campos, comenzando por el primero:

 postgres=# explain (costs off) select * from t where a <= 100; 

  QUERY PLAN -------------------------------------- Bitmap Heap Scan on t Recheck Cond: (a <= 100) -> Bitmap Index Scan on t_a_b_idx Index Cond: (a <= 100) (4 rows) 

En general, si la condición no se impone en el primer campo, el índice no se utilizará. Pero a veces el optimizador puede considerar el uso del índice como más eficiente que la exploración secuencial. Ampliaremos este tema cuando consideremos los índices "btree".

No todos los métodos de acceso admiten la creación de índices en varias columnas.

Índices sobre expresiones

Ya hemos mencionado que la condición de búsqueda debe verse como " expresión de operador de campo indexado ". En el siguiente ejemplo, el índice no se usará ya que se usa una expresión que contiene el nombre del campo en lugar del nombre del campo en sí:

 postgres=# explain (costs off) select * from t where lower(b) = 'a'; 

  QUERY PLAN ------------------------------------------ Seq Scan on t Filter: (lower((b)::text) = 'a'::text) (2 rows) 

No es necesario reescribir esta consulta específica para que solo el nombre del campo se escriba a la izquierda del operador. Pero si esto no es posible, los índices en expresiones (índices funcionales) ayudarán:

 postgres=# create index on t(lower(b)); postgres=# analyze t; postgres=# explain (costs off) select * from t where lower(b) = 'a'; 

  QUERY PLAN ---------------------------------------------------- Bitmap Heap Scan on t Recheck Cond: (lower((b)::text) = 'a'::text) -> Bitmap Index Scan on t_lower_idx Index Cond: (lower((b)::text) = 'a'::text) (4 rows) 

El índice funcional no se crea en un campo de tabla, sino en una expresión arbitraria. El optimizador considerará este índice para condiciones como " expresión de operador de expresión indexada ". Si el cálculo de la expresión a indexar es una operación costosa, la actualización del índice también requerirá importantes recursos de cálculo.

Tenga en cuenta también que se recopila una estadística individual para la expresión indexada. Podemos conocer esta estadística en la vista "pg_stats" por el nombre del índice:

 postgres=# \dt 

  Table "public.t" Column | Type | Modifiers --------+---------+----------- a | integer | b | text | c | boolean | Indexes: "t_a_b_idx" btree (a, b) "t_a_idx" btree (a) "t_b_idx" btree (b) "t_lower_idx" btree (lower(b)) 

 postgres=# select * from pg_stats where tablename = 't_lower_idx'; 

Es posible, si es necesario, controlar el número de cestas de histograma de la misma manera que para los campos de datos regulares (observando que el nombre de la columna puede diferir dependiendo de la expresión indexada):

 postgres=# \d t_lower_idx 

  Index "public.t_lower_idx" Column | Type | Definition --------+------+------------ lower | text | lower(b) btree, for table "public.t" 

 postgres=# alter index t_lower_idx alter column "lower" set statistics 69; 

PostgreSQL 11 ha introducido una forma más limpia de controlar el objetivo de estadísticas para índices especificando el número de columna en el comando ALTER INDEX ... SET STATISTICS. El parche fue desarrollado por mi colega Alexander Korotkov y Adrien Nayrat.

Índices parciales

A veces surge la necesidad de indexar solo parte de las filas de la tabla. Esto generalmente está relacionado con una distribución altamente no uniforme: tiene sentido buscar un valor poco frecuente por un índice, pero es más fácil encontrar un valor frecuente mediante el escaneo completo de la tabla.

Ciertamente podemos construir un índice regular en la columna "c", que funcionará de la manera que esperamos:

 postgres=# create index on t(c); postgres=# analyze t; postgres=# explain (costs off) select * from t where c; 

  QUERY PLAN ------------------------------- Index Scan using t_c_idx on t Index Cond: (c = true) Filter: c (3 rows) 

 postgres=# explain (costs off) select * from t where not c; 

  QUERY PLAN ------------------- Seq Scan on t Filter: (NOT c) (2 rows) 

Y el tamaño del índice es de 276 páginas:

 postgres=# select relpages from pg_class where relname='t_c_idx'; 

  relpages ---------- 276 (1 row) 

Pero como la columna "c" tiene el valor de verdadero solo para el 1% de las filas, el 99% del índice en realidad nunca se usa. En este caso, podemos construir un índice parcial:

 postgres=# create index on t(c) where c; postgres=# analyze t; 

El tamaño del índice se reduce a 5 páginas:

 postgres=# select relpages from pg_class where relname='t_c_idx1'; 

  relpages ---------- 5 (1 row) 

A veces, la diferencia en el tamaño y el rendimiento puede ser bastante significativa.

Clasificación

Si un método de acceso devuelve identificadores de fila en un orden particular, esto le brinda al optimizador opciones adicionales para realizar la consulta.

Podemos escanear la tabla y luego ordenar los datos:

 postgres=# set enable_indexscan=off; postgres=# explain (costs off) select * from t order by a; 

  QUERY PLAN --------------------- Sort Sort Key: a -> Seq Scan on t (3 rows) 

Pero podemos leer los datos usando el índice fácilmente en el orden deseado:

 postgres=# set enable_indexscan=on; postgres=# explain (costs off) select * from t order by a; 

  QUERY PLAN ------------------------------- Index Scan using t_a_idx on t (1 row) 

Solo "btree" de todos los métodos de acceso puede devolver datos ordenados, así que pospongamos una discusión más detallada hasta considerar este tipo de índice.

Edificio concurrente

Por lo general, la creación de un índice adquiere un bloqueo COMPARTIR para la tabla. Este bloqueo permite leer datos de la tabla, pero prohíbe cualquier cambio mientras se construye el índice.

Podemos asegurarnos de esto si, por ejemplo, durante la creación de un índice en la tabla "t", realizamos la consulta a continuación en otra sesión:

 postgres=# select mode, granted from pg_locks where relation = 't'::regclass; 

  mode | granted -----------+--------- ShareLock | t (1 row) 

Si la tabla es lo suficientemente grande y se usa ampliamente para la inserción, actualización o eliminación, esto puede parecer inadmisible ya que los procesos de modificación esperarán a que se libere el bloqueo durante mucho tiempo.

En este caso, podemos usar la construcción concurrente de un índice.

 postgres=# create index concurrently on t(a); 

Este comando bloquea la tabla en el modo COMPARTIR EXCLUSIVA ACTUALIZACIÓN, lo que permite tanto la lectura como la actualización (solo está prohibido cambiar la estructura de la tabla, así como la aspiración, el análisis o la creación simultánea de otro índice en esta tabla).

Sin embargo, también hay otro lado negativo. Primero, el índice se construirá más lentamente de lo habitual ya que se realizan dos pases a través de la tabla en lugar de uno, y también es necesario esperar la finalización de las transacciones paralelas que modifican los datos.

Segundo, con la construcción concurrente del índice, puede ocurrir un punto muerto o pueden violarse restricciones únicas. Sin embargo, el índice se construirá, aunque no operará. Tal índice debe ser eliminado y reconstruido. Los índices que no funcionan están marcados con la palabra NO VÁLIDA en la salida del comando psql \ d, y la siguiente consulta devuelve una lista completa de esos:

 postgres=# select indexrelid::regclass index_name, indrelid::regclass table_name from pg_index where not indisvalid; 

  index_name | table_name ------------+------------ t_a_idx | t (1 row) 

Sigue leyendo .