public inbox for [email protected]help / color / mirror / Atom feed
[PATCH 7/8] patched 2 2+ messages / 2 participants [nested] [flat]
* [PATCH 7/8] patched 2 @ 2021-01-21 23:12 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 2+ 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] 2+ messages in thread
* Re: cutting down the TODO list thread @ 2023-05-16 08:50 Alvaro Herrera <[email protected]> 0 siblings, 0 replies; 2+ messages in thread From: Alvaro Herrera @ 2023-05-16 08:50 UTC (permalink / raw) To: John Naylor <[email protected]>; +Cc: PostgreSQL Hackers <[email protected]> On 2023-May-13, John Naylor wrote: > -------------------- > 2. Propose to move to the "Not Wanted list": > Consider having single-page pruning update the visibility map > -> Comment from Heikki in the thread: > "I think I was worried about the possible performance impact of having to > clear the bit in visibility map again. If you're frequently updating a > tuple so that HOT and page pruning is helping you, setting the bit in > visibility map seems counter-productive; it's going to be cleared soon > again by another UPDATE. That's just a hunch, though. Maybe the overhead > is negligible." Hmm, I agree with removing the entry from the TODO list, but why is this something we Do Not Want? If somebody shows up and do some analysis that in a certain workload it is beneficial to do this, then I don't think we should turn them down. -- Álvaro Herrera PostgreSQL Developer — https://www.EnterpriseDB.com/ ^ permalink raw reply [nested|flat] 2+ messages in thread
end of thread, other threads:[~2023-05-16 08:50 UTC | newest] Thread overview: 2+ 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]> 2023-05-16 08:50 Re: cutting down the TODO list thread Alvaro Herrera <[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