Inaccurate Rows estimate for "Bitmap And" causes Planner to choose wrong join

[Steve Pritchard <steve.pritchard@xxxxxxx>]

Version: Postgres 9.6.3 production system (but also tested on Postgres 12)

For my query the Planner is sometimes choosing an execution plan that uses "Bitmap And" (depending on the parameters):

->  Bitmap Heap Scan on observation  (cost=484.92..488.93 rows=1 width=203) (actual time=233.129..330.886 rows=15636 loops=1)
  Recheck Cond: (((user_id)::text = 'USER123'::text) AND ((loc_id)::text = ANY ('{LOC12345678}'::text[])))
  Filter: ((taxa)::text = 'Birds'::text)
  Rows Removed by Filter: 3
  Heap Blocks: exact=1429
  Buffers: shared hit=721 read=944
  ->  BitmapAnd  (cost=484.92..484.92 rows=1 width=0) (actual time=232.888..232.888 rows=0 loops=1)
    Buffers: shared hit=3 read=233
    ->  Bitmap Index Scan on indx_observation_user_id  (cost=0.00..81.14 rows=3277 width=0) (actual time=169.003..169.003 rows=32788 loops=1)
        Index Cond: ((user_id)::text = 'USER123'::text)
        Buffers: shared hit=2 read=134
    ->  Bitmap Index Scan on indx_observation_loc_id  (cost=0.00..403.52 rows=13194 width=0) (actual time=63.520..63.520 rows=15853 loops=1)
        Index Cond: ((loc_id)::text = ANY ('{LOC12345678}'::text[]))
        Buffers: shared hit=1 read=99

(fragment of explain plan)

However it is estimating the number of rows as 1, whereas in this case the actual number of rows is 15636 (it can be much higher).

The Planner then carries this estimate of "1 row" through the rest of the query (which is quite complex), and then makes poor choices about joins.

e.g. uses "Nested Loop Left Join" because it's only expecting one row, whereas in practice it has to do 15636 loops which is very slow.

Note that in cases where the Planner selects a single Index Scan for this query (with different parameters), the Planner makes an accurate estimate of the number of rows and then makes sensible selections of joins (i.e. quick).

i.e. the issue seems to be with the "Bitmap And".

I don't have an index with both user_id & loc_id, as this is one of several different combinations that can arise (it would require quite a few indexes to cover all the possible combinations). However if I did have such an index, the planner would presumably be able to use the statistics for user_id and loc_id to estimate the number of rows.

So why can't it make an accurate estimate of the rows with a "Bitmap And" & " Bitmap Heap Scan"? (as above)

Steve Pritchard

-- 

Steve Pritchard

Database Developer

British Trust for Ornithology, The Nunnery, Thetford, Norfolk IP24 2PU, UK 
Tel: +44 (0)1842 750050, fax: +44 (0)1842 750030
Registered Charity No 216652 (England & Wales) No SC039193 (Scotland)
Company Limited by Guarantee No 357284 (England & Wales)