√ćndices en PostgreSQL - 3 (Hash)

El primer artículo describió el motor de indexación PostgreSQL , el segundo se ocupó de la interfaz de los métodos de acceso , y ahora estamos listos para discutir tipos específicos de índices. Comencemos con el índice hash.

Hachís


Estructura


Teoría general


Muchos lenguajes de programaci√≥n modernos incluyen tablas hash como tipo de datos base. En el exterior, una tabla hash se parece a una matriz regular que se indexa con cualquier tipo de datos (por ejemplo, cadena) en lugar de con un n√ļmero entero. El √≠ndice hash en PostgreSQL est√° estructurado de manera similar. ¬ŅC√≥mo funciona esto?

Como regla, los tipos de datos tienen rangos muy grandes de valores permitidos: ¬Ņcu√°ntas cadenas diferentes podemos imaginar en una columna de tipo "texto"? Al mismo tiempo, ¬Ņcu√°ntos valores diferentes se almacenan realmente en una columna de texto de alguna tabla? Por lo general, no muchos de ellos.

La idea del hash es asociar un n√ļmero peque√Īo (de 0 a N ‚ąí1, N valores en total) con un valor de cualquier tipo de datos. Una asociaci√≥n como esta se llama funci√≥n hash . El n√ļmero obtenido se puede usar como un √≠ndice de una matriz regular donde se almacenar√°n las referencias a las filas de la tabla (TID). Los elementos de esta matriz se denominan cubos de tabla hash : un cubo puede almacenar varios TID si el mismo valor indexado aparece en diferentes filas.

Cuanto más uniformemente una función hash distribuya los valores de origen por cubos, mejor será. Pero incluso una buena función hash a veces producirá resultados iguales para diferentes valores de origen; esto se denomina colisión . Por lo tanto, un depósito puede almacenar los TID correspondientes a diferentes claves y, por lo tanto, los TID obtenidos del índice deben volver a comprobarse.

Solo por ejemplo: ¬Ņen qu√© funci√≥n hash para cadenas podemos pensar? Deje que el n√ļmero de dep√≥sitos sea 256. Luego, por ejemplo, de un n√ļmero de dep√≥sito, podemos tomar el c√≥digo del primer car√°cter (suponiendo una codificaci√≥n de caracteres de un solo byte). ¬ŅEs esta una buena funci√≥n hash? Evidentemente, no: si todas las cadenas comienzan con el mismo car√°cter, todas entrar√°n en un cubo, por lo que la uniformidad est√° fuera de discusi√≥n, todos los valores deber√°n volver a comprobarse, y el hash no tendr√° ning√ļn sentido. ¬ŅQu√© pasa si resumimos los c√≥digos de todos los caracteres del m√≥dulo 256? Esto ser√° mucho mejor, pero lejos de ser ideal. Si est√° interesado en los aspectos internos de dicha funci√≥n hash en PostgreSQL, consulte la definici√≥n de hash_any () en hashfunc.c .

Estructura del índice


Volvamos al √≠ndice hash. Para un valor de alg√ļn tipo de datos (una clave de √≠ndice), nuestra tarea es encontrar r√°pidamente el TID correspondiente.

Al insertar en el √≠ndice, calculemos la funci√≥n hash para la clave. Las funciones hash en PostgreSQL siempre devuelven el tipo "entero", que est√° en el rango de 2 32 ‚Čą 4 mil millones de valores. El n√ļmero de dep√≥sitos inicialmente es igual a dos y aumenta din√°micamente para ajustarse al tama√Īo de los datos. El n√ļmero de dep√≥sito se puede calcular a partir del c√≥digo hash utilizando la aritm√©tica de bits. Y este es el cubo donde pondremos nuestro TID.

Pero esto es insuficiente ya que los TID que coinciden con diferentes claves se pueden poner en el mismo dep√≥sito. Que haremos Es posible almacenar el valor de origen de la clave en un dep√≥sito, adem√°s del TID, pero esto aumentar√≠a significativamente el tama√Īo del √≠ndice. Para ahorrar espacio, en lugar de una clave, el dep√≥sito almacena el c√≥digo hash de la clave.

Al buscar a trav√©s del √≠ndice, calculamos la funci√≥n hash para la clave y obtenemos el n√ļmero de dep√≥sito. Ahora queda revisar el contenido del dep√≥sito y devolver solo los TID coincidentes con los c√≥digos hash apropiados. Esto se realiza de manera eficiente ya que se ordenan los pares almacenados de "c√≥digo hash - TID".

Sin embargo, pueden suceder dos claves diferentes no solo para entrar en un cubo, sino también para tener los mismos códigos hash de cuatro bytes: nadie ha eliminado la colisión. Por lo tanto, el método de acceso solicita al motor de indexación general que verifique cada TID volviendo a verificar la condición en la fila de la tabla (el motor puede hacer esto junto con la verificación de visibilidad).

Asignación de estructuras de datos a páginas


Si observamos un √≠ndice tal como lo ve el administrador de la memoria cach√© del b√ļfer en lugar de desde la perspectiva de la planificaci√≥n y ejecuci√≥n de consultas, resulta que toda la informaci√≥n y todas las filas del √≠ndice deben empaquetarse en p√°ginas. Dichas p√°ginas de √≠ndice se almacenan en la memoria cach√© del b√ļfer y se expulsan de all√≠ exactamente de la misma manera que las p√°ginas de la tabla.



El índice hash, como se muestra en la figura, utiliza cuatro tipos de páginas (rectángulos grises):

  • Meta p√°gina: n√ļmero de p√°gina cero, que contiene informaci√≥n sobre lo que est√° dentro del √≠ndice.
  • P√°ginas de dep√≥sito: p√°ginas principales del √≠ndice, que almacenan datos como pares "c√≥digo hash - TID".
  • P√°ginas de desbordamiento: estructuradas de la misma manera que las p√°ginas de dep√≥sito y utilizadas cuando una p√°gina es insuficiente para un dep√≥sito.
  • P√°ginas de mapa de bits: que realizan un seguimiento de las p√°ginas de desbordamiento que actualmente son claras y pueden reutilizarse para otros dep√≥sitos.

Las flechas hacia abajo que comienzan en los elementos de la página de índice representan TID, es decir, referencias a las filas de la tabla.

Cada vez que aumenta el √≠ndice, PostgreSQL crea instant√°neamente el doble de dep√≥sitos (y, por lo tanto, p√°ginas) que la √ļltima vez que se crearon. Para evitar la asignaci√≥n de este n√ļmero potencialmente grande de p√°ginas a la vez, la versi√≥n 10 hizo que el tama√Īo aumentara m√°s suavemente. En cuanto a las p√°ginas de desbordamiento, se asignan justo cuando surge la necesidad y se rastrean en p√°ginas de mapa de bits, que tambi√©n se asignan cuando surge la necesidad.

Tenga en cuenta que el √≠ndice hash no puede disminuir de tama√Īo. Si eliminamos algunas de las filas indexadas, las p√°ginas una vez asignadas no se devolver√°n al sistema operativo, sino que solo se reutilizar√°n para nuevos datos despu√©s de VACUUMING. La √ļnica opci√≥n para disminuir el tama√Īo del √≠ndice es reconstruirlo desde cero utilizando el comando REINDEX o VACUUM FULL.

Ejemplo


Veamos c√≥mo se crea el √≠ndice hash. Para evitar dise√Īar nuestras propias tablas, a partir de ahora utilizaremos la base de datos de demostraci√≥n de transporte a√©reo, y esta vez consideraremos la tabla de vuelos.

demo=# create index on flights using hash(flight_no); 
 WARNING: hash indexes are not WAL-logged and their use is discouraged CREATE INDEX 

 demo=# explain (costs off) select * from flights where flight_no = 'PG0001'; 
  QUERY PLAN ---------------------------------------------------- Bitmap Heap Scan on flights Recheck Cond: (flight_no = 'PG0001'::bpchar) -> Bitmap Index Scan on flights_flight_no_idx Index Cond: (flight_no = 'PG0001'::bpchar) (4 rows) 

Lo inconveniente de la implementación actual del índice hash es que las operaciones con el índice no se registran en el registro de escritura anticipada (de lo cual PostgreSQL advierte cuando se crea el índice). En consecuencia, los índices hash no se pueden recuperar después del error y no participan en las réplicas. Además, el índice de hash está muy por debajo del "árbol B" en versatilidad, y su eficiencia también es cuestionable. Por lo tanto, ahora no es práctico usar tales índices.

Sin embargo, esto cambiar√° tan pronto como este oto√Īo (2017) una vez que se lance la versi√≥n 10 de PostgreSQL. En esta versi√≥n, el √≠ndice hash finalmente obtuvo soporte para el registro de escritura anticipada; Adem√°s, la asignaci√≥n de memoria se optimiz√≥ y el trabajo concurrente se hizo m√°s eficiente.

Eso es verdad Desde PostgreSQL 10 los índices hash tienen soporte completo y se pueden usar sin restricciones. La advertencia ya no se muestra.

Sem√°ntica de hash


