Nos artigos anteriores, discutimos o mecanismo de indexação do PostgreSQL e a interface dos métodos de acesso, bem como índices de hash , árvores B , GiST , SP-GiST , GIN , RUM e BRIN . Mas ainda precisamos examinar os índices da Bloom.

Bloom

Conceito geral

Um filtro Bloom clássico é uma estrutura de dados que permite verificar rapidamente a associação de um elemento em um conjunto. O filtro é altamente compacto, mas permite falsos positivos: pode considerar erroneamente que um elemento é um membro de um conjunto (falso positivo), mas não é permitido considerar que um elemento de um conjunto não seja um membro (falso negativo) .

O filtro é uma matriz de $$$m$ bits (também chamados de assinatura ) que são preenchidos inicialmente com zeros. $$$k$ diferentes funções de hash são escolhidas que mapeiam qualquer elemento do conjunto para $$$k$ bits da assinatura. Para adicionar um elemento ao conjunto, precisamos definir cada um desses bits na assinatura como um. Consequentemente, se todos os bits correspondentes a um elemento estiverem definidos como um, o elemento poderá ser um membro do conjunto, mas se pelo menos um bit for igual a zero, o elemento não estará no conjunto com certeza.

No caso de um DBMS, nós realmente temos $$$N$ filtros separados criados para cada linha do índice. Como regra, vários campos são incluídos no índice e são os valores desses campos que compõem o conjunto de elementos para cada linha.

Escolhendo o comprimento da assinatura $$$m$ , podemos encontrar uma troca entre o tamanho do índice e a probabilidade de falsos positivos. A área de aplicação do índice Bloom é grande, com tabelas significativamente "amplas" a serem consultadas usando filtros em cada um dos campos. Esse método de acesso, como o BRIN, pode ser considerado um acelerador da varredura sequencial: todas as correspondências encontradas pelo índice devem ser verificadas novamente com a tabela, mas existe a chance de evitar considerar a maioria das linhas.

Estrutura

Já discutimos árvores de assinatura no contexto do método de acesso do GiST . Diferentemente dessas árvores, o índice Bloom é uma estrutura plana. Consiste em uma metapage seguida por páginas regulares com linhas de índice. Cada linha do índice contém uma assinatura e referência a uma linha da tabela (TID), conforme mostrado esquematicamente na figura.

Criação e escolha dos valores dos parâmetros

Ao criar o índice Bloom, é especificado um tamanho total da assinatura ("comprimento"), bem como o número de bits a serem definidos para cada campo individual incluído no índice ("col1" - "col32"):

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

A maneira de especificar o número de bits parece estranha: esses números devem ser parâmetros de uma classe de operador e não o índice. O fato é que as classes de operadores não podem ser parametrizadas no momento, embora o trabalho esteja em andamento.

Infelizmente, não há mais progresso nisso.

Como podemos escolher valores adequados? A teoria afirma que, dada a probabilidade $$$p$ de um filtro para retornar um falso positivo, o número ideal de bits de assinatura pode ser estimado como $$$m = −n \ log_2 p / \ ln 2$ onde $$$n$ é o número de campos no índice e o número de bits a ser definido é $$$k = - \ log_2 p$ .

A assinatura é armazenada dentro do índice como uma matriz de números inteiros de dois bytes, portanto, o valor de $$$m$ pode ser arredondado com segurança até $$$16$ .

Ao escolher a probabilidade $$$p$ , precisamos levar em consideração o tamanho do índice, que será aproximadamente igual $$$(m / 8 + 6) N$ onde $$$N$ é o número de linhas na tabela e $$$6$ é o tamanho do ponteiro TID em bytes.

Alguns pontos a serem observados:

