diff --git a/src/backend/statistics/dependencies.c b/src/backend/statistics/dependencies.c new file mode 100644 index 72dc1cd..e0cc2b9 --- a/src/backend/statistics/dependencies.c +++ b/src/backend/statistics/dependencies.c @@ -30,6 +30,7 @@ #include "utils/fmgroids.h" #include "utils/fmgrprotos.h" #include "utils/lsyscache.h" +#include "utils/selfuncs.h" #include "utils/syscache.h" #include "utils/typcache.h" @@ -73,8 +74,6 @@ static double dependency_degree(int numr AttrNumber *dependency, VacAttrStats **stats, Bitmapset *attrs); static bool dependency_is_fully_matched(MVDependency *dependency, Bitmapset *attnums); -static bool dependency_implies_attribute(MVDependency *dependency, - AttrNumber attnum); static bool dependency_is_compatible_clause(Node *clause, Index relid, AttrNumber *attnum); static MVDependency *find_strongest_dependency(MVDependencies **dependencies, @@ -614,19 +613,6 @@ dependency_is_fully_matched(MVDependency } /* - * dependency_implies_attribute - * check that the attnum matches is implied by the functional dependency - */ -static bool -dependency_implies_attribute(MVDependency *dependency, AttrNumber attnum) -{ - if (attnum == dependency->attributes[dependency->nattributes - 1]) - return true; - - return false; -} - -/* * statext_dependencies_load * Load the functional dependencies for the indicated pg_statistic_ext tuple */ @@ -966,7 +952,7 @@ find_strongest_dependency(MVDependencies * between them, i.e. either (a=>b) or (b=>a). Assuming (a=>b) is the selected * dependency, we then combine the per-clause selectivities using the formula * - * P(a,b) = P(a) * [f + (1-f)*P(b)] + * P(a,b) = f * Min(P(a), P(b)) + (1-f) * P(a) * P(b) * * where 'f' is the degree of the dependency. * @@ -974,7 +960,7 @@ find_strongest_dependency(MVDependencies * recursively, starting with the widest/strongest dependencies. For example * P(a,b,c) is first split like this: * - * P(a,b,c) = P(a,b) * [f + (1-f)*P(c)] + * P(a,b,c) = f * Min(P(a,b), P(c)) + (1-f) * P(a,b) * P(c) * * assuming (a,b=>c) is the strongest dependency. */ @@ -987,20 +973,27 @@ dependencies_clauselist_selectivity(Plan RelOptInfo *rel, Bitmapset **estimatedclauses) { - Selectivity s1 = 1.0; + Selectivity s1; ListCell *l; - Bitmapset *clauses_attnums = NULL; - Bitmapset **list_attnums; + Bitmapset *clauses_attnums; + AttrNumber *list_attnums; int listidx; - MVDependencies **dependencies = NULL; - int ndependencies = 0; + MVDependencies **dependencies; + int ndependencies; + int total_ndeps; + MVDependency **dependencies_used; + int ndependencies_used; + Bitmapset *attrs_used; + int nattrs_used; + Selectivity *attr_sel; int i; + int attidx; /* check if there's any stats that might be useful for us. */ if (!has_stats_of_kind(rel->statlist, STATS_EXT_DEPENDENCIES)) return 1.0; - list_attnums = (Bitmapset **) palloc(sizeof(Bitmapset *) * + list_attnums = (AttrNumber *) palloc(sizeof(AttrNumber) * list_length(clauses)); /* @@ -1014,6 +1007,7 @@ dependencies_clauselist_selectivity(Plan * We also skip clauses that we already estimated using different types of * statistics (we treat them as incompatible). */ + clauses_attnums = NULL; listidx = 0; foreach(l, clauses) { @@ -1023,11 +1017,11 @@ dependencies_clauselist_selectivity(Plan if (!bms_is_member(listidx, *estimatedclauses) && dependency_is_compatible_clause(clause, rel->relid, &attnum)) { - list_attnums[listidx] = bms_make_singleton(attnum); + list_attnums[listidx] = attnum; clauses_attnums = bms_add_member(clauses_attnums, attnum); } else - list_attnums[listidx] = NULL; + list_attnums[listidx] = InvalidAttrNumber; listidx++; } @@ -1039,6 +1033,7 @@ dependencies_clauselist_selectivity(Plan */ if (bms_num_members(clauses_attnums) < 2) { + bms_free(clauses_attnums); pfree(list_attnums); return 1.0; } @@ -1055,6 +1050,7 @@ dependencies_clauselist_selectivity(Plan * to moving the freed chunks to freelists etc. */ ndependencies = 0; + total_ndeps = 0; dependencies = (MVDependencies **) palloc(sizeof(MVDependencies *) * list_length(rel->statlist)); @@ -1076,104 +1072,185 @@ dependencies_clauselist_selectivity(Plan if (num_matched < 2) continue; - dependencies[ndependencies++] + dependencies[ndependencies] = statext_dependencies_load(stat->statOid); + + total_ndeps += dependencies[ndependencies]->ndeps; + ndependencies++; } /* if no matching stats could be found then we've nothing to do */ if (!ndependencies) { + pfree(dependencies); + bms_free(clauses_attnums); pfree(list_attnums); return 1.0; } /* - * Apply the dependencies recursively, starting with the widest/strongest - * ones, and proceeding to the smaller/weaker ones. At the end of each - * round we factor in the selectivity of clauses on the implied attribute, - * and remove the clauses from the list. + * Work out which dependencies we can apply, starting with the + * widest/stongest ones, and proceeding to smaller/weaker ones. */ + ndependencies_used = 0; + dependencies_used = (MVDependency **) palloc(sizeof(MVDependency *) * + total_ndeps); + + attrs_used = NULL; + while (true) { - Selectivity s2 = 1.0; MVDependency *dependency; + AttrNumber attnum; - /* the widest/strongest dependency, fully matched by clauses */ + /* The widest/strongest dependency, fully matched by clauses */ dependency = find_strongest_dependency(dependencies, ndependencies, clauses_attnums); - - /* if no suitable dependency was found, we're done */ if (!dependency) break; + dependencies_used[ndependencies_used++] = dependency; + + /* Track all attributes used */ + for (i = 0; i < dependency->nattributes; i++) + { + attnum = dependency->attributes[i]; + attrs_used = bms_add_member(attrs_used, attnum); + } + /* - * We found an applicable dependency, so find all the clauses on the - * implied attribute - with dependency (a,b => c) we look for clauses - * on 'c'. + * Ignore dependencies involving the implied attribute in later loops. */ + clauses_attnums = bms_del_member(clauses_attnums, attnum); + } + + if (!ndependencies_used) + { + bms_free(attrs_used); + pfree(dependencies_used); + pfree(dependencies); + bms_free(clauses_attnums); + pfree(list_attnums); + return 1.0; + } + + /* + * For each attribute used in the dependencies to be applied, compute the + * single-column selectivity of all the clauses using that attribute, and + * mark all those clauses as having been estimated. + */ + nattrs_used = bms_num_members(attrs_used); + attr_sel = (Selectivity *) palloc(sizeof(Selectivity) * nattrs_used); + + attidx = 0; + i = -1; + while ((i = bms_next_member(attrs_used, i)) >= 0) + { + List *attr_clauses = NIL; + Selectivity simple_sel; + listidx = -1; foreach(l, clauses) { - Node *clause; - AttrNumber attnum; + Node *clause = (Node *) lfirst(l); listidx++; - - /* - * Skip incompatible clauses, and ones we've already estimated on. - */ - if (!list_attnums[listidx]) - continue; - - /* - * We expect the bitmaps ton contain a single attribute number. - */ - attnum = bms_singleton_member(list_attnums[listidx]); - - /* - * Technically we could find more than one clause for a given - * attnum. Since these clauses must be equality clauses, we choose - * to only take the selectivity estimate from the final clause in - * the list for this attnum. If the attnum happens to be compared - * to a different Const in another clause then no rows will match - * anyway. If it happens to be compared to the same Const, then - * ignoring the additional clause is just the thing to do. - */ - if (dependency_implies_attribute(dependency, attnum)) + if (list_attnums[listidx] == i) { - clause = (Node *) lfirst(l); + attr_clauses = lappend(attr_clauses, clause); + *estimatedclauses = bms_add_member(*estimatedclauses, listidx); + } + } - s2 = clause_selectivity(root, clause, varRelid, jointype, - sjinfo); + simple_sel = clauselist_selectivity_simple(root, attr_clauses, varRelid, + jointype, sjinfo, NULL); + attr_sel[attidx++] = simple_sel; + } - /* mark this one as done, so we don't touch it again. */ - *estimatedclauses = bms_add_member(*estimatedclauses, listidx); + /* + * Now combine these selectivities using the dependency information. For + * chains of dependencies such as a -> b -> c, the b -> c dependency will + * come before the a -> b dependency in the array, so we traverse the + * array backwards to ensure such chains are computed in the right order. + * + * Pairs of selectivities for attributes with dependencies are combined + * using the formula + * + * P(a,b) = f * Min(P(a), P(b)) + (1-f) * P(a) * P(b) + * + * where 'f' is the degree of validity of the dependency. This ensures + * that the combined selectivity is never greater than either individual + * selectivity. + * + * Where multiple dependencies apply (e.g., a -> b -> c), we use + * conditional probabilities to compute the overall result as follows: + * + * P(a,b,c) = P(c|a,b) * P(a,b) = P(c|a,b) * P(b|a) * P(a) + * + * so we replace the probabilities of all implied attributes with + * conditional probabilities, conditional on all their implying + * attributes. The probabilities of all other non-implied attributes are + * left as they are. + */ + for (i = ndependencies_used-1; i >= 0; i--) + { + MVDependency *dependency = dependencies_used[i]; + int j; + AttrNumber attnum; + Selectivity s2; + double f; - /* - * Mark that we've got and used the dependency on this clause. - * We'll want to ignore this when looking for the next - * strongest dependency above. - */ - clauses_attnums = bms_del_member(clauses_attnums, attnum); - } + /* Selectivity of all the implying attributes */ + s1 = 1.0; + for (j = 0; j < dependency->nattributes - 1; j++) + { + attnum = dependency->attributes[j]; + attidx = bms_member_index(attrs_used, attnum); + s1 *= attr_sel[attidx]; } + /* Original selectivity of the implied attribute */ + attnum = dependency->attributes[j]; + attidx = bms_member_index(attrs_used, attnum); + s2 = attr_sel[attidx]; + /* - * Now factor in the selectivity for all the "implied" clauses into - * the final one, using this formula: + * Replace s2 with the conditional probability s2 given s1, computed + * using the formula P(b|a) = P(a,b) / P(a), which simplifies to * - * P(a,b) = P(a) * (f + (1-f) * P(b)) + * P(b|a) = f * Min(P(a), P(b)) / P(a) + (1-f) * P(b) * - * where 'f' is the degree of validity of the dependency. + * where P(a) = s1, the selectivity of the implying attributes, and + * P(b) = s2, the selectivity of the implied attribute. */ - s1 *= (dependency->degree + (1 - dependency->degree) * s2); + f = dependency->degree; + + if (s1 <= s2) + attr_sel[attidx] = f + (1 - f) * s2; + else + attr_sel[attidx] = f * s2 / s1 + (1 -f) * s2; } + /* + * The overall selectivity of all the clauses on all these attributes is + * then the product of all the original (non-implied) and conditional + * (implied) probabilities. + */ + s1 = 1.0; + for (i = 0; i < nattrs_used; i++) + s1 *= attr_sel[i]; + + CLAMP_PROBABILITY(s1); + /* free deserialized functional dependencies (and then the array) */ for (i = 0; i < ndependencies; i++) pfree(dependencies[i]); + pfree(attr_sel); + bms_free(attrs_used); + pfree(dependencies_used); pfree(dependencies); + bms_free(clauses_attnums); pfree(list_attnums); return s1; diff --git a/src/test/regress/expected/stats_ext.out b/src/test/regress/expected/stats_ext.out new file mode 100644 index dbc2532..f96e651 --- a/src/test/regress/expected/stats_ext.out +++ b/src/test/regress/expected/stats_ext.out @@ -440,6 +440,12 @@ SELECT * FROM check_estimated_rows('SELE 8 | 200 (1 row) +SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 2, 51, 52) AND b = ''1'''); + estimated | actual +-----------+-------- + 4 | 100 +(1 row) + SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 26, 51, 76) AND b IN (''1'', ''26'') AND c = 1'); estimated | actual -----------+-------- @@ -574,6 +580,12 @@ SELECT * FROM check_estimated_rows('SELE 200 | 200 (1 row) +SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 2, 51, 52) AND b = ''1'''); + estimated | actual +-----------+-------- + 100 | 100 +(1 row) + SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 26, 51, 76) AND b IN (''1'', ''26'') AND c = 1'); estimated | actual -----------+-------- @@ -667,12 +679,14 @@ SELECT * FROM check_estimated_rows('SELE 1 | 0 (1 row) --- check change of column type doesn't break it +-- changing the type of column c causes its single-column stats to be dropped, +-- giving a default estimate of 0.005 * 5000 = 25 for (c = 1); check multiple +-- clauses estimated with functional dependencies does not exceed this ALTER TABLE functional_dependencies ALTER COLUMN c TYPE numeric; SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a = 1 AND b = ''1'' AND c = 1'); estimated | actual -----------+-------- - 50 | 50 + 25 | 50 (1 row) ANALYZE functional_dependencies; diff --git a/src/test/regress/sql/stats_ext.sql b/src/test/regress/sql/stats_ext.sql new file mode 100644 index 8beb042..203d38d --- a/src/test/regress/sql/stats_ext.sql +++ b/src/test/regress/sql/stats_ext.sql @@ -280,6 +280,8 @@ SELECT * FROM check_estimated_rows('SELE SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 2, 51, 52) AND b IN (''1'', ''2'')'); +SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 2, 51, 52) AND b = ''1'''); + SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 26, 51, 76) AND b IN (''1'', ''26'') AND c = 1'); SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 26, 51, 76) AND b IN (''1'', ''26'') AND c IN (1)'); @@ -332,6 +334,8 @@ SELECT * FROM check_estimated_rows('SELE SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 2, 51, 52) AND b IN (''1'', ''2'')'); +SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 2, 51, 52) AND b = ''1'''); + SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 26, 51, 76) AND b IN (''1'', ''26'') AND c = 1'); SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 26, 51, 76) AND b IN (''1'', ''26'') AND c IN (1)'); @@ -365,7 +369,9 @@ SELECT * FROM check_estimated_rows('SELE SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a IN (1, 2, 51, 52) AND b = ALL (ARRAY[''1'', ''2''])'); --- check change of column type doesn't break it +-- changing the type of column c causes its single-column stats to be dropped, +-- giving a default estimate of 0.005 * 5000 = 25 for (c = 1); check multiple +-- clauses estimated with functional dependencies does not exceed this ALTER TABLE functional_dependencies ALTER COLUMN c TYPE numeric; SELECT * FROM check_estimated_rows('SELECT * FROM functional_dependencies WHERE a = 1 AND b = ''1'' AND c = 1');