public inbox for [email protected]help / color / mirror / Atom feed
[PATCH 5/5] WIP unify handling of attributes and expressions 5+ messages / 3 participants [nested] [flat]
* [PATCH 5/5] WIP unify handling of attributes and expressions @ 2021-03-04 03:53 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 5+ messages in thread From: Tomas Vondra @ 2021-03-04 03:53 UTC (permalink / raw) --- src/backend/statistics/dependencies.c | 82 ++------ src/backend/statistics/extended_stats.c | 180 +++++++++++------- src/backend/statistics/mcv.c | 89 ++------- src/backend/statistics/mvdistinct.c | 138 +++----------- .../statistics/extended_stats_internal.h | 40 ++-- 5 files changed, 183 insertions(+), 346 deletions(-) diff --git a/src/backend/statistics/dependencies.c b/src/backend/statistics/dependencies.c index 602301b724..14d6503e1a 100644 --- a/src/backend/statistics/dependencies.c +++ b/src/backend/statistics/dependencies.c @@ -70,10 +70,7 @@ static void generate_dependencies(DependencyGenerator state); static DependencyGenerator DependencyGenerator_init(int n, int k); static void DependencyGenerator_free(DependencyGenerator state); static AttrNumber *DependencyGenerator_next(DependencyGenerator state); -static double dependency_degree(int numrows, HeapTuple *rows, - ExprInfo *exprs, int k, - AttrNumber *dependency, VacAttrStats **stats, - Bitmapset *attrs); +static double dependency_degree(StatBuildData *data, int k, AttrNumber *dependency); static bool dependency_is_fully_matched(MVDependency *dependency, Bitmapset *attnums); static bool dependency_is_compatible_clause(Node *clause, Index relid, @@ -222,17 +219,13 @@ DependencyGenerator_next(DependencyGenerator state) * the last one. */ static double -dependency_degree(int numrows, HeapTuple *rows, ExprInfo *exprs, int k, - AttrNumber *dependency, VacAttrStats **stats, - Bitmapset *attrs) +dependency_degree(StatBuildData *data, int k, AttrNumber *dependency) { int i, nitems; MultiSortSupport mss; SortItem *items; - AttrNumber *attnums; AttrNumber *attnums_dep; - int numattrs; /* counters valid within a group */ int group_size = 0; @@ -247,16 +240,9 @@ dependency_degree(int numrows, HeapTuple *rows, ExprInfo *exprs, int k, /* sort info for all attributes columns */ mss = multi_sort_init(k); - /* - * Transform the attrs from bitmap to an array to make accessing the i-th - * member easier, and then construct a filtered version with only attnums - * referenced by the dependency we validate. - */ - attnums = build_attnums_array(attrs, exprs->nexprs, &numattrs); - attnums_dep = (AttrNumber *) palloc(k * sizeof(AttrNumber)); for (i = 0; i < k; i++) - attnums_dep[i] = attnums[dependency[i]]; + attnums_dep[i] = data->attnums[dependency[i]]; /* * Verify the dependency (a,b,...)->z, using a rather simple algorithm: @@ -274,7 +260,7 @@ dependency_degree(int numrows, HeapTuple *rows, ExprInfo *exprs, int k, /* prepare the sort function for the dimensions */ for (i = 0; i < k; i++) { - VacAttrStats *colstat = stats[dependency[i]]; + VacAttrStats *colstat = data->stats[dependency[i]]; TypeCacheEntry *type; type = lookup_type_cache(colstat->attrtypid, TYPECACHE_LT_OPR); @@ -293,8 +279,7 @@ dependency_degree(int numrows, HeapTuple *rows, ExprInfo *exprs, int k, * descriptor. For now that assumption holds, but it might change in the * future for example if we support statistics on multiple tables. */ - items = build_sorted_items(numrows, &nitems, rows, exprs, - stats[0]->tupDesc, mss, k, attnums_dep); + items = build_sorted_items(data, &nitems, mss, k, attnums_dep); /* * Walk through the sorted array, split it into rows according to the @@ -340,11 +325,10 @@ dependency_degree(int numrows, HeapTuple *rows, ExprInfo *exprs, int k, pfree(items); pfree(mss); - pfree(attnums); pfree(attnums_dep); /* Compute the 'degree of validity' as (supporting/total). */ - return (n_supporting_rows * 1.0 / numrows); + return (n_supporting_rows * 1.0 / data->numrows); } /* @@ -364,54 +348,15 @@ dependency_degree(int numrows, HeapTuple *rows, ExprInfo *exprs, int k, * (c) -> b */ MVDependencies * -statext_dependencies_build(int numrows, HeapTuple *rows, - ExprInfo *exprs, Bitmapset *attrs, - VacAttrStats **stats) +statext_dependencies_build(StatBuildData *data) { int i, k; - int numattrs; - AttrNumber *attnums; - int nattnums; /* result */ MVDependencies *dependencies = NULL; - /* - * Transform the bms into an array of attnums, to make accessing i-th - * member easier. We add the expressions first, represented by negative - * attnums (this is OK, we don't allow statistics on system attributes), - * and then regular attributes. - */ - nattnums = bms_num_members(attrs) + exprs->nexprs; - attnums = (AttrNumber *) palloc(sizeof(AttrNumber) * nattnums); - - numattrs = 0; - - /* treat expressions as attributes with negative attnums */ - for (i = 0; i < exprs->nexprs; i++) - attnums[numattrs++] = -(i+1); - - /* - * and then regular attributes - * - * XXX Maybe add this in the opposite order, just like in MCV? first - * regular attnums, then exressions. - */ - k = -1; - while ((k = bms_next_member(attrs, k)) >= 0) - attnums[numattrs++] = k; - - Assert(numattrs >= 2); - Assert(numattrs == nattnums); - - /* - * Build a new bitmapset of attnums, offset by number of expressions (this - * is needed, because bitmaps can store only non-negative values). - */ - attrs = NULL; - for (i = 0; i < numattrs; i++) - attrs = bms_add_member(attrs, attnums[i] + exprs->nexprs); + Assert(data->nattnums >= 2); /* * We'll try build functional dependencies starting from the smallest ones @@ -419,12 +364,12 @@ statext_dependencies_build(int numrows, HeapTuple *rows, * included in the statistics object. We start from the smallest ones * because we want to be able to skip already implied ones. */ - for (k = 2; k <= numattrs; k++) + for (k = 2; k <= data->nattnums; k++) { AttrNumber *dependency; /* array with k elements */ /* prepare a DependencyGenerator of variation */ - DependencyGenerator DependencyGenerator = DependencyGenerator_init(numattrs, k); + DependencyGenerator DependencyGenerator = DependencyGenerator_init(data->nattnums, k); /* generate all possible variations of k values (out of n) */ while ((dependency = DependencyGenerator_next(DependencyGenerator))) @@ -433,8 +378,7 @@ statext_dependencies_build(int numrows, HeapTuple *rows, MVDependency *d; /* compute how valid the dependency seems */ - degree = dependency_degree(numrows, rows, exprs, k, dependency, - stats, attrs); + degree = dependency_degree(data, k, dependency); /* * if the dependency seems entirely invalid, don't store it @@ -449,7 +393,7 @@ statext_dependencies_build(int numrows, HeapTuple *rows, d->degree = degree; d->nattributes = k; for (i = 0; i < k; i++) - d->attributes[i] = attnums[dependency[i]]; + d->attributes[i] = data->attnums[dependency[i]]; /* initialize the list of dependencies */ if (dependencies == NULL) @@ -477,8 +421,6 @@ statext_dependencies_build(int numrows, HeapTuple *rows, DependencyGenerator_free(DependencyGenerator); } - pfree(attrs); - return dependencies; } diff --git a/src/backend/statistics/extended_stats.c b/src/backend/statistics/extended_stats.c index 95b2cc683e..5b3fa523e9 100644 --- a/src/backend/statistics/extended_stats.c +++ b/src/backend/statistics/extended_stats.c @@ -96,8 +96,11 @@ static Datum serialize_expr_stats(AnlExprData *exprdata, int nexprs); static Datum expr_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull); static AnlExprData *build_expr_data(List *exprs); static VacAttrStats *examine_expression(Node *expr); -static ExprInfo *evaluate_expressions(Relation rel, List *exprs, - int numrows, HeapTuple *rows); + +static StatBuildData *make_build_data(Relation onerel, StatExtEntry *stat, + int numrows, HeapTuple *rows, + VacAttrStats **stats); + /* * Compute requested extended stats, using the rows sampled for the plain @@ -156,7 +159,7 @@ BuildRelationExtStatistics(Relation onerel, double totalrows, VacAttrStats **stats; ListCell *lc2; int stattarget; - ExprInfo *exprs; + StatBuildData *data; /* * Check if we can build these stats based on the column analyzed. If @@ -191,7 +194,7 @@ BuildRelationExtStatistics(Relation onerel, double totalrows, continue; /* evaluate expressions (if the statistics has any) */ - exprs = evaluate_expressions(onerel, stat->exprs, numrows, rows); + data = make_build_data(onerel, stat, numrows, rows, stats); /* compute statistic of each requested type */ foreach(lc2, stat->types) @@ -199,16 +202,11 @@ BuildRelationExtStatistics(Relation onerel, double totalrows, char t = (char) lfirst_int(lc2); if (t == STATS_EXT_NDISTINCT) - ndistinct = statext_ndistinct_build(totalrows, numrows, rows, - exprs, stat->columns, - stats); + ndistinct = statext_ndistinct_build(totalrows, data); else if (t == STATS_EXT_DEPENDENCIES) - dependencies = statext_dependencies_build(numrows, rows, - exprs, stat->columns, - stats); + dependencies = statext_dependencies_build(data); else if (t == STATS_EXT_MCV) - mcv = statext_mcv_build(numrows, rows, exprs, stat->columns, - stats, totalrows, stattarget); + mcv = statext_mcv_build(data, totalrows, stattarget); else if (t == STATS_EXT_EXPRESSIONS) { AnlExprData *exprdata; @@ -236,7 +234,8 @@ BuildRelationExtStatistics(Relation onerel, double totalrows, pgstat_progress_update_param(PROGRESS_ANALYZE_EXT_STATS_COMPUTED, ++ext_cnt); - pfree(exprs); + /* free the build data (allocated as a single chunk) */ + pfree(data); } table_close(pg_stext, RowExclusiveLock); @@ -937,30 +936,31 @@ build_attnums_array(Bitmapset *attrs, int nexprs, int *numattrs) * can simply pfree the return value to release all of it. */ SortItem * -build_sorted_items(int numrows, int *nitems, HeapTuple *rows, ExprInfo *exprs, - TupleDesc tdesc, MultiSortSupport mss, +build_sorted_items(StatBuildData *data, int *nitems, + MultiSortSupport mss, int numattrs, AttrNumber *attnums) { int i, j, len, - idx; - int nvalues = numrows * numattrs; + nrows; + int nvalues = data->numrows * numattrs; SortItem *items; Datum *values; bool *isnull; char *ptr; + int *typlen; /* Compute the total amount of memory we need (both items and values). */ - len = numrows * sizeof(SortItem) + nvalues * (sizeof(Datum) + sizeof(bool)); + len = data->numrows * sizeof(SortItem) + nvalues * (sizeof(Datum) + sizeof(bool)); /* Allocate the memory and split it into the pieces. */ ptr = palloc0(len); /* items to sort */ items = (SortItem *) ptr; - ptr += numrows * sizeof(SortItem); + ptr += data->numrows * sizeof(SortItem); /* values and null flags */ values = (Datum *) ptr; @@ -973,13 +973,24 @@ build_sorted_items(int numrows, int *nitems, HeapTuple *rows, ExprInfo *exprs, Assert((ptr - (char *) items) == len); /* fix the pointers to Datum and bool arrays */ - idx = 0; - for (i = 0; i < numrows; i++) + nrows = 0; + for (i = 0; i < data->numrows; i++) { - bool toowide = false; + items[nrows].values = &values[nrows * numattrs]; + items[nrows].isnull = &isnull[nrows * numattrs]; + + nrows++; + } + + /* build a local cache of typlen for all attributes */ + typlen = (int *) palloc(sizeof(int) * data->nattnums); + for (i = 0; i < data->nattnums; i++) + typlen[i] = get_typlen(data->stats[i]->attrtypid); - items[idx].values = &values[idx * numattrs]; - items[idx].isnull = &isnull[idx * numattrs]; + nrows = 0; + for (i = 0; i < data->numrows; i++) + { + bool toowide = false; /* load the values/null flags from sample rows */ for (j = 0; j < numattrs; j++) @@ -989,22 +1000,20 @@ build_sorted_items(int numrows, int *nitems, HeapTuple *rows, ExprInfo *exprs, int attlen; AttrNumber attnum = attnums[j]; - if (AttrNumberIsForUserDefinedAttr(attnum)) + int idx; + + /* match attnum to the pre-calculated data */ + for (idx = 0; idx < data->nattnums; idx++) { - value = heap_getattr(rows[i], attnum, tdesc, &isnull); - attlen = TupleDescAttr(tdesc, attnum - 1)->attlen; + if (attnum == data->attnums[idx]) + break; } - else - { - int idx = -(attnums[j] + 1); - - Assert((idx >= 0) && (idx < exprs->nexprs)); - value = exprs->values[idx][i]; - isnull = exprs->nulls[idx][i]; + Assert(idx < data->nattnums); - attlen = get_typlen(exprs->types[idx]); - } + value = data->values[idx][i]; + isnull = data->nulls[idx][i]; + attlen = typlen[idx]; /* * If this is a varlena value, check if it's too wide and if yes @@ -1026,21 +1035,21 @@ build_sorted_items(int numrows, int *nitems, HeapTuple *rows, ExprInfo *exprs, value = PointerGetDatum(PG_DETOAST_DATUM(value)); } - items[idx].values[j] = value; - items[idx].isnull[j] = isnull; + items[nrows].values[j] = value; + items[nrows].isnull[j] = isnull; } if (toowide) continue; - idx++; + nrows++; } /* store the actual number of items (ignoring the too-wide ones) */ - *nitems = idx; + *nitems = nrows; /* all items were too wide */ - if (idx == 0) + if (nrows == 0) { /* everything is allocated as a single chunk */ pfree(items); @@ -1048,7 +1057,7 @@ build_sorted_items(int numrows, int *nitems, HeapTuple *rows, ExprInfo *exprs, } /* do the sort, using the multi-sort */ - qsort_arg((void *) items, idx, sizeof(SortItem), + qsort_arg((void *) items, nrows, sizeof(SortItem), multi_sort_compare, mss); return items; @@ -2434,59 +2443,61 @@ statext_expressions_load(Oid stxoid, int idx) * all the requested statistics types. This matters especially for * expensive expressions, of course. */ -static ExprInfo * -evaluate_expressions(Relation rel, List *exprs, int numrows, HeapTuple *rows) +static StatBuildData * +make_build_data(Relation rel, StatExtEntry *stat, int numrows, HeapTuple *rows, + VacAttrStats **stats) { /* evaluated expressions */ - ExprInfo *result; + StatBuildData *result; char *ptr; Size len; int i; + int k; int idx; TupleTableSlot *slot; EState *estate; ExprContext *econtext; List *exprstates = NIL; - int nexprs = list_length(exprs); + int nkeys = bms_num_members(stat->columns) + list_length(stat->exprs); ListCell *lc; /* allocate everything as a single chunk, so we can free it easily */ - len = MAXALIGN(sizeof(ExprInfo)); - len += MAXALIGN(sizeof(Oid) * nexprs); /* types */ - len += MAXALIGN(sizeof(Oid) * nexprs); /* collations */ + len = MAXALIGN(sizeof(StatBuildData)); + len += MAXALIGN(sizeof(AttrNumber) * nkeys); /* attnums */ + len += MAXALIGN(sizeof(VacAttrStats *) * nkeys); /* stats */ /* values */ - len += MAXALIGN(sizeof(Datum *) * nexprs); - len += nexprs * MAXALIGN(sizeof(Datum) * numrows); + len += MAXALIGN(sizeof(Datum *) * nkeys); + len += nkeys * MAXALIGN(sizeof(Datum) * numrows); /* nulls */ - len += MAXALIGN(sizeof(bool *) * nexprs); - len += nexprs * MAXALIGN(sizeof(bool) * numrows); + len += MAXALIGN(sizeof(bool *) * nkeys); + len += nkeys * MAXALIGN(sizeof(bool) * numrows); ptr = palloc(len); /* set the pointers */ - result = (ExprInfo *) ptr; - ptr += MAXALIGN(sizeof(ExprInfo)); + result = (StatBuildData *) ptr; + ptr += MAXALIGN(sizeof(StatBuildData)); - /* types */ - result->types = (Oid *) ptr; - ptr += MAXALIGN(sizeof(Oid) * nexprs); + /* attnums */ + result->attnums = (AttrNumber *) ptr; + ptr += MAXALIGN(sizeof(AttrNumber) * nkeys); - /* collations */ - result->collations = (Oid *) ptr; - ptr += MAXALIGN(sizeof(Oid) * nexprs); + /* stats */ + result->stats = (VacAttrStats **) ptr; + ptr += MAXALIGN(sizeof(VacAttrStats *) * nkeys); /* values */ result->values = (Datum **) ptr; - ptr += MAXALIGN(sizeof(Datum *) * nexprs); + ptr += MAXALIGN(sizeof(Datum *) * nkeys); /* nulls */ result->nulls = (bool **) ptr; - ptr += MAXALIGN(sizeof(bool *) * nexprs); + ptr += MAXALIGN(sizeof(bool *) * nkeys); - for (i = 0; i < nexprs; i++) + for (i = 0; i < nkeys; i++) { result->values[i] = (Datum *) ptr; ptr += MAXALIGN(sizeof(Datum) * numrows); @@ -2497,17 +2508,46 @@ evaluate_expressions(Relation rel, List *exprs, int numrows, HeapTuple *rows) Assert((ptr - (char *) result) == len); - result->nexprs = list_length(exprs); + /* we have it allocated, so let's fill the values */ + result->nattnums = nkeys; + result->numrows = numrows; + /* fill the attribute info - first attributes, then expressions */ idx = 0; - foreach (lc, exprs) + k = -1; + while ((k = bms_next_member(stat->columns, k)) >= 0) + { + result->attnums[idx] = k; + result->stats[idx] = stats[idx]; + + idx++; + } + + k = -1; + foreach (lc, stat->exprs) { Node *expr = (Node *) lfirst(lc); - result->types[idx] = exprType(expr); - result->collations[idx] = exprCollation(expr); + result->attnums[idx] = k; + result->stats[idx] = examine_expression(expr); idx++; + k--; + } + + /* first extract values for all the regular attributes */ + for (i = 0; i < numrows; i++) + { + idx = 0; + k = -1; + while ((k = bms_next_member(stat->columns, k)) >= 0) + { + result->values[idx][i] = heap_getattr(rows[i], k, + result->stats[idx]->tupDesc, + &result->nulls[idx][i]); + + idx++; + } } /* @@ -2526,7 +2566,7 @@ evaluate_expressions(Relation rel, List *exprs, int numrows, HeapTuple *rows) econtext->ecxt_scantuple = slot; /* Set up expression evaluation state */ - exprstates = ExecPrepareExprList(exprs, estate); + exprstates = ExecPrepareExprList(stat->exprs, estate); for (i = 0; i < numrows; i++) { @@ -2539,7 +2579,7 @@ evaluate_expressions(Relation rel, List *exprs, int numrows, HeapTuple *rows) /* Set up for predicate or expression evaluation */ ExecStoreHeapTuple(rows[i], slot, false); - idx = 0; + idx = bms_num_members(stat->columns); foreach (lc, exprstates) { Datum datum; diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c index 323d476814..844ba6f71f 100644 --- a/src/backend/statistics/mcv.c +++ b/src/backend/statistics/mcv.c @@ -74,8 +74,7 @@ ((ndims) * sizeof(DimensionInfo)) + \ ((nitems) * ITEM_SIZE(ndims))) -static MultiSortSupport build_mss(VacAttrStats **stats, int numattrs, - ExprInfo *exprs); +static MultiSortSupport build_mss(StatBuildData *data); static SortItem *build_distinct_groups(int numrows, SortItem *items, MultiSortSupport mss, int *ndistinct); @@ -182,16 +181,11 @@ get_mincount_for_mcv_list(int samplerows, double totalrows) * */ MCVList * -statext_mcv_build(int numrows, HeapTuple *rows, ExprInfo *exprs, - Bitmapset *attrs, VacAttrStats **stats, - double totalrows, int stattarget) +statext_mcv_build(StatBuildData *data, double totalrows, int stattarget) { int i, - k, - numattrs, ngroups, nitems; - AttrNumber *attnums; double mincount; SortItem *items; SortItem *groups; @@ -199,38 +193,11 @@ statext_mcv_build(int numrows, HeapTuple *rows, ExprInfo *exprs, MultiSortSupport mss; /* comparator for all the columns */ - mss = build_mss(stats, bms_num_members(attrs), exprs); - - /* - * treat expressions as special attributes with high attnums - * - * XXX We do this after build_mss, because that expects the bitmapset - * to only contain simple attributes (with a matching VacAttrStats) - */ - - /* - * Transform the bms into an array, to make accessing i-th member easier. - */ - attnums = (AttrNumber *) palloc(sizeof(AttrNumber) * (bms_num_members(attrs) + exprs->nexprs)); - - numattrs = 0; - - /* regular attributes */ - k = -1; - while ((k = bms_next_member(attrs, k)) >= 0) - attnums[numattrs++] = k; - - /* treat expressions as attributes with negative attnums */ - for (i = 0; i < exprs->nexprs; i++) - attnums[numattrs++] = -(i+1); - - Assert(numattrs >= 2); - Assert(numattrs == (bms_num_members(attrs) + exprs->nexprs)); - + mss = build_mss(data); /* sort the rows */ - items = build_sorted_items(numrows, &nitems, rows, exprs, - stats[0]->tupDesc, mss, numattrs, attnums); + items = build_sorted_items(data, &nitems, mss, + data->nattnums, data->attnums); if (!items) return NULL; @@ -265,7 +232,7 @@ statext_mcv_build(int numrows, HeapTuple *rows, ExprInfo *exprs, * using get_mincount_for_mcv_list() and then keep all items that seem to * be more common than that. */ - mincount = get_mincount_for_mcv_list(numrows, totalrows); + mincount = get_mincount_for_mcv_list(data->numrows, totalrows); /* * Walk the groups until we find the first group with a count below the @@ -301,7 +268,7 @@ statext_mcv_build(int numrows, HeapTuple *rows, ExprInfo *exprs, + sizeof(SortSupportData)); /* compute frequencies for values in each column */ - nfreqs = (int *) palloc0(sizeof(int) * numattrs); + nfreqs = (int *) palloc0(sizeof(int) * data->nattnums); freqs = build_column_frequencies(groups, ngroups, mss, nfreqs); /* @@ -312,12 +279,12 @@ statext_mcv_build(int numrows, HeapTuple *rows, ExprInfo *exprs, mcvlist->magic = STATS_MCV_MAGIC; mcvlist->type = STATS_MCV_TYPE_BASIC; - mcvlist->ndimensions = numattrs; + mcvlist->ndimensions = data->nattnums; mcvlist->nitems = nitems; /* store info about data type OIDs */ - for (i = 0; i < numattrs; i++) - mcvlist->types[i] = stats[i]->attrtypid; + for (i = 0; i < data->nattnums; i++) + mcvlist->types[i] = data->stats[i]->attrtypid; /* Copy the first chunk of groups into the result. */ for (i = 0; i < nitems; i++) @@ -325,22 +292,22 @@ statext_mcv_build(int numrows, HeapTuple *rows, ExprInfo *exprs, /* just pointer to the proper place in the list */ MCVItem *item = &mcvlist->items[i]; - item->values = (Datum *) palloc(sizeof(Datum) * numattrs); - item->isnull = (bool *) palloc(sizeof(bool) * numattrs); + item->values = (Datum *) palloc(sizeof(Datum) * data->nattnums); + item->isnull = (bool *) palloc(sizeof(bool) * data->nattnums); /* copy values for the group */ - memcpy(item->values, groups[i].values, sizeof(Datum) * numattrs); - memcpy(item->isnull, groups[i].isnull, sizeof(bool) * numattrs); + memcpy(item->values, groups[i].values, sizeof(Datum) * data->nattnums); + memcpy(item->isnull, groups[i].isnull, sizeof(bool) * data->nattnums); /* groups should be sorted by frequency in descending order */ Assert((i == 0) || (groups[i - 1].count >= groups[i].count)); /* group frequency */ - item->frequency = (double) groups[i].count / numrows; + item->frequency = (double) groups[i].count / data->numrows; /* base frequency, if the attributes were independent */ item->base_frequency = 1.0; - for (j = 0; j < numattrs; j++) + for (j = 0; j < data->nattnums; j++) { SortItem *freq; @@ -356,7 +323,7 @@ statext_mcv_build(int numrows, HeapTuple *rows, ExprInfo *exprs, sizeof(SortItem), multi_sort_compare, tmp); - item->base_frequency *= ((double) freq->count) / numrows; + item->base_frequency *= ((double) freq->count) / data->numrows; } } @@ -375,17 +342,17 @@ statext_mcv_build(int numrows, HeapTuple *rows, ExprInfo *exprs, * build MultiSortSupport for the attributes passed in attrs */ static MultiSortSupport -build_mss(VacAttrStats **stats, int numattrs, ExprInfo *exprs) +build_mss(StatBuildData *data) { int i; /* Sort by multiple columns (using array of SortSupport) */ - MultiSortSupport mss = multi_sort_init(numattrs + exprs->nexprs); + MultiSortSupport mss = multi_sort_init(data->nattnums); /* prepare the sort functions for all the attributes */ - for (i = 0; i < numattrs; i++) + for (i = 0; i < data->nattnums; i++) { - VacAttrStats *colstat = stats[i]; + VacAttrStats *colstat = data->stats[i]; TypeCacheEntry *type; type = lookup_type_cache(colstat->attrtypid, TYPECACHE_LT_OPR); @@ -396,20 +363,6 @@ build_mss(VacAttrStats **stats, int numattrs, ExprInfo *exprs) multi_sort_add_dimension(mss, i, type->lt_opr, colstat->attrcollid); } - /* prepare the sort functions for all the expressions */ - for (i = 0; i < exprs->nexprs; i++) - { - TypeCacheEntry *type; - - type = lookup_type_cache(exprs->types[i], TYPECACHE_LT_OPR); - if (type->lt_opr == InvalidOid) /* shouldn't happen */ - elog(ERROR, "cache lookup failed for ordering operator for type %u", - exprs->types[i]); - - multi_sort_add_dimension(mss, numattrs + i, type->lt_opr, - exprs->collations[i]); - } - return mss; } diff --git a/src/backend/statistics/mvdistinct.c b/src/backend/statistics/mvdistinct.c index 5e796e7123..7ca59d9785 100644 --- a/src/backend/statistics/mvdistinct.c +++ b/src/backend/statistics/mvdistinct.c @@ -36,9 +36,7 @@ #include "utils/syscache.h" #include "utils/typcache.h" -static double ndistinct_for_combination(double totalrows, int numrows, - HeapTuple *rows, ExprInfo *exprs, - int nattrs, VacAttrStats **stats, +static double ndistinct_for_combination(double totalrows, StatBuildData *data, int k, int *combination); static double estimate_ndistinct(double totalrows, int numrows, int d, int f1); static int n_choose_k(int n, int k); @@ -88,17 +86,12 @@ static void generate_combinations(CombinationGenerator *state); * allow using Bitmapsets. */ MVNDistinct * -statext_ndistinct_build(double totalrows, int numrows, HeapTuple *rows, - ExprInfo *exprs, Bitmapset *attrs, - VacAttrStats **stats) +statext_ndistinct_build(double totalrows, StatBuildData *data) { MVNDistinct *result; - int i; int k; int itemcnt; - int numattrs = bms_num_members(attrs); - int numcombs = num_combinations(numattrs + exprs->nexprs); - Bitmapset *tmp = NULL; + int numcombs = num_combinations(data->nattnums); result = palloc(offsetof(MVNDistinct, items) + numcombs * sizeof(MVNDistinctItem)); @@ -106,38 +99,14 @@ statext_ndistinct_build(double totalrows, int numrows, HeapTuple *rows, result->type = STATS_NDISTINCT_TYPE_BASIC; result->nitems = numcombs; - /* - * Treat expressions as system attributes with negative attnums, - * but offset everything by number of expressions. - */ - for (i = 0; i < exprs->nexprs; i++) - { - AttrNumber attnum = -(i + 1); - tmp = bms_add_member(tmp, attnum + exprs->nexprs); - } - - /* regular attributes */ - k = -1; - while ((k = bms_next_member(attrs, k)) >= 0) - { - AttrNumber attnum = k; - tmp = bms_add_member(tmp, attnum + exprs->nexprs); - } - - /* use the newly built bitmapset */ - attrs = tmp; - - /* make sure there were no clashes */ - Assert(bms_num_members(attrs) == numattrs + exprs->nexprs); - itemcnt = 0; - for (k = 2; k <= bms_num_members(attrs); k++) + for (k = 2; k <= data->nattnums; k++) { int *combination; CombinationGenerator *generator; /* generate combinations of K out of N elements */ - generator = generator_init(bms_num_members(attrs), k); + generator = generator_init(data->nattnums, k); while ((combination = generator_next(generator))) { @@ -147,36 +116,16 @@ statext_ndistinct_build(double totalrows, int numrows, HeapTuple *rows, item->attributes = palloc(sizeof(AttrNumber) * k); item->nattributes = k; + /* translate the indexes to attnums */ for (j = 0; j < k; j++) { - AttrNumber attnum = InvalidAttrNumber; - - /* - * The expressions have negative attnums, so even with the - * offset are before regular attributes. So the first chunk - * of indexes are for expressions. - */ - if (combination[j] >= exprs->nexprs) - attnum - = stats[combination[j] - exprs->nexprs]->attr->attnum; - else - { - /* make sure the expression index is valid */ - Assert(combination[j] >= 0); - Assert(combination[j] < exprs->nexprs); - - attnum = -(combination[j] + 1); - } - - Assert(attnum != InvalidAttrNumber); - - item->attributes[j] = attnum; + item->attributes[j] = data->attnums[combination[j]]; + + Assert(AttributeNumberIsValid(item->attributes[j])); } item->ndistinct = - ndistinct_for_combination(totalrows, numrows, rows, - exprs, numattrs, - stats, k, combination); + ndistinct_for_combination(totalrows, data, k, combination); itemcnt++; Assert(itemcnt <= result->nitems); @@ -471,9 +420,8 @@ pg_ndistinct_send(PG_FUNCTION_ARGS) * combination of multiple columns. */ static double -ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows, - ExprInfo *exprs, int nattrs, - VacAttrStats **stats, int k, int *combination) +ndistinct_for_combination(double totalrows, StatBuildData *data, + int k, int *combination) { int i, j; @@ -493,11 +441,11 @@ ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows, * using the specified column combination as dimensions. We could try to * sort in place, but it'd probably be more complex and bug-prone. */ - items = (SortItem *) palloc(numrows * sizeof(SortItem)); - values = (Datum *) palloc0(sizeof(Datum) * numrows * k); - isnull = (bool *) palloc0(sizeof(bool) * numrows * k); + items = (SortItem *) palloc(data->numrows * sizeof(SortItem)); + values = (Datum *) palloc0(sizeof(Datum) * data->numrows * k); + isnull = (bool *) palloc0(sizeof(bool) * data->numrows * k); - for (i = 0; i < numrows; i++) + for (i = 0; i < data->numrows; i++) { items[i].values = &values[i * k]; items[i].isnull = &isnull[i * k]; @@ -514,24 +462,11 @@ ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows, { Oid typid; TypeCacheEntry *type; - AttrNumber attnum = InvalidAttrNumber; - TupleDesc tdesc = NULL; Oid collid = InvalidOid; + VacAttrStats *colstat = data->stats[combination[i]]; - /* first nexprs indexes are for expressions, then regular attributes */ - if (combination[i] >= exprs->nexprs) - { - VacAttrStats *colstat = stats[combination[i] - exprs->nexprs]; - typid = colstat->attrtypid; - attnum = colstat->attr->attnum; - collid = colstat->attrcollid; - tdesc = colstat->tupDesc; - } - else - { - typid = exprs->types[combination[i]]; - collid = exprs->collations[combination[i]]; - } + typid = colstat->attrtypid; + collid = colstat->attrcollid; type = lookup_type_cache(typid, TYPECACHE_LT_OPR); if (type->lt_opr == InvalidOid) /* shouldn't happen */ @@ -542,38 +477,15 @@ ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows, multi_sort_add_dimension(mss, i, type->lt_opr, collid); /* accumulate all the data for this dimension into the arrays */ - for (j = 0; j < numrows; j++) + for (j = 0; j < data->numrows; j++) { - /* - * The first exprs indexes identify expressions, higher indexes - * are for plain attributes. - * - * XXX This seems a bit strange that we don't offset the (i) - * in any way? - */ - if (combination[i] >= exprs->nexprs) - items[j].values[i] = - heap_getattr(rows[j], - attnum, - tdesc, - &items[j].isnull[i]); - else - { - /* we know the first nexprs expressions are expressions, - * and the value is directly the expression index */ - int idx = combination[i]; - - /* make sure the expression index is valid */ - Assert((idx >= 0) && (idx < exprs->nexprs)); - - items[j].values[i] = exprs->values[idx][j]; - items[j].isnull[i] = exprs->nulls[idx][j]; - } + items[j].values[i] = data->values[combination[i]][j]; + items[j].isnull[i] = data->nulls[combination[i]][j]; } } /* We can sort the array now ... */ - qsort_arg((void *) items, numrows, sizeof(SortItem), + qsort_arg((void *) items, data->numrows, sizeof(SortItem), multi_sort_compare, mss); /* ... and count the number of distinct combinations */ @@ -581,7 +493,7 @@ ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows, f1 = 0; cnt = 1; d = 1; - for (i = 1; i < numrows; i++) + for (i = 1; i < data->numrows; i++) { if (multi_sort_compare(&items[i], &items[i - 1], mss) != 0) { @@ -598,7 +510,7 @@ ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows, if (cnt == 1) f1 += 1; - return estimate_ndistinct(totalrows, numrows, d, f1); + return estimate_ndistinct(totalrows, data->numrows, d, f1); } /* The Duj1 estimator (already used in analyze.c). */ diff --git a/src/include/statistics/extended_stats_internal.h b/src/include/statistics/extended_stats_internal.h index 1f09799deb..7acf82aa0e 100644 --- a/src/include/statistics/extended_stats_internal.h +++ b/src/include/statistics/extended_stats_internal.h @@ -57,35 +57,26 @@ typedef struct SortItem int count; } SortItem; -/* - * Used to pass pre-computed information about expressions the stats - * object is defined on. - */ -typedef struct ExprInfo -{ - int nexprs; /* number of expressions */ - Oid *collations; /* collation for each expression */ - Oid *types; /* type of each expression */ - Datum **values; /* values for each expression */ - bool **nulls; /* nulls for each expression */ -} ExprInfo; - -extern MVNDistinct *statext_ndistinct_build(double totalrows, - int numrows, HeapTuple *rows, - ExprInfo *exprs, Bitmapset *attrs, - VacAttrStats **stats); +/* a unified representation of the data the statistics is built on */ +typedef struct StatBuildData { + int numrows; + int nattnums; + AttrNumber *attnums; + VacAttrStats **stats; + Datum **values; + bool **nulls; +} StatBuildData; + + +extern MVNDistinct *statext_ndistinct_build(double totalrows, StatBuildData *data); extern bytea *statext_ndistinct_serialize(MVNDistinct *ndistinct); extern MVNDistinct *statext_ndistinct_deserialize(bytea *data); -extern MVDependencies *statext_dependencies_build(int numrows, HeapTuple *rows, - ExprInfo *exprs, Bitmapset *attrs, - VacAttrStats **stats); +extern MVDependencies *statext_dependencies_build(StatBuildData *data); extern bytea *statext_dependencies_serialize(MVDependencies *dependencies); extern MVDependencies *statext_dependencies_deserialize(bytea *data); -extern MCVList *statext_mcv_build(int numrows, HeapTuple *rows, - ExprInfo *exprs, Bitmapset *attrs, - VacAttrStats **stats, +extern MCVList *statext_mcv_build(StatBuildData *data, double totalrows, int stattarget); extern bytea *statext_mcv_serialize(MCVList *mcv, VacAttrStats **stats); extern MCVList *statext_mcv_deserialize(bytea *data); @@ -108,8 +99,7 @@ extern void *bsearch_arg(const void *key, const void *base, extern AttrNumber *build_attnums_array(Bitmapset *attrs, int nexprs, int *numattrs); -extern SortItem *build_sorted_items(int numrows, int *nitems, HeapTuple *rows, - ExprInfo *exprs, TupleDesc tdesc, +extern SortItem *build_sorted_items(StatBuildData *data, int *nitems, MultiSortSupport mss, int numattrs, AttrNumber *attnums); -- 2.26.2 --------------614DDB87AFFED893713AC0E9-- ^ permalink raw reply [nested|flat] 5+ messages in thread
* Buffer Manager and Contention @ 2022-02-24 12:58 Simon Riggs <[email protected]> 0 siblings, 1 reply; 5+ messages in thread From: Simon Riggs @ 2022-02-24 12:58 UTC (permalink / raw) To: pgsql-hackers Thinking about poor performance in the case where the data fits in RAM, but the working set is too big for shared_buffers, I notice a couple of things that seem bad in BufMgr, but don't understand why they are like that. 1. If we need to allocate a buffer to a new block we do this in one step, while holding both partition locks for the old and the new tag. Surely it would cause less contention to make the old block/tag invalid (after flushing), drop the old partition lock and then switch to the new one? i.e. just hold one mapping partition lock at a time. Is there a specific reason we do it this way? 2. Possibly connected to the above, we issue BufTableInsert() BEFORE we issue BufTableDelete(). That means we need extra entries in the buffer mapping hash table to allow us to hold both the old and the new at the same time, for a short period. The way dynahash.c works, we try to allocate an entry from the freelist and if that doesn't work, we begin searching ALL the freelists for free entries to steal. So if we get enough people trying to do virtual I/O at the same time, then we will hit a "freelist storm" where everybody is chasing the last few entries. It would make more sense if we could do BufTableDelete() first, then hold onto the buffer mapping entry rather than add it to the freelist, so we can use it again when we do BufTableInsert() very shortly afterwards. That way we wouldn't need to search the freelist at all. What is the benefit or reason of doing the Delete after the Insert? Put that another way, it looks like BufTable functions are used in a way that mismatches against the way dynahash is designed. Thoughts? -- Simon Riggs http://www.EnterpriseDB.com/ ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Buffer Manager and Contention @ 2022-02-25 01:20 Kyotaro Horiguchi <[email protected]> parent: Simon Riggs <[email protected]> 0 siblings, 2 replies; 5+ messages in thread From: Kyotaro Horiguchi @ 2022-02-25 01:20 UTC (permalink / raw) To: [email protected]; +Cc: Yura Sokolov <[email protected]>; pgsql-hackers (I added Yura, as the author of a related patch) At Thu, 24 Feb 2022 12:58:23 +0000, Simon Riggs <[email protected]> wrote in > Thinking about poor performance in the case where the data fits in > RAM, but the working set is too big for shared_buffers, I notice a > couple of things that seem bad in BufMgr, but don't understand why > they are like that. > > 1. If we need to allocate a buffer to a new block we do this in one > step, while holding both partition locks for the old and the new tag. > Surely it would cause less contention to make the old block/tag > invalid (after flushing), drop the old partition lock and then switch > to the new one? i.e. just hold one mapping partition lock at a time. > Is there a specific reason we do it this way? I'm not sure but I guess the developer wanted to make the operation atomic. Yura Sokolov is proposing a patch to separte the two partition locks. https://www.postgresql.org/message-id/1edbb61981fe1d99c3f20e3d56d6c88999f4227c.camel%40postgrespro.r... And it seems to me viable for me and a benchmarking in the thread showed a good result. I'd appreciate your input on that thread. > 2. Possibly connected to the above, we issue BufTableInsert() BEFORE > we issue BufTableDelete(). That means we need extra entries in the > buffer mapping hash table to allow us to hold both the old and the new > at the same time, for a short period. The way dynahash.c works, we try Yes. > to allocate an entry from the freelist and if that doesn't work, we > begin searching ALL the freelists for free entries to steal. So if we > get enough people trying to do virtual I/O at the same time, then we > will hit a "freelist storm" where everybody is chasing the last few > entries. It would make more sense if we could do BufTableDelete() To reduce that overhead, Yura proposed a surgically modification on dynahash, but I didn't like that and the latest patch doesn't contain that part. > first, then hold onto the buffer mapping entry rather than add it to > the freelist, so we can use it again when we do BufTableInsert() very > shortly afterwards. That way we wouldn't need to search the freelist > at all. What is the benefit or reason of doing the Delete after the > Insert? Hmm. something like hash_swap_key() or hash_reinsert_entry()? That sounds reasonable. (Yura's proposal was taking out an entry from hash then attach it with a new key again.) > Put that another way, it looks like BufTable functions are used in a > way that mismatches against the way dynahash is designed. > > Thoughts? On the first part, I think Yura's patch works. On the second point, Yura already showed it gives a certain amount of gain if we do that. regards. -- Kyotaro Horiguchi NTT Open Source Software Center ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Buffer Manager and Contention @ 2022-02-25 03:29 Kyotaro Horiguchi <[email protected]> parent: Kyotaro Horiguchi <[email protected]> 1 sibling, 0 replies; 5+ messages in thread From: Kyotaro Horiguchi @ 2022-02-25 03:29 UTC (permalink / raw) To: [email protected]; +Cc: [email protected]; pgsql-hackers At Fri, 25 Feb 2022 10:20:25 +0900 (JST), Kyotaro Horiguchi <[email protected]> wrote in > (I added Yura, as the author of a related patch) > > At Thu, 24 Feb 2022 12:58:23 +0000, Simon Riggs <[email protected]> wrote in > > Thinking about poor performance in the case where the data fits in > > RAM, but the working set is too big for shared_buffers, I notice a > > couple of things that seem bad in BufMgr, but don't understand why > > they are like that. > > > > 1. If we need to allocate a buffer to a new block we do this in one > > step, while holding both partition locks for the old and the new tag. > > Surely it would cause less contention to make the old block/tag > > invalid (after flushing), drop the old partition lock and then switch > > to the new one? i.e. just hold one mapping partition lock at a time. > > Is there a specific reason we do it this way? > > I'm not sure but I guess the developer wanted to make the operation > atomic. > > Yura Sokolov is proposing a patch to separte the two partition locks. > > https://www.postgresql.org/message-id/1edbb61981fe1d99c3f20e3d56d6c88999f4227c.camel%40postgrespro.r... > > And it seems to me viable for me and a benchmarking in the thread > showed a good result. I'd appreciate your input on that thread. > > > 2. Possibly connected to the above, we issue BufTableInsert() BEFORE > > we issue BufTableDelete(). That means we need extra entries in the > > buffer mapping hash table to allow us to hold both the old and the new > > at the same time, for a short period. The way dynahash.c works, we try > > Yes. > > > to allocate an entry from the freelist and if that doesn't work, we > > begin searching ALL the freelists for free entries to steal. So if we > > get enough people trying to do virtual I/O at the same time, then we > > will hit a "freelist storm" where everybody is chasing the last few > > entries. It would make more sense if we could do BufTableDelete() > > To reduce that overhead, Yura proposed a surgically modification on > dynahash, but I didn't like that and the latest patch doesn't contain > that part. > > > first, then hold onto the buffer mapping entry rather than add it to > > the freelist, so we can use it again when we do BufTableInsert() very > > shortly afterwards. That way we wouldn't need to search the freelist > > at all. What is the benefit or reason of doing the Delete after the > > Insert? > > Hmm. something like hash_swap_key() or hash_reinsert_entry()? That > sounds reasonable. (Yura's proposal was taking out an entry from hash > then attach it with a new key again.) > > > Put that another way, it looks like BufTable functions are used in a > > way that mismatches against the way dynahash is designed. > > > > Thoughts? > > On the first part, I think Yura's patch works. On the second point, > Yura already showed it gives a certain amount of gain if we do that. On second thought, even if we have a new dynahash API to atomically replace hash key, we need to hold two partition locks to do that. That is contradicting our objective. regards. -- Kyotaro Horiguchi NTT Open Source Software Center ^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Buffer Manager and Contention @ 2022-02-25 03:34 Simon Riggs <[email protected]> parent: Kyotaro Horiguchi <[email protected]> 1 sibling, 0 replies; 5+ messages in thread From: Simon Riggs @ 2022-02-25 03:34 UTC (permalink / raw) To: Kyotaro Horiguchi <[email protected]>; +Cc: Yura Sokolov <[email protected]>; pgsql-hackers On Fri, 25 Feb 2022 at 01:20, Kyotaro Horiguchi <[email protected]> wrote: > Yura Sokolov is proposing a patch to separte the two partition locks. > > https://www.postgresql.org/message-id/1edbb61981fe1d99c3f20e3d56d6c88999f4227c.camel%40postgrespro.r... > > And it seems to me viable for me and a benchmarking in the thread > showed a good result. I'd appreciate your input on that thread. Certainly, I will stop this thread and contribute to Yura's thread. -- Simon Riggs http://www.EnterpriseDB.com/ ^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2022-02-25 03:34 UTC | newest] Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2021-03-04 03:53 [PATCH 5/5] WIP unify handling of attributes and expressions Tomas Vondra <[email protected]> 2022-02-24 12:58 Buffer Manager and Contention Simon Riggs <[email protected]> 2022-02-25 01:20 ` Re: Buffer Manager and Contention Kyotaro Horiguchi <[email protected]> 2022-02-25 03:29 ` Re: Buffer Manager and Contention Kyotaro Horiguchi <[email protected]> 2022-02-25 03:34 ` Re: Buffer Manager and Contention Simon Riggs <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox