De beste verklaring komt van Tom Lane, de auteur van het algoritme, tenzij ik me vergis. Zie ook het wikipedia-artikel.
Kortom, het lijkt een beetje op een seq-scan. Het verschil is dat, in plaats van elke schijfpagina te bezoeken, een bitmapindex AND's en OR's toepasselijke indexen samen scant, en alleen de schijfpagina's bezoekt die nodig zijn.
Dit is anders dan een indexscan, waarbij de index rij voor rij in volgorde wordt bezocht -- wat betekent dat een schijfpagina meerdere keren kan worden bezocht.
Re:de vraag in je reactie... Ja, dat is het precies.
Een indexscan doorloopt de rijen één voor één, waarbij schijfpagina's keer op keer worden geopend, zo vaak als nodig is (sommige blijven natuurlijk in het geheugen, maar u begrijpt het punt).
Een bitmapindexscan opent achtereenvolgens een korte lijst met schijfpagina's en pakt elke toepasselijke rij in elke pagina (vandaar de zogenaamde recheck-cond die u in queryplannen ziet).
Merk terzijde op hoe clustering/rijvolgorde van invloed is op de bijbehorende kosten bij beide methoden. Als rijen overal in willekeurige volgorde staan, is een bitmapindex goedkoper. (En, in feite, als ze echt allemaal zijn in plaats daarvan zal een seq-scan het goedkoopst zijn, aangezien een bitmap-indexscan niet zonder enige overhead is.)