En los artículos anteriores discutimos el motor de indexación PostgreSQL y la interfaz de los métodos de acceso, así como los índices hash , B-trees , GiST , SP-GiST , GIN , RUM y BRIN . Pero aún tenemos que mirar los índices de Bloom.

Bloom

Concepto general

Un filtro clásico de Bloom es una estructura de datos que nos permite verificar rápidamente la pertenencia de un elemento en un conjunto. El filtro es muy compacto, pero permite falsos positivos: puede considerar erróneamente que un elemento es miembro de un conjunto (falso positivo), pero no está permitido considerar que un elemento de un conjunto no sea miembro (falso negativo) .

El filtro es una matriz de $$$m$ bits (también llamada firma ) que inicialmente se rellena con ceros. $$$k$ Se eligen diferentes funciones hash que asignan cualquier elemento del conjunto a $$$k$ partes de la firma. Para agregar un elemento al conjunto, necesitamos establecer cada uno de estos bits en la firma en uno. En consecuencia, si todos los bits correspondientes a un elemento se establecen en uno, el elemento puede ser miembro del conjunto, pero si al menos un bit es igual a cero, el elemento no está seguro en el conjunto.

En el caso de un DBMS, en realidad tenemos $$$N$ filtros separados creados para cada fila de índice. Como regla general, se incluyen varios campos en el índice, y son los valores de estos campos los que componen el conjunto de elementos para cada fila.

Al elegir la longitud de la firma $$$m$ , podemos encontrar una compensación entre el tamaño del índice y la probabilidad de falsos positivos. El área de aplicación para el índice de Bloom es tablas grandes, significativamente "anchas" que deben consultarse utilizando filtros en cada uno de los campos. Este método de acceso, como BRIN, puede considerarse como un acelerador de la exploración secuencial: todas las coincidencias encontradas por el índice deben volverse a verificar con la tabla, pero existe la posibilidad de evitar considerar la mayoría de las filas.

Estructura

Ya hemos discutido los árboles de firmas en el contexto del método de acceso GiST . A diferencia de estos árboles, el índice de Bloom es una estructura plana. Consiste en una metapágina seguida de páginas regulares con filas de índice. Cada fila de índice contiene una firma y una referencia a una fila de tabla (TID), como se muestra esquemáticamente en la figura.

Creación y elección de valores de parámetros.

Al crear el índice Bloom, se especifica un tamaño total de la firma ("longitud"), así como el número de bits que se establecerán para cada campo individual incluido en el índice ("col1" - "col32"):

create index on ... using bloom(...) with (length=..., col1=..., col2=..., ...); 

La forma de especificar el número de bits parece extraña: estos números deben ser parámetros de una clase de operador en lugar del índice. La cuestión es que las clases de operador no pueden parametrizarse actualmente, aunque se está trabajando en esto .

Desafortunadamente, no hay más progreso en esto.

¿Cómo podemos elegir valores adecuados? La teoría establece que dada la probabilidad $$$p$ de un filtro para devolver un falso positivo, el número óptimo de bits de firma se puede estimar como $$$m = −n \ log_2 p / \ ln 2$ donde $$$n$ es el número de campos en el índice y el número de bits a configurar es $$$k = - \ log_2 p$ .

La firma se almacena dentro del índice como una matriz de números enteros de dos bytes, por lo que el valor de $$$m$ se puede redondear de forma segura a $$$16$ .

Al elegir la probabilidad $$$p$ , debemos tener en cuenta el tamaño del índice, que será aproximadamente igual $$$(m / 8 + 6) N$ donde $$$N$ es el número de filas en la tabla y $$$6$ es el tamaño del puntero TID en bytes.

Algunos puntos a tener en cuenta:

• La probabilidad $$$p$ de un falso positivo se relaciona con un filtro, por lo tanto, esperamos obtener $$$Np$ falsos positivos durante el escaneo de la tabla (por supuesto, para una consulta que devuelve pocas filas). Por ejemplo, para una tabla con un millón de filas y la probabilidad 0.01, en el plan de consulta, en promedio, podemos esperar "Filas eliminadas por la comprobación de índice: 10000".
• El filtro Bloom es una estructura probabilística. Tiene sentido hablar de números específicos solo cuando se promedian muchos valores, mientras que en cada caso particular, podemos obtener lo que podamos pensar.
• Las estimaciones anteriores se basan en un modelo matemático idealizado y algunos supuestos. En la práctica, es probable que el resultado sea peor. Por lo tanto, no sobreestimes las fórmulas: son solo un medio para elegir valores iniciales para futuros experimentos.
• Para cada campo individualmente, el método de acceso nos permite elegir el número de bits que se establecerán. Hay una suposición razonable de que en realidad el número óptimo depende de la distribución de los valores en la columna. Para profundizar, puede leer este artículo (las referencias a otras investigaciones son bienvenidas). Pero vuelva a leer el artículo anterior primero.

Actualización

Cuando se inserta una nueva fila en una tabla, se crea una firma: para los valores de todos los campos indexados, todos sus bits correspondientes se establecen en uno. En teoría, debemos tener k funciones hash diferentes, mientras que en la práctica es suficiente el generador de números pseudoaleatorios, cuya semilla se elige cada vez con la ayuda de la única función hash.

Un filtro regular de Bloom no admite la eliminación de elementos, pero esto no es necesario para el índice de Bloom: cuando se elimina una fila de la tabla, se elimina toda la firma, junto con la fila del índice.

Como de costumbre, una actualización consiste en la eliminación de la versión de fila obsoleta y la inserción de la nueva (la firma se calcula desde cero).

Escaneo

Dado que lo único que puede hacer el filtro Bloom es verificar la pertenencia de un elemento en un conjunto, la única operación admitida por el índice Bloom es una verificación de igualdad (como en el índice hash).

Como ya mencionamos, el índice de Bloom es plano, por lo que en el curso del acceso al índice, siempre se lee de forma sucesiva y completa. En el curso de la lectura, se construye un mapa de bits, que luego se utiliza para acceder a la tabla.

En un acceso de índice regular, se supone que habrá que leer pocas filas de índice y, además, pueden volver a necesitarse pronto, por lo tanto, se almacenan en una memoria caché de búfer. La lectura del índice de Bloom, sin embargo, es en realidad una exploración secuencial. Para evitar desalojar información útil del caché, la lectura se realiza a través de un pequeño anillo de almacenamiento intermedio, exactamente de la misma manera que para el análisis secuencial de tablas.

Debemos tener en cuenta que cuanto mayor sea el tamaño del índice de Bloom, menos atractivo le parecerá al planificador. Esta dependencia es lineal, a diferencia de los índices en forma de árbol.

Ejemplo

Mesa

Veamos el índice de Bloom con un ejemplo de una gran tabla de "vuelos_bi" del artículo anterior . Para recordarle, el tamaño de esta tabla es de 4 GB con aproximadamente 30 millones de filas. Definición de la tabla:

 demo=# \d flights_bi 

  Table "bookings.flights_bi" Column | Type | Collation | Nullable | Default --------------------+--------------------------+-----------+----------+--------- airport_code | character(3) | | | airport_coord | point | | | airport_utc_offset | interval | | | flight_no | character(6) | | | flight_type | text | | | scheduled_time | timestamp with time zone | | | actual_time | timestamp with time zone | | | aircraft_code | character(3) | | | seat_no | character varying(4) | | | fare_conditions | character varying(10) | | | passenger_id | character varying(20) | | | passenger_name | text | | | 

Primero creemos la extensión: aunque el índice Bloom está incluido en una entrega estándar que comienza con la versión 9.6, no está disponible de forma predeterminada.

 demo=# create extension bloom; 

La última vez pudimos indexar tres campos usando BRIN ("horario_programado", "hora_actual", "aeropuerto_utc_offset"). Dado que los índices de Bloom no dependen del orden físico de los datos, intentemos incluir casi todos los campos de la tabla en el índice. Sin embargo, excluyamos los campos de hora ("horario_programado" y "hora_actual"): el método solo admite la comparación para la igualdad, pero una consulta para la hora exacta apenas es interesante para nadie (podríamos, sin embargo, construir el índice en una expresión, redondeando el tiempo a un día, pero no haremos esto). También tendremos que excluir las coordenadas geográficas de los aeropuertos ("airport_coord"): de cara al futuro, el tipo de "punto" no es compatible.

Para elegir los valores de los parámetros, configuremos la probabilidad de un falso positivo en 0.01 (teniendo en cuenta que en realidad obtendremos más). Las fórmulas anteriores para $$$n = 9$ y $$$N = 30 \, 000 \, $ 00$ proporcione el tamaño de firma de 96 bits y sugiera configurar 7 bits por elemento. El tamaño estimado del índice es de 515 MB (aproximadamente un octavo de la tabla).

(Con el tamaño mínimo de firma de 16 bits, las fórmulas prometen un tamaño de índice que es dos veces más pequeño, pero permiten confiar solo en la probabilidad de 0.5, que es muy pobre).

Clases de operador

Entonces, intentemos crear el índice.

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 ERROR: data type character has no default operator class for access method "bloom" HINT: You must specify an operator class for the index or define a default operator class for the data type. 

Desafortunadamente, la extensión nos proporciona solo dos clases de operadores:

 demo=# select opcname, opcintype::regtype from pg_opclass where opcmethod = (select oid from pg_am where amname = 'bloom') order by opcintype::regtype::text; 

  opcname | opcintype ----------+----------- int4_ops | integer text_ops | text (2 rows) 

Pero afortunadamente, también es bastante fácil crear clases similares para otros tipos de datos. Una clase de operador para el método de acceso Bloom debe contener exactamente un operador - igualdad - y exactamente una función auxiliar - hashing. La forma más sencilla de encontrar los operadores y funciones necesarios para un tipo arbitrario es buscar en el catálogo del sistema las clases de operadores del método "hash":

 demo=# select distinct opc.opcintype::regtype::text, amop.amopopr::regoperator, ampr.amproc from pg_am am, pg_opclass opc, pg_amop amop, pg_amproc ampr where am.amname = 'hash' and opc.opcmethod = am.oid and amop.amopfamily = opc.opcfamily and amop.amoplefttype = opc.opcintype and amop.amoprighttype = opc.opcintype and ampr.amprocfamily = opc.opcfamily and ampr.amproclefttype = opc.opcintype order by opc.opcintype::regtype::text; 

  opcintype | amopopr | amproc -----------+----------------------+-------------- abstime | =(abstime,abstime) | hashint4 aclitem | =(aclitem,aclitem) | hash_aclitem anyarray | =(anyarray,anyarray) | hash_array anyenum | =(anyenum,anyenum) | hashenum anyrange | =(anyrange,anyrange) | hash_range ... 

Crearemos dos clases faltantes utilizando esta información:

 demo=# CREATE OPERATOR CLASS character_ops DEFAULT FOR TYPE character USING bloom AS OPERATOR 1 =(character,character), FUNCTION 1 hashbpchar; demo=# CREATE OPERATOR CLASS interval_ops DEFAULT FOR TYPE interval USING bloom AS OPERATOR 1 =(interval,interval), FUNCTION 1 interval_hash; 

Una función hash no está definida para puntos (tipo "punto"), y es por esta razón que no podemos construir el índice Bloom en dicho campo (al igual que no podemos realizar una unión hash en campos de este tipo).

Intentando de nuevo:

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 CREATE INDEX 

El tamaño del índice es de 526 MB, que es algo mayor de lo esperado. Esto se debe a que la fórmula no tiene en cuenta la sobrecarga de la página.

 demo=# select pg_size_pretty(pg_total_relation_size('flights_bi_bloom')); 

  pg_size_pretty ---------------- 526 MB (1 row) 

Consultas

Ahora podemos realizar búsquedas usando varios criterios, y el índice lo admitirá.

Como ya mencionamos, el filtro Bloom es una estructura probabilística, por lo tanto, la eficiencia depende en gran medida de cada caso particular. Por ejemplo, veamos las filas relacionadas con dos pasajeros, Miroslav Sidorov:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=2639.010..3010.692 rows=2 loops=1) Recheck Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Rows Removed by Index Recheck: 38562 Heap Blocks: exact=21726 -> Bitmap Index Scan on flights_bi_bloom (actual time=1065.191..1065.191 rows=38564 loops=1) Index Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Planning time: 0.109 ms Execution time: 3010.736 ms 

y Marfa Soloveva:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MARFA SOLOVEVA'; 

  QUERY PLAN --------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=9980.884..10142.684 rows=2 loops=1) Recheck Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Rows Removed by Index Recheck: 3950168 Heap Blocks: exact=45757 lossy=67332 -> Bitmap Index Scan on flights_bi_bloom (actual time=1037.588..1037.588 rows=212972 loops=1) Index Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Planning time: 0.157 ms Execution time: 10142.730 ms 

En un caso, el filtro permitió solo 40 mil falsos positivos y hasta 4 millones de ellos en el otro ("Filas eliminadas por la comprobación de índice"). Los tiempos de ejecución de las consultas difieren en consecuencia.

