bloom proporciona un método de acceso a índices basado en
filtros de Bloom.
Un filtro de Bloom es una estructura de datos eficiente en espacio que se utiliza para comprobar si un elemento pertenece a un conjunto. En el caso de un método de acceso a índices, permite la exclusión rápida de tuplas que no coinciden mediante firmas cuyo tamaño se determina en la creación del índice.
Una firma es una representación con pérdidas de los atributos indexados y, como tal, es propensa a reportar falsos positivos; es decir, se puede reportar que un elemento está en el conjunto cuando no es así. Por lo tanto, los resultados de la búsqueda del índice siempre deben volver a comprobarse utilizando los valores reales de los atributos de la entrada de la tabla (heap). Las firmas más grandes reducen las probabilidades de un falso positivo y, por tanto, reducen el número de visitas inútiles a la tabla, pero, por supuesto, también hacen que el índice sea más grande y, por ende, más lento de escanear.
Este tipo de índice es muy útil cuando una tabla tiene muchos atributos y las consultas comprueban combinaciones arbitrarias de los mismos. Un índice btree tradicional es más rápido que un índice bloom, pero puede requerir muchos índices btree para dar soporte a todas las consultas posibles en situaciones donde solo se necesita un único índice bloom. Ten en cuenta, sin embargo, que los índices bloom solo soportan consultas de igualdad, mientras que los índices btree también pueden realizar búsquedas de desigualdad y de rango.
Un índice bloom acepta los siguientes parámetros en su
cláusula WITH:
length
Longitud de cada firma (entrada de índice) en bits. Se redondea al
múltiplo de 16 más cercano. El valor por defecto es
80 bits y el máximo es 4096.
col1 — col32
Número de bits generados para cada columna del índice. El nombre de cada parámetro
se refiere al número de la columna del índice que controla. El valor por defecto
es 2 bits y el máximo es 4095.
Se ignoran los parámetros de las columnas del índice que no se utilicen realmente.
Este es un ejemplo de creación de un índice bloom:
CREATE INDEX bloomidx ON tbloom USING bloom (i1,i2,i3)
WITH (length=80, col1=2, col2=2, col3=4);
El índice se crea con una longitud de firma de 80 bits, con los atributos
i1 e i2 mapeados a 2 bits, y el atributo i3 mapeado a 4 bits. Podríamos
haber omitido las especificaciones de length, col1,
y col2 ya que tienen los valores por defecto.
Aquí tienes un ejemplo más completo de la definición y el uso del índice bloom, así como una comparación con los índices btree equivalentes. El índice bloom es considerablemente más pequeño que el índice btree y puede ofrecer un mejor rendimiento.
=# CREATE TABLE tbloom AS
SELECT
(random() * 1000000)::int as i1,
(random() * 1000000)::int as i2,
(random() * 1000000)::int as i3,
(random() * 1000000)::int as i4,
(random() * 1000000)::int as i5,
(random() * 1000000)::int as i6
FROM
generate_series(1,10000000);
SELECT 10000000
Un escaneo secuencial sobre esta gran tabla toma mucho tiempo:
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
------------------------------------------------------------------------------------------------------
Seq Scan on tbloom (cost=0.00..213744.00 rows=250 width=24) (actual time=357.059..357.059 rows=0.00 loops=1)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 10000000
Buffers: shared hit=63744
Planning Time: 0.346 ms
Execution Time: 357.076 ms
(6 rows)
Incluso con el índice btree definido, el resultado seguirá siendo un escaneo secuencial:
=# CREATE INDEX btreeidx ON tbloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('btreeidx'));
pg_size_pretty
----------------
386 MB
(1 row)
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
------------------------------------------------------------------------------------------------------
Seq Scan on tbloom (cost=0.00..213744.00 rows=2 width=24) (actual time=351.016..351.017 rows=0.00 loops=1)
Filter: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Filter: 10000000
Buffers: shared hit=63744
Planning Time: 0.138 ms
Execution Time: 351.035 ms
(6 rows)
Tener el índice bloom definido en la tabla es mejor que btree al manejar este tipo de búsqueda:
=# CREATE INDEX bloomidx ON tbloom USING bloom (i1, i2, i3, i4, i5, i6);
CREATE INDEX
=# SELECT pg_size_pretty(pg_relation_size('bloomidx'));
pg_size_pretty
----------------
153 MB
(1 row)
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=1792.00..1799.69 rows=2 width=24) (actual time=22.605..22.606 rows=0.00 loops=1)
Recheck Cond: ((i2 = 898732) AND (i5 = 123451))
Rows Removed by Index Recheck: 2300
Heap Blocks: exact=2256
Buffers: shared hit=21864
-> Bitmap Index Scan on bloomidx (cost=0.00..178436.00 rows=1 width=0) (actual time=20.005..20.005 rows=2300.00 loops=1)
Index Cond: ((i2 = 898732) AND (i5 = 123451))
Index Searches: 1
Buffers: shared hit=19608
Planning Time: 0.099 ms
Execution Time: 22.632 ms
(11 rows)
Ahora bien, el principal problema con la búsqueda btree es que btree es ineficiente cuando las condiciones de búsqueda no limitan la(s) primera(s) columna(s) del índice. Una estrategia mejor para btree es crear un índice independiente en cada columna. Entonces el planificador elegirá algo como esto:
=# CREATE INDEX btreeidx1 ON tbloom (i1);
CREATE INDEX
=# CREATE INDEX btreeidx2 ON tbloom (i2);
CREATE INDEX
=# CREATE INDEX btreeidx3 ON tbloom (i3);
CREATE INDEX
=# CREATE INDEX btreeidx4 ON tbloom (i4);
CREATE INDEX
=# CREATE INDEX btreeidx5 ON tbloom (i5);
CREATE INDEX
=# CREATE INDEX btreeidx6 ON tbloom (i6);
CREATE INDEX
=# EXPLAIN ANALYZE SELECT * FROM tbloom WHERE i2 = 898732 AND i5 = 123451;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on tbloom (cost=9.29..13.30 rows=1 width=24) (actual time=0.032..0.033 rows=0.00 loops=1)
Recheck Cond: ((i5 = 123451) AND (i2 = 898732))
Buffers: shared read=6
-> BitmapAnd (cost=9.29..9.29 rows=1 width=0) (actual time=0.047..0.047 rows=0.00 loops=1)
Buffers: shared hit=6
-> Bitmap Index Scan on btreeidx5 (cost=0.00..4.52 rows=11 width=0) (actual time=0.026..0.026 rows=7.00 loops=1)
Index Cond: (i5 = 123451)
Index Searches: 1
Buffers: shared hit=3
-> Bitmap Index Scan on btreeidx2 (cost=0.00..4.52 rows=11 width=0) (actual time=0.007..0.007 rows=8.00 loops=1)
Index Cond: (i2 = 898732)
Index Searches: 1
Buffers: shared hit=3
Planning Time: 0.264 ms
Execution Time: 0.047 ms
(15 rows)
Aunque esta consulta se ejecuta mucho más rápido que con cualquiera de los índices únicos, pagamos una penalización en el tamaño del índice. Cada uno de los índices btree de una sola columna ocupa 88.5 MB, por lo que el espacio total necesario es de 531 MB, más de tres veces el espacio utilizado por el índice bloom.
Una clase de operadores para índices bloom requiere únicamente una función de hash para el
tipo de datos indexado y un operador de igualdad para la búsqueda. Este ejemplo
muestra la definición de la clase de operadores para el tipo de datos text:
CREATE OPERATOR CLASS text_ops
DEFAULT FOR TYPE text USING bloom AS
OPERATOR 1 =(text, text),
FUNCTION 1 hashtext(text);
Solo se incluyen con el módulo clases de operadores para int4 y text.
Solo se soporta el operador = para la búsqueda. Pero
es posible añadir soporte para arrays con operaciones de unión e intersección
en el futuro.
El método de acceso bloom no soporta
índices UNIQUE.
El método de acceso bloom no soporta la búsqueda de
valores NULL.
Teodor Sigaev <[email protected]>,
Postgres Professional, Moscú, Rusia
Alexander Korotkov <[email protected]>,
Postgres Professional, Moscú, Rusia
Oleg Bartunov <[email protected]>,
Postgres Professional, Moscú, Rusia