SAOP-index-optimiser-v4.diff
text/x-patch
Filename: SAOP-index-optimiser-v4.diff
Type: text/x-patch
Part: 0
Patch
Same data as JSON:
GET /api/v1/attachments/:id/patch
the parsed metadata as JSON — format, series position, per-file stats; never the diff bytes.
API reference →
Format: unified
Series: patch v4
| File | + | − |
|---|---|---|
| src/backend/optimizer/path/indxpath.c | 315 | 0 |
| src/test/regress/expected/bitmapops.out | 115 | 0 |
| src/test/regress/sql/bitmapops.sql | 62 | 0 |
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.
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;