New version of patch implicitly adding multicolumn statistic in
auto_explain extension and using it in optimizer for more precise
estimation of join selectivity.
This patch fixes race condition while adding statistics and restricts
generated statistic name to fit in 64 bytes (NameData).
--
Konstantin Knizhnik
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
diff --git a/contrib/auto_explain/auto_explain.c b/contrib/auto_explain/auto_explain.c
index a9536c2..3f9d6ef 100644
--- a/contrib/auto_explain/auto_explain.c
+++ b/contrib/auto_explain/auto_explain.c
@@ -13,12 +13,32 @@
#include "postgres.h"
#include <limits.h>
+#include <math.h>
+#include "access/hash.h"
#include "access/parallel.h"
+#include "access/relscan.h"
+#include "access/skey.h"
+#include "access/table.h"
+#include "access/tableam.h"
+#include "catalog/pg_statistic_ext.h"
#include "commands/explain.h"
+#include "commands/defrem.h"
#include "executor/instrument.h"
#include "jit/jit.h"
+#include "nodes/makefuncs.h"
+#include "nodes/nodeFuncs.h"
+#include "optimizer/cost.h"
+#include "optimizer/optimizer.h"
+#include "optimizer/planmain.h"
+#include "parser/parsetree.h"
+#include "storage/ipc.h"
+#include "statistics/statistics.h"
+#include "utils/fmgroids.h"
#include "utils/guc.h"
+#include "utils/syscache.h"
+#include "utils/lsyscache.h"
+#include "utils/ruleutils.h"
PG_MODULE_MAGIC;
@@ -33,7 +53,9 @@ static bool auto_explain_log_settings = false;
static int auto_explain_log_format = EXPLAIN_FORMAT_TEXT;
static int auto_explain_log_level = LOG;
static bool auto_explain_log_nested_statements = false;
+static bool auto_explain_suggest_only = false;
static double auto_explain_sample_rate = 1;
+static double auto_explain_add_statistics_threshold = 0.0;
static const struct config_enum_entry format_options[] = {
{"text", EXPLAIN_FORMAT_TEXT, false},
@@ -218,6 +240,30 @@ _PG_init(void)
NULL,
NULL);
+ DefineCustomRealVariable("auto_explain.add_statistics_threshold",
+ "Sets the threshold for actual/estimated #rows ratio triggering creation of multicolumn statistic for the related columns.",
+ "Zero disables implicit creation of multicolumn statistic.",
+ &auto_explain_add_statistics_threshold,
+ 0.0,
+ 0.0,
+ INT_MAX,
+ PGC_SUSET,
+ 0,
+ NULL,
+ NULL,
+ NULL);
+
+ DefineCustomBoolVariable("auto_explain.suggest_only",
+ "Do not create statistic but just record in WAL suggested create statistics statement.",
+ NULL,
+ &auto_explain_suggest_only,
+ false,
+ PGC_SUSET,
+ 0,
+ NULL,
+ NULL,
+ NULL);
+
EmitWarningsOnPlaceholders("auto_explain");
/* Install hooks. */
@@ -353,6 +399,256 @@ explain_ExecutorFinish(QueryDesc *queryDesc)
PG_END_TRY();
}
+static void
+AddMultiColumnStatisticsForNode(PlanState *planstate, ExplainState *es);
+
+static void
+AddMultiColumnStatisticsForSubPlans(List *plans, ExplainState *es)
+{
+ ListCell *lst;
+
+ foreach(lst, plans)
+ {
+ SubPlanState *sps = (SubPlanState *) lfirst(lst);
+
+ AddMultiColumnStatisticsForNode(sps->planstate, es);
+ }
+}
+
+static void
+AddMultiColumnStatisticsForMemberNodes(PlanState **planstates, int nsubnodes,
+ ExplainState *es)
+{
+ int j;
+
+ for (j = 0; j < nsubnodes; j++)
+ AddMultiColumnStatisticsForNode(planstates[j], es);
+}
+
+static int
+vars_list_comparator(const ListCell *a, const ListCell *b)
+{
+ char* va = strVal((Value *) linitial(((ColumnRef *)lfirst(a))->fields));
+ char* vb = strVal((Value *) linitial(((ColumnRef *)lfirst(b))->fields));
+ return strcmp(va, vb);
+}
+
+static void
+AddMultiColumnStatisticsForQual(void* qual, ExplainState *es)
+{
+ List *vars = NULL;
+ ListCell* lc;
+
+ foreach (lc, qual)
+ {
+ Node* node = (Node*)lfirst(lc);
+ if (IsA(node, RestrictInfo))
+ node = (Node*)((RestrictInfo*)node)->clause;
+ vars = list_concat(vars, pull_vars_of_level(node, 0));
+ }
+ while (vars != NULL)
+ {
+ ListCell *cell;
+ List *cols = NULL;
+ Index varno = 0;
+ Bitmapset* colmap = NULL;
+
+ foreach (cell, vars)
+ {
+ Node* node = (Node *) lfirst(cell);
+ if (IsA(node, Var))
+ {
+ Var *var = (Var *) node;
+ if (cols == NULL || var->varnoold == varno)
+ {
+ varno = var->varnoold;
+ if (var->varoattno > 0 &&
+ !bms_is_member(var->varoattno, colmap) &&
+ varno >= 1 &&
+ varno <= list_length(es->rtable) &&
+ list_length(cols) < STATS_MAX_DIMENSIONS)
+ {
+ RangeTblEntry *rte = rt_fetch(varno, es->rtable);
+ if (rte->rtekind == RTE_RELATION)
+ {
+ ColumnRef *col = makeNode(ColumnRef);
+ char *colname = get_rte_attribute_name(rte, var->varoattno);
+ col->fields = list_make1(makeString(colname));
+ cols = lappend(cols, col);
+ colmap = bms_add_member(colmap, var->varoattno);
+ }
+ }
+ }
+ else
+ {
+ continue;
+ }
+ }
+ vars = foreach_delete_current(vars, cell);
+ }
+ if (list_length(cols) >= 2)
+ {
+ RangeTblEntry *rte = rt_fetch(varno, es->rtable);
+ CreateStatsStmt* stats = makeNode(CreateStatsStmt);
+ char *rel_namespace = get_namespace_name(get_rel_namespace(rte->relid));
+ char *rel_name = get_rel_name(rte->relid);
+ RangeVar* rel = makeRangeVar(rel_namespace, rel_name, 0);
+ char* stat_name = rel_name;
+ char* create_stat_stmt = (char*)"";
+ char const* sep = "ON";
+ ScanKeyData entry[2];
+ TableScanDesc scan;
+ Relation stat_rel;
+ size_t name_len;
+ TupleTableSlot *slot;
+
+ list_sort(cols, vars_list_comparator);
+ /* Construct name for statistic by concatenating relation name with all columns */
+ foreach (cell, cols)
+ {
+ char* col_name = strVal((Value *) linitial(((ColumnRef *)lfirst(cell))->fields));
+ stat_name = psprintf("%s_%s", stat_name, col_name);
+ create_stat_stmt = psprintf("%s%s %s", create_stat_stmt, sep, col_name);
+ sep = ",";
+ }
+
+ name_len = strlen(stat_name);
+ if (name_len >= NAMEDATALEN)
+ stat_name = psprintf("%.*s_%08x", NAMEDATALEN - 10, stat_name, (unsigned)hash_any((uint8*)stat_name, name_len));
+
+ ScanKeyInit(&entry[0],
+ Anum_pg_statistic_ext_stxname,
+ BTEqualStrategyNumber, F_NAMEEQ,
+ CStringGetDatum(stat_name));
+ ScanKeyInit(&entry[1],
+ Anum_pg_statistic_ext_stxnamespace,
+ BTEqualStrategyNumber, F_OIDEQ,
+ ObjectIdGetDatum(get_rel_namespace(rte->relid)));
+
+ /*
+ * Prevent concurrent access to extended statistic table
+ */
+ stat_rel = table_open(StatisticExtRelationId, AccessExclusiveLock);
+ slot = table_slot_create(stat_rel, NULL);
+ scan = table_beginscan_catalog(stat_rel, 2, entry);
+
+ /*
+ * Check if multicolumn statistic object with such name already exists.
+ * Most likely if was already created by auto_explain, but either ANALYZE was not performed since
+ * this time, either presence of this multicolumn statistic doesn't help to provide more precise estimation.
+ * Despite to the fact that we create statistics with "if_not_exist" option, presence of such check
+ * allows to eliminate notice message that statistics object already exists.
+ */
+ if (!table_scan_getnextslot(scan, ForwardScanDirection, slot))
+ {
+ if (auto_explain_suggest_only)
+ {
+ elog(NOTICE, "Auto_explain suggestion: CREATE STATISTICS %s %s FROM %s", stat_name, create_stat_stmt, rel_name);
+ }
+ else
+ {
+ elog(LOG, "Add statistics %s", stat_name);
+ stats->defnames = list_make2(makeString(rel_namespace), makeString(stat_name));
+ stats->if_not_exists = true;
+ stats->relations = list_make1(rel);
+ stats->exprs = cols;
+ CreateStatistics(stats);
+ }
+ }
+ table_close(stat_rel, AccessExclusiveLock);
+ }
+ }
+}
+
+static void
+AddMultiColumnStatisticsForNode(PlanState *planstate, ExplainState *es)
+{
+ Plan *plan = planstate->plan;
+
+ if (planstate->instrument && plan->plan_rows != 0)
+ {
+ if (auto_explain_add_statistics_threshold != 0
+ && planstate->instrument->ntuples / plan->plan_rows >= auto_explain_add_statistics_threshold)
+ {
+ elog(DEBUG1, "Estimated=%f, actual=%f, error=%f: plan=%s", plan->plan_rows, planstate->instrument->ntuples, planstate->instrument->ntuples / plan->plan_rows, nodeToString(plan));
+ /* quals, sort keys, etc */
+ switch (nodeTag(plan))
+ {
+ case T_IndexScan:
+ AddMultiColumnStatisticsForQual(((IndexScan *) plan)->indexqualorig, es);
+ break;
+ case T_IndexOnlyScan:
+ AddMultiColumnStatisticsForQual(((IndexOnlyScan *) plan)->indexqual, es);
+ break;
+ case T_BitmapIndexScan:
+ AddMultiColumnStatisticsForQual(((BitmapIndexScan *) plan)->indexqualorig, es);
+ break;
+ case T_NestLoop:
+ AddMultiColumnStatisticsForQual(((NestLoop *) plan)->join.joinqual, es);
+ break;
+ case T_MergeJoin:
+ AddMultiColumnStatisticsForQual(((MergeJoin *) plan)->mergeclauses, es);
+ AddMultiColumnStatisticsForQual(((MergeJoin *) plan)->join.joinqual, es);
+ break;
+ case T_HashJoin:
+ AddMultiColumnStatisticsForQual(((HashJoin *) plan)->hashclauses, es);
+ AddMultiColumnStatisticsForQual(((HashJoin *) plan)->join.joinqual, es);
+ break;
+ default:
+ break;
+ }
+ AddMultiColumnStatisticsForQual(plan->qual, es);
+ }
+ }
+
+ /* initPlan-s */
+ if (planstate->initPlan)
+ AddMultiColumnStatisticsForSubPlans(planstate->initPlan, es);
+
+ /* lefttree */
+ if (outerPlanState(planstate))
+ AddMultiColumnStatisticsForNode(outerPlanState(planstate), es);
+
+ /* righttree */
+ if (innerPlanState(planstate))
+ AddMultiColumnStatisticsForNode(innerPlanState(planstate), es);
+
+ /* special child plans */
+ switch (nodeTag(plan))
+ {
+ case T_ModifyTable:
+ AddMultiColumnStatisticsForMemberNodes(((ModifyTableState *) planstate)->mt_plans,
+ ((ModifyTableState *) planstate)->mt_nplans,
+ es);
+ break;
+ case T_Append:
+ AddMultiColumnStatisticsForMemberNodes(((AppendState *) planstate)->appendplans,
+ ((AppendState *) planstate)->as_nplans,
+ es);
+ break;
+ case T_MergeAppend:
+ AddMultiColumnStatisticsForMemberNodes(((MergeAppendState *) planstate)->mergeplans,
+ ((MergeAppendState *) planstate)->ms_nplans,
+ es);
+ break;
+ case T_BitmapAnd:
+ AddMultiColumnStatisticsForMemberNodes(((BitmapAndState *) planstate)->bitmapplans,
+ ((BitmapAndState *) planstate)->nplans,
+ es);
+ break;
+ case T_BitmapOr:
+ AddMultiColumnStatisticsForMemberNodes(((BitmapOrState *) planstate)->bitmapplans,
+ ((BitmapOrState *) planstate)->nplans,
+ es);
+ break;
+ case T_SubqueryScan:
+ AddMultiColumnStatisticsForNode(((SubqueryScanState *) planstate)->subplan, es);
+ break;
+ default:
+ break;
+ }
+}
+
/*
* ExecutorEnd hook: log results if needed
*/
@@ -392,6 +688,10 @@ explain_ExecutorEnd(QueryDesc *queryDesc)
ExplainPrintJITSummary(es, queryDesc);
ExplainEndOutput(es);
+ /* Add multicolumn statistic if requested */
+ if (auto_explain_add_statistics_threshold && !IsParallelWorker())
+ AddMultiColumnStatisticsForNode(queryDesc->planstate, es);
+
/* Remove last line break */
if (es->str->len > 0 && es->str->data[es->str->len - 1] == '\n')
es->str->data[--es->str->len] = '\0';
diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c
index 4bf777d..085defe 100644
--- a/src/backend/optimizer/path/clausesel.c
+++ b/src/backend/optimizer/path/clausesel.c
@@ -25,6 +25,7 @@
#include "utils/lsyscache.h"
#include "utils/selfuncs.h"
#include "statistics/statistics.h"
+#include "catalog/pg_statistic_ext.h"
/*
@@ -106,6 +107,47 @@ clauselist_selectivity(PlannerInfo *root,
}
/*
+ * Find functional dependency between attributes using multicolumn statistic.
+ * relid: index of relation to which all considered attributes belong
+ * var: variable which dependencies are inspected
+ * attnums: set of considered attributes included specified variables
+ * This function return degree of strongest dependency between some subset of this attributes
+ * and specified variable or 0.0 if on dependency is found.
+ */
+double
+find_var_dependency(PlannerInfo *root, Index relid, Var *var, Bitmapset *attnums)
+{
+ RelOptInfo* rel = find_base_rel(root, relid);
+ if (rel->rtekind == RTE_RELATION && rel->statlist != NIL)
+ {
+ StatisticExtInfo *stat = choose_best_statistics(rel->statlist, attnums,
+ STATS_EXT_DEPENDENCIES);
+ if (stat != NULL)
+ {
+ MVDependencies *dependencies = statext_dependencies_load(stat->statOid);
+ MVDependency *strongest = NULL;
+ int i;
+ for (i = 0; i < dependencies->ndeps; i++)
+ {
+ MVDependency *dependency = dependencies->deps[i];
+ int n_dep_vars = dependency->nattributes - 1;
+ /* Dependency implies attribute */
+ if (var->varattno == dependency->attributes[n_dep_vars])
+ {
+ while (--n_dep_vars >= 0
+ && bms_is_member(dependency->attributes[n_dep_vars], attnums));
+ if (n_dep_vars < 0 && (!strongest || strongest->degree < dependency->degree))
+ strongest = dependency;
+ }
+ }
+ if (strongest)
+ return strongest->degree;
+ }
+ }
+ return 0.0;
+}
+
+/*
* clauselist_selectivity_simple -
* Compute the selectivity of an implicitly-ANDed list of boolean
* expression clauses. The list can be empty, in which case 1.0
@@ -159,6 +201,9 @@ clauselist_selectivity_simple(PlannerInfo *root,
RangeQueryClause *rqlist = NULL;
ListCell *l;
int listidx;
+ Bitmapset *clauses_attnums = NULL;
+ int n_clauses_attnums = 0;
+ int innerRelid = varRelid;
/*
* If there's exactly one clause (and it was not estimated yet), just go
@@ -170,6 +215,9 @@ clauselist_selectivity_simple(PlannerInfo *root,
return clause_selectivity(root, (Node *) linitial(clauses),
varRelid, jointype, sjinfo);
+ if (innerRelid == 0 && sjinfo)
+ bms_get_singleton_member(sjinfo->min_righthand, &innerRelid);
+
/*
* Anything that doesn't look like a potential rangequery clause gets
* multiplied into s1 and forgotten. Anything that does gets inserted into
@@ -181,7 +229,6 @@ clauselist_selectivity_simple(PlannerInfo *root,
Node *clause = (Node *) lfirst(l);
RestrictInfo *rinfo;
Selectivity s2;
-
listidx++;
/*
@@ -213,6 +260,7 @@ clauselist_selectivity_simple(PlannerInfo *root,
else
rinfo = NULL;
+
/*
* See if it looks like a restriction clause with a pseudoconstant on
* one side. (Anything more complicated than that might not behave in
@@ -224,6 +272,30 @@ clauselist_selectivity_simple(PlannerInfo *root,
OpExpr *expr = (OpExpr *) clause;
bool varonleft = true;
bool ok;
+ int oprrest = get_oprrest(expr->opno);
+
+ /* Try to take in account functional dependencies between attributes */
+ if (oprrest == F_EQSEL && rinfo != NULL && innerRelid != 0)
+ {
+ Var* var = (Var*)linitial(expr->args);
+ if (!IsA(var, Var) || var->varnoold != innerRelid)
+ {
+ var = (Var*)lsecond(expr->args);
+ }
+ if (IsA(var, Var) && var->varattno >= 0 && var->varnoold == innerRelid)
+ {
+ clauses_attnums = bms_add_member(clauses_attnums, var->varattno);
+ if (n_clauses_attnums++ != 0)
+ {
+ double dep = find_var_dependency(root, innerRelid, var, clauses_attnums);
+ if (dep != 0.0)
+ {
+ s1 *= dep + (1 - dep) * s2;
+ continue;
+ }
+ }
+ }
+ }
if (rinfo)
{
@@ -249,7 +321,7 @@ clauselist_selectivity_simple(PlannerInfo *root,
* selectivity in generically. But if it's the right oprrest,
* add the clause to rqlist for later processing.
*/
- switch (get_oprrest(expr->opno))
+ switch (oprrest)
{
case F_SCALARLTSEL:
case F_SCALARLESEL:
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index c5f6593..f6714e4 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -4543,6 +4543,30 @@ get_parameterized_joinrel_size(PlannerInfo *root, RelOptInfo *rel,
return nrows;
}
+
+/*
+ * Try to find dependency between variables.
+ * var: varaibles which dependencies are considered
+ * join_vars: list of variables used in other clauses
+ * This functions return strongest dependency and some subset of variables from the same relation
+ * or 0.0 if no dependency was found.
+ */
+static double
+var_depends_on(PlannerInfo *root, Var* var, List* clause_vars)
+{
+ ListCell* lc;
+ Bitmapset *attnums = NULL;
+ Index relid = var->varnoold;
+
+ foreach (lc, clause_vars)
+ {
+ Var* join_var = (Var*)lfirst(lc);
+ if (join_var->varnoold == relid && join_var->varattno >= 0)
+ attnums = bms_add_member(attnums, join_var->varattno);
+ }
+ return attnums ? find_var_dependency(root, relid, var, bms_add_member(attnums, var->varattno)) : 0.0;
+}
+
/*
* calc_joinrel_size_estimate
* Workhorse for set_joinrel_size_estimates and
@@ -4639,6 +4663,39 @@ calc_joinrel_size_estimate(PlannerInfo *root,
pselec = 0.0; /* not used, keep compiler quiet */
}
+ /* Try to take in account functional dependencies between attributes of clauses pushed-down to joined relations and
+ * retstrictlist clause. Right now we consider only case of restrictlist consists of one clause.
+ */
+ if (list_length(restrictlist) == 1)
+ {
+ RestrictInfo* rinfo = linitial(restrictlist);
+ Expr* clause = rinfo->clause;
+
+ Assert(IsA(rinfo, RestrictInfo));
+
+ if (is_opclause(clause))
+ {
+ OpExpr *expr = (OpExpr *) clause;
+ ListCell* lc;
+ List* join_vars = NULL;
+
+ /* Get list of all attributes in pushed-down clauses */
+ foreach (lc, outer_rel->baserestrictinfo)
+ join_vars = list_concat(join_vars, pull_vars_of_level((Node*)((RestrictInfo*)lfirst(lc))->clause, 0));
+ foreach (lc, inner_rel->baserestrictinfo)
+ join_vars = list_concat(join_vars, pull_vars_of_level((Node*)((RestrictInfo*)lfirst(lc))->clause, 0));
+
+ foreach (lc, expr->args)
+ {
+ Var *var = (Var*) lfirst(lc);
+ if (IsA(var, Var) && var->varattno >= 0)
+ {
+ double dep = var_depends_on(root, var, join_vars);
+ jselec = jselec*(1.0 - dep) + dep;
+ }
+ }
+ }
+ }
/*
* Basically, we multiply size of Cartesian product by selectivity.
*
diff --git a/src/include/optimizer/clauses.h b/src/include/optimizer/clauses.h
index 2f9aeec..09ff0c4 100644
--- a/src/include/optimizer/clauses.h
+++ b/src/include/optimizer/clauses.h
@@ -55,4 +55,6 @@ extern void CommuteOpExpr(OpExpr *clause);
extern Query *inline_set_returning_function(PlannerInfo *root,
RangeTblEntry *rte);
+extern double find_var_dependency(PlannerInfo *root, Index relid, Var *var, Bitmapset *attnums);
+
#endif /* CLAUSES_H */
