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

Hi Manu,

> Attached is a patch for it.

Thank you for the quick patch. I tested v1 on master and on
REL_15_STABLE. Each time I compared a patched and an unpatched build of
the same commit, both built with the default -O2 on my laptop.

On master (3ff475ac) the patch applies cleanly. Both make check (239
tests) and test_predtest pass. Planning time of "c = 1 AND (a, b) IN
(...)" with literals, median of three runs:

entries master patched
250 14.5 0.9 ms
1000 195.7 3.6 ms
2000 840.2 8.3 ms
4000 3269.9 23.1 ms (one run)

With a generic plan, the planning time for 2000 entries goes from
189.5 ms to 17.3 ms. In all three scripts of my first mail the top plan
node and the presence of a Filter are the same with and without the
patch.

On REL_15_STABLE (011dd509, 15.19) the patch applies cleanly as well. Of
the regression tests I ran only test_predtest there, and it passes.
Since the original batch job from my first mail runs on 15, I also
tested a prepared statement of the same shape: an (id, validfrom) IN
(...) list of 448 entries that all share the same validfrom, with a
varchar id, an index on (id, validfrom) and a custom plan.

Its planning time goes from 45.4 ms to 1.7 ms (median of five runs).
With enable_bitmapscan = off it takes 1.2 ms. The plan stays a Bitmap
Heap Scan.

On master the same statement plans in under 2 ms with and without the
patch, since master matches the OR over id to the index as = ANY(...).

Will you register the patch in the commitfest? I will then sign up as
its reviewer.

Regards,
Stefan