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
From 2bd319841e0ddf12b06dad1a583aabafa7d94032 Mon Sep 17 00:00:00 2001 From: Manuel Reyes Bravo <[email protected]> Date: Sun, 4 Oct 2026 15:38:09 -0300 Subject: [PATCH v1] Make OR => OR predicate proofs linear for corresponding arms create_bitmap_scan_plan() checks whether each scan clause is implied by the indexquals of the bitmap plan. For an OR clause turned into a BitmapOr, such as a row-value IN list on a multicolumn index, the indexquals are an OR whose arms were built from the clause's arms one by one, so arm i of one corresponds to arm i of the other. The OR-clause => OR-clause rule in predicate_implied_by_recurse() searched the predicate's arms from the first one for each arm of the clause, so that test took a number of proof attempts quadratic in the number of arms, each failing attempt possibly building and evaluating a test expression in operator_predicate_proof(). With 2000 entries in "c = 1 AND (a, b) IN (...)" planning took about 370 ms. When both sides are plain OR lists, try the predicate's arm at the same position first, and the others only if that fails. The result of the proof is unchanged; when the arms do not correspond, this costs one more proof attempt per arm. The test_predtest module gains cases where the arms correspond, are swapped, and differ in number. Reported-by: Stefan Guha Discussion: https://postgr.es/m/[email protected] --- src/backend/optimizer/util/predtest.c | 29 +++++++++- .../test_predtest/expected/test_predtest.out | 58 +++++++++++++++++++ .../test_predtest/sql/test_predtest.sql | 22 +++++++ 3 files changed, 108 insertions(+), 1 deletion(-) diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c index 690a23d619a..2a735033ae2 100644 --- a/src/backend/optimizer/util/predtest.c +++ b/src/backend/optimizer/util/predtest.c @@ -296,6 +296,8 @@ predicate_implied_by_recurse(Node *clause, Node *predicate, PredIterInfoData pred_info; PredClass pclass; bool result; + List *pargs; + int cpos; /* skip through RestrictInfo */ Assert(clause != NULL); @@ -393,15 +395,40 @@ predicate_implied_by_recurse(Node *clause, Node *predicate, /* * 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. + * + * When both are plain OR lists, first try B's item at the + * same position as A's. create_bitmap_scan_plan() tests + * a scan clause against the indexquals of the BitmapOr + * built from it arm by arm, so the arms correspond in + * order, and this makes the test take a number of proof + * attempts linear rather than quadratic in the number of + * arms. The result is the same either way. */ + pargs = NIL; + if (is_orclause(clause) && is_orclause(predicate)) + pargs = ((BoolExpr *) predicate)->args; + cpos = 0; result = true; iterate_begin(citem, clause, clause_info) { bool presult = false; + Node *tried = NULL; + + if (cpos < list_length(pargs)) + { + tried = (Node *) list_nth(pargs, cpos); + presult = predicate_implied_by_recurse(citem, + tried, + weak); + } + cpos++; iterate_begin(pitem, predicate, pred_info) { - if (predicate_implied_by_recurse(citem, pitem, + if (presult) + break; + if (pitem != tried && + predicate_implied_by_recurse(citem, pitem, weak)) { presult = true; diff --git a/src/test/modules/test_predtest/expected/test_predtest.out b/src/test/modules/test_predtest/expected/test_predtest.out index ad82b4f8f91..f8225b82a7b 100644 --- a/src/test/modules/test_predtest/expected/test_predtest.out +++ b/src/test/modules/test_predtest/expected/test_predtest.out @@ -431,6 +431,64 @@ w_i_holds | t s_r_holds | f w_r_holds | f +-- OR-clause => OR-clause tries the item at the same position first; check +-- arms that correspond, arms that don't, and lists of different lengths +select * from test_predtest($$ +select x or z, (x and y) or (z and w) +from booleans +$$); +-[ RECORD 1 ]-----+-- +strong_implied_by | t +weak_implied_by | t +strong_refuted_by | f +weak_refuted_by | f +s_i_holds | t +w_i_holds | t +s_r_holds | f +w_r_holds | f + +select * from test_predtest($$ +select z or x, (x and y) or (z and w) +from booleans +$$); +-[ RECORD 1 ]-----+-- +strong_implied_by | t +weak_implied_by | t +strong_refuted_by | f +weak_refuted_by | f +s_i_holds | t +w_i_holds | t +s_r_holds | f +w_r_holds | f + +select * from test_predtest($$ +select x or z, (x and y) or (z and w) or w +from booleans +$$); +-[ RECORD 1 ]-----+-- +strong_implied_by | f +weak_implied_by | f +strong_refuted_by | f +weak_refuted_by | f +s_i_holds | f +w_i_holds | f +s_r_holds | f +w_r_holds | f + +select * from test_predtest($$ +select w or x or z, (x and y) or z +from booleans +$$); +-[ RECORD 1 ]-----+-- +strong_implied_by | t +weak_implied_by | t +strong_refuted_by | f +weak_refuted_by | f +s_i_holds | t +w_i_holds | t +s_r_holds | f +w_r_holds | f + select * from test_predtest($$ select x and z, x and y and z from booleans diff --git a/src/test/modules/test_predtest/sql/test_predtest.sql b/src/test/modules/test_predtest/sql/test_predtest.sql index dc59f0c22f0..2432bf2c1c9 100644 --- a/src/test/modules/test_predtest/sql/test_predtest.sql +++ b/src/test/modules/test_predtest/sql/test_predtest.sql @@ -180,6 +180,28 @@ select x or y or z, x or z from booleans $$); +-- OR-clause => OR-clause tries the item at the same position first; check +-- arms that correspond, arms that don't, and lists of different lengths +select * from test_predtest($$ +select x or z, (x and y) or (z and w) +from booleans +$$); + +select * from test_predtest($$ +select z or x, (x and y) or (z and w) +from booleans +$$); + +select * from test_predtest($$ +select x or z, (x and y) or (z and w) or w +from booleans +$$); + +select * from test_predtest($$ +select w or x or z, (x and y) or z +from booleans +$$); + select * from test_predtest($$ select x and z, x and y and z from booleans -- 2.55.0
