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)
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 */