Y los siguientes son los resultados de buscar las mismas filas por la ID del pasajero en lugar de por el nombre. Miroslav:

 demo=# explain(costs off,analyze) demo-# select * from flights_bi where passenger_id='5864 006033'; 

  QUERY PLAN ------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=13747.305..16907.387 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '5864 006033'::text) Rows Removed by Index Recheck: 9620258 Heap Blocks: exact=50510 lossy=165722 -> Bitmap Index Scan on flights_bi_bloom (actual time=937.202..937.202 rows=426474 loops=1) Index Cond: ((passenger_id)::text = '5864 006033'::text) Planning time: 0.110 ms Execution time: 16907.423 ms 

Y marfa:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_id='2461 559238'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=3881.615..3934.481 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '2461 559238'::text) Rows Removed by Index Recheck: 30669 Heap Blocks: exact=27513 -> Bitmap Index Scan on flights_bi_bloom (actual time=1084.391..1084.391 rows=30671 loops=1) Index Cond: ((passenger_id)::text = '2461 559238'::text) Planning time: 0.120 ms Execution time: 3934.517 ms 

Las eficiencias difieren mucho nuevamente, y esta vez Marfa tuvo más suerte.

Tenga en cuenta que la búsqueda por dos campos simultáneamente se realizará de manera mucho más eficiente ya que la probabilidad de un falso positivo $$$p$ se convierte en $$$p ^ 2$ :

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV' and passenger_id='5864 006033'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=872.593..877.915 rows=2 loops=1) Recheck Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Rows Removed by Index Recheck: 357 Heap Blocks: exact=356 -> Bitmap Index Scan on flights_bi_bloom (actual time=832.041..832.041 rows=359 loops=1) Index Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Planning time: 0.524 ms Execution time: 877.967 ms 

Sin embargo, la búsqueda con booleano "o" no es compatible en absoluto; Esta es una limitación de un planificador en lugar del método de acceso. Por supuesto, queda una opción para leer el índice dos veces, construir dos mapas de bits y unirlos, pero es muy probable que sea demasiado costoso para elegir este plan.

Comparación con BRIN y Hash

Las áreas de aplicación de los índices Bloom y BRIN obviamente se cruzan. Estas son tablas grandes para las cuales es deseable asegurar la búsqueda por diferentes campos, sacrificándose la precisión de la búsqueda a la compacidad.

Los índices BRIN son más compactos (por ejemplo, hasta decenas de megabytes en nuestro ejemplo) y pueden admitir la búsqueda por rango, pero tienen una fuerte limitación relacionada con el orden físico de los datos en un archivo. Los índices de floración son más grandes (cientos de megabytes), pero no tienen limitaciones, excepto la disponibilidad de una función hash adecuada.

Al igual que los índices Bloom, los índices hash admiten la única operación de verificación de igualdad. El índice hash asegura la precisión de búsqueda que es inaccesible para Bloom, pero el tamaño del índice es mucho mayor (en nuestro ejemplo, un gigabyte para un solo campo, y el índice hash no se puede crear en varios campos).

Propiedades

Como de costumbre, veamos las propiedades de Bloom ( ya se han proporcionado consultas ).

Las siguientes son las propiedades del método de acceso:

  amname | name | pg_indexam_has_property --------+---------------+------------------------- bloom | can_order | f bloom | can_unique | f bloom | can_multi_col | t bloom | can_exclude | f 

Evidentemente, el método de acceso nos permite construir un índice en varias columnas. Apenas tiene sentido crear el índice de Bloom en una columna.

Las siguientes propiedades de capa de índice están disponibles:

  name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | f bitmap_scan | t backward_scan | f 

La única técnica de escaneo disponible es el escaneo de mapa de bits. Dado que el índice siempre se escanea por completo, no tiene sentido implementar un acceso regular al índice que devuelva las filas TID por TID.

  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 

Solo hay guiones aquí; el método ni siquiera puede manipular NULLs.

Y finalmente:

No es imposible que esta serie de artículos continúe en el futuro, cuando aparezcan nuevos tipos de interés de índice, pero es hora de detenerse ahora.

Me gustaría expresar mi agradecimiento a mis colegas de Postgres Professional (algunos de ellos son los autores de muchos métodos de acceso discutidos) por leer los borradores y proporcionar sus comentarios. Y, sin duda, les agradezco su paciencia y sus valiosos comentarios. Su atención me animó a llegar a este punto. Gracias