public inbox for [email protected]
help / color / mirror / Atom feedFrom: a.rybakina <[email protected]>
To: Peter Geoghegan <[email protected]>
Cc: Finnerty, Jim <[email protected]>
Cc: Marcos Pegoraro <[email protected]>
Cc: Andrey Lepikhov <[email protected]>
Cc: [email protected]
Cc: [email protected]
Cc: Ranier Vilela <[email protected]>
Cc: Tomas Vondra <[email protected]>
Subject: Re: POC, WIP: OR-clause support for indexes
Date: Thu, 17 Aug 2023 13:20:33 +0300
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
<[email protected]>
<CAH2-WzmD5u5kCZG0qMtVySz8VB1_drOiX=j0buDufK-EJc3YkQ@mail.gmail.com>
<[email protected]>
<CAH2-WzkzzDK7FPEv7M5GL_jo0E81DDG41t7wHU9SOAwnqwX=eQ@mail.gmail.com>
<[email protected]>
<CAH2-Wzm-W7KYtMQ_3F1zU3Fg0zhRd-kASuOzNewXEWjR5kZrtg@mail.gmail.com>
<[email protected]>
<CAH2-WznHNTXQ=bX4Kc9hHebyXvR0a0CxH9OnirkP0ahgQAX7Aw@mail.gmail.com>
<[email protected]>
<CAH2-WzkNaPbBJ_yWDXzk5ESJZH62vi=+brHHQ2SrDrPXka1xYA@mail.gmail.com>
<[email protected]>
<CAH2-WzmG-+vvN6YEh4J_j3-Q1Yn=HRrjDrz2HDhttPcLVqN0rw@mail.gmail.com>
<[email protected]>
<CAH2-WzkmLg0JPXkZ75b+ha_wJGoJk3QyZ6aUjA0Ba11rdPwdgw@mail.gmail.com>
<[email protected]>
<[email protected]>
Sorry, I didn't write correctly enough, about the second second place in
the code where the conversion works well enough is the removal of
duplicate OR expressions.
I attached patch to learn it in more detail.
On 17.08.2023 13:08, a.rybakina wrote:
> Hi, all!
>>> The optimizer will itself do a limited form of "normalizing to CNF".
>>> Are you familiar with extract_restriction_or_clauses(), from
>>> orclauses.c? Comments above the function have an example of how this
>>> can work:
>>>
>>> * Although a join clause must reference multiple relations overall,
>>> * an OR of ANDs clause might contain sub-clauses that reference
>>> just one
>>> * relation and can be used to build a restriction clause for that
>>> rel.
>>> * For example consider
>>> * WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45));
>>> * We can transform this into
>>> * WHERE ((a.x = 42 AND b.y = 43) OR (a.x = 44 AND b.z = 45))
>>> * AND (a.x = 42 OR a.x = 44)
>>> * AND (b.y = 43 OR b.z = 45);
>>> * which allows the latter clauses to be applied during the scans
>>> of a and b,
>>> * perhaps as index qualifications, and in any case reducing the
>>> number of
>>> * rows arriving at the join. In essence this is a partial
>>> transformation to
>>> * CNF (AND of ORs format). It is not complete, however, because
>>> we do not
>>> * unravel the original OR --- doing so would usually bloat the
>>> qualification
>>> * expression to little gain.
>> This is an interesting feature. I didn't notice this function before,
>> I studied many times consider_new_or_cause, which were called there.
>> As far as I know, there is a selectivity calculation going on there,
>> but as far as I remember, I called it earlier after my conversion,
>> and unfortunately it didn't solve my problem with calculating
>> selectivity. I'll reconsider it again, maybe I can find something I
>> missed.
>>> Of course this immediately makes me wonder: shouldn't your patch be
>>> able to perform an additional transformation here? You know, by
>>> transforming "a.x = 42 OR a.x = 44" into "a IN (42, 44)"? Although I
>>> haven't checked for myself, I assume that this doesn't happen right
>>> now, since your patch currently performs all of its transformations
>>> during parsing.
>>>
>>> I also noticed that the same comment block goes on to say something
>>> about "clauselist_selectivity's inability to recognize redundant
>>> conditions". Perhaps that is relevant to the problems you were having
>>> with selectivity estimation, back when the code was in
>>> preprocess_qual_conditions() instead? I have no reason to believe that
>>> there should be any redundancy left behind by your transformation, so
>>> this is just one possibility to consider.
>>> Separately, the commit message of commit 25a9e54d2d says something
>>> about how the planner builds RestrictInfos, which seems
>>> possibly-relevant. That commit enhanced extended statistics for OR
>>> clauses, so the relevant paragraph describes a limitation of extended
>>> statistics with OR clauses specifically. I'm just guessing, but it
>>> still seems like it might be relevant to the problem you ran into with
>>> selectivity estimation. Another possibility to consider.
>>
>> I understood what is said about AND clauses in this comment. It seems
>> to me that AND clauses saved like (BoolExpr *)
>> expr->args->(RestrictInfo *) clauseA->(RestrictInfo *)clauseB lists
>> and OR clauses saved like (BoolExpr *) expr ->
>> orclause->(RestrictInfo *)clause A->(RestrictInfo *)clause B.
>>
>> As I understand it, selectivity is calculated for each expression.
>> But I'll exploring it deeper, because I think this place may contain
>> the answer to the question, what's wrong with selectivity calculation
>> in my patch.
>
> I could move transformation in there (extract_restriction_or_clauses)
> and didn't have any problem with selectivity calculation, besides it
> also works on the redundant or duplicates stage. So, it looks like:
>
> CREATE TABLE tenk1 (unique1 int, unique2 int, ten int, hundred int);
> 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);
>
> explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3
> or a.unique2 = 7));
>
> PLAN
> ------------------------------------------------------------------------------------------------------------------------------
> Nested Loop (cost=0.29..2033.62 rows=100000 width=32) (actual
> time=0.090..60.258 rows=100000 loops=1) -> Seq Scan on tenk1 b
> (cost=0.00..771.00 rows=50000 width=16) (actual time=0.016..9.747
> rows=50000 loops=1) -> Materialize (cost=0.29..12.62 rows=2 width=16)
> (actual time=0.000..0.000 rows=2 loops=50000) -> Index Scan using
> a_idx2 on tenk1 a (cost=0.29..12.62 rows=2 width=16) (actual
> time=0.063..0.068 rows=2 loops=1) Index Cond: (unique2 = ANY (ARRAY[3,
> 7])) Planning Time: 8.257 ms Execution Time: 64.453 ms (7 rows)
>
> Overall, this was due to incorrectly defined types of elements in the
> array, and if we had applied the transformation with the definition of
> the tup operator, we could have avoided such problems (I used
> make_scalar_array_op and have not yet found an alternative to this).
>
> When I moved the transformation on the index creation stage, it
> couldn't work properly and as a result I faced the same problem of
> selectivity calculation. I supposed that the selectivity values are
> also used there, and not recalculated all over again. perhaps we can
> solve this by forcibly recalculating the selectivity values, but I
> foresee other problems there.
>
> explain analyze select * from tenk1 a join tenk1 b on ((a.unique2 = 3
> or a.unique2 = 7));
>
> QUERY PLAN
> -----------------------------------------------------------------------------------------------------------------------------------
> Nested Loop (cost=12.58..312942.91 rows=24950000 width=32) (actual
> time=0.040..47.582 rows=100000 loops=1) -> Seq Scan on tenk1 b
> (cost=0.00..771.00 rows=50000 width=16) (actual time=0.009..7.039
> rows=50000 loops=1) -> Materialize (cost=12.58..298.16 rows=499
> width=16) (actual time=0.000..0.000 rows=2 loops=50000) -> Bitmap Heap
> Scan on tenk1 a (cost=12.58..295.66 rows=499 width=16) (actual
> time=0.025..0.028 rows=2 loops=1) Recheck Cond: ((unique2 = 3) OR
> (unique2 = 7)) Heap Blocks: exact=1 -> BitmapOr (cost=12.58..12.58
> rows=500 width=0) (actual time=0.023..0.024 rows=0 loops=1) -> Bitmap
> Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual
> time=0.019..0.019 rows=1 loops=1) Index Cond: (unique2 = 3) -> Bitmap
> Index Scan on a_idx2 (cost=0.00..6.17 rows=250 width=0) (actual
> time=0.003..0.003 rows=1 loops=1) Index Cond: (unique2 = 7) Planning
> Time: 0.401 ms Execution Time: 51.350 ms (13 rows)
>
> I have attached a diff file so far, but it is very raw and did not
> pass all regression tests (I attached regression.diff) and even had
> bad conversion cases (some of the cases did not work at all, in other
> cases there were no non-converted nodes). But now I see an interesting
> transformation, which was the most interesting for me.
>
> EXPLAIN (COSTS OFF) SELECT * FROM tenk1 WHERE thousand = 42 AND
> (tenthous = 1 OR tenthous = 3 OR tenthous = 42); - QUERY PLAN
> ------------------------------------------------------------------------------------------------------------------------------------------
> - Bitmap Heap Scan on tenk1 - Recheck Cond: (((thousand = 42) AND
> (tenthous = 1)) OR ((thousand = 42) AND (tenthous = 3)) OR ((thousand
> = 42) AND (tenthous = 42))) - -> BitmapOr - -> Bitmap Index Scan on
> tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous =
> 1)) - -> Bitmap Index Scan on tenk1_thous_tenthous - Index Cond:
> ((thousand = 42) AND (tenthous = 3)) - -> Bitmap Index Scan on
> tenk1_thous_tenthous - Index Cond: ((thousand = 42) AND (tenthous =
> 42)) -(9 rows) + QUERY PLAN
> +------------------------------------------------------------------------
> + Index Scan using tenk1_thous_tenthous on tenk1 + Index Cond:
> ((thousand = 42) AND (tenthous = ANY (ARRAY[1, 3, 42]))) +(2 rows)
>
Attachments:
[text/x-patch] diff_fix_sel1.diff (8.7K, ../[email protected]/3-diff_fix_sel1.diff)
download | inline diff:
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 44efb1f4ebc..80935cec7aa 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -67,6 +67,7 @@
#include "utils/rel.h"
#include "utils/selfuncs.h"
#include "utils/syscache.h"
+#include "optimizer/orclauses.h"
/* GUC parameters */
double cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
@@ -1169,7 +1170,7 @@ preprocess_expression(PlannerInfo *root, Node *expr, int kind)
if (kind == EXPRKIND_QUAL)
{
expr = (Node *) canonicalize_qual((Expr *) expr, false);
-
+expr = transform_ors(root, (Expr *) expr);
#ifdef OPTIMIZER_DEBUG
printf("After canonicalize_qual()\n");
pprint(expr);
diff --git a/src/backend/optimizer/util/orclauses.c b/src/backend/optimizer/util/orclauses.c
index 6ef9d14b902..2e30f2bf88a 100644
--- a/src/backend/optimizer/util/orclauses.c
+++ b/src/backend/optimizer/util/orclauses.c
@@ -22,6 +22,10 @@
#include "optimizer/optimizer.h"
#include "optimizer/orclauses.h"
#include "optimizer/restrictinfo.h"
+#include "utils/lsyscache.h"
+#include "parser/parse_expr.h"
+#include "parser/parse_coerce.h"
+#include "parser/parse_oper.h"
static bool is_safe_restriction_clause_for(RestrictInfo *rinfo, RelOptInfo *rel);
@@ -29,7 +33,255 @@ static Expr *extract_or_clause(RestrictInfo *or_rinfo, RelOptInfo *rel);
static void consider_new_or_clause(PlannerInfo *root, RelOptInfo *rel,
Expr *orclause, RestrictInfo *join_or_rinfo);
+typedef struct OrClauseGroupEntry
+{
+ Node *node;
+ List *consts;
+ Oid collation;
+ Oid opno;
+ RestrictInfo *rinfo;
+ Expr *expr;
+} 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 Expr *
+transform_ors_for_rel(Expr *qual)
+{
+ List *modified_clause = NIL;
+ bool something_changed = false;
+ List *or_list = NIL;
+ ListCell *lc_eargs,
+ *lc_args;
+ List *groups_list = NIL;
+ bool change_apply = false;
+
+ if (!(is_orclause(qual)))
+ {
+ /* Add a clause without changes */
+ return qual;
+ }
+
+ /*
+ * 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, ((BoolExpr *) qual)->args)
+ {
+ Expr *bare_orarg = (Expr *) lfirst(lc_eargs);
+ Node *const_expr;
+ Node *non_const_expr;
+ ListCell *lc_groups;
+ OrClauseGroupEntry *gentry;
+ Oid opno;
+
+ /* Check: it is an expr of the form 'F(x) oper ConstExpr' */
+ if (!bare_orarg ||
+ 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 = get_rightop(bare_orarg);
+ non_const_expr = get_leftop(bare_orarg);
+
+ opno = ((OpExpr *)bare_orarg)->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 *) bare_orarg);
+ gentry->opno = opno;
+ gentry->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.
+ */
+ modified_clause = lappend(modified_clause, qual);
+ }
+ else
+ {
+ /* Let's convert each group of clauses to an IN operation. */
+
+ /*
+ * Go through the list of groups and convert each, where number of
+ * consts more than 1. trivial groups move to OR-list again
+ */
+
+ foreach(lc_args, groups_list)
+ {
+ OrClauseGroupEntry *gentry = (OrClauseGroupEntry *) lfirst(lc_args);
+ List *allexprs;
+ Oid scalar_type;
+ Oid array_type;
+
+ Assert(list_length(gentry->consts) > 0);
+
+ if (list_length(gentry->consts) == 1)
+ {
+ /*
+ * Only one element in the class. Return rinfo into the BoolExpr
+ * args list unchanged.
+ */
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ continue;
+ }
+
+ /*
+ * Do the transformation.
+ *
+ * First of all, try to select a common type for the array elements.
+ * Note that since the LHS' type is first in the list, it will be
+ * preferred when there is doubt (eg, when all the RHS items are
+ * unknown literals).
+ *
+ * Note: use list_concat here not lcons, to avoid damaging rnonvars.
+ *
+ * As a source of insides, use make_scalar_array_op()
+ */
+ allexprs = list_concat(list_make1(gentry->node), gentry->consts);
+ scalar_type = select_common_type(NULL, allexprs, NULL, NULL);
+
+ if (scalar_type != RECORDOID && OidIsValid(scalar_type))
+ array_type = get_array_type(scalar_type);
+ else
+ array_type = InvalidOid;
+
+ if (array_type != InvalidOid)
+ {
+ /*
+ * OK: coerce all the right-hand non-Var inputs to the common
+ * type and build an ArrayExpr for them.
+ */
+ List *aexprs;
+ ArrayExpr *newa;
+ ScalarArrayOpExpr *saopexpr;
+ ListCell *l;
+
+ aexprs = NIL;
+
+ foreach(l, gentry->consts)
+ {
+ Node *rexpr = (Node *) lfirst(l);
+
+ rexpr = coerce_to_common_type(NULL, rexpr,
+ scalar_type,
+ "IN");
+ aexprs = lappend(aexprs, rexpr);
+ }
+
+ newa = makeNode(ArrayExpr);
+ /* array_collid will be set by parse_collate.c */
+ newa->element_typeid = scalar_type;
+ newa->array_typeid = array_type;
+ newa->multidims = false;
+ newa->elements = aexprs;
+ newa->location = -1;
+
+ saopexpr =
+ (ScalarArrayOpExpr *)
+ make_scalar_array_op(NULL,
+ list_make1(makeString((char *) "=")),
+ true,
+ gentry->node,
+ (Node *) newa,
+ -1);
+
+ or_list = lappend(or_list, (void *) saopexpr);
+ }
+ else
+ {
+ list_free(gentry->consts);
+ or_list = lappend(or_list, gentry->expr);
+ 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 */
+ qual = list_length(or_list) > 1 ? make_orclause(or_list) : linitial(or_list);
+ //modified_clause = lappend(modified_clause, qual);
+ 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_clause;
+ } */
+
+ list_free(modified_clause);
+ return qual;
+}
+Node *
+transform_ors(PlannerInfo *root, Expr *jtnode)
+{
+ return (Node *) transform_ors_for_rel(jtnode);
+}
/*
* extract_restriction_or_clauses
* Examine join OR-of-AND clauses to see if any useful restriction OR
diff --git a/src/include/optimizer/orclauses.h b/src/include/optimizer/orclauses.h
index f9dbe6a2972..6a232aeb3ed 100644
--- a/src/include/optimizer/orclauses.h
+++ b/src/include/optimizer/orclauses.h
@@ -17,5 +17,5 @@
#include "nodes/pathnodes.h"
extern void extract_restriction_or_clauses(PlannerInfo *root);
-
+extern Node * transform_ors(PlannerInfo *root, Expr *jtnode);
#endif /* ORCLAUSES_H */
view thread (33+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: POC, WIP: OR-clause support for indexes
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox