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

Hi Stefan,

> 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?

Attached is a patch for it. A perf profile on master confirms your
reading: the time goes to predicate_implied_by_recurse() called from
create_bitmap_scan_plan().

When both sides are plain OR lists, the OR => OR rule now tries the
predicate's arm at the same position first and searches the others
only if that fails, skipping the one already tried. The result of the
proof does not change, and it never takes more than one extra attempt
per arm. ScalarArrayOpExpr is left alone, since MAX_SAOP_ARRAY_SIZE
already bounds it.

Planning time with your repro_short.sql, master and patched, -O2:

250 entries: 6.1 ms, 0.5 ms
1000 entries: 92 ms, 1.8 ms
2000 entries: 360 ms, 4.0 ms
4000 entries: 1480 ms, 11.5 ms

The generic plan goes from 459 ms to 21 ms with 4000 entries. What
remains with the patch is spent mostly in parsing, catalog lookups
and memory; predtest.c is under 2% of the profile with 8000 entries,
against 16% on master with 2000.

The other forms of your repro.sql get the same plans, and when the
arms do not correspond the proof executes the same number of
instructions as on master. EXPLAIN VERBOSE of your queries is
identical to master, Recheck Cond and Filter included.

The test_predtest module gains cases with corresponding, swapped and
uneven arms. On 20,000 random clause/predicate pairs test_predtest
gives the same results with and without the patch.

It applies as is to every branch from REL_14 to REL_19 and passes the
same checks there; 2000 entries plan in 4 to 10 ms instead of about
370 ms. Whether a planning-time change is back-patched is for a
committer to decide.

Regards,
Manu