Noções básicas sobre “verificação de heap de bitmap” e “verificação de índice de bitmap”

Vou tentar explicar meus mal-entendidos pelo exemplo a seguir.

Eu não entendi os fundamentos do Bitmap Heap Scan Node. Considere a consulta SELECT customerid, username FROM customers WHERE customerid < 1000 AND username <'user100';cujo plano é 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)

Meu entendimento deste nó :

Conforme explicado lá , a bitmap heap scantabela lê os blocos em ordem sequencial, para que não produza sobrecarga de acesso à tabela aleatória, o que acontece exatamente como acontece Index Scan.

Depois de Index Scanfeito, o PostgreSQL não sabe como buscar as linhas da melhor maneira, para evitar desnecessários heap blocks reads(ou hitsse houver um cache quente). Então, para descobrir isso, gera a estrutura ( Bitmap Index Scan) chamada bitmapque, no meu caso, está sendo gerada, gerando dois bitmaps dos índices e executando BITWISE AND. Como o bitmap foi gerado, agora é possível ler a tabela de maneira otimizada em uma ordem seqüencial, evitando desnecessários heap I/O-operations.

É aí que muitas perguntas surgem.

PERGUNTA: Temos apenas um bitmap. Como o PostgreSQL conhece apenas um bitmap sobre a ordem física das linhas? Ou gera o bitmap para que qualquer elemento dele possa ser mapeado para o ponteiro para uma página facilmente? Se assim for, isso explica tudo, mas é apenas o meu palpite.

Então, podemos dizer simplesmente que bitmap heap scan -> bitmap index scané como uma varredura seqüencial, mas apenas da parte apropriada da tabela?

Como o PostgreSQL sabe apenas por um bitmap algo sobre a ordem física das linhas?

O bitmap é um bit por página de heap. A verificação do índice de bitmap define os bits com base no endereço da página da pilha que a entrada do índice aponta.

Portanto, quando ele faz a varredura de heap de bitmap, apenas faz uma varredura linear de tabela, lendo o bitmap para ver se deveria se preocupar com uma página específica ou procurá-la.

Ou gera o bitmap para que qualquer elemento dele possa ser mapeado para o ponteiro para uma página facilmente?

Não, o bitmap corresponde 1: 1 às páginas da pilha.

Eu escrevi um pouco mais sobre isso aqui .

OK, parece que você pode estar entendendo mal o que "bitmap" significa neste contexto.

Não é uma sequência de bits como "101011" criada para cada página da pilha, ou cada índice lido, ou o que seja.

O bitmap inteiro é uma matriz de bit único , com tantos bits quanto páginas de heap na relação que está sendo varrida.

Um bitmap é criado pela primeira varredura de índice, iniciando com todas as entradas 0 (false). Sempre que uma entrada de índice que corresponde à condição de pesquisa é encontrada, o endereço de heap apontado por essa entrada de índice é procurado como um deslocamento no bitmap, e esse bit é definido como 1 (verdadeiro). Portanto, em vez de procurar diretamente a página da pilha, a verificação do índice de bitmap procura a posição de bit correspondente no bitmap.

A segunda e mais verificações de índice de bitmap fazem a mesma coisa com os outros índices e as condições de pesquisa neles.

Cada bitmap é ANDed juntos. O bitmap resultante possui um bit para cada página de heap, onde os bits são verdadeiros apenas se forem verdadeiros em todas as varreduras de índice de bitmap individuais, ou seja, a condição de pesquisa corresponde a cada varredura de índice. Essas são as únicas páginas de pilha que precisamos nos preocupar em carregar e examinar. Como cada página de heap pode conter várias linhas, precisamos examinar cada linha para ver se ela corresponde a todas as condições - é disso que trata a parte "verificar novamente cond".

Uma coisa crucial a entender com tudo isso é que o endereço da tupla em uma entrada de índice aponta para a linha ctid, que é uma combinação do número da página da pilha e o deslocamento dentro da página da pilha. Uma verificação de índice de bitmap ignora os deslocamentos, pois verifica a página inteira de qualquer maneira e define o bit se alguma linha dessa página corresponder à condição.

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

Depois que os bitmaps são criados, um AND bit a bit é executado neles:

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

A varredura de heap de bitmap procura o início de cada página e lê a página:

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

e cada página de leitura é verificada novamente com relação à condição, pois pode haver> 1 linha por página e nem todas necessariamente correspondem à condição.

Consulte minha postagem no blog https://rajeevrastogi.blogspot.in/2018/02/bitmap-scan-in-postgresql.html?showComment=1518410565792#c4647352762092142586 para obter detalhes da descrição da verificação de bitmap no PostgreSQL.

Visão geral da funcionalidade rápida geral da verificação de bitmap:

1. A verificação de heap de bitmap solicita uma tupla na verificação de índice de bitmap.

2. Varredura de índice de bitmap varre o índice de acordo com a condição quase da mesma maneira que na Varredura de índice normal. Mas, em vez de retornar o TID (consistindo no número da página e deslocamento dentro dele) correspondente aos dados do heap, ele adiciona esses TID em um bitmap. Para um entendimento simples, você pode considerar que este bitmap contém o hash de todas as páginas (com base no número da página) e cada entrada de página contém uma matriz de todos os deslocamentos dentro dessa página.

3. A verificação de heap de bitmap lê o bitmap para obter dados de heap correspondentes ao número da página armazenada e deslocamento. Em seguida, verifica a visibilidade, a qualificação etc. e retorna a tupla com base no resultado de todas essas verificações.