I wrote a 'larger' more contrived example (SAOP-saturation-test.sql) yesterday to evaluate any performance overheads and it actually exposed a shortcoming of the original patch. I've added two more patches to address that. The new patches are both optimisations and functionality improvements whereby previously I'd overlooked where only the synthesized equality clause was matched.
I've attached here the script I used, though it isn't part of the patchset. Having run it many times against both master and my local branch with the 5 patches on, I can see that both the planner and execution timings are consistent and indeed better with the new partial index support for SAOP and the optimiser chooses the same path as the original chain of ORs present in both branches (established code). Jim On Sun, 7 Jun 2026 at 18:20, Jim Vanns <[email protected]> wrote: > > Oh. I see my CF status suggests a wrong format. Trying git > format-patch here instead of git-diff. My bad... > > On Sun, 7 Jun 2026 at 17:30, Jim Vanns <[email protected]> wrote: > > > > Just adding the same patch rebased atop today's master at > > 89eafad297a9b01ad77cfc1ab93a433e0af894b0 before I attempt my first > > commit-fest entry. I've been sitting on this for a year now but I > > think I missed the PG19 boat? So I targeted PG20 in the CF entry. > > > > Jim > > > > > > On Sun, 1 Mar 2026 at 11:22, Jim Vanns <[email protected]> wrote: > > > > > > OK, I've had a considerable refactor which hopefully addresses all your > > > points. > > > > > > The function now proceeds as follows; > > > > > > 1) Preparatory/rudimentary checks outside of main loop (OR-based SAOP > > > clause, array dimensionality, element count etc.) > > > 2) Pre-filter bitmap indices for partials or planner implied > > > 3) For each element IN() now look for best choice index via > > > compare_path_costs (not just first as before) > > > 3a) Check clause fits general index structure (affecting all elements) > > > 3b) Check index matches predicate value/element > > > 4) Build bitmap OR path for this candidate > > > 5) Tests now moved to existing bitmapopts sql/out > > > > > > I've extended the existing test too to include the multiple-choice > > > path for the planner as you suggested, which this patch should now > > > handle (before it was greedy). > > > > > > It's rebased on top of the current master > > > (aecc558666ad62fbecb08ff7af1394656811a581) to remain > > > relevant/up-to-date. > > > > > > I've not yet tested the performance of it (preferring > > > correctness/acceptance first!) in the face of many indexes and 100 > > > elements in the array but before I do so, is there a best place for > > > this kind of test in the source tree? Somewhere beneath src/test > > > again? I looked but couldn't see an obvious place (bar the regression > > > tests). > > > > > > Cheers, > > > > > > Jim > > > > > > > > > Jim > > > > > > On Mon, 12 Jan 2026 at 00:54, David Rowley <[email protected]> wrote: > > > > > > > > On Sun, 11 Jan 2026 at 06:03, Jim Vanns <[email protected]> wrote: > > > > > Before I continue with the other suggestions of consolidating the test > > > > > and benchmarking, I've made the code change you suggested and used a > > > > > bitmap for recording positions in the list of candidate indexes. Can > > > > > you check and make sure I'm on the right track? > > > > > > > > Just a quick look; > > > > > > > > 1. There doesn't seem to be any consideration that there may be many > > > > partial indexes which are suitable for the SAOP element: > > > > > > > > drop table if exists t; > > > > create table t (a int); > > > > insert into t select x/1000 from generate_series(1,1000000)x; > > > > create index t_eq_1 on t (a) where a = 1; > > > > create index t_eq_2 on t (a) where a = 2; > > > > create index t_eq_3 on t (a) where a = 3; > > > > > > > > create index t_le_2 on t (a) where a <= 2; > > > > > > > > explain select * from t where a in(1,2,3); -- Uses t_le_2 twice rather > > > > than the other two more suitable indexes. > > > > > > > > drop index t_le_2; > > > > explain select * from t where a in(1,2,3); -- What I'd expect the > > > > above query to produce. > > > > > > > > See: compare_path_costs_fuzzily() > > > > > > > > 2. Is there any point in trying the index again when this condition is > > > > true: if (!clauseset.nonempty). Since you'll be looking for the same > > > > column for the next element, shouldn't you do bms_del_member() on that > > > > index? Then put an "if (bms_is_empty(suitable_indexes)) break;" before > > > > the while loop so that you don't needlessly process the entire SAOP > > > > array when you run out of suitable indexes. > > > > > > > > 3. Styistically, instead of using int index_pos, you can use > > > > foreach_current_index(idx_lc). > > > > > > > > 4. I think the following code puts too much faith into there only > > > > being 1 path produced. From a quick skim of the current code in > > > > build_index_paths(), because you're requesting ST_BITMAPSCAN, we don't > > > > seem to ever produce more than 1 path, but if that changed, then your > > > > code would make the list contain too many paths. > > > > > > > > per_saop_paths = list_concat(per_saop_paths, indexpaths); > > > > > > > > 5. Minor detail, but there's a bit of inconsistency in how you're > > > > checking for empty Lists. The preferred way is: list != NIL. > > > > > > > > 6. Are you sure you want to use predOK == true indexes? Do you have a > > > > case where this new code can produce a better plan than if the predOK > > > > index was used directly by the existing Path generation code? If so, > > > > please provide examples. > > > > > > > > David
From 581ec5afff0e346bb65dec8a61d2bd15e6487cfd Mon Sep 17 00:00:00 2001 From: Jim Vanns <[email protected]> Date: Mon, 23 Jun 2025 10:55:03 +0100 Subject: [PATCH 1/5] [PATCH 1/5] Add support for SAOP in the optimizer for partial index paths Prior to this patch, only BitmapOr paths were considered for partial indexes. With this patch, we now support ScalarArrayOpExpr clauses too (i.e. ANY() and IN()). I found no entry for this feature in the TODO list here; - https://wiki.postgresql.org/wiki/Todo However, it has previously been reported/raised here; - https://www.postgresql.org/message-id/flat/c128bd06-a246-4129-914c-3dee7b13417a%40vondra.me#5b3f3b7e90d6de8c39a095afaea6b460 The new function, generate_bitmap_saop_paths, was largely based on the existing generate_bitmap_or_paths() function while also glancing at other array handling code such as that found in backend/utils/adt/xml.c plus some additional false-starts in backend/optimizer/util/predtest.c This complete patch includes a change recommended via the hacker mailing list to include a precheck phase on suitable/candidate index types outside of the main element loop, recording index list positions in a bitmap for faster lookup nested within the main element loop. diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 3f5d4fa3182..b980854a582 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -35,12 +35,23 @@ #include "optimizer/restrictinfo.h" #include "utils/lsyscache.h" #include "utils/selfuncs.h" +#include "utils/array.h" /* XXX see PartCollMatchesExprColl */ #define IndexCollMatchesExprColl(idxcollation, exprcollation) \ ((idxcollation) == InvalidOid || (idxcollation) == (exprcollation)) +/* + * Proof attempts involving large arrays in ScalarArrayOpExpr nodes are + * likely to require O(N^2) time, and more often than not fail anyway. + * So we set an arbitrary limit on the number of array elements that + * we will allow to be treated as an AND or OR clause. + * XXX is it worth exposing this as a GUC knob? + * This block was copied verbatim from ../utils/predtest.c + */ +#define MAX_SAOP_ARRAY_SIZE 100 + /* Whether we are looking for plain indexscan, bitmap scan, or either */ typedef enum { @@ -112,6 +123,8 @@ static List *build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel, List *clauses, List *other_clauses); static List *generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel, List *clauses, List *other_clauses); +static List *generate_bitmap_saop_paths(PlannerInfo *root, RelOptInfo *rel, + List *clauses, List *indexes); static Path *choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths); static int path_usage_comparator(const void *a, const void *b); @@ -322,6 +335,15 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel) rel->baserestrictinfo, NIL); bitindexpaths = list_concat(bitindexpaths, indexpaths); + /* + * Now generate BitmapOrPaths for any suitable SAOP-clauses present in the + * restriction list. Add these to bitindexpaths. + */ + indexpaths = generate_bitmap_saop_paths(root, rel, + rel->baserestrictinfo, + rel->indexlist); + bitindexpaths = list_concat(bitindexpaths, indexpaths); + /* * Likewise, generate BitmapOrPaths for any suitable OR-clauses present in * the joinclause list. Add these to bitjoinpaths. @@ -1769,6 +1791,299 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel, } +/* + * generate_bitmap_saop_paths + * + * Attempt to transform simple ScalarArrayOpExpr (IN/ANY) clauses into + * a BitmapOr of per-element bitmap index scans. + * + * For a clause of the form: + * + * var IN (c1, c2, ..., cn) or + * var = ANY(c1, c2, ..., cn) + * + * where the right-hand side is a non-null constant array, we decompose + * the SAOP into n equality clauses: + * + * var = c1 + * var = c2 + * ... + * + * For each element, we search for bitmap-capable indexes (including partial + * indexes - the original motivation for this patch) that can support the + * derived equality clause. Note we support this for only up to a maximum + * number of elements which must not exceed MAX_SAOP_ARRAY_SIZE. + * + * All viable index paths for each element are costed, and the cheapest + * path is selected. If and only if every element of the IN list can + * be satisfied by some index, the resulting per-element bitmap scans + * are combined into a BitmapOrPath and returned. + * + * If any element cannot be matched to a usable index, the transformation is + * abandoned and the SAOP is left to the normal planner machinery. + * + * Structural index mismatches are pruned during processing to avoid repeated + * checks across elements, but value-specific predicate failures do not + * eliminate an index globally. + */ +static List * +generate_bitmap_saop_paths(PlannerInfo *root, RelOptInfo *rel, + List *clauses, List *indexes) +{ + ListCell *lc; + List *result = NIL; + + foreach(lc, clauses) + { + RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc); + ScalarArrayOpExpr *saop; + Node *leftop; + Node *rightop; + const Const *arrayconst; + ArrayType *arrayval; + Datum *elem_values = NULL; + bool *elem_nulls = NULL; + Bitmapset *suitable_indexes = NULL; + List *per_saop_paths = NIL; + int nelems; + Oid elem_type; + int16 elem_typlen; + bool elem_typbyval; + char elem_typalign; + + if (!IsA(rinfo->clause, ScalarArrayOpExpr)) + continue; + + saop = (ScalarArrayOpExpr *) rinfo->clause; + + /* Only handle IN (ANY), not ALL */ + if (!saop->useOr) + continue; + + leftop = (Node *) linitial(saop->args); + rightop = (Node *) lsecond(saop->args); + + if (!rightop || !IsA(rightop, Const) || + ((Const *) rightop)->constisnull) + continue; + + arrayconst = (const Const *) rightop; + arrayval = DatumGetArrayTypeP(arrayconst->constvalue); + + if (ARR_NDIM(arrayval) != 1) + continue; + + nelems = ArrayGetNItems(1, ARR_DIMS(arrayval)); + + if (nelems < 1 || nelems > MAX_SAOP_ARRAY_SIZE) + continue; + + /* + * Pre-filter indexes - structurally only. Note we must check for + * indpred (the predicate expression of a partial index) or where + * the planner has already proven that the query's WHERE clause + * *implies* the index predicate. + */ + { + int index_pos = 0; + ListCell *idx_lc; + + foreach(idx_lc, indexes) + { + IndexOptInfo *index = lfirst(idx_lc); + + if (index->amhasgetbitmap && + (index->indpred != NIL || index->predOK)) + { + suitable_indexes = + bms_add_member(suitable_indexes, index_pos); + } + index_pos++; + } + } + + if (bms_is_empty(suitable_indexes)) + continue; + + elem_type = ARR_ELEMTYPE(arrayval); + get_typlenbyvalalign(elem_type, + &elem_typlen, + &elem_typbyval, + &elem_typalign); + + deconstruct_array(arrayval, + elem_type, + elem_typlen, + elem_typbyval, + elem_typalign, + &elem_values, + &elem_nulls, + &nelems); + + /* + * For each IN element, build ALL possible index paths, + * not just the first one (avoid greedy choice). + */ + for (int i = 0; i < nelems; i++) + { + Expr *elem_const; + OpExpr *opclause; + RestrictInfo *new_rinfo; + List *paths_for_elem = NIL; + Bitmapset *to_remove = NULL; + int index_pos = -1; + + if (elem_nulls[i]) + { + per_saop_paths = NIL; + break; + } + + elem_const = (Expr *) makeConst(elem_type, + -1, + arrayconst->constcollid, + elem_typlen, + elem_values[i], + false, + elem_typbyval); + + opclause = (OpExpr *) make_opclause(saop->opno, + BOOLOID, + false, + (Expr *) copyObject(leftop), + elem_const, + saop->inputcollid, + saop->inputcollid); + + new_rinfo = make_simple_restrictinfo(root, + (Expr *) opclause); + + while ((index_pos = + bms_next_member(suitable_indexes, + index_pos)) >= 0) + { + IndexOptInfo *index = + list_nth(indexes, index_pos); + IndexClauseSet clauseset; + List *indexpaths; + + /* + * Element-specific predicate check. + * Do NOT prune index here. + */ + if (!predicate_implied_by(index->indpred, + list_make1(new_rinfo), + false)) + continue; + + MemSet(&clauseset, 0, sizeof(clauseset)); + + match_clause_to_index(root, + new_rinfo, + index, + &clauseset); + + /* + * Structural mismatch → prune permanently. + */ + if (!clauseset.nonempty) + { + to_remove = + bms_add_member(to_remove, + index_pos); + continue; + } + + indexpaths = + build_index_paths(root, + rel, + index, + &clauseset, + true, + ST_BITMAPSCAN, + NULL); + + if (indexpaths != NIL) + paths_for_elem = + list_concat(paths_for_elem, + indexpaths); + } + + /* + * Apply structural pruning after iteration. + */ + if (to_remove != NULL) + { + suitable_indexes = + bms_del_members(suitable_indexes, + to_remove); + bms_free(to_remove); + + if (bms_is_empty(suitable_indexes)) + { + per_saop_paths = NIL; + break; + } + } + + /* + * If no index could satisfy this element, + * abort entire SAOP transformation. + */ + if (paths_for_elem == NIL) + { + per_saop_paths = NIL; + break; + } + + /* + * Choose cheapest path for this element. + * Avoid path explosion and respect planner costing. + */ + { + Path *cheapest = (Path *) linitial(paths_for_elem); + ListCell *plc; + + foreach(plc, paths_for_elem) + { + Path *p = lfirst(plc); + + if (compare_path_costs(p, cheapest, TOTAL_COST) < 0) + cheapest = p; + } + + per_saop_paths = lappend(per_saop_paths, cheapest); + } + } + + bms_free(suitable_indexes); + + if (per_saop_paths != NIL) + { + Path *bitmapqual; + + if (list_length(per_saop_paths) > 1) + bitmapqual = + (Path *) create_bitmap_or_path(root, + rel, + per_saop_paths); + else + bitmapqual = + (Path *) linitial(per_saop_paths); + + result = lappend(result, bitmapqual); + } + + if (elem_values) + pfree(elem_values); + if (elem_nulls) + pfree(elem_nulls); + } + + return result; +} + + /* * choose_bitmap_and * Given a nonempty list of bitmap paths, AND them into one path. -- 2.43.0
From aa163906db6c872ea4a7ca406a2b52928439f6ab Mon Sep 17 00:00:00 2001 From: Jim Vanns <[email protected]> Date: Mon, 8 Jun 2026 08:02:42 +0100 Subject: [PATCH 4/5] [PATCH 4/5] Fix costing and planner overhead in SAOP partial index optimization In generate_bitmap_saop_paths() do NOT prune based on !clauseset.nonempty here. If predicate_implied_by() passed above, an empty clauseset simply results in a full scan of the partial index, which is perfectly valid and desired. The initial implementation of generate_bitmap_saop_paths failed to match other base query restriction clauses (e.g., range boundaries on the indexed key) against candidate partial indexes during the array element decomposition phase. This resulted in an empty clauseset being passed to build_index_paths(), forcing the planner to assume a full scan of each partial index. Consequently, the overstated cost estimates caused the planner to reject the valid BitmapOr paths for large arrays. Attempting to match these base restrictions inside the per-element loop introduced an unacceptable O(N*M) complexity, spiking planner overhead significantly when evaluating large arrays against multiple candidate partial indexes. Fix this by hoisting the evaluation of non-SAOP restrictions out of the inner element processing loop. We pre-calculate an array of base IndexClauseSet structs for all suitable candidate indexes using standard palloc and explicit MemSet to align with indxpath.c styling. Inside the per-element loop, we then perform a fast stack copy via memcpy() of the pre-calculated clause boundaries before appending the synthesized scalar element clause. This brings the total planning complexity back down to nearer O(M(R+N)), where N = array elements, M = indexes and R = non-SAOP restrictions, while properly factoring in all restriction clauses, ensuring the optimizer accurately costs and selects the optimized ScalarArrayOpExpr paths. diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index b980854a582..9fc7ae31393 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -1920,6 +1920,35 @@ generate_bitmap_saop_paths(PlannerInfo *root, RelOptInfo *rel, &elem_nulls, &nelems); + /* + * Create an array to hold the base matched clauses for each index. + * We match all query restrictions (except the SAOP itself) against + * our candidate indexes just once. + */ + IndexClauseSet *base_clausesets = + (IndexClauseSet *) palloc0(list_length(indexes) * sizeof(IndexClauseSet)); + + { + int idx_pos = -1; + while ((idx_pos = bms_next_member(suitable_indexes, idx_pos)) >= 0) + { + IndexOptInfo *index = list_nth(indexes, idx_pos); + ListCell *clc; + + foreach(clc, clauses) + { + RestrictInfo *other_rinfo = lfirst_node(RestrictInfo, clc); + /* Skip the original SAOP clause we are actively decomposing */ + if (other_rinfo != rinfo) { + match_clause_to_index(root, + other_rinfo, + index, + &base_clausesets[idx_pos]); + } + } + } + } + /* * For each IN element, build ALL possible index paths, * not just the first one (avoid greedy choice). @@ -1976,24 +2005,12 @@ generate_bitmap_saop_paths(PlannerInfo *root, RelOptInfo *rel, false)) continue; - MemSet(&clauseset, 0, sizeof(clauseset)); + memcpy(&clauseset, &base_clausesets[index_pos], sizeof(IndexClauseSet)); match_clause_to_index(root, new_rinfo, index, &clauseset); - - /* - * Structural mismatch → prune permanently. - */ - if (!clauseset.nonempty) - { - to_remove = - bms_add_member(to_remove, - index_pos); - continue; - } - indexpaths = build_index_paths(root, rel, @@ -2056,6 +2073,7 @@ generate_bitmap_saop_paths(PlannerInfo *root, RelOptInfo *rel, } } + pfree(base_clausesets); bms_free(suitable_indexes); if (per_saop_paths != NIL) -- 2.43.0
From a3964ca366b5621cf3ea34d7c45584e254a771ee Mon Sep 17 00:00:00 2001 From: Jim Vanns <[email protected]> Date: Sun, 1 Mar 2026 11:10:04 +0000 Subject: [PATCH 3/5] [PATCH 3/5] Extend expected output for bitmapops test We now include the expected output from the new SAOP BitmapOr optimisation. diff --git a/src/test/regress/expected/bitmapops.out b/src/test/regress/expected/bitmapops.out index 64068e0469c..2d632edfab1 100644 --- a/src/test/regress/expected/bitmapops.out +++ b/src/test/regress/expected/bitmapops.out @@ -46,3 +46,118 @@ SELECT count(*) FROM bmscantest WHERE a = 1 OR b = 1; -- clean up DROP TABLE bmscantest; +-- Test ScalarArrayOpExpr (SAOP) for partial indexes +-- Generate enough data that we can test the use of an index +CREATE TABLE ipairs( + key INT, + value INT +) +WITH (autovacuum_enabled = false); +-- Install the partial index on these values +CREATE INDEX ipairs_key_idx1 ON ipairs(key) WHERE key = 507; +CREATE INDEX ipairs_key_idx2 ON ipairs(key) WHERE key = 508; +CREATE INDEX ipairs_key_idx3 ON ipairs(key) WHERE key = 509; +CREATE INDEX ipairs_key_idx4 ON ipairs(key) WHERE key <= 508; -- Give planner a choice +-- Dummy data to surround ours +INSERT INTO ipairs(key, value) +SELECT n, -n +FROM generate_series(1, 1000) AS tmp(n); +-- Update statistics +VACUUM (ANALYZE) ipairs; +-- Our specific test data to force the partial index +EXPLAIN (ANALYZE, COSTS OFF, BUFFERS OFF, SUMMARY OFF, TIMING OFF) +UPDATE ipairs +SET value = 0 +WHERE key IN (507,508,509); + QUERY PLAN +----------------------------------------------------------------------------------- + Update on ipairs (actual rows=0.00 loops=1) + -> Bitmap Heap Scan on ipairs (actual rows=3.00 loops=1) + Recheck Cond: ((key = 507) OR (key = 508) OR (key = 509)) + Heap Blocks: exact=1 + -> BitmapOr (actual rows=0.00 loops=1) + -> Bitmap Index Scan on ipairs_key_idx1 (actual rows=1.00 loops=1) + Index Cond: (key = 507) + Index Searches: 1 + -> Bitmap Index Scan on ipairs_key_idx2 (actual rows=1.00 loops=1) + Index Cond: (key = 508) + Index Searches: 1 + -> Bitmap Index Scan on ipairs_key_idx3 (actual rows=1.00 loops=1) + Index Cond: (key = 509) + Index Searches: 1 +(14 rows) + +-- We want ensure that an index use is always attempted - just for the test +SET enable_seqscan=false; +-- Variant 1 (works without the SAOP optimiser patch) +EXPLAIN (COSTS OFF) +SELECT value = 0 +FROM ipairs +WHERE + key = 507 OR + key = 508 OR + key = 509; + QUERY PLAN +------------------------------------------------------------- + Bitmap Heap Scan on ipairs + Recheck Cond: ((key = 507) OR (key = 508) OR (key = 509)) + -> BitmapOr + -> Bitmap Index Scan on ipairs_key_idx1 + Index Cond: (key = 507) + -> Bitmap Index Scan on ipairs_key_idx2 + Index Cond: (key = 508) + -> Bitmap Index Scan on ipairs_key_idx3 + Index Cond: (key = 509) +(9 rows) + +-- Variant 2 (works only with the SAOP optimiser patch) +EXPLAIN (COSTS OFF) +SELECT value = 0 +FROM ipairs +WHERE key IN (507, 508, 509); + QUERY PLAN +------------------------------------------------------------- + Bitmap Heap Scan on ipairs + Recheck Cond: ((key = 507) OR (key = 508) OR (key = 509)) + -> BitmapOr + -> Bitmap Index Scan on ipairs_key_idx1 + Index Cond: (key = 507) + -> Bitmap Index Scan on ipairs_key_idx2 + Index Cond: (key = 508) + -> Bitmap Index Scan on ipairs_key_idx3 + Index Cond: (key = 509) +(9 rows) + +-- Variant 3 (as above) +EXPLAIN (COSTS OFF) +SELECT value = 0 +FROM ipairs +WHERE key = ANY('{507,508,509}'::INT[]); + QUERY PLAN +------------------------------------------------------------- + Bitmap Heap Scan on ipairs + Recheck Cond: ((key = 507) OR (key = 508) OR (key = 509)) + -> BitmapOr + -> Bitmap Index Scan on ipairs_key_idx1 + Index Cond: (key = 507) + -> Bitmap Index Scan on ipairs_key_idx2 + Index Cond: (key = 508) + -> Bitmap Index Scan on ipairs_key_idx3 + Index Cond: (key = 509) +(9 rows) + +-- Variant 5 (should use only ipairs_key_idx4) +EXPLAIN (COSTS OFF) +SELECT value = 0 +FROM ipairs +WHERE key < ANY('{508}'::INT[]); + QUERY PLAN +------------------------------------------------------ + Bitmap Heap Scan on ipairs + Recheck Cond: (key < ANY ('{508}'::integer[])) + -> Bitmap Index Scan on ipairs_key_idx4 + Index Cond: (key < ANY ('{508}'::integer[])) +(4 rows) + +-- Clean up +DROP TABLE ipairs; -- 2.43.0
From b2afa4f028d85988b11b0171698945fdca6101de Mon Sep 17 00:00:00 2001 From: Jim Vanns <[email protected]> Date: Sun, 1 Mar 2026 10:44:12 +0000 Subject: [PATCH 2/5] [PATCH 2/5] Extend existing BitmapOps test for SAOP This patch adds the test for planners choice of partial indexes for SAOP as part of the WHERE clause. - Minimal schema plus required partial indexes - Generates some fake data - Adds explicit values that are in the partial indexes - Runs 4x queries all functionally equivalent but semantically different Note the 4th run tests specifically the best index is chosen via the costings. diff --git a/src/test/regress/sql/bitmapops.sql b/src/test/regress/sql/bitmapops.sql index 1b175f6ff96..aec5fb5a625 100644 --- a/src/test/regress/sql/bitmapops.sql +++ b/src/test/regress/sql/bitmapops.sql @@ -45,3 +45,65 @@ SELECT count(*) FROM bmscantest WHERE a = 1 OR b = 1; -- clean up DROP TABLE bmscantest; + + +-- Test ScalarArrayOpExpr (SAOP) for partial indexes + +-- Generate enough data that we can test the use of an index +CREATE TABLE ipairs( + key INT, + value INT +) +WITH (autovacuum_enabled = false); +-- Install the partial index on these values +CREATE INDEX ipairs_key_idx1 ON ipairs(key) WHERE key = 507; +CREATE INDEX ipairs_key_idx2 ON ipairs(key) WHERE key = 508; +CREATE INDEX ipairs_key_idx3 ON ipairs(key) WHERE key = 509; +CREATE INDEX ipairs_key_idx4 ON ipairs(key) WHERE key <= 508; -- Give planner a choice + +-- Dummy data to surround ours +INSERT INTO ipairs(key, value) +SELECT n, -n +FROM generate_series(1, 1000) AS tmp(n); + +-- Update statistics +VACUUM (ANALYZE) ipairs; + +-- Our specific test data to force the partial index +EXPLAIN (ANALYZE, COSTS OFF, BUFFERS OFF, SUMMARY OFF, TIMING OFF) +UPDATE ipairs +SET value = 0 +WHERE key IN (507,508,509); + +-- We want ensure that an index use is always attempted - just for the test +SET enable_seqscan=false; + +-- Variant 1 (works without the SAOP optimiser patch) +EXPLAIN (COSTS OFF) +SELECT value = 0 +FROM ipairs +WHERE + key = 507 OR + key = 508 OR + key = 509; + +-- Variant 2 (works only with the SAOP optimiser patch) +EXPLAIN (COSTS OFF) +SELECT value = 0 +FROM ipairs +WHERE key IN (507, 508, 509); + +-- Variant 3 (as above) +EXPLAIN (COSTS OFF) +SELECT value = 0 +FROM ipairs +WHERE key = ANY('{507,508,509}'::INT[]); + +-- Variant 5 (should use only ipairs_key_idx4) +EXPLAIN (COSTS OFF) +SELECT value = 0 +FROM ipairs +WHERE key < ANY('{508}'::INT[]); + +-- Clean up +DROP TABLE ipairs; -- 2.43.0
From 99f72242736d7fc976bc780c4497d6b975c41bf9 Mon Sep 17 00:00:00 2001 From: Jim Vanns <[email protected]> Date: Mon, 8 Jun 2026 15:15:20 +0100 Subject: [PATCH 5/5] [PATCH 5/5] Improve partial-index predicate proving for SAOP bitmap paths Building on the previous and initial patch in this branch, when generate_bitmap_saop_paths() expands a ScalarArrayOpExpr into per-element equality clauses, partial-index applicability is currently checked using only the synthesized clause for the current array element. For example, a query such as: WHERE x IN (1,2,3) AND status = 'active' may be unable to use a partial index defined as: CREATE INDEX ... WHERE status = 'active'; because the predicate proof is performed against "x = 1" (or the corresponding equality for another array element) rather than against the full set of query restrictions. Build a base proof-clause list containing all restriction clauses except the original SAOP and append the synthesized equality clause for each array element before calling predicate_implied_by(). This allows partial-index predicates to be proven using the complete restriction environment available to the query. Also skip redundant predicate implication checks for indexes already marked predOK by check_index_predicates(). This improves plan selection for queries that combine SAOP clauses with other restrictions that imply a partial-index predicate. diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 9fc7ae31393..db965507d62 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -1845,6 +1845,7 @@ generate_bitmap_saop_paths(PlannerInfo *root, RelOptInfo *rel, bool *elem_nulls = NULL; Bitmapset *suitable_indexes = NULL; List *per_saop_paths = NIL; + List *base_proof_clauses = NIL; int nelems; Oid elem_type; int16 elem_typlen; @@ -1905,6 +1906,43 @@ generate_bitmap_saop_paths(PlannerInfo *root, RelOptInfo *rel, if (bms_is_empty(suitable_indexes)) continue; + /* + * Build the clause set used for partial-index predicate proof. + * + * We must not attempt to prove a partial index predicate using + * only the synthesized equality clause generated from a single + * SAOP element. Partial-index predicates are often implied by + * other query restrictions. + * + * Example: + * + * WHERE x IN (1,2,3) + * AND status = 'active' + * + * with: + * + * CREATE INDEX ... WHERE status = 'active'; + * + * Therefore construct a base proof clause list containing all + * query restriction clauses except the SAOP currently being + * expanded. The per-element equality clause will be appended + * during processing below. + */ + { + ListCell *proof_lc; + + foreach(proof_lc, clauses) + { + RestrictInfo *proof_rinfo = + lfirst_node(RestrictInfo, proof_lc); + + if (proof_rinfo != rinfo) + base_proof_clauses = + lappend(base_proof_clauses, + proof_rinfo); + } + } + elem_type = ARR_ELEMTYPE(arrayval); get_typlenbyvalalign(elem_type, &elem_typlen, @@ -1959,6 +1997,7 @@ generate_bitmap_saop_paths(PlannerInfo *root, RelOptInfo *rel, OpExpr *opclause; RestrictInfo *new_rinfo; List *paths_for_elem = NIL; + List *proof_clauses; Bitmapset *to_remove = NULL; int index_pos = -1; @@ -1984,8 +2023,16 @@ generate_bitmap_saop_paths(PlannerInfo *root, RelOptInfo *rel, saop->inputcollid, saop->inputcollid); + /* + * Partial-index applicability may depend on the synthesized equality + * clause for the current SAOP element (e.g. a predicate such as + * "x = 1"), so predicate implication must be evaluated per element + * rather than once per index. + */ new_rinfo = make_simple_restrictinfo(root, (Expr *) opclause); + proof_clauses = lappend(list_copy(base_proof_clauses), + new_rinfo); while ((index_pos = bms_next_member(suitable_indexes, @@ -1997,11 +2044,15 @@ generate_bitmap_saop_paths(PlannerInfo *root, RelOptInfo *rel, List *indexpaths; /* - * Element-specific predicate check. - * Do NOT prune index here. + * For partial indexes that have not already been proven + * usable by check_index_predicates(), test implication + * against the full restriction environment rather than + * just the synthesized equality clause. */ - if (!predicate_implied_by(index->indpred, - list_make1(new_rinfo), + if (!index->predOK && + index->indpred != NIL && + !predicate_implied_by(index->indpred, + proof_clauses, false)) continue; @@ -2071,6 +2122,8 @@ generate_bitmap_saop_paths(PlannerInfo *root, RelOptInfo *rel, per_saop_paths = lappend(per_saop_paths, cheapest); } + + list_free(proof_clauses); } pfree(base_clausesets); -- 2.43.0
SAOP-saturation-test.sql
Description: application/sql