• A probabilidade $$$p$ de um falso positivo se relaciona a um filtro, portanto, esperamos obter $$$Np$ falsos positivos durante a verificação da tabela (é claro, para uma consulta que retorna poucas linhas). Por exemplo, para uma tabela com um milhão de linhas e a probabilidade 0,01, no plano de consulta, em média, podemos esperar "Linhas removidas pela verificação do índice: 10000".
• O filtro Bloom é uma estrutura probabilística. Faz sentido falar de números específicos apenas quando se calcula a média de muitos valores, enquanto em cada caso específico, podemos obter o que conseguimos pensar.
• As estimativas acima são baseadas em um modelo matemático idealizado e em algumas suposições. Na prática, o resultado provavelmente será pior. Portanto, não superestime as fórmulas: elas são apenas um meio de escolher valores iniciais para experimentos futuros.
• Para cada campo individualmente, o método de acesso permite escolher o número de bits a serem definidos. Há uma suposição razoável de que, na verdade, o número ideal depende da distribuição dos valores na coluna. Para mergulhar mais fundo, você pode ler este artigo (referências a outras pesquisas são bem-vindas). Mas releia o item anterior primeiro.

Atualizando

Quando uma nova linha é inserida em uma tabela, uma assinatura é criada: para valores de todos os campos indexados, todos os seus bits correspondentes são definidos como um. Em teoria, devemos ter k diferentes funções hash, enquanto na prática o gerador de números pseudo-aleatórios é suficiente, cuja semente é escolhida a cada vez com a ajuda da única função hash.

Um filtro Bloom normal não suporta a exclusão de elementos, mas isso não é necessário para o índice Bloom: quando uma linha da tabela é excluída, a assinatura inteira é excluída, juntamente com a linha do índice.

Como de costume, uma atualização consiste na exclusão da versão de linha desatualizada e na inserção da nova (a assinatura sendo calculada a partir do zero).

Digitalização

Como a única coisa que o filtro Bloom pode fazer é verificar a associação de um elemento em um conjunto, a única operação suportada pelo índice Bloom é uma verificação de igualdade (como no índice de hash).

Como já mencionamos, o índice Bloom é plano, portanto, durante o acesso ao índice, ele é sempre lido sucessivamente e inteiramente. No decorrer da leitura, é criado um bitmap, que é usado para acessar a tabela.

Em um acesso regular ao índice, assume-se que poucas linhas do índice precisarão ser lidas e, além disso, elas poderão ser necessárias em breve novamente, portanto, são armazenadas em um cache de buffer. A leitura do índice Bloom, no entanto, é na verdade uma varredura seqüencial. Para impedir a remoção de informações úteis do cache, a leitura é feita através de um pequeno anel de buffer, exatamente da mesma maneira que na varredura seqüencial de tabelas.

Devemos levar em conta que quanto mais o tamanho do índice Bloom, menos atraente ele parecerá para o planejador. Essa dependência é linear, diferente dos índices de árvore.

Exemplo

Quadro

Vejamos o índice Bloom por exemplo de uma grande tabela "flights_bi" do artigo anterior . Para lembrá-lo, o tamanho desta tabela é de 4 GB com aproximadamente 30 milhões de linhas. Definição da tabela:

 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 | | | 

Vamos primeiro criar a extensão: embora o índice Bloom esteja incluído em uma entrega padrão a partir da versão 9.6, ele está indisponível por padrão.

 demo=# create extension bloom; 

Da última vez, pudemos indexar três campos usando BRIN ("horário_ agendado", "horário_atual", "aeroporto_utc_offset"). Como os índices Bloom não dependem da ordem física dos dados, vamos tentar incluir quase todos os campos da tabela no índice. No entanto, vamos excluir os campos de hora ("horário_ agendado" e "horário atual"): o método suporta apenas comparação por igualdade, mas uma consulta por hora exata dificilmente é interessante para ninguém (no entanto, poderíamos criar o índice em uma expressão, arredondando o tempo para um dia, mas não faremos isso). Também teremos que excluir as coordenadas geográficas dos aeroportos ("airport_coord"): olhando para o futuro, o tipo "point" não é suportado.

Para escolher os valores dos parâmetros, vamos definir a probabilidade de um falso positivo como 0,01 (tendo em mente que, na verdade, obteremos mais). As fórmulas acima para $$$n = 9$ e $$$N = 30 \, 000 \, $ 00$ forneça o tamanho da assinatura de 96 bits e sugira definir 7 bits por elemento. O tamanho estimado do índice é de 515 MB (aproximadamente um oitavo da tabela).

(Com o tamanho mínimo de assinatura de 16 bits, as fórmulas prometem o tamanho do índice duas vezes menor, mas permitem confiar apenas na probabilidade de 0,5, o que é muito ruim.)

