A melhor explicação vem de Tom Lane, que é o autor do algoritmo, a menos que eu esteja enganado. Veja também o artigo da Wikipédia.

Em suma, é um pouco como uma varredura seq. A diferença é que, em vez de visitar todas as páginas do disco, um índice de bitmap varre os índices aplicáveis ​​dos ANDs e ORs juntos e visita apenas as páginas do disco necessárias.

Isso é diferente de uma varredura de índice, onde o índice é visitado linha por linha em ordem - o que significa que uma página de disco pode ser visitada várias vezes.

Re:a pergunta no seu comentário... Sim, é exatamente isso.

Uma varredura de índice percorrerá as linhas uma a uma, abrindo páginas de disco repetidamente, quantas vezes forem necessárias (algumas, é claro, permanecerão na memória, mas você entendeu).

Uma varredura de índice de bitmap abrirá sequencialmente uma pequena lista de páginas de disco e capturará todas as linhas aplicáveis ​​em cada uma (daí o chamado recheck cond que você vê nos planos de consulta).

Observe, como um aparte, como a ordem de agrupamento/linha afeta os custos associados com qualquer método. Se as linhas estiverem espalhadas em uma ordem aleatória, um índice de bitmap será mais barato. (E, de fato, se eles são realmente todos sobre o lugar, uma varredura seq será mais barata, uma vez que uma varredura de índice de bitmap não é sem alguma sobrecarga.)