public inbox for [email protected]
help / color / mirror / Atom feedFrom: a.rybakina <[email protected]>
To: Peter Eisentraut <[email protected]>
To: Peter Geoghegan <[email protected]>
Cc: Finnerty, Jim <[email protected]>
Cc: Marcos Pegoraro <[email protected]>
Cc: Andrey Lepikhov <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: Ranier Vilela <[email protected]>
Cc: Tomas Vondra <[email protected]>
Subject: Re: POC, WIP: OR-clause support for indexes
Date: Tue, 26 Sep 2023 12:08:52 +0300
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
<CAH2-Wzm-W7KYtMQ_3F1zU3Fg0zhRd-kASuOzNewXEWjR5kZrtg@mail.gmail.com>
<[email protected]>
<CAH2-WznHNTXQ=bX4Kc9hHebyXvR0a0CxH9OnirkP0ahgQAX7Aw@mail.gmail.com>
<[email protected]>
<CAH2-WzkNaPbBJ_yWDXzk5ESJZH62vi=+brHHQ2SrDrPXka1xYA@mail.gmail.com>
<[email protected]>
<CAH2-WzmG-+vvN6YEh4J_j3-Q1Yn=HRrjDrz2HDhttPcLVqN0rw@mail.gmail.com>
<[email protected]>
<CAH2-WzkmLg0JPXkZ75b+ha_wJGoJk3QyZ6aUjA0Ba11rdPwdgw@mail.gmail.com>
<[email protected]>
<[email protected]>
<CAH2-Wzkp1RYWC4Lsh==ALNeOR=gQEtCMVbcFRLa-faMQe6YRPA@mail.gmail.com>
<CAH2-Wz=rJOP_1niMTSN_=pzKXUu5tAGRYMGj6uC6Xx=XzkgdPg@mail.gmail.com>
<[email protected]>
<[email protected]>
<[email protected]>
I'm sorry I didn't write for a long time, but I really had a very
difficult month, now I'm fully back to work.
*I was able to implement the patches to the end and moved the
transformation of "OR" expressions to ANY.* I haven't seen a big
difference between them yet, one has a conversion before calculating
selectivity (v7-v1-Replace-OR-clause-to-ANY.patch), the other after
(v7-v2-Replace-OR-clause-to-ANY.patch). Regression tests are passing, I
don't see any problems with selectivity, nothing has fallen into the
coredump, but I found some incorrect transformations. What is the reason
for these inaccuracies, I have not found, but, to be honest, they look
unusual). Gave the error below.
In the patch, I don't like that I had to drag three libraries from
parsing until I found a way around it.The advantage of this approach
compared to the other (v7-v0-Replace-OR-clause-to-ANY.patch) is that at
this stage all possible or transformations are performed, compared to
the patch, where the transformation was done at the parsing stage. That
is, here, for example, there are such optimizations in the transformation:
I took the common element out of the bracket and the rest is converted
to ANY, while, as noted by Peter Geoghegan, we did not have several
bitmapscans, but only one scan through the array.
postgres=# explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 AND prolang=1 OR prolang = 13 AND prolang = 2 OR
prolang = 13 AND prolang = 3;
QUERY PLAN
-------------------------------------------------------------------------------------------------------
Seq Scan on pg_proc p1 (cost=0.00..151.66 rows=1 width=68) (actual
time=1.167..1.168 rows=0 loops=1)
Filter: ((prolang = '13'::oid) AND (prolang = ANY (ARRAY['1'::oid,
'2'::oid, '3'::oid])))
Rows Removed by Filter: 3302
Planning Time: 0.146 ms
Execution Time: 1.191 ms
(5 rows)
*While I was testing, I found some transformations that don't work,
although in my opinion, they should:**
**
**1. First case:*
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 AND prolang=1 OR prolang = 2 AND prolang = 2 OR
prolang = 13 AND prolang = 13;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
Seq Scan on pg_proc p1 (cost=0.00..180.55 rows=2 width=68) (actual
time=2.959..3.335 rows=89 loops=1)
Filter: (((prolang = '13'::oid) AND (prolang = '1'::oid)) OR
((prolang = '2'::oid) AND (prolang = '2'::oid)) OR ((prolang =
'13'::oid) AND (prolang = '13'::oid)))
Rows Removed by Filter: 3213
Planning Time: 1.278 ms
Execution Time: 3.486 ms
(5 rows)
Should have left only prolang = '13'::oid:
QUERY PLAN
-------------------------------------------------------------------------------------------------------
Seq Scan on pg_proc p1 (cost=0.00..139.28 rows=1 width=68) (actual
time=2.034..2.034 rows=0 loops=1)
Filter: ((prolang = '13'::oid ))
Rows Removed by Filter: 3302
Planning Time: 0.181 ms
Execution Time: 2.079 ms
(5 rows)
*2. Also does not work:*
postgres=# explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Seq Scan on pg_proc p1 (cost=0.00..164.04 rows=176 width=68) (actual
time=2.422..2.686 rows=89 loops=1)
Filter: ((prolang = '13'::oid) OR ((prolang = '2'::oid) AND (prolang
= '2'::oid)) OR (prolang = '13'::oid))
Rows Removed by Filter: 3213
Planning Time: 1.370 ms
Execution Time: 2.799 ms
(5 rows)
Should have left:
Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))
*3. Or another:*
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Seq Scan on pg_proc p1 (cost=0.00..164.04 rows=176 width=68) (actual
time=2.350..2.566 rows=89 loops=1)
Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR ((prolang
= '2'::oid) AND (prolang = '2'::oid)))
Rows Removed by Filter: 3213
Planning Time: 0.215 ms
Execution Time: 2.624 ms
(5 rows)
Should have left:
Filter: ((prolang = '13'::oid) OR (prolang = '2'::oid))
*Falls into coredump at me:*
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang = 2 AND prolang = 2 OR prolang = 13;
explain analyze SELECT p1.oid, p1.proname
FROM pg_proc as p1
WHERE prolang = 13 OR prolang=13 OR prolang = 2 AND prolang = 2;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Seq Scan on pg_proc p1 (cost=0.00..164.04 rows=176 width=68) (actual
time=2.350..2.566 rows=89 loops=1)
Filter: ((prolang = '13'::oid) OR (prolang = '13'::oid) OR ((prolang
= '2'::oid) AND (prolang = '2'::oid)))
Rows Removed by Filter: 3213
Planning Time: 0.215 ms
Execution Time: 2.624 ms
(5 rows)
I remind that initially the task was to find an opportunity to optimize
the case of processing a large number of "or" expressions to optimize
memory consumption. The FlameGraph for executing 50,000 "or"
expressionshas grown 1.4Gb and remains in this state until exiting the
psql session (flamegraph1.png) and it sagged a lot in execution time. If
this case is converted to ANY, the query is executed much faster and
memory is optimized (flamegraph2.png). It may be necessary to use this
approach if there is no support for the framework to process ANY, IN
expressions.
Peter Geoghegan also noticed some development of this patch in terms of
preparing some transformations to optimize the query at the stage of its
execution [0].
[0]
https://www.postgresql.org/message-id/CAH2-Wz%3D9N_4%2BEyhtyFqYQRx4OgVbP%2B1aoYU2JQPVogCir61ZEQ%40ma...
Attachments:
[text/x-patch] v7-v0-Replace-OR-clause-to-ANY.patch (32.8K, ../[email protected]/3-v7-v0-Replace-OR-clause-to-ANY.patch)
download | inline diff:
From 087125cc413429bda05f22ebbd51115c23819285 Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Tue, 18 Jul 2023 17:19:53 +0300
Subject: [PATCH] Replace OR clause to ANY expressions. Replace (X=N1) OR
(X=N2) ... with X = ANY(N1, N2) on the stage of the optimiser when we are
still working with a tree expression. Firstly, we do not try to make a
transformation for "non-or" expressions or inequalities and the creation of a
relation with "or" expressions occurs according to the same scenario.
Secondly, we do not make transformations if there are less than set
or_transform_limit. Thirdly, it is worth considering that we consider "or"
expressions only at the current level.
Authors: Alena Rybakina <[email protected]>, Andrey Lepikhov <[email protected]>
Reviewed-by: Peter Geoghegan <[email protected]>, Ranier Vilela <[email protected]>
---
src/backend/parser/parse_expr.c | 230 +++++++++++++++++-
src/backend/utils/misc/guc_tables.c | 10 +
src/include/parser/parse_expr.h | 1 +
src/test/regress/expected/create_index.out | 115 +++++++++
src/test/regress/expected/guc.out | 3 +-
src/test/regress/expected/join.out | 50 ++++
src/test/regress/expected/partition_prune.out | 179 ++++++++++++++
src/test/regress/expected/tidscan.out | 17 ++
src/test/regress/sql/create_index.sql | 32 +++
src/test/regress/sql/join.sql | 10 +
src/test/regress/sql/partition_prune.sql | 22 ++
src/test/regress/sql/tidscan.sql | 6 +
src/tools/pgindent/typedefs.list | 1 +
13 files changed, 674 insertions(+), 2 deletions(-)
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 5a05caa8744..b2294af0f43 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -43,6 +43,7 @@
/* GUC parameters */
bool Transform_null_equals = false;
+int or_transform_limit = 500;
static Node *transformExprRecurse(ParseState *pstate, Node *expr);
@@ -95,6 +96,233 @@ static Expr *make_distinct_op(ParseState *pstate, List *opname,
static Node *make_nulltest_from_distinct(ParseState *pstate,
A_Expr *distincta, Node *arg);
+typedef struct OrClauseGroupEntry
+{
+ Node *node;
+ List *consts;
+ Oid scalar_type;
+ Oid opno;
+ Expr *expr;
+} OrClauseGroupEntry;
+
+static Node *
+transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
+{
+ List *or_list = NIL;
+ List *groups_list = NIL;
+ ListCell *lc;
+
+ /* If this is not an 'OR' expression, skip the transformation */
+ if (expr_orig->boolop != OR_EXPR ||
+ list_length(expr_orig->args) < or_transform_limit)
+ return transformBoolExpr(pstate, (BoolExpr *) expr_orig);
+
+ foreach(lc, expr_orig->args)
+ {
+ Node *arg = lfirst(lc);
+ Node *orqual;
+ Node *const_expr;
+ Node *nconst_expr;
+ ListCell *lc_groups;
+ OrClauseGroupEntry *gentry;
+
+ /* At first, transform the arg and evaluate constant expressions. */
+ orqual = transformExprRecurse(pstate, (Node *) arg);
+ orqual = coerce_to_boolean(pstate, orqual, "OR");
+ orqual = eval_const_expressions(NULL, orqual);
+
+ if (!IsA(orqual, OpExpr))
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ /*
+ * 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.
+ */
+ if (IsA(get_leftop(orqual), Const))
+ {
+ nconst_expr = get_rightop(orqual);
+ const_expr = get_leftop(orqual);
+ }
+ else if (IsA(get_rightop(orqual), Const))
+ {
+ const_expr = get_rightop(orqual);
+ nconst_expr = get_leftop(orqual);
+ }
+ else
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ if (!op_mergejoinable(((OpExpr *) orqual)->opno, exprType(nconst_expr)))
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ /*
+ * At this point we definitely have a transformable clause.
+ * Classify it and add into specific group of clauses, or create new
+ * group.
+ * TODO: to manage complexity in the case of many different clauses
+ * (X1=C1) OR (X2=C2 OR) ... (XN = CN) we could invent something
+ * like a hash table. But also we believe, that the case of many
+ * different variable sides is very rare.
+ */
+ foreach(lc_groups, groups_list)
+ {
+ OrClauseGroupEntry *v = (OrClauseGroupEntry *) lfirst(lc_groups);
+
+ Assert(v->node != NULL);
+
+ if (equal(v->node, nconst_expr))
+ {
+ v->consts = lappend(v->consts, const_expr);
+ nconst_expr = NULL;
+ break;
+ }
+ }
+
+ if (nconst_expr == NULL)
+ /*
+ * The clause classified successfully and added into existed
+ * clause group.
+ */
+ continue;
+
+ /* New clause group needed */
+ gentry = palloc(sizeof(OrClauseGroupEntry));
+ gentry->node = nconst_expr;
+ gentry->consts = list_make1(const_expr);
+ gentry->expr = (Expr *) orqual;
+ groups_list = lappend(groups_list, (void *) gentry);
+ }
+
+ if (groups_list == NIL)
+ {
+ /*
+ * No any transformations possible with this list of arguments. Here we
+ * already made all underlying transformations. Thus, just return the
+ * transformed bool expression.
+ */
+ return (Node *) makeBoolExpr(OR_EXPR, or_list, expr_orig->location);
+ }
+ else
+ {
+ ListCell *lc_args;
+
+ /* Let's convert each group of clauses to an IN operation. */
+
+ /*
+ * Go through the list of groups and convert each, where number of
+ * consts more than 1. trivial groups move to OR-list again
+ */
+
+ foreach(lc_args, groups_list)
+ {
+ OrClauseGroupEntry *gentry = (OrClauseGroupEntry *) lfirst(lc_args);
+ List *allexprs;
+ Oid scalar_type;
+ Oid array_type;
+
+ Assert(list_length(gentry->consts) > 0);
+
+ if (list_length(gentry->consts) == 1)
+ {
+ /*
+ * Only one element in the class. Return rinfo into the BoolExpr
+ * args list unchanged.
+ */
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ continue;
+ }
+
+ /*
+ * Do the transformation.
+ *
+ * First of all, try to select a common type for the array elements.
+ * Note that since the LHS' type is first in the list, it will be
+ * preferred when there is doubt (eg, when all the RHS items are
+ * unknown literals).
+ *
+ * Note: use list_concat here not lcons, to avoid damaging rnonvars.
+ *
+ * As a source of insides, use make_scalar_array_op()
+ */
+ allexprs = list_concat(list_make1(gentry->node), gentry->consts);
+ scalar_type = select_common_type(NULL, allexprs, NULL, NULL);
+
+ if (scalar_type != RECORDOID && OidIsValid(scalar_type))
+ array_type = get_array_type(scalar_type);
+ else
+ array_type = InvalidOid;
+
+ if (array_type != InvalidOid)
+ {
+ /*
+ * OK: coerce all the right-hand non-Var inputs to the common
+ * type and build an ArrayExpr for them.
+ */
+ List *aexprs;
+ ArrayExpr *newa;
+ ScalarArrayOpExpr *saopexpr;
+ ListCell *l;
+
+ aexprs = NIL;
+
+ foreach(l, gentry->consts)
+ {
+ Node *rexpr = (Node *) lfirst(l);
+
+ rexpr = coerce_to_common_type(pstate, rexpr,
+ scalar_type,
+ "IN");
+ aexprs = lappend(aexprs, rexpr);
+ }
+
+ newa = makeNode(ArrayExpr);
+ /* array_collid will be set by parse_collate.c */
+ newa->element_typeid = scalar_type;
+ newa->array_typeid = array_type;
+ newa->multidims = false;
+ newa->elements = aexprs;
+ newa->location = -1;
+
+ saopexpr =
+ (ScalarArrayOpExpr *)
+ make_scalar_array_op(pstate,
+ list_make1(makeString((char *) "=")),
+ true,
+ gentry->node,
+ (Node *) newa,
+ -1);
+
+ or_list = lappend(or_list, (void *) saopexpr);
+ }
+ else
+ {
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ continue;
+ }
+ }
+
+ list_free_deep(groups_list);
+ }
+
+ /* One more trick: assemble correct clause */
+ return (Node *) ((list_length(or_list) > 1) ?
+ makeBoolExpr(OR_EXPR, or_list, expr_orig->location) :
+ linitial(or_list));
+}
/*
* transformExpr -
@@ -208,7 +436,7 @@ transformExprRecurse(ParseState *pstate, Node *expr)
}
case T_BoolExpr:
- result = transformBoolExpr(pstate, (BoolExpr *) expr);
+ result = (Node *)transformBoolExprOr(pstate, (BoolExpr *) expr);
break;
case T_FuncCall:
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index f9dba43b8c0..ddc27e2277c 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -2040,6 +2040,16 @@ struct config_int ConfigureNamesInt[] =
100, 1, MAX_STATISTICS_TARGET,
NULL, NULL, NULL
},
+ {
+ {"or_transform_limit", PGC_USERSET, QUERY_TUNING_OTHER,
+ gettext_noop("Transform a sequence of OR clauses to an IN expression."),
+ gettext_noop("The planner will replace clauses like 'x=c1 OR x=c2 .."
+ "to the clause 'x IN (c1,c2,...)'")
+ },
+ &or_transform_limit,
+ 500, 0, INT_MAX,
+ NULL, NULL, NULL
+ },
{
{"from_collapse_limit", PGC_USERSET, QUERY_TUNING_OTHER,
gettext_noop("Sets the FROM-list size beyond which subqueries "
diff --git a/src/include/parser/parse_expr.h b/src/include/parser/parse_expr.h
index 7d38ca75f7b..891e6a462b9 100644
--- a/src/include/parser/parse_expr.h
+++ b/src/include/parser/parse_expr.h
@@ -17,6 +17,7 @@
/* GUC parameters */
extern PGDLLIMPORT bool Transform_null_equals;
+extern PGDLLIMPORT int or_transform_limit;
extern Node *transformExpr(ParseState *pstate, Node *expr, ParseExprKind exprKind);
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index acfd9d1f4f7..cc229d4dcaf 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1883,6 +1883,121 @@ SELECT count(*) FROM tenk1
10
(1 row)
+SET or_transform_limit = 0;
+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 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 ((tenthous < 2) OR (thousand = ANY ('{42,99}'::integer[])))) 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: (tenthous < 2)
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = ANY ('{42,99}'::integer[]))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = 41)
+(14 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 = 99) AND (tenthous = 2)) OR (thousand = ANY ('{42,41}'::integer[]))))
+ -> BitmapAnd
+ -> Bitmap Index Scan on tenk1_hundred
+ Index Cond: (hundred = 42)
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: ((thousand = 99) AND (tenthous = 2))
+ -> Bitmap Index Scan on tenk1_thous_tenthous
+ Index Cond: (thousand = ANY ('{42,41}'::integer[]))
+(11 rows)
+
+SELECT count(*) FROM tenk1
+ WHERE hundred = 42 AND (thousand = 42 OR thousand = 41 OR thousand = 99 AND tenthous = 2);
+ count
+-------
+ 10
+(1 row)
+
+RESET or_transform_limit;
--
-- Check behavior with duplicate index column contents
--
diff --git a/src/test/regress/expected/guc.out b/src/test/regress/expected/guc.out
index 127c9532976..c052b113eea 100644
--- a/src/test/regress/expected/guc.out
+++ b/src/test/regress/expected/guc.out
@@ -861,7 +861,8 @@ SELECT name FROM tab_settings_flags
name
---------------------------
default_statistics_target
-(1 row)
+ or_transform_limit
+(2 rows)
-- Runtime-computed GUCs should be part of the preset category.
SELECT name FROM tab_settings_flags
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 9b8638f286a..2314d92a6d4 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4207,6 +4207,56 @@ select * from tenk1 a join tenk1 b on
Index Cond: (unique2 = 7)
(19 rows)
+SET or_transform_limit = 0;
+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 = ANY ('{3,7}'::integer[])) 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[])))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 = 1)
+ -> Bitmap Index Scan on tenk1_unique2
+ Index Cond: (unique2 = ANY ('{3,7}'::integer[]))
+(17 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 = 1) AND (b.unique1 = 2)) OR ((a.unique2 = ANY ('{3,7}'::integer[])) AND (b.hundred = 4)) OR (a.unique1 = 3))
+ -> Seq Scan on tenk1 b
+ -> Materialize
+ -> Bitmap Heap Scan on tenk1 a
+ Recheck Cond: ((unique1 < 20) OR (unique1 = 1) OR (unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 3))
+ -> BitmapOr
+ -> Bitmap Index Scan on tenk1_unique1
+ Index Cond: (unique1 < 20)
+ -> 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 = 3)
+(15 rows)
+
+RESET or_transform_limit;
--
-- test placement of movable quals in a parameterized join tree
--
diff --git a/src/test/regress/expected/partition_prune.out b/src/test/regress/expected/partition_prune.out
index 1eb347503aa..d1c5ce8be09 100644
--- a/src/test/regress/expected/partition_prune.out
+++ b/src/test/regress/expected/partition_prune.out
@@ -101,6 +101,28 @@ explain (costs off) select * from lp where a is not null and (a = 'a' or a = 'c'
Filter: ((a IS NOT NULL) AND ((a = 'a'::bpchar) OR (a = 'c'::bpchar)))
(5 rows)
+SET or_transform_limit = 0;
+explain (costs off) select * from lp where a = 'a' or a = 'c';
+ QUERY PLAN
+-----------------------------------------------
+ Append
+ -> Seq Scan on lp_ad lp_1
+ Filter: (a = ANY ('{a,c}'::bpchar[]))
+ -> Seq Scan on lp_bc lp_2
+ Filter: (a = ANY ('{a,c}'::bpchar[]))
+(5 rows)
+
+explain (costs off) select * from lp where a is not null and (a = 'a' or a = 'c');
+ QUERY PLAN
+---------------------------------------------------------------------
+ Append
+ -> Seq Scan on lp_ad lp_1
+ Filter: ((a IS NOT NULL) AND (a = ANY ('{a,c}'::bpchar[])))
+ -> Seq Scan on lp_bc lp_2
+ Filter: ((a IS NOT NULL) AND (a = ANY ('{a,c}'::bpchar[])))
+(5 rows)
+
+RESET or_transform_limit;
explain (costs off) select * from lp where a <> 'g';
QUERY PLAN
------------------------------------
@@ -671,6 +693,163 @@ explain (costs off) select * from rlp where (a = 1 and a = 3) or (a > 1 and a =
Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
(11 rows)
+SET or_transform_limit = 0;
+explain (costs off) select * from rlp where a = 1 or a = 7;
+ QUERY PLAN
+------------------------------------------
+ Seq Scan on rlp2 rlp
+ Filter: (a = ANY ('{1,7}'::integer[]))
+(2 rows)
+
+explain (costs off) select * from rlp where a = 1 or b = 'ab';
+ QUERY PLAN
+-------------------------------------------------------
+ Append
+ -> Seq Scan on rlp1 rlp_1
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+ -> Seq Scan on rlp2 rlp_2
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+ -> Seq Scan on rlp3abcd rlp_3
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+ -> Seq Scan on rlp4_1 rlp_4
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+ -> Seq Scan on rlp4_2 rlp_5
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+ -> Seq Scan on rlp4_default rlp_6
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+ -> Seq Scan on rlp5_1 rlp_7
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+ -> Seq Scan on rlp5_default rlp_8
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+ -> Seq Scan on rlp_default_10 rlp_9
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+ -> Seq Scan on rlp_default_30 rlp_10
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+ -> Seq Scan on rlp_default_null rlp_11
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+ -> Seq Scan on rlp_default_default rlp_12
+ Filter: ((a = 1) OR ((b)::text = 'ab'::text))
+(25 rows)
+
+explain (costs off) select * from rlp where a > 20 and a < 27;
+ QUERY PLAN
+-----------------------------------------
+ Append
+ -> Seq Scan on rlp4_1 rlp_1
+ Filter: ((a > 20) AND (a < 27))
+ -> Seq Scan on rlp4_2 rlp_2
+ Filter: ((a > 20) AND (a < 27))
+(5 rows)
+
+explain (costs off) select * from rlp where a = 29;
+ QUERY PLAN
+------------------------------
+ Seq Scan on rlp4_default rlp
+ Filter: (a = 29)
+(2 rows)
+
+explain (costs off) select * from rlp where a >= 29;
+ QUERY PLAN
+---------------------------------------------
+ Append
+ -> Seq Scan on rlp4_default rlp_1
+ Filter: (a >= 29)
+ -> Seq Scan on rlp5_1 rlp_2
+ Filter: (a >= 29)
+ -> Seq Scan on rlp5_default rlp_3
+ Filter: (a >= 29)
+ -> Seq Scan on rlp_default_30 rlp_4
+ Filter: (a >= 29)
+ -> Seq Scan on rlp_default_default rlp_5
+ Filter: (a >= 29)
+(11 rows)
+
+explain (costs off) select * from rlp where a < 1 or (a > 20 and a < 25);
+ QUERY PLAN
+------------------------------------------------------
+ Append
+ -> Seq Scan on rlp1 rlp_1
+ Filter: ((a < 1) OR ((a > 20) AND (a < 25)))
+ -> Seq Scan on rlp4_1 rlp_2
+ Filter: ((a < 1) OR ((a > 20) AND (a < 25)))
+(5 rows)
+
+explain (costs off) select * from rlp where a = 20 or a = 40;
+ QUERY PLAN
+--------------------------------------------------
+ Append
+ -> Seq Scan on rlp4_1 rlp_1
+ Filter: (a = ANY ('{20,40}'::integer[]))
+ -> Seq Scan on rlp5_default rlp_2
+ Filter: (a = ANY ('{20,40}'::integer[]))
+(5 rows)
+
+explain (costs off) select * from rlp3 where a = 20; /* empty */
+ QUERY PLAN
+--------------------------
+ Result
+ One-Time Filter: false
+(2 rows)
+
+explain (costs off) select * from rlp where a > 1 and a = 10; /* only default */
+ QUERY PLAN
+----------------------------------
+ Seq Scan on rlp_default_10 rlp
+ Filter: ((a > 1) AND (a = 10))
+(2 rows)
+
+explain (costs off) select * from rlp where a > 1 and a >=15; /* rlp3 onwards, including default */
+ QUERY PLAN
+----------------------------------------------
+ Append
+ -> Seq Scan on rlp3abcd rlp_1
+ Filter: ((a > 1) AND (a >= 15))
+ -> Seq Scan on rlp3efgh rlp_2
+ Filter: ((a > 1) AND (a >= 15))
+ -> Seq Scan on rlp3nullxy rlp_3
+ Filter: ((a > 1) AND (a >= 15))
+ -> Seq Scan on rlp3_default rlp_4
+ Filter: ((a > 1) AND (a >= 15))
+ -> Seq Scan on rlp4_1 rlp_5
+ Filter: ((a > 1) AND (a >= 15))
+ -> Seq Scan on rlp4_2 rlp_6
+ Filter: ((a > 1) AND (a >= 15))
+ -> Seq Scan on rlp4_default rlp_7
+ Filter: ((a > 1) AND (a >= 15))
+ -> Seq Scan on rlp5_1 rlp_8
+ Filter: ((a > 1) AND (a >= 15))
+ -> Seq Scan on rlp5_default rlp_9
+ Filter: ((a > 1) AND (a >= 15))
+ -> Seq Scan on rlp_default_30 rlp_10
+ Filter: ((a > 1) AND (a >= 15))
+ -> Seq Scan on rlp_default_default rlp_11
+ Filter: ((a > 1) AND (a >= 15))
+(23 rows)
+
+explain (costs off) select * from rlp where a = 1 and a = 3; /* empty */
+ QUERY PLAN
+--------------------------
+ Result
+ One-Time Filter: false
+(2 rows)
+
+explain (costs off) select * from rlp where (a = 1 and a = 3) or (a > 1 and a = 15);
+ QUERY PLAN
+-------------------------------------------------------------------
+ Append
+ -> Seq Scan on rlp2 rlp_1
+ Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
+ -> Seq Scan on rlp3abcd rlp_2
+ Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
+ -> Seq Scan on rlp3efgh rlp_3
+ Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
+ -> Seq Scan on rlp3nullxy rlp_4
+ Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
+ -> Seq Scan on rlp3_default rlp_5
+ Filter: (((a = 1) AND (a = 3)) OR ((a > 1) AND (a = 15)))
+(11 rows)
+
+RESET or_transform_limit;
-- multi-column keys
create table mc3p (a int, b int, c int) partition by range (a, abs(b), c);
create table mc3p_default partition of mc3p default;
diff --git a/src/test/regress/expected/tidscan.out b/src/test/regress/expected/tidscan.out
index f133b5a4ac7..a2949d3d699 100644
--- a/src/test/regress/expected/tidscan.out
+++ b/src/test/regress/expected/tidscan.out
@@ -56,6 +56,23 @@ SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
(0,2) | 2
(2 rows)
+SET or_transform_limit = 0;
+EXPLAIN (COSTS OFF)
+SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
+ QUERY PLAN
+-------------------------------------------------------
+ Tid Scan on tidscan
+ TID Cond: (ctid = ANY ('{"(0,2)","(0,1)"}'::tid[]))
+(2 rows)
+
+SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
+ ctid | id
+-------+----
+ (0,1) | 1
+ (0,2) | 2
+(2 rows)
+
+RESET or_transform_limit;
-- ctid = ScalarArrayOp - implemented as tidscan
EXPLAIN (COSTS OFF)
SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,1)', '(0,2)']::tid[]);
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index d49ce9f3007..9c6baace0e2 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -737,6 +737,38 @@ SELECT count(*) FROM tenk1
SELECT count(*) FROM tenk1
WHERE hundred = 42 AND (thousand = 42 OR thousand = 99);
+SET or_transform_limit = 0;
+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 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 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);
+RESET or_transform_limit;
+
--
-- Check behavior with duplicate index column contents
--
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 3e5032b04dd..d4d7d853a4a 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1396,6 +1396,16 @@ 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);
+SET or_transform_limit = 0;
+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);
+RESET or_transform_limit;
--
-- test placement of movable quals in a parameterized join tree
diff --git a/src/test/regress/sql/partition_prune.sql b/src/test/regress/sql/partition_prune.sql
index d1c60b8fe9d..77f3e6c3b9b 100644
--- a/src/test/regress/sql/partition_prune.sql
+++ b/src/test/regress/sql/partition_prune.sql
@@ -21,6 +21,12 @@ explain (costs off) select * from lp where a is not null;
explain (costs off) select * from lp where a is null;
explain (costs off) select * from lp where a = 'a' or a = 'c';
explain (costs off) select * from lp where a is not null and (a = 'a' or a = 'c');
+
+SET or_transform_limit = 0;
+explain (costs off) select * from lp where a = 'a' or a = 'c';
+explain (costs off) select * from lp where a is not null and (a = 'a' or a = 'c');
+RESET or_transform_limit;
+
explain (costs off) select * from lp where a <> 'g';
explain (costs off) select * from lp where a <> 'a' and a <> 'd';
explain (costs off) select * from lp where a not in ('a', 'd');
@@ -99,6 +105,22 @@ explain (costs off) select * from rlp where a > 1 and a >=15; /* rlp3 onwards, i
explain (costs off) select * from rlp where a = 1 and a = 3; /* empty */
explain (costs off) select * from rlp where (a = 1 and a = 3) or (a > 1 and a = 15);
+
+SET or_transform_limit = 0;
+explain (costs off) select * from rlp where a = 1 or a = 7;
+explain (costs off) select * from rlp where a = 1 or b = 'ab';
+explain (costs off) select * from rlp where a > 20 and a < 27;
+explain (costs off) select * from rlp where a = 29;
+explain (costs off) select * from rlp where a >= 29;
+explain (costs off) select * from rlp where a < 1 or (a > 20 and a < 25);
+explain (costs off) select * from rlp where a = 20 or a = 40;
+explain (costs off) select * from rlp3 where a = 20; /* empty */
+explain (costs off) select * from rlp where a > 1 and a = 10; /* only default */
+explain (costs off) select * from rlp where a > 1 and a >=15; /* rlp3 onwards, including default */
+explain (costs off) select * from rlp where a = 1 and a = 3; /* empty */
+explain (costs off) select * from rlp where (a = 1 and a = 3) or (a > 1 and a = 15);
+RESET or_transform_limit;
+
-- multi-column keys
create table mc3p (a int, b int, c int) partition by range (a, abs(b), c);
create table mc3p_default partition of mc3p default;
diff --git a/src/test/regress/sql/tidscan.sql b/src/test/regress/sql/tidscan.sql
index 313e0fb9b67..634bf08e5fc 100644
--- a/src/test/regress/sql/tidscan.sql
+++ b/src/test/regress/sql/tidscan.sql
@@ -22,6 +22,12 @@ EXPLAIN (COSTS OFF)
SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
+SET or_transform_limit = 0;
+EXPLAIN (COSTS OFF)
+SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
+SELECT ctid, * FROM tidscan WHERE ctid = '(0,2)' OR '(0,1)' = ctid;
+RESET or_transform_limit;
+
-- ctid = ScalarArrayOp - implemented as tidscan
EXPLAIN (COSTS OFF)
SELECT ctid, * FROM tidscan WHERE ctid = ANY(ARRAY['(0,1)', '(0,2)']::tid[]);
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index e941fb6c82f..c3abb725c8c 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1631,6 +1631,7 @@ NumericVar
OM_uint32
OP
OSAPerGroupState
+OrClauseGroupEntry
OSAPerQueryState
OSInfo
OSSLCipher
--
6.0.1
[text/x-patch] v7-v1-Replace-OR-clause-to-ANY.patch (9.0K, ../[email protected]/4-v7-v1-Replace-OR-clause-to-ANY.patch)
download | inline diff:
From 9e0a0200525e7e72f1a91f658b4674fbf78ea18d Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Thu, 21 Sep 2023 19:15:42 +0300
Subject: [PATCH] Replace OR clause to ANY expressions. Replace (X=N1) OR
(X=N2) ... with X = ANY(N1, N2) on the stage of the optimiser when we are
still working with a tree expression. Firstly, we do not try to make a
transformation for "non-or" expressions or inequalities and the creation of a
relation with "or" expressions occurs according to the same scenario.
Secondly, we do not make transformations if there are less than set
or_transform_limit. Thirdly, it is worth considering that we consider "or"
expressions only at the current level.
Authors: Alena Rybakina <[email protected]>, Andrey Lepikhov <[email protected]>
Reviewed-by: Peter Geoghegan <[email protected]>, Ranier Vilela <[email protected]>
---
src/backend/optimizer/plan/planner.c | 3 +-
src/backend/optimizer/util/orclauses.c | 232 +++++++++++++++++++++++++
src/include/optimizer/orclauses.h | 2 +-
3 files changed, 235 insertions(+), 2 deletions(-)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 44efb1f4ebc..80935cec7aa 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -67,6 +67,7 @@
#include "utils/rel.h"
#include "utils/selfuncs.h"
#include "utils/syscache.h"
+#include "optimizer/orclauses.h"
/* GUC parameters */
double cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
@@ -1169,7 +1170,7 @@ preprocess_expression(PlannerInfo *root, Node *expr, int kind)
if (kind == EXPRKIND_QUAL)
{
expr = (Node *) canonicalize_qual((Expr *) expr, false);
-
+expr = transform_ors(root, (Expr *) expr);
#ifdef OPTIMIZER_DEBUG
printf("After canonicalize_qual()\n");
pprint(expr);
diff --git a/src/backend/optimizer/util/orclauses.c b/src/backend/optimizer/util/orclauses.c
index 6ef9d14b902..805f4b7294a 100644
--- a/src/backend/optimizer/util/orclauses.c
+++ b/src/backend/optimizer/util/orclauses.c
@@ -22,6 +22,10 @@
#include "optimizer/optimizer.h"
#include "optimizer/orclauses.h"
#include "optimizer/restrictinfo.h"
+#include "utils/lsyscache.h"
+#include "parser/parse_expr.h"
+#include "parser/parse_coerce.h"
+#include "parser/parse_oper.h"
static bool is_safe_restriction_clause_for(RestrictInfo *rinfo, RelOptInfo *rel);
@@ -29,7 +33,235 @@ static Expr *extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel);
static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
Expr *orclause, RestrictInfo *join_or_rinfo);
+typedef struct OrClauseGroupEntry
+{
+ Node *node;
+ List *consts;
+ Oid scalar_type;
+ Oid opno;
+ Expr *expr;
+} OrClauseGroupEntry;
+
+static Node *
+transform_ors_for_rel(BoolExpr *expr_orig)
+{
+ List *or_list = NIL;
+ List *groups_list = NIL;
+ ListCell *lc;
+
+ /* If this is not an 'OR' expression, skip the transformation */
+ if (expr_orig->boolop != OR_EXPR ||
+ list_length(expr_orig->args) < 1)
+ return (Node*) expr_orig;
+
+ foreach(lc, expr_orig->args)
+ {
+ Node *orqual = lfirst(lc);
+ Node *const_expr;
+ Node *nconst_expr;
+ ListCell *lc_groups;
+ OrClauseGroupEntry *gentry;
+
+ if (!IsA(orqual, OpExpr))
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ /*
+ * 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.
+ */
+ if (IsA(get_leftop(orqual), Const))
+ {
+ nconst_expr = get_rightop(orqual);
+ const_expr = get_leftop(orqual);
+ }
+ else if (IsA(get_rightop(orqual), Const))
+ {
+ const_expr = get_rightop(orqual);
+ nconst_expr = get_leftop(orqual);
+ }
+ else
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ if (!op_mergejoinable(((OpExpr *) orqual)->opno, exprType(nconst_expr)))
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ /*
+ * At this point we definitely have a transformable clause.
+ * Classify it and add into specific group of clauses, or create new
+ * group.
+ * TODO: to manage complexity in the case of many different clauses
+ * (X1=C1) OR (X2=C2 OR) ... (XN = CN) we could invent something
+ * like a hash table. But also we believe, that the case of many
+ * different variable sides is very rare.
+ */
+ foreach(lc_groups, groups_list)
+ {
+ OrClauseGroupEntry *v = (OrClauseGroupEntry *) lfirst(lc_groups);
+
+ Assert(v->node != NULL);
+
+ if (equal(v->node, nconst_expr))
+ {
+ v->consts = lappend(v->consts, const_expr);
+ nconst_expr = NULL;
+ break;
+ }
+ }
+
+ if (nconst_expr == NULL)
+ /*
+ * The clause classified successfully and added into existed
+ * clause group.
+ */
+ continue;
+
+ /* New clause group needed */
+ gentry = palloc(sizeof(OrClauseGroupEntry));
+ gentry->node = nconst_expr;
+ gentry->consts = list_make1(const_expr);
+ gentry->expr = (Expr *) orqual;
+ groups_list = lappend(groups_list, (void *) gentry);
+ }
+ if (groups_list == NIL)
+ {
+ /*
+ * No any transformations possible with this list of arguments. Here we
+ * already made all underlying transformations. Thus, just return the
+ * transformed bool expression.
+ */
+ return (Node *) expr_orig;
+ }
+ else
+ {
+ ListCell *lc_args;
+
+ /* Let's convert each group of clauses to an IN operation. */
+
+ /*
+ * Go through the list of groups and convert each, where number of
+ * consts more than 1. trivial groups move to OR-list again
+ */
+
+ foreach(lc_args, groups_list)
+ {
+ OrClauseGroupEntry *gentry = (OrClauseGroupEntry *) lfirst(lc_args);
+ List *allexprs;
+ Oid scalar_type;
+ Oid array_type;
+
+ Assert(list_length(gentry->consts) > 0);
+
+ if (list_length(gentry->consts) == 1)
+ {
+ /*
+ * Only one element in the class. Return rinfo into the BoolExpr
+ * args list unchanged.
+ */
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ continue;
+ }
+
+ /*
+ * Do the transformation.
+ *
+ * First of all, try to select a common type for the array elements.
+ * Note that since the LHS' type is first in the list, it will be
+ * preferred when there is doubt (eg, when all the RHS items are
+ * unknown literals).
+ *
+ * Note: use list_concat here not lcons, to avoid damaging rnonvars.
+ *
+ * As a source of insides, use make_scalar_array_op()
+ */
+ allexprs = list_concat(list_make1(gentry->node), gentry->consts);
+ scalar_type = select_common_type(NULL, allexprs, NULL, NULL);
+
+ if (scalar_type != RECORDOID && OidIsValid(scalar_type))
+ array_type = get_array_type(scalar_type);
+ else
+ array_type = InvalidOid;
+
+ if (array_type != InvalidOid)
+ {
+ /*
+ * OK: coerce all the right-hand non-Var inputs to the common
+ * type and build an ArrayExpr for them.
+ */
+ List *aexprs;
+ ArrayExpr *newa;
+ ScalarArrayOpExpr *saopexpr;
+ ListCell *l;
+
+ aexprs = NIL;
+
+ foreach(l, gentry->consts)
+ {
+ Node *rexpr = (Node *) lfirst(l);
+
+ rexpr = coerce_to_common_type(NULL, rexpr,
+ scalar_type,
+ "IN");
+ aexprs = lappend(aexprs, rexpr);
+ }
+
+ newa = makeNode(ArrayExpr);
+ /* array_collid will be set by parse_collate.c */
+ newa->element_typeid = scalar_type;
+ newa->array_typeid = array_type;
+ newa->multidims = false;
+ newa->elements = aexprs;
+ newa->location = -1;
+
+ saopexpr =
+ (ScalarArrayOpExpr *)
+ make_scalar_array_op(NULL,
+ list_make1(makeString((char *) "=")),
+ true,
+ gentry->node,
+ (Node *) newa,
+ -1);
+ saopexpr->inputcollid = exprInputCollation((Node *)gentry->expr);;
+
+ or_list = lappend(or_list, (void *) saopexpr);
+ }
+ else
+ {
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ continue;
+ }
+ }
+
+ list_free_deep(groups_list);
+ }
+
+ /* One more trick: assemble correct clause */
+ return (Node *) ((list_length(or_list) > 1) ?
+ makeBoolExpr(OR_EXPR, or_list, expr_orig->location) :
+ linitial(or_list));
+}
+Node *
+transform_ors(PlannerInfo *root, Expr *jtnode)
+{
+ if (IsA(jtnode, BoolExpr))
+ return transform_ors_for_rel((BoolExpr *) jtnode);
+ return (Node *) jtnode;
+}
/*
* extract_restriction_or_clauses
* Examine join OR-of-AND clauses to see if any useful restriction OR
diff --git a/src/include/optimizer/orclauses.h b/src/include/optimizer/orclauses.h
index f9dbe6a2972..6a232aeb3ed 100644
--- a/src/include/optimizer/orclauses.h
+++ b/src/include/optimizer/orclauses.h
@@ -17,5 +17,5 @@
#include "nodes/pathnodes.h"
extern void extract_restriction_or_clauses(PlannerInfo *root);
-
+extern Node * transform_ors(PlannerInfo *root, Expr *jtnode);
#endif /* ORCLAUSES_H */
--
2.34.1
[text/x-patch] v7-v2-Replace-OR-clause-to-ANY.patch (10.2K, ../[email protected]/5-v7-v2-Replace-OR-clause-to-ANY.patch)
download | inline diff:
From 84ba19a988447bd5e19132080375101e1ae2e63b Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Tue, 26 Sep 2023 09:23:44 +0300
Subject: [PATCH] Replace OR clause to ANY expressions. Replace (X=N1) OR
(X=N2) ... with X = ANY(N1, N2) on the stage of the optimiser when we are
still working with a tree expression. Firstly, we do not try to make a
transformation for "non-or" expressions or inequalities and the creation of a
relation with "or" expressions occurs according to the same scenario.
Secondly, we do not make transformations if there are less than set
or_transform_limit. Thirdly, it is worth considering that we consider "or"
expressions only at the current level.
Authors: Alena Rybakina <[email protected]>, Andrey Lepikhov <[email protected]>
Reviewed-by: Peter Geoghegan <[email protected]>, Ranier Vilela <[email protected]>
---
src/backend/optimizer/util/orclauses.c | 295 +++++++++++++++++++++++++
1 file changed, 295 insertions(+)
diff --git a/src/backend/optimizer/util/orclauses.c b/src/backend/optimizer/util/orclauses.c
index 6ef9d14b902..b4ac9370461 100644
--- a/src/backend/optimizer/util/orclauses.c
+++ b/src/backend/optimizer/util/orclauses.c
@@ -22,6 +22,10 @@
#include "optimizer/optimizer.h"
#include "optimizer/orclauses.h"
#include "optimizer/restrictinfo.h"
+#include "utils/lsyscache.h"
+#include "parser/parse_expr.h"
+#include "parser/parse_coerce.h"
+#include "parser/parse_oper.h"
static bool is_safe_restriction_clause_for(RestrictInfo *rinfo, RelOptInfo *rel);
@@ -30,6 +34,292 @@ static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
Expr *orclause, RestrictInfo *join_or_rinfo);
+int or_transform_limit = 2;
+
+typedef struct OrClauseGroupEntry
+{
+ Node *node;
+ List *consts;
+ Oid scalar_type;
+ Oid opno;
+ Expr *expr;
+} OrClauseGroupEntry;
+
+static List *
+transform_ors(PlannerInfo *root, List *baserestrictinfo)
+{
+ ListCell *lc_clause, *lc_or;
+ List *modified_rinfo = NIL;
+ bool something_changed = false;
+
+
+ foreach (lc_clause, baserestrictinfo)
+ {
+ RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc_clause);
+ RestrictInfo *rinfo_base = copyObject(rinfo);
+ List *groups_list = NIL;
+ OrClauseGroupEntry *gentry;
+ List *or_list = NIL;
+ bool change_apply = false;
+
+ if (!restriction_is_or_clause(rinfo) ||
+ list_length(((BoolExpr *) rinfo->clause)->args) < or_transform_limit)
+ {
+ /* Add a clause without changes */
+ modified_rinfo = lappend(modified_rinfo, copyObject(rinfo));
+ continue;
+ }
+ foreach (lc_or, ((BoolExpr *) rinfo->clause)->args)
+ {
+ Node *orqual = lfirst(lc_or);
+ Node *const_expr;
+ Node *nconst_expr;
+ ListCell *lc_groups;
+
+ /* If this is not an 'OR' expression, skip the transformation */
+ if (!IsA(orqual, OpExpr))
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+
+ /*
+ * 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.
+ */
+ if (IsA(get_leftop(orqual), Const))
+ {
+ nconst_expr = get_rightop(orqual);
+ const_expr = get_leftop(orqual);
+ }
+ else if (IsA(get_rightop(orqual), Const))
+ {
+ const_expr = get_rightop(orqual);
+ nconst_expr = get_leftop(orqual);
+ }
+ else
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ if (!op_mergejoinable(((OpExpr *) orqual)->opno, exprType(nconst_expr)))
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ /*
+ * At this point we definitely have a transformable clause.
+ * Classify it and add into specific group of clauses, or create new
+ * group.
+ * TODO: to manage complexity in the case of many different clauses
+ * (X1=C1) OR (X2=C2 OR) ... (XN = CN) we could invent something
+ * like a hash table. But also we believe, that the case of many
+ * different variable sides is very rare.
+ */
+ foreach(lc_groups, groups_list)
+ {
+ OrClauseGroupEntry *v = (OrClauseGroupEntry *) lfirst(lc_groups);
+
+ Assert(v->node != NULL);
+
+ if (equal(v->node, nconst_expr))
+ {
+ v->consts = lappend(v->consts, const_expr);
+ nconst_expr = NULL;
+ break;
+ }
+ }
+
+ if (nconst_expr == NULL)
+ /*
+ * The clause classified successfully and added into existed
+ * clause group.
+ */
+ continue;
+
+ /* New clause group needed */
+ gentry = palloc(sizeof(OrClauseGroupEntry));
+ gentry->node = nconst_expr;
+ gentry->consts = list_make1(const_expr);
+ gentry->expr = (Expr *) orqual;
+ groups_list = lappend(groups_list, (void *) gentry);
+ }
+
+ if (groups_list == NIL)
+ {
+ /*
+ * No any transformations possible with this list of arguments. Here we
+ * already made all underlying transformations. Thus, just return the
+ * transformed bool expression.
+ */
+ modified_rinfo = lappend(modified_rinfo, copyObject(rinfo));
+ continue;
+ }
+ else
+ {
+ ListCell *lc_args;
+
+ /* Let's convert each group of clauses to an IN operation. */
+
+ /*
+ * Go through the list of groups and convert each, where number of
+ * consts more than 1. trivial groups move to OR-list again
+ */
+
+ foreach(lc_args, groups_list)
+ {
+ List *allexprs;
+ Oid scalar_type;
+ Oid array_type;
+ gentry = (OrClauseGroupEntry *) lfirst(lc_args);
+
+ Assert(list_length(gentry->consts) > 0);
+
+ if (list_length(gentry->consts) == 1)
+ {
+ /*
+ * Only one element in the class. Return rinfo into the BoolExpr
+ * args list unchanged.
+ */
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ continue;
+ }
+
+ /*
+ * Do the transformation.
+ *
+ * First of all, try to select a common type for the array elements.
+ * Note that since the LHS' type is first in the list, it will be
+ * preferred when there is doubt (eg, when all the RHS items are
+ * unknown literals).
+ *
+ * Note: use list_concat here not lcons, to avoid damaging rnonvars.
+ *
+ * As a source of insides, use make_scalar_array_op()
+ */
+ allexprs = list_concat(list_make1(gentry->node), gentry->consts);
+ scalar_type = select_common_type(NULL, allexprs, NULL, NULL);
+
+ if (scalar_type != RECORDOID && OidIsValid(scalar_type))
+ array_type = get_array_type(scalar_type);
+ else
+ array_type = InvalidOid;
+
+ if (array_type != InvalidOid)
+ {
+ /*
+ * OK: coerce all the right-hand non-Var inputs to the common
+ * type and build an ArrayExpr for them.
+ */
+ List *aexprs;
+ ArrayExpr *newa;
+ ScalarArrayOpExpr *saopexpr;
+ ListCell *l;
+
+ aexprs = NIL;
+
+ foreach(l, gentry->consts)
+ {
+ Node *rexpr = (Node *) lfirst(l);
+
+ rexpr = coerce_to_common_type(NULL, rexpr,
+ scalar_type,
+ "IN");
+ aexprs = lappend(aexprs, rexpr);
+ }
+
+ newa = makeNode(ArrayExpr);
+ /* array_collid will be set by parse_collate.c */
+ newa->element_typeid = scalar_type;
+ newa->array_typeid = array_type;
+ newa->multidims = false;
+ newa->elements = aexprs;
+ newa->location = -1;
+
+ saopexpr =
+ (ScalarArrayOpExpr *)
+ make_scalar_array_op(NULL,
+ list_make1(makeString((char *) "=")),
+ true,
+ gentry->node,
+ (Node *) newa,
+ -1);
+ saopexpr->inputcollid = exprInputCollation((Node *)gentry->expr);;
+
+ or_list = lappend(or_list, (void *) saopexpr);
+
+ something_changed = true;
+ change_apply = true;
+ }
+ else
+ {
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ continue;
+ }
+
+ if (!change_apply)
+ {
+ /*
+ * Each group contains only one element - use rinfo as is.
+ */
+ modified_rinfo = lappend(modified_rinfo, rinfo);
+ continue;
+ }
+
+ /*
+ * Make a new version of the restriction. Remember source restriction
+ * can be used in another path (SeqScan, for example).
+ */
+
+ /* One more trick: assemble correct clause */
+ rinfo = make_restrictinfo(root,
+ list_length(or_list) > 1 ? make_orclause(or_list) :
+ (Expr *) linitial(or_list),
+ rinfo->has_clone,
+ rinfo->is_clone,
+ rinfo->is_pushed_down,
+ rinfo->pseudoconstant,
+ rinfo->security_level,
+ rinfo->required_relids,
+ rinfo->outer_relids,
+ rinfo->outer_relids);
+ rinfo->eval_cost=rinfo_base->eval_cost;
+ rinfo->norm_selec=rinfo_base->norm_selec;
+ rinfo->outer_selec=rinfo_base->outer_selec;
+ rinfo->left_bucketsize=rinfo_base->left_bucketsize;
+ rinfo->right_bucketsize=rinfo_base->right_bucketsize;
+ rinfo->left_mcvfreq=rinfo_base->left_mcvfreq;
+ rinfo->right_mcvfreq=rinfo_base->right_mcvfreq;
+ modified_rinfo = lappend(modified_rinfo, rinfo);
+ something_changed = true;
+ }
+ }
+ list_free(or_list);
+ list_free_deep(groups_list);
+
+ }
+ /*
+ * Check if transformation has made. If nothing changed - return
+ * baserestrictinfo as is.
+ */
+ if (something_changed)
+ {
+ return modified_rinfo;
+ }
+
+ list_free(modified_rinfo);
+ return baserestrictinfo;
+}
+
/*
* extract_restriction_or_clauses
* Examine join OR-of-AND clauses to see if any useful restriction OR
@@ -93,6 +383,9 @@ extract_restriction_or_clauses(PlannerInfo *root)
if (rel->reloptkind != RELOPT_BASEREL)
continue;
+ rel->baserestrictinfo = transform_ors(root, rel->baserestrictinfo);
+ rel->joininfo = transform_ors(root, rel->joininfo);
+
/*
* Find potentially interesting OR joinclauses. We can use any
* joinclause that is considered safe to move to this rel by the
@@ -114,7 +407,9 @@ extract_restriction_or_clauses(PlannerInfo *root)
* and insert it into the rel's restrictinfo list if so.
*/
if (orclause)
+ {
consider_new_or_clause(root, rel, orclause, rinfo);
+ }
}
}
}
--
2.34.1
[image/png] flamegraph1.png (106.0K, ../[email protected]/6-flamegraph1.png)
download | view image
[image/png] flamegraph2.png (159.5K, ../[email protected]/7-flamegraph2.png)
download | view image
view thread (33+ messages) latest in thread
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]
Subject: Re: POC, WIP: OR-clause support for indexes
In-Reply-To: <[email protected]>
* 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