public inbox for [email protected]
help / color / mirror / Atom feed[PATCH 03/17] avoid shadow vars: pg_dump.c: owning_tab
25+ messages / 6 participants
[nested] [flat]
* [PATCH 03/17] avoid shadow vars: pg_dump.c: owning_tab
@ 2022-08-16 21:22 Justin Pryzby <[email protected]>
0 siblings, 0 replies; 25+ messages in thread
From: Justin Pryzby @ 2022-08-16 21:22 UTC (permalink / raw)
backpatch to v15
commit 344d62fb9a978a72cf8347f0369b9ee643fd0b31
Author: Peter Eisentraut <[email protected]>
Date: Thu Apr 7 16:13:23 2022 +0200
Unlogged sequences
---
src/bin/pg_dump/pg_dump.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/bin/pg_dump/pg_dump.c b/src/bin/pg_dump/pg_dump.c
index 5c196d66985..ecf29f3c52a 100644
--- a/src/bin/pg_dump/pg_dump.c
+++ b/src/bin/pg_dump/pg_dump.c
@@ -16799,7 +16799,7 @@ dumpSequence(Archive *fout, const TableInfo *tbinfo)
*/
if (OidIsValid(tbinfo->owning_tab) && !tbinfo->is_identity_sequence)
{
- TableInfo *owning_tab = findTableByOid(tbinfo->owning_tab);
+ owning_tab = findTableByOid(tbinfo->owning_tab);
if (owning_tab == NULL)
pg_fatal("failed sanity check, parent table with OID %u of sequence with OID %u not found",
--
2.17.1
--uTRFFR9qmiCqR05s
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment;
filename="0004-avoid-shadow-vars-tablesync.c-first.patch"
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
@ 2023-06-27 19:50 Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
0 siblings, 1 reply; 25+ messages in thread
From: Peter Geoghegan @ 2023-06-27 19:50 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Alena Rybakina <[email protected]>; Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected]
On Tue, Jun 27, 2023 at 6:19 AM Alena Rybakina <[email protected]> wrote:
> I learned something new from your letter, thank you very much for that!
Cool. The MDAM paper is also worth a read:
https://vldb.org/conf/1995/P710.PDF
Some of the techniques it describes are already in Postgres. With
varying degrees of maturity.
The paper actually mentions OR optimization at one point, under
"Duplicate Elimination". The general idea is that ScalarArrayOpExpr
execution can "eliminate duplicates before the data is read". The
important underlying principle is that it can be really useful to give
the B-Tree code the context it requires to be clever about stuff like
that. We can do this by (say) using one ScalarArrayOpExpr, rather than
using two or more index scans that the B-Tree code will treat as
independent things. So a lot of the value in your patch comes from the
way that it can enable other optimizations (the immediate benefits are
also nice).
In the past, OR optimizations have been prototyped that were later
withdrawn/rejected because the duplicate elimination aspect was...too
scary [1]. It's very easy to see that ScalarArrayOpExpr index scans
don't really have the same problem. "Giving the B-Tree code the
required context" helps here too.
> I analyzed the buffer consumption when I ran control regression tests using my patch. diff shows me that there is no difference between the number of buffer block scans without and using my patch, as far as I have seen. (regression.diffs)
To be clear, I wasn't expecting that there'd be any regressions from
your patch. Intuitively, it seems like this optimization should make
the query plan do almost the same thing at execution time -- just
slightly more efficiently on average, and much more efficiently in
some individual cases.
It would probably be very hard for the optimizer to model/predict how
much work it can save by using a ScalarArrayOpExpr instead of an
"equivalent" set of bitmap index scans, OR'd together. But it doesn't
necessarily matter -- the only truly critical detail is understanding
the worst case for the transformation optimization. It cannot be too
bad (maybe it's ~zero added runtime overhead relative to not doing the
transformation, even?). At the same time, nbtree can be clever about
ScalarArrayOpExpr execution at runtime (once that's implemented),
without ever needing to make any kind of up-front commitment to
navigating through the index in any particular way. It's all dynamic,
and can be driven by the actual observed characteristics of the index
structure.
In other words, we don't really need to gamble (in the planner, or at
execution time). We're just keeping our options open in more cases.
(My thinking on these topics was influenced by Goetz Graefe -- "choice
is confusion" [2]).
[1] https://www.postgresql.org/message-id/flat/1397.1486598083%40sss.pgh.pa.us#310f974a8dc84478d6d3c70f3...
[2] https://sigmodrecord.org/publications/sigmodRecord/2009/pdfs/05_Profiles_Graefe.pdf
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
@ 2023-06-29 09:32 ` Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-25 23:47 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
0 siblings, 2 replies; 25+ messages in thread
From: Alena Rybakina @ 2023-06-29 09:32 UTC (permalink / raw)
To: Peter Geoghegan <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Alena Rybakina <[email protected]>; Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected]
Hi! I'm sorry I didn't answer you right away, I was too busy with work.
On 27.06.2023 22:50, Peter Geoghegan wrote:
> On Tue, Jun 27, 2023 at 6:19 AM Alena Rybakina<[email protected]> wrote:
>> I learned something new from your letter, thank you very much for that!
> Cool. The MDAM paper is also worth a read:
>
> https://vldb.org/conf/1995/P710.PDF
>
> Some of the techniques it describes are already in Postgres. With
> varying degrees of maturity.
>
> The paper actually mentions OR optimization at one point, under
> "Duplicate Elimination". The general idea is that ScalarArrayOpExpr
> execution can "eliminate duplicates before the data is read". The
> important underlying principle is that it can be really useful to give
> the B-Tree code the context it requires to be clever about stuff like
> that. We can do this by (say) using one ScalarArrayOpExpr, rather than
> using two or more index scans that the B-Tree code will treat as
> independent things. So a lot of the value in your patch comes from the
> way that it can enable other optimizations (the immediate benefits are
> also nice).
>
> In the past, OR optimizations have been prototyped that were later
> withdrawn/rejected because the duplicate elimination aspect was...too
> scary [1]. It's very easy to see that ScalarArrayOpExpr index scans
> don't really have the same problem. "Giving the B-Tree code the
> required context" helps here too.
>
Thank you for the explanation and the material provided) unfortunately,
I am still only studying the article and at the moment I cannot write
more. To be honest, I didn't think about the fact that my optimization
can help eliminate duplicates before reading the data before.
I am still only in the process of familiarizing myself with the thread
[1] (reference from your letter), but I have already seen that there are
problems related, for example, to when "or" expressions refer to the
parent element.
I think, I would face the similar problems if I complicate the current
code, for example, so that not only or expressions standing on the same
level are written in any, but also on different ones without violating
the logic of the priority of executing operators.
For example, this query works now:
postgres=# EXPLAIN (analyze, COSTS OFF)
SELECT oid,relname FROM pg_class
WHERE
(oid = 13779 OR oid = 2) OR (oid = 4 OR oid = 5) OR
relname = 'pg_extension'
;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Seq Scan on pg_class (actual time=0.086..0.140 rows=1 loops=1)
Filter: ((oid = ANY ('{4,5}'::oid[])) OR (oid = ANY
('{13779,2}'::oid[])) OR (relname = 'pg_extension'::name))
Rows Removed by Filter: 412
Planning Time: 2.135 ms
Execution Time: 0.160 ms
(5 rows)
But I would like it works such as:
QUERY PLAN
--------------------------------------------------------------------------------------
Seq Scan on pg_class (actual time=0.279..0.496 rows=1 loops=1)
Filter: ((oid = ANY ('{13779,2,4,5}'::oid[])) OR (relname =
'pg_extension'::name))
Rows Removed by Filter: 412
Planning Time: 0.266 ms
Execution Time: 0.536 ms
(5 rows)
>> I analyzed the buffer consumption when I ran control regression tests using my patch. diff shows me that there is no difference between the number of buffer block scans without and using my patch, as far as I have seen. (regression.diffs)
> To be clear, I wasn't expecting that there'd be any regressions from
> your patch. Intuitively, it seems like this optimization should make
> the query plan do almost the same thing at execution time -- just
> slightly more efficiently on average, and much more efficiently in
> some individual cases.
>
> It would probably be very hard for the optimizer to model/predict how
> much work it can save by using a ScalarArrayOpExpr instead of an
> "equivalent" set of bitmap index scans, OR'd together. But it doesn't
> necessarily matter -- the only truly critical detail is understanding
> the worst case for the transformation optimization.
Yes, I agree with you and I have yet to analyze this.
> It cannot be too
> bad (maybe it's ~zero added runtime overhead relative to not doing the
> transformation, even?).
I haven't seen a major performance degradation so far, but to be honest,
I have not conducted a detailed analysis on other types of queries other
than x=1 or x=2 or x=1 or y=2, etc. As soon as something is known, I
will provide the data, it is very interesting to me.
> At the same time, nbtree can be clever about
> ScalarArrayOpExpr execution at runtime (once that's implemented),
> without ever needing to make any kind of up-front commitment to
> navigating through the index in any particular way. It's all dynamic,
> and can be driven by the actual observed characteristics of the index
> structure.
>
> In other words, we don't really need to gamble (in the planner, or at
> execution time). We're just keeping our options open in more cases.
> (My thinking on these topics was influenced by Goetz Graefe -- "choice
> is confusion" [2]).
Unfortunately, when I tried to make a transformation at the stage of
index formation, I encountered too incorrect an assessment of the
selectivity of relation, which affected the incorrect calculation of the
cost and cardinality. I couldn't solve this problem.
My diff (transform_or_v0.diff). I got this result:
CREATE TABLE tenk1 (unique1int, unique2int, tenint, hundredint);
insert into tenk1 SELECT x,x,x,x FROM generate_series(1,50000) as x;
CREATE INDEX a_idx1 ON tenk1(unique1);
CREATE INDEX a_idx2 ON tenk1(unique2);
CREATE INDEX a_hundred ON tenk1(hundred);
postgres=# explain analyze
select * from tenk1 a join tenk1 b on
a.unique2 = 3 or a.unique2 = 7 or a.unique1 = 1;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.00..15627479.50 rows=1250050000 width=32) (actual time=0.040..75.531 rows=150000 loops=1)
-> Seq Scan on tenk1 b (cost=0.00..771.00 rows=50000 width=16) (actual time=0.022..5.467 rows=50000 loops=1)
-> Materialize (cost=0.00..1146.01 rows=25001 width=16) (actual time=0.000..0.001 rows=3 loops=50000)
-> Seq Scan on tenk1 a (cost=0.00..1021.00 rows=25001 width=16) (actual time=0.011..22.789 rows=3 loops=1)
Filter: ((unique2 = ANY (ARRAY[3, 7])) OR (unique1 = 1))
Rows Removed by Filter: 49997
Planning Time: 0.427 ms
Execution Time: 80.027 ms
(8 rows)
The current patch's result:
postgres=# set enable_bitmapscan ='off';
SET
postgres=# explain analyze
select * from tenk1 a join tenk1 b on
a.unique2 = 3 or a.unique2 = 7 or a.unique1 = 1;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.00..22247.02 rows=1350000 width=32) (actual time=0.094..373.627 rows=1350000 loops=1)
-> Seq Scan on tenk1 b (cost=0.00..2311.00 rows=150000 width=16) (actual time=0.051..14.667 rows=150000 loops=1)
-> Materialize (cost=0.00..3061.05 rows=9 width=16) (actual time=0.000..0.001 rows=9 loops=150000)
-> Seq Scan on tenk1 a (cost=0.00..3061.00 rows=9 width=16) (actual time=0.026..42.389 rows=9 loops=1)
Filter: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
Rows Removed by Filter: 149991
Planning Time: 0.414 ms
Execution Time: 409.154 ms
(8 rows)
> [1]https://www.postgresql.org/message-id/flat/1397.1486598083%40sss.pgh.pa.us#310f974a8dc84478d6d3c70f3...
> [2]https://sigmodrecord.org/publications/sigmodRecord/2009/pdfs/05_Profiles_Graefe.pdf
Thank you again for the explanations and the material provided. I will
carefully study everything as soon as possible and will write if there
are any thoughts or if there are ideas about my patch.
--
Regards,
Alena Rybakina
Postgres Professional
Attachments:
[text/x-patch] transform_or_v0.diff (9.0K, ../../[email protected]/3-transform_or_v0.diff)
download | inline diff:
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 0065c8992bd..8ef3438d78c 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -193,6 +193,273 @@ static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
EquivalenceClass *ec, EquivalenceMember *em,
void *arg);
+typedef struct OrClauseGroupEntry
+{
+ Node *node;
+ List *consts;
+ Oid collation;
+ Oid opno;
+ RestrictInfo *rinfo;
+} OrClauseGroupEntry;
+
+/*
+ * Pass through baserestrictinfo clauses and try to convert OR clauses into IN
+ * Return a modified clause list or just the same baserestrictinfo, if no
+ * changes have made.
+ * XXX: do not change source list of clauses at all.
+ */
+static List *
+transform_ors(PlannerInfo *root, List *baserestrictinfo)
+{
+ ListCell *lc;
+ ListCell *lc_cp;
+ List *modified_rinfo = NIL;
+ bool something_changed = false;
+ List *baserestrictinfo_origin = list_copy(baserestrictinfo);
+
+ /*
+ * Complexity of a clause could be arbitrarily sophisticated. Here, we will
+ * look up only on the top level of clause list.
+ * XXX: It is substantiated? Could we change something here?
+ */
+ forboth (lc, baserestrictinfo, lc_cp, baserestrictinfo_origin)
+ {
+ RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
+ RestrictInfo *rinfo_base = lfirst_node(RestrictInfo, lc_cp);
+ List *or_list = NIL;
+ ListCell *lc_eargs,
+ *lc_rargs,
+ *lc_args;
+ List *groups_list = NIL;
+ bool change_apply = false;
+
+ if (!restriction_is_or_clause(rinfo))
+ {
+ /* Add a clause without changes */
+ modified_rinfo = lappend(modified_rinfo, rinfo);
+ continue;
+ }
+
+ /*
+ * NOTE:
+ * It is an OR-clause. So, rinfo->orclause is a BoolExpr node, contains
+ * a list of sub-restrictinfo args, and rinfo->clause - which is the
+ * same expression, made from bare clauses. To not break selectivity
+ * caches and other optimizations, use both:
+ * - use rinfos from orclause if no transformation needed
+ * - use bare quals from rinfo->clause in the case of transformation,
+ * to create new RestrictInfo: in this case we have no options to avoid
+ * selectivity estimation procedure.
+ */
+ forboth(lc_eargs, ((BoolExpr *) rinfo->clause)->args,
+ lc_rargs, ((BoolExpr *) rinfo->orclause)->args)
+ {
+ Expr *bare_orarg = (Expr *) lfirst(lc_eargs);
+ RestrictInfo *sub_rinfo;
+ Node *const_expr;
+ Node *non_const_expr;
+ ListCell *lc_groups;
+ OrClauseGroupEntry *gentry;
+ Oid opno;
+
+ /* It may be one more boolean expression, skip it for now */
+ if (!IsA(lfirst(lc_rargs), RestrictInfo))
+ {
+ or_list = lappend(or_list, (void *) bare_orarg);
+ continue;
+ }
+
+ sub_rinfo = lfirst_node(RestrictInfo, lc_rargs);
+
+ /* Check: it is an expr of the form 'F(x) oper ConstExpr' */
+ if (!IsA(bare_orarg, OpExpr) ||
+ !(bms_is_empty(sub_rinfo->left_relids) ^
+ bms_is_empty(sub_rinfo->right_relids)) ||
+ contain_volatile_functions((Node *) bare_orarg))
+ {
+ /* Again, it's not the expr we can transform */
+ or_list = lappend(or_list, (void *) bare_orarg);
+ continue;
+ }
+
+ /* Get pointers to constant and expression sides of the clause */
+ const_expr =bms_is_empty(sub_rinfo->left_relids) ?
+ get_leftop(sub_rinfo->clause) :
+ get_rightop(sub_rinfo->clause);
+ non_const_expr = bms_is_empty(sub_rinfo->left_relids) ?
+ get_rightop(sub_rinfo->clause) :
+ get_leftop(sub_rinfo->clause);
+
+ opno = ((OpExpr *) sub_rinfo->clause)->opno;
+ if (!op_mergejoinable(opno, exprType(non_const_expr)))
+ {
+ /* And again, filter out non-equality operators */
+ or_list = lappend(or_list, (void *) bare_orarg);
+ 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 (htab key ???).
+ */
+ foreach(lc_groups, groups_list)
+ {
+ OrClauseGroupEntry *v = (OrClauseGroupEntry *) lfirst(lc_groups);
+
+ Assert(v->node != NULL);
+
+ if (equal(v->node, non_const_expr))
+ {
+ v->consts = lappend(v->consts, const_expr);
+ non_const_expr = NULL;
+ break;
+ }
+ }
+
+ if (non_const_expr == NULL)
+ /*
+ * The clause classified successfully and added into existed
+ * clause group.
+ */
+ continue;
+
+ /* New clause group needed */
+ gentry = palloc(sizeof(OrClauseGroupEntry));
+ gentry->node = non_const_expr;
+ gentry->consts = list_make1(const_expr);
+ gentry->collation = exprInputCollation((Node *)sub_rinfo->clause);
+ gentry->opno = opno;
+ gentry->rinfo = sub_rinfo;
+ groups_list = lappend(groups_list, (void *) gentry);
+ }
+
+ if (groups_list == NIL)
+ {
+ /*
+ * No any transformations possible with this rinfo, just add itself
+ * to the list and go further.
+ */
+ modified_rinfo = lappend(modified_rinfo, rinfo);
+ continue;
+ }
+
+ /* 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);
+ ScalarArrayOpExpr *saopexpr;
+ ArrayExpr *newa;
+
+ 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, (void *) gentry->rinfo->clause);
+ continue;
+ }
+
+ /*
+ * Do the transformation. It's been a long way ;)
+ *
+ * As a source of insides, use make_scalar_array_op()
+ */
+
+ newa = makeNode(ArrayExpr);
+ newa->element_typeid = exprType(gentry->node);
+ newa->array_typeid = newa->element_typeid; /* don't used in the case of one dimension, but exprType returns this value */
+ newa->multidims = false;
+ newa->elements = gentry->consts;
+ newa->location = -1; /* Position of the new clause is undefined */
+
+ saopexpr = makeNode(ScalarArrayOpExpr);
+ saopexpr->opno = gentry->opno;
+ saopexpr->opfuncid = get_opcode(gentry->opno);
+ saopexpr->useOr = true;
+ saopexpr->inputcollid = gentry->collation;
+ saopexpr->args = list_make2(gentry->node, newa);
+ saopexpr->location = -1;
+
+ /* TODO: study on these parameters. */
+ saopexpr->hashfuncid = InvalidOid;
+ saopexpr->negfuncid = InvalidOid;
+
+ /*
+ * TODO: here we can try to coerce the array to a Const and find
+ * hash func instead of linear search (see 50e17ad281b).
+ * convert_saop_to_hashed_saop((Node *) saopexpr);
+ */
+
+ or_list = lappend(or_list, (void *) saopexpr);
+ change_apply = true;
+ }
+
+ if (!change_apply)
+ {
+ /*
+ * Each group contains only one element - use rinfo as is.
+ */
+ modified_rinfo = lappend(modified_rinfo, rinfo);
+ list_free(or_list);
+ list_free_deep(groups_list);
+ 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->is_pushed_down,
+ rinfo->has_clone,
+ rinfo->is_clone,
+ rinfo->pseudoconstant,
+ rinfo->security_level,
+ rinfo->required_relids,
+ rinfo->incompatible_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);
+ list_free_deep(groups_list);
+ something_changed = true;
+ }
+
+ /*
+ * Check if transformation has made. If nothing changed - return
+ * baserestrictinfo as is.
+ */
+ if (something_changed)
+ {
+ return modified_rinfo;
+ }
+
+ list_free(modified_rinfo);
+ return baserestrictinfo;
+}
/*
* create_index_paths()
@@ -3309,11 +3576,16 @@ check_index_predicates(PlannerInfo *root, RelOptInfo *rel)
* not, this is all we need to do.
*/
have_partial = false;
+
+ if (rel->reloptkind == RELOPT_BASEREL)
+ rel->baserestrictinfo = transform_ors(root, rel->baserestrictinfo);
+
foreach(lc, rel->indexlist)
{
IndexOptInfo *index = (IndexOptInfo *) lfirst(lc);
index->indrestrictinfo = rel->baserestrictinfo;
+
if (index->indpred)
have_partial = true;
}
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-06-29 09:55 ` Alena Rybakina <[email protected]>
2023-06-29 11:23 ` Re: POC, WIP: OR-clause support for indexes Ranier Vilela <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
1 sibling, 2 replies; 25+ messages in thread
From: Alena Rybakina @ 2023-06-29 09:55 UTC (permalink / raw)
To: pgsql-hackers; Tomas Vondra <[email protected]>; Ranier Vilela <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Andrey Lepikhov <[email protected]>; [email protected]
I apologize for breaks the original thread. In my defense, I can say
that I'm new to all this and I'm just learning. I will try to make as
few mistakes as possible.
I try to fix it by forwarding this message to you, besides it might be
interesting to you too. This message to you, because it might be
interesting to you too.
I'm sorry if I didn't state my goals clearly at first, but it seemed to
me that initially the problem I encountered was very similar to what is
described in this thread, only I suggested a slightly different way to
solve it.
I have described the problem more or less clearly here [1] and the worst
case, as it seems to me, too, but if this is not the case, let me know.
1.
https://www.mail-archive.com/[email protected]/msg146230.html
> On 29.06.2023 12:32, Alena Rybakina wrote:
>>
>> Hi! I'm sorry I didn't answer you right away, I was too busy with work.
>>
>> On 27.06.2023 22:50, Peter Geoghegan wrote:
>>> On Tue, Jun 27, 2023 at 6:19 AM Alena Rybakina<[email protected]> wrote:
>>>> I learned something new from your letter, thank you very much for that!
>>> Cool. The MDAM paper is also worth a read:
>>>
>>> https://vldb.org/conf/1995/P710.PDF
>>>
>>> Some of the techniques it describes are already in Postgres. With
>>> varying degrees of maturity.
>>>
>>> The paper actually mentions OR optimization at one point, under
>>> "Duplicate Elimination". The general idea is that ScalarArrayOpExpr
>>> execution can "eliminate duplicates before the data is read". The
>>> important underlying principle is that it can be really useful to give
>>> the B-Tree code the context it requires to be clever about stuff like
>>> that. We can do this by (say) using one ScalarArrayOpExpr, rather than
>>> using two or more index scans that the B-Tree code will treat as
>>> independent things. So a lot of the value in your patch comes from the
>>> way that it can enable other optimizations (the immediate benefits are
>>> also nice).
>>>
>>> In the past, OR optimizations have been prototyped that were later
>>> withdrawn/rejected because the duplicate elimination aspect was...too
>>> scary [1]. It's very easy to see that ScalarArrayOpExpr index scans
>>> don't really have the same problem. "Giving the B-Tree code the
>>> required context" helps here too.
>>>
>> Thank you for the explanation and the material provided)
>> unfortunately, I am still only studying the article and at the moment
>> I cannot write more. To be honest, I didn't think about the fact that
>> my optimization can help eliminate duplicates before reading the data
>> before.
>>
>> I am still only in the process of familiarizing myself with the
>> thread [1] (reference from your letter), but I have already seen that
>> there are problems related, for example, to when "or" expressions
>> refer to the parent element.
>>
>> I think, I would face the similar problems if I complicate the
>> current code, for example, so that not only or expressions standing
>> on the same level are written in any, but also on different ones
>> without violating the logic of the priority of executing operators.
>>
>> For example, this query works now:
>>
>> postgres=# EXPLAIN (analyze, COSTS OFF)
>> SELECT oid,relname FROM pg_class
>> WHERE
>> (oid = 13779 OR oid = 2) OR (oid = 4 OR oid = 5) OR
>> relname = 'pg_extension'
>> ;
>>
>> QUERY PLAN
>> ------------------------------------------------------------------------------------------------------------------
>> Seq Scan on pg_class (actual time=0.086..0.140 rows=1 loops=1)
>> Filter: ((oid = ANY ('{4,5}'::oid[])) OR (oid = ANY
>> ('{13779,2}'::oid[])) OR (relname = 'pg_extension'::name))
>> Rows Removed by Filter: 412
>> Planning Time: 2.135 ms
>> Execution Time: 0.160 ms
>> (5 rows)
>>
>> But I would like it works such as:
>>
>> QUERY PLAN
>> --------------------------------------------------------------------------------------
>> Seq Scan on pg_class (actual time=0.279..0.496 rows=1 loops=1)
>> Filter: ((oid = ANY ('{13779,2,4,5}'::oid[])) OR (relname =
>> 'pg_extension'::name))
>> Rows Removed by Filter: 412
>> Planning Time: 0.266 ms
>> Execution Time: 0.536 ms
>> (5 rows)
>>
>>>> I analyzed the buffer consumption when I ran control regression tests using my patch. diff shows me that there is no difference between the number of buffer block scans without and using my patch, as far as I have seen. (regression.diffs)
>>> To be clear, I wasn't expecting that there'd be any regressions from
>>> your patch. Intuitively, it seems like this optimization should make
>>> the query plan do almost the same thing at execution time -- just
>>> slightly more efficiently on average, and much more efficiently in
>>> some individual cases.
>>>
>>> It would probably be very hard for the optimizer to model/predict how
>>> much work it can save by using a ScalarArrayOpExpr instead of an
>>> "equivalent" set of bitmap index scans, OR'd together. But it doesn't
>>> necessarily matter -- the only truly critical detail is understanding
>>> the worst case for the transformation optimization.
>> Yes, I agree with you and I have yet to analyze this.
>>> It cannot be too
>>> bad (maybe it's ~zero added runtime overhead relative to not doing the
>>> transformation, even?).
>> I haven't seen a major performance degradation so far, but to be
>> honest, I have not conducted a detailed analysis on other types of
>> queries other than x=1 or x=2 or x=1 or y=2, etc. As soon as
>> something is known, I will provide the data, it is very interesting
>> to me.
>>> At the same time, nbtree can be clever about
>>> ScalarArrayOpExpr execution at runtime (once that's implemented),
>>> without ever needing to make any kind of up-front commitment to
>>> navigating through the index in any particular way. It's all dynamic,
>>> and can be driven by the actual observed characteristics of the index
>>> structure.
>>>
>>> In other words, we don't really need to gamble (in the planner, or at
>>> execution time). We're just keeping our options open in more cases.
>>> (My thinking on these topics was influenced by Goetz Graefe -- "choice
>>> is confusion" [2]).
>>
>> Unfortunately, when I tried to make a transformation at the stage of
>> index formation, I encountered too incorrect an assessment of the
>> selectivity of relation, which affected the incorrect calculation of
>> the cost and cardinality. I couldn't solve this problem.
>>
>> My diff (transform_or_v0.diff). I got this result:
>>
>> CREATE TABLE tenk1 (unique1int, unique2int, tenint, hundredint);
>> insert into tenk1 SELECT x,x,x,x FROM generate_series(1,50000) as x;
>> CREATE INDEX a_idx1 ON tenk1(unique1);
>> CREATE INDEX a_idx2 ON tenk1(unique2);
>> CREATE INDEX a_hundred ON tenk1(hundred);
>>
>> postgres=# explain analyze
>> select * from tenk1 a join tenk1 b on
>> a.unique2 = 3 or a.unique2 = 7 or a.unique1 = 1;
>> QUERY PLAN
>> ----------------------------------------------------------------------------------------------------------------------
>> Nested Loop (cost=0.00..15627479.50 rows=1250050000 width=32) (actual time=0.040..75.531 rows=150000 loops=1)
>> -> Seq Scan on tenk1 b (cost=0.00..771.00 rows=50000 width=16) (actual time=0.022..5.467 rows=50000 loops=1)
>> -> Materialize (cost=0.00..1146.01 rows=25001 width=16) (actual time=0.000..0.001 rows=3 loops=50000)
>> -> Seq Scan on tenk1 a (cost=0.00..1021.00 rows=25001 width=16) (actual time=0.011..22.789 rows=3 loops=1)
>> Filter: ((unique2 = ANY (ARRAY[3, 7])) OR (unique1 = 1))
>> Rows Removed by Filter: 49997
>> Planning Time: 0.427 ms
>> Execution Time: 80.027 ms
>> (8 rows)
>>
>> The current patch's result:
>>
>> postgres=# set enable_bitmapscan ='off';
>> SET
>> postgres=# explain analyze
>> select * from tenk1 a join tenk1 b on
>> a.unique2 = 3 or a.unique2 = 7 or a.unique1 = 1;
>> QUERY PLAN
>> ----------------------------------------------------------------------------------------------------------------------
>> Nested Loop (cost=0.00..22247.02 rows=1350000 width=32) (actual time=0.094..373.627 rows=1350000 loops=1)
>> -> Seq Scan on tenk1 b (cost=0.00..2311.00 rows=150000 width=16) (actual time=0.051..14.667 rows=150000 loops=1)
>> -> Materialize (cost=0.00..3061.05 rows=9 width=16) (actual time=0.000..0.001 rows=9 loops=150000)
>> -> Seq Scan on tenk1 a (cost=0.00..3061.00 rows=9 width=16) (actual time=0.026..42.389 rows=9 loops=1)
>> Filter: ((unique2 = ANY ('{3,7}'::integer[])) OR (unique1 = 1))
>> Rows Removed by Filter: 149991
>> Planning Time: 0.414 ms
>> Execution Time: 409.154 ms
>> (8 rows)
>>
>>> [1]https://www.postgresql.org/message-id/flat/1397.1486598083%40sss.pgh.pa.us#310f974a8dc84478d6d3c70f3...
>>> [2]https://sigmodrecord.org/publications/sigmodRecord/2009/pdfs/05_Profiles_Graefe.pdf
>> Thank you again for the explanations and the material provided. I
>> will carefully study everything as soon as possible and will write if
>> there are any thoughts or if there are ideas about my patch.
--
Regards,
Alena Rybakina
Postgres Professional
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-06-29 11:23 ` Ranier Vilela <[email protected]>
2023-06-29 15:16 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
1 sibling, 1 reply; 25+ messages in thread
From: Ranier Vilela @ 2023-06-29 11:23 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: pgsql-hackers; Tomas Vondra <[email protected]>; Marcos Pegoraro <[email protected]>; Andrey Lepikhov <[email protected]>; [email protected]
Em qui., 29 de jun. de 2023 às 06:56, Alena Rybakina <
[email protected]> escreveu:
> I apologize for breaks the original thread. In my defense, I can say that
> I'm new to all this and I'm just learning. I will try to make as few
> mistakes as possible.
>
By no means, your work is excellent and deserves all compliments.
regards,
Ranier Vilela
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 11:23 ` Re: POC, WIP: OR-clause support for indexes Ranier Vilela <[email protected]>
@ 2023-06-29 15:16 ` Alena Rybakina <[email protected]>
0 siblings, 0 replies; 25+ messages in thread
From: Alena Rybakina @ 2023-06-29 15:16 UTC (permalink / raw)
To: Ranier Vilela <[email protected]>; +Cc: pgsql-hackers
On 29.06.2023 14:23, Ranier Vilela wrote:
> Em qui., 29 de jun. de 2023 às 06:56, Alena Rybakina
> <[email protected]> escreveu:
>
> I apologize for breaks the original thread. In my defense, I can
> say that I'm new to all this and I'm just learning. I will try to
> make as few mistakes as possible.
>
> By no means, your work is excellent and deserves all compliments.
Thank you, I will try to work in the same spirit, especially since there
is still quite a lot of work left).
Thank you for your feedback.
--
Regards,
Alena Rybakina
Postgres Professional
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-07-05 19:39 ` Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
1 sibling, 1 reply; 25+ messages in thread
From: Alena Rybakina @ 2023-07-05 19:39 UTC (permalink / raw)
To: pgsql-hackers; Tomas Vondra <[email protected]>; Ranier Vilela <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Andrey Lepikhov <[email protected]>; [email protected]; Peter Geoghegan <[email protected]>
HI, all!
> On 27.06.2023 16:19, Alena Rybakina wrote:
>> Thank you for your feedback, your work is also very interesting and
>> important, and I will be happy to review it. I learned something new
>> from your letter, thank you very much for that!
>>
>> I analyzed the buffer consumption when I ran control regression tests
>> using my patch. diff shows me that there is no difference between the
>> number of buffer block scans without and using my patch, as far as I
>> have seen. (regression.diffs)
>>
>>
>> In addition, I analyzed the scheduling and duration of the execution
>> time of the source code and with my applied patch. I generated 20
>> billion data from pgbench and plotted the scheduling and execution
>> time depending on the number of "or" expressions.
>> By runtime, I noticed a clear acceleration for queries when using the
>> index, but I can't say the same when the index is disabled.
>> At first I turned it off in this way:
>> 1)enable_seqscan='off'
>> 2)enable_indexonlyscan='off'
>> enable_indexscan='off'
>>
>> Unfortunately, it is not yet clear which constant needs to be set
>> when the transformation needs to be done, I will still study in
>> detail. (the graph for all this is presented in graph1.svg
I finished comparing the performance of queries with converted or
expressions and the original ones and found that about 500 "OR"
expressions have significantly noticeable degradation of execution time,
both using the index and without it (you can look at
time_comsuption_with_indexes.png and time_comsuption_without_indexes.html )
The test was performed on the same benchmark database generated by 2
billion values.
I corrected this constant in the patch.
--
Regards,
Alena Rybakina
Postgres Professional
Attachments:
[image/png] time_comsuption_with_indexes.png (78.9K, ../../[email protected]/2-time_comsuption_with_indexes.png)
download | view image
[image/png] time_comsuption_without_indexes.png (78.9K, ../../[email protected]/3-time_comsuption_without_indexes.png)
download | view image
[text/x-patch] 0001-Replace-OR-clause-to-ANY-expressions.patch (10.0K, ../../[email protected]/4-0001-Replace-OR-clause-to-ANY-expressions.patch)
download | inline diff:
From f9f5958707bc1d7931323df05d51a60fc9d6cd38 Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Thu, 29 Jun 2023 17:46:58 +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 15 or
expressions. Thirdly, it is worth considering that we consider "or"
expressions only at the current level.
---
src/backend/parser/parse_expr.c | 290 ++++++++++++++++++++++++++++++-
src/tools/pgindent/typedefs.list | 1 +
2 files changed, 290 insertions(+), 1 deletion(-)
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 346fd272b6d..3d395fd6459 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -95,6 +95,294 @@ 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 int const_transform_or_limit = 500;
+
+static Node *
+transformBoolExprOr(ParseState *pstate, Expr *expr_orig)
+{
+ List *or_list = NIL;
+ List *groups_list = NIL;
+ ListCell *lc_eargs;
+ Node *result;
+ BoolExpr *expr = (BoolExpr *)copyObject(expr_orig);
+ const char *opname;
+ bool change_apply = false;
+ bool or_statement = false;
+
+ Assert(IsA(expr, BoolExpr));
+
+ /* If this is not expression "Or", then will do it the old way. */
+ switch (expr->boolop)
+ {
+ case AND_EXPR:
+ opname = "AND";
+ break;
+ case OR_EXPR:
+ opname = "OR";
+ or_statement = true;
+ break;
+ case NOT_EXPR:
+ opname = "NOT";
+ break;
+ default:
+ elog(ERROR, "unrecognized boolop: %d", (int) expr->boolop);
+ opname = NULL; /* keep compiler quiet */
+ break;
+ }
+
+ if (!or_statement || list_length(expr->args) < const_transform_or_limit)
+ return transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+
+ /*
+ * NOTE:
+ * It is an OR-clause. So, rinfo->orclause is a BoolExpr node, contains
+ * a list of sub-restrictinfo args, and rinfo->clause - which is the
+ * same expression, made from bare clauses. To not break selectivity
+ * caches and other optimizations, use both:
+ * - use rinfos from orclause if no transformation needed
+ * - use bare quals from rinfo->clause in the case of transformation,
+ * to create new RestrictInfo: in this case we have no options to avoid
+ * selectivity estimation procedure.
+ */
+ foreach(lc_eargs, expr->args)
+ {
+ A_Expr *arg = (A_Expr *) lfirst(lc_eargs);
+ Node *bare_orarg;
+ Node *const_expr;
+ Node *non_const_expr;
+ ListCell *lc_groups;
+ OrClauseGroupEntry *gentry;
+ bool allow_transformation;
+
+ /*
+ * The first step: checking that the expression consists only of equality.
+ * We can only do this here, while arg is still row data type, namely A_Expr.
+ * After applying transformExprRecurce, we already know that it will be OpExr type,
+ * but checking the expression for equality is already becoming impossible for us.
+ * Sometimes we have the chance to devide expression into the groups on
+ * equality and inequality. This is possible if all list items are not at the
+ * same level of a single BoolExpr expression, otherwise all of them cannot be converted.
+ */
+
+ if (!arg)
+ break;
+
+ allow_transformation = (
+ or_statement &&
+ arg->type == T_A_Expr && (arg)->kind == AEXPR_OP &&
+ list_length((arg)->name) >=1 && strcmp(strVal(linitial((arg)->name)), "=") == 0
+ );
+
+
+ bare_orarg = transformExprRecurse(pstate, (Node *)arg);
+ bare_orarg = coerce_to_boolean(pstate, bare_orarg, opname);
+
+ /*
+ * The next step: transform all the inputs, and detect whether any contain
+ * Vars.
+ */
+ if (!allow_transformation || !bare_orarg || !IsA(bare_orarg, OpExpr) || !contain_vars_of_level(bare_orarg, 0))
+ {
+ /* Again, it's not the expr we can transform */
+ or_list = lappend(or_list, bare_orarg);
+ continue;
+ }
+
+ /*
+ * Get pointers to constant and expression sides of the clause
+ */
+ non_const_expr = get_leftop(bare_orarg);
+ const_expr = get_rightop(bare_orarg);
+
+ /*
+ * 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 (htab key ???).
+ */
+ foreach(lc_groups, groups_list)
+ {
+ OrClauseGroupEntry *v = (OrClauseGroupEntry *) lfirst(lc_groups);
+
+ Assert(v->node != NULL);
+
+ if (equal(v->node, non_const_expr))
+ {
+ v->consts = lappend(v->consts, const_expr);
+ non_const_expr = NULL;
+ break;
+ }
+ }
+
+ if (non_const_expr == NULL)
+ /*
+ * The clause classified successfully and added into existed
+ * clause group.
+ */
+ continue;
+
+ /* New clause group needed */
+ gentry = palloc(sizeof(OrClauseGroupEntry));
+ gentry->node = non_const_expr;
+ gentry->consts = list_make1(const_expr);
+ gentry->opno = ((OpExpr *)bare_orarg)->opno;
+ gentry->expr = (Expr *)bare_orarg;
+ groups_list = lappend(groups_list, (void *) gentry);
+ }
+
+ if (groups_list == NIL)
+ {
+ /*
+ * No any transformations possible with this rinfo, just add itself
+ * to the list and go further.
+ */
+ list_free(or_list);
+
+ return transformBoolExpr(pstate, (BoolExpr *)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. It's been a long way ;)
+ *
+ * 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 (OidIsValid(scalar_type) && scalar_type != RECORDOID)
+ 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 = get_array_type(scalar_type);
+ newa->multidims = false;
+ newa->elements = aexprs;
+ newa->location = -1; /* Position of the new clause is undefined */
+
+ saopexpr = (ScalarArrayOpExpr *)make_scalar_array_op(pstate,
+ list_make1(makeString((char *) "=")),
+ true,
+ gentry->node,
+ (Node *) newa,
+ -1); /* Position of the new clause is undefined */
+
+ /*
+ * TODO: here we can try to coerce the array to a Const and find
+ * hash func instead of linear search (see 50e17ad281b).
+ * convert_saop_to_hashed_saop((Node *) saopexpr);
+ * We don't have to do this anymore, do we?
+ */
+
+ or_list = lappend(or_list, (void *) saopexpr);
+ change_apply = true;
+ }
+ else
+ {
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ continue;
+ }
+ }
+
+ if (!change_apply)
+ {
+ or_statement = false;
+ }
+ list_free_deep(groups_list);
+ }
+
+ if (or_statement)
+ {
+ /* One more trick: assemble correct clause */
+ expr = list_length(or_list) > 1 ? makeBoolExpr(OR_EXPR, list_copy(or_list), -1) : linitial(or_list);
+ result = (Node *)expr;
+ }
+ /*
+ * There was no reasons to create a new expresion, so
+ * run the original BoolExpr conversion with using
+ * transformBoolExpr function
+ */
+ else
+ {
+ result = transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+ }
+ list_free(or_list);
+
+ return result;
+}
/*
* transformExpr -
@@ -208,7 +496,7 @@ transformExprRecurse(ParseState *pstate, Node *expr)
}
case T_BoolExpr:
- result = transformBoolExpr(pstate, (BoolExpr *) expr);
+ result = (Node *)transformBoolExprOr(pstate, (Expr *)expr);
break;
case T_FuncCall:
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 260854747b4..cc1b676d200 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
--
2.34.1
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-07-05 20:06 ` Alena Rybakina <[email protected]>
2023-07-06 10:20 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-07 02:43 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
0 siblings, 2 replies; 25+ messages in thread
From: Alena Rybakina @ 2023-07-05 20:06 UTC (permalink / raw)
To: pgsql-hackers; Tomas Vondra <[email protected]>; Ranier Vilela <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Andrey Lepikhov <[email protected]>; [email protected]; Peter Geoghegan <[email protected]>
Sorry, I threw off the wrong charts, I'm sending the right ones.
On 05.07.2023 22:39, Alena Rybakina wrote:
> HI, all!
>
>> On 27.06.2023 16:19, Alena Rybakina wrote:
>>> Thank you for your feedback, your work is also very interesting and
>>> important, and I will be happy to review it. I learned something new
>>> from your letter, thank you very much for that!
>>>
>>> I analyzed the buffer consumption when I ran control regression
>>> tests using my patch. diff shows me that there is no difference
>>> between the number of buffer block scans without and using my patch,
>>> as far as I have seen. (regression.diffs)
>>>
>>>
>>> In addition, I analyzed the scheduling and duration of the execution
>>> time of the source code and with my applied patch. I generated 20
>>> billion data from pgbench and plotted the scheduling and execution
>>> time depending on the number of "or" expressions.
>>> By runtime, I noticed a clear acceleration for queries when using
>>> the index, but I can't say the same when the index is disabled.
>>> At first I turned it off in this way:
>>> 1)enable_seqscan='off'
>>> 2)enable_indexonlyscan='off'
>>> enable_indexscan='off'
>>>
>>> Unfortunately, it is not yet clear which constant needs to be set
>>> when the transformation needs to be done, I will still study in
>>> detail. (the graph for all this is presented in graph1.svg
>
> I finished comparing the performance of queries with converted or
> expressions and the original ones and found that about 500 "OR"
> expressions have significantly noticeable degradation of execution
> time, both using the index and without it (you can look at
> time_comsuption_with_indexes.png and
> time_comsuption_without_indexes.html )
>
> The test was performed on the same benchmark database generated by 2
> billion values.
>
> I corrected this constant in the patch.
>
--
Regards,
Alena Rybakina
Postgres Professional
Attachments:
[image/png] time_comsuption_with_indexes.png (75.6K, ../../[email protected]/2-time_comsuption_with_indexes.png)
download | view image
[image/png] time_comsuption_without_indexes.png (78.9K, ../../[email protected]/3-time_comsuption_without_indexes.png)
download | view image
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-07-06 10:20 ` Andrey Lepikhov <[email protected]>
2023-07-07 08:20 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
1 sibling, 1 reply; 25+ messages in thread
From: Andrey Lepikhov @ 2023-07-06 10:20 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; [email protected]; Ranier Vilela <[email protected]>; pgsql-hackers; Tomas Vondra <[email protected]>; Peter Geoghegan <[email protected]>
On 6/7/2023 03:06, Alena Rybakina wrote:
>> I corrected this constant in the patch.
The patch don't apply cleanly: it contains some trailing spaces.
Also, quick glance into the code shows some weak points;
1. transformBoolExprOr should have input type BoolExpr.
2. You can avoid the switch operator at the beginning of the function,
because you only need one option.
3. Stale comments: RestrictIinfos definitely not exists at this point.
4. I don't know, you really need to copy the expr or not, but it is
better to do as late, as possible.
5. You assume, that leftop is non-constant and rightop - constant. Why?
6.I doubt about equivalence operator. Someone can invent a custom '='
operator with another semantics, than usual. May be better to check
mergejoinability?
7. I don't know how to confidently identify constant expressions at this
level. So, I guess, You can only merge here expressions like
"F(X)=Const", not an 'F(X)=ConstExpression'.
See delta.diff with mentioned changes in attachment.
--
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index c9193d826f..26648b0876 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -107,41 +107,22 @@ typedef struct OrClauseGroupEntry
static int const_transform_or_limit = 500;
static Node *
-transformBoolExprOr(ParseState *pstate, Expr *expr_orig)
+transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
{
List *or_list = NIL;
List *groups_list = NIL;
ListCell *lc_eargs;
Node *result;
- BoolExpr *expr = (BoolExpr *)copyObject(expr_orig);
- const char *opname;
+ BoolExpr *expr;
bool change_apply = false;
- bool or_statement = false;
-
- Assert(IsA(expr, BoolExpr));
/* If this is not expression "Or", then will do it the old way. */
- switch (expr->boolop)
- {
- case AND_EXPR:
- opname = "AND";
- break;
- case OR_EXPR:
- opname = "OR";
- or_statement = true;
- break;
- case NOT_EXPR:
- opname = "NOT";
- break;
- default:
- elog(ERROR, "unrecognized boolop: %d", (int) expr->boolop);
- opname = NULL; /* keep compiler quiet */
- break;
- }
-
- if (!or_statement || list_length(expr->args) < const_transform_or_limit)
+ if (expr_orig->boolop != OR_EXPR ||
+ list_length(expr_orig->args) < const_transform_or_limit)
return transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+ expr = (BoolExpr *)copyObject(expr_orig);
+
/*
* NOTE:
* It is an OR-clause. So, rinfo->orclause is a BoolExpr node, contains
@@ -176,15 +157,13 @@ transformBoolExprOr(ParseState *pstate, Expr *expr_orig)
if (!arg)
break;
- allow_transformation = (
- or_statement &&
- arg->type == T_A_Expr && (arg)->kind == AEXPR_OP &&
+ allow_transformation = (arg->type == T_A_Expr && (arg)->kind == AEXPR_OP &&
list_length((arg)->name) >=1 && strcmp(strVal(linitial((arg)->name)), "=") == 0
);
bare_orarg = transformExprRecurse(pstate, (Node *)arg);
- bare_orarg = coerce_to_boolean(pstate, bare_orarg, opname);
+ bare_orarg = coerce_to_boolean(pstate, bare_orarg, "OR");
/*
* The next step: transform all the inputs, and detect whether any contain
@@ -357,14 +336,10 @@ transformBoolExprOr(ParseState *pstate, Expr *expr_orig)
}
}
- if (!change_apply)
- {
- or_statement = false;
- }
list_free_deep(groups_list);
}
- if (or_statement)
+ if (change_apply)
{
/* One more trick: assemble correct clause */
expr = list_length(or_list) > 1 ? makeBoolExpr(OR_EXPR, list_copy(or_list), -1) : linitial(or_list);
@@ -376,9 +351,8 @@ transformBoolExprOr(ParseState *pstate, Expr *expr_orig)
* transformBoolExpr function
*/
else
- {
result = transformBoolExpr(pstate, (BoolExpr *)expr_orig);
- }
+
list_free(or_list);
return result;
@@ -496,7 +470,7 @@ transformExprRecurse(ParseState *pstate, Node *expr)
}
case T_BoolExpr:
- result = (Node *)transformBoolExprOr(pstate, (Expr *)expr);
+ result = (Node *)transformBoolExprOr(pstate, (BoolExpr *)expr);
break;
case T_FuncCall:
Attachments:
[text/plain] delta.diff (3.0K, ../../[email protected]/2-delta.diff)
download | inline diff:
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index c9193d826f..26648b0876 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -107,41 +107,22 @@ typedef struct OrClauseGroupEntry
static int const_transform_or_limit = 500;
static Node *
-transformBoolExprOr(ParseState *pstate, Expr *expr_orig)
+transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
{
List *or_list = NIL;
List *groups_list = NIL;
ListCell *lc_eargs;
Node *result;
- BoolExpr *expr = (BoolExpr *)copyObject(expr_orig);
- const char *opname;
+ BoolExpr *expr;
bool change_apply = false;
- bool or_statement = false;
-
- Assert(IsA(expr, BoolExpr));
/* If this is not expression "Or", then will do it the old way. */
- switch (expr->boolop)
- {
- case AND_EXPR:
- opname = "AND";
- break;
- case OR_EXPR:
- opname = "OR";
- or_statement = true;
- break;
- case NOT_EXPR:
- opname = "NOT";
- break;
- default:
- elog(ERROR, "unrecognized boolop: %d", (int) expr->boolop);
- opname = NULL; /* keep compiler quiet */
- break;
- }
-
- if (!or_statement || list_length(expr->args) < const_transform_or_limit)
+ if (expr_orig->boolop != OR_EXPR ||
+ list_length(expr_orig->args) < const_transform_or_limit)
return transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+ expr = (BoolExpr *)copyObject(expr_orig);
+
/*
* NOTE:
* It is an OR-clause. So, rinfo->orclause is a BoolExpr node, contains
@@ -176,15 +157,13 @@ transformBoolExprOr(ParseState *pstate, Expr *expr_orig)
if (!arg)
break;
- allow_transformation = (
- or_statement &&
- arg->type == T_A_Expr && (arg)->kind == AEXPR_OP &&
+ allow_transformation = (arg->type == T_A_Expr && (arg)->kind == AEXPR_OP &&
list_length((arg)->name) >=1 && strcmp(strVal(linitial((arg)->name)), "=") == 0
);
bare_orarg = transformExprRecurse(pstate, (Node *)arg);
- bare_orarg = coerce_to_boolean(pstate, bare_orarg, opname);
+ bare_orarg = coerce_to_boolean(pstate, bare_orarg, "OR");
/*
* The next step: transform all the inputs, and detect whether any contain
@@ -357,14 +336,10 @@ transformBoolExprOr(ParseState *pstate, Expr *expr_orig)
}
}
- if (!change_apply)
- {
- or_statement = false;
- }
list_free_deep(groups_list);
}
- if (or_statement)
+ if (change_apply)
{
/* One more trick: assemble correct clause */
expr = list_length(or_list) > 1 ? makeBoolExpr(OR_EXPR, list_copy(or_list), -1) : linitial(or_list);
@@ -376,9 +351,8 @@ transformBoolExprOr(ParseState *pstate, Expr *expr_orig)
* transformBoolExpr function
*/
else
- {
result = transformBoolExpr(pstate, (BoolExpr *)expr_orig);
- }
+
list_free(or_list);
return result;
@@ -496,7 +470,7 @@ transformExprRecurse(ParseState *pstate, Node *expr)
}
case T_BoolExpr:
- result = (Node *)transformBoolExprOr(pstate, (Expr *)expr);
+ result = (Node *)transformBoolExprOr(pstate, (BoolExpr *)expr);
break;
case T_FuncCall:
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-06 10:20 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
@ 2023-07-07 08:20 ` Alena Rybakina <[email protected]>
2023-07-10 03:12 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
0 siblings, 1 reply; 25+ messages in thread
From: Alena Rybakina @ 2023-07-07 08:20 UTC (permalink / raw)
To: Andrey Lepikhov <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; [email protected]; Ranier Vilela <[email protected]>; pgsql-hackers; Tomas Vondra <[email protected]>; Peter Geoghegan <[email protected]>
Hi! Thank you for your detailed review, your changes have greatly helped
to improve this patch.
On 06.07.2023 13:20, Andrey Lepikhov wrote:
> On 6/7/2023 03:06, Alena Rybakina wrote:
>>> I corrected this constant in the patch.
> The patch don't apply cleanly: it contains some trailing spaces.
I fixed it.
>
> Also, quick glance into the code shows some weak points;
> 1. transformBoolExprOr should have input type BoolExpr.
Agreed.
> 2. You can avoid the switch operator at the beginning of the function,
> because you only need one option.
Agreed.
> 3. Stale comments: RestrictIinfos definitely not exists at this point.
Yes, unfortunately, I missed this from the previous version when I tried
to perform such a transformation at the index creation stage.
> 4. I don't know, you really need to copy the expr or not, but it is
> better to do as late, as possible.
Yes, I agree with you, copying "expr" is not necessary in this patch
> 5. You assume, that leftop is non-constant and rightop - constant. Why?
Agreed, It was too presumptuous on my part and I agree with your changes.
> 6.I doubt about equivalence operator. Someone can invent a custom '='
> operator with another semantics, than usual. May be better to check
> mergejoinability?
Yes, I agree with you, and I haven't thought about it before. But I
haven't found any functions to arrange this in PostgreSQL, but using
mergejoinability turns out to be more beautiful here.
> 7. I don't know how to confidently identify constant expressions at
> this level. So, I guess, You can only merge here expressions like
> "F(X)=Const", not an 'F(X)=ConstExpression'.
I see, you can find solution for this case, thank you for this, and I
think it's reliable enough.
On 07.07.2023 05:43, Andrey Lepikhov wrote:
> On 6/7/2023 03:06, Alena Rybakina wrote:
>>> The test was performed on the same benchmark database generated by 2
>>> billion values.
>>>
>>> I corrected this constant in the patch.
> In attempt to resolve some issues had mentioned in my previous letter
> I used op_mergejoinable to detect mergejoinability of a clause.
> Constant side of the expression is detected by call of
> eval_const_expressions() and check each side on the Const type of node.
>
> See 'diff to diff' in attachment.
I notices you remove condition for checking equal operation.
strcmp(strVal(linitial((arg)->name)), "=") == 0
Firstly, it is noticed me not correct, but a simple example convinced me
otherwise:
postgres=# explain analyze select x from a where x=1 or x>5 or x<3 or x=2;
QUERY PLAN
--------------------------------------------------------------------------------------------------------
Seq Scan on a (cost=0.00..2291.00 rows=97899 width=4) (actual
time=0.038..104.168 rows=99000 loops=1)
Filter: ((x > '5'::numeric) OR (x < '3'::numeric) OR (x = ANY
('{1,2}'::numeric[])))
Rows Removed by Filter: 1000
Planning Time: 9.938 ms
Execution Time: 113.457 ms
(5 rows)
It surprises me that such check I can write such similar way:
eval_const_expressions(NULL, orqual).
Yes, I see we can remove this code:
bare_orarg = transformExprRecurse(pstate, (Node *)arg);
bare_orarg = coerce_to_boolean(pstate, bare_orarg, "OR");
because we will provide similar manipulation in this:
foreach(l, gentry->consts)
{
Node *rexpr = (Node *) lfirst(l);
rexpr = coerce_to_common_type(pstate, rexpr,
scalar_type,
"IN");
aexprs = lappend(aexprs, rexpr);
}
--
Regards,
Alena Rybakina
Postgres Professional
Attachments:
[text/x-patch] 0001-Replace-OR-clause-to-ANY-expressions.patch (9.2K, ../../[email protected]/2-0001-Replace-OR-clause-to-ANY-expressions.patch)
download | inline diff:
From 9134099ef9808ca27494bc131558d04b24d9bdeb Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Thu, 29 Jun 2023 17:46:58 +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 500 or
expressions. Thirdly, it is worth considering that we consider "or"
expressions only at the current level.
---
src/backend/parser/parse_expr.c | 269 ++++++++++++++++++++++++++++++-
src/tools/pgindent/typedefs.list | 1 +
2 files changed, 269 insertions(+), 1 deletion(-)
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 346fd272b6d..961ca3e482c 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -95,6 +95,273 @@ 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 int const_transform_or_limit = 500;
+
+static Node *
+transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
+{
+ List *or_list = NIL;
+ List *groups_list = NIL;
+ ListCell *lc;
+ Node *result;
+ BoolExpr *expr;
+ bool change_apply = false;
+
+ /* If this is not an 'OR' expression, skip the transformation */
+ if (expr_orig->boolop != OR_EXPR ||
+ list_length(expr_orig->args) < const_transform_or_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;
+ bool const_is_left = true;
+
+ /*
+ * The first step: checking that the expression consists only of equality.
+ * We can only do this here, while arg is still row data type, namely A_Expr.
+ * After applying transformExprRecurce, we already know that it will be OpExr type,
+ * but checking the expression for equality is already becoming impossible for us.
+ * Sometimes we have the chance to devide expression into the groups on
+ * equality and inequality. This is possible if all list items are not at the
+ * same level of a single BoolExpr expression, otherwise all of them cannot be converted.
+ */
+
+ 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 constant side of the clause */
+ if (IsA(get_leftop(orqual), Const))
+ const_is_left = true;
+ else if (IsA(get_rightop(orqual), Const))
+ const_is_left = false;
+ else
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ /* Get pointers to constant and expression sides of the qual */
+ nconst_expr = (const_is_left) ? get_rightop(orqual) :
+ get_leftop(orqual);
+ const_expr = (const_is_left) ? get_leftop(orqual) :
+ get_rightop(orqual);
+
+ if (!op_mergejoinable(((OpExpr *) orqual)->opno, exprType(nconst_expr)))
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ /*
+ * The next step: transform all the inputs, and detect whether
+ * any contain Vars.
+ */
+ if (!contain_vars_of_level(orqual, 0))
+ {
+ /* Again, it's not the expr we can transform */
+ 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 (htab key ???).
+ */
+ 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->opno = ((OpExpr *)orqual)->opno;
+ gentry->expr = (Expr *)orqual;
+ groups_list = lappend(groups_list, (void *) gentry);
+ }
+
+ if (groups_list == NIL)
+ {
+ /*
+ * No any transformations possible with this rinfo, just add itself
+ * to the list and go further.
+ */
+ list_free(or_list);
+
+ return transformBoolExpr(pstate, (BoolExpr *)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. It's been a long way ;)
+ *
+ * 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 (OidIsValid(scalar_type) && scalar_type != RECORDOID)
+ 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 = get_array_type(scalar_type);
+ newa->multidims = false;
+ newa->elements = aexprs;
+ newa->location = -1; /* Position of the new clause is undefined */
+
+ saopexpr = (ScalarArrayOpExpr *)make_scalar_array_op(pstate,
+ list_make1(makeString((char *) "=")),
+ true,
+ gentry->node,
+ (Node *) newa,
+ -1); /* Position of the new clause is undefined */
+
+ /*
+ * TODO: here we can try to coerce the array to a Const and find
+ * hash func instead of linear search (see 50e17ad281b).
+ * convert_saop_to_hashed_saop((Node *) saopexpr);
+ * We don't have to do this anymore, do we?
+ */
+
+ or_list = lappend(or_list, (void *) saopexpr);
+ change_apply = true;
+ }
+ else
+ {
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ continue;
+ }
+ }
+
+ list_free_deep(groups_list);
+ }
+
+ if (change_apply)
+ {
+ /* One more trick: assemble correct clause */
+ expr = list_length(or_list) > 1 ? makeBoolExpr(OR_EXPR, list_copy(or_list), -1) : linitial(or_list);
+ result = (Node *)expr;
+ }
+ /*
+ * There was no reasons to create a new expresion, so
+ * run the original BoolExpr conversion with using
+ * transformBoolExpr function
+ */
+ else
+ result = transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+
+ list_free(or_list);
+
+ return result;
+}
/*
* transformExpr -
@@ -208,7 +475,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/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
--
2.34.1
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-06 10:20 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-07 08:20 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-07-10 03:12 ` Andrey Lepikhov <[email protected]>
2023-07-10 08:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
0 siblings, 1 reply; 25+ messages in thread
From: Andrey Lepikhov @ 2023-07-10 03:12 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; [email protected]; Ranier Vilela <[email protected]>; pgsql-hackers; Tomas Vondra <[email protected]>; Peter Geoghegan <[email protected]>
On 7/7/2023 15:20, Alena Rybakina wrote:
>
> because we will provide similar manipulation in this:
>
> foreach(l, gentry->consts)
> {
> Node *rexpr = (Node *) lfirst(l);
>
> rexpr = coerce_to_common_type(pstate, rexpr,
> scalar_type,
> "IN");
> aexprs = lappend(aexprs, rexpr);
> }
I'm not sure that it should be replaced.
In attachment - a bit more corrections to the patch.
The most important change - or_list contains already transformed
expression subtree. So, I think we don't need to free it at all.
--
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 961ca3e482..f0fd63f05c 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -112,9 +112,6 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
List *or_list = NIL;
List *groups_list = NIL;
ListCell *lc;
- Node *result;
- BoolExpr *expr;
- bool change_apply = false;
/* If this is not an 'OR' expression, skip the transformation */
if (expr_orig->boolop != OR_EXPR ||
@@ -131,16 +128,7 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
OrClauseGroupEntry *gentry;
bool const_is_left = true;
- /*
- * The first step: checking that the expression consists only of equality.
- * We can only do this here, while arg is still row data type, namely A_Expr.
- * After applying transformExprRecurce, we already know that it will be OpExr type,
- * but checking the expression for equality is already becoming impossible for us.
- * Sometimes we have the chance to devide expression into the groups on
- * equality and inequality. This is possible if all list items are not at the
- * same level of a single BoolExpr expression, otherwise all of them cannot be converted.
- */
-
+ /* 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);
@@ -151,7 +139,13 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
continue;
}
- /* Detect constant side of the clause */
+ /*
+ * 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.
+ */
if (IsA(get_leftop(orqual), Const))
const_is_left = true;
else if (IsA(get_rightop(orqual), Const))
@@ -175,26 +169,14 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
}
/*
- * The next step: transform all the inputs, and detect whether
- * any contain Vars.
- */
- if (!contain_vars_of_level(orqual, 0))
- {
- /* Again, it's not the expr we can transform */
- 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 (htab key ???).
- */
+ * 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);
@@ -220,20 +202,18 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
gentry = palloc(sizeof(OrClauseGroupEntry));
gentry->node = nconst_expr;
gentry->consts = list_make1(const_expr);
- gentry->opno = ((OpExpr *)orqual)->opno;
- gentry->expr = (Expr *)orqual;
+ gentry->expr = (Expr *) orqual;
groups_list = lappend(groups_list, (void *) gentry);
}
if (groups_list == NIL)
{
/*
- * No any transformations possible with this rinfo, just add itself
- * to the list and go further.
+ * No any transformations possible with this list of arguments. Here we
+ * already made all underlying transformations. Thus, just return the
+ * transformed bool expression.
*/
- list_free(or_list);
-
- return transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+ return (Node *) makeBoolExpr(OR_EXPR, or_list, expr_orig->location);
}
else
{
@@ -267,11 +247,12 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
}
/*
- * Do the transformation. It's been a long way ;)
+ * 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).
+ * 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.
*
@@ -288,8 +269,8 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
if (array_type != InvalidOid)
{
/*
- * OK: coerce all the right-hand non-Var inputs to the common type
- * and build an ArrayExpr for them.
+ * OK: coerce all the right-hand non-Var inputs to the common
+ * type and build an ArrayExpr for them.
*/
List *aexprs;
ArrayExpr *newa;
@@ -314,24 +295,18 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
newa->array_typeid = get_array_type(scalar_type);
newa->multidims = false;
newa->elements = aexprs;
- newa->location = -1; /* Position of the new clause is undefined */
+ newa->location = -1;
- saopexpr = (ScalarArrayOpExpr *)make_scalar_array_op(pstate,
- list_make1(makeString((char *) "=")),
- true,
- gentry->node,
- (Node *) newa,
- -1); /* Position of the new clause is undefined */
-
- /*
- * TODO: here we can try to coerce the array to a Const and find
- * hash func instead of linear search (see 50e17ad281b).
- * convert_saop_to_hashed_saop((Node *) saopexpr);
- * We don't have to do this anymore, do we?
- */
+ saopexpr =
+ (ScalarArrayOpExpr *)
+ make_scalar_array_op(pstate,
+ list_make1(makeString((char *) "=")),
+ true,
+ gentry->node,
+ (Node *) newa,
+ -1);
or_list = lappend(or_list, (void *) saopexpr);
- change_apply = true;
}
else
{
@@ -344,23 +319,10 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
list_free_deep(groups_list);
}
- if (change_apply)
- {
- /* One more trick: assemble correct clause */
- expr = list_length(or_list) > 1 ? makeBoolExpr(OR_EXPR, list_copy(or_list), -1) : linitial(or_list);
- result = (Node *)expr;
- }
- /*
- * There was no reasons to create a new expresion, so
- * run the original BoolExpr conversion with using
- * transformBoolExpr function
- */
- else
- result = transformBoolExpr(pstate, (BoolExpr *)expr_orig);
-
- list_free(or_list);
-
- return result;
+ /* One more trick: assemble correct clause */
+ return (Node *) ((list_length(or_list) > 1) ?
+ makeBoolExpr(OR_EXPR, or_list, expr_orig->location) :
+ linitial(or_list));
}
/*
@@ -475,7 +437,7 @@ transformExprRecurse(ParseState *pstate, Node *expr)
}
case T_BoolExpr:
- result = (Node *)transformBoolExprOr(pstate, (BoolExpr *)expr);
+ result = (Node *)transformBoolExprOr(pstate, (BoolExpr *) expr);
break;
case T_FuncCall:
Attachments:
[text/plain] diff-3.diff (7.3K, ../../[email protected]/2-diff-3.diff)
download | inline diff:
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 961ca3e482..f0fd63f05c 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -112,9 +112,6 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
List *or_list = NIL;
List *groups_list = NIL;
ListCell *lc;
- Node *result;
- BoolExpr *expr;
- bool change_apply = false;
/* If this is not an 'OR' expression, skip the transformation */
if (expr_orig->boolop != OR_EXPR ||
@@ -131,16 +128,7 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
OrClauseGroupEntry *gentry;
bool const_is_left = true;
- /*
- * The first step: checking that the expression consists only of equality.
- * We can only do this here, while arg is still row data type, namely A_Expr.
- * After applying transformExprRecurce, we already know that it will be OpExr type,
- * but checking the expression for equality is already becoming impossible for us.
- * Sometimes we have the chance to devide expression into the groups on
- * equality and inequality. This is possible if all list items are not at the
- * same level of a single BoolExpr expression, otherwise all of them cannot be converted.
- */
-
+ /* 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);
@@ -151,7 +139,13 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
continue;
}
- /* Detect constant side of the clause */
+ /*
+ * 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.
+ */
if (IsA(get_leftop(orqual), Const))
const_is_left = true;
else if (IsA(get_rightop(orqual), Const))
@@ -175,26 +169,14 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
}
/*
- * The next step: transform all the inputs, and detect whether
- * any contain Vars.
- */
- if (!contain_vars_of_level(orqual, 0))
- {
- /* Again, it's not the expr we can transform */
- 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 (htab key ???).
- */
+ * 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);
@@ -220,20 +202,18 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
gentry = palloc(sizeof(OrClauseGroupEntry));
gentry->node = nconst_expr;
gentry->consts = list_make1(const_expr);
- gentry->opno = ((OpExpr *)orqual)->opno;
- gentry->expr = (Expr *)orqual;
+ gentry->expr = (Expr *) orqual;
groups_list = lappend(groups_list, (void *) gentry);
}
if (groups_list == NIL)
{
/*
- * No any transformations possible with this rinfo, just add itself
- * to the list and go further.
+ * No any transformations possible with this list of arguments. Here we
+ * already made all underlying transformations. Thus, just return the
+ * transformed bool expression.
*/
- list_free(or_list);
-
- return transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+ return (Node *) makeBoolExpr(OR_EXPR, or_list, expr_orig->location);
}
else
{
@@ -267,11 +247,12 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
}
/*
- * Do the transformation. It's been a long way ;)
+ * 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).
+ * 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.
*
@@ -288,8 +269,8 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
if (array_type != InvalidOid)
{
/*
- * OK: coerce all the right-hand non-Var inputs to the common type
- * and build an ArrayExpr for them.
+ * OK: coerce all the right-hand non-Var inputs to the common
+ * type and build an ArrayExpr for them.
*/
List *aexprs;
ArrayExpr *newa;
@@ -314,24 +295,18 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
newa->array_typeid = get_array_type(scalar_type);
newa->multidims = false;
newa->elements = aexprs;
- newa->location = -1; /* Position of the new clause is undefined */
+ newa->location = -1;
- saopexpr = (ScalarArrayOpExpr *)make_scalar_array_op(pstate,
- list_make1(makeString((char *) "=")),
- true,
- gentry->node,
- (Node *) newa,
- -1); /* Position of the new clause is undefined */
-
- /*
- * TODO: here we can try to coerce the array to a Const and find
- * hash func instead of linear search (see 50e17ad281b).
- * convert_saop_to_hashed_saop((Node *) saopexpr);
- * We don't have to do this anymore, do we?
- */
+ saopexpr =
+ (ScalarArrayOpExpr *)
+ make_scalar_array_op(pstate,
+ list_make1(makeString((char *) "=")),
+ true,
+ gentry->node,
+ (Node *) newa,
+ -1);
or_list = lappend(or_list, (void *) saopexpr);
- change_apply = true;
}
else
{
@@ -344,23 +319,10 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
list_free_deep(groups_list);
}
- if (change_apply)
- {
- /* One more trick: assemble correct clause */
- expr = list_length(or_list) > 1 ? makeBoolExpr(OR_EXPR, list_copy(or_list), -1) : linitial(or_list);
- result = (Node *)expr;
- }
- /*
- * There was no reasons to create a new expresion, so
- * run the original BoolExpr conversion with using
- * transformBoolExpr function
- */
- else
- result = transformBoolExpr(pstate, (BoolExpr *)expr_orig);
-
- list_free(or_list);
-
- return result;
+ /* One more trick: assemble correct clause */
+ return (Node *) ((list_length(or_list) > 1) ?
+ makeBoolExpr(OR_EXPR, or_list, expr_orig->location) :
+ linitial(or_list));
}
/*
@@ -475,7 +437,7 @@ transformExprRecurse(ParseState *pstate, Node *expr)
}
case T_BoolExpr:
- result = (Node *)transformBoolExprOr(pstate, (BoolExpr *)expr);
+ result = (Node *)transformBoolExprOr(pstate, (BoolExpr *) expr);
break;
case T_FuncCall:
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-06 10:20 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-07 08:20 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-10 03:12 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
@ 2023-07-10 08:38 ` Alena Rybakina <[email protected]>
2023-07-10 12:03 ` Re: POC, WIP: OR-clause support for indexes Ranier Vilela <[email protected]>
2023-07-11 08:47 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
0 siblings, 2 replies; 25+ messages in thread
From: Alena Rybakina @ 2023-07-10 08:38 UTC (permalink / raw)
To: Andrey Lepikhov <[email protected]>; Ranier Vilela <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; [email protected]; pgsql-hackers; Tomas Vondra <[email protected]>; Peter Geoghegan <[email protected]>
I agreed with the changes. Thank you for your work.
I updated patch and added you to the authors.
I specified Ranier Vilela as a reviewer.
On 10.07.2023 06:12, Andrey Lepikhov wrote:
> On 7/7/2023 15:20, Alena Rybakina wrote:
>>
>> because we will provide similar manipulation in this:
>>
>> foreach(l, gentry->consts)
>> {
>> Node *rexpr = (Node *) lfirst(l);
>>
>> rexpr = coerce_to_common_type(pstate, rexpr,
>> scalar_type,
>> "IN");
>> aexprs = lappend(aexprs, rexpr);
>> }
> I'm not sure that it should be replaced.
> In attachment - a bit more corrections to the patch.
> The most important change - or_list contains already transformed
> expression subtree. So, I think we don't need to free it at all.
>
--
Regards,
Alena Rybakina
Postgres Professional
Attachments:
[text/x-patch] 0001-Replace-OR-clause-to-ANY-expressions.patch (8.2K, ../../[email protected]/2-0001-Replace-OR-clause-to-ANY-expressions.patch)
download | inline diff:
From 97239cdeac541d3aaeafde3d15a5b6fdc36f86de Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Thu, 29 Jun 2023 17:46:58 +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 500 or
expressions. 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: Ranier Vilela <[email protected]>
---
src/backend/parser/parse_expr.c | 231 ++++++++++++++++++++++++++++++-
src/tools/pgindent/typedefs.list | 1 +
2 files changed, 231 insertions(+), 1 deletion(-)
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 346fd272b6d..0ddcb880ef8 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -95,6 +95,235 @@ 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 int const_transform_or_limit = 500;
+
+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) < const_transform_or_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;
+ bool const_is_left = true;
+
+ /* 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.
+ */
+ if (IsA(get_leftop(orqual), Const))
+ const_is_left = true;
+ else if (IsA(get_rightop(orqual), Const))
+ const_is_left = false;
+ else
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+
+ /* Get pointers to constant and expression sides of the qual */
+ nconst_expr = (const_is_left) ? get_rightop(orqual) :
+ get_leftop(orqual);
+ const_expr = (const_is_left) ? get_leftop(orqual) :
+ get_rightop(orqual);
+
+ 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 (OidIsValid(scalar_type) && scalar_type != RECORDOID)
+ 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 = get_array_type(scalar_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 +437,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/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
--
2.34.1
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-06 10:20 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-07 08:20 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-10 03:12 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-10 08:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-07-10 12:03 ` Ranier Vilela <[email protected]>
2023-07-10 12:15 ` Re: POC, WIP: OR-clause support for indexes Ranier Vilela <[email protected]>
1 sibling, 1 reply; 25+ messages in thread
From: Ranier Vilela @ 2023-07-10 12:03 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Andrey Lepikhov <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; pgsql-hackers; Tomas Vondra <[email protected]>; Peter Geoghegan <[email protected]>
Hi Alena,
Em seg., 10 de jul. de 2023 às 05:38, Alena Rybakina <
[email protected]> escreveu:
> I agreed with the changes. Thank you for your work.
>
> I updated patch and added you to the authors.
>
> I specified Ranier Vilela as a reviewer.
>
Is a good habit when post a new version of the patch, name it v1, v2,
v3,etc.
Makes it easy to follow development and references on the thread.
Regarding the last patch.
1. I think that variable const_is_left is not necessary.
You can stick with:
+ if (IsA(get_leftop(orqual), Const))
+ nconst_expr =get_rightop(orqual);
+ const_expr = get_leftop(orqual) ;
+ else if (IsA(get_rightop(orqual), Const))
+ nconst_expr =get_leftop(orqual);
+ const_expr = get_rightop(orqual) ;
+ else
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
2. Test scalar_type != RECORDOID is more cheaper,
mainly if OidIsValid were a function, we knows that is a macro.
+ if (scalar_type != RECORDOID && OidIsValid(scalar_type))
3. Sorry about wrong tip about array_type, but if really necessary,
better use it.
+ newa->element_typeid = scalar_type;
+ newa->array_typeid = array_type;
4. Is a good habit, call free last, to avoid somebody accidentally using it.
+ or_list = lappend(or_list, gentry->expr);
+ list_free(gentry->consts);
+ continue;
5. list_make1(makeString((char *) "=")
Is an invariant?
We can store in a variable and keep out the loop?
Keep up the good work.
best regards,
Ranier Vilela
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-06 10:20 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-07 08:20 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-10 03:12 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-10 08:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-10 12:03 ` Re: POC, WIP: OR-clause support for indexes Ranier Vilela <[email protected]>
@ 2023-07-10 12:15 ` Ranier Vilela <[email protected]>
0 siblings, 0 replies; 25+ messages in thread
From: Ranier Vilela @ 2023-07-10 12:15 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Andrey Lepikhov <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; pgsql-hackers; Tomas Vondra <[email protected]>; Peter Geoghegan <[email protected]>
Em seg., 10 de jul. de 2023 às 09:03, Ranier Vilela <[email protected]>
escreveu:
> Hi Alena,
>
> Em seg., 10 de jul. de 2023 às 05:38, Alena Rybakina <
> [email protected]> escreveu:
>
>> I agreed with the changes. Thank you for your work.
>>
>> I updated patch and added you to the authors.
>>
>> I specified Ranier Vilela as a reviewer.
>>
> Is a good habit when post a new version of the patch, name it v1, v2,
> v3,etc.
> Makes it easy to follow development and references on the thread.
>
> Regarding the last patch.
> 1. I think that variable const_is_left is not necessary.
> You can stick with:
> + if (IsA(get_leftop(orqual), Const))
> + nconst_expr =get_rightop(orqual);
> + const_expr = get_leftop(orqual) ;
> + else if (IsA(get_rightop(orqual), Const))
> + nconst_expr =get_leftop(orqual);
> + const_expr = get_rightop(orqual) ;
> + else
> + {
> + or_list = lappend(or_list, orqual);
> + continue;
> + }
>
> 2. Test scalar_type != RECORDOID is more cheaper,
> mainly if OidIsValid were a function, we knows that is a macro.
> + if (scalar_type != RECORDOID && OidIsValid(scalar_type))
>
> 3. Sorry about wrong tip about array_type, but if really necessary,
> better use it.
> + newa->element_typeid = scalar_type;
> + newa->array_typeid = array_type;
>
> 4. Is a good habit, call free last, to avoid somebody accidentally using
> it.
> + or_list = lappend(or_list, gentry->expr);
> + list_free(gentry->consts);
> + continue;
>
> 5. list_make1(makeString((char *) "=")
> Is an invariant?
>
Please nevermind 5. Is not invariant.
regards,
Ranier Vilela
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-06 10:20 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-07 08:20 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-10 03:12 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-10 08:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-07-11 08:47 ` Andrey Lepikhov <[email protected]>
2023-07-11 18:11 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
1 sibling, 1 reply; 25+ messages in thread
From: Andrey Lepikhov @ 2023-07-11 08:47 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; Ranier Vilela <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; [email protected]; pgsql-hackers; Tomas Vondra <[email protected]>; Peter Geoghegan <[email protected]>
On 10/7/2023 15:38, Alena Rybakina wrote:
> I agreed with the changes. Thank you for your work.
>
> I updated patch and added you to the authors.
>
> I specified Ranier Vilela as a reviewer.
This patch looks much better than earlier. But it definitely needs some
covering with tests. As a first simple approximation, here you can see
the result of regression tests, where the transformation limit is set to
0. See in the attachment some test changes induced by these diffs.
Also, I see some impact of the transformation to other queries:
create_view.out:
(NOT x > z) ----> (x <= z)
inherit.out:
(((a)::text = 'ab'::text) OR ((a)::text = ANY ('{NULL,cd}'::text[])))
to
(((a)::text = ANY ('{NULL,cd}'::text[])) OR ((a)::text = 'ab'::text))
Transformations, mentioned above, are correct, of course. But it can be
a sign of possible unstable behavior.
--
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 0ddcb880ef..3d9b385c1f 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);
@@ -104,8 +105,6 @@ typedef struct OrClauseGroupEntry
Expr *expr;
} OrClauseGroupEntry;
-static int const_transform_or_limit = 500;
-
static Node *
transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
{
@@ -115,7 +114,7 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
/* If this is not an 'OR' expression, skip the transformation */
if (expr_orig->boolop != OR_EXPR ||
- list_length(expr_orig->args) < const_transform_or_limit)
+ list_length(expr_orig->args) < or_transform_limit)
return transformBoolExpr(pstate, (BoolExpr *) expr_orig);
foreach(lc, expr_orig->args)
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index c14456060c..c7ac73ebe0 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -2046,6 +2046,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 7d38ca75f7..891e6a462b 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 acfd9d1f4f..60e053d217 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1883,6 +1883,46 @@ 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)
+
+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 127c953297..c052b113ee 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 9b8638f286..fbe711e0ee 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4207,6 +4207,33 @@ 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)
+
+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 2abf759385..5eb94d2821 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 f133b5a4ac..a2949d3d69 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 d49ce9f300..0d33c0b61e 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -737,6 +737,20 @@ 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);
+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 3e5032b04d..3b717400d9 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1396,6 +1396,12 @@ 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);
+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 d1c60b8fe9..77f3e6c3b9 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 313e0fb9b6..634bf08e5f 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[]);
Attachments:
[text/plain] diff-4.diff (19.2K, ../../[email protected]/2-diff-4.diff)
download | inline diff:
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 0ddcb880ef..3d9b385c1f 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);
@@ -104,8 +105,6 @@ typedef struct OrClauseGroupEntry
Expr *expr;
} OrClauseGroupEntry;
-static int const_transform_or_limit = 500;
-
static Node *
transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
{
@@ -115,7 +114,7 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
/* If this is not an 'OR' expression, skip the transformation */
if (expr_orig->boolop != OR_EXPR ||
- list_length(expr_orig->args) < const_transform_or_limit)
+ list_length(expr_orig->args) < or_transform_limit)
return transformBoolExpr(pstate, (BoolExpr *) expr_orig);
foreach(lc, expr_orig->args)
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index c14456060c..c7ac73ebe0 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -2046,6 +2046,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 7d38ca75f7..891e6a462b 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 acfd9d1f4f..60e053d217 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1883,6 +1883,46 @@ 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)
+
+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 127c953297..c052b113ee 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 9b8638f286..fbe711e0ee 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4207,6 +4207,33 @@ 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)
+
+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 2abf759385..5eb94d2821 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 f133b5a4ac..a2949d3d69 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 d49ce9f300..0d33c0b61e 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -737,6 +737,20 @@ 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);
+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 3e5032b04d..3b717400d9 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1396,6 +1396,12 @@ 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);
+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 d1c60b8fe9..77f3e6c3b9 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 313e0fb9b6..634bf08e5f 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[]);
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-06 10:20 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-07 08:20 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-10 03:12 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-10 08:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-11 08:47 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
@ 2023-07-11 18:11 ` Alena Rybakina <[email protected]>
2023-07-18 14:25 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
0 siblings, 1 reply; 25+ messages in thread
From: Alena Rybakina @ 2023-07-11 18:11 UTC (permalink / raw)
To: Andrey Lepikhov <[email protected]>; +Cc: Ranier Vilela <[email protected]>; Marcos Pegoraro <[email protected]>; [email protected]; pgsql-hackers; Tomas Vondra <[email protected]>; Peter Geoghegan <[email protected]>
Hi!
On 11.07.2023 11:47, Andrey Lepikhov wrote:
> This patch looks much better than earlier. But it definitely needs
> some covering with tests. As a first simple approximation, here you
> can see the result of regression tests, where the transformation limit
> is set to 0. See in the attachment some test changes induced by these
> diffs.
>
Yes, I think so too. I also added some tests. I have attached an
additional diff-5.diff where you can see the changes.
> Also, I see some impact of the transformation to other queries:
> create_view.out:
> (NOT x > z) ----> (x <= z)
> inherit.out:
> (((a)::text = 'ab'::text) OR ((a)::text = ANY ('{NULL,cd}'::text[])))
> to -
> (((a)::text = ANY ('{NULL,cd}'::text[])) OR ((a)::text = 'ab'::text))
>
> Transformations, mentioned above, are correct, of course. But it can
> be a sign of possible unstable behavior.
>
I think it can be made more stable if we always add the existing
transformed expressions first, and then the original ones, or vice versa. T
o do this, we will need two more lists, I think, and then we can combine
them, where the elements of the second will be written to the end of the
first.
But I suppose that this may not be the only unstable behavior - I
suppose we need sorting result elements on the left side, what do you think?
--
Regards,
Alena Rybakina
Postgres Professional
Attachments:
[text/x-patch] diff-5.diff (7.4K, ../../[email protected]/2-diff-5.diff)
download | inline diff:
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
index cc229d4dcaf..60e053d2179 100644
--- a/src/test/regress/expected/create_index.out
+++ b/src/test/regress/expected/create_index.out
@@ -1922,81 +1922,6 @@ SELECT count(*) FROM tenk1
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/join.out b/src/test/regress/expected/join.out
index 2314d92a6d4..fbe711e0eec 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -4233,29 +4233,6 @@ select * from tenk1 a join tenk1 b on
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/sql/create_index.sql b/src/test/regress/sql/create_index.sql
index 9c6baace0e2..0d33c0b61ee 100644
--- a/src/test/regress/sql/create_index.sql
+++ b/src/test/regress/sql/create_index.sql
@@ -749,24 +749,6 @@ 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;
--
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index d4d7d853a4a..3b717400d9d 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1401,10 +1401,6 @@ 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;
--
[text/x-patch] v6-Replace-OR-clause-to-ANY-expressions.patch (32.7K, ../../[email protected]/3-v6-Replace-OR-clause-to-ANY-expressions.patch)
download | inline diff:
From be10ec6237542a1f6d3706a109073840656b645d Mon Sep 17 00:00:00 2001
From: Alena Rybakina <[email protected]>
Date: Tue, 11 Jul 2023 20:46:06 +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.
---
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 346fd272b6d..9d4f586448b 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 c14456060c0..c7ac73ebe02 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -2046,6 +2046,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 2abf7593858..5eb94d2821c 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
--
2.34.1
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-06 10:20 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-07 08:20 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-10 03:12 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-10 08:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-11 08:47 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-11 18:11 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-07-18 14:25 ` Alena Rybakina <[email protected]>
0 siblings, 0 replies; 25+ messages in thread
From: Alena Rybakina @ 2023-07-18 14:25 UTC (permalink / raw)
To: Andrey Lepikhov <[email protected]>; Ranier Vilela <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; [email protected]; pgsql-hackers; Tomas Vondra <[email protected]>; Peter Geoghegan <[email protected]>
Hi, all!
I sent a patch to commitfest and noticed that the authors and the
reviewer were incorrectly marked.
Sorry about that. I fixed it and sent the current version of the patch.
--
Regards,
Alena Rybakina
Postgres Professional
Attachments:
[text/x-patch] v6-Replace-OR-clause-to-ANY-expressions.patch (32.8K, ../../[email protected]/2-v6-Replace-OR-clause-to-ANY-expressions.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: 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
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-07-07 02:43 ` Andrey Lepikhov <[email protected]>
1 sibling, 0 replies; 25+ messages in thread
From: Andrey Lepikhov @ 2023-07-07 02:43 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; [email protected]; Peter Geoghegan <[email protected]>; pgsql-hackers; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>
On 6/7/2023 03:06, Alena Rybakina wrote:
>> The test was performed on the same benchmark database generated by 2
>> billion values.
>>
>> I corrected this constant in the patch.
In attempt to resolve some issues had mentioned in my previous letter I
used op_mergejoinable to detect mergejoinability of a clause.
Constant side of the expression is detected by call of
eval_const_expressions() and check each side on the Const type of node.
See 'diff to diff' in attachment.
--
regards,
Andrey Lepikhov
Postgres Professional
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 26648b0876..67d6f85010 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -111,38 +111,27 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
{
List *or_list = NIL;
List *groups_list = NIL;
- ListCell *lc_eargs;
+ ListCell *lc;
Node *result;
BoolExpr *expr;
bool change_apply = false;
- /* If this is not expression "Or", then will do it the old way. */
+ /* If this is not an 'OR' expression, skip the transformation */
if (expr_orig->boolop != OR_EXPR ||
list_length(expr_orig->args) < const_transform_or_limit)
- return transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+ return transformBoolExpr(pstate, (BoolExpr *) expr_orig);
expr = (BoolExpr *)copyObject(expr_orig);
- /*
- * NOTE:
- * It is an OR-clause. So, rinfo->orclause is a BoolExpr node, contains
- * a list of sub-restrictinfo args, and rinfo->clause - which is the
- * same expression, made from bare clauses. To not break selectivity
- * caches and other optimizations, use both:
- * - use rinfos from orclause if no transformation needed
- * - use bare quals from rinfo->clause in the case of transformation,
- * to create new RestrictInfo: in this case we have no options to avoid
- * selectivity estimation procedure.
- */
- foreach(lc_eargs, expr->args)
+ foreach(lc, expr->args)
{
- A_Expr *arg = (A_Expr *) lfirst(lc_eargs);
- Node *bare_orarg;
+ Node *arg = lfirst(lc);
+ Node *orqual;
Node *const_expr;
- Node *non_const_expr;
+ Node *nconst_expr;
ListCell *lc_groups;
OrClauseGroupEntry *gentry;
- bool allow_transformation;
+ bool const_is_left = true;
/*
* The first step: checking that the expression consists only of equality.
@@ -154,33 +143,51 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
* same level of a single BoolExpr expression, otherwise all of them cannot be converted.
*/
- if (!arg)
- break;
+ orqual = transformExprRecurse(pstate, (Node *) arg);
+ orqual = coerce_to_boolean(pstate, orqual, "OR");
+ orqual = eval_const_expressions(NULL, orqual);
- allow_transformation = (arg->type == T_A_Expr && (arg)->kind == AEXPR_OP &&
- list_length((arg)->name) >=1 && strcmp(strVal(linitial((arg)->name)), "=") == 0
- );
+ if (!IsA(orqual, OpExpr))
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+ /* Detect constant side of the clause */
+ if (IsA(get_leftop(orqual), Const))
+ const_is_left = true;
+ else if (IsA(get_rightop(orqual), Const))
+ const_is_left = false;
+ else
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
- bare_orarg = transformExprRecurse(pstate, (Node *)arg);
- bare_orarg = coerce_to_boolean(pstate, bare_orarg, "OR");
+ /* Get pointers to constant and expression sides of the qual */
+ nconst_expr = (const_is_left) ? get_rightop(orqual) :
+ get_leftop(orqual);
+ const_expr = (const_is_left) ? get_leftop(orqual) :
+ get_rightop(orqual);
+
+ if (!op_mergejoinable(((OpExpr *) orqual)->opno, exprType(nconst_expr)))
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
/*
* The next step: transform all the inputs, and detect whether any contain
* Vars.
*/
- if (!allow_transformation || !bare_orarg || !IsA(bare_orarg, OpExpr) || !contain_vars_of_level(bare_orarg, 0))
+ if (!contain_vars_of_level(orqual, 0))
{
/* Again, it's not the expr we can transform */
- or_list = lappend(or_list, bare_orarg);
+ or_list = lappend(or_list, orqual);
continue;
}
- /*
- * Get pointers to constant and expression sides of the clause
- */
- non_const_expr = get_leftop(bare_orarg);
- const_expr = get_rightop(bare_orarg);
+ ;
/*
* At this point we definitely have a transformable clause.
@@ -196,15 +203,15 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
Assert(v->node != NULL);
- if (equal(v->node, non_const_expr))
+ if (equal(v->node, nconst_expr))
{
v->consts = lappend(v->consts, const_expr);
- non_const_expr = NULL;
+ nconst_expr = NULL;
break;
}
}
- if (non_const_expr == NULL)
+ if (nconst_expr == NULL)
/*
* The clause classified successfully and added into existed
* clause group.
@@ -213,10 +220,10 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
/* New clause group needed */
gentry = palloc(sizeof(OrClauseGroupEntry));
- gentry->node = non_const_expr;
+ gentry->node = nconst_expr;
gentry->consts = list_make1(const_expr);
- gentry->opno = ((OpExpr *)bare_orarg)->opno;
- gentry->expr = (Expr *)bare_orarg;
+ gentry->opno = ((OpExpr *)orqual)->opno;
+ gentry->expr = (Expr *)orqual;
groups_list = lappend(groups_list, (void *) gentry);
}
Attachments:
[text/plain] delta-2.diff (4.8K, ../../[email protected]/2-delta-2.diff)
download | inline diff:
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 26648b0876..67d6f85010 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -111,38 +111,27 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
{
List *or_list = NIL;
List *groups_list = NIL;
- ListCell *lc_eargs;
+ ListCell *lc;
Node *result;
BoolExpr *expr;
bool change_apply = false;
- /* If this is not expression "Or", then will do it the old way. */
+ /* If this is not an 'OR' expression, skip the transformation */
if (expr_orig->boolop != OR_EXPR ||
list_length(expr_orig->args) < const_transform_or_limit)
- return transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+ return transformBoolExpr(pstate, (BoolExpr *) expr_orig);
expr = (BoolExpr *)copyObject(expr_orig);
- /*
- * NOTE:
- * It is an OR-clause. So, rinfo->orclause is a BoolExpr node, contains
- * a list of sub-restrictinfo args, and rinfo->clause - which is the
- * same expression, made from bare clauses. To not break selectivity
- * caches and other optimizations, use both:
- * - use rinfos from orclause if no transformation needed
- * - use bare quals from rinfo->clause in the case of transformation,
- * to create new RestrictInfo: in this case we have no options to avoid
- * selectivity estimation procedure.
- */
- foreach(lc_eargs, expr->args)
+ foreach(lc, expr->args)
{
- A_Expr *arg = (A_Expr *) lfirst(lc_eargs);
- Node *bare_orarg;
+ Node *arg = lfirst(lc);
+ Node *orqual;
Node *const_expr;
- Node *non_const_expr;
+ Node *nconst_expr;
ListCell *lc_groups;
OrClauseGroupEntry *gentry;
- bool allow_transformation;
+ bool const_is_left = true;
/*
* The first step: checking that the expression consists only of equality.
@@ -154,33 +143,51 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
* same level of a single BoolExpr expression, otherwise all of them cannot be converted.
*/
- if (!arg)
- break;
+ orqual = transformExprRecurse(pstate, (Node *) arg);
+ orqual = coerce_to_boolean(pstate, orqual, "OR");
+ orqual = eval_const_expressions(NULL, orqual);
- allow_transformation = (arg->type == T_A_Expr && (arg)->kind == AEXPR_OP &&
- list_length((arg)->name) >=1 && strcmp(strVal(linitial((arg)->name)), "=") == 0
- );
+ if (!IsA(orqual, OpExpr))
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
+ /* Detect constant side of the clause */
+ if (IsA(get_leftop(orqual), Const))
+ const_is_left = true;
+ else if (IsA(get_rightop(orqual), Const))
+ const_is_left = false;
+ else
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
- bare_orarg = transformExprRecurse(pstate, (Node *)arg);
- bare_orarg = coerce_to_boolean(pstate, bare_orarg, "OR");
+ /* Get pointers to constant and expression sides of the qual */
+ nconst_expr = (const_is_left) ? get_rightop(orqual) :
+ get_leftop(orqual);
+ const_expr = (const_is_left) ? get_leftop(orqual) :
+ get_rightop(orqual);
+
+ if (!op_mergejoinable(((OpExpr *) orqual)->opno, exprType(nconst_expr)))
+ {
+ or_list = lappend(or_list, orqual);
+ continue;
+ }
/*
* The next step: transform all the inputs, and detect whether any contain
* Vars.
*/
- if (!allow_transformation || !bare_orarg || !IsA(bare_orarg, OpExpr) || !contain_vars_of_level(bare_orarg, 0))
+ if (!contain_vars_of_level(orqual, 0))
{
/* Again, it's not the expr we can transform */
- or_list = lappend(or_list, bare_orarg);
+ or_list = lappend(or_list, orqual);
continue;
}
- /*
- * Get pointers to constant and expression sides of the clause
- */
- non_const_expr = get_leftop(bare_orarg);
- const_expr = get_rightop(bare_orarg);
+ ;
/*
* At this point we definitely have a transformable clause.
@@ -196,15 +203,15 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
Assert(v->node != NULL);
- if (equal(v->node, non_const_expr))
+ if (equal(v->node, nconst_expr))
{
v->consts = lappend(v->consts, const_expr);
- non_const_expr = NULL;
+ nconst_expr = NULL;
break;
}
}
- if (non_const_expr == NULL)
+ if (nconst_expr == NULL)
/*
* The clause classified successfully and added into existed
* clause group.
@@ -213,10 +220,10 @@ transformBoolExprOr(ParseState *pstate, BoolExpr *expr_orig)
/* New clause group needed */
gentry = palloc(sizeof(OrClauseGroupEntry));
- gentry->node = non_const_expr;
+ gentry->node = nconst_expr;
gentry->consts = list_make1(const_expr);
- gentry->opno = ((OpExpr *)bare_orarg)->opno;
- gentry->expr = (Expr *)bare_orarg;
+ gentry->opno = ((OpExpr *)orqual)->opno;
+ gentry->expr = (Expr *)orqual;
groups_list = lappend(groups_list, (void *) gentry);
}
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-07-25 23:47 ` Peter Geoghegan <[email protected]>
2023-07-26 22:30 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
1 sibling, 1 reply; 25+ messages in thread
From: Peter Geoghegan @ 2023-07-25 23:47 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Alena Rybakina <[email protected]>; Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected]
On Thu, Jun 29, 2023 at 2:32 AM Alena Rybakina <[email protected]> wrote:
> Hi! I'm sorry I didn't answer you right away, I was too busy with work.
Same for me, this time. I was busy working on my patch, which I
finally posted yesterday.
> To be honest, I didn't think about the fact that my optimization can help eliminate duplicates before reading the data before.
I'm not surprised that you didn't specifically think of that, because
it's very subtle.
> I am still only in the process of familiarizing myself with the thread [1] (reference from your letter), but I have already seen that there are problems related, for example, to when "or" expressions refer to the parent element.
I didn't intend to imply that you might have the same problem here. I
just meant that OR optimizations can have problems with duplicate
elimination, in general. I suspect that your patch doesn't have that
problem, because you are performing a transformation of one kind of OR
into another kind of OR.
> I think, I would face the similar problems if I complicate the current code, for example, so that not only or expressions standing on the same level are written in any, but also on different ones without violating the logic of the priority of executing operators.
I can't say that I am particularly experienced in this general area --
I have never tried to formally reason about how two different
statements are equivalent. It just hasn't been something that I've
needed to have a totally rigorous understanding of up until now. But
my recent patch changes that. Now I need to study this area to make
sure that I have a truly rigorous understanding.
Jeff Davis suggested that I read "Logic and Databases", by C.J. Date.
So now I have some homework to do.
> Unfortunately, when I tried to make a transformation at the stage of index formation, I encountered too incorrect an assessment of the selectivity of relation, which affected the incorrect calculation of the cost and cardinality.
It's not surprising that a weird shift in the plan chosen by the
optimizer is seen with some random test case, as a result of this
added transformation. Even changes that are 100% strictly better (e.g.
changes in a selectivity estimation function that is somehow
guaranteed to be more accurate in all cases) might do that. Here is a
recent example of that with another patch, involving a bitmap OR:
https://postgr.es/m/CAH2-WznCDK9n2tZ6j_-iLN563_ePuC3NzP6VSVTL6jHzs6nRuQ@mail.gmail.com
This example was *not* a regression, if you go by conventional
measures. It was merely a less robust plan than the bitmap OR plan,
because it didn't pass down both columns as index quals.
BTW, there are various restrictions on the sort order of SAOPs that
you might want to try to familiarize yourself with. I describe them
(perhaps not very clearly) here:
https://postgr.es/m/CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com
Currently, the optimizer doesn't recognize multi-column indexes with
SAOPs on every column as having a valid sort order, except on the
first column. It seems possible that that has consequences for your
patch. (I'm really only guessing, though; don't trust anything that I
say about the optimizer too much.)
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-25 23:47 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
@ 2023-07-26 22:30 ` Alena Rybakina <[email protected]>
2023-07-29 16:15 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
0 siblings, 1 reply; 25+ messages in thread
From: Alena Rybakina @ 2023-07-26 22:30 UTC (permalink / raw)
To: Peter Geoghegan <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Alena Rybakina <[email protected]>; Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected]; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>
Hi!
On 26.07.2023 02:47, Peter Geoghegan wrote:
> On Thu, Jun 29, 2023 at 2:32 AM Alena Rybakina <[email protected]> wrote:
>> Hi! I'm sorry I didn't answer you right away, I was too busy with work.
> Same for me, this time. I was busy working on my patch, which I
> finally posted yesterday.
I'm glad to hear it, I've seen your thread ("Optimizing nbtree
ScalarArrayOp execution, allowing multi-column ordered scans, skip
scan"), but, unfortunately, I didn't have enough time to read it. I'll
review it soon!
>> To be honest, I didn't think about the fact that my optimization can help eliminate duplicates before reading the data before.
> I'm not surprised that you didn't specifically think of that, because
> it's very subtle.
>
>> I am still only in the process of familiarizing myself with the thread [1] (reference from your letter), but I have already seen that there are problems related, for example, to when "or" expressions refer to the parent element.
> I didn't intend to imply that you might have the same problem here. I
> just meant that OR optimizations can have problems with duplicate
> elimination, in general. I suspect that your patch doesn't have that
> problem, because you are performing a transformation of one kind of OR
> into another kind of OR.
Yes, you are right, but I studied this topic and two other sources to
accumulate my knowledge. It was an exciting experience for me)
I was especially inspired after studying the interview with Goetz Graf
[2], his life experience is the most inspiring, and from this article I
was able to get a broad understanding of the field of databases:
current problems, future development, how it works... Thank you for the
recommendation.
I discovered for myself that the idea described in the article [1] is
similar to the idea of representing grouped data in OLAP cubes, and
also, if I saw correctly, an algorithm like depth-first search is used
there, but for indexes.
I think it really helps to speed up the search with similar deep
filtering compared to cluster indexes, but do we have cases where we
don't use this algorithm because it takes longer than an usual index?
I thought about the situation with wide indexes (with a lot of multiple
columns) and having a lot of filtering predicates for them.
But I'm not sure about this, so it seems to me that this is a problem of
improper use of indexes rather.
>> I think, I would face the similar problems if I complicate the current code, for example, so that not only or expressions standing on the same level are written in any, but also on different ones without violating the logic of the priority of executing operators.
> I can't say that I am particularly experienced in this general area --
> I have never tried to formally reason about how two different
> statements are equivalent. It just hasn't been something that I've
> needed to have a totally rigorous understanding of up until now. But
> my recent patch changes that. Now I need to study this area to make
> sure that I have a truly rigorous understanding.
>
> Jeff Davis suggested that I read "Logic and Databases", by C.J. Date.
> So now I have some homework to do.
I'll read this book too. Maybe I can finish work with the knowledge I
got from there. Thank you for sharing!
>> Unfortunately, when I tried to make a transformation at the stage of index formation, I encountered too incorrect an assessment of the selectivity of relation, which affected the incorrect calculation of the cost and cardinality.
> It's not surprising that a weird shift in the plan chosen by the
> optimizer is seen with some random test case, as a result of this
> added transformation. Even changes that are 100% strictly better (e.g.
> changes in a selectivity estimation function that is somehow
> guaranteed to be more accurate in all cases) might do that. Here is a
> recent example of that with another patch, involving a bitmap OR:
>
> https://postgr.es/m/CAH2-WznCDK9n2tZ6j_-iLN563_ePuC3NzP6VSVTL6jHzs6nRuQ@mail.gmail.com
At first, this surprised me very much. It took time to find a suitable
place to implement the transformation.
I have looked through this thread many times, I will study it in more
detail .
> This example was *not* a regression, if you go by conventional
> measures. It was merely a less robust plan than the bitmap OR plan,
> because it didn't pass down both columns as index quals.
>
> BTW, there are various restrictions on the sort order of SAOPs that
> you might want to try to familiarize yourself with. I describe them
> (perhaps not very clearly) here:
>
> https://postgr.es/m/CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com
Thank you! Yes, I'll study it too)
> Currently, the optimizer doesn't recognize multi-column indexes with
> SAOPs on every column as having a valid sort order, except on the
> first column. It seems possible that that has consequences for your
> patch. (I'm really only guessing, though; don't trust anything that I
> say about the optimizer too much.)
>
Honestly, I couldn't understand your concerns very well, could you
describe it in more detail?
1. https://vldb.org/conf/1995/P710.PDF
2.
https://sigmodrecord.org/publications/sigmodRecord/2009/pdfs/05_Profiles_Graefe.pdf
--
Regards,
Alena Rybakina
Postgres Professional
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-25 23:47 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-07-26 22:30 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-07-29 16:15 ` Peter Geoghegan <[email protected]>
2023-07-31 16:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
0 siblings, 1 reply; 25+ messages in thread
From: Peter Geoghegan @ 2023-07-29 16:15 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Alena Rybakina <[email protected]>; Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected]; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>
On Wed, Jul 26, 2023 at 6:30 PM Alena Rybakina <[email protected]> wrote:
> > I didn't intend to imply that you might have the same problem here. I
> > just meant that OR optimizations can have problems with duplicate
> > elimination, in general. I suspect that your patch doesn't have that
> > problem, because you are performing a transformation of one kind of OR
> > into another kind of OR.
>
> Yes, you are right, but I studied this topic and two other sources to
> accumulate my knowledge. It was an exciting experience for me)
Cool! Yeah, a lot of the value with these sorts of things comes from
the way that they can interact with each other. This is hard to
describe exactly, but still important.
> I was especially inspired after studying the interview with Goetz Graf
> [2], his life experience is the most inspiring, and from this article I
> was able to get a broad understanding of the field of databases:
> current problems, future development, how it works... Thank you for the
> recommendation.
I also think that his perspective is very interesting.
> I think it really helps to speed up the search with similar deep
> filtering compared to cluster indexes, but do we have cases where we
> don't use this algorithm because it takes longer than an usual index?
> I thought about the situation with wide indexes (with a lot of multiple
> columns) and having a lot of filtering predicates for them.
I think that it should be possible for the optimizer to only use
multi-column SAOP index paths when there is at least likely to be some
small advantage -- that's definitely my goal. Importantly, we may not
really need to accurately model the costs where the new approach turns
out to be much faster. The only essential thing is that we avoid cases
where the new approach is much slower than the old approach. Which is
possible (in at least some cases) by making the runtime behavior
adaptive.
The best decision that the planner can make may be no decision at all.
Better to wait until runtime where at all possible, since that gives
us the latest and most accurate picture of things.
> But I'm not sure about this, so it seems to me that this is a problem of
> improper use of indexes rather.
It's hard to say how true that is.
Certainly, workloads similar to the TPC-DS benchmark kinda need
something like MDAM. It's just not practical to have enough indexes to
support every possible query -- the benchmark is deliberately designed
to have unpredictable, hard-to-optimize access paths. It seems to
require having fewer, more general indexes that can support
multi-dimensional access reasonably efficiently.
Of course, with OLTP it's much more likely that the workload will have
predictable access patterns. That makes having exactly the right
indexes much more practical. So maybe you're right there. But, I still
see a lot of value in a design that is as forgiving as possible. Users
really like that kind of thing in my experience.
> > Currently, the optimizer doesn't recognize multi-column indexes with
> > SAOPs on every column as having a valid sort order, except on the
> > first column. It seems possible that that has consequences for your
> > patch. (I'm really only guessing, though; don't trust anything that I
> > say about the optimizer too much.)
> >
> Honestly, I couldn't understand your concerns very well, could you
> describe it in more detail?
Well, I'm not sure if there is any possible scenario where the
transformation from your patch makes it possible to go from an access
path that has a valid sort order (usually because there is an
underlying index scan) into an access path that doesn't. In fact, the
opposite situation seems more likely (which is good news) --
especially if you assume that my own patch is also present.
Going from a bitmap OR (which cannot return sorted output) to a
multi-column SAOP index scan (which now can) may have significant
value in some specific circumstances. Most obviously, it's really
useful when it enables us to feed tuples into a GroupAggregate without
a separate sort step, and without a hash aggregate (that's why I see
value in combining your patch with my own patch). You just need to be
careful about allowing the opposite situation to take place.
More generally, there is a need to think about strange second order
effects. We want to be open to useful second order effects that make
query execution much faster in some specific context, while avoiding
harmful second order effects. Intuitively, I think that it should be
possible to do this with the transformations performed by your patch.
In other words, "helpful serendipity" is an important advantage, while
"harmful anti-serendipity" is what we really want to avoid. Ideally by
making the harmful cases impossible "by construction".
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-25 23:47 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-07-26 22:30 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-29 16:15 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
@ 2023-07-31 16:38 ` Alena Rybakina <[email protected]>
2023-08-01 19:42 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
0 siblings, 1 reply; 25+ messages in thread
From: Alena Rybakina @ 2023-07-31 16:38 UTC (permalink / raw)
To: Peter Geoghegan <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Alena Rybakina <[email protected]>; Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected]; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>
Hi!
>> I think it really helps to speed up the search with similar deep
>> filtering compared to cluster indexes, but do we have cases where we
>> don't use this algorithm because it takes longer than an usual index?
>> I thought about the situation with wide indexes (with a lot of multiple
>> columns) and having a lot of filtering predicates for them.
> I think that it should be possible for the optimizer to only use
> multi-column SAOP index paths when there is at least likely to be some
> small advantage -- that's definitely my goal. Importantly, we may not
> really need to accurately model the costs where the new approach turns
> out to be much faster. The only essential thing is that we avoid cases
> where the new approach is much slower than the old approach. Which is
> possible (in at least some cases) by making the runtime behavior
> adaptive.
>
> The best decision that the planner can make may be no decision at all.
> Better to wait until runtime where at all possible, since that gives
> us the latest and most accurate picture of things.
>
>> But I'm not sure about this, so it seems to me that this is a problem of
>> improper use of indexes rather.
> It's hard to say how true that is.
>
> Certainly, workloads similar to the TPC-DS benchmark kinda need
> something like MDAM. It's just not practical to have enough indexes to
> support every possible query -- the benchmark is deliberately designed
> to have unpredictable, hard-to-optimize access paths. It seems to
> require having fewer, more general indexes that can support
> multi-dimensional access reasonably efficiently.
>
> Of course, with OLTP it's much more likely that the workload will have
> predictable access patterns. That makes having exactly the right
> indexes much more practical. So maybe you're right there. But, I still
> see a lot of value in a design that is as forgiving as possible. Users
> really like that kind of thing in my experience.
I tend to agree with you, but a runtime estimate cannot give us an
accurate picture when using indexes correctly or
any other optimizations due to the unstable state of the environment in
which the query is executed.
I believe that a more complex analysis is needed here.
>>> Currently, the optimizer doesn't recognize multi-column indexes with
>>> SAOPs on every column as having a valid sort order, except on the
>>> first column. It seems possible that that has consequences for your
>>> patch. (I'm really only guessing, though; don't trust anything that I
>>> say about the optimizer too much.)
>>>
>> Honestly, I couldn't understand your concerns very well, could you
>> describe it in more detail?
> Well, I'm not sure if there is any possible scenario where the
> transformation from your patch makes it possible to go from an access
> path that has a valid sort order (usually because there is an
> underlying index scan) into an access path that doesn't. In fact, the
> opposite situation seems more likely (which is good news) --
> especially if you assume that my own patch is also present.
>
> Going from a bitmap OR (which cannot return sorted output) to a
> multi-column SAOP index scan (which now can) may have significant
> value in some specific circumstances. Most obviously, it's really
> useful when it enables us to feed tuples into a GroupAggregate without
> a separate sort step, and without a hash aggregate (that's why I see
> value in combining your patch with my own patch). You just need to be
> careful about allowing the opposite situation to take place.
>
> More generally, there is a need to think about strange second order
> effects. We want to be open to useful second order effects that make
> query execution much faster in some specific context, while avoiding
> harmful second order effects. Intuitively, I think that it should be
> possible to do this with the transformations performed by your patch.
>
> In other words, "helpful serendipity" is an important advantage, while
> "harmful anti-serendipity" is what we really want to avoid. Ideally by
> making the harmful cases impossible "by construction".
>
I noticed only one thing there: when we have unsorted array values in
SOAP, the query takes longer than
when it has a sorted array. I'll double-check it just in case and write
about the results later.
I am also testing some experience with multi-column indexes using SAOPs.
--
Regards,
Alena Rybakina
Postgres Professional
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-25 23:47 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-07-26 22:30 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-29 16:15 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-07-31 16:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
@ 2023-08-01 19:42 ` Peter Geoghegan <[email protected]>
2023-08-01 20:11 ` Re: POC, WIP: OR-clause support for indexes Finnerty, Jim <[email protected]>
0 siblings, 1 reply; 25+ messages in thread
From: Peter Geoghegan @ 2023-08-01 19:42 UTC (permalink / raw)
To: Alena Rybakina <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Alena Rybakina <[email protected]>; Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected]; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>
On Mon, Jul 31, 2023 at 9:38 AM Alena Rybakina <[email protected]> wrote:
> I noticed only one thing there: when we have unsorted array values in
> SOAP, the query takes longer than
> when it has a sorted array. I'll double-check it just in case and write
> about the results later.
I would expect the B-Tree preprocessing by _bt_preprocess_array_keys()
to be very slightly faster when the query is written with presorted,
duplicate-free constants. Sorting is faster when you don't really have
to sort. However, I would not expect the effect to be significant
enough to matter, except perhaps in very extreme cases.
Although...some of the cases you care about are very extreme cases.
> I am also testing some experience with multi-column indexes using SAOPs.
Have you thought about a similar transformation for when the row
constructor syntax happens to have been used?
Consider a query like the following, against a table with a composite
index on (a, b):
select * from multi_test where ( a, b ) in (( 1, 1 ), ( 2, 1 ));
This query will get a BitmapOr based plan that's similar to the plans
that OR-based queries affected by your transformation patch get today,
on HEAD. However, this equivalent spelling has the potential to be
significantly faster:
select * from multi_test where a = any('{1,2}') and b = 1;
(Of course, this is more likely to be true with my nbtree SAOP patch in place.)
Note that we currently won't use RowCompareExpr in many simple cases
where the row constructor syntax has been used. For example, a query
like this:
select * from multi_test where ( a, b ) = (( 2, 1 ));
This case already involves a transformation that is roughly comparable
to the one you're working on now. We'll remove the RowCompareExpr
during parsing. It'll be as if my example row constructor equality
query was written this way instead:
select * from multi_test where a = 2 and b = 1;
This can be surprisingly important, when combined with other things,
in more realistic examples.
The nbtree code has special knowledge of RowCompareExpr that makes the
rules for comparing index tuples different to those from other kinds
of index scans. However, due to the RowCompareExpr transformation
process I just described, we don't need to rely on that specialized
nbtree code when the row constructor syntax is used with a simple
equality clause -- which is what makes the normalization process have
real value. If the nbtree code cannot see RowCompareExpr index quals
then it cannot have this problem in the first place. In general it is
useful to "normalize to conjunctive normal form" when it might allow
scan key preprocessing in the nbtree code to come up with a much
faster approach to executing the scan.
It's easier to understand what I mean by showing a simple example. The
nbtree preprocessing code is smart enough to recognize that the
following query doesn't really need to do any work, due to having
quals that it recognizes as contradictory (it can set so->qual_okay to
false for unsatisfiable quals):
select * from multi_test where ( a, b ) = (( 2, 1 )) and a = -1;
However, it is not smart enough to perform the same trick if we change
one small detail with the query:
select * from multi_test where ( a, b ) >= (( 2, 1 )) and a = -1;
Ideally, the optimizer would canonicalize/normalize everything in a
way that made all of the nbtree preprocessing optimizations work just
as well, without introducing any new special cases. Obviously, there
is no reason why we can't perform the same trick with the second
variant. (Note also that the nbtree preprocessing code can be smart
about redundant quals, not just contradictory quals, so it matters
more than it may appear from this simple, unrealistic example of
mine.)
While these similar RowCompareExpr transformations are at least
somewhat important, that's not really why I bring them up now. I am
pointing them out now because I think that it might help you to
develop a more complete mental model of these transformations.
Ideally, your initial approach will generalize to other situations
later on. So it's worth considering the relationship between this
existing RowCompareExpr transformation, and the one that you're
working on currently. Plus other, future transformations.
This example might also give you some appreciation of why my SAOP
patch is confused about when we need to do normalization/safety
checks. Some things seem necessary when generating index paths in the
optimizer. Other things seem necessary during preprocessing, in the
nbtree code, at the start of the index scan. Unfortunately, it's not
obvious to me where the right place is to deal with each aspect of
setting up multi-column SAOP index quals. My mental model is very
incomplete.
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-25 23:47 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-07-26 22:30 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-29 16:15 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-07-31 16:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-08-01 19:42 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
@ 2023-08-01 20:11 ` Finnerty, Jim <[email protected]>
2023-08-01 21:16 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
0 siblings, 1 reply; 25+ messages in thread
From: Finnerty, Jim @ 2023-08-01 20:11 UTC (permalink / raw)
To: Peter Geoghegan <[email protected]>; Alena Rybakina <[email protected]>; +Cc: Marcos Pegoraro <[email protected]>; Alena Rybakina <[email protected]>; Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected] <[email protected]>; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>
Peter, I'm very glad to hear that you're researching this!
Will this include skip-scan optimizations for OR or IN predicates, or when the number of distinct values in a leading non-constant index column(s) is sufficiently small? e.g. suppose there is an ORDER BY b, and WHERE clause predicates (a = 1 AND b = 5) OR (c > 12 AND b BETWEEN 100 AND 200). Then a single index scan on an index with leading column b could visit b = 5, and then the range b from 100:200, and deliver the rows in the order requested. Or if the predicate is (a = 1 AND b = 5) OR (c LIKE 'XYZ' AND b < 12), then you can scan just b < 12. Or if the index is defined on (a, b) and you know that b = 100, and that there are only 4 distinct values of column a, then you could skip each distinct value of a where b = 100, and so on.
If you have an ORDER BY clause and a lower and upper bound on the first column of the ORDER BY list, you have a potential to reduce search effort versus a full index scan, even when that upper and lower bound needs to be derived from a complex predicate.
Of course, if you have an IN list you can either skip to the distinct values listed or scan the entire index, depending on estimated cost.
/Jim F
On 8/1/23, 3:43 PM, "Peter Geoghegan" <[email protected] <mailto:[email protected]>> wrote:
CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.
On Mon, Jul 31, 2023 at 9:38 AM Alena Rybakina <[email protected] <mailto:[email protected]>> wrote:
> I noticed only one thing there: when we have unsorted array values in
> SOAP, the query takes longer than
> when it has a sorted array. I'll double-check it just in case and write
> about the results later.
I would expect the B-Tree preprocessing by _bt_preprocess_array_keys()
to be very slightly faster when the query is written with presorted,
duplicate-free constants. Sorting is faster when you don't really have
to sort. However, I would not expect the effect to be significant
enough to matter, except perhaps in very extreme cases.
Although...some of the cases you care about are very extreme cases.
> I am also testing some experience with multi-column indexes using SAOPs.
Have you thought about a similar transformation for when the row
constructor syntax happens to have been used?
Consider a query like the following, against a table with a composite
index on (a, b):
select * from multi_test where ( a, b ) in (( 1, 1 ), ( 2, 1 ));
This query will get a BitmapOr based plan that's similar to the plans
that OR-based queries affected by your transformation patch get today,
on HEAD. However, this equivalent spelling has the potential to be
significantly faster:
select * from multi_test where a = any('{1,2}') and b = 1;
(Of course, this is more likely to be true with my nbtree SAOP patch in place.)
Note that we currently won't use RowCompareExpr in many simple cases
where the row constructor syntax has been used. For example, a query
like this:
select * from multi_test where ( a, b ) = (( 2, 1 ));
This case already involves a transformation that is roughly comparable
to the one you're working on now. We'll remove the RowCompareExpr
during parsing. It'll be as if my example row constructor equality
query was written this way instead:
select * from multi_test where a = 2 and b = 1;
This can be surprisingly important, when combined with other things,
in more realistic examples.
The nbtree code has special knowledge of RowCompareExpr that makes the
rules for comparing index tuples different to those from other kinds
of index scans. However, due to the RowCompareExpr transformation
process I just described, we don't need to rely on that specialized
nbtree code when the row constructor syntax is used with a simple
equality clause -- which is what makes the normalization process have
real value. If the nbtree code cannot see RowCompareExpr index quals
then it cannot have this problem in the first place. In general it is
useful to "normalize to conjunctive normal form" when it might allow
scan key preprocessing in the nbtree code to come up with a much
faster approach to executing the scan.
It's easier to understand what I mean by showing a simple example. The
nbtree preprocessing code is smart enough to recognize that the
following query doesn't really need to do any work, due to having
quals that it recognizes as contradictory (it can set so->qual_okay to
false for unsatisfiable quals):
select * from multi_test where ( a, b ) = (( 2, 1 )) and a = -1;
However, it is not smart enough to perform the same trick if we change
one small detail with the query:
select * from multi_test where ( a, b ) >= (( 2, 1 )) and a = -1;
Ideally, the optimizer would canonicalize/normalize everything in a
way that made all of the nbtree preprocessing optimizations work just
as well, without introducing any new special cases. Obviously, there
is no reason why we can't perform the same trick with the second
variant. (Note also that the nbtree preprocessing code can be smart
about redundant quals, not just contradictory quals, so it matters
more than it may appear from this simple, unrealistic example of
mine.)
While these similar RowCompareExpr transformations are at least
somewhat important, that's not really why I bring them up now. I am
pointing them out now because I think that it might help you to
develop a more complete mental model of these transformations.
Ideally, your initial approach will generalize to other situations
later on. So it's worth considering the relationship between this
existing RowCompareExpr transformation, and the one that you're
working on currently. Plus other, future transformations.
This example might also give you some appreciation of why my SAOP
patch is confused about when we need to do normalization/safety
checks. Some things seem necessary when generating index paths in the
optimizer. Other things seem necessary during preprocessing, in the
nbtree code, at the start of the index scan. Unfortunately, it's not
obvious to me where the right place is to deal with each aspect of
setting up multi-column SAOP index quals. My mental model is very
incomplete.
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: POC, WIP: OR-clause support for indexes
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-25 23:47 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-07-26 22:30 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-29 16:15 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-07-31 16:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-08-01 19:42 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-08-01 20:11 ` Re: POC, WIP: OR-clause support for indexes Finnerty, Jim <[email protected]>
@ 2023-08-01 21:16 ` Peter Geoghegan <[email protected]>
0 siblings, 0 replies; 25+ messages in thread
From: Peter Geoghegan @ 2023-08-01 21:16 UTC (permalink / raw)
To: Finnerty, Jim <[email protected]>; +Cc: Alena Rybakina <[email protected]>; Marcos Pegoraro <[email protected]>; Alena Rybakina <[email protected]>; Andrey Lepikhov <[email protected]>; pgsql-hackers; [email protected] <[email protected]>; Ranier Vilela <[email protected]>; Tomas Vondra <[email protected]>
Jim,
On Tue, Aug 1, 2023 at 1:11 PM Finnerty, Jim <[email protected]> wrote:
> Peter, I'm very glad to hear that you're researching this!
Glad to hear it!
> Will this include skip-scan optimizations for OR or IN predicates, or when the number of distinct values in a leading non-constant index column(s) is sufficiently small?
Yes -- though perhaps not in the first iteration.
As I go into on the thread associated with my own patch [1], my
initial goal is to support efficient execution of multiple IN() lists
for multiple columns from the same index, all while preserving index
sort order on output, and avoiding a separate duplicate elimination
step. Some of the most compelling cases for these MDAM techniques
involve GroupAggregates, ORDER BY ... LIMIT, and DISTINCT -- I
understand the importance of making the index scan appear to be a
conventional index scan to the optimizer.
> If you have an ORDER BY clause and a lower and upper bound on the first column of the ORDER BY list, you have a potential to reduce search effort versus a full index scan, even when that upper and lower bound needs to be derived from a complex predicate.
It sounds like your example is an attempt to ascertain whether or not
my design considers the need to convert complicated predicates into
disjuncts that can be executed as if by one single index scan, via CNF
-> DNF transformations/preprocessing. That is certainly the plan, at
least medium term -- I fully expect to be able to combine all of these
techniques together, in ways that continue to work even with very
complicated predicates. Like the really hairy example from the MDAM
paper, or like your example.
There are already some nbtree scan key preprocessing steps a little
like the ones considered by the MDAM paper. These steps eliminate
redundant and contradictory quals -- but they weren't specifically
written with the very general MDAM DNF design requirements in mind.
Plus there are already at least some transformations like the one that
Alena is working on in the patch discussed on this thread -- these
were also not written with MDAM stuff in mind.
A major goal of mine for this project in the short term is to come up
with a very general design. I must reconcile all this stuff, somehow
or other, so that these very complicated cases will work just as well
as simpler and more obvious cases. I really hate special cases.
> Of course, if you have an IN list you can either skip to the distinct values listed or scan the entire index, depending on estimated cost.
Actually, I think that it should be possible to decide on how to skip
dynamically, without needing an up-front decision around skipping from
the optimizer. In other words, the scans can skip using an adaptive
strategy. This is feasible provided I can make the overhead of a
dynamic/adaptive approach negligible. When it turns out that a full
index scan is appropriate, we'll just end up doing it that way at
runtime.
Nothing stops a given scan from needing to do skip a great deal in the
first half of an index, while scanning everything in the second half
of the index. Obviously, a static choice won't do well there, since it
works at the level of the whole scan/index, which seems like the wrong
framing to me. (Of course we'll still need to model skipping stuff in
the planner -- just not so that we can decide between two index paths
that are essentially identical, that should just be one index path.)
[1] https://postgr.es/m/CAH2-Wz=ksvN_sjcnD1+Bt-WtifRA5ok48aDYnq3pkKhxgMQpcw@mail.gmail.com
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 25+ messages in thread
end of thread, other threads:[~2023-08-01 21:16 UTC | newest]
Thread overview: 25+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2022-08-16 21:22 [PATCH 03/17] avoid shadow vars: pg_dump.c: owning_tab Justin Pryzby <[email protected]>
2023-06-27 19:50 Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-06-29 09:32 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 09:55 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-06-29 11:23 ` Re: POC, WIP: OR-clause support for indexes Ranier Vilela <[email protected]>
2023-06-29 15:16 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 19:39 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-05 20:06 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-06 10:20 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-07 08:20 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-10 03:12 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-10 08:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-10 12:03 ` Re: POC, WIP: OR-clause support for indexes Ranier Vilela <[email protected]>
2023-07-10 12:15 ` Re: POC, WIP: OR-clause support for indexes Ranier Vilela <[email protected]>
2023-07-11 08:47 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-11 18:11 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-18 14:25 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-07 02:43 ` Re: POC, WIP: OR-clause support for indexes Andrey Lepikhov <[email protected]>
2023-07-25 23:47 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-07-26 22:30 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-07-29 16:15 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-07-31 16:38 ` Re: POC, WIP: OR-clause support for indexes Alena Rybakina <[email protected]>
2023-08-01 19:42 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
2023-08-01 20:11 ` Re: POC, WIP: OR-clause support for indexes Finnerty, Jim <[email protected]>
2023-08-01 21:16 ` Re: POC, WIP: OR-clause support for indexes Peter Geoghegan <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox