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 7d3c9668-fe28-4db8-a8c2-a70e93eb018f@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,

 > Done: https://commitfest.postgresql.org/patch/7393/

Thank you for registering it. Besides the tests in my previous mail, I
read v1 in the context of predicate_classify() and the list iterator in
predtest.c, and found no correctness issue. The verdict rests on these
checks:

- The rule asks, for each arm of the clause, whether any arm of the
   predicate implies it, so the order of the search does not change the
   result. The patch skips an arm only after testing it.
- The proof takes N attempts when the arms correspond and at most one
   extra attempt per arm compared with master otherwise, as the commit
   message states.
- The shortcut applies only when both sides are plain OR lists, so
   ScalarArrayOpExpr and implicit-AND lists keep the old path.
- The comparison pitem != tried is safe, since for a plain OR the
   iterator returns the same pointers as list_nth().
- The four new test cases cover corresponding arms, swapped arms and
   lists of different lengths, with correct expected results.

One cosmetic point for whoever commits it: guarding the inner loop with
"if (!presult)" avoids starting the iterator after a successful first
attempt and states the intent more directly. By my estimate the saving
is too small to show in the planning time.

I will set the entry to Ready for Committer once my new account can log
in to the commitfest application.

Regards,
Stefan



pgsql-hackers by date:

Previous
From: Zhijie Hou
Date:
Subject: Re: Fix apply worker crash when subscriber table has only a deferrable primary key
Next
From: Dongpo Liu
Date:
Subject: pg_plan_advice fails on a CustomScan that replaces a join