Classes de operadores

Então, vamos tentar criar o í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. 

Infelizmente, a extensão nos fornece apenas duas classes 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) 

Felizmente, porém, é muito fácil criar classes semelhantes para outros tipos de dados. Uma classe de operador para o método de acesso Bloom deve conter exatamente um hash de operador - igualdade - e exatamente uma função auxiliar -. A maneira mais simples de encontrar os operadores e funções necessários para um tipo arbitrário é procurar no catálogo do sistema as classes de operadores do 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 ... 

Criaremos duas classes ausentes usando essas informações:

 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; 

Uma função de hash não está definida para pontos (tipo "point") e é por esse motivo que não podemos criar o índice Bloom em um campo desse tipo (assim como não podemos executar uma junção de hash em campos desse tipo).

Tentando novamente:

 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 

O tamanho do índice é 526 MB, que é um pouco maior que o esperado. Isso ocorre porque a fórmula não leva em conta a sobrecarga da página.

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

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

Consultas

Agora podemos realizar a pesquisa usando vários critérios, e o índice o apoiará.

Como já mencionamos, o filtro Bloom é uma estrutura probabilística, portanto, a eficiência depende muito de cada caso específico. Por exemplo, vejamos as linhas relacionadas a dois passageiros, 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 

e 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 

Em um caso, o filtro permitiu apenas 40 mil falsos positivos e até 4 milhões deles no outro ("Linhas removidas pela verificação do índice"). Os tempos de execução das consultas diferem de acordo.

E a seguir estão os resultados da pesquisa nas mesmas linhas pelo ID do passageiro, e não pelo nome. 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 

E 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 

As eficiências diferem muito mais uma vez, e desta vez Marfa teve mais sorte.

Observe que a pesquisa por dois campos simultaneamente será feita com muito mais eficiência, pois a probabilidade de um falso positivo $$$p$ se transforma em $$$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 

No entanto, a pesquisa com booleano "ou" não é suportada; essa é uma limitação de um planejador e não do método de acesso. Obviamente, resta uma opção para ler o índice duas vezes, criar dois bitmaps e juntá-los, mas isso provavelmente é muito caro para que esse plano seja escolhido.

Comparação com BRIN e Hash

As áreas de aplicação dos índices Bloom e BRIN obviamente se cruzam. São tabelas grandes para as quais é desejável garantir a pesquisa por campos diferentes, sendo a precisão da pesquisa sacrificada pela compacidade.

Os índices BRIN são mais compactos (digamos, até dezenas de megabytes em nosso exemplo) e podem oferecer suporte à pesquisa por intervalo, mas têm uma forte limitação relacionada à ordenação física dos dados em um arquivo. Os índices de Bloom são maiores (centenas de megabytes), mas não têm limitações, exceto a disponibilidade de uma função de hash adequada.

Como os índices Bloom, os índices de hash suportam a única operação de verificação de igualdade. O índice de hash garante a precisão da pesquisa inacessível para o Bloom, mas o tamanho do índice é bem maior (no nosso exemplo, um gigabyte para apenas um campo e o índice de hash não pode ser criado em vários campos).

Propriedades

Como de costume, vamos examinar as propriedades do Bloom (as consultas já foram fornecidas ).

A seguir estão as propriedades do método de acesso:

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

Evidentemente, o método de acesso nos permite criar um índice em várias colunas. Não faz sentido criar o índice Bloom em uma coluna.

As seguintes propriedades da camada de índice estão disponíveis:

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

A única técnica de verificação disponível é a verificação de bitmap. Como o índice é sempre verificado inteiramente, não faz sentido implementar um acesso regular ao índice que retorne as linhas 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 

Apenas traços estão aqui; o método não pode nem manipular NULLs.

E finalmente:

Não é impossível que essa série de artigos continue no futuro, quando novos tipos de interesse aparecerem, mas é hora de parar agora.

Gostaria de agradecer aos meus colegas do Postgres Professional (alguns deles são os autores de muitos métodos de acesso discutidos) por ler os rascunhos e fornecer seus comentários. E certamente sou grato por sua paciência e comentários valiosos. Sua atenção me incentivou a chegar a esse ponto. Obrigada