agora inbox for [email protected]
help / color / mirror / Atom feedFrom: Tomas Vondra <[email protected]>
Subject: [PATCH 3/4] simplify ndistinct
Date: Thu, 25 Mar 2021 00:00:31 +0100
---
src/backend/utils/adt/selfuncs.c | 306 ++++++-------------------------
1 file changed, 56 insertions(+), 250 deletions(-)
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index f58840c877..3a9d16bcb8 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -3233,153 +3233,66 @@ matchingjoinsel(PG_FUNCTION_ARGS)
/*
* Helper routine for estimate_num_groups: add an item to a list of
- * GroupVarInfos, but only if it's not known equal to any of the existing
+ * GroupExprInfos, but only if it's not known equal to any of the existing
* entries.
*/
typedef struct
{
- Node *var; /* might be an expression, not just a Var */
+ Node *expr; /* expression */
RelOptInfo *rel; /* relation it belongs to */
double ndistinct; /* # distinct values */
-} GroupVarInfo;
+} GroupExprInfo;
static List *
-add_unique_group_var(PlannerInfo *root, List *varinfos,
- Node *var, VariableStatData *vardata)
+add_unique_group_expr(PlannerInfo *root, List *exprinfos, Node *expr,
+ VariableStatData *vardata)
{
- GroupVarInfo *varinfo;
+ GroupExprInfo *exprinfo;
double ndistinct;
bool isdefault;
ListCell *lc;
ndistinct = get_variable_numdistinct(vardata, &isdefault);
- foreach(lc, varinfos)
+ /* can't get both vars and vardata for the expression */
+ Assert(vardata);
+
+ foreach(lc, exprinfos)
{
- varinfo = (GroupVarInfo *) lfirst(lc);
+ exprinfo = (GroupExprInfo *) lfirst(lc);
/* Drop exact duplicates */
- if (equal(var, varinfo->var))
- return varinfos;
+ if (equal(expr, exprinfo->expr))
+ return exprinfos;
/*
* Drop known-equal vars, but only if they belong to different
* relations (see comments for estimate_num_groups)
*/
- if (vardata->rel != varinfo->rel &&
- exprs_known_equal(root, var, varinfo->var))
+ if (vardata->rel != exprinfo->rel &&
+ exprs_known_equal(root, expr, exprinfo->expr))
{
- if (varinfo->ndistinct <= ndistinct)
+ if (exprinfo->ndistinct <= ndistinct)
{
/* Keep older item, forget new one */
- return varinfos;
+ return exprinfos;
}
else
{
/* Delete the older item */
- varinfos = foreach_delete_current(varinfos, lc);
+ exprinfos = foreach_delete_current(exprinfos, lc);
}
}
}
- varinfo = (GroupVarInfo *) palloc(sizeof(GroupVarInfo));
-
- varinfo->var = var;
- varinfo->rel = vardata->rel;
- varinfo->ndistinct = ndistinct;
- varinfos = lappend(varinfos, varinfo);
- return varinfos;
-}
-
-/*
- * Helper routine for estimate_num_groups: add an item to a list of
- * GroupExprInfos, but only if it's not known equal to any of the existing
- * entries.
- */
-typedef struct
-{
- Node *expr; /* expression */
- RelOptInfo *rel; /* relation it belongs to */
- List *varinfos; /* info for variables in this expression */
-} GroupExprInfo;
-
-static List *
-add_unique_group_expr(PlannerInfo *root, List *exprinfos, Node *expr,
- List *vars, VariableStatData *vardata)
-{
- GroupExprInfo *exprinfo;
- ListCell *lc;
-
- /* can't get both vars and vardata for the expression */
- Assert(!(vars && vardata));
-
- foreach(lc, exprinfos)
- {
- exprinfo = (GroupExprInfo *) lfirst(lc);
-
- /* Drop exact duplicates */
- if (equal(expr, exprinfo->expr))
- return exprinfos;
- }
-
exprinfo = (GroupExprInfo *) palloc(sizeof(GroupExprInfo));
exprinfo->expr = expr;
- exprinfo->varinfos = NIL;
-
- /*
- * If we already have a valid vardata, then we can just grab relation
- * from it. Otherwise we need to inspect the provided vars.
- */
- if (vardata)
- exprinfo->rel = vardata->rel;
- else
- {
- Bitmapset *varnos;
- Index varno;
-
- /*
- * Extract varno from the supplied vars.
- *
- * Expressions with vars from multiple relations should never get
- * here, thanks to the BMS_SINGLETON check in estimate_num_groups.
- * That is important e.g. for PlaceHolderVars, which might have
- * multiple varnos in the expression.
- */
- varnos = pull_varnos(root, (Node *) expr);
- Assert(bms_num_members(varnos) == 1);
-
- varno = bms_singleton_member(varnos);
- exprinfo->rel = root->simple_rel_array[varno];
- }
+ exprinfo->ndistinct = ndistinct;
+ exprinfo->rel = vardata->rel;
Assert(exprinfo->rel);
- /* Track vars for this expression. */
- foreach(lc, vars)
- {
- VariableStatData tmp;
- Node *var = (Node *) lfirst(lc);
-
- /* can we get no vardata for the variable? */
- examine_variable(root, var, 0, &tmp);
-
- exprinfo->varinfos
- = add_unique_group_var(root, exprinfo->varinfos, var, &tmp);
-
- ReleaseVariableStats(tmp);
- }
-
- /* without a list of variables, use the expression itself */
- if (vars == NIL)
- {
- Assert(vardata);
-
- exprinfo->varinfos
- = add_unique_group_var(root, exprinfo->varinfos,
- expr, vardata);
- }
-
return lappend(exprinfos, exprinfo);
}
@@ -3535,8 +3448,7 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
if (HeapTupleIsValid(vardata.statsTuple) || vardata.isunique)
{
exprinfos = add_unique_group_expr(root, exprinfos,
- groupexpr, NIL,
- &vardata);
+ groupexpr, &vardata);
ReleaseVariableStats(vardata);
continue;
@@ -3575,8 +3487,7 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
Node *var = (Node *) lfirst(l2);
examine_variable(root, var, 0, &vardata);
- exprinfos = add_unique_group_expr(root, exprinfos, var, NIL,
- &vardata);
+ exprinfos = add_unique_group_expr(root, exprinfos, var, &vardata);
ReleaseVariableStats(vardata);
}
}
@@ -3666,18 +3577,12 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
{
foreach(l, relexprinfos)
{
- ListCell *lc;
GroupExprInfo *exprinfo2 = (GroupExprInfo *) lfirst(l);
- foreach(lc, exprinfo2->varinfos)
- {
- GroupVarInfo *varinfo2 = (GroupVarInfo *) lfirst(lc);
-
- reldistinct *= varinfo2->ndistinct;
- if (relmaxndistinct < varinfo2->ndistinct)
- relmaxndistinct = varinfo2->ndistinct;
- relvarcount++;
- }
+ reldistinct *= exprinfo2->ndistinct;
+ if (relmaxndistinct < exprinfo2->ndistinct)
+ relmaxndistinct = exprinfo2->ndistinct;
+ relvarcount++;
}
/* we're done with this relation */
@@ -4036,7 +3941,6 @@ estimate_multivariate_ndistinct(PlannerInfo *root, RelOptInfo *rel,
ListCell *lc3;
GroupExprInfo *exprinfo = (GroupExprInfo *) lfirst(lc2);
AttrNumber attnum;
- bool found = false;
Assert(exprinfo->rel == rel);
@@ -4067,38 +3971,9 @@ estimate_multivariate_ndistinct(PlannerInfo *root, RelOptInfo *rel,
if (equal(exprinfo->expr, expr))
{
nshared_exprs++;
- found = true;
break;
}
}
-
- /*
- * If it's a complex expression, and we have found it in the
- * statistics object, we're done. Otherwise try to match the
- * varinfos we've extracted from the expression. That way we can
- * do at least some estimation.
- */
- if (found)
- continue;
-
- /* Inspect the individual Vars extracted from the expression. */
- foreach(lc3, exprinfo->varinfos)
- {
- GroupVarInfo *varinfo = (GroupVarInfo *) lfirst(lc3);
-
- if (IsA(varinfo->var, Var))
- {
- attnum = ((Var *) varinfo->var)->varattno;
-
- if (!AttrNumberIsForUserDefinedAttr(attnum))
- continue;
-
- if (bms_is_member(attnum, info->keys))
- nshared_vars++;
- }
-
- /* XXX What if it's not a Var? Probably can't do much. */
- }
}
if (nshared_vars + nshared_exprs < 2)
@@ -4161,55 +4036,46 @@ estimate_multivariate_ndistinct(PlannerInfo *root, RelOptInfo *rel,
GroupExprInfo *exprinfo = (GroupExprInfo *) lfirst(lc2);
- /* expression - see if it's in the statistics */
- idx = 0;
- foreach(lc3, matched_info->exprs)
+ /*
+ * Process a simple Var expression, by matching it to keys
+ * directly. If there's a matchine expression, we'll try
+ * matching it later.
+ */
+ if (IsA(exprinfo->expr, Var))
{
- Node *expr = (Node *) lfirst(lc3);
+ AttrNumber attnum = ((Var *) exprinfo->expr)->varattno;
- if (equal(exprinfo->expr, expr))
- {
- AttrNumber attnum = -(idx + 1);
+ /*
+ * Ignore expressions on system attributes. Can't rely on
+ * the bms check for negative values.
+ */
+ if (!AttrNumberIsForUserDefinedAttr(attnum))
+ continue;
- attnum = attnum + attnum_offset;
+ /* Is the variable covered by the statistics? */
+ if (!bms_is_member(attnum, matched_info->keys))
+ continue;
- /* ensure sufficient offset */
- Assert(AttrNumberIsForUserDefinedAttr(attnum));
+ attnum = attnum + attnum_offset;
- matched = bms_add_member(matched, attnum);
- found = true;
- break;
- }
+ /* ensure sufficient offset */
+ Assert(AttrNumberIsForUserDefinedAttr(attnum));
- idx++;
+ matched = bms_add_member(matched, attnum);
}
if (found)
continue;
- /*
- * Process the varinfos (this also handles regular attributes,
- * which have a GroupExprInfo with one varinfo.
- */
- foreach(lc3, exprinfo->varinfos)
+ /* expression - see if it's in the statistics */
+ idx = 0;
+ foreach(lc3, matched_info->exprs)
{
- GroupVarInfo *varinfo = (GroupVarInfo *) lfirst(lc3);
+ Node *expr = (Node *) lfirst(lc3);
- /* simple Var, search in statistics keys directly */
- if (IsA(varinfo->var, Var))
+ if (equal(exprinfo->expr, expr))
{
- AttrNumber attnum = ((Var *) varinfo->var)->varattno;
-
- /*
- * Ignore expressions on system attributes. Can't rely on
- * the bms check for negative values.
- */
- if (!AttrNumberIsForUserDefinedAttr(attnum))
- continue;
-
- /* Is the variable covered by the statistics? */
- if (!bms_is_member(attnum, matched_info->keys))
- continue;
+ AttrNumber attnum = -(idx + 1);
attnum = attnum + attnum_offset;
@@ -4217,7 +4083,10 @@ estimate_multivariate_ndistinct(PlannerInfo *root, RelOptInfo *rel,
Assert(AttrNumberIsForUserDefinedAttr(attnum));
matched = bms_add_member(matched, attnum);
+ break;
}
+
+ idx++;
}
}
@@ -4269,7 +4138,6 @@ estimate_multivariate_ndistinct(PlannerInfo *root, RelOptInfo *rel,
GroupExprInfo *exprinfo = (GroupExprInfo *) lfirst(lc);
ListCell *lc3;
bool found = false;
- List *varinfos;
/*
* Let's look at plain variables first, because it's the most
@@ -4327,69 +4195,7 @@ estimate_multivariate_ndistinct(PlannerInfo *root, RelOptInfo *rel,
if (found)
continue;
- /*
- * Look at the varinfo parts and filter the matched ones. This is
- * quite similar to processing of plain Vars above (the logic
- * evaluating them).
- *
- * XXX Maybe just removing the Var is not sufficient, and we
- * should "explode" the current GroupExprInfo into one element for
- * each Var? Consider for examle grouping by
- *
- * a, b, (a+c), d
- *
- * with extended stats on [a,b] and [(a+c), d]. If we apply the
- * [a,b] first, it will remove "a" from the (a+c) item, but then
- * we will estimate the whole expression again when applying
- * [(a+c), d]. But maybe it's better than failing to match the
- * second statistics?
- */
- varinfos = NIL;
- foreach(lc3, exprinfo->varinfos)
- {
- GroupVarInfo *varinfo = (GroupVarInfo *) lfirst(lc3);
- Var *var = (Var *) varinfo->var;
- AttrNumber attnum;
-
- /*
- * Could get expressions, not just plain Vars here. But we
- * don't know what to do about those, so just keep them.
- *
- * XXX Maybe we could inspect them recursively, somehow?
- */
- if (!IsA(varinfo->var, Var))
- {
- varinfos = lappend(varinfos, varinfo);
- continue;
- }
-
- attnum = var->varattno;
-
- /*
- * If it's a system attribute, we have to keep it. We don't
- * support extended statistics on system attributes, so it's
- * clearly not matched. Just add the varinfo and continue.
- */
- if (!AttrNumberIsForUserDefinedAttr(attnum))
- {
- varinfos = lappend(varinfos, varinfo);
- continue;
- }
-
- /* it's a user attribute, apply the same offset as above */
- attnum += attnum_offset;
-
- /* if it's not matched, keep the exprinfo */
- if (!bms_is_member(attnum, matched))
- varinfos = lappend(varinfos, varinfo);
- }
-
- /* remember the recalculated (filtered) list of varinfos */
- exprinfo->varinfos = varinfos;
-
- /* if there are no remaining varinfos for the item, skip it */
- if (varinfos)
- newlist = lappend(newlist, exprinfo);
+ newlist = lappend(newlist, exprinfo);
}
*exprinfos = newlist;
--
2.30.2
--------------F01142171AD1152B03477D21--
view thread (3+ 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]
Subject: Re: [PATCH 3/4] simplify ndistinct
In-Reply-To: <no-message-id-171429@localhost>
* 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