($INBOX_DIR/description missing)
help / color / mirror / Atom feedFrom: Tomas Vondra <[email protected]>
Subject: [PATCH 7/8] patched 2
Date: Fri, 22 Jan 2021 00:12:00 +0100
---
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"
view thread (22+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected]
Subject: Re: [PATCH 7/8] patched 2
In-Reply-To: <no-message-id-1865077@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox