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

From Stefan Guha
Subject Re: Planning time quadratic in the IN-list length for "c = X AND (a, b) IN (...)" with BitmapOr
Date
Msg-id c6ca1826-a7c8-49d7-b3c4-d81b997af263@stefanguha.com
Whole thread
In response to Re: Planning time quadratic in the IN-list length for "c = X AND (a, b) IN (...)" with BitmapOr  (Manu <manuelreyesbravo@gmail.com>)
Responses Re: Planning time quadratic in the IN-list length for "c = X AND (a, b) IN (...)" with BitmapOr
List pgsql-hackers
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



pgsql-hackers by date:

Previous
From: Sho Ito
Date:
Subject: Re: [PATCH] psql: avoid CREATE command completion after GRANT/REVOKE CREATE
Next
From: Manu
Date:
Subject: Re: Partial indexes on system catalogs