Nejlepší vysvětlení pochází od Toma Lanea, který je autorem algoritmu, pokud se nepletu. Viz také článek na wikipedii.
Zkrátka je to trochu jako seq scan. Rozdíl je v tom, že namísto navštěvování každé stránky na disku bitmapový index skenuje příslušné indexy AND a OR společně a navštěvuje pouze stránky disku, které potřebuje.
To se liší od prohledávání indexu, kde je index navštěvován řádek po řádku v pořadí – což znamená, že stránka disku může být navštívena vícekrát.
Re:otázka ve vašem komentáři... Jo, to je přesně ono.
Skenování indexu bude procházet řádky jeden po druhém a znovu a znovu otevírat stránky disku, kolikrát je potřeba (některé samozřejmě zůstanou v paměti, ale rozumíte tomu).
Skenování indexu bitmapy postupně otevře krátký seznam stránek na disku a zachytí všechny použitelné řádky na každé z nich (proto takzvaný stav opětovné kontroly, který vidíte v plánech dotazů).
Povšimněte si jen toho, jak shlukování/pořadí řádků ovlivňuje související náklady u obou metod. Pokud jsou řádky všude v náhodném pořadí, index bitmapy bude levnější. (A ve skutečnosti, pokud jsou opravdu všichni navíc bude sekvenční skenování nejlevnější, protože skenování indexu bitmapy není bez určité režie.)