A few weeks back I was staring at an EXPLAIN ANALYZE output, feeling pretty good about myself. I knew the two big scan types — Seq Scan and Index Scan — and I thought that covered it. Full table, or use the index. Simple.
Then I ran a query and saw this:
Bitmap Index Scan
Bitmap Heap Scan
Two lines I didn't recognize. My first reaction was to just ignore it and move on — but that never sits right with me, so I went down the rabbit hole. What I found actually changed how I think about databases.
Picture a librarian, not a computer
Here's the mental model that finally made it click for me.
Imagine you ask a librarian for every book about "Engineering." A librarian doing an Index Scan would work like this: check the catalog, walk to shelf 12, grab the book, walk back, check the catalog again, walk to shelf 47, grab the next book, walk back... For 10 books, that's fine. For 10,000 books scattered across the building? You'd fire that librarian.
A Seq Scan librarian does the opposite — ignores the catalog entirely and just walks every single shelf in the building, checking every book. Wasteful if you only needed a handful, but honestly not bad if you needed most of the books anyway.
Then there's the librarian who does something smarter. Before walking anywhere, they sit down with the catalog and write out a full list: "shelf 4, shelf 9, shelf 9 again, shelf 12, shelf 30." Then they walk the building once, in order, picking up every book along the way without doubling back.
That third librarian is a Bitmap Scan. And once I saw it that way, the Postgres version stopped feeling abstract.
What Postgres is actually doing
It happens in two acts.
Act one — Bitmap Index Scan. Postgres goes through the index, but instead of fetching rows as it finds them, it just marks down where the matches live — a simple map of "yes, this page has something I need." No data is touched yet. Just the map.
Act two — Bitmap Heap Scan. Now Postgres walks the actual table, but it follows that map in physical order instead of chasing matches one by one. Fewer detours, fewer random jumps, way less wasted motion.
That's it. That's the whole trick — look before you leap, and leap in order.
Why this matters more than it sounds
Random disk access is one of the slowest things a database can do. Every time it jumps somewhere new, there's a cost. So Postgres' planner is constantly asking: "is this query going to touch so few rows that random jumping is fine? Or so many rows that I should just read everything? Or is it somewhere annoyingly in the middle?"
That "annoying middle" is exactly where bitmap scans live. Say you've got a million employees and you're looking for everyone in Engineering:
SELECT * FROM employees WHERE department = 'Engineering';
- Only a tiny sliver of the table matches? Index Scan — a few random jumps are cheap enough.
- About 15% of the table matches? Bitmap Scan — too many for random jumps, too few to justify reading it all.
- More than half the table matches? Seq Scan — at that point, just read everything.
The part that actually impressed me
Here's what made me sit up, though. Bitmaps aren't limited to one index — Postgres can build two of them and merge them before ever touching the table:
SELECT * FROM employees
WHERE department = 'Engineering' AND salary > 100000;
One bitmap from the department index, one from the salary index, combined with a quick AND — and only then does it go fetch rows. A regular index scan has no clean way to do that. This, to me, is the real reason bitmap scans exist.
One honest caveat
A bitmap only tells Postgres which pages to check — it still has to visit the table and confirm each row is actually visible (thanks to how MVCC works under the hood). And if the matching set is so big the bitmap can't track individual rows anymore, Postgres quietly downgrades to tracking whole pages instead. You'll spot this in the plan as Recheck Cond — Postgres double-checking the condition itself once it gets to the page, since the bitmap only promised "something here," not "this exact row."
Where I landed
I used to think "index = automatically fast." Turns out that's only true when few rows match. Once the number of matches climbs, blindly following the index becomes its own kind of slow — and that's the gap bitmap scans are built to fill.
So next time Bitmap Index Scan shows up in your EXPLAIN, don't skim past it. It's Postgres quietly doing the librarian thing — mapping first, walking second.
