Re: Avoid redundant BitmapAnd with a clauseless partial index

From: Sami Imseih <samimseih(dot)pg(at)gmail(dot)com>
To: Krishna Sarabu <krishna(dot)sarabu(at)gmail(dot)com>
Cc: pgsql-hackers(at)lists(dot)postgresql(dot)org
Subject: Re: Avoid redundant BitmapAnd with a clauseless partial index
Date: 2026-11-19 13:55:40
Message-ID: CAN12+YLi=zC6BsMnf6ABedCsiPqvfsxssVn04K3UmWP4PeYJrA@mail.gmail.com
Views: Whole Thread | Raw Message | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hi,

I spent some time digging into this. Here is what I found.

> choose_bitmap_and() rejects a partial index whose predicate is implied
> by the quals already chosen, to avoid double-counting selectivity,

2e824a8ea96 in 2007 rewrote choose_bitmap_and() so that the paths are sorted
cheapest first, and each path leads its own AND group, with the paths after it
added to the group, instead of building a single group in selectivity order.
The goal was to make the result "much less dependent on the exact order in
which the indexes are considered".

> it doesn't check the reverse: when a clauseless partial index leads the
> AND group and a later index's quals imply its predicate.

Right. However, the predicate check still depends on the order. It only tests a
partial index's predicate against qualsofar, i.e. the quals and predicates of
the paths before it in the group. So when the partial index leads, which is
likely since a clauseless partial index is usually cheap, nothing stops its
predicate from being double counted later, in cost_bitmap_and_node().

So, it seems to me that ultimately this is a costing concern. In your repro the
BitmapAnd is estimated at 14 rows, and the heap scan is costed for those 14 rows
even though it estimates 2379 rows returned:

```
SET random_page_cost = 1.1;
SET
EXPLAIN
SELECT * FROM bitmap_demo.shipment
WHERE state IN ('PENDING', 'PACKING') AND depot_id IS NOT NULL;

QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on shipment (cost=53.80..69.34 rows=2379 width=292)
Recheck Cond: (((state = 'PENDING'::text) OR (state =
'PACKING'::text) OR (state = 'ON_HOLD'::text)) AND (state = ANY
('{PENDING,PACKING}'::text[])) AND (depot_id IS NOT NULL))
-> BitmapAnd (cost=53.80..53.80 rows=14 width=0)
-> Bitmap Index Scan on shipment_open_by_customer
(cost=0.00..23.32 rows=2848 width=0)
-> Bitmap Index Scan on shipment_state_depot
(cost=0.00..29.05 rows=2379 width=0)
Index Cond: ((state = ANY
('{PENDING,PACKING}'::text[])) AND (depot_id IS NOT NULL))
(6 rows)
```

With random_page_cost = 1.1, that 69.34 also beats a plain index scan on
shipment_state_depot, costed at 1621.48. The attached patch works around this
misestimate by not building the BitmapAnd, since the later index's quals imply
the partial index predicate.

There is a note in choose_bitmap_and() that acknowledges this behavior:

"""
* ... costsize.c and clausesel.c aren't very smart about redundant clauses.
* They will usually double-count the redundant clauses, producing a
* too-small selectivity that makes a redundant AND step look like it
* reduces the total cost. Perhaps someday that code will be smarter and
* we can remove this limitation.
"""

So, maybe the better fix is to avoid counting a predicate that is implied by
another path's clause?

The check as you have it is maybe still worth it since a clauseless
partial index whose predicate is implied cannot remove any rows, so it is a good
defensive check to keep. But, that does not fix the root misestimate, AFAICT.
Here is a case with your patch applied with the repro.sql schema:

```
EXPLAIN ANALYZE
SELECT * FROM bitmap_demo.shipment
WHERE customer_id < 50000
AND state IN ('PENDING', 'PACKING') AND depot_id IS NOT NULL;

QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on shipment (cost=59.89..75.78 rows=709 width=292)
(actual time=0.958..2.047 rows=600.00 loops=1)
Recheck Cond: ((customer_id < 50000) AND ((state = 'PENDING'::text)
OR (state = 'PACKING'::text) OR (state = 'ON_HOLD'::text)) AND (state
= ANY ('{PENDING,PACKING}'::text[])) AND (depot_id IS NOT NULL))
Heap Blocks: exact=600
Buffers: shared hit=608
-> BitmapAnd (cost=59.89..59.89 rows=4 width=0) (actual
time=0.834..0.835 rows=0.00 loops=1)
Buffers: shared hit=8
-> Bitmap Index Scan on shipment_open_by_customer
(cost=0.00..18.64 rows=848 width=0) (actual time=0.199..0.200
rows=899.00 loops=1)
Index Cond: (customer_id < 50000)
Index Searches: 1
Buffers: shared hit=3
-> Bitmap Index Scan on shipment_state_depot
(cost=0.00..40.64 rows=2379 width=0) (actual time=0.546..0.546
rows=2000.00 loops=1)
Index Cond: ((state = ANY
('{PENDING,PACKING}'::text[])) AND (depot_id IS NOT NULL))
Index Searches: 1
Buffers: shared hit=5
Planning:
Buffers: shared hit=192
Planning Time: 1.145 ms
Execution Time: 2.152 ms
(18 rows)
```

The BitmapAnd is the right plan here, since it reads 600 heap blocks instead of
899, but it is estimated at 4 rows against 600 actual.

On the patch itself, a few comments:

> + * selectivity. Skip this path; it still gets considered as a
> + * leader itself. Only plain IndexPaths are checked, since

1/ I think this comment belongs in the header comment of choose_bitmap_and(),
next to the existing predicate check.

> + if (IsA(pathinfoarray[i]->path, IndexPath) &&
> + pathinfoarray[i]->quals == NIL &&
> + pathinfoarray[i]->preds != NIL &&
> + IsA(pathinfo->path, IndexPath) &&
> + pathinfo->quals != NIL &&
> + predicate_implied_by(pathinfoarray[i]->preds, pathinfo->quals,
> + false))
> + continue;

2/ I think pathinfo->quals != NIL can be dropped, since predicate_implied_by()
returns false for an empty clause list.

Also, I think the check should look at the candidate's predicate too, not just
its quals. The check before it already does this, since qualsofar includes the
predicates of the paths chosen so far. For example, with your patch and one
more partial index:

```
CREATE INDEX shipment_pp_id ON bitmap_demo.shipment (id) INCLUDE (payload)
WHERE state IN ('PENDING', 'PACKING');
CREATE INDEX
SET enable_indexscan = off;
SET
SET random_page_cost = 1.1;
SET
EXPLAIN ANALYZE
SELECT * FROM bitmap_demo.shipment
WHERE state IN ('PENDING', 'PACKING') AND id > 0;

QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on shipment (cost=149.61..165.19 rows=2383
width=292) (actual time=3.500..6.513 rows=2500.00 loops=1)
Recheck Cond: (((state = 'PENDING'::text) OR (state =
'PACKING'::text) OR (state = 'ON_HOLD'::text)) AND (id > 0) AND (state
= ANY ('{PENDING,PACKING}'::text[])))
Heap Blocks: exact=2500
Buffers: shared hit=2511 read=101
-> BitmapAnd (cost=149.61..149.61 rows=14 width=0) (actual
time=2.928..2.929 rows=0.00 loops=1)
Buffers: shared hit=11 read=101
-> Bitmap Index Scan on shipment_open_by_customer
(cost=0.00..23.32 rows=2848 width=0) (actual time=0.674..0.674
rows=3000.00 loops=1)
Index Searches: 1
Buffers: shared hit=8
-> Bitmap Index Scan on shipment_pp_id (cost=0.00..124.85
rows=2383 width=0) (actual time=2.051..2.051 rows=2500.00 loops=1)
Index Cond: (id > 0)
Index Searches: 1
Buffers: shared hit=3 read=101
Planning:
Buffers: shared hit=164 read=1
Planning Time: 1.111 ms
Execution Time: 6.758 ms
(17 rows)
```

shipment_pp_id only has PENDING and PACKING rows, so ANDing it with
shipment_open_by_customer cannot remove anything, but the patch still builds the
BitmapAnd, because "id > 0" alone does not imply the partial index predicate.
The INCLUDE is only there to make shipment_pp_id larger, so it is considered
after shipment_open_by_customer. This case should probably be added to the tests
as well.

3/ The tests could be trimmed to the main case, the "own qual" case, and the
BitmapOr case, probably with a smaller table.

What do you think?

--
Sami Imseih
Amazon Web Services (AWS)

In response to

Browse pgsql-hackers by date

  From Date Subject
Previous Message Amit Kapila 2026-11-19 13:49:21 Re: Assertion failure in update_local_synced_slot(), slotsync.c:364