Planning time quadratic in the IN-list length for "c = X AND (a, b) IN (...)" with BitmapOr

Hi,

Planning a query of the form

    SELECT * FROM t WHERE c = 1 AND (a, b) IN ((...), (...), ...)

on a table with an index on (c, a, b) takes time that grows with the square
of the number of entries in the IN list. With 2000 entries the planner needs
about one second on each of 15.19, 16.15, 17.11, 18.6 and 19beta4. With 4000
entries, measured on 18.6 and 19beta4, it needs about four seconds. I found
no earlier report of this behaviour in the archives of pgsql-hackers,
pgsql-bugs and pgsql-performance.

I first observed the behaviour on 15.2, in a batch job whose prepared
statements each contain an (a, b) IN (...) list of 448 entries that all
share the same b. Planning one such statement took 104 to 187 ms, against
5 to 9 ms with enable_bitmapscan = off. Since version 18 that form plans in
a few milliseconds, while the form above stays quadratic.

I have two questions for the list. Is the first suggestion below, testing
the arm at the same position before the others, an acceptable change to
predtest.c? And is someone who knows that file willing to write it? I cannot
write the patch myself. If the change is back-patched to 15, 16 or 17, I
will test it with the statements of that batch job.

Reproduction

Each attached script runs with psql -X -f <file> against an empty database.
The attached repro_short.sql creates a table of 500000 generated rows and
runs EXPLAIN (SUMMARY ON) only, so none of the measured queries is executed.
Its core:

    create table orproof_t (c int not null, a text not null,
                            b timestamp not null, d int);
    insert into orproof_t
    select i % 5, 'K' || lpad(i::text, 7, '0'),
           timestamp '2026-01-01' + (i % 10) * interval '1 day', i
    from generate_series(1, 500000) i;
    create index orproof_t_c_a_b on orproof_t (c, a, b);
    vacuum analyze orproof_t;

    explain (summary on)
    select * from orproof_t
     where c = 1 and (a, b) in (('K0000006', '2026-01-07'),
                                ('K0000011', '2026-01-02'), ...);

It prints the top plan node and the planning time for 250 to 4000 entries,
with and without enable_bitmapscan. For 4000 entries it printed 3871 ms on
18.6 and 3930 ms on 19beta4.

Measurements

All figures are the planning time in ms that EXPLAIN (SUMMARY ON) reports,
as the median of three runs. The servers are the official Docker images with
their default configuration, on a laptop under WSL2. The attached repro2.sql
produces these figures.

Literal values, default settings; the top plan node is a Bitmap Heap Scan
over a BitmapOr with one Bitmap Index Scan per entry of the list:

 entries    15.19    16.15    17.11     18.6   19beta4
     250     19.2     16.8     14.4     25.2      15.5
     500     68.4     64.6     60.7     95.6      66.1
    1000    253.3    233.9    243.1    381.8     268.5
    2000    939.2   1410.8   1046.8   1209.8    1053.6

With enable_bitmapscan = off the same statement with 2000 entries plans in
6 to 8 ms on all five versions, as a Gather over a Parallel Seq Scan.

Prepared statement with parameters, plan_cache_mode = force_generic_plan;
Bitmap Heap Scan:

 entries    15.19    16.15    17.11     18.6   19beta4
     250      4.6      4.5      4.0      6.4       3.7
     500     19.4     16.3     15.7     26.2      13.4
    1000     58.8     56.5     54.1     70.3      58.7
    2000    253.0    245.2    223.2    220.4     243.0

As a workaround, the same lookup written as a join against
unnest(array[...]::text[], array[...]::timestamp[]) plans in 0.3 to 0.4 ms
for 2000 entries on all five versions.

Two related query forms show which queries are affected (attached
repro.sql; index on (a, b), no condition on c):

1. (a, b) IN (...) where b varies across the entries of the list: planning
   stays below 17 ms for 2000 entries on all five versions.

2. (a, b) IN (...) where every entry of the list has the same b: planning
   is quadratic on 15.19, 16.15 and 17.11 (762, 890 and 975 ms for 2000
   entries) and stays below 8 ms on 18.6 and 19beta4. The plan on 18.6 and
   19beta4 is an Index Scan.

Source reading

The following is my reading of master as of 2026-10-04. It is consistent
with every measurement above, yet I have not profiled the planner, so the
attribution to these functions is an inference.

transformAExprIn() turns the row-value IN list into one OR with one AND arm
per entry. In the reproduction the scan clauses are therefore

    c = 1
    (a = a1 AND b = b1) OR (a = a2 AND b = b2) OR ...

generate_bitmap_or_paths() builds one index path per arm and adds c = 1 to
each of them, so create_bitmap_subplan() returns as indexquals a single OR
whose arms have three conditions (createplan.c, the make_orclause() call for
subindexquals):

    (c = 1 AND a = a1 AND b = b1) OR (c = 1 AND a = a2 AND b = b2) OR ...

EXPLAIN shows both shapes: the three-condition arms as Recheck Cond and
Index Cond of the bitmap plan, the two-condition arms as Filter of the
sequential plan.

create_bitmap_scan_plan() then decides for each scan clause whether it has
to stay in qpqual:

    if (list_member(indexquals, clause))
        continue;           /* simple duplicate */
    ...
    if (!contain_mutable_functions(clause) &&
        predicate_implied_by(list_make1(clause), indexquals, false))
        continue;           /* provably implied by indexquals */

list_member() fails, because the arms differ in shape.
predicate_implied_by()
reaches the OR-versus-OR case of predicate_implied_by_recurse()
(predtest.c),

    /*
     * OR-clause => OR-clause if each of A's items implies any
     * of B's items.  Messy but can't do it any more simply.
     */

which compares arm i of the indexquals with the arms 1 to i of the scan
clause until the proof succeeds at arm i. For N entries that amounts to
about N^2/2 attempts. Each failing attempt compares a = ai with a = aj in
operator_predicate_proof(), which builds a test expression from the two
constants and evaluates it in the executor.

This reading explains the other measurements as follows:

- With enable_bitmapscan = off the planner still generates the bitmap
  paths. Since it picks the sequential scan, create_bitmap_scan_plan() does
  not run.
- With parameters instead of constants operator_predicate_proof() returns
  before it builds the test expression, so each of the N^2/2 attempts is
  cheaper, while the growth stays quadratic.
- In related form 1 the scan clause and the indexquals are equal(), so
  list_member() succeeds and the proof does not run.
- In related form 2 the common condition on b is factored out of the OR
  (process_duplicate_ors() in prepqual.c), which leaves b = X and an OR
over
  a alone. The shapes of the scan clause and the indexquals therefore
differ
  again. Since version 18 the OR over a is matched to the index as
  a = ANY(...) (commit d4378c0, "Transform OR-clauses to SAOP's during
index
  matching"), so no BitmapOr is built. group_similar_or_args() accepts only
  arms that are a single two-argument operator clause, so the AND arms of
  the reproduction keep the BitmapOr on 18 and 19.

predtest.c already limits proofs of this kind for ScalarArrayOpExpr:

    /*
     * Proof attempts involving large arrays in ScalarArrayOpExpr nodes are
     * likely to require O(N^2) time, and more often than not fail anyway.
     * So we set an arbitrary limit on the number of array elements that
     * we will allow to be treated as an AND or OR clause.
     */
    #define MAX_SAOP_ARRAY_SIZE        100

Explicit AND and OR trees have no such limit.

Suggestions

1. Try the arm at the same position first. In the OR-versus-OR case, test
   arm i of the clause against arm i of the predicate before scanning the
   other arms. In the plans of the reproduction the BitmapOr arms appear in
   the same order as the OR arms, so the proof in create_bitmap_scan_plan()
   then succeeds after N attempts. The result of the proof is unchanged,
   since the full scan remains as the fallback.

2. Limit the number of arms, as MAX_SAOP_ARRAY_SIZE does for arrays, either
   in predicate_classify() for all callers or only in
   create_bitmap_scan_plan(). A proof that is skipped there keeps the OR
   clause in qpqual, so the executor evaluates an N-arm filter for every
   heap row the bitmap returns. A limit therefore moves part of the cost
   from planning to execution. In predicate_classify() it also changes
   proofs for partial indexes and constraint exclusion.

Suggestion 1 keeps the current plans, which is why I prefer it.

Regards,
Stefan Guha