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
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 67d9dc35f44..8681afe4e78 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -34,12 +34,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
{
@@ -111,6 +122,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);
@@ -323,6 +336,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.
@@ -1770,6 +1792,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.
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;
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;
