Comprensión de "exploración de montón de mapa de bits" y "exploración de índice de mapa de bits"

Trataré de explicar mis malentendidos con el siguiente ejemplo.

No entendí los fundamentos de la Bitmap Heap Scan Node. Considere la consulta SELECT customerid, username FROM customers WHERE customerid < 1000 AND username <'user100';cuyo plan es este:

Bitmap Heap Scan on customers  (cost=25.76..61.62 rows=10 width=13) (actual time=0.077..0.077 rows=2 loops=1)
  Recheck Cond: (((username)::text < 'user100'::text) AND (customerid < 1000))
  ->  BitmapAnd  (cost=25.76..25.76 rows=10 width=0) (actual time=0.073..0.073 rows=0 loops=1)
        ->  Bitmap Index Scan on ix_cust_username  (cost=0.00..5.75 rows=200 width=0) (actual time=0.006..0.006 rows=2 loops=1)
              Index Cond: ((username)::text < 'user100'::text)
        ->  Bitmap Index Scan on customers_pkey  (cost=0.00..19.75 rows=1000 width=0) (actual time=0.065..0.065 rows=999 loops=1)
              Index Cond: (customerid < 1000)

Mi comprensión de este nodo :

Como se explica allí , la bitmap heap scantabla de lectura se bloquea en orden secuencial, por lo que no produce una sobrecarga de acceso aleatorio a la tabla, lo que sucede simplemente Index Scan.

Una Index Scanvez hecho esto, PostgreSQL no sabe cómo recuperar las filas de manera óptima, para evitar el acceso innecesario heap blocks reads(o hitssi hay una caché activa). Entonces, para descubrirlo, genera la estructura ( Bitmap Index Scan) llamada bitmapque en mi caso se genera al generar dos mapas de bits de los índices y realizarlos BITWISE AND. Dado que el mapa de bits se ha generado, ahora puede leer la tabla de manera óptima en un orden secuencial, evitando innecesarios heap I/O-operations.

Ese es el lugar donde surgen muchas preguntas.

PREGUNTA: Tenemos solo un mapa de bits. ¿Cómo sabe PostgreSQL con solo un mapa de bits algo sobre el orden físico de las filas? ¿O genera el mapa de bits para que cualquier elemento del mismo pueda asignarse fácilmente al puntero a una página? Si es así, eso lo explica todo, pero es solo mi suposición.

Entonces, ¿podemos decir simplemente que bitmap heap scan -> bitmap index scanes como un escaneo secuencial pero solo de la parte apropiada de la tabla?

¿Cómo sabe PostgreSQL con solo un mapa de bits algo sobre el orden físico de las filas?

El mapa de bits es un bit por página de montón. La exploración de índice de mapa de bits establece los bits en función de la dirección de la página de montón a la que apunta la entrada de índice.

Entonces, cuando va a hacer el escaneo del montón de mapa de bits, solo hace un escaneo lineal de la tabla, leyendo el mapa de bits para ver si debería molestarse con una página en particular o buscarla.

¿O genera el mapa de bits para que cualquier elemento del mismo pueda asignarse fácilmente al puntero a una página?

No, el mapa de bits corresponde 1: 1 a las páginas de montón.

Escribí un poco más sobre esto aquí .

OK, parece que podría estar malentendido lo que significa "mapa de bits" en este contexto.

No se crea una cadena de bits como "101011" para cada página de montón, o cada lectura de índice, o lo que sea.

Todo el mapa de bits es una matriz de bits única , con tantos bits como páginas de montón en la relación que se está escaneando.

La primera exploración de índice crea un mapa de bits, comenzando con todas las entradas 0 (falso). Cada vez que se encuentra una entrada de índice que coincide con la condición de búsqueda, la dirección de almacenamiento dinámico a la que apunta esa entrada de índice se busca como un desplazamiento en el mapa de bits, y ese bit se establece en 1 (verdadero). Entonces, en lugar de buscar directamente en la página del montón, la exploración del índice de mapa de bits busca la posición de bit correspondiente en el mapa de bits.

El segundo y más escaneos de índice de mapa de bits hacen lo mismo con los otros índices y las condiciones de búsqueda en ellos.

Luego, cada mapa de bits se une con AND. El mapa de bits resultante tiene un bit para cada página de montón, donde los bits son verdaderos solo si fueran verdaderos en todos los escaneos de índice de mapa de bits individuales, es decir, la condición de búsqueda coincida con cada escaneo de índice. Estas son las únicas páginas de montón que debemos molestarnos en cargar y examinar. Dado que cada página de almacenamiento dinámico puede contener varias filas, entonces tenemos que examinar cada fila para ver si cumple con todas las condiciones; de eso se trata la parte "recheck cond".

Una cosa crucial para entender con todo esto es que la dirección de tupla en una entrada de índice apunta a la fila ctid, que es una combinación del número de página del montón y el desplazamiento dentro de la página del montón. Un escaneo de índice de mapa de bits ignora los desplazamientos, ya que comprobará toda la página de todos modos y establece el bit si alguna fila de esa página coincide con la condición.

Ejemplo gráfico

Heap, one square = one page:
+---------------------------------------------+
|c____u_____X___u___X_________u___cXcc______u_|
+---------------------------------------------+
Rows marked c match customers pkey condition.
Rows marked u match username condition.
Rows marked X match both conditions.


Bitmap scan from customers_pkey:
+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
+---------------------------------------------+
One bit per heap page, in the same order as the heap
Bits 1 when condition matches, 0 if not

Bitmap scan from ix_cust_username:
+---------------------------------------------+
|000001000001000100010000000001000010000000010| bitmap 2
+---------------------------------------------+

Una vez que se crean los mapas de bits, se realiza un AND bit a bit en ellos:

+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
|000001000001000100010000000001000010000000010| bitmap 2
 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
|000000000001000000010000000000000010000000000| Combined bitmap
+-----------+-------+--------------+----------+
            |       |              |
            v       v              v
Used to scan the heap only for matching pages:
+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+

La exploración de montón de mapa de bits luego busca el inicio de cada página y lee la página:

+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+
seek------->^seek-->^seek--------->^
            |       |              |
            ------------------------
            only these pages read

y cada página leída se vuelve a verificar en función de la condición, ya que puede haber> 1 fila por página y no todas coinciden necesariamente con la condición.

Consulte mi publicación de blog https://rajeevrastogi.blogspot.in/2018/02/bitmap-scan-in-postgresql.html?showComment=1518410565792#c4647352762092142586 para obtener una descripción detallada del escaneo de mapa de bits en PostgreSQL.

Descripción general de la funcionalidad rápida del escaneo de mapa de bits:

1. Bitmap Heap scan solicita una tupla de Bitmap Index Scan.

2. El escaneo de índice de mapa de bits escanea el índice según la condición casi de la misma manera que en el escaneo de índice normal. Pero en lugar de devolver el TID (que consiste en el número de página y el desplazamiento dentro de ese) correspondiente a los datos del montón, agrega esos TID en un mapa de bits. Para una comprensión simple, puede considerar que este mapa de bits contiene hash de todas las páginas (hash basado en el número de página) y cada entrada de página contiene una matriz de todos los desplazamientos dentro de esa página.

3. Luego, la exploración de montón de mapa de bits lee el mapa de bits para obtener datos de montón correspondientes al número de página almacenado y al desplazamiento. Luego verifica la visibilidad, la calificación, etc. y devuelve la tupla en función del resultado de todas estas verificaciones.