public inbox for [email protected]
help / color / mirror / Atom feedFrom: Alexander Korotkov <[email protected]>
To: Alena Rybakina <[email protected]>
Cc: Nikolay Shaplov <[email protected]>
Cc: [email protected]
Cc: Andrei Lepikhov <[email protected]>
Cc: jian he <[email protected]>
Cc: Robert Haas <[email protected]>
Cc: [email protected]
Cc: Peter Geoghegan <[email protected]>
Cc: Marcos Pegoraro <[email protected]>
Cc: [email protected]
Cc: Tomas Vondra <[email protected]>
Cc: Peter Eisentraut <[email protected]>
Cc: Ranier Vilela <[email protected]>
Subject: Re: POC, WIP: OR-clause support for indexes
Date: Mon, 5 Aug 2024 22:48:53 +0300
Message-ID: <CAPpHfdv9GrXfCOdPsMszBrORig+nW2+JBuMD-np_keVuKJ7bdQ@mail.gmail.com> (raw)
In-Reply-To: <CAPpHfdu5iQOjF93vGbjidsQkhHvY2NSm29duENYH_cbhC6x+Mg@mail.gmail.com>
References: <[email protected]>
<[email protected]>
<CAPpHfdu1AZK91T8Yy4VYNYO+TEX9dSFWK59sRB6K9eM=zEjHOA@mail.gmail.com>
<8969055.VV5PYv0bhD@thinkpad-pgpro>
<[email protected]>
<CAPpHfdsrtAB=0B-qYuQMPgyyy=-CycFJfzTWO_30nx27vXc3dA@mail.gmail.com>
<[email protected]>
<CAPpHfdvUEjkuFNUbg7GuLkXotwvpDgBYz4S8YcE=LRf9aBQh-Q@mail.gmail.com>
<[email protected]>
<CAPpHfdu5iQOjF93vGbjidsQkhHvY2NSm29duENYH_cbhC6x+Mg@mail.gmail.com>
On Mon, Jul 29, 2024 at 5:36 AM Alexander Korotkov <[email protected]> wrote:
> On Sun, Jul 28, 2024 at 12:59 PM Alena Rybakina
> > Because of these reasons, I tried to save this and that transformation
> > together for each column and try to analyze for each expr separately
> > which method would be optimal.
>
> Yes, with v27 of the patch, optimization wouldn't work in these cases.
> However, you are using quite small table. If you will use larger
> table or disable sequential scans, there would be bitmap plans to
> handle these queries. So, v27 doesn't make the situation worse. It
> just doesn't optimize all that it could potentially optimize and
> that's OK.
>
> I've written a separate 0002 patch to address this. Now, before
> generation of paths for bitmap OR, similar OR entries are grouped
> together. When considering a group of similar entries, they are
> considered both together and one-by-one. Ideally we could consider
> more sophisticated grouping, but that seems fine for now. You can
> check how this patch handles the cases of above.
>
> Also, 0002 address issue of duplicated bitmap scan conditions in
> different forms. During generate_bitmap_or_paths() we need to exclude
> considered condition for other clauses. It couldn't be as normal
> filtered out in the latter stage, because could reach the index in
> another form.
>
> > I agree with you that there is an overhead and your patch fixes this
> > problem, but optimizer needs to have a good ordering of expressions for
> > application.
> >
> > I think we can try to move the transformation to another place where
> > there is already a loop pass, and also save two options "OR" expr and
> > "ANY" expr in one place (through BoolExpr) (like find_duplicate_ors
> > function) and teach the optimizer to determine which option is better,
> > for example, like now in match_orclause_to_indexcol() function.
> >
> > What do you thing about it?
>
> find_duplicate_ors() and similar places were already tried before.
> Please, check upthread. This approach receives severe critics. AFAIU,
> the problem is that find_duplicate_ors() during preprocessing, a
> cost-blind stage.
>
> This is why I'd like to continue developing ideas of v27, because it
> fits the existing framework.
The revised patchset is attached. There is no material changes in the
logic, I found no issues here yet. But it comes with refactoring,
cleanup, more comments and better commit messages. I think now this
patchset is understandable and ready for review.
------
Regards,
Alexander Korotkov
Supabase
Attachments:
[application/octet-stream] v30-0002-Teach-bitmap-path-generation-about-transforming-.patch (22.8K, ../CAPpHfdv9GrXfCOdPsMszBrORig+nW2+JBuMD-np_keVuKJ7bdQ@mail.gmail.com/2-v30-0002-Teach-bitmap-path-generation-about-transforming-.patch)
download | inline diff:
From ce9532cdd81f236e3da65bb2a22e33dd1af6413e Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email protected]>
Date: Sun, 28 Jul 2024 16:36:34 +0300
Subject: [PATCH v30 2/2] Teach bitmap path generation about transforming
OR-clauses to SAOP's
When optimizer generates bitmap paths, it considers breaking OR-clause
arguments one-by-one. But now, a group of similar OR-clauses can be
transformed into SAOP during index matching. So, bitmap paths should
keep up.
This commit teaches bitmap paths generation machinery to group similar
OR-clauses into dedicated RestrictInfos. Those RestrictInfos are considered
both to match index as a whole (as SAOP), or to match as a set of individual
OR-clause argument one-by-one (the old way).
Therefore bitmap path generation will takes advantage of OR-clauses to SAOP's
transformation. The old way of handling them is also considered. So, there
shouldn't be planning regression.
Discussion: https://postgr.es/m/567ED6CA.2040504%40sigaev.ru
Reviewed-by: Alexander Korotkov <[email protected]>
---
src/backend/optimizer/path/indxpath.c | 355 ++++++++++++++++++++-
src/test/regress/expected/create_index.out | 28 +-
src/test/regress/expected/join.out | 56 ++--
src/tools/pgindent/typedefs.list | 1 +
4 files changed, 394 insertions(+), 46 deletions(-)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 0ca51bbbb19..970cae1bc55 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1177,6 +1177,325 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
return result;
}
+/*
+ * Data structure representing information about OR-clause argument and its
+ * matching index key. Used for grouping of similar OR-clause arguments in
+ * group_similar_or_args().
+ */
+typedef struct
+{
+ int indexnum; /* index of the matching index */
+ int colnum; /* index of the matching column */
+ Oid opno; /* OID of the OpClause operator */
+ Oid inputcollid; /* OID of the OpClause input collation */
+ int argindex; /* index of the clause in the list of
+ * arguments */
+} OrArgIndexMatch;
+
+/*
+ * Comparison function for OrArgIndexMatch which provides sort order placing
+ * similar OR-clause arguments together.
+ */
+static int
+or_arg_index_match_cmp(const void *a, const void *b)
+{
+ const OrArgIndexMatch *match_a = (const OrArgIndexMatch *) a;
+ const OrArgIndexMatch *match_b = (const OrArgIndexMatch *) b;
+
+ if (match_a->indexnum < match_b->indexnum)
+ return -1;
+ else if (match_a->indexnum > match_b->indexnum)
+ return 1;
+
+ if (match_a->colnum < match_b->colnum)
+ return -1;
+ else if (match_a->colnum > match_b->colnum)
+ return 1;
+
+ if (match_a->opno < match_b->opno)
+ return -1;
+ else if (match_a->opno > match_b->opno)
+ return 1;
+
+ if (match_a->inputcollid < match_b->inputcollid)
+ return -1;
+ else if (match_a->inputcollid > match_b->inputcollid)
+ return 1;
+
+ if (match_a->argindex < match_b->argindex)
+ return -1;
+ else if (match_a->argindex > match_b->argindex)
+ return 1;
+
+ return 0;
+}
+
+/*
+ * group_similar_or_args
+ * Group similar OR arguments intro dedicated RestrictInfos. Process
+ * arguments of 'rinfo' clause, returns the processed list of arguments.
+ *
+ * Similar arguments clauses of form "indexkey op constant" having same
+ * indexkey, operator, and collation. Constantant may compise either Const
+ * or Param.
+ */
+static List *
+group_similar_or_args(PlannerInfo *root, RelOptInfo *rel, RestrictInfo *rinfo)
+{
+ int n;
+ int i;
+ int group_start;
+ OrArgIndexMatch *matches;
+ ListCell *lc;
+ ListCell *lc2;
+ List *orargs;
+ List *result = NIL;
+
+ Assert(IsA(rinfo->orclause, BoolExpr));
+ orargs = ((BoolExpr *) rinfo->orclause)->args;
+ n = list_length(orargs);
+
+ /*
+ * Allocate and fill OrArgIndexMatch struct for for each clause in the
+ * argument list.
+ */
+ i = -1;
+ matches = (OrArgIndexMatch *) palloc(sizeof(OrArgIndexMatch) * n);
+ foreach(lc, orargs)
+ {
+ Node *arg = lfirst(lc);
+ RestrictInfo *argrinfo;
+ OpExpr *clause;
+ Oid opno;
+ Node *leftop,
+ *rightop;
+ Node *nonConstExpr;
+ int indexnum;
+ int colnum;
+
+ i++;
+ matches[i].argindex = i;
+ matches[i].indexnum = -1;
+ matches[i].colnum = -1;
+ matches[i].opno = InvalidOid;
+ matches[i].inputcollid = InvalidOid;
+
+ if (!IsA(arg, RestrictInfo))
+ continue;
+
+ argrinfo = castNode(RestrictInfo, arg);
+
+ /* Only operator clauses scan match */
+ if (!IsA(argrinfo->clause, OpExpr))
+ continue;
+
+ clause = (OpExpr *) argrinfo->clause;
+ opno = clause->opno;
+
+ /* Only binary operators can match */
+ if (list_length(clause->args) != 2)
+ return NULL;
+
+ /*
+ * Ignore any RelabelType node above the operands. This is needed to
+ * be able to apply indexscanning in binary-compatible-operator cases.
+ * Note: we can assume there is at most one RelabelType node;
+ * eval_const_expressions() will have simplified if more than one.
+ */
+ leftop = get_leftop(clause);
+ if (IsA(leftop, RelabelType))
+ leftop = (Node *) ((RelabelType *) leftop)->arg;
+
+ rightop = get_rightop(clause);
+ if (IsA(rightop, RelabelType))
+ rightop = (Node *) ((RelabelType *) rightop)->arg;
+
+ /*
+ * Check for clauses of the form: (indexkey operator constant) or
+ * (constant operator indexkey). But we don't know a particular index
+ * yet. First check for a constant, which must be Const or Param.
+ * That's cheaper than search for a index key among all indexes.
+ */
+ if (IsA(leftop, Const) || IsA(leftop, Param))
+ {
+ opno = get_commutator(opno);
+
+ if (!OidIsValid(opno))
+ {
+ /* commutator doesn't exist, we can't reverse the order */
+ continue;
+ }
+ nonConstExpr = rightop;
+ }
+ else if (IsA(rightop, Const) || IsA(rightop, Param))
+ {
+ nonConstExpr = leftop;
+ }
+ else
+ {
+ continue;
+ }
+
+ /*
+ * Match non-constant part to the index key. It's possible that a
+ * single non-constant part matches multiple index keys. It's OK, we
+ * just stop with first matching index key. Given that this choice is
+ * determined the same for every clause, we will group similar clauses
+ * together anyway.
+ */
+ indexnum = 0;
+ foreach(lc2, rel->indexlist)
+ {
+ IndexOptInfo *index = (IndexOptInfo *) lfirst(lc2);
+
+ /* Ignore index if it doesn't support bitmap scans */
+ if (!index->amhasgetbitmap)
+ continue;
+
+ for (colnum = 0; colnum < index->nkeycolumns; colnum++)
+ {
+ if (match_index_to_operand(nonConstExpr, colnum, index))
+ {
+ matches[i].indexnum = indexnum;
+ matches[i].colnum = colnum;
+ matches[i].opno = opno;
+ matches[i].inputcollid = clause->inputcollid;
+ }
+ }
+ indexnum++;
+ }
+ }
+
+ /* Sort clauses to make similar clauses go together */
+ pg_qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);
+
+ /* Group similar clauses into */
+ group_start = 0;
+ for (i = 1; i <= n; i++)
+ {
+ /* Check if it's a group boundary */
+ if (group_start >= 0 &&
+ (i == n ||
+ matches[i].indexnum != matches[group_start].indexnum ||
+ matches[i].colnum != matches[group_start].colnum ||
+ matches[i].opno != matches[group_start].opno ||
+ matches[i].inputcollid != matches[group_start].inputcollid ||
+ matches[i].indexnum == -1))
+ {
+ /*
+ * One clause in group: add it "as is" to the upper-level OR.
+ */
+ if (i - group_start == 1)
+ {
+ result = lappend(result,
+ list_nth(orargs,
+ matches[group_start].argindex));
+ }
+ else
+ {
+ /*
+ * Two or more clauses in a group: create a nested OR.
+ */
+ List *args = NIL;
+ RestrictInfo *subrinfo = makeNode(RestrictInfo);
+ int j;
+
+ Assert(i - group_start >= 2);
+
+ /* Construct the list of nested OR arguments */
+ for (j = group_start; j < i; j++)
+ args = lappend(args, list_nth(orargs, matches[j].argindex));
+
+ /* Construct the nested OR and wrap it with RestrictInfo */
+ *subrinfo = *rinfo;
+ subrinfo->clause = make_orclause(args);
+ subrinfo->orclause = subrinfo->clause;
+ result = lappend(result, subrinfo);
+ }
+
+ group_start = i;
+ }
+ }
+ pfree(matches);
+ return result;
+}
+
+/*
+ * make_bitmap_paths_for_or_group
+ * Generate bitmap paths for a group of similar OR-clause arguments
+ * produced by group_similar_or_args().
+ *
+ * This function considers two cases: (1) matching a group of clauses to
+ * the index as a whole, and (2) matching the individual clauses one-by-one.
+ * (1) typically comprises an optimal solution. If not, (2) typically
+ * comprises fair alternative.
+ *
+ * Ideally, we could consider all arbitraty splits of arguments into
+ * sub-groups, but that could lead to unacceptable computational complexity.
+ * This is why we only consider two cases of above.
+ */
+static List *
+make_bitmap_paths_for_or_group(PlannerInfo *root, RelOptInfo *rel,
+ RestrictInfo *ri, List *other_clauses)
+{
+ List *jointlist = NIL;
+ List *splitlist = NIL;
+ ListCell *lc;
+ List *orargs;
+ List *args = ((BoolExpr *) ri->clause)->args;
+ Cost jointcost = 0.0,
+ splitcost = 0.0;
+ Path *bitmapqual;
+ List *indlist;
+
+ /*
+ * First, try to match the whole group to the one index.
+ */
+ orargs = list_make1(ri);
+ indlist = build_paths_for_OR(root, rel,
+ orargs,
+ other_clauses);
+ if (indlist != NIL)
+ {
+ bitmapqual = choose_bitmap_and(root, rel, indlist);
+ jointcost = bitmapqual->total_cost;
+ jointlist = list_make1(bitmapqual);
+ }
+
+ /*
+ * Also try to match all containing clauses one-by-one.
+ */
+ foreach(lc, args)
+ {
+ orargs = list_make1(lfirst(lc));
+
+ indlist = build_paths_for_OR(root, rel,
+ orargs,
+ other_clauses);
+
+ if (indlist == NIL)
+ {
+ splitlist = NIL;
+ break;
+ }
+
+ bitmapqual = choose_bitmap_and(root, rel, indlist);
+ splitcost += bitmapqual->total_cost;
+ splitlist = lappend(splitlist, bitmapqual);
+ }
+
+ /*
+ * Pick the best option.
+ */
+ if (splitlist == NIL)
+ return jointlist;
+ else if (jointlist == NIL)
+ return splitlist;
+ else
+ return (jointcost < splitcost) ? jointlist : splitlist;
+}
+
+
/*
* generate_bitmap_or_paths
* Look through the list of clauses to find OR clauses, and generate
@@ -1207,6 +1526,7 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
List *pathlist;
Path *bitmapqual;
ListCell *j;
+ List *groupedArgs;
/* Ignore RestrictInfos that aren't ORs */
if (!restriction_is_or_clause(rinfo))
@@ -1217,7 +1537,13 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
* the OR, else we can't use it.
*/
pathlist = NIL;
- foreach(j, ((BoolExpr *) rinfo->orclause)->args)
+
+ /*
+ * Group the similar OR-clause argument into decicated RestrictInfos,
+ * because those RestrictInfos might match to the index as whole.
+ */
+ groupedArgs = group_similar_or_args(root, rel, rinfo);
+ foreach(j, groupedArgs)
{
Node *orarg = (Node *) lfirst(j);
List *indlist;
@@ -1237,12 +1563,37 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
andargs,
all_clauses));
}
+ else if (restriction_is_or_clause(castNode(RestrictInfo, orarg)))
+ {
+ RestrictInfo *ri = castNode(RestrictInfo, orarg);
+
+ /*
+ * Generate bitmap paths for the group of similar OR-clause
+ * arguments. In this case we need to immediately remove the
+ * rinfo from other clauses. This is because rinfo can be
+ * transformed during index matching. So, we might be unable
+ * to remove that later.
+ */
+ indlist = make_bitmap_paths_for_or_group(root,
+ rel, ri,
+ list_delete(all_clauses, rinfo));
+
+ if (indlist == NIL)
+ {
+ pathlist = NIL;
+ break;
+ }
+ else
+ {
+ pathlist = list_concat(pathlist, indlist);
+ continue;
+ }
+ }
else
{
RestrictInfo *ri = castNode(RestrictInfo, orarg);
List *orargs;
- Assert(!restriction_is_or_clause(ri));
orargs = list_make1(ri);
indlist = build_paths_for_OR(root, rel,
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index c2b25936c8c..c6feef03810 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1982,25 +1982,24 @@ SELECT count(*) FROM tenk1
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
- QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
+ QUERY PLAN
+-----------------------------------------------------------------------------------------------------------------------------
Aggregate
-> Bitmap Heap Scan on tenk1
- Recheck Cond: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
+ Recheck Cond: (((hundred = 42) AND ((thousand = ANY ('{42,99}'::integer[])) OR (tenthous < 2))) OR (thousand = 41))
+ Filter: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
-> BitmapOr
-> BitmapAnd
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 42)
-> BitmapOr
-> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 42)
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 99)
+ Index Cond: (thousand = ANY ('{42,99}'::integer[]))
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: (tenthous < 2)
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: (thousand = 41)
-(16 rows)
+(15 rows)
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
@@ -2012,22 +2011,21 @@ SELECT count(*) FROM tenk1
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
- QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
+ QUERY PLAN
+------------------------------------------------------------------------------------------------------------------------------
Aggregate
-> Bitmap Heap Scan on tenk1
- Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2))))
+ Recheck Cond: ((hundred = 42) AND (((thousand = 99) AND (tenthous = 2)) OR (thousand = ANY ('{42,41}'::integer[]))))
+ Filter: ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2)))
-> BitmapAnd
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 42)
-> BitmapOr
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 42)
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 41)
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: ((thousand = 99) AND (tenthous = 2))
-(13 rows)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = ANY ('{42,41}'::integer[]))
+(12 rows)
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index abe98ff3c53..d26a93831d5 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4226,20 +4226,20 @@ select * from tenk1 a join tenk1 b on
Nested Loop
Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR ((a.unique2 = 3) AND (b.hundred = 4)))
-> Bitmap Heap Scan on tenk1 b
- Recheck Cond: ((unique1 = 2) OR (hundred = 4))
+ Recheck Cond: ((hundred = 4) OR (unique1 = 2))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 2)
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 4)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 2)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
+ Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
Index Cond: (unique2 = 3)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
(17 rows)
explain (costs off)
@@ -4253,12 +4253,12 @@ select * from tenk1 a join tenk1 b on
Filter: ((unique1 = 2) OR (ten = 4))
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 = 1) OR (unique2 = 3))
+ Recheck Cond: ((unique2 = 3) OR (unique1 = 1))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
Index Cond: (unique2 = 3)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
(12 rows)
explain (costs off)
@@ -4270,21 +4270,21 @@ select * from tenk1 a join tenk1 b on
Nested Loop
Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
-> Bitmap Heap Scan on tenk1 b
- Recheck Cond: ((unique1 = 2) OR (hundred = 4))
+ Recheck Cond: ((hundred = 4) OR (unique1 = 2))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 2)
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 4)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 2)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
(18 rows)
explain (costs off)
@@ -4296,21 +4296,21 @@ select * from tenk1 a join tenk1 b on
Nested Loop
Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
-> Bitmap Heap Scan on tenk1 b
- Recheck Cond: ((unique1 = 2) OR (hundred = 4))
+ Recheck Cond: ((hundred = 4) OR (unique1 = 2))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 2)
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 4)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 2)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
(18 rows)
explain (costs off)
@@ -4324,18 +4324,16 @@ select * from tenk1 a join tenk1 b on
-> Seq Scan on tenk1 b
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Recheck Cond: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = ANY ('{3,1}'::integer[])) OR (unique1 < 20))
Filter: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 < 20)
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 3)
- -> Bitmap Index Scan on tenk1_unique1
- Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
-(16 rows)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = ANY ('{3,1}'::integer[]))
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 < 20)
+(14 rows)
--
-- test placement of movable quals in a parameterized join tree
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 75fc05093cc..06c52fbf032 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1763,6 +1763,7 @@ OprCacheKey
OprInfo
OprProofCacheEntry
OprProofCacheKey
+OrArgIndexMatch
OuterJoinClauseInfo
OutputPluginCallbacks
OutputPluginOptions
--
2.39.3 (Apple Git-145)
[application/octet-stream] v30-0001-Transform-OR-clauses-to-SAOP-s-during-index-matc.patch (27.6K, ../CAPpHfdv9GrXfCOdPsMszBrORig+nW2+JBuMD-np_keVuKJ7bdQ@mail.gmail.com/3-v30-0001-Transform-OR-clauses-to-SAOP-s-during-index-matc.patch)
download | inline diff:
From 07f2912a0a266fbf2dd0daa7b729b6584b4e3b9c Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email protected]>
Date: Mon, 5 Aug 2024 21:27:02 +0300
Subject: [PATCH v30 1/2] Transform OR-clauses to SAOP's during index matching
Replace "(indexkey op C1) OR (indexkey op C2) ... (indexkey op CN)" with
"indexkey op ANY(ARRAY[C1, C2, ...])" (ScalarArrayOpExpr node) during matching
a clause to index.
Here Ci is a i-th constant or parameters expression, 'expr' is non-constant
expression, 'op' is an operator which returns boolean result and has a commuter
(for the case of reverse order of constant and non-constant parts of the
expression, like 'Cn op expr').
This transformation allows to handle long OR-clauses with single IndexScan
avoiding slower bitmap scans.
Discussion: https://postgr.es/m/567ED6CA.2040504%40sigaev.ru
Author: Alena Rybakina <[email protected]>
Author: Andrey Lepikhov <[email protected]>
Reviewed-by: Peter Geoghegan <[email protected]>
Reviewed-by: Ranier Vilela <[email protected]>
Reviewed-by: Alexander Korotkov <[email protected]>
Reviewed-by: Robert Haas <[email protected]>
Reviewed-by: Jian He <[email protected]>
Reviewed-by: Tom Lane <[email protected]>
Reviewed-by: Nikolay Shaplov <[email protected]>
---
src/backend/optimizer/path/indxpath.c | 258 +++++++++++++++++++++
src/test/regress/expected/create_index.out | 183 +++++++++++++--
src/test/regress/expected/join.out | 57 ++++-
src/test/regress/sql/create_index.sql | 42 ++++
src/test/regress/sql/join.sql | 9 +
5 files changed, 527 insertions(+), 22 deletions(-)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index c0fcc7d78df..0ca51bbbb19 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -19,10 +19,12 @@
#include "access/stratnum.h"
#include "access/sysattr.h"
+#include "catalog/namespace.h"
#include "catalog/pg_am.h"
#include "catalog/pg_operator.h"
#include "catalog/pg_opfamily.h"
#include "catalog/pg_type.h"
+#include "nodes/bitmapset.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "nodes/supportnodes.h"
@@ -30,9 +32,14 @@
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
+#include "optimizer/planmain.h"
#include "optimizer/prep.h"
#include "optimizer/restrictinfo.h"
+#include "parser/parse_oper.h"
+#include "postgres_ext.h"
+#include "utils/array.h"
#include "utils/lsyscache.h"
+#include "utils/syscache.h"
#include "utils/selfuncs.h"
@@ -177,6 +184,10 @@ static IndexClause *match_rowcompare_to_indexcol(PlannerInfo *root,
RestrictInfo *rinfo,
int indexcol,
IndexOptInfo *index);
+static IndexClause *match_orclause_to_indexcol(PlannerInfo *root,
+ RestrictInfo *rinfo,
+ int indexcol,
+ IndexOptInfo *index);
static IndexClause *expand_indexqual_rowcompare(PlannerInfo *root,
RestrictInfo *rinfo,
int indexcol,
@@ -2248,6 +2259,10 @@ match_clause_to_indexcol(PlannerInfo *root,
{
return match_rowcompare_to_indexcol(root, rinfo, indexcol, index);
}
+ else if (restriction_is_or_clause(rinfo))
+ {
+ return match_orclause_to_indexcol(root, rinfo, indexcol, index);
+ }
else if (index->amsearchnulls && IsA(clause, NullTest))
{
NullTest *nt = (NullTest *) clause;
@@ -2771,6 +2786,249 @@ match_rowcompare_to_indexcol(PlannerInfo *root,
return NULL;
}
+/*
+ * match_orclause_to_indexcol()
+ * Handles the OR-expr case for match_clause_to_indexcol() in the case
+ * when it could be transformed to ScalarArrayOpExpr.
+ */
+static IndexClause *
+match_orclause_to_indexcol(PlannerInfo *root,
+ RestrictInfo *rinfo,
+ int indexcol,
+ IndexOptInfo *index)
+{
+ ListCell *lc;
+ BoolExpr *orclause = (BoolExpr *) rinfo->orclause;
+ Node *indexExpr = NULL;
+ List *consts = NIL;
+ Node *arrayNode = NULL;
+ ScalarArrayOpExpr *saopexpr = NULL;
+ HeapTuple opertup;
+ Form_pg_operator operform;
+ Oid matchOpno = InvalidOid;
+ IndexClause *iclause;
+ Oid consttype = InvalidOid;
+ Oid arraytype = InvalidOid;
+ Oid inputcollid = InvalidOid;
+ bool firstTime = true;
+ bool have_param = false;
+
+ Assert(IsA(orclause, BoolExpr));
+ Assert(orclause->boolop == OR_EXPR);
+
+ /*
+ * Iterate over OR entries. Check that each OR entry is of the form:
+ * (indexkey operator constant) or (constant operator indexkey). Operators
+ * of all the entries must match. Constant might be either Const or
+ * Param. Exit with NULL on first non-matching entry.
+ */
+ foreach(lc, orclause->args)
+ {
+ RestrictInfo *subRinfo;
+ OpExpr *subClause;
+ Oid opno;
+ Node *leftop,
+ *rightop;
+ Node *constExpr;
+
+ if (!IsA(lfirst(lc), RestrictInfo))
+ return NULL;
+
+ subRinfo = (RestrictInfo *) lfirst(lc);
+
+ /* Only operator clauses scan match */
+ if (!IsA(subRinfo->clause, OpExpr))
+ return NULL;
+
+ subClause = (OpExpr *) subRinfo->clause;
+ opno = subClause->opno;
+
+ /* Only binary operators can match */
+ if (list_length(subClause->args) != 2)
+ return NULL;
+
+ /* RestrictInfo parameters dmust match parent */
+ if (subRinfo->is_pushed_down != rinfo->is_pushed_down ||
+ subRinfo->is_clone != rinfo->is_clone ||
+ subRinfo->security_level != rinfo->security_level ||
+ !bms_equal(subRinfo->required_relids, rinfo->required_relids) ||
+ !bms_equal(subRinfo->incompatible_relids, rinfo->incompatible_relids) ||
+ !bms_equal(subRinfo->outer_relids, rinfo->outer_relids))
+ return NULL;
+
+ /* Only operator returning boolean suits the transformation */
+ if (get_op_rettype(opno) != BOOLOID)
+ return NULL;
+
+ /*
+ * Check for clauses of the form: (indexkey operator constant) or
+ * (constant operator indexkey). Determine indexkey side first, check
+ * the constant later.
+ */
+ leftop = (Node *) linitial(subClause->args);
+ rightop = (Node *) lsecond(subClause->args);
+ if (match_index_to_operand(leftop, indexcol, index))
+ {
+ indexExpr = leftop;
+ constExpr = rightop;
+ }
+ else if (match_index_to_operand(rightop, indexcol, index))
+ {
+ opno = get_commutator(opno);
+ if (!OidIsValid(opno))
+ {
+ /* commutator doesn't exist, we can't reverse the order */
+ return NULL;
+ }
+ indexExpr = rightop;
+ constExpr = leftop;
+ }
+ else
+ {
+ return NULL;
+ }
+
+ /*
+ * Ignore any RelabelType node above the operands. This is needed to
+ * be able to apply indexscanning in binary-compatible-operator cases.
+ * Note: we can assume there is at most one RelabelType node;
+ * eval_const_expressions() will have simplified if more than one.
+ */
+ if (IsA(constExpr, RelabelType))
+ constExpr = (Node *) ((RelabelType *) constExpr)->arg;
+ if (IsA(indexExpr, RelabelType))
+ indexExpr = (Node *) ((RelabelType *) indexExpr)->arg;
+
+ /* We allow constant to be Const or Param */
+ if (!IsA(constExpr, Const) && !IsA(constExpr, Param))
+ return NULL;
+
+ /* Forbid transformation for composite types, records. */
+ if (type_is_rowtype(exprType(constExpr)) ||
+ type_is_rowtype(exprType(indexExpr)))
+ return NULL;
+
+ /*
+ * For the first matching qual, save information about operator, type
+ * and collation. For the other quals just check the match with the
+ * first.
+ */
+ if (firstTime)
+ {
+ matchOpno = opno;
+ consttype = exprType(constExpr);
+ arraytype = get_array_type(consttype);
+ inputcollid = subClause->inputcollid;
+
+ /*
+ * There must be an array type in order to construct an array
+ * later
+ */
+ if (!OidIsValid(arraytype))
+ return NULL;
+ firstTime = false;
+ }
+ else
+ {
+ if (opno != matchOpno ||
+ inputcollid != subClause->inputcollid ||
+ consttype != exprType(constExpr))
+ return NULL;
+ }
+
+ if (IsA(constExpr, Param))
+ have_param = true;
+ consts = lappend(consts, constExpr);
+ }
+
+ if (have_param)
+ {
+ /*
+ * We need to construct an ArrayExpr given we have Param's not just
+ * Const's.
+ */
+ ArrayExpr *arrayExpr = makeNode(ArrayExpr);
+
+ /* array_collid will be set by parse_collate.c */
+ arrayExpr->element_typeid = consttype;
+ arrayExpr->array_typeid = arraytype;
+ arrayExpr->multidims = false;
+ arrayExpr->elements = consts;
+ arrayExpr->location = -1;
+
+ arrayNode = (Node *) arrayExpr;
+ }
+ else
+ {
+ /*
+ * We have only Costs's. In this case we can contruct an array
+ * directly.
+ */
+ int16 typlen;
+ bool typbyval;
+ char typalign;
+ Datum *elems;
+ int i = 0;
+ ArrayType *arrayConst;
+
+ get_typlenbyvalalign(consttype, &typlen, &typbyval, &typalign);
+
+ elems = (Datum *) palloc(sizeof(Datum) * list_length(consts));
+ foreach(lc, consts)
+ elems[i++] = ((Const *) lfirst(lc))->constvalue;
+
+ arrayConst = construct_array(elems, i, consttype,
+ typlen, typbyval, typalign);
+ arrayNode = (Node *) makeConst(arraytype, -1, inputcollid,
+ -1, PointerGetDatum(arrayConst),
+ false, false);
+
+ pfree(elems);
+ list_free(consts);
+ }
+
+ /* Lookup for operator to fetch necessary information for the SAOP node */
+ opertup = SearchSysCache1(OPEROID,
+ ObjectIdGetDatum(matchOpno));
+ if (!HeapTupleIsValid(opertup))
+ elog(ERROR, "cache lookup failed for operator %u", matchOpno);
+
+ operform = (Form_pg_operator) GETSTRUCT(opertup);
+
+ /* Build the SAOP expression node */
+ saopexpr = makeNode(ScalarArrayOpExpr);
+ saopexpr->opno = matchOpno;
+ saopexpr->opfuncid = operform->oprcode;
+ saopexpr->hashfuncid = InvalidOid;
+ saopexpr->negfuncid = InvalidOid;
+ saopexpr->useOr = true;
+ saopexpr->inputcollid = inputcollid;
+ saopexpr->args = list_make2(indexExpr, arrayNode);
+ saopexpr->location = -1;
+
+ ReleaseSysCache(opertup);
+
+ /*
+ * Finally build an IndexClause based on the SAOP node.
+ */
+ iclause = makeNode(IndexClause);
+ iclause->rinfo = make_restrictinfo(root,
+ &saopexpr->xpr,
+ rinfo->is_pushed_down,
+ rinfo->has_clone,
+ rinfo->is_clone,
+ rinfo->pseudoconstant,
+ rinfo->security_level,
+ rinfo->required_relids,
+ rinfo->incompatible_relids,
+ rinfo->outer_relids);
+ iclause->indexquals = list_make1(iclause->rinfo);
+ iclause->lossy = false;
+ iclause->indexcol = indexcol;
+ iclause->indexcols = NIL;
+ return iclause;
+}
+
/*
* expand_indexqual_rowcompare --- expand a single indexqual condition
* that is a RowCompareExpr
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index cf6eac57349..c2b25936c8c 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1844,18 +1844,11 @@ DROP TABLE onek_with_null;
EXPLAIN (COSTS OFF)
SELECT * FROM tenk1
WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
- QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------
- Bitmap Heap Scan on tenk1
- Recheck Cond: (((thousand = 42) AND (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand = 42) AND (tenthous = 42)))
- -> BitmapOr
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous = 1))
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous = 3))
- -> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: ((thousand = 42) AND (tenthous = 42))
-(9 rows)
+ QUERY PLAN
+------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(2 rows)
SELECT * FROM tenk1
WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -1864,14 +1857,166 @@ SELECT * FROM tenk1
42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx
(1 row)
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+ QUERY PLAN
+----------------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+ Index Cond: ((thousand = 42) AND (tenthous = ANY (ARRAY[1, (InitPlan 1).col1, 42])))
+ InitPlan 1
+ -> Result
+(4 rows)
+
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+ 42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx
+(1 row)
+
EXPLAIN (COSTS OFF)
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
- QUERY PLAN
----------------------------------------------------------------------------------
+ QUERY PLAN
+------------------------------------------------------------------------------------
Aggregate
-> Bitmap Heap Scan on tenk1
- Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 99)))
+ Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+ QUERY PLAN
+------------------------------------------------------------------------------
+ Index Scan using tenk1_thous_tenthous on tenk1
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3,42}'::integer[])))
+(2 rows)
+
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+ unique1 | unique2 | two | four | ten | twenty | hundred | thousand | twothousand | fivethous | tenthous | odd | even | stringu1 | stringu2 | string4
+---------+---------+-----+------+-----+--------+---------+----------+-------------+-----------+----------+-----+------+----------+----------+---------
+ 42 | 5530 | 0 | 2 | 2 | 2 | 42 | 42 | 42 | 42 | 42 | 84 | 85 | QBAAAA | SEIAAA | OOOOxx
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ QUERY PLAN
+------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: ((hundred = 42) AND (thousand = ANY ('{42,99}'::integer[])))
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+ QUERY PLAN
+------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: ((hundred = 42) AND (thousand < ANY ('{42,99,43,42}'::integer[])))
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand < ANY ('{42,99,43,42}'::integer[]))
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+ QUERY PLAN
+--------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: (((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[]))) OR (thousand = 41))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 42) AND (tenthous = ANY ('{1,3}'::integer[])))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 41)
+(8 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+ count
+-------
+ 10
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+ QUERY PLAN
+------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: (((hundred = 42) AND ((thousand = 42) OR (thousand = 99) OR (tenthous < 2))) OR (thousand = 41))
+ -> BitmapOr
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 42)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 99)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (tenthous < 2)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 41)
+(16 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+ count
+-------
+ 20
+(1 row)
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Bitmap Heap Scan on tenk1
+ Recheck Cond: ((hundred = 42) AND ((thousand = 42) OR (thousand = 41) OR ((thousand = 99) AND (tenthous = 2))))
-> BitmapAnd
-> Bitmap Index Scan on tenk1_hundred
Index Cond: (hundred = 42)
@@ -1879,11 +2024,13 @@ SELECT count(*) FROM tenk1
-> Bitmap Index Scan on tenk1_thous_tenthous
Index Cond: (thousand = 42)
-> Bitmap Index Scan on tenk1_thous_tenthous
- Index Cond: (thousand = 99)
-(11 rows)
+ Index Cond: (thousand = 41)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 99) AND (tenthous = 2))
+(13 rows)
SELECT count(*) FROM tenk1
- WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
count
-------
10
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 53f70d72ed6..abe98ff3c53 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4278,15 +4278,64 @@ select * from tenk1 a join tenk1 b on
Index Cond: (hundred = 4)
-> Materialize
-> Bitmap Heap Scan on tenk1 a
- Recheck Cond: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+ Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
-> BitmapOr
-> Bitmap Index Scan on tenk1_unique1
Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = 3)
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(18 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------
+ Nested Loop
+ Join Filter: (((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
+ -> Bitmap Heap Scan on tenk1 b
+ Recheck Cond: ((unique1 = 2) OR (hundred = 4))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 2)
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 4)
+ -> Materialize
+ -> Bitmap Heap Scan on tenk1 a
+ Recheck Cond: ((unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Filter: ((unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
-> Bitmap Index Scan on tenk1_unique2
- Index Cond: (unique2 = 7)
-(19 rows)
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(18 rows)
+
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------------------------------------------
+ Nested Loop
+ Join Filter: ((a.unique1 < 20) OR (a.unique1 = 3) OR ((a.unique1 = 1) AND (b.unique1 = 2)) OR (((a.unique2 = 3) OR (a.unique2 = 7)) AND (b.hundred = 4)))
+ -> Seq Scan on tenk1 b
+ -> Materialize
+ -> Bitmap Heap Scan on tenk1 a
+ Recheck Cond: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])))
+ Filter: ((unique1 < 20) OR (unique1 = 3) OR (unique1 = 1) OR (unique2 = 3) OR (unique2 = 7))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 < 20)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 3)
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(16 rows)
--
-- test placement of movable quals in a parameterized join tree
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index e296891cab8..f74ad415fbf 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -726,6 +726,24 @@ DROP TABLE onek_with_null;
-- Check bitmap index path planning
--
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+SELECT * FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = (SELECT 1 + 2) OR tenthous = 42);
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+
EXPLAIN (COSTS OFF)
SELECT * FROM tenk1
WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3 OR tenthous = 42);
@@ -738,6 +756,30 @@ SELECT count(*) FROM tenk1
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand < 42 OR thousand < 99 OR 43 > thousand OR 42 > thousand);
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+SELECT count(*) FROM tenk1
+ WHERE thousand = 42 AND (tenthous = 1 OR tenthous = 3) OR thousand = 41;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 99 OR tenthous < 2) OR thousand = 41;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+
--
-- Check behavior with duplicate index column contents
--
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index d81ff63be53..4473b8f04d5 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1433,6 +1433,15 @@ select * from tenk1 a join tenk1 b on
(a.unique1 = 1 and b.unique1 = 2) or
((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+explain (costs off)
+select * from tenk1 a join tenk1 b on
+ (a.unique1 < 20 or a.unique1 = 3 or a.unique1 = 1 and b.unique1 = 2) or
+ ((a.unique2 = 3 or a.unique2 = 7) and b.hundred = 4);
+
--
-- test placement of movable quals in a parameterized join tree
--
--
2.39.3 (Apple Git-145)
view thread (2+ messages)
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: POC, WIP: OR-clause support for indexes
In-Reply-To: <CAPpHfdv9GrXfCOdPsMszBrORig+nW2+JBuMD-np_keVuKJ7bdQ@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox