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 2fe2a397311ca529e2d99c3706862afb9276f90e Mon Sep 17 00:00:00 2001 From: Jim Vanns <[email protected]> Date: Mon, 23 Jun 2025 10:55:03 +0100 Subject: [PATCH 1/3] [PATCH 1/3] 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 a44fb0dbfbf086c08a8e88b9c096c0bf36052df6 Mon Sep 17 00:00:00 2001 From: Jim Vanns <[email protected]> Date: Sun, 1 Mar 2026 11:10:04 +0000 Subject: [PATCH 3/3] [PATCH 3/3] 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 bfe88b7499589247c452e9f87d686183e5b96828 Mon Sep 17 00:00:00 2001 From: Jim Vanns <[email protected]> Date: Sun, 1 Mar 2026 10:44:12 +0000 Subject: [PATCH 2/3] [PATCH 2/3] 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
