From: Tomas Vondra Date: Thu, 25 Mar 2021 00:00:31 +0100 Subject: [PATCH 3/4] simplify ndistinct --- 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--