Обсуждение: Bitmap scan seem like such a strange choice when "limit 1"

On Fri, 2020-09-04 at 11:42 +0000, Klaudie Willis wrote:
> Postgres 13 beta3
> 
> set enable_bitmapscan=1; -- default
> explain (analyze,buffers) 
> select *
> from bigtable 
> where cars_ref = 1769854207 and t > '2020-01-01'::timestamp  and  t < '2021-01-01'::timestamp 
> limit 1
> 
> Short story.  Big table > 100M rows. b-tree index on cars_ref, the t constraints limits it to one partition, but I
don'tthink that is very relevant.  In any case, running this query takes 1.5s:
 
> 
> Limit  (cost=23728.33..23729.24 rows=1 width=635) (actual time=1516.865..1516.867 rows=1 loops=1)
>   Buffers: shared hit=2376
>   ->  Bitmap Heap Scan on bigtable_y2020 bigtable (cost=23728.33..2530109.01 rows=2730872 width=635) (actual
time=1516.863..1516.864rows=1 loops=1)
 
>         Recheck Cond: (cars_ref = 1769854207)
>         Filter: ((t > '2020-01-01 00:00:00'::timestamp without time zone) AND (t < '2021-01-01 00:00:00'::timestamp
withouttime zone))
 
>         Heap Blocks: exact=1
>         Buffers: shared hit=2376
>         ->  Bitmap Index Scan on bigtable_y2020_cars_ref_idx  (cost=0.00..23045.61 rows=2731965 width=0) (actual
time=751.640..751.640rows=2817675 loops=1)
 
>               Index Cond: (cars_ref = 1769854207)
>               Buffers: shared hit=2375
> Planning Time: 0.365 ms
> Execution Time: 1540.207 ms
> 
> 1.5 seconds seems a lot for a single indexed row.  I would think it should be instant, and so it is when I disable
bitmapscan with: set enable_bitmapscan=0
 
> 
> Limit  (cost=0.57..1.60 rows=1 width=636) (actual time=0.027..0.028 rows=1 loops=1)
>   Buffers: shared hit=5
>   ->  Index Scan using bigtable_y2020_cars_ref_idx on bigtable_y2020 bigtable (cost=0.57..2966738.51 rows=2873818
width=636)(actual time=0.026..0.026 rows=1 loops=1)
 
>         Index Cond: (cars_ref = 1769854207)
>         Filter: ((t > '2020-01-01 00:00:00'::timestamp without time zone) AND (t < '2021-01-01 00:00:00'::timestamp
withouttime zone))
 
>         Buffers: shared hit=5
> Planning Time: 0.291 ms
> Execution Time: 0.049 ms
> 
> But I am not supposed to disable bitmap scan!  So why on earth do Postgres 13 beta3 think that returning 1 row,
shouldbe done with a bitmap scan?
 
> I noticed that different values for "cars_ref" result in different plans in the query above.  I belive that it has to
dowith wheter or not the cars_ref is in the "most common value" list.  But in
 
> any case, I cant see why a bitmap scan is wise then you expect one row.

PostgreSQL estimates that 2817675 rows satisfy the index condition and expects
that it will have to scan many of them before it finds one that satisfies the
filter condition.  That turns out to be a wrong guess.

You could create an index on (cars_ref, t), then PostgreSQL will certainly
pick an index scan.

Yours,
Laurenz Albe
-- 
Cybertec | https://www.cybertec-postgresql.com

> PostgreSQL estimates that 2817675 rows satisfy the index condition and expects
> that it will have to scan many of them before it finds one that satisfies the
> filter condition. That turns out to be a wrong guess.
>
> You could create an index on (cars_ref, t), then PostgreSQL will certainly
> pick an index scan.


Thanks!  But, the t (time constraint) already isolates a particular partition.  The bigtable is partitioned on exactly
t,by year.  This is why you do not see any other indexes/partitions being queried in the EXPLAIN. 

...
PARTITION BY RANGE (t)
...
CREATE TABLE public.bigtable_y2020 PARTITION OF public.bigtable
    FOR VALUES FROM ('2020-01-01 00:00:00') TO ('2021-01-01 00:00:00');

To me, it seems like filter on date is unnecessary when you already IS on such a partition!

I'd like to add, that when I do the same query DIRECTLY on the bigtable_y2020 (instead of the partition parent) it does
changeto "index scan" again. 

best regards
K

Klaudie Willis <Klaudie.Willis@protonmail.com> writes:
> I'd like to add, that when I do the same query DIRECTLY on the bigtable_y2020 (instead of the partition parent) it
doeschange to "index scan" again. 

Yeah.  I think the issue here is that add_paths_to_append_rel only
considers cheapest-total paths for the member relations.  Seeing
that it's already considering a slightly ridiculous number of
parallelization options, I'm hesitant to throw in cheapest-startup
considerations as well, for fear of blowing out planning time.

Maybe the right way to improve this is to bypass add_paths_to_append_rel
entirely when there's exactly one surviving child rel, and make it
just use all the surviving paths for that child.

            regards, tom lane

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Monday, September 7, 2020 9:04 AM, Klaudie Willis <Klaudie.Willis@protonmail.com> wrote:

 > Maybe the right way to improve this is to bypass add_paths_to_append_rel
 > entirely when there's exactly one surviving child rel, and make it
 > just use all the surviving paths for that child.
 > regards, tom lane

Does this classify as a bug, or is it "by design"? Should I submit one for PG13beta3? To me, this seems like quite a
straightforward case. Big database partitioned, two key lookups, both indexed where one key isolates a partition, and
witha limit constraint. Yet it chooses a plan that is 1000x slower than the optimal plan. 

K