Menu
Bitmap scans are a multi-step process that consist of a Bitmap Heap Scan, one or more Bitmap Index Scans and optionally BitmapOr and BitmapAnd operations. The Bitmap Heap Scan reads pages from a bitmap created by the other operations, filtering out any rows that don't match the condition.
Bitmap Heap Scans aren't inherently bad; in fact, they include a built-in optimization to only fetch from disk once we know what we need which can avoid unnecessary duplicate fetches. Fetching rows from disk to satisfy multiple index usage.
A Bitmap Heap Scan is the most common parent node of a Bitmap Index Scan, but a plan may also combine several different Bitmap Index Scans with BitmapAnd or BitmapOr nodes before actually fetching the underlying data. This allows Postgres to use two different indexes at once to execute a query.
In a parallel bitmap heap scan, one process is chosen as the leader. That process performs a scan of one or more indexes and builds a bitmap indicating which table blocks need to be visited. These blocks are then divided among the cooperating processes as in a parallel sequential scan.
The best explanation comes from Tom Lane, which is the algorithm's author unless I'm mistaking. See also the wikipedia article.
In short, it's a bit like a seq scan. The difference is that, rather than visiting every disk page, a bitmap index scan ANDs and ORs applicable indexes together, and only visits the disk pages that it needs to.
This is different from an index scan, where the index is visited row by row in order -- meaning a disk page may get visited multiple times.
Re: the question in your comment... Yep, that's exactly it.
An index scan will go through rows one by one, opening disk pages again and again, as many times as necessary (some will of course stay in memory, but you get the point).
A bitmap index scan will sequentially open a short-list of disk pages, and grab every applicable row in each one (hence the so-called recheck cond you see in query plans).
Note, as an aside, how clustering/row order affects the associated costs with either method. If rows are all over the place in a random order, a bitmap index will be cheaper. (And, in fact, if they're really all over the place, a seq scan will be cheapest, since a bitmap index scan is not without some overhead.)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With