Pero, ¬Ņpor qu√© el √≠ndice hash sobrevivi√≥ casi desde el nacimiento de PostgreSQL hasta que 9.6 no se pudo utilizar? La cuesti√≥n es que DBMS hace un uso extensivo del algoritmo de hash (espec√≠ficamente, para combinaciones de hash y agrupaciones), y el sistema debe saber qu√© funci√≥n de hash se aplica a qu√© tipos de datos. Pero esta correspondencia no es est√°tica, y no se puede establecer de una vez por todas, ya que PostgreSQL permite agregar nuevos tipos de datos sobre la marcha. Y este es un m√©todo de acceso por hash, donde se almacena esta correspondencia, representada como una asociaci√≥n de funciones auxiliares con familias de operadores.

 demo=# select opf.opfname as opfamily_name, amproc.amproc::regproc AS opfamily_procedure from pg_am am, pg_opfamily opf, pg_amproc amproc where opf.opfmethod = am.oid and amproc.amprocfamily = opf.oid and am.amname = 'hash' order by opfamily_name, opfamily_procedure; 
  opfamily_name | opfamily_procedure --------------------+-------------------- abstime_ops | hashint4 aclitem_ops | hash_aclitem array_ops | hash_array bool_ops | hashchar ... 

Aunque estas funciones no están documentadas, se pueden usar para calcular el código hash para un valor del tipo de datos apropiado. Por ejemplo, la función "hashtext" si se usa para la familia de operadores "text_ops":

 demo=# select hashtext('one'); 
  hashtext ----------- 127722028 (1 row) 

 demo=# select hashtext('two'); 
  hashtext ----------- 345620034 (1 row) 

Propiedades


Veamos las propiedades del √≠ndice hash, donde este m√©todo de acceso proporciona al sistema informaci√≥n sobre s√≠ mismo. Proporcionamos consultas la √ļltima vez . Ahora no iremos m√°s all√° de los resultados:

  name | pg_indexam_has_property ---------------+------------------------- can_order | f can_unique | f can_multi_col | f can_exclude | t name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | t bitmap_scan | t backward_scan | t name | pg_index_column_has_property --------------------+------------------------------ asc | f desc | f nulls_first | f nulls_last | f orderable | f distance_orderable | f returnable | f search_array | f search_nulls | f 

Una funci√≥n hash no retiene la relaci√≥n de orden: si el valor de una funci√≥n hash para una clave es menor que para la otra clave, es imposible sacar conclusiones sobre c√≥mo se ordenan las claves. Por lo tanto, en general, el √≠ndice hash puede admitir la √ļnica operaci√≥n "igual":

 demo=# select opf.opfname AS opfamily_name, amop.amopopr::regoperator AS opfamily_operator from pg_am am, pg_opfamily opf, pg_amop amop where opf.opfmethod = am.oid and amop.amopfamily = opf.oid and am.amname = 'hash' order by opfamily_name, opfamily_operator; 
  opfamily_name | opfamily_operator ---------------+---------------------- abstime_ops | =(abstime,abstime) aclitem_ops | =(aclitem,aclitem) array_ops | =(anyarray,anyarray) bool_ops | =(boolean,boolean) ... 

En consecuencia, el índice hash no puede devolver datos ordenados ("can_order", "orderable"). El índice hash no manipula NULL por la misma razón: la operación "igual" no tiene sentido para NULL ("search_nulls").

Dado que el índice hash no almacena claves (sino solo sus códigos hash), no se puede usar para acceso de solo índice ("retornable").

Este método de acceso tampoco admite índices de varias columnas ("can_multi_col").

Internos


A partir de la versión 10, será posible buscar en el índice interno hash a través de la extensión " pageinspect ". Así se verá:

 demo=# create extension pageinspect; 

La p√°gina meta (obtenemos el n√ļmero de filas en el √≠ndice y el n√ļmero m√°ximo de cubos usados):

 demo=# select hash_page_type(get_raw_page('flights_flight_no_idx',0)); 
  hash_page_type ---------------- metapage (1 row) 

 demo=# select ntuples, maxbucket from hash_metapage_info(get_raw_page('flights_flight_no_idx',0)); 
  ntuples | maxbucket ---------+----------- 33121 | 127 (1 row) 

Una p√°gina de dep√≥sito (obtenemos el n√ļmero de tuplas vivas y tuplas muertas, es decir, las que se pueden aspirar):

 demo=# select hash_page_type(get_raw_page('flights_flight_no_idx',1)); 
  hash_page_type ---------------- bucket (1 row) 

 demo=# select live_items, dead_items from hash_page_stats(get_raw_page('flights_flight_no_idx',1)); 
  live_items | dead_items ------------+------------ 407 | 0 (1 row) 

Y así sucesivamente. Pero apenas es posible descifrar el significado de todos los campos disponibles sin examinar el código fuente. Si desea hacerlo, debe comenzar con README .

Sigue leyendo .

Source: https://habr.com/ru/post/442776/


All Articles