Em qui., 29 de jun. de 2023 às 02:50, Alena Rybakina < lena.riback...@yandex.ru> escreveu:
> Hi!
> On 29.06.2023 04:36, Ranier Vilela wrote:
>
> I don't want to be rude, but this doesn't seem very helpful.
>>
> Sorry, It was not my intention to cause interruptions.
>
>
>> - You made some changes, but you don't even attempt to explain what you
>> changed or why you changed it.
>>
> 1. Reduce scope
> 2. Eliminate unnecessary variables
> 3. Eliminate unnecessary expressions
>
>
>>
>> - You haven't even tried to compile the code, nor tested it. If it
>> happens to compile, wow could others even know it actually behaves the
>> way you wanted?
>
> Sorry I didn't answer right away. I will try not to do this in the future
> thank you for your participation and help.
>
There's no need to apologize.
> Yes, the scope of this patch may be small, but I am sure that it will
> solve the worst case of memory consumption with large numbers of "or"
> expressions or reduce execution and planning time.
>
Yeah, I also believe it will help performance.
> As I have already said, I conducted a launch on a database with 20 billion
> data generated using a benchmark. Unfortunately, at that time I sent a not
> quite correct picture: the execution time, not the planning time, increases
> with the number of "or" expressions (execution_time.png). x is the number
> of or expressions, y is the execution/scheduling time.I also throw memory
> consumption at 50,000 "or" expressions collected by HeapTrack (where memory
> consumption was recorded already at the initialization stage of the 1.27GB
> pic3.png). I think such a transformation will allow just the same to avoid
> such a worst case, since in comparison with ANY memory is much less and
> takes little time.
>
SELECT FORMAT('prepare x %s AS SELECT * FROM pgbench_accounts a WHERE %s',
> '(' || string_agg('int', ',') || ')',
> string_agg(FORMAT('aid = $%s', g.id), ' or ')
> ) AS cmd
> FROM generate_series(1, 50000) AS g(id)
> \gexec
>
> SELECT FORMAT('execute x %s;', '(' || string_agg(g.id::text, ',') || ')') AS
> cmd
> FROM generate_series(1, 50000) AS g(id)
> \gexec
>
> I tried to add a transformation at the path formation stage before we form
> indexes (set_plain_rel_pathlist function) and at the stage when we have
> preprocessing of "or" expressions (getting rid of duplicates or useless
> conditions), but everywhere there was a problem of incorrect selectivity
> estimation.
>
> 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);
>
> 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..140632434.50 rows=11250150000 width=32) (actual
> time=0.077..373.279 rows=1350000 loops=1)
> -> Seq Scan on tenk1 b (cost=0.00..2311.00 rows=150000 width=16) (actual
> time=0.037..13.941 rows=150000 loops=1)
> -> Materialize (cost=0.00..3436.01 rows=75001 width=16) (actual
> time=0.000..0.001 rows=9 loops=150000)
> -> Seq Scan on tenk1 a (cost=0.00..3061.00 rows=75001 width=16)
> (actual time=0.027..59.174 rows=9 loops=1)
> Filter: ((unique2 = ANY (ARRAY[3, 7])) OR (unique1 = 1))
> Rows Removed by Filter: 149991
> Planning Time: 0.438 ms
> Execution Time: 407.144 ms
> (8 rows)
>
> Only by converting the expression at this stage, we do not encounter this
> problem.
>
> 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)
>
> I compiled my original patch and there were no problems with regression
> tests. The only time there was a problem when I set the
> const_transform_or_limit variable to 0 (I have 15), as you have in the
> patch. To be honest, diff appears there because you had a different plan,
> specifically the expressions "or" are replaced by ANY (see
> regression.diffs).
>
You are right. The v3 attached shows the same diff.
Unfortunately, your patch version did not apply immediately, I did not
> understand the reasons, I applied it manually.
>
Sorry.
> At the moment, I'm not sure that the constant is the right number for
> applying transformations, so I'm in search of it, to be honest. I will post
> my observations on this issue later. If you don't mind, I'll leave the
> constant equal to 15 for now.
>
It's hard to predict. Perhaps accounting for time on each benchmark could
help decide.
> Sorry, I don't understand well enough what is meant by points "Eliminate
> unnecessary variables" and "Eliminate unnecessary expressions". Can you
> explain in more detail?
>
One example is array_type.
As you can see in v2 and v3 it no longer exists.
>
> Regarding the patch, there was a Warning at the compilation stage.
>
> In file included from ../../../src/include/nodes/bitmapset.h:21,
>
> from ../../../src/include/nodes/parsenodes.h:26,
>
> from ../../../src/include/catalog/objectaddress.h:17,
>
> from ../../../src/include/catalog/pg_aggregate.h:24,
>
> from parse_expr.c:18:
>
> parse_expr.c: In function ‘transformBoolExprOr’:
>
> ../../../src/include/nodes/nodes.h:133:66: warning: ‘expr’ is used
> uninitialized [-Wuninitialized]
>
> 133 | #define nodeTag(nodeptr) (((const
> Node*)(nodeptr))->type)
>
> | ^~
>
> parse_expr.c:116:29: note: ‘expr’ was declared here
>
> 116 | BoolExpr *expr;
>
> | ^~~~
>
> Sorry, this error did not appear in my builds
> I couldn't figure out how to fix it and went back to my original version.
> To be honest, I don't think anything needs to be changed here.
>
> Unfortunately, I didn't understand the reasons why, with the available or
> expressions, you don't even try to convert to ANY by calling
> transformBoolExpr, as I saw. I went back to my version.
>
> I think it's worth checking whether the or_statement variable is positive.
>
> I think it's worth leaving the use of the or_statement variable in its
> original form.
>
> 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);
>
You are right, the v3 this way.
As I said earlier, these are just suggestions.
But thinking about it now, I think they can be classified as bad early
optimizations.
regards,
Ranier Vilela
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 346fd272b6..99b12d4037 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 = 0;
+
+static Node *
+transformBoolExprOr(ParseState *pstate, Expr *expr_orig)
+{
+ List *or_list = NIL;
+ List *groups_list = NIL;
+ ListCell *lc_eargs;
+ Node *result;
+ BoolExpr *expr;
+ const char *opname;
+ bool change_apply = false;
+ bool or_statement = false;
+
+ Assert(IsA(expr, BoolExpr));
+
+ expr = (BoolExpr *) expr_orig;
+ if (list_length(expr->args) < const_transform_or_limit)
+ return transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+
+ /* 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;
+ }
+
+ /*
+ * 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.
+ */
+ if (!or_statement)
+ return transformBoolExpr(pstate, (BoolExpr *)expr_orig);
+
+ expr = (BoolExpr *)copyObject(expr_orig);
+ 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 = (
+ 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;
+
+ 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 &&
+ verify_common_type(scalar_type, allexprs))
+ {
+ /*
+ * 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 260854747b..01918e6aea 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1630,6 +1630,7 @@ NumericSumAccum
NumericVar
OM_uint32
OP
+OrClauseGroupEntry
OSAPerGroupState
OSAPerQueryState
OSInfo
v3-regression.diffs
Description: Binary data
