Thread: Bitmap indexes etc.
Hi! This is not actually a question about performance, but an inquiry to help me understand what is going on. Below this text are two EXPLAIN ANALYZE outputs, before and after VACUUM ANALYZE was run. I have several questions about the proposed plans (mostly the first one). There is only one table in the query, "layout", containing ~10k rows. In it, for each "page_id" there are several (1-10) rows (i.e. there are around 10000/5 unique page_id values). There's an index on "page_id" and I've upped statistics collection on it to 150 at table creation time because sometimes the planner didn't use the index at all. This is PostgreSQL 8.1.0. - what does "Bitmap Heap Scan" phase do? - what is "Recheck condition" and why is it needed? - why are proposed "width" fields in the plan different between the two plans? (actually, a nice explanation what exactly are those widths would also be nice :) ) - I thought "Bitmap Index Scan" was only used when there are two or more applicable indexes in the plan, so I don't understand why is it used now? cw2=> explain analyze select * from layout where page_id=10060; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------ Bitmap Heap Scan on layout (cost=2.15..64.21 rows=43 width=60) (actual time=0.043..0.053 rows=4 loops=1) Recheck Cond: (page_id = 10060) -> Bitmap Index Scan on layout_page_id (cost=0.00..2.15 rows=43 width=0) (actual time=0.034..0.034 rows=4 loops=1) Index Cond: (page_id = 10060) Total runtime: 0.112 ms (5 rows) cw2> VACUUM ANALYZE; cw2=> explain analyze select * from layout where page_id=10060; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------- Index Scan using layout_page_id on layout (cost=0.00..12.14 rows=4 width=42) (actual time=0.014..0.025 rows=4 loops=1) Index Cond: (page_id = 10060) Total runtime: 0.076 ms (3 rows) -- Preserve wildlife -- pickle a squirrel today!
Ivan Voras <ivoras@fer.hr> writes: > This is PostgreSQL 8.1.0. > - what does "Bitmap Heap Scan" phase do? A plain indexscan fetches one tuple-pointer at a time from the index, and immediately visits that tuple in the table. A bitmap scan fetches all the tuple-pointers from the index in one go, sorts them using an in-memory "bitmap" data structure, and then visits the table tuples in physical tuple-location order. The bitmap scan improves locality of reference to the table at the cost of more bookkeeping overhead to manage the "bitmap" data structure --- and at the cost that the data is no longer retrieved in index order, which doesn't matter for your query but would matter if you said ORDER BY. > - what is "Recheck condition" and why is it needed? If the bitmap gets too large we convert it to "lossy" style, in which we only remember which pages contain matching tuples instead of remembering each tuple individually. When that happens, the table-visiting phase has to examine each tuple on the page and recheck the scan condition to see which tuples to return. > - why are proposed "width" fields in the plan different between the two > plans? Updated statistics about average column widths, presumably. > (actually, a nice explanation what exactly are those widths would also > be nice :) ) Sum of the average widths of the columns being fetched from the table. > - I thought "Bitmap Index Scan" was only used when there are two or more > applicable indexes in the plan, so I don't understand why is it used > now? True, we can combine multiple bitmaps via AND/OR operations to merge results from multiple indexes before visiting the table ... but it's still potentially worthwhile even for one index. A rule of thumb is that plain indexscan wins for fetching a small number of tuples, bitmap scan wins for a somewhat larger number of tuples, and seqscan wins if you're fetching a large percentage of the whole table. regards, tom lane
On Mon, 26 Dec 2005, Tom Lane wrote: > ...snip... Thanks, it's a very good explanation! -- Preserve wildlife -- pickle a squirrel today!