6

I'm implementing pagination and sorting of rows in, let's say, products table, using multicolumn index on category, score and id.

-- index
create index category_score_id on products(category, score, id)
  where active = true;

-- selecting first page
select * from products where
  category = 1
  and active = true
order by score desc, id desc
limit 30;

-- selecting following pages
select * from products where
  category = 1
  and active = true
  and (score, id) < (893, 102458)  -- values from previous page
order by score desc, id desc
limit 30;

This works perfectly fine and as expected, using only index scan:

-- explain analyze of 2-nd query:
Limit  (cost=0.00..99.52 rows=30 width=2591) (actual time=0.090..0.179 rows=30 loops=1)
  ->  Index Scan Backward using category_score_id on products  (cost=0.00..76435.07 rows=23041 width=2591) (actual time=0.089..0.172 rows=30 loops=1)
        Index Cond: ((category = 1) AND (ROW(score, id) < ROW(893, 102458)))
Total runtime: 0.085 ms

What I am curious about is why the following query requires extra Bitmap Heap Scan:

select count(*) from products where
  category = 1
  and active = true;
-- explain analyze:
Aggregate  (cost=49987.80..49987.81 rows=1 width=0) (actual time=104.847..104.847 rows=1 loops=1)
  ->  Bitmap Heap Scan on products  (cost=538.85..49930.20 rows=23041 width=0) (actual time=8.919..98.952 rows=47937     loops=1)
        Recheck Cond: ((category = 1) AND active)
        Rows Removed by Index Recheck: 93006
        ->  Bitmap Index Scan on category_score_id  (cost=0.00..533.09 rows=23041 width=0) (actual time=7.181..7.181 rows=47937     loops=1)
              Index Cond: (category = 1)
Total runtime: 104.892 ms
  • As always, your Postgres version, please. – Erwin Brandstetter Aug 5 '14 at 15:28
  • @ErwinBrandstetter yeah, sorry, forgot about that. I'm using 9.3 on 64-bit Ubuntu. – Aleksei Zabrodskii Aug 5 '14 at 15:31
3

It is not doing an extra bitmap scan. It is doing a bitmap scan instead of the regular index scan.

Why is it doing the bitmap scan instead?

Because it thinks it will be faster that way. Without the LIMIT and the ORDER BY, it anticipates that using the bitmap scan will let it do the IO on the table heap in a more efficient manner. You can see if PostgreSQL is correct in this assessment by temporarily doing a set enable_bitmapscan TO off; (although caching effects may make that experiment difficult to interpret correctly.)

Also, the line:

Rows Removed by Index Recheck: 93006

Suggests that your work_mem setting might be too small to accommodate the bitmap efficiently.

Why does it show up in the explain plan as two entries rather than one?

The ordinary index scan is really two scans in one, a scan over the index, and then a nested look-up over the table. But these two parts are integrated, and only show up as one entry in the execution plan.

The bitmap case also has these two steps, but they are not integrated. It is possible to inject extra steps between them, such as a BitmapOr or a BitmapAnd. It reports them as two separate entries to accommodate this possibility.

3

Index definition

Your multicolumn index generally looks good. If all or most of your queries use order by score desc, id desc, it would be a bit more efficient to define it with matching sort order and a simpler condition:

CREATE INDEX prod_category_score_id ON products(category, score DESC, id DESC)
WHERE active;
  • WHERE active = TRUE is just a more complicated way of saying WHERE active.
  • While Index Scan Backward is practically as fast as a plain index scan, access is simpler with matching sort order in multicolumn index.

Why the extra Bitmap Heap Scan?

Due to the MVCC model of Postgres it needs to make sure that entries in the index are actually still alive in the table.

The planner method Index Scan works best for a small number of rows. Postgres takes each row pointer from the index and fetches the row from the heap (the table) sequentially, thereby also checking if the row is actually visible to the current transaction.

With a growing number of hits, this gets less effective. If multiple rows reside on the same data page, it's more efficient to collect tuples and visit the same page only once. That's what a Bitmap Index Scan does essentially (among other things).

When counting rows with count(*), Postgres wouldn't need data from the heap. But it still must verify that each tuple is visible and actually counts. The Wiki page about "Slow counting".

Postgres 9.2 introduced Index Only Scans. If the "visibility map" says all tuples of a page are visible to all current transactions, Postgres does not have to visit the heap to verify. That would be faster for a query such as yours, that only counts a small percentage of rows, most efficiently determined by using the index.

Obviously, you have a lot of concurrent write operations. Or your autovacuum settings are not aggressive enough. Else, you might see a faster Index Only Scan.

The Postgres Wiki about that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.