($INBOX_DIR/description missing)help / color / mirror / Atom feed
[PATCH 7/8] patched 2 22+ messages / 2 participants [nested] [flat]
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Tomas Vondra @ 2021-01-21 23:12 UTC (permalink / raw) --- src/backend/access/brin/brin_minmax_multi.c | 284 +++++++++++++------- 1 file changed, 189 insertions(+), 95 deletions(-) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index 6ef5c5f2bf..094ecd2be9 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -90,6 +90,7 @@ */ #define PROCNUM_BASE 11 +#define MINMAX_LOAD_FACTOR 0.75 typedef struct MinmaxMultiOpaque { @@ -160,11 +161,11 @@ typedef struct Ranges } Ranges; /* - * On-disk the summary is stored as a bytea value, represented by the - * SerializedRanges structure. It has a 4B varlena header, so can treated - * as varlena directly. + * On-disk the summary is stored as a bytea value, with a simple header + * with basic metadata, followed by the boundary values. It has a varlena + * header, so can be treated as varlena directly. * - * See range_serialize/range_deserialize methods for serialization details. + * See range_serialize/range_deserialize for serialization details. */ typedef struct SerializedRanges { @@ -483,6 +484,32 @@ compare_combine_ranges(const void *a, const void *b, void *arg) return 0; } +/* + * compare_values + * Compare the values. + */ +static int +compare_values(const void *a, const void *b, void *arg) +{ + Datum *da = (Datum *) a; + Datum *db = (Datum *) b; + Datum r; + + compare_context *cxt = (compare_context *) arg; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db); + + if (DatumGetBool(r)) + return -1; + + r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da); + + if (DatumGetBool(r)) + return 1; + + return 0; +} + /* * range_contains_value * See if the new value is already contained in the range list. @@ -923,6 +950,8 @@ typedef struct DistanceValue /* * Simple comparator for distance values, comparing the double value. + * This is intentionally sorting the distances in descending order, i.e. + * the longer gaps will be at the front. */ static int compare_distances(const void *a, const void *b) @@ -931,9 +960,9 @@ compare_distances(const void *a, const void *b) DistanceValue *db = (DistanceValue *)b; if (da->value < db->value) - return -1; - else if (da->value > db->value) return 1; + else if (da->value > db->value) + return -1; return 0; } @@ -942,8 +971,8 @@ compare_distances(const void *a, const void *b) * Given an array of combine ranges, compute distance of the gaps betwen * the ranges - for ncranges there are (ncranges-1) gaps. * - * We simply call the "distance" function to compute the (min-max) for pairs - * of consecutive ganges. The function may be fairly expensive, so we do that + * We simply call the "distance" function to compute the (max-min) for pairs + * of consecutive ranges. The function may be fairly expensive, so we do that * just once (and then use it to pick as many ranges to merge as possible). * * See reduce_combine_ranges for details. @@ -970,16 +999,20 @@ build_distances(FmgrInfo *distanceFn, Oid colloid, a1 = cranges[i].maxval; a2 = cranges[i+1].minval; - /* compute length of the empty gap (distance between max/min) */ + /* compute length of the gap (between max/min) */ r = FunctionCall2Coll(distanceFn, colloid, a1, a2); - /* remember the index */ + /* remember the index of the gap the distance is for */ distances[i].index = i; distances[i].value = DatumGetFloat8(r); } - /* sort the distances in ascending order */ - pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), compare_distances); + /* + * Sort the distances in descending order, so that the longest gaps + * are at the front. + */ + pg_qsort(distances, (ncranges-1), sizeof(DistanceValue), + compare_distances); return distances; } @@ -1017,6 +1050,7 @@ build_combine_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges, return cranges; } +#ifdef USE_ASSERT_CHECKING /* * Counts bondary values needed to store the ranges. Each single-point * range is stored using a single value, each regular range needs two. @@ -1038,10 +1072,26 @@ count_values(CombineRange *cranges, int ncranges) return count; } +#endif /* - * Combines ranges until the number of boundary values drops below 75% - * of the capacity (as set by values_per_range reloption). + * reduce_combine_ranges + * reduce the ranges until the number of values is low enough + * + * Combines ranges until the number of boundary values drops below the + * threshold specified by max_values. This happens by merging enough + * ranges by distance between them. + * + * Returns the number of result ranges. + * + * We simply use the global min/max and then add boundaries for enough + * largest gaps. Each gap adds 2 values, so we simply use (target/2-1) + * distances. Then we simply sort all the values - each two values are + * a boundary of a range (possibly collapsed). + * + * XXX Some of the ranges may be collapsed (i.e. the min/max values are + * equal), but we ignore that for now. We could repeat the process, + * adding a couple more gaps recursively. * * XXX The ranges to merge are selected solely using the distance. But * that may not be the best strategy, for example when multiple gaps @@ -1062,66 +1112,86 @@ count_values(CombineRange *cranges, int ncranges) * length of the ranges? Or perhaps randomize the choice of ranges, with * probability inversely proportional to the distance (the gap lengths * may be very close, but not exactly the same). + * + * XXX Or maybe we could just handle this by using random value as a + * tie-break, or by adding random noise to the actual distance. */ static int reduce_combine_ranges(CombineRange *cranges, int ncranges, - DistanceValue *distances, int max_values) + DistanceValue *distances, int max_values, + FmgrInfo *cmp, Oid colloid) { int i; + int nvalues; + Datum *values; + + compare_context cxt; + + /* total number of gaps between ranges */ int ndistances = (ncranges - 1); - int count = count_values(cranges, ncranges); + + /* number of gaps to keep */ + int keep = (max_values/2 - 1); /* - * We have one fewer 'gaps' than the ranges. We'll be decrementing - * the number of combine ranges (reduction is the primary goal of - * this function), so we must use a separate value. + * Maybe we have sufficiently low number of ranges already? + * + * XXX This should happen before we actually do the expensive stuff + * like sorting, so maybe this should be just an assert. */ - for (i = 0; i < ndistances; i++) - { - int j; - int shortest; + if (keep >= ndistances) + return ncranges; - if (count <= max_values * 0.75) - break; + /* sort the values */ + cxt.colloid = colloid; + cxt.cmpFn = cmp; - shortest = distances[i].index; + /* allocate space for the boundary values */ + nvalues = 0; + values = (Datum *) palloc(sizeof(Datum) * max_values); - /* - * The index must be still valid with respect to the current size - * of cranges array (and it always points to the first range, so - * never to the last one - hence the -1 in the condition). - */ - Assert(shortest < (ncranges - 1)); + /* add the global min/max values, from the first/last range */ + values[nvalues++] = cranges[0].minval; + values[nvalues++] = cranges[ncranges-1].maxval; - if (!cranges[shortest].collapsed && !cranges[shortest+1].collapsed) - count -= 2; - else if (!cranges[shortest].collapsed || !cranges[shortest+1].collapsed) - count -= 1; + /* add boundary values for enough gaps */ + for (i = 0; i < keep; i++) + { + /* index of the gap between (index) and (index+1) ranges */ + int index = distances[i].index; - /* - * Move the values to join the two selected ranges. The new range is - * definiely not collapsed but a regular range. - */ - cranges[shortest].maxval = cranges[shortest+1].maxval; - cranges[shortest].collapsed = false; + Assert((index >= 0) && ((index+1) < ncranges)); - /* shuffle the subsequent combine ranges */ - memmove(&cranges[shortest+1], &cranges[shortest+2], - (ncranges - shortest - 2) * sizeof(CombineRange)); + /* add min from the preceding range, max from the next one */ + values[nvalues++] = cranges[index].minval; + values[nvalues++] = cranges[index+1].minval; - /* also, shuffle all higher indexes (we've just moved the ranges) */ - for (j = i; j < ndistances; j++) - { - if (distances[j].index > shortest) - distances[j].index--; - } + Assert(nvalues <= max_values); + } - ncranges--; + /* We should have even number of range values. */ + Assert(nvalues % 2 == 0); + + /* + * Sort the values using the comparator function, and form ranges + * from the sorted result. + */ + qsort_arg(values, nvalues, sizeof(Datum), + compare_values, (void *) &cxt); - Assert(ncranges > 0); + /* We have nvalues boundary values, which means nvalues/2 ranges. */ + for (i = 0; i < (nvalues / 2); i++) + { + cranges[i].minval = values[2*i]; + cranges[i].maxval = values[2*i + 1]; + + /* if the boundary values are the same, it's a collapsed range */ + cranges[i].collapsed = (compare_values(&values[2*i], + &values[2*i+1], + &cxt) == 0); } - return ncranges; + return (nvalues / 2); } /* @@ -1251,43 +1321,58 @@ range_add_value(BrinDesc *bdesc, Oid colloid, AssertArrayOrder(cmpFn, colloid, &ranges->values[ranges->nranges*2], ranges->nvalues); - /* and we'll also need the 'distance' procedure */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + /* OK build the combine ranges */ + cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); - /* - * The distanceFn calls (which may internally call e.g. numeric_le) may - * allocate quite a bit of memory, and we must not leak it. Otherwise - * we'd have problems e.g. when building indexes. So we create a local - * memory context and make sure we free the memory before leaving this - * function (not after every call). - */ - ctx = AllocSetContextCreate(CurrentMemoryContext, - "minmax-multi context", - ALLOCSET_DEFAULT_SIZES); + /* Reduce the ranges if needed */ + if (ncranges > ranges->maxvalues) + { + /* and we'll also need the 'distance' procedure */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - oldctx = MemoryContextSwitchTo(ctx); + /* + * The distanceFn calls (which may internally call e.g. numeric_le) may + * allocate quite a bit of memory, and we must not leak it. Otherwise + * we'd have problems e.g. when building indexes. So we create a local + * memory context and make sure we free the memory before leaving this + * function (not after every call). + */ + ctx = AllocSetContextCreate(CurrentMemoryContext, + "minmax-multi context", + ALLOCSET_DEFAULT_SIZES); - /* OK build the combine ranges */ - cranges = build_combine_ranges(cmpFn, colloid, ranges, newval, &ncranges); + oldctx = MemoryContextSwitchTo(ctx); - /* build array of gap distances and sort them in ascending order */ - distances = build_distances(distanceFn, colloid, cranges, ncranges); + /* build array of gap distances and sort them in ascending order */ + distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * Combine ranges until we release at least 25% of the space. This - * threshold is somewhat arbitrary, perhaps needs tuning. We must not - * use too low or high value. - */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges->maxvalues); + /* + * Combine ranges until we release at least 25% of the space. This + * threshold is somewhat arbitrary, perhaps needs tuning. We must not + * use too low or high value. + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges->maxvalues * MINMAX_LOAD_FACTOR, + cmpFn, colloid); - Assert(count_values(cranges, ncranges) <= ranges->maxvalues * 0.75); + Assert(count_values(cranges, ncranges) <= ranges->maxvalues * MINMAX_LOAD_FACTOR); - /* decompose the combine ranges into regular ranges and single values */ - store_combine_ranges(ranges, cranges, ncranges); + /* decompose the combine ranges into regular ranges and single values */ + store_combine_ranges(ranges, cranges, ncranges); - MemoryContextSwitchTo(oldctx); - MemoryContextDelete(ctx); + MemoryContextSwitchTo(oldctx); + MemoryContextDelete(ctx); + } + else + /* + * This seems like a fairly expensive thing, maybe we could just + * modify the ranges directly, instead of building cranges and + * decomposing them again? + */ + store_combine_ranges(ranges, cranges, ncranges); + + /* combine ranges were allocated outside the memory context */ + pfree(cranges); /* Check the ordering invariants are not violated (for both parts). */ AssertArrayOrder(cmpFn, colloid, ranges->values, ranges->nranges*2); @@ -1795,7 +1880,7 @@ brin_minmax_multi_add_value(PG_FUNCTION_ARGS) /* * Try to add the new value to the range. We need to update the modified - * flag, so that we serialize the correct value. + * flag, so that we serialize the updated summary later. */ modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval); @@ -2066,19 +2151,28 @@ brin_minmax_multi_union(PG_FUNCTION_ARGS) /* check that the combine ranges are correct (no overlaps, ordering) */ AssertValidCombineRanges(bdesc, colloid, attno, attr, cranges, ncranges); - /* build array of gap distances and sort them in ascending order */ - distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); - distances = build_distances(distanceFn, colloid, cranges, ncranges); - /* - * See how many values would be needed to store the current ranges, and if - * needed combine as many off them to get below the maxvalues threshold. - * The collapsed ranges will be stored as a single value. - * - * XXX The maxvalues may be different, so perhaps use Max? + * If needed, reduce some of the ranges. This may be fairly expensive, + * so only do that when necessary (when we have too many ranges). */ - ncranges = reduce_combine_ranges(cranges, ncranges, distances, - ranges_a->maxvalues); + if (ncranges > ranges_a->maxvalues) + { + /* build array of gap distances and sort them in ascending order */ + distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE); + distances = build_distances(distanceFn, colloid, cranges, ncranges); + + /* + * See how many values would be needed to store the current ranges, + * and if needed combine as many off them to get below the threshold. + * The collapsed ranges will be stored as a single value. + * + * XXX Can the maxvalues be different in the two ranges? Perhaps + * we should use maximum of those? + */ + ncranges = reduce_combine_ranges(cranges, ncranges, distances, + ranges_a->maxvalues, + cmpFn, colloid); + } /* update the first range summary */ store_combine_ranges(ranges_a, cranges, ncranges); -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0008-batch-build-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0008-batch-build-20210122.patch" ^ permalink raw reply [nested|flat] 22+ messages in thread
* RE: PostgreSQL 17 Release Management Team & Feature Freeze @ 2024-03-18 03:49 Hayato Kuroda (Fujitsu) <[email protected]> 0 siblings, 0 replies; 22+ messages in thread From: Hayato Kuroda (Fujitsu) @ 2024-03-18 03:49 UTC (permalink / raw) To: 'Michael Paquier' <[email protected]>; +Cc: Heikki Linnakangas <[email protected]>; Robert Haas <[email protected]>; Postgres hackers <[email protected]> Dear Michael, > We are pleased to announce the Release Management Team (RMT) (cc'd) > for the PostgreSQL 17 release: > - Robert Haas > - Heikki Linnakangas > - Michael Paquier Thanks for managing the release of PostgreSQL to proceed the right direction! > You can track open items for the PostgreSQL 17 release here: > https://wiki.postgresql.org/wiki/PostgreSQL_17_Open_Items I think the entry can be closed: ``` pg_upgrade with --link mode failing upgrade of publishers Commit: 29d0a77fa660 Owner: Amit Kapila ``` The reported failure was only related with the test script, not the feature. The issue has already been analyzed and the fix patch was pushed as f17529b710. Best Regards, Hayato Kuroda FUJITSU LIMITED https://www.fujitsu.com/ ^ permalink raw reply [nested|flat] 22+ messages in thread
end of thread, other threads:[~2024-03-18 03:49 UTC | newest] Thread overview: 22+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2021-01-21 23:12 [PATCH 7/8] patched 2 Tomas Vondra <[email protected]> 2024-03-18 03:49 RE: PostgreSQL 17 Release Management Team & Feature Freeze Hayato Kuroda (Fujitsu) <[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