La meilleure explication vient de Tom Lane, qui est l'auteur de l'algorithme, sauf erreur de ma part. Voir aussi l'article de wikipedia.
Bref, c'est un peu comme un seq scan. La différence est que, plutôt que de visiter chaque page de disque, un index bitmap analyse les ET et OU les index applicables ensemble, et ne visite que les pages de disque dont il a besoin.
Ceci est différent d'une analyse d'index, où l'index est visité ligne par ligne dans l'ordre, ce qui signifie qu'une page de disque peut être visitée plusieurs fois.
Re :la question dans votre commentaire... Oui, c'est exactement ça.
Un parcours d'index parcourra les lignes une par une, ouvrant les pages du disque encore et encore, autant de fois que nécessaire (certaines resteront bien sûr en mémoire, mais vous avez compris).
Une analyse d'index bitmap ouvrira séquentiellement une liste restreinte de pages de disque et saisira chaque ligne applicable dans chacune d'elles (d'où la soi-disant cond de revérification que vous voyez dans les plans de requête).
Notez, en aparté, comment le regroupement/ordre des lignes affecte les coûts associés à l'une ou l'autre méthode. Si les lignes sont partout dans un ordre aléatoire, un index bitmap sera moins cher. (Et, en fait, s'ils sont vraiment tous à la place, un scan seq sera le moins cher, car un scan d'index bitmap n'est pas sans surcoût.)
