public inbox for [email protected]
help / color / mirror / Atom feed[PATCH 4/5] WIP rework tracking of expressions
3+ messages / 3 participants
[nested] [flat]
* [PATCH 4/5] WIP rework tracking of expressions
@ 2021-02-17 00:02 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 3+ messages in thread
From: Tomas Vondra @ 2021-02-17 00:02 UTC (permalink / raw)
---
src/backend/statistics/dependencies.c | 136 ++++++++++++++----
src/backend/statistics/extended_stats.c | 73 ++++------
src/backend/statistics/mcv.c | 26 +++-
src/backend/statistics/mvdistinct.c | 120 +++++++++-------
src/backend/utils/adt/selfuncs.c | 29 +++-
.../statistics/extended_stats_internal.h | 11 +-
src/include/statistics/statistics.h | 3 +-
7 files changed, 255 insertions(+), 143 deletions(-)
diff --git a/src/backend/statistics/dependencies.c b/src/backend/statistics/dependencies.c
index 6bf3127bcc..602301b724 100644
--- a/src/backend/statistics/dependencies.c
+++ b/src/backend/statistics/dependencies.c
@@ -252,7 +252,7 @@ dependency_degree(int numrows, HeapTuple *rows, ExprInfo *exprs, int k,
* member easier, and then construct a filtered version with only attnums
* referenced by the dependency we validate.
*/
- attnums = build_attnums_array(attrs, &numattrs);
+ attnums = build_attnums_array(attrs, exprs->nexprs, &numattrs);
attnums_dep = (AttrNumber *) palloc(k * sizeof(AttrNumber));
for (i = 0; i < k; i++)
@@ -372,19 +372,46 @@ statext_dependencies_build(int numrows, HeapTuple *rows,
k;
int numattrs;
AttrNumber *attnums;
+ int nattnums;
/* result */
MVDependencies *dependencies = NULL;
- /* treat expressions as special attributes with high attnums */
- attrs = add_expressions_to_attributes(attrs, exprs->nexprs);
+ /*
+ * 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);
/*
- * Transform the bms into an array, to make accessing i-th member easier.
+ * and then regular attributes
+ *
+ * XXX Maybe add this in the opposite order, just like in MCV? first
+ * regular attnums, then exressions.
*/
- attnums = build_attnums_array(attrs, &numattrs);
+ 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);
/*
* We'll try build functional dependencies starting from the smallest ones
@@ -1374,8 +1401,10 @@ dependencies_clauselist_selectivity(PlannerInfo *root,
* We also skip clauses that we already estimated using different types of
* statistics (we treat them as incompatible).
*
- * For expressions, we generate attnums higher than MaxHeapAttributeNumber
- * so that we can work with attnums only.
+ * To handle expressions, we assign them negative attnums, as if it was a
+ * system attribute (this is fine, as we only allow extended stats on user
+ * attributes). And then we offset everything by the number of expressions,
+ * so that we can store the values in a bitmapset.
*/
listidx = 0;
foreach(l, clauses)
@@ -1391,13 +1420,12 @@ dependencies_clauselist_selectivity(PlannerInfo *root,
{
/*
* If it's a simple column refrence, just extract the attnum. If
- * it's an expression, make sure it's not a duplicate and assign
- * a special attnum to it (higher than any regular value).
+ * it's an expression, assign a negative attnum as if it was a
+ * system attribute.
*/
if (dependency_is_compatible_clause(clause, rel->relid, &attnum))
{
list_attnums[listidx] = attnum;
- clauses_attnums = bms_add_member(clauses_attnums, attnum);
}
else if (dependency_is_compatible_expression(clause, rel->relid,
rel->statlist,
@@ -1413,7 +1441,8 @@ dependencies_clauselist_selectivity(PlannerInfo *root,
{
if (equal(unique_exprs[i], expr))
{
- attnum = EXPRESSION_ATTNUM(i);
+ /* negative attribute number to expression */
+ attnum = -(i + 1);
break;
}
}
@@ -1421,14 +1450,10 @@ dependencies_clauselist_selectivity(PlannerInfo *root,
/* not found in the list, so add it */
if (attnum == InvalidAttrNumber)
{
- attnum = EXPRESSION_ATTNUM(unique_exprs_cnt);
unique_exprs[unique_exprs_cnt++] = expr;
- /* shouldn't have seen this attnum yet */
- Assert(!bms_is_member(attnum, clauses_attnums));
-
- /* we may add the attnum repeatedly to clauses_attnums */
- clauses_attnums = bms_add_member(clauses_attnums, attnum);
+ /* after incrementing the value, to get -1, -2, ... */
+ attnum = -unique_exprs_cnt;
}
/* remember which attnum was assigned to this clause */
@@ -1439,6 +1464,37 @@ dependencies_clauselist_selectivity(PlannerInfo *root,
listidx++;
}
+ Assert(listidx == list_length(clauses));
+
+ /*
+ * Now that we know how many expressions there are, we can offset the
+ * values just enough to build the bitmapset.
+ */
+ for (i = 0; i < list_length(clauses); i++)
+ {
+ AttrNumber attnum;
+
+ /* ignore incompatible or already estimated clauses */
+ if (list_attnums[i] == InvalidAttrNumber)
+ continue;
+
+ /* make sure the attnum is in the expected range */
+ Assert(list_attnums[i] >= (-unique_exprs_cnt));
+ Assert(list_attnums[i] <= MaxHeapAttributeNumber);
+
+ /* make sure the attnum is not negative */
+ attnum = list_attnums[i] + unique_exprs_cnt;
+
+ /*
+ * Expressions are unique, and so we must not have seen this attnum
+ * before.
+ */
+ Assert(AttrNumberIsForUserDefinedAttr(list_attnums[i]) ||
+ !bms_is_member(attnum, clauses_attnums));
+
+ clauses_attnums = bms_add_member(clauses_attnums, attnum);
+ }
+
/*
* If there's not at least two distinct attnums and expressions, then
* reject the whole list of clauses. We must return 1.0 so the calling
@@ -1470,19 +1526,37 @@ dependencies_clauselist_selectivity(PlannerInfo *root,
foreach(l, rel->statlist)
{
StatisticExtInfo *stat = (StatisticExtInfo *) lfirst(l);
- Bitmapset *matched;
int nmatched;
int nexprs;
+ int k;
MVDependencies *deps;
/* skip statistics that are not of the correct type */
if (stat->kind != STATS_EXT_DEPENDENCIES)
continue;
- /* count matching simple clauses */
- matched = bms_intersect(clauses_attnums, stat->keys);
- nmatched = bms_num_members(matched);
- bms_free(matched);
+ /*
+ * Count matching attributes - we have to undo two attnum offsets.
+ * First, the dependency is offset using the number of expressions
+ * for that statistics, and then (if it's a plain attribute) we
+ * need to apply the same offset as above, by unique_exprs_cnt.
+ */
+ nmatched = 0;
+ k = -1;
+ while ((k = bms_next_member(stat->keys, k)) >= 0)
+ {
+ AttrNumber attnum = (AttrNumber) k;
+
+ /* skip expressions */
+ if (!AttrNumberIsForUserDefinedAttr(attnum))
+ continue;
+
+ /* apply the same offset as above */
+ attnum += unique_exprs_cnt;
+
+ if (bms_is_member(attnum, clauses_attnums))
+ nmatched++;
+ }
/* count matching expressions */
nexprs = 0;
@@ -1537,13 +1611,23 @@ dependencies_clauselist_selectivity(PlannerInfo *root,
Node *expr;
int k;
AttrNumber unique_attnum = InvalidAttrNumber;
+ AttrNumber attnum;
- /* regular attribute, no need to remap */
- if (dep->attributes[j] <= MaxHeapAttributeNumber)
+ /* undo the per-statistics offset */
+ attnum = dep->attributes[j];
+
+ /* regular attribute, simply offset by number of expressions */
+ if (AttrNumberIsForUserDefinedAttr(attnum))
+ {
+ dep->attributes[j] = attnum + unique_exprs_cnt;
continue;
+ }
+
+ /* the attnum should be a valid system attnum (-1, -2, ...) */
+ Assert(AttributeNumberIsValid(attnum));
/* index of the expression */
- idx = EXPRESSION_INDEX(dep->attributes[j]);
+ idx = (1 - attnum);
/* make sure the expression index is valid */
Assert((idx >= 0) && (idx < list_length(stat->exprs)));
@@ -1559,7 +1643,7 @@ dependencies_clauselist_selectivity(PlannerInfo *root,
*/
if (equal(unique_exprs[k], expr))
{
- unique_attnum = EXPRESSION_ATTNUM(k);
+ unique_attnum = -(k + 1) + unique_exprs_cnt;
break;
}
}
diff --git a/src/backend/statistics/extended_stats.c b/src/backend/statistics/extended_stats.c
index 6ed938d6ab..95b2cc683e 100644
--- a/src/backend/statistics/extended_stats.c
+++ b/src/backend/statistics/extended_stats.c
@@ -892,7 +892,7 @@ bsearch_arg(const void *key, const void *base, size_t nmemb, size_t size,
* is not necessary here (and when querying the bitmap).
*/
AttrNumber *
-build_attnums_array(Bitmapset *attrs, int *numattrs)
+build_attnums_array(Bitmapset *attrs, int nexprs, int *numattrs)
{
int i,
j;
@@ -908,16 +908,19 @@ build_attnums_array(Bitmapset *attrs, int *numattrs)
j = -1;
while ((j = bms_next_member(attrs, j)) >= 0)
{
+ AttrNumber attnum = (j - nexprs);
+
/*
* Make sure the bitmap contains only user-defined attributes. As
* bitmaps can't contain negative values, this can be violated in two
* ways. Firstly, the bitmap might contain 0 as a member, and secondly
* the integer value might be larger than MaxAttrNumber.
*/
- Assert(AttrNumberIsForUserDefinedAttr(j));
- Assert(j <= MaxAttrNumber);
+ Assert(AttributeNumberIsValid(attnum));
+ Assert(attnum <= MaxAttrNumber);
+ Assert(attnum >= (-nexprs));
- attnums[i++] = (AttrNumber) j;
+ attnums[i++] = (AttrNumber) attnum;
/* protect against overflows */
Assert(i <= num);
@@ -984,15 +987,16 @@ build_sorted_items(int numrows, int *nitems, HeapTuple *rows, ExprInfo *exprs,
Datum value;
bool isnull;
int attlen;
+ AttrNumber attnum = attnums[j];
- if (attnums[j] <= MaxHeapAttributeNumber)
+ if (AttrNumberIsForUserDefinedAttr(attnum))
{
- value = heap_getattr(rows[i], attnums[j], tdesc, &isnull);
- attlen = TupleDescAttr(tdesc, attnums[j] - 1)->attlen;
+ value = heap_getattr(rows[i], attnum, tdesc, &isnull);
+ attlen = TupleDescAttr(tdesc, attnum - 1)->attlen;
}
else
{
- int idx = EXPRESSION_INDEX(attnums[j]);
+ int idx = -(attnums[j] + 1);
Assert((idx >= 0) && (idx < exprs->nexprs));
@@ -1097,6 +1101,21 @@ stat_find_expression(StatisticExtInfo *stat, Node *expr)
return -1;
}
+static bool
+stat_covers_attributes(StatisticExtInfo *stat, Bitmapset *attnums)
+{
+ int k;
+
+ k = -1;
+ while ((k = bms_next_member(attnums, k)) >= 0)
+ {
+ if (!bms_is_member(k, stat->keys))
+ return false;
+ }
+
+ return true;
+}
+
/*
* stat_covers_expressions
* Test whether a statistics object covers all expressions in a list.
@@ -1181,7 +1200,7 @@ choose_best_statistics(List *stats, char requiredkind,
continue;
/* ignore clauses that are not covered by this object */
- if (!bms_is_subset(clause_attnums[i], info->keys) ||
+ if (!stat_covers_attributes(info, clause_attnums[i]) ||
!stat_covers_expressions(info, clause_exprs[i], &expr_idxs))
continue;
@@ -1685,7 +1704,7 @@ statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varReli
* estimate.
*/
if (!bms_is_member(listidx, *estimatedclauses) &&
- bms_is_subset(list_attnums[listidx], stat->keys) &&
+ stat_covers_attributes(stat, list_attnums[listidx]) &&
stat_covers_expressions(stat, list_exprs[listidx], NULL))
{
/* record simple clauses (single column or expression) */
@@ -2555,37 +2574,3 @@ evaluate_expressions(Relation rel, List *exprs, int numrows, HeapTuple *rows)
return result;
}
-
-/*
- * add_expressions_to_attributes
- * add expressions as attributes with high attnums
- *
- * Treat the expressions as attributes with attnums above the regular
- * attnum range. This will allow us to handle everything in the same
- * way, and identify expressions in the dependencies.
- *
- * XXX This always creates a copy of the bitmap. We might optimize this
- * by only creating the copy with (nexprs > 0) but then we'd have to track
- * this in order to free it (if we want to). Does not seem worth it.
- */
-Bitmapset *
-add_expressions_to_attributes(Bitmapset *attrs, int nexprs)
-{
- int i;
-
- /*
- * Copy the bitmapset and add fake attnums representing expressions,
- * starting above MaxHeapAttributeNumber.
- */
- attrs = bms_copy(attrs);
-
- /* start with (MaxHeapAttributeNumber + 1) */
- for (i = 0; i < nexprs; i++)
- {
- Assert(EXPRESSION_ATTNUM(i) > MaxHeapAttributeNumber);
-
- attrs = bms_add_member(attrs, EXPRESSION_ATTNUM(i));
- }
-
- return attrs;
-}
diff --git a/src/backend/statistics/mcv.c b/src/backend/statistics/mcv.c
index 3bb6fa733d..323d476814 100644
--- a/src/backend/statistics/mcv.c
+++ b/src/backend/statistics/mcv.c
@@ -187,6 +187,7 @@ statext_mcv_build(int numrows, HeapTuple *rows, ExprInfo *exprs,
double totalrows, int stattarget)
{
int i,
+ k,
numattrs,
ngroups,
nitems;
@@ -206,10 +207,26 @@ statext_mcv_build(int numrows, HeapTuple *rows, ExprInfo *exprs,
* XXX We do this after build_mss, because that expects the bitmapset
* to only contain simple attributes (with a matching VacAttrStats)
*/
- attrs = add_expressions_to_attributes(attrs, exprs->nexprs);
- /* now build the array, with the special expression attnums */
- attnums = build_attnums_array(attrs, &numattrs);
+ /*
+ * 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));
+
/* sort the rows */
items = build_sorted_items(numrows, &nitems, rows, exprs,
@@ -349,7 +366,6 @@ statext_mcv_build(int numrows, HeapTuple *rows, ExprInfo *exprs,
pfree(items);
pfree(groups);
- pfree(attrs);
return mcvlist;
}
@@ -1692,6 +1708,8 @@ mcv_get_match_bitmap(PlannerInfo *root, List *clauses,
bool match = true;
MCVItem *item = &mcvlist->items[i];
+ Assert(idx >= 0);
+
/*
* When the MCV item or the Const value is NULL we can
* treat this as a mismatch. We must not call the operator
diff --git a/src/backend/statistics/mvdistinct.c b/src/backend/statistics/mvdistinct.c
index 55d3fa0e1f..5e796e7123 100644
--- a/src/backend/statistics/mvdistinct.c
+++ b/src/backend/statistics/mvdistinct.c
@@ -83,9 +83,9 @@ static void generate_combinations(CombinationGenerator *state);
* This computes the ndistinct estimate using the same estimator used
* in analyze.c and then computes the coefficient.
*
- * To handle expressions easily, we treat them as special attributes with
- * attnums above MaxHeapAttributeNumber, and we assume the expressions are
- * placed after all simple attributes.
+ * To handle expressions easily, we treat them as system attributes with
+ * negative attnums, and offset everything by number of expressions to
+ * allow using Bitmapsets.
*/
MVNDistinct *
statext_ndistinct_build(double totalrows, int numrows, HeapTuple *rows,
@@ -93,10 +93,12 @@ statext_ndistinct_build(double totalrows, int numrows, HeapTuple *rows,
VacAttrStats **stats)
{
MVNDistinct *result;
+ int i;
int k;
int itemcnt;
int numattrs = bms_num_members(attrs);
int numcombs = num_combinations(numattrs + exprs->nexprs);
+ Bitmapset *tmp = NULL;
result = palloc(offsetof(MVNDistinct, items) +
numcombs * sizeof(MVNDistinctItem));
@@ -104,8 +106,26 @@ statext_ndistinct_build(double totalrows, int numrows, HeapTuple *rows,
result->type = STATS_NDISTINCT_TYPE_BASIC;
result->nitems = numcombs;
- /* treat expressions as special attributes with high attnums */
- attrs = add_expressions_to_attributes(attrs, exprs->nexprs);
+ /*
+ * 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);
@@ -124,29 +144,33 @@ statext_ndistinct_build(double totalrows, int numrows, HeapTuple *rows,
MVNDistinctItem *item = &result->items[itemcnt];
int j;
- item->attrs = NULL;
+ item->attributes = palloc(sizeof(AttrNumber) * k);
+ item->nattributes = k;
+
for (j = 0; j < k; j++)
{
AttrNumber attnum = InvalidAttrNumber;
/*
- * The simple attributes are before expressions, so have
- * indexes below numattrs.
- * */
- if (combination[j] < numattrs)
- attnum = stats[combination[j]]->attr->attnum;
+ * 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] - numattrs) >= 0);
- Assert((combination[j] - numattrs) < exprs->nexprs);
+ Assert(combination[j] >= 0);
+ Assert(combination[j] < exprs->nexprs);
- attnum = EXPRESSION_ATTNUM(combination[j] - numattrs);
+ attnum = -(combination[j] + 1);
}
Assert(attnum != InvalidAttrNumber);
- item->attrs = bms_add_member(item->attrs, attnum);
+ item->attributes[j] = attnum;
}
item->ndistinct =
@@ -223,7 +247,7 @@ statext_ndistinct_serialize(MVNDistinct *ndistinct)
{
int nmembers;
- nmembers = bms_num_members(ndistinct->items[i].attrs);
+ nmembers = ndistinct->items[i].nattributes;
Assert(nmembers >= 2);
len += SizeOfItem(nmembers);
@@ -248,22 +272,15 @@ statext_ndistinct_serialize(MVNDistinct *ndistinct)
for (i = 0; i < ndistinct->nitems; i++)
{
MVNDistinctItem item = ndistinct->items[i];
- int nmembers = bms_num_members(item.attrs);
- int x;
+ int nmembers = item.nattributes;
memcpy(tmp, &item.ndistinct, sizeof(double));
tmp += sizeof(double);
memcpy(tmp, &nmembers, sizeof(int));
tmp += sizeof(int);
- x = -1;
- while ((x = bms_next_member(item.attrs, x)) >= 0)
- {
- AttrNumber value = (AttrNumber) x;
-
- memcpy(tmp, &value, sizeof(AttrNumber));
- tmp += sizeof(AttrNumber);
- }
+ memcpy(tmp, item.attributes, sizeof(AttrNumber) * nmembers);
+ tmp += nmembers * sizeof(AttrNumber);
/* protect against overflows */
Assert(tmp <= ((char *) output + len));
@@ -335,27 +352,21 @@ statext_ndistinct_deserialize(bytea *data)
for (i = 0; i < ndistinct->nitems; i++)
{
MVNDistinctItem *item = &ndistinct->items[i];
- int nelems;
-
- item->attrs = NULL;
/* ndistinct value */
memcpy(&item->ndistinct, tmp, sizeof(double));
tmp += sizeof(double);
/* number of attributes */
- memcpy(&nelems, tmp, sizeof(int));
+ memcpy(&item->nattributes, tmp, sizeof(int));
tmp += sizeof(int);
- Assert((nelems >= 2) && (nelems <= STATS_MAX_DIMENSIONS));
+ Assert((item->nattributes >= 2) && (item->nattributes <= STATS_MAX_DIMENSIONS));
- while (nelems-- > 0)
- {
- AttrNumber attno;
+ item->attributes
+ = (AttrNumber *) palloc(item->nattributes * sizeof(AttrNumber));
- memcpy(&attno, tmp, sizeof(AttrNumber));
- tmp += sizeof(AttrNumber);
- item->attrs = bms_add_member(item->attrs, attno);
- }
+ memcpy(item->attributes, tmp, sizeof(AttrNumber) * item->nattributes);
+ tmp += sizeof(AttrNumber) * item->nattributes;
/* still within the bytea */
Assert(tmp <= ((char *) data + VARSIZE_ANY(data)));
@@ -403,17 +414,16 @@ pg_ndistinct_out(PG_FUNCTION_ARGS)
for (i = 0; i < ndist->nitems; i++)
{
- MVNDistinctItem item = ndist->items[i];
- int x = -1;
- bool first = true;
+ int j;
+ MVNDistinctItem item = ndist->items[i];
if (i > 0)
appendStringInfoString(&str, ", ");
- while ((x = bms_next_member(item.attrs, x)) >= 0)
+ for (j = 0; j < item.nattributes; j++)
{
- appendStringInfo(&str, "%s%d", first ? "\"" : ", ", x);
- first = false;
+ AttrNumber attnum = item.attributes[j];
+ appendStringInfo(&str, "%s%d", (j == 0) ? "\"" : ", ", attnum);
}
appendStringInfo(&str, "\": %d", (int) item.ndistinct);
}
@@ -508,9 +518,10 @@ ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows,
TupleDesc tdesc = NULL;
Oid collid = InvalidOid;
- if (combination[i] < nattrs)
+ /* first nexprs indexes are for expressions, then regular attributes */
+ if (combination[i] >= exprs->nexprs)
{
- VacAttrStats *colstat = stats[combination[i]];
+ VacAttrStats *colstat = stats[combination[i] - exprs->nexprs];
typid = colstat->attrtypid;
attnum = colstat->attr->attnum;
collid = colstat->attrcollid;
@@ -518,8 +529,8 @@ ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows,
}
else
{
- typid = exprs->types[combination[i] - nattrs];
- collid = exprs->collations[combination[i] - nattrs];
+ typid = exprs->types[combination[i]];
+ collid = exprs->collations[combination[i]];
}
type = lookup_type_cache(typid, TYPECACHE_LT_OPR);
@@ -534,10 +545,13 @@ ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows,
for (j = 0; j < numrows; j++)
{
/*
- * The first nattrs indexes identify simple attributes, higher
- * indexes are expressions.
+ * 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] < nattrs)
+ if (combination[i] >= exprs->nexprs)
items[j].values[i] =
heap_getattr(rows[j],
attnum,
@@ -545,7 +559,9 @@ ndistinct_for_combination(double totalrows, int numrows, HeapTuple *rows,
&items[j].isnull[i]);
else
{
- int idx = (combination[i] - nattrs);
+ /* 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));
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index a7edcaeaff..26e1912940 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -4144,7 +4144,8 @@ estimate_multivariate_ndistinct(PlannerInfo *root, RelOptInfo *rel,
if (equal(exprinfo->expr, expr))
{
- matched = bms_add_member(matched, MaxHeapAttributeNumber + idx);
+ AttrNumber attnum = -(idx + 1);
+ matched = bms_add_member(matched, attnum + list_length(matched_info->exprs));
found = true;
break;
}
@@ -4165,10 +4166,10 @@ estimate_multivariate_ndistinct(PlannerInfo *root, RelOptInfo *rel,
if (!AttrNumberIsForUserDefinedAttr(attnum))
continue;
- if (!bms_is_member(attnum, matched_info->keys))
+ if (!bms_is_member(attnum + list_length(matched_info->exprs), matched_info->keys))
continue;
- matched = bms_add_member(matched, attnum);
+ matched = bms_add_member(matched, attnum + list_length(matched_info->exprs));
}
}
}
@@ -4176,13 +4177,29 @@ estimate_multivariate_ndistinct(PlannerInfo *root, RelOptInfo *rel,
/* Find the specific item that exactly matches the combination */
for (i = 0; i < stats->nitems; i++)
{
+ int j;
MVNDistinctItem *tmpitem = &stats->items[i];
- if (bms_subset_compare(tmpitem->attrs, matched) == BMS_EQUAL)
+ if (tmpitem->nattributes != bms_num_members(matched))
+ continue;
+
+ /* assume it's the right item */
+ item = tmpitem;
+
+ for (j = 0; j < tmpitem->nattributes; j++)
{
- item = tmpitem;
- break;
+ AttrNumber attnum = tmpitem->attributes[j];
+
+ if (!bms_is_member(attnum, matched))
+ {
+ /* nah, it's not this item */
+ item = NULL;
+ break;
+ }
}
+
+ if (item)
+ break;
}
/* make sure we found an item */
diff --git a/src/include/statistics/extended_stats_internal.h b/src/include/statistics/extended_stats_internal.h
index b2e59f9bc5..1f09799deb 100644
--- a/src/include/statistics/extended_stats_internal.h
+++ b/src/include/statistics/extended_stats_internal.h
@@ -106,7 +106,7 @@ extern void *bsearch_arg(const void *key, const void *base,
int (*compar) (const void *, const void *, void *),
void *arg);
-extern AttrNumber *build_attnums_array(Bitmapset *attrs, int *numattrs);
+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,
@@ -141,13 +141,4 @@ extern Selectivity mcv_clause_selectivity_or(PlannerInfo *root,
Selectivity *overlap_basesel,
Selectivity *totalsel);
-extern Bitmapset *add_expressions_to_attributes(Bitmapset *attrs, int nexprs);
-
-/* translate 0-based expression index to attnum and back */
-#define EXPRESSION_ATTNUM(index) \
- (MaxHeapAttributeNumber + (index) + 1)
-
-#define EXPRESSION_INDEX(attnum) \
- ((attnum) - MaxHeapAttributeNumber - 1)
-
#endif /* EXTENDED_STATS_INTERNAL_H */
diff --git a/src/include/statistics/statistics.h b/src/include/statistics/statistics.h
index 006d578e0c..326cf26fea 100644
--- a/src/include/statistics/statistics.h
+++ b/src/include/statistics/statistics.h
@@ -26,7 +26,8 @@
typedef struct MVNDistinctItem
{
double ndistinct; /* ndistinct value for this combination */
- Bitmapset *attrs; /* attr numbers of items */
+ int nattributes; /* number of attributes */
+ AttrNumber *attributes; /* attribute numbers */
} MVNDistinctItem;
/* A MVNDistinct object, comprising all possible combinations of columns */
--
2.26.2
--------------614DDB87AFFED893713AC0E9
Content-Type: text/x-patch; charset=UTF-8;
name="0005-WIP-unify-handling-of-attributes-and-expres-20210304.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="0005-WIP-unify-handling-of-attributes-and-expres-20210304.pa";
filename*1="tch"
^ permalink raw reply [nested|flat] 3+ messages in thread
* Using read stream in autoprewarm
@ 2024-08-08 07:32 Nazir Bilal Yavuz <[email protected]>
0 siblings, 1 reply; 3+ messages in thread
From: Nazir Bilal Yavuz @ 2024-08-08 07:32 UTC (permalink / raw)
To: PostgreSQL Hackers <[email protected]>
Hi,
I am working on using the read stream in autoprewarm. I observed ~10%
performance gain with this change. The patch is attached.
The downside of the read stream approach is that a new read stream
object needs to be created for each database, relation and fork. I was
wondering if this would cause a regression but it did not (at least
depending on results of my testing). Another downside could be the
code getting complicated.
For the testing,
- I created 50 databases with each of them having 50 tables and the
size of the tables are 520KB.
- patched: 51157 ms
- master: 56769 ms
- I created 5 databases with each of them having 1 table and the size
of the tables are 3GB.
- patched: 32679 ms
- master: 36706 ms
I put debugging message with timing information in
autoprewarm_database_main() function, then run autoprewarm 100 times
(by restarting the server) and cleared the OS cache before each
restart. Also, I ensured that the block number of the buffer returning
from the read stream API is correct. I am not sure if that much
testing is enough for this kind of change.
Any feedback would be appreciated.
--
Regards,
Nazir Bilal Yavuz
Microsoft
Attachments:
[text/x-patch] v1-0001-Use-read-stream-in-autoprewarm.patch (5.4K, ../../CAN55FZ3n8Gd+hajbL=5UkGzu_aHGRqnn+xktXq2fuds=1AOR6Q@mail.gmail.com/2-v1-0001-Use-read-stream-in-autoprewarm.patch)
download | inline diff:
From c5e286612912ba6840d967812171162a948153e4 Mon Sep 17 00:00:00 2001
From: Nazir Bilal Yavuz <[email protected]>
Date: Wed, 7 Aug 2024 17:27:50 +0300
Subject: [PATCH v1] Use read stream in autoprewarm
Instead of reading blocks with ReadBufferExtended(), create read stream
object for each possible case and use it.
This change provides about 10% performance improvement.
---
contrib/pg_prewarm/autoprewarm.c | 102 +++++++++++++++++++++++++++++--
1 file changed, 97 insertions(+), 5 deletions(-)
diff --git a/contrib/pg_prewarm/autoprewarm.c b/contrib/pg_prewarm/autoprewarm.c
index d061731706a..96e93c46f85 100644
--- a/contrib/pg_prewarm/autoprewarm.c
+++ b/contrib/pg_prewarm/autoprewarm.c
@@ -44,6 +44,7 @@
#include "storage/lwlock.h"
#include "storage/proc.h"
#include "storage/procsignal.h"
+#include "storage/read_stream.h"
#include "storage/shmem.h"
#include "storage/smgr.h"
#include "tcop/tcopprot.h"
@@ -429,6 +430,58 @@ apw_load_buffers(void)
apw_state->prewarmed_blocks, num_elements)));
}
+struct apw_read_stream_private
+{
+ bool first_block;
+ int max_pos;
+ int pos;
+ BlockInfoRecord *block_info;
+ BlockNumber nblocks_in_fork;
+
+};
+
+static BlockNumber
+apw_read_stream_next_block(ReadStream *stream,
+ void *callback_private_data,
+ void *per_buffer_data)
+{
+ struct apw_read_stream_private *p = callback_private_data;
+ bool *rs_have_free_buffer = per_buffer_data;
+ BlockInfoRecord *old_blk;
+ BlockInfoRecord *cur_blk;
+
+ *rs_have_free_buffer = true;
+
+ if (!have_free_buffer())
+ {
+ *rs_have_free_buffer = false;
+ return InvalidBlockNumber;
+ }
+
+ if (p->pos == p->max_pos)
+ return InvalidBlockNumber;
+
+ if (p->first_block)
+ {
+ p->first_block = false;
+ return p->block_info[p->pos++].blocknum;
+ }
+
+ old_blk = &(p->block_info[p->pos - 1]);
+ cur_blk = &(p->block_info[p->pos]);
+
+ if (old_blk->database == cur_blk->database &&
+ old_blk->forknum == cur_blk->forknum &&
+ old_blk->filenumber == cur_blk->filenumber &&
+ cur_blk->blocknum < p->nblocks_in_fork)
+ {
+ p->pos++;
+ return cur_blk->blocknum;
+ }
+
+ return InvalidBlockNumber;
+}
+
/*
* Prewarm all blocks for one database (and possibly also global objects, if
* those got grouped with this database).
@@ -442,6 +495,9 @@ autoprewarm_database_main(Datum main_arg)
BlockNumber nblocks = 0;
BlockInfoRecord *old_blk = NULL;
dsm_segment *seg;
+ ReadStream *stream = NULL;
+ struct apw_read_stream_private p;
+ bool *rs_have_free_buffer;
/* Establish signal handlers; once that's done, unblock signals. */
pqsignal(SIGTERM, die);
@@ -458,13 +514,16 @@ autoprewarm_database_main(Datum main_arg)
block_info = (BlockInfoRecord *) dsm_segment_address(seg);
pos = apw_state->prewarm_start_idx;
+ p.block_info = block_info;
+ p.max_pos = apw_state->prewarm_stop_idx;
+
/*
* Loop until we run out of blocks to prewarm or until we run out of free
* buffers.
*/
- while (pos < apw_state->prewarm_stop_idx && have_free_buffer())
+ for (; pos < apw_state->prewarm_stop_idx; pos++)
{
- BlockInfoRecord *blk = &block_info[pos++];
+ BlockInfoRecord *blk = &block_info[pos];
Buffer buf;
CHECK_FOR_INTERRUPTS();
@@ -477,6 +536,18 @@ autoprewarm_database_main(Datum main_arg)
old_blk->database != 0)
break;
+ /*
+ * If stream needs to be created again, end it before closing the old
+ * relation.
+ */
+ if (stream && (old_blk == NULL ||
+ old_blk->filenumber != blk->filenumber ||
+ old_blk->forknum != blk->forknum))
+ {
+ Assert(read_stream_next_buffer(stream, (void **) &rs_have_free_buffer) == InvalidBuffer);
+ read_stream_end(stream);
+ }
+
/*
* As soon as we encounter a block of a new relation, close the old
* relation. Note that rel will be NULL if try_relation_open failed
@@ -513,7 +584,10 @@ autoprewarm_database_main(Datum main_arg)
continue;
}
- /* Once per fork, check for fork existence and size. */
+ /*
+ * Once per fork, check for fork existence and size. Then create read
+ * stream if it is suitable.
+ */
if (old_blk == NULL ||
old_blk->filenumber != blk->filenumber ||
old_blk->forknum != blk->forknum)
@@ -525,7 +599,21 @@ autoprewarm_database_main(Datum main_arg)
if (blk->forknum > InvalidForkNumber &&
blk->forknum <= MAX_FORKNUM &&
smgrexists(RelationGetSmgr(rel), blk->forknum))
+ {
nblocks = RelationGetNumberOfBlocksInFork(rel, blk->forknum);
+
+ /* Create read stream. */
+ p.nblocks_in_fork = nblocks;
+ p.pos = pos;
+ p.first_block = true;
+ stream = read_stream_begin_relation(READ_STREAM_FULL,
+ NULL,
+ rel,
+ blk->forknum,
+ apw_read_stream_next_block,
+ &p,
+ sizeof(bool));
+ }
else
nblocks = 0;
}
@@ -539,16 +627,20 @@ autoprewarm_database_main(Datum main_arg)
}
/* Prewarm buffer. */
- buf = ReadBufferExtended(rel, blk->forknum, blk->blocknum, RBM_NORMAL,
- NULL);
+ buf = read_stream_next_buffer(stream, (void **) &rs_have_free_buffer);
if (BufferIsValid(buf))
{
apw_state->prewarmed_blocks++;
ReleaseBuffer(buf);
}
+ /* There are no free buffers left in shared buffers, break the loop. */
+ else if (!(*rs_have_free_buffer))
+ break;
old_blk = blk;
}
+ Assert(read_stream_next_buffer(stream, (void **) &rs_have_free_buffer) == InvalidBuffer);
+ read_stream_end(stream);
dsm_detach(seg);
--
2.45.2
^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: Using read stream in autoprewarm
@ 2024-11-27 13:50 Matheus Alcantara <[email protected]>
parent: Nazir Bilal Yavuz <[email protected]>
0 siblings, 0 replies; 3+ messages in thread
From: Matheus Alcantara @ 2024-11-27 13:50 UTC (permalink / raw)
To: Nazir Bilal Yavuz <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]>
Hi,
Newer reviewer here, trying to understand more about the read stream API.
On Tuesday, November 26th, 2024 at 11:07 AM, Nazir Bilal Yavuz <[email protected]> wrote:
> Any feedback would be appreciated.
I've executed the same test of 5 databases with each of them having 1 table of
3GB of size and I've got very similar results.
I've also tested using a single database with 4 tables with ~60GB of size and
the results compared with master was more closer but still an improvement. Note
that I've also increased the default shared_buffers to 7GB to see how it works
with large buffer pools.
- patched: 5.4259 s
- master: 5.53186 s
Not to much to say about the code, I'm currently learning more about the read
stream API and Postgresql hacking itself. Just some minor points and questions
about the patches.
v2-0002-Count-free-buffers-at-the-start-of-the-autoprewar.patch
--- a/src/backend/storage/buffer/freelist.c
+/*
+ * get_number_of_free_buffers -- a lockless way to get the number of free
+ * buffers in buffer pool.
+ *
+ * Note that result continuosly changes as free buffers are moved out by other
+ * operations.
+ */
+int
+get_number_of_free_buffers(void)
typo on continuosly -> continuously
v2-0001-Use-read-stream-in-autoprewarm.patch
+ bool *rs_have_free_buffer = per_buffer_data;
+
+
+ *rs_have_free_buffer = true;
+
Not sure if I understand why this variable is needed, it seems that it is only
written and never read? Just as comparison, the block_range_read_stream_cb
callback used on pg_prewarm seems to not use the per_buffer_data parameter.
--
Matheus Alcantara
EDB: https://www.enterprisedb.com
^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2024-11-27 13:50 UTC | newest]
Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2021-02-17 00:02 [PATCH 4/5] WIP rework tracking of expressions Tomas Vondra <[email protected]>
2024-08-08 07:32 Using read stream in autoprewarm Nazir Bilal Yavuz <[email protected]>
2024-11-27 13:50 ` Re: Using read stream in autoprewarm Matheus Alcantara <[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