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: Finnerty, Jim <[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, 29 Jul 2024 05:36:57 +0300
Message-ID: <CAPpHfdu5iQOjF93vGbjidsQkhHvY2NSm29duENYH_cbhC6x+Mg@mail.gmail.com> (raw)
In-Reply-To: <[email protected]>
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]>
On Sun, Jul 28, 2024 at 12:59 PM Alena Rybakina
<[email protected]> wrote:
> On 27.07.2024 13:56, Alexander Korotkov wrote:
> > On Thu, Jul 25, 2024 at 5:04 PM Alena Rybakina
> > <[email protected]> wrote:
> >> To be honest, I have found a big problem in this patch - we try to perform the transformation every time we examime a column:
> >>
> >> for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++) { ...
> >>
> >> }
> >>
> >> I have fixed it and moved the transformation before going through the loop.
> > What makes you think there is a problem?
>
> To be honest, I was bothered by the fact that we need to go through
> expressions several times that obviously will not fit under other
> conditions.
> Just yesterday I thought that it would be worthwhile to create a list of
> candidates - expressions that did not fit because the column did not
> match the index (!match_index_to_operand(nconst_expr, indexcol, index)).
I admit that this area probably could use some optimization,
especially for case of many clauses and many indexes. But in the
scope of this patch, I think this is enough to not make things worse
in this area.
> Another problem that is related to the first one that the boolexpr could
> contain expressions referring to different operands, for example, both x
> and y. that is, we may have the problem that the optimal "ANY"
> expression may not be used, because the expression with x may come
> earlier and the loop may end earlier.
>
> alena@postgres=# create table b (x int, y int);
> CREATE TABLE
> alena@postgres=# insert into b select id, id from
> generate_series(1,1000) as id;
> INSERT 0 1000
> alena@postgres=# create index x_idx on b(x);
> CREATE INDEX
> alena@postgres=# analyze;
> ANALYZE
> alena@postgres=# explain select * from b where y =3 or x =4 or x=5 or
> x=6 or x = 7 or x=8 or x=9;
> QUERY PLAN
> ---------------------------------------------------------------------------------------
> Seq Scan on b (cost=0.00..32.50 rows=7 width=8)
> Filter: ((y = 3) OR (x = 4) OR (x = 5) OR (x = 6) OR (x = 7) OR (x =
> 8) OR (x = 9))
> (2 rows)
> alena@postgres=# explain select * from b where x =4 or x=5 or x=6 or x =
> 7 or x=8 or x=9 or y=1;
> QUERY PLAN
> ---------------------------------------------------------------------------------------
> Seq Scan on b (cost=0.00..32.50 rows=7 width=8)
> Filter: ((x = 4) OR (x = 5) OR (x = 6) OR (x = 7) OR (x = 8) OR (x =
> 9) OR (y = 1))
> (2 rows)
> alena@postgres=# explain select * from b where x =4 or x=5 or x=6 or x =
> 7 or x=8 or x=9;
> QUERY PLAN
> ----------------------------------------------------------------
> Index Scan using x_idx on b (cost=0.28..12.75 rows=6 width=8)
> Index Cond: (x = ANY ('{4,5,6,7,8,9}'::integer[]))
> (2 rows)
>
> Furthermore expressions can be stored in a different order.
> For example, first comes "AND" expr, and then group of "OR" expr, which
> we can convert to "ANY" expr, but we won't do this due to the fact that
> we will exit the loop early, according to this condition:
>
> if (!IsA(sub_rinfo->clause, OpExpr))
> return NULL;
>
> or it may occur due to other conditions.
>
> alena@postgres=# create index x_y_idx on b(x,y);
> CREATE INDEX
> alena@postgres=# analyze;
> ANALYZE
>
> alena@postgres=# explain select * from b where (x = 2 and y =3) or x =4
> or x=5 or x=6 or x = 7 or x=8 or x=9;
> QUERY PLAN
> -----------------------------------------------------------------------------------------------------
> Seq Scan on b (cost=0.00..35.00 rows=6 width=8)
> Filter: (((x = 2) AND (y = 3)) OR (x = 4) OR (x = 5) OR (x = 6) OR
> (x = 7) OR (x = 8) OR (x = 9))
> (2 rows)
>
> 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.
> > Do you have a test case
> > illustrating a slow planning time?
> No, I didn't have time to measure it and sorry for that. I'll do it.
> > When v27 performs transformation for a particular column, it just
> > stops facing the first unmatched OR entry. So,
> > match_orclause_to_indexcol() examines just the first OR entry for all
> > the columns excepts at most one. So, the check
> > match_orclause_to_indexcol() does is not much slower than other
> > match_*_to_indexcol() do.
> >
> > I actually think this could help performance in many cases, not hurt
> > it. At least we get rid of O(n^2) complexity over the number of OR
> > entries, which could be very many.
>
> 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.
------
Regards,
Alexander Korotkov
Supabase
Attachments:
[application/octet-stream] v29-0002-Teach-bitmap-scan-about-transforming-OR-clauses-.patch (18.9K, ../CAPpHfdu5iQOjF93vGbjidsQkhHvY2NSm29duENYH_cbhC6x+Mg@mail.gmail.com/2-v29-0002-Teach-bitmap-scan-about-transforming-OR-clauses-.patch)
download | inline diff:
From a56cb787bb302d8bc1a2f53bf1e82bc1cb37fb01 Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <[email protected]>
Date: Sun, 28 Jul 2024 16:36:34 +0300
Subject: [PATCH v29 2/2] Teach bitmap scan about transforming OR clauses to
ANY expression
Now, (expr op C1) OR (expr op C2) ... are transformet to
expr op ANY(ARRAY[C1, C2, ...]) during matching a clause to index.
This commit teaches bitmap scan planning to take advantage of this
transformation.
The similar clauses are grouped together before considering bitmap-OR.
Groups of similar clauses are matched to indexes both together and one-by-one.
---
src/backend/optimizer/path/indxpath.c | 266 ++++++++++++++++++++-
src/test/regress/expected/create_index.out | 28 +--
src/test/regress/expected/join.out | 56 +++--
src/tools/pgindent/typedefs.list | 1 +
4 files changed, 304 insertions(+), 47 deletions(-)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 4fd0bbce2ce..f697b95db39 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1177,6 +1177,248 @@ build_paths_for_OR(PlannerInfo *root, RelOptInfo *rel,
return result;
}
+typedef struct
+{
+ int indexnum;
+ int colnum;
+ Oid opno;
+ int argindex;
+} OrArgIndexMatch;
+
+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->argindex < match_b->argindex)
+ return -1;
+ else if (match_a->argindex > match_b->argindex)
+ return 1;
+
+ return 0;
+}
+
+/*
+ * Group clauses "col op const" belonging to the single index clause into
+ * dedicated ORs.
+ */
+static List *
+group_or_args(PlannerInfo *root, RelOptInfo *rel,
+ RestrictInfo *rinfo, List *orargs)
+{
+ int n = list_length(orargs);
+ int i;
+ int group_start;
+ OrArgIndexMatch *matches;
+ ListCell *lc;
+ ListCell *lc2;
+ List *result = NIL;
+
+ /*
+ * Find corresponding index column for each clause in target form.
+ */
+ 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 *nconst_expr;
+ int indexnum;
+ int colnum;
+
+ i++;
+ matches[i].argindex = i;
+ matches[i].indexnum = -1;
+ matches[i].colnum = -1;
+ matches[i].opno = InvalidOid;
+
+ if (!IsA(arg, RestrictInfo))
+ continue;
+
+ argrinfo = castNode(RestrictInfo, arg);
+
+ if (!IsA(argrinfo->clause, OpExpr))
+ continue;
+
+ clause = (OpExpr *) argrinfo->clause;
+ opno = clause->opno;
+
+ 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;
+
+ 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;
+ }
+
+ nconst_expr = rightop;
+ }
+ else if (IsA(rightop, Const) || IsA(rightop, Param))
+ {
+ nconst_expr = leftop;
+ }
+ else
+ {
+ continue;
+ }
+
+ 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(nconst_expr, colnum, index))
+ {
+ matches[i].indexnum = indexnum;
+ matches[i].colnum = colnum;
+ matches[i].opno = opno;
+ }
+ }
+ indexnum++;
+ }
+ }
+
+ /* Sort clauses to make similar clauses go together */
+ pg_qsort(matches, n, sizeof(OrArgIndexMatch), or_arg_index_match_cmp);
+
+ /* Group similar clauses */
+ group_start = 0;
+ for (i = 1; i <= n; i++)
+ {
+ 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].indexnum == -1))
+ {
+ if (i - group_start == 1)
+ {
+ result = lappend(result, list_nth(orargs, matches[group_start].argindex));
+ }
+ else
+ {
+ List *args = NIL;
+ RestrictInfo *subrinfo = makeNode(RestrictInfo);
+ int j;
+
+ for (j = group_start; j < i; j++)
+ args = lappend(args, list_nth(orargs, matches[j].argindex));
+
+ *subrinfo = *rinfo;
+ subrinfo->clause = make_orclause(args);
+ subrinfo->orclause = subrinfo->clause;
+ result = lappend(result, subrinfo);
+ }
+
+ group_start = i;
+ }
+ }
+ return result;
+}
+
+/*
+ * Generate bitmap paths for group produced by group_or_args()
+ */
+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 +1449,7 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
List *pathlist;
Path *bitmapqual;
ListCell *j;
+ List *grouped;
/* Ignore RestrictInfos that aren't ORs */
if (!restriction_is_or_clause(rinfo))
@@ -1217,7 +1460,8 @@ generate_bitmap_or_paths(PlannerInfo *root, RelOptInfo *rel,
* the OR, else we can't use it.
*/
pathlist = NIL;
- foreach(j, ((BoolExpr *) rinfo->orclause)->args)
+ grouped = group_or_args(root, rel, rinfo, ((BoolExpr *) rinfo->orclause)->args);
+ foreach(j, grouped)
{
Node *orarg = (Node *) lfirst(j);
List *indlist;
@@ -1237,12 +1481,28 @@ 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);
+
+ 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,
@@ -2878,7 +3138,7 @@ match_orclause_to_indexcol(PlannerInfo *root,
if (!OidIsValid(opno))
{
/* commutator doesn't exist, we can't reverse the order */
- return false;
+ return NULL;
}
nconst_expr = rightop;
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 992c80f9350..ba66983cf45 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1764,6 +1764,7 @@ OprCacheKey
OprInfo
OprProofCacheEntry
OprProofCacheKey
+OrArgIndexMatch
OuterJoinClauseInfo
OutputPluginCallbacks
OutputPluginOptions
--
2.39.3 (Apple Git-145)
[application/octet-stream] v29-0001-Transform-OR-clauses-to-ANY-expression.patch (26.8K, ../CAPpHfdu5iQOjF93vGbjidsQkhHvY2NSm29duENYH_cbhC6x+Mg@mail.gmail.com/3-v29-0001-Transform-OR-clauses-to-ANY-expression.patch)
download | inline diff:
From f540ee7b4fc600c2aedb02b139adcf8824c0f7f1 Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Thu, 11 Jul 2024 19:01:10 +0300
Subject: [PATCH v29 1/2] Transform OR clauses to ANY expression
Replace (expr op C1) OR (expr op C2) ... with expr op ANY(ARRAY[C1, C2, ...])
during matching a clause to index.
Here Cn is a n-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').
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 | 241 +++++++++++++++++++++
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 +
src/tools/pgindent/typedefs.list | 1 +
6 files changed, 511 insertions(+), 22 deletions(-)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index c0fcc7d78df..4fd0bbce2ce 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,232 @@ 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
+ * where 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 *newa = 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 have_param = false;
+
+ Assert(IsA(orclause, BoolExpr));
+ Assert(orclause->boolop == OR_EXPR);
+
+ if (bms_is_member(index->rel->relid, rinfo->right_relids))
+ return NULL;
+
+ foreach(lc, orclause->args)
+ {
+ RestrictInfo *sub_rinfo;
+ OpExpr *sub_qual;
+ Oid opno;
+ Node *leftop,
+ *rightop;
+ Node *const_expr;
+ Node *nconst_expr;
+
+ if (!IsA(lfirst(lc), RestrictInfo))
+ return NULL;
+
+ sub_rinfo = (RestrictInfo *) lfirst(lc);
+ sub_qual = (OpExpr *) sub_rinfo->clause;
+ opno = sub_qual->opno;
+
+ if (!IsA(sub_rinfo->clause, OpExpr))
+ return NULL;
+
+ if (sub_rinfo->is_pushed_down != rinfo->is_pushed_down ||
+ sub_rinfo->is_clone != rinfo->is_clone ||
+ sub_rinfo->security_level != rinfo->security_level ||
+ !bms_equal(sub_rinfo->required_relids, rinfo->required_relids) ||
+ !bms_equal(sub_rinfo->incompatible_relids, rinfo->incompatible_relids) ||
+ !bms_equal(sub_rinfo->outer_relids, rinfo->outer_relids))
+ {
+ /* RestrictInfo parameters don't match parent, so bail out */
+ return NULL;
+ }
+
+ if (get_op_rettype(opno) != BOOLOID)
+ {
+ /* Only operator returning boolean suits OR -> ANY transformation */
+ return NULL;
+ }
+
+ /*
+ * Detect the constant side of the clause. Recall non-constant
+ * expression can be made not only with Vars, but also with Params,
+ * which is not bonded with any relation. Thus, we detect the const
+ * side - if another side is constant too, the orqual couldn't be an
+ * OpExpr. Get pointers to constant and expression sides of the qual.
+ */
+
+ leftop = get_leftop(sub_qual);
+ if (IsA(leftop, RelabelType))
+ leftop = (Node *) ((RelabelType *) leftop)->arg;
+
+ rightop = get_rightop(sub_qual);
+ if (IsA(rightop, RelabelType))
+ rightop = (Node *) ((RelabelType *) rightop)->arg;
+
+ if (IsA(leftop, Const) || IsA(leftop, Param))
+ {
+ opno = get_commutator(opno);
+
+ if (!OidIsValid(opno))
+ {
+ /* commutator doesn't exist, we can't reverse the order */
+ return false;
+ }
+
+ nconst_expr = rightop;
+ const_expr = leftop;
+ }
+ else if (IsA(rightop, Const) || IsA(rightop, Param))
+ {
+ const_expr = rightop;
+ nconst_expr = leftop;
+ }
+ else
+ {
+ return NULL;
+ }
+
+ if (!match_index_to_operand(nconst_expr, indexcol, index))
+ return NULL;
+
+ /*
+ * Forbid transformation for composite types, records.
+ */
+ if (type_is_rowtype(exprType(nconst_expr)) ||
+ type_is_rowtype(exprType(const_expr)))
+ {
+ return NULL;
+ }
+
+ if (!OidIsValid(matchOpno))
+ {
+ matchOpno = opno;
+ indexExpr = nconst_expr;
+ consttype = exprType(const_expr);
+ arraytype = get_array_type(consttype);
+ inputcollid = sub_qual->inputcollid;
+ if (!OidIsValid(arraytype))
+ return NULL;
+ }
+ else
+ {
+ if (opno != matchOpno ||
+ inputcollid != sub_qual->inputcollid)
+ return NULL;
+ }
+
+ if (IsA(const_expr, Param))
+ have_param = true;
+ consts = lappend(consts, const_expr);
+ }
+
+ if (have_param)
+ {
+ /*
+ * We need to construct an ArrayExpr given we have Param's not just
+ * Const's.
+ */
+ ArrayExpr *arexpr = makeNode(ArrayExpr);
+
+ /* array_collid will be set by parse_collate.c */
+ arexpr->element_typeid = consttype;
+ arexpr->array_typeid = arraytype;
+ arexpr->multidims = false;
+ arexpr->elements = consts;
+ arexpr->location = -1;
+
+ newa = (Node *) arexpr;
+ }
+ else
+ {
+ /* We have only Costs's. Can generate constant array. */
+
+ int16 typlen;
+ bool typbyval;
+ char typalign;
+ Datum *elems;
+ int i = 0;
+ ArrayType *ar;
+
+ get_typlenbyvalalign(consttype, &typlen, &typbyval, &typalign);
+
+ elems = (Datum *) palloc(sizeof(Datum) * list_length(consts));
+ foreach(lc, consts)
+ {
+ Node *elem = (Node *) lfirst(lc);
+
+ elems[i++] = ((Const *) elem)->constvalue;
+ }
+
+ ar = construct_array(elems, i, consttype, typlen, typbyval, typalign);
+ newa = (Node *) makeConst(arraytype, -1, inputcollid, -1, PointerGetDatum(ar), false, false);
+
+ pfree(elems);
+ list_free(consts);
+ }
+
+ opertup = SearchSysCache1(OPEROID,
+ ObjectIdGetDatum(matchOpno));
+ if (!HeapTupleIsValid(opertup))
+ elog(ERROR, "cache lookup failed for operator %u", matchOpno);
+
+ operform = (Form_pg_operator) GETSTRUCT(opertup);
+
+ /* and build the expression node */
+ saopexpr = makeNode(ScalarArrayOpExpr);
+ saopexpr->opno = matchOpno;
+ saopexpr->opfuncid = operform->oprcode;
+ saopexpr->hashfuncid = InvalidOid;
+ saopexpr->negfuncid = InvalidOid;
+ saopexpr->useOr = true;
+ saopexpr->inputcollid = inputcollid;
+ /* inputcollid will be set by parse_collate.c */
+ saopexpr->args = list_make2(indexExpr, newa);
+ saopexpr->location = -1;
+
+ ReleaseSysCache(opertup);
+
+ 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
--
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index b4d7f9217ce..992c80f9350 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1717,6 +1717,7 @@ NumericVar
OM_uint32
OP
OSAPerGroupState
+OrClauseGroup
OSAPerQueryState
OSInfo
OSSLCipher
--
2.39.3 (Apple Git-145)
view thread (8+ 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], [email protected]
Subject: Re: POC, WIP: OR-clause support for indexes
In-Reply-To: <CAPpHfdu5iQOjF93vGbjidsQkhHvY2NSm29duENYH_cbhC6x+Mg@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