Age Owner Branch data TLA Line data Source code
1 : : /*
2 : : * brin_minmax_multi.c
3 : : * Implementation of Multi Min/Max opclass for BRIN
4 : : *
5 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
6 : : * Portions Copyright (c) 1994, Regents of the University of California
7 : : *
8 : : *
9 : : * Implements a variant of minmax opclass, where the summary is composed of
10 : : * multiple smaller intervals. This allows us to handle outliers, which
11 : : * usually make the simple minmax opclass inefficient.
12 : : *
13 : : * Consider for example page range with simple minmax interval [1000,2000],
14 : : * and assume a new row gets inserted into the range with value 1000000.
15 : : * Due to that the interval gets [1000,1000000]. I.e. the minmax interval
16 : : * got 1000x wider and won't be useful to eliminate scan keys between 2001
17 : : * and 1000000.
18 : : *
19 : : * With minmax-multi opclass, we may have [1000,2000] interval initially,
20 : : * but after adding the new row we start tracking it as two interval:
21 : : *
22 : : * [1000,2000] and [1000000,1000000]
23 : : *
24 : : * This allows us to still eliminate the page range when the scan keys hit
25 : : * the gap between 2000 and 1000000, making it useful in cases when the
26 : : * simple minmax opclass gets inefficient.
27 : : *
28 : : * The number of intervals tracked per page range is somewhat flexible.
29 : : * What is restricted is the number of values per page range, and the limit
30 : : * is currently 32 (see values_per_range reloption). Collapsed intervals
31 : : * (with equal minimum and maximum value) are stored as a single value,
32 : : * while regular intervals require two values.
33 : : *
34 : : * When the number of values gets too high (by adding new values to the
35 : : * summary), we merge some of the intervals to free space for more values.
36 : : * This is done in a greedy way - we simply pick the two closest intervals,
37 : : * merge them, and repeat this until the number of values to store gets
38 : : * sufficiently low (below 50% of maximum values), but that is mostly
39 : : * arbitrary threshold and may be changed easily).
40 : : *
41 : : * To pick the closest intervals we use the "distance" support procedure,
42 : : * which measures space between two ranges (i.e. the length of an interval).
43 : : * The computed value may be an approximation - in the worst case we will
44 : : * merge two ranges that are slightly less optimal at that step, but the
45 : : * index should still produce correct results.
46 : : *
47 : : * The compactions (reducing the number of values) is fairly expensive, as
48 : : * it requires calling the distance functions, sorting etc. So when building
49 : : * the summary, we use a significantly larger buffer, and only enforce the
50 : : * exact limit at the very end. This improves performance, and it also helps
51 : : * with building better ranges (due to the greedy approach).
52 : : *
53 : : *
54 : : * IDENTIFICATION
55 : : * src/backend/access/brin/brin_minmax_multi.c
56 : : */
57 : : #include "postgres.h"
58 : :
59 : : /* needed for PGSQL_AF_INET */
60 : : #include <sys/socket.h>
61 : :
62 : : #include "access/brin.h"
63 : : #include "access/brin_internal.h"
64 : : #include "access/brin_tuple.h"
65 : : #include "access/genam.h"
66 : : #include "access/htup_details.h"
67 : : #include "access/reloptions.h"
68 : : #include "access/stratnum.h"
69 : : #include "catalog/pg_am.h"
70 : : #include "catalog/pg_amop.h"
71 : : #include "catalog/pg_type.h"
72 : : #include "utils/array.h"
73 : : #include "utils/builtins.h"
74 : : #include "utils/date.h"
75 : : #include "utils/datum.h"
76 : : #include "utils/float.h"
77 : : #include "utils/inet.h"
78 : : #include "utils/lsyscache.h"
79 : : #include "utils/memutils.h"
80 : : #include "utils/pg_lsn.h"
81 : : #include "utils/rel.h"
82 : : #include "utils/syscache.h"
83 : : #include "utils/timestamp.h"
84 : : #include "utils/uuid.h"
85 : :
86 : : /*
87 : : * Additional SQL level support functions
88 : : *
89 : : * Procedure numbers must not use values reserved for BRIN itself; see
90 : : * brin_internal.h.
91 : : */
92 : : #define MINMAX_MAX_PROCNUMS 1 /* maximum support procs we need */
93 : : #define PROCNUM_DISTANCE 11 /* required, distance between values */
94 : :
95 : : /*
96 : : * Subtract this from procnum to obtain index in MinmaxMultiOpaque arrays
97 : : * (Must be equal to minimum of private procnums).
98 : : */
99 : : #define PROCNUM_BASE 11
100 : :
101 : : /*
102 : : * Sizing the insert buffer - we use 10x the number of values specified
103 : : * in the reloption, but we cap it to 8192 not to get too large. When
104 : : * the buffer gets full, we reduce the number of values by half.
105 : : */
106 : : #define MINMAX_BUFFER_FACTOR 10
107 : : #define MINMAX_BUFFER_MIN 256
108 : : #define MINMAX_BUFFER_MAX 8192
109 : : #define MINMAX_BUFFER_LOAD_FACTOR 0.5
110 : :
111 : : typedef struct MinmaxMultiOpaque
112 : : {
113 : : FmgrInfo extra_procinfos[MINMAX_MAX_PROCNUMS];
114 : : Oid cached_subtype;
115 : : FmgrInfo strategy_procinfos[BTMaxStrategyNumber];
116 : : } MinmaxMultiOpaque;
117 : :
118 : : /*
119 : : * Storage type for BRIN's minmax reloptions
120 : : */
121 : : typedef struct MinMaxMultiOptions
122 : : {
123 : : int32 vl_len_; /* varlena header (do not touch directly!) */
124 : : int valuesPerRange; /* number of values per range */
125 : : } MinMaxMultiOptions;
126 : :
127 : : #define MINMAX_MULTI_DEFAULT_VALUES_PER_PAGE 32
128 : :
129 : : #define MinMaxMultiGetValuesPerRange(opts) \
130 : : ((opts) && (((MinMaxMultiOptions *) (opts))->valuesPerRange != 0) ? \
131 : : ((MinMaxMultiOptions *) (opts))->valuesPerRange : \
132 : : MINMAX_MULTI_DEFAULT_VALUES_PER_PAGE)
133 : :
134 : : /*
135 : : * The summary of minmax-multi indexes has two representations - Ranges for
136 : : * convenient processing, and SerializedRanges for storage in bytea value.
137 : : *
138 : : * The Ranges struct stores the boundary values in a single array, but we
139 : : * treat regular and single-point ranges differently to save space. For
140 : : * regular ranges (with different boundary values) we have to store both
141 : : * the lower and upper bound of the range, while for "single-point ranges"
142 : : * we only need to store a single value.
143 : : *
144 : : * The 'values' array stores boundary values for regular ranges first (there
145 : : * are 2*nranges values to store), and then the nvalues boundary values for
146 : : * single-point ranges. That is, we have (2*nranges + nvalues) boundary
147 : : * values in the array.
148 : : *
149 : : * +-------------------------+----------------------------------+
150 : : * | ranges (2 * nranges of) | single point values (nvalues of) |
151 : : * +-------------------------+----------------------------------+
152 : : *
153 : : * This allows us to quickly add new values, and store outliers without
154 : : * having to widen any of the existing range values.
155 : : *
156 : : * 'nsorted' denotes how many of 'nvalues' in the values[] array are sorted.
157 : : * When nsorted == nvalues, all single point values are sorted.
158 : : *
159 : : * We never store more than maxvalues values (as set by values_per_range
160 : : * reloption). If needed we merge some of the ranges.
161 : : *
162 : : * To minimize palloc overhead, we always allocate the full array with
163 : : * space for maxvalues elements. This should be fine as long as the
164 : : * maxvalues is reasonably small (64 seems fine), which is the case
165 : : * thanks to values_per_range reloption being limited to 256.
166 : : */
167 : : typedef struct Ranges
168 : : {
169 : : /* Cache information that we need quite often. */
170 : : Oid typid;
171 : : Oid colloid;
172 : : AttrNumber attno;
173 : : FmgrInfo *cmp;
174 : :
175 : : /* (2*nranges + nvalues) <= maxvalues */
176 : : int nranges; /* number of ranges in the values[] array */
177 : : int nsorted; /* number of nvalues which are sorted */
178 : : int nvalues; /* number of point values in values[] array */
179 : : int maxvalues; /* number of elements in the values[] array */
180 : :
181 : : /*
182 : : * We simply add the values into a large buffer, without any expensive
183 : : * steps (sorting, deduplication, ...). The buffer is a multiple of the
184 : : * target number of values, so the compaction happens less often,
185 : : * amortizing the costs. We keep the actual target and compact to the
186 : : * requested number of values at the very end, before serializing to
187 : : * on-disk representation.
188 : : */
189 : : /* requested number of values */
190 : : int target_maxvalues;
191 : :
192 : : /* values stored for this range - either raw values, or ranges */
193 : : Datum values[FLEXIBLE_ARRAY_MEMBER];
194 : : } Ranges;
195 : :
196 : : /*
197 : : * On-disk the summary is stored as a bytea value, with a simple header
198 : : * with basic metadata, followed by the boundary values. It has a varlena
199 : : * header, so can be treated as varlena directly.
200 : : *
201 : : * See brin_range_serialize/brin_range_deserialize for serialization details.
202 : : */
203 : : typedef struct SerializedRanges
204 : : {
205 : : /* varlena header (do not touch directly!) */
206 : : int32 vl_len_;
207 : :
208 : : /* type of values stored in the data array */
209 : : Oid typid;
210 : :
211 : : /* (2*nranges + nvalues) <= maxvalues */
212 : : int nranges; /* number of ranges in the array (stored) */
213 : : int nvalues; /* number of values in the data array (all) */
214 : : int maxvalues; /* maximum number of values (reloption) */
215 : :
216 : : /* contains the actual data */
217 : : char data[FLEXIBLE_ARRAY_MEMBER];
218 : : } SerializedRanges;
219 : :
220 : : static SerializedRanges *brin_range_serialize(Ranges *range);
221 : :
222 : : static Ranges *brin_range_deserialize(int maxvalues,
223 : : SerializedRanges *serialized);
224 : :
225 : :
226 : : /*
227 : : * Used to represent ranges expanded to make merging and combining easier.
228 : : *
229 : : * Each expanded range is essentially an interval, represented by min/max
230 : : * values, along with a flag whether it's a collapsed range (in which case
231 : : * the min and max values are equal). We have the flag to handle by-ref
232 : : * data types - we can't simply compare the datums, and this saves some
233 : : * calls to the type-specific comparator function.
234 : : */
235 : : typedef struct ExpandedRange
236 : : {
237 : : Datum minval; /* lower boundary */
238 : : Datum maxval; /* upper boundary */
239 : : bool collapsed; /* true if minval==maxval */
240 : : } ExpandedRange;
241 : :
242 : : /*
243 : : * Represents a distance between two ranges (identified by index into
244 : : * an array of extended ranges).
245 : : */
246 : : typedef struct DistanceValue
247 : : {
248 : : int index;
249 : : double value;
250 : : } DistanceValue;
251 : :
252 : :
253 : : /* Cache for support and strategy procedures. */
254 : :
255 : : static FmgrInfo *minmax_multi_get_procinfo(BrinDesc *bdesc, uint16 attno,
256 : : uint16 procnum);
257 : :
258 : : static FmgrInfo *minmax_multi_get_strategy_procinfo(BrinDesc *bdesc,
259 : : uint16 attno, Oid subtype,
260 : : uint16 strategynum);
261 : :
262 : : typedef struct compare_context
263 : : {
264 : : FmgrInfo *cmpFn;
265 : : Oid colloid;
266 : : } compare_context;
267 : :
268 : : static int compare_values(const void *a, const void *b, void *arg);
269 : :
270 : :
271 : : #ifdef USE_ASSERT_CHECKING
272 : : /*
273 : : * Check that the order of the array values is correct, using the cmp
274 : : * function (which should be BTLessStrategyNumber).
275 : : */
276 : : static void
135 peter@eisentraut.org 277 :GNC 271886 : AssertArrayOrder(FmgrInfo *cmp, Oid colloid, const Datum *values, int nvalues)
278 : : {
279 : : int i;
280 : : Datum lt;
281 : :
1815 tomas.vondra@postgre 282 [ + + ]:CBC 4951929 : for (i = 0; i < (nvalues - 1); i++)
283 : : {
284 : 4680043 : lt = FunctionCall2Coll(cmp, colloid, values[i], values[i + 1]);
285 [ - + ]: 4680043 : Assert(DatumGetBool(lt));
286 : : }
287 : 271886 : }
288 : : #endif
289 : :
290 : : /*
291 : : * Comprehensive check of the Ranges structure.
292 : : */
293 : : static void
294 : 135943 : AssertCheckRanges(Ranges *ranges, FmgrInfo *cmpFn, Oid colloid)
295 : : {
296 : : #ifdef USE_ASSERT_CHECKING
297 : : int i;
298 : :
299 : : /* some basic sanity checks */
300 [ - + ]: 135943 : Assert(ranges->nranges >= 0);
301 [ - + ]: 135943 : Assert(ranges->nsorted >= 0);
302 [ - + ]: 135943 : Assert(ranges->nvalues >= ranges->nsorted);
303 [ - + ]: 135943 : Assert(ranges->maxvalues >= 2 * ranges->nranges + ranges->nvalues);
304 [ - + ]: 135943 : Assert(ranges->typid != InvalidOid);
305 : :
306 : : /*
307 : : * First the ranges - there are 2*nranges boundary values, and the values
308 : : * have to be strictly ordered (equal values would mean the range is
309 : : * collapsed, and should be stored as a point). This also guarantees that
310 : : * the ranges do not overlap.
311 : : */
312 : 135943 : AssertArrayOrder(cmpFn, colloid, ranges->values, 2 * ranges->nranges);
313 : :
314 : : /* then the single-point ranges (with nvalues boundary values ) */
315 : 135943 : AssertArrayOrder(cmpFn, colloid, &ranges->values[2 * ranges->nranges],
316 : : ranges->nsorted);
317 : :
318 : : /*
319 : : * Check that none of the values are not covered by ranges (both sorted
320 : : * and unsorted)
321 : : */
1279 drowley@postgresql.o 322 [ + + ]: 135943 : if (ranges->nranges > 0)
323 : : {
324 [ + + ]: 11629560 : for (i = 0; i < ranges->nvalues; i++)
325 : : {
326 : : Datum compar;
327 : : int start,
328 : : end;
329 : 11570358 : Datum minvalue = ranges->values[0];
330 : 11570358 : Datum maxvalue = ranges->values[2 * ranges->nranges - 1];
331 : 11570358 : Datum value = ranges->values[2 * ranges->nranges + i];
332 : :
333 : 11570358 : compar = FunctionCall2Coll(cmpFn, colloid, value, minvalue);
334 : :
335 : : /*
336 : : * If the value is smaller than the lower bound in the first range
337 : : * then it cannot possibly be in any of the ranges.
338 : : */
1815 tomas.vondra@postgre 339 [ + + ]: 11570358 : if (DatumGetBool(compar))
340 : 4607820 : continue;
341 : :
342 : 6962538 : compar = FunctionCall2Coll(cmpFn, colloid, maxvalue, value);
343 : :
344 : : /*
345 : : * Likewise, if the value is larger than the upper bound of the
346 : : * final range, then it cannot possibly be inside any of the
347 : : * ranges.
348 : : */
349 [ + + ]: 6962538 : if (DatumGetBool(compar))
350 : 6956427 : continue;
351 : :
352 : : /* bsearch the ranges to see if 'value' fits within any of them */
1279 drowley@postgresql.o 353 : 6111 : start = 0; /* first range */
354 : 6111 : end = ranges->nranges - 1; /* last range */
355 : : while (true)
356 : 17658 : {
357 : 23769 : int midpoint = (start + end) / 2;
358 : :
359 : : /* this means we ran out of ranges in the last step */
360 [ + + ]: 23769 : if (start > end)
361 : 6111 : break;
362 : :
363 : : /* copy the min/max values from the ranges */
364 : 17658 : minvalue = ranges->values[2 * midpoint];
365 : 17658 : maxvalue = ranges->values[2 * midpoint + 1];
366 : :
367 : : /*
368 : : * Is the value smaller than the minval? If yes, we'll recurse
369 : : * to the left side of range array.
370 : : */
371 : 17658 : compar = FunctionCall2Coll(cmpFn, colloid, value, minvalue);
372 : :
373 : : /* smaller than the smallest value in this range */
374 [ + + ]: 17658 : if (DatumGetBool(compar))
375 : : {
376 : 7872 : end = (midpoint - 1);
377 : 7872 : continue;
378 : : }
379 : :
380 : : /*
381 : : * Is the value greater than the minval? If yes, we'll recurse
382 : : * to the right side of range array.
383 : : */
384 : 9786 : compar = FunctionCall2Coll(cmpFn, colloid, maxvalue, value);
385 : :
386 : : /* larger than the largest value in this range */
387 [ + - ]: 9786 : if (DatumGetBool(compar))
388 : : {
389 : 9786 : start = (midpoint + 1);
390 : 9786 : continue;
391 : : }
392 : :
393 : : /* hey, we found a matching range */
1279 drowley@postgresql.o 394 :UBC 0 : Assert(false);
395 : : }
396 : : }
397 : : }
398 : :
399 : : /* and values in the unsorted part must not be in the sorted part */
1279 drowley@postgresql.o 400 [ + + ]:CBC 135943 : if (ranges->nsorted > 0)
401 : : {
402 : : compare_context cxt;
403 : :
1815 tomas.vondra@postgre 404 : 133433 : cxt.colloid = ranges->colloid;
405 : 133433 : cxt.cmpFn = ranges->cmp;
406 : :
1279 drowley@postgresql.o 407 [ + + ]: 10274751 : for (i = ranges->nsorted; i < ranges->nvalues; i++)
408 : : {
409 : 10141318 : Datum value = ranges->values[2 * ranges->nranges + i];
410 : :
411 [ - + ]: 10141318 : Assert(bsearch_arg(&value, &ranges->values[2 * ranges->nranges],
412 : : ranges->nsorted, sizeof(Datum),
413 : : compare_values, &cxt) == NULL);
414 : : }
415 : : }
416 : : #endif
1815 tomas.vondra@postgre 417 : 135943 : }
418 : :
419 : : /*
420 : : * Check that the expanded ranges (built when reducing the number of ranges
421 : : * by combining some of them) are correctly sorted and do not overlap.
422 : : */
423 : : static void
424 : 280 : AssertCheckExpandedRanges(BrinDesc *bdesc, Oid colloid, AttrNumber attno,
425 : : Form_pg_attribute attr, ExpandedRange *ranges,
426 : : int nranges)
427 : : {
428 : : #ifdef USE_ASSERT_CHECKING
429 : : int i;
430 : : FmgrInfo *eq;
431 : : FmgrInfo *lt;
432 : :
433 : 280 : eq = minmax_multi_get_strategy_procinfo(bdesc, attno, attr->atttypid,
434 : : BTEqualStrategyNumber);
435 : :
436 : 280 : lt = minmax_multi_get_strategy_procinfo(bdesc, attno, attr->atttypid,
437 : : BTLessStrategyNumber);
438 : :
439 : : /*
440 : : * Each range independently should be valid, i.e. that for the boundary
441 : : * values (lower <= upper).
442 : : */
443 [ + + ]: 49694 : for (i = 0; i < nranges; i++)
444 : : {
445 : : Datum r;
446 : 49414 : Datum minval = ranges[i].minval;
447 : 49414 : Datum maxval = ranges[i].maxval;
448 : :
449 [ + + ]: 49414 : if (ranges[i].collapsed) /* collapsed: minval == maxval */
450 : 49171 : r = FunctionCall2Coll(eq, colloid, minval, maxval);
451 : : else /* non-collapsed: minval < maxval */
452 : 243 : r = FunctionCall2Coll(lt, colloid, minval, maxval);
453 : :
454 [ - + ]: 49414 : Assert(DatumGetBool(r));
455 : : }
456 : :
457 : : /*
458 : : * And the ranges should be ordered and must not overlap, i.e. upper <
459 : : * lower for boundaries of consecutive ranges.
460 : : */
461 [ + + ]: 49414 : for (i = 0; i < nranges - 1; i++)
462 : : {
463 : : Datum r;
464 : 49134 : Datum maxval = ranges[i].maxval;
465 : 49134 : Datum minval = ranges[i + 1].minval;
466 : :
467 : 49134 : r = FunctionCall2Coll(lt, colloid, maxval, minval);
468 : :
469 [ - + ]: 49134 : Assert(DatumGetBool(r));
470 : : }
471 : : #endif
472 : 280 : }
473 : :
474 : :
475 : : /*
476 : : * minmax_multi_init
477 : : * Initialize the deserialized range list, allocate all the memory.
478 : : *
479 : : * This is only in-memory representation of the ranges, so we allocate
480 : : * enough space for the maximum number of values (so as not to have to do
481 : : * repallocs as the ranges grow).
482 : : */
483 : : static Ranges *
484 : 25452 : minmax_multi_init(int maxvalues)
485 : : {
486 : : Size len;
487 : : Ranges *ranges;
488 : :
489 [ - + ]: 25452 : Assert(maxvalues > 0);
490 : :
491 : 25452 : len = offsetof(Ranges, values); /* fixed header */
492 : 25452 : len += maxvalues * sizeof(Datum); /* Datum values */
493 : :
494 : 25452 : ranges = (Ranges *) palloc0(len);
495 : :
496 : 25452 : ranges->maxvalues = maxvalues;
497 : :
498 : 25452 : return ranges;
499 : : }
500 : :
501 : :
502 : : /*
503 : : * range_deduplicate_values
504 : : * Deduplicate the part with values in the simple points.
505 : : *
506 : : * This is meant to be a cheaper way of reducing the size of the ranges. It
507 : : * does not touch the ranges, and only sorts the other values - it does not
508 : : * call the distance functions, which may be quite expensive, etc.
509 : : *
510 : : * We do know the values are not duplicate with the ranges, because we check
511 : : * that before adding a new value. Same for the sorted part of values.
512 : : */
513 : : static void
514 : 9208 : range_deduplicate_values(Ranges *range)
515 : : {
516 : : int i,
517 : : n;
518 : : int start;
519 : : compare_context cxt;
520 : :
521 : : /*
522 : : * If there are no unsorted values, we're done (this probably can't
523 : : * happen, as we're adding values to unsorted part).
524 : : */
525 [ + + ]: 9208 : if (range->nsorted == range->nvalues)
526 : 9085 : return;
527 : :
528 : : /* sort the values */
529 : 123 : cxt.colloid = range->colloid;
530 : 123 : cxt.cmpFn = range->cmp;
531 : :
532 : : /* the values start right after the ranges (which are always sorted) */
533 : 123 : start = 2 * range->nranges;
534 : :
535 : : /*
536 : : * XXX This might do a merge sort, to leverage that the first part of the
537 : : * array is already sorted. If the sorted part is large, it might be quite
538 : : * a bit faster.
539 : : */
540 : 123 : qsort_arg(&range->values[start],
541 : 123 : range->nvalues, sizeof(Datum),
542 : : compare_values, &cxt);
543 : :
544 : 123 : n = 1;
545 [ + + ]: 39120 : for (i = 1; i < range->nvalues; i++)
546 : : {
547 : : /* same as preceding value, so store it */
548 [ - + ]: 38997 : if (compare_values(&range->values[start + i - 1],
549 : 38997 : &range->values[start + i],
550 : : &cxt) == 0)
1815 tomas.vondra@postgre 551 :UBC 0 : continue;
552 : :
1815 tomas.vondra@postgre 553 :CBC 38997 : range->values[start + n] = range->values[start + i];
554 : :
555 : 38997 : n++;
556 : : }
557 : :
558 : : /* now all the values are sorted */
559 : 123 : range->nvalues = n;
560 : 123 : range->nsorted = n;
561 : :
562 : 123 : AssertCheckRanges(range, range->cmp, range->colloid);
563 : : }
564 : :
565 : :
566 : : /*
567 : : * brin_range_serialize
568 : : * Serialize the in-memory representation into a compact varlena value.
569 : : *
570 : : * Simply copy the header and then also the individual values, as stored
571 : : * in the in-memory value array.
572 : : */
573 : : static SerializedRanges *
1525 peter@eisentraut.org 574 : 9085 : brin_range_serialize(Ranges *range)
575 : : {
576 : : Size len;
577 : : int nvalues;
578 : : SerializedRanges *serialized;
579 : : Oid typid;
580 : : int typlen;
581 : : bool typbyval;
582 : :
583 : : char *ptr;
584 : :
585 : : /* simple sanity checks */
1815 tomas.vondra@postgre 586 [ - + ]: 9085 : Assert(range->nranges >= 0);
587 [ - + ]: 9085 : Assert(range->nsorted >= 0);
588 [ - + ]: 9085 : Assert(range->nvalues >= 0);
589 [ - + ]: 9085 : Assert(range->maxvalues > 0);
590 [ - + ]: 9085 : Assert(range->target_maxvalues > 0);
591 : :
592 : : /* at this point the range should be compacted to the target size */
593 [ - + ]: 9085 : Assert(2 * range->nranges + range->nvalues <= range->target_maxvalues);
594 : :
595 [ - + ]: 9085 : Assert(range->target_maxvalues <= range->maxvalues);
596 : :
597 : : /* range boundaries are always sorted */
598 [ - + ]: 9085 : Assert(range->nvalues >= range->nsorted);
599 : :
600 : : /* deduplicate values, if there's unsorted part */
601 : 9085 : range_deduplicate_values(range);
602 : :
603 : : /* see how many Datum values we actually have */
604 : 9085 : nvalues = 2 * range->nranges + range->nvalues;
605 : :
606 : 9085 : typid = range->typid;
607 : 9085 : typbyval = get_typbyval(typid);
608 : 9085 : typlen = get_typlen(typid);
609 : :
610 : : /* header is always needed */
611 : 9085 : len = offsetof(SerializedRanges, data);
612 : :
613 : : /*
614 : : * The space needed depends on data type - for fixed-length data types
615 : : * (by-value and some by-reference) it's pretty simple, just multiply
616 : : * (attlen * nvalues) and we're done. For variable-length by-reference
617 : : * types we need to actually walk all the values and sum the lengths.
618 : : */
619 [ + + ]: 9085 : if (typlen == -1) /* varlena */
620 : : {
621 : : int i;
622 : :
623 [ + + ]: 5976 : for (i = 0; i < nvalues; i++)
624 : : {
222 peter@eisentraut.org 625 :GNC 4683 : len += VARSIZE_ANY(DatumGetPointer(range->values[i]));
626 : : }
627 : : }
1815 tomas.vondra@postgre 628 [ - + ]:CBC 7792 : else if (typlen == -2) /* cstring */
629 : : {
630 : : int i;
631 : :
1815 tomas.vondra@postgre 632 [ # # ]:UBC 0 : for (i = 0; i < nvalues; i++)
633 : : {
634 : : /* don't forget to include the null terminator ;-) */
1745 drowley@postgresql.o 635 : 0 : len += strlen(DatumGetCString(range->values[i])) + 1;
636 : : }
637 : : }
638 : : else /* fixed-length types (even by-reference) */
639 : : {
1815 tomas.vondra@postgre 640 [ - + ]:CBC 7792 : Assert(typlen > 0);
641 : 7792 : len += nvalues * typlen;
642 : : }
643 : :
644 : : /*
645 : : * Allocate the serialized object, copy the basic information. The
646 : : * serialized object is a varlena, so update the header.
647 : : */
648 : 9085 : serialized = (SerializedRanges *) palloc0(len);
649 : 9085 : SET_VARSIZE(serialized, len);
650 : :
651 : 9085 : serialized->typid = typid;
652 : 9085 : serialized->nranges = range->nranges;
653 : 9085 : serialized->nvalues = range->nvalues;
654 : 9085 : serialized->maxvalues = range->target_maxvalues;
655 : :
656 : : /*
657 : : * And now copy also the boundary values (like the length calculation this
658 : : * depends on the particular data type).
659 : : */
660 : 9085 : ptr = serialized->data; /* start of the serialized data */
661 : :
1299 drowley@postgresql.o 662 [ + + ]: 45029 : for (int i = 0; i < nvalues; i++)
663 : : {
1815 tomas.vondra@postgre 664 [ + + ]: 35944 : if (typbyval) /* simple by-value data types */
665 : : {
666 : : Datum tmp;
667 : :
668 : : /*
669 : : * For byval types, we need to copy just the significant bytes -
670 : : * we can't use memcpy directly, as that assumes little-endian
671 : : * behavior. store_att_byval does almost what we need, but it
672 : : * requires a properly aligned buffer - the output buffer does not
673 : : * guarantee that. So we simply use a local Datum variable (which
674 : : * guarantees proper alignment), and then copy the value from it.
675 : : */
676 : 22505 : store_att_byval(&tmp, range->values[i], typlen);
677 : :
678 : 22505 : memcpy(ptr, &tmp, typlen);
679 : 22505 : ptr += typlen;
680 : : }
681 [ + + ]: 13439 : else if (typlen > 0) /* fixed-length by-ref types */
682 : : {
683 : 8756 : memcpy(ptr, DatumGetPointer(range->values[i]), typlen);
684 : 8756 : ptr += typlen;
685 : : }
686 [ + - ]: 4683 : else if (typlen == -1) /* varlena */
687 : : {
688 [ - + - - : 4683 : int tmp = VARSIZE_ANY(DatumGetPointer(range->values[i]));
- - - - +
- ]
689 : :
690 : 4683 : memcpy(ptr, DatumGetPointer(range->values[i]), tmp);
691 : 4683 : ptr += tmp;
692 : : }
1815 tomas.vondra@postgre 693 [ # # ]:UBC 0 : else if (typlen == -2) /* cstring */
694 : : {
1745 drowley@postgresql.o 695 : 0 : int tmp = strlen(DatumGetCString(range->values[i])) + 1;
696 : :
697 : 0 : memcpy(ptr, DatumGetCString(range->values[i]), tmp);
1815 tomas.vondra@postgre 698 : 0 : ptr += tmp;
699 : : }
700 : :
701 : : /* make sure we haven't overflown the buffer end */
1815 tomas.vondra@postgre 702 [ - + ]:CBC 35944 : Assert(ptr <= ((char *) serialized + len));
703 : : }
704 : :
705 : : /* exact size */
706 [ - + ]: 9085 : Assert(ptr == ((char *) serialized + len));
707 : :
708 : 9085 : return serialized;
709 : : }
710 : :
711 : : /*
712 : : * brin_range_deserialize
713 : : * Deserialize a compact varlena value into the in-memory representation.
714 : : *
715 : : * Simply copy the header and then also the individual values, as stored
716 : : * in the in-memory value array.
717 : : */
718 : : static Ranges *
1525 peter@eisentraut.org 719 : 22957 : brin_range_deserialize(int maxvalues, SerializedRanges *serialized)
720 : : {
721 : : int i,
722 : : nvalues;
723 : : char *ptr,
724 : : *dataptr;
725 : : bool typbyval;
726 : : int typlen;
727 : : Size datalen;
728 : :
729 : : Ranges *range;
730 : :
1815 tomas.vondra@postgre 731 [ - + ]: 22957 : Assert(serialized->nranges >= 0);
732 [ - + ]: 22957 : Assert(serialized->nvalues >= 0);
733 [ - + ]: 22957 : Assert(serialized->maxvalues > 0);
734 : :
735 : 22957 : nvalues = 2 * serialized->nranges + serialized->nvalues;
736 : :
737 [ - + ]: 22957 : Assert(nvalues <= serialized->maxvalues);
738 [ - + ]: 22957 : Assert(serialized->maxvalues <= maxvalues);
739 : :
740 : 22957 : range = minmax_multi_init(maxvalues);
741 : :
742 : : /* copy the header info */
743 : 22957 : range->nranges = serialized->nranges;
744 : 22957 : range->nvalues = serialized->nvalues;
745 : 22957 : range->nsorted = serialized->nvalues;
746 : 22957 : range->maxvalues = maxvalues;
747 : 22957 : range->target_maxvalues = serialized->maxvalues;
748 : :
749 : 22957 : range->typid = serialized->typid;
750 : :
751 : 22957 : typbyval = get_typbyval(serialized->typid);
752 : 22957 : typlen = get_typlen(serialized->typid);
753 : :
754 : : /*
755 : : * And now deconstruct the values into Datum array. We have to copy the
756 : : * data because the serialized representation ignores alignment, and we
757 : : * don't want to rely on it being kept around anyway.
758 : : */
759 : 22957 : ptr = serialized->data;
760 : :
761 : : /*
762 : : * We don't want to allocate many pieces, so we just allocate everything
763 : : * in one chunk. How much space will we need?
764 : : *
765 : : * XXX We don't need to copy simple by-value data types.
766 : : */
767 : 22957 : datalen = 0;
768 : 22957 : dataptr = NULL;
769 [ + + + + ]: 52811 : for (i = 0; (i < nvalues) && (!typbyval); i++)
770 : : {
1768 tgl@sss.pgh.pa.us 771 [ + + ]: 29854 : if (typlen > 0) /* fixed-length by-ref types */
1815 tomas.vondra@postgre 772 : 18040 : datalen += MAXALIGN(typlen);
773 [ + - ]: 11814 : else if (typlen == -1) /* varlena */
774 : : {
1295 peter@eisentraut.org 775 [ - + - - : 11814 : datalen += MAXALIGN(VARSIZE_ANY(ptr));
- - - - +
- ]
776 [ - + - - : 11814 : ptr += VARSIZE_ANY(ptr);
- - - - +
- ]
777 : : }
1815 tomas.vondra@postgre 778 [ # # ]:UBC 0 : else if (typlen == -2) /* cstring */
779 : : {
1295 peter@eisentraut.org 780 : 0 : Size slen = strlen(ptr) + 1;
781 : :
1745 drowley@postgresql.o 782 : 0 : datalen += MAXALIGN(slen);
783 : 0 : ptr += slen;
784 : : }
785 : : }
786 : :
1815 tomas.vondra@postgre 787 [ + + ]:CBC 22957 : if (datalen > 0)
788 : 8697 : dataptr = palloc(datalen);
789 : :
790 : : /*
791 : : * Restore the source pointer (might have been modified when calculating
792 : : * the space we need to allocate).
793 : : */
794 : 22957 : ptr = serialized->data;
795 : :
796 [ + + ]: 118792 : for (i = 0; i < nvalues; i++)
797 : : {
798 [ + + ]: 95835 : if (typbyval) /* simple by-value data types */
799 : : {
800 : 65981 : Datum v = 0;
801 : :
802 : 65981 : memcpy(&v, ptr, typlen);
803 : :
804 : 65981 : range->values[i] = fetch_att(&v, true, typlen);
805 : 65981 : ptr += typlen;
806 : : }
807 [ + + ]: 29854 : else if (typlen > 0) /* fixed-length by-ref types */
808 : : {
809 : 18040 : range->values[i] = PointerGetDatum(dataptr);
810 : :
811 : 18040 : memcpy(dataptr, ptr, typlen);
812 : 18040 : dataptr += MAXALIGN(typlen);
813 : :
814 : 18040 : ptr += typlen;
815 : : }
816 [ + - ]: 11814 : else if (typlen == -1) /* varlena */
817 : : {
818 : 11814 : range->values[i] = PointerGetDatum(dataptr);
819 : :
820 [ - + - - : 11814 : memcpy(dataptr, ptr, VARSIZE_ANY(ptr));
- - - - +
- ]
821 [ - + - - : 11814 : dataptr += MAXALIGN(VARSIZE_ANY(ptr));
- - - - +
- ]
822 [ - + - - : 11814 : ptr += VARSIZE_ANY(ptr);
- - - - +
- ]
823 : : }
1815 tomas.vondra@postgre 824 [ # # ]:UBC 0 : else if (typlen == -2) /* cstring */
825 : : {
1768 tgl@sss.pgh.pa.us 826 : 0 : Size slen = strlen(ptr) + 1;
827 : :
1815 tomas.vondra@postgre 828 : 0 : range->values[i] = PointerGetDatum(dataptr);
829 : :
830 : 0 : memcpy(dataptr, ptr, slen);
831 : 0 : dataptr += MAXALIGN(slen);
1745 drowley@postgresql.o 832 : 0 : ptr += slen;
833 : : }
834 : :
835 : : /* make sure we haven't overflown the buffer end */
1815 tomas.vondra@postgre 836 [ - + - - :CBC 95835 : Assert(ptr <= ((char *) serialized + VARSIZE_ANY(serialized)));
- - - - -
+ - + ]
837 : : }
838 : :
839 : : /* should have consumed the whole input value exactly */
840 [ - + - - : 22957 : Assert(ptr == ((char *) serialized + VARSIZE_ANY(serialized)));
- - - - -
+ - + ]
841 : :
842 : : /* return the deserialized value */
843 : 22957 : return range;
844 : : }
845 : :
846 : : /*
847 : : * compare_expanded_ranges
848 : : * Compare the expanded ranges - first by minimum, then by maximum.
849 : : *
850 : : * We do guarantee that ranges in a single Ranges object do not overlap, so it
851 : : * may seem strange that we don't order just by minimum. But when merging two
852 : : * Ranges (which happens in the union function), the ranges may in fact
853 : : * overlap. So we do compare both.
854 : : */
855 : : static int
856 : 419955 : compare_expanded_ranges(const void *a, const void *b, void *arg)
857 : : {
62 peter@eisentraut.org 858 :GNC 419955 : const ExpandedRange *ra = a;
859 : 419955 : const ExpandedRange *rb = b;
860 : : Datum r;
861 : :
1815 tomas.vondra@postgre 862 :CBC 419955 : compare_context *cxt = (compare_context *) arg;
863 : :
864 : : /* first compare minvals */
865 : 419955 : r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, ra->minval, rb->minval);
866 : :
867 [ + + ]: 419955 : if (DatumGetBool(r))
868 : 271211 : return -1;
869 : :
870 : 148744 : r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, rb->minval, ra->minval);
871 : :
872 [ + + ]: 148744 : if (DatumGetBool(r))
873 : 116509 : return 1;
874 : :
875 : : /* then compare maxvals */
876 : 32235 : r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, ra->maxval, rb->maxval);
877 : :
878 [ - + ]: 32235 : if (DatumGetBool(r))
1815 tomas.vondra@postgre 879 :UBC 0 : return -1;
880 : :
1815 tomas.vondra@postgre 881 :CBC 32235 : r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, rb->maxval, ra->maxval);
882 : :
883 [ - + ]: 32235 : if (DatumGetBool(r))
1815 tomas.vondra@postgre 884 :UBC 0 : return 1;
885 : :
1815 tomas.vondra@postgre 886 :CBC 32235 : return 0;
887 : : }
888 : :
889 : : /*
890 : : * compare_values
891 : : * Compare the values.
892 : : */
893 : : static int
894 : 45519652 : compare_values(const void *a, const void *b, void *arg)
895 : : {
62 peter@eisentraut.org 896 :GNC 45519652 : const Datum *da = a;
897 : 45519652 : const Datum *db = b;
898 : : Datum r;
899 : :
1815 tomas.vondra@postgre 900 :CBC 45519652 : compare_context *cxt = (compare_context *) arg;
901 : :
902 : 45519652 : r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db);
903 : :
904 [ + + ]: 45519652 : if (DatumGetBool(r))
905 : 1641949 : return -1;
906 : :
907 : 43877703 : r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da);
908 : :
909 [ + + ]: 43877703 : if (DatumGetBool(r))
910 : 43844088 : return 1;
911 : :
912 : 33615 : return 0;
913 : : }
914 : :
915 : : /*
916 : : * Check if the new value matches one of the existing ranges.
917 : : */
918 : : static bool
919 : 132630 : has_matching_range(BrinDesc *bdesc, Oid colloid, Ranges *ranges,
920 : : Datum newval, AttrNumber attno, Oid typid)
921 : : {
922 : : Datum compar;
923 : :
924 : : Datum minvalue;
925 : : Datum maxvalue;
926 : :
927 : : FmgrInfo *cmpLessFn;
928 : : FmgrInfo *cmpGreaterFn;
929 : :
930 : : /* binary search on ranges */
931 : : int start,
932 : : end;
933 : :
934 [ + + ]: 132630 : if (ranges->nranges == 0)
935 : 73968 : return false;
936 : :
1279 drowley@postgresql.o 937 : 58662 : minvalue = ranges->values[0];
938 : 58662 : maxvalue = ranges->values[2 * ranges->nranges - 1];
939 : :
940 : : /*
941 : : * Otherwise, need to compare the new value with boundaries of all the
942 : : * ranges. First check if it's less than the absolute minimum, which is
943 : : * the first value in the array.
944 : : */
1815 tomas.vondra@postgre 945 : 58662 : cmpLessFn = minmax_multi_get_strategy_procinfo(bdesc, attno, typid,
946 : : BTLessStrategyNumber);
947 : 58662 : compar = FunctionCall2Coll(cmpLessFn, colloid, newval, minvalue);
948 : :
949 : : /* smaller than the smallest value in the range list */
950 [ + + ]: 58662 : if (DatumGetBool(compar))
951 : 18 : return false;
952 : :
953 : : /*
954 : : * And now compare it to the existing maximum (last value in the data
955 : : * array). But only if we haven't already ruled out a possible match in
956 : : * the minvalue check.
957 : : */
958 : 58644 : cmpGreaterFn = minmax_multi_get_strategy_procinfo(bdesc, attno, typid,
959 : : BTGreaterStrategyNumber);
960 : 58644 : compar = FunctionCall2Coll(cmpGreaterFn, colloid, newval, maxvalue);
961 : :
962 [ + + ]: 58644 : if (DatumGetBool(compar))
963 : 58197 : return false;
964 : :
965 : : /*
966 : : * So we know it's in the general min/max, the question is whether it
967 : : * falls in one of the ranges or gaps. We'll do a binary search on
968 : : * individual ranges - for each range we check equality (value falls into
969 : : * the range), and then check ranges either above or below the current
970 : : * range.
971 : : */
972 : 447 : start = 0; /* first range */
973 : 447 : end = (ranges->nranges - 1); /* last range */
974 : : while (true)
975 : 1041 : {
976 : 1488 : int midpoint = (start + end) / 2;
977 : :
978 : : /* this means we ran out of ranges in the last step */
979 [ + + ]: 1488 : if (start > end)
980 : 228 : return false;
981 : :
982 : : /* copy the min/max values from the ranges */
983 : 1260 : minvalue = ranges->values[2 * midpoint];
984 : 1260 : maxvalue = ranges->values[2 * midpoint + 1];
985 : :
986 : : /*
987 : : * Is the value smaller than the minval? If yes, we'll recurse to the
988 : : * left side of range array.
989 : : */
990 : 1260 : compar = FunctionCall2Coll(cmpLessFn, colloid, newval, minvalue);
991 : :
992 : : /* smaller than the smallest value in this range */
993 [ + + ]: 1260 : if (DatumGetBool(compar))
994 : : {
995 : 396 : end = (midpoint - 1);
996 : 396 : continue;
997 : : }
998 : :
999 : : /*
1000 : : * Is the value greater than the minval? If yes, we'll recurse to the
1001 : : * right side of range array.
1002 : : */
1003 : 864 : compar = FunctionCall2Coll(cmpGreaterFn, colloid, newval, maxvalue);
1004 : :
1005 : : /* larger than the largest value in this range */
1006 [ + + ]: 864 : if (DatumGetBool(compar))
1007 : : {
1008 : 645 : start = (midpoint + 1);
1009 : 645 : continue;
1010 : : }
1011 : :
1012 : : /* hey, we found a matching range */
1013 : 219 : return true;
1014 : : }
1015 : :
1016 : : return false;
1017 : : }
1018 : :
1019 : :
1020 : : /*
1021 : : * range_contains_value
1022 : : * See if the new value is already contained in the range list.
1023 : : *
1024 : : * We first inspect the list of intervals. We use a small trick - we check
1025 : : * the value against min/max of the whole range (min of the first interval,
1026 : : * max of the last one) first, and only inspect the individual intervals if
1027 : : * this passes.
1028 : : *
1029 : : * If the value matches none of the intervals, we check the exact values.
1030 : : * We simply loop through them and invoke equality operator on them.
1031 : : *
1032 : : * The last parameter (full) determines whether we need to search all the
1033 : : * values, including the unsorted part. With full=false, the unsorted part
1034 : : * is not searched, which may produce false negatives and duplicate values
1035 : : * (in the unsorted part only), but when we're building the range that's
1036 : : * fine - we'll deduplicate before serialization, and it can only happen
1037 : : * if there already are unsorted values (so it was already modified).
1038 : : *
1039 : : * Serialized ranges don't have any unsorted values, so this can't cause
1040 : : * false negatives during querying.
1041 : : */
1042 : : static bool
1043 : 132630 : range_contains_value(BrinDesc *bdesc, Oid colloid,
1044 : : AttrNumber attno, Form_pg_attribute attr,
1045 : : Ranges *ranges, Datum newval, bool full)
1046 : : {
1047 : : int i;
1048 : : FmgrInfo *cmpEqualFn;
1049 : 132630 : Oid typid = attr->atttypid;
1050 : :
1051 : : /*
1052 : : * First inspect the ranges, if there are any. We first check the whole
1053 : : * range, and only when there's still a chance of getting a match we
1054 : : * inspect the individual ranges.
1055 : : */
1056 [ + + ]: 132630 : if (has_matching_range(bdesc, colloid, ranges, newval, attno, typid))
1057 : 219 : return true;
1058 : :
1059 : 132411 : cmpEqualFn = minmax_multi_get_strategy_procinfo(bdesc, attno, typid,
1060 : : BTEqualStrategyNumber);
1061 : :
1062 : : /*
1063 : : * There is no matching range, so let's inspect the sorted values.
1064 : : *
1065 : : * We do a sequential search for small numbers of values, and binary
1066 : : * search once we have more than 16 values. This threshold is somewhat
1067 : : * arbitrary, as it depends on how expensive the comparison function is.
1068 : : *
1069 : : * XXX If we use the threshold here, maybe we should do the same thing in
1070 : : * has_matching_range? Or maybe we should do the bin search all the time?
1071 : : *
1072 : : * XXX We could use the same optimization as for ranges, to check if the
1073 : : * value is between min/max, to maybe rule out all sorted values without
1074 : : * having to inspect all of them.
1075 : : */
1076 [ + + ]: 132411 : if (ranges->nsorted >= 16)
1077 : : {
1078 : : compare_context cxt;
1079 : :
1080 : 58092 : cxt.colloid = ranges->colloid;
1081 : 58092 : cxt.cmpFn = ranges->cmp;
1082 : :
1083 [ - + ]: 58092 : if (bsearch_arg(&newval, &ranges->values[2 * ranges->nranges],
1084 : 58092 : ranges->nsorted, sizeof(Datum),
1085 : : compare_values, &cxt) != NULL)
1815 tomas.vondra@postgre 1086 :UBC 0 : return true;
1087 : : }
1088 : : else
1089 : : {
1815 tomas.vondra@postgre 1090 [ + + ]:CBC 148493 : for (i = 2 * ranges->nranges; i < 2 * ranges->nranges + ranges->nsorted; i++)
1091 : : {
1092 : : Datum compar;
1093 : :
1094 : 84574 : compar = FunctionCall2Coll(cmpEqualFn, colloid, newval, ranges->values[i]);
1095 : :
1096 : : /* found an exact match */
1097 [ + + ]: 84574 : if (DatumGetBool(compar))
1098 : 10400 : return true;
1099 : : }
1100 : : }
1101 : :
1102 : : /* If not asked to inspect the unsorted part, we're done. */
1103 [ + + ]: 122011 : if (!full)
1104 : 62253 : return false;
1105 : :
1106 : : /* Inspect the unsorted part. */
1107 [ + - ]: 4250097 : for (i = 2 * ranges->nranges + ranges->nsorted; i < 2 * ranges->nranges + ranges->nvalues; i++)
1108 : : {
1109 : : Datum compar;
1110 : :
1111 : 4250097 : compar = FunctionCall2Coll(cmpEqualFn, colloid, newval, ranges->values[i]);
1112 : :
1113 : : /* found an exact match */
1114 [ + + ]: 4250097 : if (DatumGetBool(compar))
1115 : 59758 : return true;
1116 : : }
1117 : :
1118 : : /* the value is not covered by this BRIN tuple */
1815 tomas.vondra@postgre 1119 :UBC 0 : return false;
1120 : : }
1121 : :
1122 : : /*
1123 : : * Expand ranges from Ranges into ExpandedRange array. This expects the
1124 : : * eranges to be pre-allocated and with the correct size - there needs to be
1125 : : * (nranges + nvalues) elements.
1126 : : *
1127 : : * The order of expanded ranges is arbitrary. We do expand the ranges first,
1128 : : * and this part is sorted. But then we expand the values, and this part may
1129 : : * be unsorted.
1130 : : */
1131 : : static void
1815 tomas.vondra@postgre 1132 :CBC 3224 : fill_expanded_ranges(ExpandedRange *eranges, int neranges, Ranges *ranges)
1133 : : {
1134 : : int idx;
1135 : : int i;
1136 : :
1137 : : /* Check that the output array has the right size. */
1138 [ - + ]: 3224 : Assert(neranges == (ranges->nranges + ranges->nvalues));
1139 : :
1140 : 3224 : idx = 0;
1141 [ + + ]: 4358 : for (i = 0; i < ranges->nranges; i++)
1142 : : {
1143 : 1134 : eranges[idx].minval = ranges->values[2 * i];
1144 : 1134 : eranges[idx].maxval = ranges->values[2 * i + 1];
1145 : 1134 : eranges[idx].collapsed = false;
1146 : 1134 : idx++;
1147 : :
1148 [ - + ]: 1134 : Assert(idx <= neranges);
1149 : : }
1150 : :
1151 [ + + ]: 79020 : for (i = 0; i < ranges->nvalues; i++)
1152 : : {
1153 : 75796 : eranges[idx].minval = ranges->values[2 * ranges->nranges + i];
1154 : 75796 : eranges[idx].maxval = ranges->values[2 * ranges->nranges + i];
1155 : 75796 : eranges[idx].collapsed = true;
1156 : 75796 : idx++;
1157 : :
1158 [ - + ]: 75796 : Assert(idx <= neranges);
1159 : : }
1160 : :
1161 : : /* Did we produce the expected number of elements? */
1162 [ - + ]: 3224 : Assert(idx == neranges);
1163 : :
1164 : 3224 : return;
1165 : : }
1166 : :
1167 : : /*
1168 : : * Sort and deduplicate expanded ranges.
1169 : : *
1170 : : * The ranges may be deduplicated - we're simply appending values, without
1171 : : * checking for duplicates etc. So maybe the deduplication will reduce the
1172 : : * number of ranges enough, and we won't have to compute the distances etc.
1173 : : *
1174 : : * Returns the number of expanded ranges.
1175 : : */
1176 : : static int
1177 : 3207 : sort_expanded_ranges(FmgrInfo *cmp, Oid colloid,
1178 : : ExpandedRange *eranges, int neranges)
1179 : : {
1180 : : int n;
1181 : : int i;
1182 : : compare_context cxt;
1183 : :
1184 [ - + ]: 3207 : Assert(neranges > 0);
1185 : :
1186 : : /* sort the values */
1187 : 3207 : cxt.colloid = colloid;
1188 : 3207 : cxt.cmpFn = cmp;
1189 : :
1190 : : /*
1191 : : * XXX We do qsort on all the values, but we could also leverage the fact
1192 : : * that some of the input data is already sorted (all the ranges and maybe
1193 : : * some of the points) and do merge sort.
1194 : : */
1195 : 3207 : qsort_arg(eranges, neranges, sizeof(ExpandedRange),
1196 : : compare_expanded_ranges, &cxt);
1197 : :
1198 : : /*
1199 : : * Deduplicate the ranges - simply compare each range to the preceding
1200 : : * one, and skip the duplicate ones.
1201 : : */
1202 : 3207 : n = 1;
1203 [ + + ]: 76930 : for (i = 1; i < neranges; i++)
1204 : : {
1205 : : /* if the current range is equal to the preceding one, do nothing */
472 peter@eisentraut.org 1206 [ + + ]: 73723 : if (!compare_expanded_ranges(&eranges[i - 1], &eranges[i], &cxt))
1815 tomas.vondra@postgre 1207 : 14815 : continue;
1208 : :
1209 : : /* otherwise, copy it to n-th place (if not already there) */
1210 [ + + ]: 58908 : if (i != n)
1211 : 4867 : memcpy(&eranges[n], &eranges[i], sizeof(ExpandedRange));
1212 : :
1213 : 58908 : n++;
1214 : : }
1215 : :
1216 [ + - - + ]: 3207 : Assert((n > 0) && (n <= neranges));
1217 : :
1218 : 3207 : return n;
1219 : : }
1220 : :
1221 : : /*
1222 : : * When combining multiple Range values (in union function), some of the
1223 : : * ranges may overlap. We simply merge the overlapping ranges to fix that.
1224 : : *
1225 : : * XXX This assumes the expanded ranges were previously sorted (by minval
1226 : : * and then maxval). We leverage this when detecting overlap.
1227 : : */
1228 : : static int
1229 : 17 : merge_overlapping_ranges(FmgrInfo *cmp, Oid colloid,
1230 : : ExpandedRange *eranges, int neranges)
1231 : : {
1232 : : int idx;
1233 : :
1234 : : /* Merge ranges (idx) and (idx+1) if they overlap. */
1235 : 17 : idx = 0;
1236 [ + + ]: 167 : while (idx < (neranges - 1))
1237 : : {
1238 : : Datum r;
1239 : :
1240 : : /*
1241 : : * comparing [?,maxval] vs. [minval,?] - the ranges overlap if (minval
1242 : : * < maxval)
1243 : : */
1244 : 150 : r = FunctionCall2Coll(cmp, colloid,
1245 : 150 : eranges[idx].maxval,
1246 : 150 : eranges[idx + 1].minval);
1247 : :
1248 : : /*
1249 : : * Nope, maxval < minval, so no overlap. And we know the ranges are
1250 : : * ordered, so there are no more overlaps, because all the remaining
1251 : : * ranges have greater or equal minval.
1252 : : */
1253 [ + - ]: 150 : if (DatumGetBool(r))
1254 : : {
1255 : : /* proceed to the next range */
1256 : 150 : idx += 1;
1257 : 150 : continue;
1258 : : }
1259 : :
1260 : : /*
1261 : : * So ranges 'idx' and 'idx+1' do overlap, but we don't know if
1262 : : * 'idx+1' is contained in 'idx', or if they overlap only partially.
1263 : : * So compare the upper bounds and keep the larger one.
1264 : : */
1815 tomas.vondra@postgre 1265 :UBC 0 : r = FunctionCall2Coll(cmp, colloid,
1266 : 0 : eranges[idx].maxval,
1267 : 0 : eranges[idx + 1].maxval);
1268 : :
1269 [ # # ]: 0 : if (DatumGetBool(r))
1270 : 0 : eranges[idx].maxval = eranges[idx + 1].maxval;
1271 : :
1272 : : /*
1273 : : * The range certainly is no longer collapsed (irrespectively of the
1274 : : * previous state).
1275 : : */
1276 : 0 : eranges[idx].collapsed = false;
1277 : :
1278 : : /*
1279 : : * Now get rid of the (idx+1) range entirely by shifting the remaining
1280 : : * ranges by 1. There are neranges elements, and we need to move
1281 : : * elements from (idx+2). That means the number of elements to move is
1282 : : * [ncranges - (idx+2)].
1283 : : */
1284 : 0 : memmove(&eranges[idx + 1], &eranges[idx + 2],
1285 : 0 : (neranges - (idx + 2)) * sizeof(ExpandedRange));
1286 : :
1287 : : /*
1288 : : * Decrease the number of ranges, and repeat (with the same range, as
1289 : : * it might overlap with additional ranges thanks to the merge).
1290 : : */
1291 : 0 : neranges--;
1292 : : }
1293 : :
1815 tomas.vondra@postgre 1294 :CBC 17 : return neranges;
1295 : : }
1296 : :
1297 : : /*
1298 : : * Simple comparator for distance values, comparing the double value.
1299 : : * This is intentionally sorting the distances in descending order, i.e.
1300 : : * the longer gaps will be at the front.
1301 : : */
1302 : : static int
1303 : 86462 : compare_distances(const void *a, const void *b)
1304 : : {
62 peter@eisentraut.org 1305 :GNC 86462 : const DistanceValue *da = a;
1306 : 86462 : const DistanceValue *db = b;
1307 : :
1815 tomas.vondra@postgre 1308 [ + + ]:CBC 86462 : if (da->value < db->value)
1309 : 20521 : return 1;
1310 [ + + ]: 65941 : else if (da->value > db->value)
1311 : 13891 : return -1;
1312 : :
1313 : 52050 : return 0;
1314 : : }
1315 : :
1316 : : /*
1317 : : * Given an array of expanded ranges, compute size of the gaps between each
1318 : : * range. For neranges there are (neranges-1) gaps.
1319 : : *
1320 : : * We simply call the "distance" function to compute the (max-min) for pairs
1321 : : * of consecutive ranges. The function may be fairly expensive, so we do that
1322 : : * just once (and then use it to pick as many ranges to merge as possible).
1323 : : *
1324 : : * See reduce_expanded_ranges for details.
1325 : : */
1326 : : static DistanceValue *
1327 : 3207 : build_distances(FmgrInfo *distanceFn, Oid colloid,
1328 : : ExpandedRange *eranges, int neranges)
1329 : : {
1330 : : int i;
1331 : : int ndistances;
1332 : : DistanceValue *distances;
1333 : :
1171 1334 [ - + ]: 3207 : Assert(neranges > 0);
1335 : :
1336 : : /* If there's only a single range, there's no distance to calculate. */
1337 [ - + ]: 3207 : if (neranges == 1)
1171 tomas.vondra@postgre 1338 :UBC 0 : return NULL;
1339 : :
1815 tomas.vondra@postgre 1340 :CBC 3207 : ndistances = (neranges - 1);
95 michael@paquier.xyz 1341 :GNC 3207 : distances = palloc0_array(DistanceValue, ndistances);
1342 : :
1343 : : /*
1344 : : * Walk through the ranges once and compute the distance between the
1345 : : * ranges so that we can sort them once.
1346 : : */
1815 tomas.vondra@postgre 1347 [ + + ]:CBC 62115 : for (i = 0; i < ndistances; i++)
1348 : : {
1349 : : Datum a1,
1350 : : a2,
1351 : : r;
1352 : :
1353 : 58908 : a1 = eranges[i].maxval;
1354 : 58908 : a2 = eranges[i + 1].minval;
1355 : :
1356 : : /* compute length of the gap (between max/min) */
1357 : 58908 : r = FunctionCall2Coll(distanceFn, colloid, a1, a2);
1358 : :
1359 : : /* remember the index of the gap the distance is for */
1360 : 58908 : distances[i].index = i;
1361 : 58908 : distances[i].value = DatumGetFloat8(r);
1362 : : }
1363 : :
1364 : : /*
1365 : : * Sort the distances in descending order, so that the longest gaps are at
1366 : : * the front.
1367 : : */
758 nathan@postgresql.or 1368 : 3207 : qsort(distances, ndistances, sizeof(DistanceValue), compare_distances);
1369 : :
1815 tomas.vondra@postgre 1370 : 3207 : return distances;
1371 : : }
1372 : :
1373 : : /*
1374 : : * Builds expanded ranges for the existing ranges (and single-point ranges),
1375 : : * and also the new value (which did not fit into the array). This expanded
1376 : : * representation makes the processing a bit easier, as it allows handling
1377 : : * ranges and points the same way.
1378 : : *
1379 : : * We sort and deduplicate the expanded ranges - this is necessary, because
1380 : : * the points may be unsorted. And moreover the two parts (ranges and
1381 : : * points) are sorted on their own.
1382 : : */
1383 : : static ExpandedRange *
1384 : 3190 : build_expanded_ranges(FmgrInfo *cmp, Oid colloid, Ranges *ranges,
1385 : : int *nranges)
1386 : : {
1387 : : int neranges;
1388 : : ExpandedRange *eranges;
1389 : :
1390 : : /* both ranges and points are expanded into a separate element */
1391 : 3190 : neranges = ranges->nranges + ranges->nvalues;
1392 : :
1393 : 3190 : eranges = (ExpandedRange *) palloc0(neranges * sizeof(ExpandedRange));
1394 : :
1395 : : /* fill the expanded ranges */
1396 : 3190 : fill_expanded_ranges(eranges, neranges, ranges);
1397 : :
1398 : : /* sort and deduplicate the expanded ranges */
1399 : 3190 : neranges = sort_expanded_ranges(cmp, colloid, eranges, neranges);
1400 : :
1401 : : /* remember how many ranges we built */
1402 : 3190 : *nranges = neranges;
1403 : :
1404 : 3190 : return eranges;
1405 : : }
1406 : :
1407 : : #ifdef USE_ASSERT_CHECKING
1408 : : /*
1409 : : * Counts boundary values needed to store the ranges. Each single-point
1410 : : * range is stored using a single value, each regular range needs two.
1411 : : */
1412 : : static int
1413 : 6397 : count_values(ExpandedRange *cranges, int ncranges)
1414 : : {
1415 : : int i;
1416 : : int count;
1417 : :
1418 : 6397 : count = 0;
1419 [ + + ]: 56624 : for (i = 0; i < ncranges; i++)
1420 : : {
1421 [ + + ]: 50227 : if (cranges[i].collapsed)
1422 : 45811 : count += 1;
1423 : : else
1424 : 4416 : count += 2;
1425 : : }
1426 : :
1427 : 6397 : return count;
1428 : : }
1429 : : #endif
1430 : :
1431 : : /*
1432 : : * reduce_expanded_ranges
1433 : : * reduce the ranges until the number of values is low enough
1434 : : *
1435 : : * Combines ranges until the number of boundary values drops below the
1436 : : * threshold specified by max_values. This happens by merging enough
1437 : : * ranges by the distance between them.
1438 : : *
1439 : : * Returns the number of result ranges.
1440 : : *
1441 : : * We simply use the global min/max and then add boundaries for enough
1442 : : * largest gaps. Each gap adds 2 values, so we simply use (target/2-1)
1443 : : * distances. Then we simply sort all the values - each two values are
1444 : : * a boundary of a range (possibly collapsed).
1445 : : *
1446 : : * XXX Some of the ranges may be collapsed (i.e. the min/max values are
1447 : : * equal), but we ignore that for now. We could repeat the process,
1448 : : * adding a couple more gaps recursively.
1449 : : *
1450 : : * XXX The ranges to merge are selected solely using the distance. But
1451 : : * that may not be the best strategy, for example when multiple gaps
1452 : : * are of equal (or very similar) length.
1453 : : *
1454 : : * Consider for example points 1, 2, 3, .., 64, which have gaps of the
1455 : : * same length 1 of course. In that case, we tend to pick the first
1456 : : * gap of that length, which leads to this:
1457 : : *
1458 : : * step 1: [1, 2], 3, 4, 5, .., 64
1459 : : * step 2: [1, 3], 4, 5, .., 64
1460 : : * step 3: [1, 4], 5, .., 64
1461 : : * ...
1462 : : *
1463 : : * So in the end we'll have one "large" range and multiple small points.
1464 : : * That may be fine, but it seems a bit strange and non-optimal. Maybe
1465 : : * we should consider other things when picking ranges to merge - e.g.
1466 : : * length of the ranges? Or perhaps randomize the choice of ranges, with
1467 : : * probability inversely proportional to the distance (the gap lengths
1468 : : * may be very close, but not exactly the same).
1469 : : *
1470 : : * XXX Or maybe we could just handle this by using random value as a
1471 : : * tie-break, or by adding random noise to the actual distance.
1472 : : */
1473 : : static int
1474 : 3207 : reduce_expanded_ranges(ExpandedRange *eranges, int neranges,
1475 : : DistanceValue *distances, int max_values,
1476 : : FmgrInfo *cmp, Oid colloid)
1477 : : {
1478 : : int i;
1479 : : int nvalues;
1480 : : Datum *values;
1481 : :
1482 : : compare_context cxt;
1483 : :
1484 : : /* total number of gaps between ranges */
1485 : 3207 : int ndistances = (neranges - 1);
1486 : :
1487 : : /* number of gaps to keep */
1488 : 3207 : int keep = (max_values / 2 - 1);
1489 : :
1490 : : /*
1491 : : * Maybe we have a sufficiently low number of ranges already?
1492 : : *
1493 : : * XXX This should happen before we actually do the expensive stuff like
1494 : : * sorting, so maybe this should be just an assert.
1495 : : */
1496 [ + + ]: 3207 : if (keep >= ndistances)
1497 : 2784 : return neranges;
1498 : :
1499 : : /* sort the values */
1500 : 423 : cxt.colloid = colloid;
1501 : 423 : cxt.cmpFn = cmp;
1502 : :
1503 : : /* allocate space for the boundary values */
1504 : 423 : nvalues = 0;
95 michael@paquier.xyz 1505 :GNC 423 : values = palloc_array(Datum, max_values);
1506 : :
1507 : : /* add the global min/max values, from the first/last range */
1815 tomas.vondra@postgre 1508 :CBC 423 : values[nvalues++] = eranges[0].minval;
1509 : 423 : values[nvalues++] = eranges[neranges - 1].maxval;
1510 : :
1511 : : /* add boundary values for enough gaps */
1512 [ + + ]: 14640 : for (i = 0; i < keep; i++)
1513 : : {
1514 : : /* index of the gap between (index) and (index+1) ranges */
1515 : 14217 : int index = distances[i].index;
1516 : :
1517 [ + - - + ]: 14217 : Assert((index >= 0) && ((index + 1) < neranges));
1518 : :
1519 : : /* add max from the preceding range, minval from the next one */
1520 : 14217 : values[nvalues++] = eranges[index].maxval;
1521 : 14217 : values[nvalues++] = eranges[index + 1].minval;
1522 : :
1523 [ - + ]: 14217 : Assert(nvalues <= max_values);
1524 : : }
1525 : :
1526 : : /* We should have an even number of range values. */
1527 [ - + ]: 423 : Assert(nvalues % 2 == 0);
1528 : :
1529 : : /*
1530 : : * Sort the values using the comparator function, and form ranges from the
1531 : : * sorted result.
1532 : : */
1533 : 423 : qsort_arg(values, nvalues, sizeof(Datum),
1534 : : compare_values, &cxt);
1535 : :
1536 : : /* We have nvalues boundary values, which means nvalues/2 ranges. */
1537 [ + + ]: 15063 : for (i = 0; i < (nvalues / 2); i++)
1538 : : {
1539 : 14640 : eranges[i].minval = values[2 * i];
1540 : 14640 : eranges[i].maxval = values[2 * i + 1];
1541 : :
1542 : : /* if the boundary values are the same, it's a collapsed range */
1543 : 29280 : eranges[i].collapsed = (compare_values(&values[2 * i],
1544 : 14640 : &values[2 * i + 1],
1545 : 14640 : &cxt) == 0);
1546 : : }
1547 : :
1548 : 423 : return (nvalues / 2);
1549 : : }
1550 : :
1551 : : /*
1552 : : * Store the boundary values from ExpandedRanges back into 'ranges' (using
1553 : : * only the minimal number of values needed).
1554 : : */
1555 : : static void
1556 : 3207 : store_expanded_ranges(Ranges *ranges, ExpandedRange *eranges, int neranges)
1557 : : {
1558 : : int i;
1559 : 3207 : int idx = 0;
1560 : :
1561 : : /* first copy in the regular ranges */
1562 : 3207 : ranges->nranges = 0;
1563 [ + + ]: 28404 : for (i = 0; i < neranges; i++)
1564 : : {
1565 [ + + ]: 25197 : if (!eranges[i].collapsed)
1566 : : {
1567 : 2208 : ranges->values[idx++] = eranges[i].minval;
1568 : 2208 : ranges->values[idx++] = eranges[i].maxval;
1569 : 2208 : ranges->nranges++;
1570 : : }
1571 : : }
1572 : :
1573 : : /* now copy in the collapsed ones */
1574 : 3207 : ranges->nvalues = 0;
1575 [ + + ]: 28404 : for (i = 0; i < neranges; i++)
1576 : : {
1577 [ + + ]: 25197 : if (eranges[i].collapsed)
1578 : : {
1579 : 22989 : ranges->values[idx++] = eranges[i].minval;
1580 : 22989 : ranges->nvalues++;
1581 : : }
1582 : : }
1583 : :
1584 : : /* all the values are sorted */
1585 : 3207 : ranges->nsorted = ranges->nvalues;
1586 : :
1587 [ - + ]: 3207 : Assert(count_values(eranges, neranges) == 2 * ranges->nranges + ranges->nvalues);
1588 [ - + ]: 3207 : Assert(2 * ranges->nranges + ranges->nvalues <= ranges->maxvalues);
1589 : 3207 : }
1590 : :
1591 : :
1592 : : /*
1593 : : * Consider freeing space in the ranges. Checks if there's space for at least
1594 : : * one new value, and performs compaction if needed.
1595 : : *
1596 : : * Returns true if the value was actually modified.
1597 : : */
1598 : : static bool
1599 : 70377 : ensure_free_space_in_buffer(BrinDesc *bdesc, Oid colloid,
1600 : : AttrNumber attno, Form_pg_attribute attr,
1601 : : Ranges *range)
1602 : : {
1603 : : MemoryContext ctx;
1604 : : MemoryContext oldctx;
1605 : :
1606 : : FmgrInfo *cmpFn,
1607 : : *distanceFn;
1608 : :
1609 : : /* expanded ranges */
1610 : : ExpandedRange *eranges;
1611 : : int neranges;
1612 : : DistanceValue *distances;
1613 : :
1614 : : /*
1615 : : * If there is free space in the buffer, we're done without having to
1616 : : * modify anything.
1617 : : */
1618 [ + + ]: 70377 : if (2 * range->nranges + range->nvalues < range->maxvalues)
1619 : 70254 : return false;
1620 : :
1621 : : /* we'll certainly need the comparator, so just look it up now */
1622 : 123 : cmpFn = minmax_multi_get_strategy_procinfo(bdesc, attno, attr->atttypid,
1623 : : BTLessStrategyNumber);
1624 : :
1625 : : /* deduplicate values, if there's an unsorted part */
1626 : 123 : range_deduplicate_values(range);
1627 : :
1628 : : /*
1629 : : * Did we reduce enough free space by just the deduplication?
1630 : : *
1631 : : * We don't simply check against range->maxvalues again. The deduplication
1632 : : * might have freed very little space (e.g. just one value), forcing us to
1633 : : * do deduplication very often. In that case, it's better to do the
1634 : : * compaction and reduce more space.
1635 : : */
1636 [ - + ]: 123 : if (2 * range->nranges + range->nvalues <= range->maxvalues * MINMAX_BUFFER_LOAD_FACTOR)
1815 tomas.vondra@postgre 1637 :UBC 0 : return true;
1638 : :
1639 : : /*
1640 : : * We need to combine some of the existing ranges, to reduce the number of
1641 : : * values we have to store.
1642 : : *
1643 : : * The distanceFn calls (which may internally call e.g. numeric_le) may
1644 : : * allocate quite a bit of memory, and we must not leak it (we might have
1645 : : * to do this repeatedly, even for a single BRIN page range). Otherwise
1646 : : * we'd have problems e.g. when building new indexes. So we use a memory
1647 : : * context and make sure we free the memory at the end (so if we call the
1648 : : * distance function many times, it might be an issue, but meh).
1649 : : */
1815 tomas.vondra@postgre 1650 :CBC 123 : ctx = AllocSetContextCreate(CurrentMemoryContext,
1651 : : "minmax-multi context",
1652 : : ALLOCSET_DEFAULT_SIZES);
1653 : :
1654 : 123 : oldctx = MemoryContextSwitchTo(ctx);
1655 : :
1656 : : /* build the expanded ranges */
1657 : 123 : eranges = build_expanded_ranges(cmpFn, colloid, range, &neranges);
1658 : :
1659 : : /* Is the expanded representation of ranges correct? */
987 1660 : 123 : AssertCheckExpandedRanges(bdesc, colloid, attno, attr, eranges, neranges);
1661 : :
1662 : : /* and we'll also need the 'distance' procedure */
1815 1663 : 123 : distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE);
1664 : :
1665 : : /* build array of gap distances and sort them in ascending order */
1666 : 123 : distances = build_distances(distanceFn, colloid, eranges, neranges);
1667 : :
1668 : : /*
1669 : : * Combine ranges until we release at least 50% of the space. This
1670 : : * threshold is somewhat arbitrary, perhaps needs tuning. We must not use
1671 : : * too low or high value.
1672 : : */
1673 : 246 : neranges = reduce_expanded_ranges(eranges, neranges, distances,
1674 : 123 : range->maxvalues * MINMAX_BUFFER_LOAD_FACTOR,
1675 : : cmpFn, colloid);
1676 : :
1677 : : /* Is the result of reducing expanded ranges correct? */
987 1678 : 123 : AssertCheckExpandedRanges(bdesc, colloid, attno, attr, eranges, neranges);
1679 : :
1680 : : /* Make sure we've sufficiently reduced the number of ranges. */
1815 1681 [ - + ]: 123 : Assert(count_values(eranges, neranges) <= range->maxvalues * MINMAX_BUFFER_LOAD_FACTOR);
1682 : :
1683 : : /* decompose the expanded ranges into regular ranges and single values */
1684 : 123 : store_expanded_ranges(range, eranges, neranges);
1685 : :
1686 : 123 : MemoryContextSwitchTo(oldctx);
1687 : 123 : MemoryContextDelete(ctx);
1688 : :
1689 : : /* Did we break the ranges somehow? */
1690 : 123 : AssertCheckRanges(range, cmpFn, colloid);
1691 : :
1692 : 123 : return true;
1693 : : }
1694 : :
1695 : : /*
1696 : : * range_add_value
1697 : : * Add the new value to the minmax-multi range.
1698 : : */
1699 : : static bool
1700 : 70377 : range_add_value(BrinDesc *bdesc, Oid colloid,
1701 : : AttrNumber attno, Form_pg_attribute attr,
1702 : : Ranges *ranges, Datum newval)
1703 : : {
1704 : : FmgrInfo *cmpFn;
1705 : 70377 : bool modified = false;
1706 : :
1707 : : /* we'll certainly need the comparator, so just look it up now */
1708 : 70377 : cmpFn = minmax_multi_get_strategy_procinfo(bdesc, attno, attr->atttypid,
1709 : : BTLessStrategyNumber);
1710 : :
1711 : : /* comprehensive checks of the input ranges */
1712 : 70377 : AssertCheckRanges(ranges, cmpFn, colloid);
1713 : :
1714 : : /*
1715 : : * Make sure there's enough free space in the buffer. We only trigger this
1716 : : * when the buffer is full, which means it had to be modified as we size
1717 : : * it to be larger than what is stored on disk.
1718 : : *
1719 : : * This needs to happen before we check if the value is contained in the
1720 : : * range, because the value might be in the unsorted part, and we don't
1721 : : * check that in range_contains_value. The deduplication would then move
1722 : : * it to the sorted part, and we'd add the value too, which violates the
1723 : : * rule that we never have duplicates with the ranges or sorted values.
1724 : : *
1725 : : * We might also deduplicate and recheck if the value is contained, but
1726 : : * that seems like overkill. We'd need to deduplicate anyway, so why not
1727 : : * do it now.
1728 : : */
1729 : 70377 : modified = ensure_free_space_in_buffer(bdesc, colloid,
1730 : : attno, attr, ranges);
1731 : :
1732 : : /*
1733 : : * Bail out if the value already is covered by the range.
1734 : : *
1735 : : * We could also add values until we hit values_per_range, and then do the
1736 : : * deduplication in a batch, hoping for better efficiency. But that would
1737 : : * mean we actually modify the range every time, which means having to
1738 : : * serialize the value, which does palloc, walks the values, copies them,
1739 : : * etc. Not exactly cheap.
1740 : : *
1741 : : * So instead we do the check, which should be fairly cheap - assuming the
1742 : : * comparator function is not very expensive.
1743 : : *
1744 : : * This also implies the values array can't contain duplicate values.
1745 : : */
1746 [ + + ]: 70377 : if (range_contains_value(bdesc, colloid, attno, attr, ranges, newval, false))
1747 : 8124 : return modified;
1748 : :
1749 : : /* Make a copy of the value, if needed. */
1750 : 62253 : newval = datumCopy(newval, attr->attbyval, attr->attlen);
1751 : :
1752 : : /*
1753 : : * If there's space in the values array, copy it in and we're done.
1754 : : *
1755 : : * We do want to keep the values sorted (to speed up searches), so we do a
1756 : : * simple insertion sort. We could do something more elaborate, e.g. by
1757 : : * sorting the values only now and then, but for small counts (e.g. when
1758 : : * maxvalues is 64) this should be fine.
1759 : : */
1760 : 62253 : ranges->values[2 * ranges->nranges + ranges->nvalues] = newval;
1761 : 62253 : ranges->nvalues++;
1762 : :
1763 : : /* If we added the first value, we can consider it as sorted. */
1764 [ + + ]: 62253 : if (ranges->nvalues == 1)
1765 : 2495 : ranges->nsorted = 1;
1766 : :
1767 : : /*
1768 : : * Check we haven't broken the ordering of boundary values (checks both
1769 : : * parts, but that doesn't hurt).
1770 : : */
1771 : 62253 : AssertCheckRanges(ranges, cmpFn, colloid);
1772 : :
1773 : : /* Check the range contains the value we just added. */
1774 [ - + ]: 62253 : Assert(range_contains_value(bdesc, colloid, attno, attr, ranges, newval, true));
1775 : :
1776 : : /* yep, we've modified the range */
1777 : 62253 : return true;
1778 : : }
1779 : :
1780 : : /*
1781 : : * Generate range representation of data collected during "batch mode".
1782 : : * This is similar to reduce_expanded_ranges, except that we can't assume
1783 : : * the values are sorted and there may be duplicate values.
1784 : : */
1785 : : static void
1786 : 9068 : compactify_ranges(BrinDesc *bdesc, Ranges *ranges, int max_values)
1787 : : {
1788 : : FmgrInfo *cmpFn,
1789 : : *distanceFn;
1790 : :
1791 : : /* expanded ranges */
1792 : : ExpandedRange *eranges;
1793 : : int neranges;
1794 : : DistanceValue *distances;
1795 : :
1796 : : MemoryContext ctx;
1797 : : MemoryContext oldctx;
1798 : :
1799 : : /*
1800 : : * Do we need to actually compactify anything?
1801 : : *
1802 : : * There are two reasons why compaction may be needed - firstly, there may
1803 : : * be too many values, or some of the values may be unsorted.
1804 : : */
1805 [ + + ]: 9068 : if ((ranges->nranges * 2 + ranges->nvalues <= max_values) &&
1806 [ + + ]: 8825 : (ranges->nsorted == ranges->nvalues))
1807 : 6001 : return;
1808 : :
1809 : : /* we'll certainly need the comparator, so just look it up now */
1810 : 3067 : cmpFn = minmax_multi_get_strategy_procinfo(bdesc, ranges->attno, ranges->typid,
1811 : : BTLessStrategyNumber);
1812 : :
1813 : : /* and we'll also need the 'distance' procedure */
1814 : 3067 : distanceFn = minmax_multi_get_procinfo(bdesc, ranges->attno, PROCNUM_DISTANCE);
1815 : :
1816 : : /*
1817 : : * The distanceFn calls (which may internally call e.g. numeric_le) may
1818 : : * allocate quite a bit of memory, and we must not leak it. Otherwise,
1819 : : * we'd have problems e.g. when building indexes. So we create a local
1820 : : * memory context and make sure we free the memory before leaving this
1821 : : * function (not after every call).
1822 : : */
1823 : 3067 : ctx = AllocSetContextCreate(CurrentMemoryContext,
1824 : : "minmax-multi context",
1825 : : ALLOCSET_DEFAULT_SIZES);
1826 : :
1827 : 3067 : oldctx = MemoryContextSwitchTo(ctx);
1828 : :
1829 : : /* build the expanded ranges */
1830 : 3067 : eranges = build_expanded_ranges(cmpFn, ranges->colloid, ranges, &neranges);
1831 : :
1832 : : /* build array of gap distances and sort them in ascending order */
1833 : 3067 : distances = build_distances(distanceFn, ranges->colloid,
1834 : : eranges, neranges);
1835 : :
1836 : : /*
1837 : : * Combine ranges until we get below max_values. We don't use any scale
1838 : : * factor, because this is used during serialization, and we don't expect
1839 : : * more tuples to be inserted anytime soon.
1840 : : */
1841 : 3067 : neranges = reduce_expanded_ranges(eranges, neranges, distances,
1842 : : max_values, cmpFn, ranges->colloid);
1843 : :
1844 [ - + ]: 3067 : Assert(count_values(eranges, neranges) <= max_values);
1845 : :
1846 : : /* transform back into regular ranges and single values */
1847 : 3067 : store_expanded_ranges(ranges, eranges, neranges);
1848 : :
1849 : : /* check all the range invariants */
1850 : 3067 : AssertCheckRanges(ranges, cmpFn, ranges->colloid);
1851 : :
1852 : 3067 : MemoryContextSwitchTo(oldctx);
1853 : 3067 : MemoryContextDelete(ctx);
1854 : : }
1855 : :
1856 : : Datum
1857 : 9754 : brin_minmax_multi_opcinfo(PG_FUNCTION_ARGS)
1858 : : {
1859 : : BrinOpcInfo *result;
1860 : :
1861 : : /*
1862 : : * opaque->strategy_procinfos is initialized lazily; here it is set to
1863 : : * all-uninitialized by palloc0 which sets fn_oid to InvalidOid.
1864 : : */
1865 : :
1866 : 9754 : result = palloc0(MAXALIGN(SizeofBrinOpcInfo(1)) +
1867 : : sizeof(MinmaxMultiOpaque));
1868 : 9754 : result->oi_nstored = 1;
1869 : 9754 : result->oi_regular_nulls = true;
1870 : 9754 : result->oi_opaque = (MinmaxMultiOpaque *)
1871 : 9754 : MAXALIGN((char *) result + SizeofBrinOpcInfo(1));
1872 : 9754 : result->oi_typcache[0] = lookup_type_cache(PG_BRIN_MINMAX_MULTI_SUMMARYOID, 0);
1873 : :
1874 : 9754 : PG_RETURN_POINTER(result);
1875 : : }
1876 : :
1877 : : /*
1878 : : * Compute the distance between two float4 values (plain subtraction).
1879 : : */
1880 : : Datum
1881 : 354 : brin_minmax_multi_distance_float4(PG_FUNCTION_ARGS)
1882 : : {
1883 : 354 : float a1 = PG_GETARG_FLOAT4(0);
1884 : 354 : float a2 = PG_GETARG_FLOAT4(1);
1885 : :
1886 : : /* if both values are NaN, then we consider them the same */
1590 1887 [ - + - - ]: 354 : if (isnan(a1) && isnan(a2))
1590 tomas.vondra@postgre 1888 :UBC 0 : PG_RETURN_FLOAT8(0.0);
1889 : :
1890 : : /* if one value is NaN, use infinite distance */
1590 tomas.vondra@postgre 1891 [ + - + + ]:CBC 354 : if (isnan(a1) || isnan(a2))
1892 : 3 : PG_RETURN_FLOAT8(get_float8_infinity());
1893 : :
1894 : : /*
1895 : : * We know the values are range boundaries, but the range may be collapsed
1896 : : * (i.e. single points), with equal values.
1897 : : */
1815 1898 [ - + ]: 351 : Assert(a1 <= a2);
1899 : :
1900 : 351 : PG_RETURN_FLOAT8((double) a2 - (double) a1);
1901 : : }
1902 : :
1903 : : /*
1904 : : * Compute the distance between two float8 values (plain subtraction).
1905 : : */
1906 : : Datum
1907 : 528 : brin_minmax_multi_distance_float8(PG_FUNCTION_ARGS)
1908 : : {
1909 : 528 : double a1 = PG_GETARG_FLOAT8(0);
1910 : 528 : double a2 = PG_GETARG_FLOAT8(1);
1911 : :
1912 : : /* if both values are NaN, then we consider them the same */
1590 1913 [ - + - - ]: 528 : if (isnan(a1) && isnan(a2))
1590 tomas.vondra@postgre 1914 :UBC 0 : PG_RETURN_FLOAT8(0.0);
1915 : :
1916 : : /* if one value is NaN, use infinite distance */
1590 tomas.vondra@postgre 1917 [ + - + + ]:CBC 528 : if (isnan(a1) || isnan(a2))
1918 : 3 : PG_RETURN_FLOAT8(get_float8_infinity());
1919 : :
1920 : : /*
1921 : : * We know the values are range boundaries, but the range may be collapsed
1922 : : * (i.e. single points), with equal values.
1923 : : */
1815 1924 [ - + ]: 525 : Assert(a1 <= a2);
1925 : :
1926 : 525 : PG_RETURN_FLOAT8(a2 - a1);
1927 : : }
1928 : :
1929 : : /*
1930 : : * Compute the distance between two int2 values (plain subtraction).
1931 : : */
1932 : : Datum
1933 : 513 : brin_minmax_multi_distance_int2(PG_FUNCTION_ARGS)
1934 : : {
1935 : 513 : int16 a1 = PG_GETARG_INT16(0);
1936 : 513 : int16 a2 = PG_GETARG_INT16(1);
1937 : :
1938 : : /*
1939 : : * We know the values are range boundaries, but the range may be collapsed
1940 : : * (i.e. single points), with equal values.
1941 : : */
1942 [ - + ]: 513 : Assert(a1 <= a2);
1943 : :
1944 : 513 : PG_RETURN_FLOAT8((double) a2 - (double) a1);
1945 : : }
1946 : :
1947 : : /*
1948 : : * Compute the distance between two int4 values (plain subtraction).
1949 : : */
1950 : : Datum
1951 : 43389 : brin_minmax_multi_distance_int4(PG_FUNCTION_ARGS)
1952 : : {
1953 : 43389 : int32 a1 = PG_GETARG_INT32(0);
1954 : 43389 : int32 a2 = PG_GETARG_INT32(1);
1955 : :
1956 : : /*
1957 : : * We know the values are range boundaries, but the range may be collapsed
1958 : : * (i.e. single points), with equal values.
1959 : : */
1960 [ - + ]: 43389 : Assert(a1 <= a2);
1961 : :
1962 : 43389 : PG_RETURN_FLOAT8((double) a2 - (double) a1);
1963 : : }
1964 : :
1965 : : /*
1966 : : * Compute the distance between two int8 values (plain subtraction).
1967 : : */
1968 : : Datum
1969 : 5791 : brin_minmax_multi_distance_int8(PG_FUNCTION_ARGS)
1970 : : {
1971 : 5791 : int64 a1 = PG_GETARG_INT64(0);
1972 : 5791 : int64 a2 = PG_GETARG_INT64(1);
1973 : :
1974 : : /*
1975 : : * We know the values are range boundaries, but the range may be collapsed
1976 : : * (i.e. single points), with equal values.
1977 : : */
1978 [ - + ]: 5791 : Assert(a1 <= a2);
1979 : :
1980 : 5791 : PG_RETURN_FLOAT8((double) a2 - (double) a1);
1981 : : }
1982 : :
1983 : : /*
1984 : : * Compute the distance between two tid values (by mapping them to float8 and
1985 : : * then subtracting them).
1986 : : */
1987 : : Datum
1988 : 519 : brin_minmax_multi_distance_tid(PG_FUNCTION_ARGS)
1989 : : {
1990 : : double da1,
1991 : : da2;
1992 : :
219 peter@eisentraut.org 1993 :GNC 519 : ItemPointer pa1 = (ItemPointer) PG_GETARG_POINTER(0);
1994 : 519 : ItemPointer pa2 = (ItemPointer) PG_GETARG_POINTER(1);
1995 : :
1996 : : /*
1997 : : * We know the values are range boundaries, but the range may be collapsed
1998 : : * (i.e. single points), with equal values.
1999 : : */
1815 tomas.vondra@postgre 2000 [ - + ]:CBC 519 : Assert(ItemPointerCompare(pa1, pa2) <= 0);
2001 : :
2002 : : /*
2003 : : * We use the no-check variants here, because user-supplied values may
2004 : : * have (ip_posid == 0). See ItemPointerCompare.
2005 : : */
2006 : 519 : da1 = ItemPointerGetBlockNumberNoCheck(pa1) * MaxHeapTuplesPerPage +
2007 : 519 : ItemPointerGetOffsetNumberNoCheck(pa1);
2008 : :
2009 : 519 : da2 = ItemPointerGetBlockNumberNoCheck(pa2) * MaxHeapTuplesPerPage +
2010 : 519 : ItemPointerGetOffsetNumberNoCheck(pa2);
2011 : :
2012 : 519 : PG_RETURN_FLOAT8(da2 - da1);
2013 : : }
2014 : :
2015 : : /*
2016 : : * Compute the distance between two numeric values (plain subtraction).
2017 : : */
2018 : : Datum
2019 : 519 : brin_minmax_multi_distance_numeric(PG_FUNCTION_ARGS)
2020 : : {
2021 : : Datum d;
2022 : 519 : Datum a1 = PG_GETARG_DATUM(0);
2023 : 519 : Datum a2 = PG_GETARG_DATUM(1);
2024 : :
2025 : : /*
2026 : : * We know the values are range boundaries, but the range may be collapsed
2027 : : * (i.e. single points), with equal values.
2028 : : */
2029 [ - + ]: 519 : Assert(DatumGetBool(DirectFunctionCall2(numeric_le, a1, a2)));
2030 : :
2031 : 519 : d = DirectFunctionCall2(numeric_sub, a2, a1); /* a2 - a1 */
2032 : :
222 tgl@sss.pgh.pa.us 2033 : 519 : PG_RETURN_DATUM(DirectFunctionCall1(numeric_float8, d));
2034 : : }
2035 : :
2036 : : /*
2037 : : * Compute the approximate distance between two UUID values.
2038 : : *
2039 : : * XXX We do not need a perfectly accurate value, so we approximate the
2040 : : * deltas (which would have to be 128-bit integers) with a 64-bit float.
2041 : : * The small inaccuracies do not matter in practice, in the worst case
2042 : : * we'll decide to merge ranges that are not the closest ones.
2043 : : */
2044 : : Datum
1815 tomas.vondra@postgre 2045 : 866 : brin_minmax_multi_distance_uuid(PG_FUNCTION_ARGS)
2046 : : {
2047 : : int i;
2048 : 866 : float8 delta = 0;
2049 : :
2050 : 866 : Datum a1 = PG_GETARG_DATUM(0);
2051 : 866 : Datum a2 = PG_GETARG_DATUM(1);
2052 : :
2053 : 866 : pg_uuid_t *u1 = DatumGetUUIDP(a1);
2054 : 866 : pg_uuid_t *u2 = DatumGetUUIDP(a2);
2055 : :
2056 : : /*
2057 : : * We know the values are range boundaries, but the range may be collapsed
2058 : : * (i.e. single points), with equal values.
2059 : : */
2060 [ - + ]: 866 : Assert(DatumGetBool(DirectFunctionCall2(uuid_le, a1, a2)));
2061 : :
2062 : : /* compute approximate delta as a double precision value */
2063 [ + + ]: 14722 : for (i = UUID_LEN - 1; i >= 0; i--)
2064 : : {
2065 : 13856 : delta += (int) u2->data[i] - (int) u1->data[i];
2066 : 13856 : delta /= 256;
2067 : : }
2068 : :
2069 [ - + ]: 866 : Assert(delta >= 0);
2070 : :
2071 : 866 : PG_RETURN_FLOAT8(delta);
2072 : : }
2073 : :
2074 : : /*
2075 : : * Compute the approximate distance between two dates.
2076 : : */
2077 : : Datum
2078 : 819 : brin_minmax_multi_distance_date(PG_FUNCTION_ARGS)
2079 : : {
870 2080 : 819 : float8 delta = 0;
1815 2081 : 819 : DateADT dateVal1 = PG_GETARG_DATEADT(0);
2082 : 819 : DateADT dateVal2 = PG_GETARG_DATEADT(1);
2083 : :
870 2084 : 819 : delta = (float8) dateVal2 - (float8) dateVal1;
2085 : :
2086 [ - + ]: 819 : Assert(delta >= 0);
2087 : :
2088 : 819 : PG_RETURN_FLOAT8(delta);
2089 : : }
2090 : :
2091 : : /*
2092 : : * Compute the approximate distance between two time (without tz) values.
2093 : : *
2094 : : * TimeADT is just an int64, so we simply subtract the values directly.
2095 : : */
2096 : : Datum
1815 2097 : 513 : brin_minmax_multi_distance_time(PG_FUNCTION_ARGS)
2098 : : {
2099 : 513 : float8 delta = 0;
2100 : :
2101 : 513 : TimeADT ta = PG_GETARG_TIMEADT(0);
2102 : 513 : TimeADT tb = PG_GETARG_TIMEADT(1);
2103 : :
2104 : 513 : delta = (tb - ta);
2105 : :
2106 [ - + ]: 513 : Assert(delta >= 0);
2107 : :
2108 : 513 : PG_RETURN_FLOAT8(delta);
2109 : : }
2110 : :
2111 : : /*
2112 : : * Compute the approximate distance between two timetz values.
2113 : : *
2114 : : * Simply subtracts the TimeADT (int64) values embedded in TimeTzADT.
2115 : : */
2116 : : Datum
2117 : 399 : brin_minmax_multi_distance_timetz(PG_FUNCTION_ARGS)
2118 : : {
2119 : 399 : float8 delta = 0;
2120 : :
2121 : 399 : TimeTzADT *ta = PG_GETARG_TIMETZADT_P(0);
2122 : 399 : TimeTzADT *tb = PG_GETARG_TIMETZADT_P(1);
2123 : :
1806 2124 : 399 : delta = (tb->time - ta->time) + (tb->zone - ta->zone) * USECS_PER_SEC;
2125 : :
1815 2126 [ - + ]: 399 : Assert(delta >= 0);
2127 : :
2128 : 399 : PG_RETURN_FLOAT8(delta);
2129 : : }
2130 : :
2131 : : /*
2132 : : * Compute the distance between two timestamp values.
2133 : : */
2134 : : Datum
2135 : 1332 : brin_minmax_multi_distance_timestamp(PG_FUNCTION_ARGS)
2136 : : {
2137 : 1332 : float8 delta = 0;
2138 : :
2139 : 1332 : Timestamp dt1 = PG_GETARG_TIMESTAMP(0);
2140 : 1332 : Timestamp dt2 = PG_GETARG_TIMESTAMP(1);
2141 : :
870 2142 : 1332 : delta = (float8) dt2 - (float8) dt1;
2143 : :
1815 2144 [ - + ]: 1332 : Assert(delta >= 0);
2145 : :
2146 : 1332 : PG_RETURN_FLOAT8(delta);
2147 : : }
2148 : :
2149 : : /*
2150 : : * Compute the distance between two interval values.
2151 : : */
2152 : : Datum
2153 : 768 : brin_minmax_multi_distance_interval(PG_FUNCTION_ARGS)
2154 : : {
2155 : 768 : float8 delta = 0;
2156 : :
2157 : 768 : Interval *ia = PG_GETARG_INTERVAL_P(0);
2158 : 768 : Interval *ib = PG_GETARG_INTERVAL_P(1);
2159 : :
2160 : : int64 dayfraction;
2161 : : int64 days;
2162 : :
2163 : : /*
2164 : : * Delta is (fractional) number of days between the intervals. Assume
2165 : : * months have 30 days for consistency with interval_cmp_internal. We
2166 : : * don't need to be exact, in the worst case we'll build a bit less
2167 : : * efficient ranges. But we should not contradict interval_cmp.
2168 : : */
870 2169 : 768 : dayfraction = (ib->time % USECS_PER_DAY) - (ia->time % USECS_PER_DAY);
2170 : 768 : days = (ib->time / USECS_PER_DAY) - (ia->time / USECS_PER_DAY);
2171 : 768 : days += (int64) ib->day - (int64) ia->day;
2172 : 768 : days += ((int64) ib->month - (int64) ia->month) * INT64CONST(30);
2173 : :
2174 : : /* convert to double precision */
1806 2175 : 768 : delta = (double) days + dayfraction / (double) USECS_PER_DAY;
2176 : :
1815 2177 [ - + ]: 768 : Assert(delta >= 0);
2178 : :
2179 : 768 : PG_RETURN_FLOAT8(delta);
2180 : : }
2181 : :
2182 : : /*
2183 : : * Compute the distance between two pg_lsn values.
2184 : : *
2185 : : * LSN is just an int64 encoding position in the stream, so just subtract
2186 : : * those int64 values directly.
2187 : : */
2188 : : Datum
2189 : 519 : brin_minmax_multi_distance_pg_lsn(PG_FUNCTION_ARGS)
2190 : : {
2191 : 519 : float8 delta = 0;
2192 : :
2193 : 519 : XLogRecPtr lsna = PG_GETARG_LSN(0);
2194 : 519 : XLogRecPtr lsnb = PG_GETARG_LSN(1);
2195 : :
2196 : 519 : delta = (lsnb - lsna);
2197 : :
2198 [ - + ]: 519 : Assert(delta >= 0);
2199 : :
2200 : 519 : PG_RETURN_FLOAT8(delta);
2201 : : }
2202 : :
2203 : : /*
2204 : : * Compute the distance between two macaddr values.
2205 : : *
2206 : : * mac addresses are treated as 6 unsigned chars, so do the same thing we
2207 : : * already do for UUID values.
2208 : : */
2209 : : Datum
2210 : 399 : brin_minmax_multi_distance_macaddr(PG_FUNCTION_ARGS)
2211 : : {
2212 : : float8 delta;
2213 : :
2214 : 399 : macaddr *a = PG_GETARG_MACADDR_P(0);
2215 : 399 : macaddr *b = PG_GETARG_MACADDR_P(1);
2216 : :
2217 : 399 : delta = ((float8) b->f - (float8) a->f);
2218 : 399 : delta /= 256;
2219 : :
2220 : 399 : delta += ((float8) b->e - (float8) a->e);
2221 : 399 : delta /= 256;
2222 : :
2223 : 399 : delta += ((float8) b->d - (float8) a->d);
2224 : 399 : delta /= 256;
2225 : :
2226 : 399 : delta += ((float8) b->c - (float8) a->c);
2227 : 399 : delta /= 256;
2228 : :
2229 : 399 : delta += ((float8) b->b - (float8) a->b);
2230 : 399 : delta /= 256;
2231 : :
2232 : 399 : delta += ((float8) b->a - (float8) a->a);
2233 : 399 : delta /= 256;
2234 : :
2235 [ - + ]: 399 : Assert(delta >= 0);
2236 : :
2237 : 399 : PG_RETURN_FLOAT8(delta);
2238 : : }
2239 : :
2240 : : /*
2241 : : * Compute the distance between two macaddr8 values.
2242 : : *
2243 : : * macaddr8 addresses are 8 unsigned chars, so do the same thing we
2244 : : * already do for UUID values.
2245 : : */
2246 : : Datum
2247 : 519 : brin_minmax_multi_distance_macaddr8(PG_FUNCTION_ARGS)
2248 : : {
2249 : : float8 delta;
2250 : :
2251 : 519 : macaddr8 *a = PG_GETARG_MACADDR8_P(0);
2252 : 519 : macaddr8 *b = PG_GETARG_MACADDR8_P(1);
2253 : :
2254 : 519 : delta = ((float8) b->h - (float8) a->h);
2255 : 519 : delta /= 256;
2256 : :
2257 : 519 : delta += ((float8) b->g - (float8) a->g);
2258 : 519 : delta /= 256;
2259 : :
2260 : 519 : delta += ((float8) b->f - (float8) a->f);
2261 : 519 : delta /= 256;
2262 : :
2263 : 519 : delta += ((float8) b->e - (float8) a->e);
2264 : 519 : delta /= 256;
2265 : :
2266 : 519 : delta += ((float8) b->d - (float8) a->d);
2267 : 519 : delta /= 256;
2268 : :
2269 : 519 : delta += ((float8) b->c - (float8) a->c);
2270 : 519 : delta /= 256;
2271 : :
2272 : 519 : delta += ((float8) b->b - (float8) a->b);
2273 : 519 : delta /= 256;
2274 : :
2275 : 519 : delta += ((float8) b->a - (float8) a->a);
2276 : 519 : delta /= 256;
2277 : :
2278 [ - + ]: 519 : Assert(delta >= 0);
2279 : :
2280 : 519 : PG_RETURN_FLOAT8(delta);
2281 : : }
2282 : :
2283 : : /*
2284 : : * Compute the distance between two inet values.
2285 : : *
2286 : : * The distance is defined as the difference between 32-bit/128-bit values,
2287 : : * depending on the IP version. The distance is computed by subtracting
2288 : : * the bytes and normalizing it to [0,1] range for each IP family.
2289 : : * Addresses from different families are considered to be in maximum
2290 : : * distance, which is 1.0.
2291 : : *
2292 : : * XXX Does this need to consider the mask (bits)? For now, it's ignored.
2293 : : */
2294 : : Datum
2295 : 1161 : brin_minmax_multi_distance_inet(PG_FUNCTION_ARGS)
2296 : : {
2297 : : float8 delta;
2298 : : int i;
2299 : : int len;
2300 : : unsigned char *addra,
2301 : : *addrb;
2302 : :
2303 : 1161 : inet *ipa = PG_GETARG_INET_PP(0);
2304 : 1161 : inet *ipb = PG_GETARG_INET_PP(1);
2305 : :
2306 : : int lena,
2307 : : lenb;
2308 : :
2309 : : /*
2310 : : * If the addresses are from different families, consider them to be in
2311 : : * maximal possible distance (which is 1.0).
2312 : : */
2313 [ + + + - : 1161 : if (ip_family(ipa) != ip_family(ipb))
+ + ]
2314 : 96 : PG_RETURN_FLOAT8(1.0);
2315 : :
1806 2316 [ + + + + ]: 1065 : addra = (unsigned char *) palloc(ip_addrsize(ipa));
2317 [ + + + + : 1065 : memcpy(addra, ip_addr(ipa), ip_addrsize(ipa));
+ - ]
2318 : :
2319 [ + + + + ]: 1065 : addrb = (unsigned char *) palloc(ip_addrsize(ipb));
2320 [ + + + + : 1065 : memcpy(addrb, ip_addr(ipb), ip_addrsize(ipb));
+ - ]
2321 : :
2322 : : /*
2323 : : * The length is calculated from the mask length, because we sort the
2324 : : * addresses by first address in the range, so A.B.C.D/24 < A.B.C.1 (the
2325 : : * first range starts at A.B.C.0, which is before A.B.C.1). We don't want
2326 : : * to produce a negative delta in this case, so we just cut the extra
2327 : : * bytes.
2328 : : *
2329 : : * XXX Maybe this should be a bit more careful and cut the bits, not just
2330 : : * whole bytes.
2331 : : */
2332 [ + - ]: 1065 : lena = ip_bits(ipa);
2333 [ + - ]: 1065 : lenb = ip_bits(ipb);
2334 : :
2335 [ + + + + ]: 1065 : len = ip_addrsize(ipa);
2336 : :
2337 : : /* apply the network mask to both addresses */
2338 [ + + ]: 8061 : for (i = 0; i < len; i++)
2339 : : {
2340 : : unsigned char mask;
2341 : : int nbits;
2342 : :
1091 2343 : 6996 : nbits = Max(0, lena - (i * 8));
1806 2344 [ + + ]: 6996 : if (nbits < 8)
2345 : : {
2346 : 837 : mask = (0xFF << (8 - nbits));
2347 : 837 : addra[i] = (addra[i] & mask);
2348 : : }
2349 : :
1091 2350 : 6996 : nbits = Max(0, lenb - (i * 8));
1806 2351 [ + + ]: 6996 : if (nbits < 8)
2352 : : {
2353 : 834 : mask = (0xFF << (8 - nbits));
2354 : 834 : addrb[i] = (addrb[i] & mask);
2355 : : }
2356 : : }
2357 : :
2358 : : /* Calculate the difference between the addresses. */
1815 2359 : 1065 : delta = 0;
2360 [ + + ]: 8061 : for (i = len - 1; i >= 0; i--)
2361 : : {
1806 2362 : 6996 : unsigned char a = addra[i];
2363 : 6996 : unsigned char b = addrb[i];
2364 : :
2365 : 6996 : delta += (float8) b - (float8) a;
1815 2366 : 6996 : delta /= 256;
2367 : : }
2368 : :
2369 [ + - - + ]: 1065 : Assert((delta >= 0) && (delta <= 1));
2370 : :
1806 2371 : 1065 : pfree(addra);
2372 : 1065 : pfree(addrb);
2373 : :
1815 2374 : 1065 : PG_RETURN_FLOAT8(delta);
2375 : : }
2376 : :
2377 : : static void
2378 : 9068 : brin_minmax_multi_serialize(BrinDesc *bdesc, Datum src, Datum *dst)
2379 : : {
2380 : 9068 : Ranges *ranges = (Ranges *) DatumGetPointer(src);
2381 : : SerializedRanges *s;
2382 : :
2383 : : /*
2384 : : * In batch mode, we need to compress the accumulated values to the
2385 : : * actually requested number of values/ranges.
2386 : : */
2387 : 9068 : compactify_ranges(bdesc, ranges, ranges->target_maxvalues);
2388 : :
2389 : : /* At this point everything has to be fully sorted. */
2390 [ - + ]: 9068 : Assert(ranges->nsorted == ranges->nvalues);
2391 : :
1525 peter@eisentraut.org 2392 : 9068 : s = brin_range_serialize(ranges);
1815 tomas.vondra@postgre 2393 : 9068 : dst[0] = PointerGetDatum(s);
2394 : 9068 : }
2395 : :
2396 : : static int
2397 : 2495 : brin_minmax_multi_get_values(BrinDesc *bdesc, MinMaxMultiOptions *opts)
2398 : : {
2399 [ + - + - ]: 2495 : return MinMaxMultiGetValuesPerRange(opts);
2400 : : }
2401 : :
2402 : : /*
2403 : : * Examine the given index tuple (which contains the partial status of a
2404 : : * certain page range) by comparing it to the given value that comes from
2405 : : * another heap tuple. If the new value is outside the min/max range
2406 : : * specified by the existing tuple values, update the index tuple and return
2407 : : * true. Otherwise, return false and do not modify in this case.
2408 : : */
2409 : : Datum
2410 : 70377 : brin_minmax_multi_add_value(PG_FUNCTION_ARGS)
2411 : : {
2412 : 70377 : BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0);
2413 : 70377 : BrinValues *column = (BrinValues *) PG_GETARG_POINTER(1);
2414 : 70377 : Datum newval = PG_GETARG_DATUM(2);
219 peter@eisentraut.org 2415 :GNC 70377 : bool isnull PG_USED_FOR_ASSERTS_ONLY = PG_GETARG_BOOL(3);
1815 tomas.vondra@postgre 2416 :CBC 70377 : MinMaxMultiOptions *opts = (MinMaxMultiOptions *) PG_GET_OPCLASS_OPTIONS();
2417 : 70377 : Oid colloid = PG_GET_COLLATION();
2418 : 70377 : bool modified = false;
2419 : : Form_pg_attribute attr;
2420 : : AttrNumber attno;
2421 : : Ranges *ranges;
2422 : 70377 : SerializedRanges *serialized = NULL;
2423 : :
2424 [ - + ]: 70377 : Assert(!isnull);
2425 : :
2426 : 70377 : attno = column->bv_attno;
2427 : 70377 : attr = TupleDescAttr(bdesc->bd_tupdesc, attno - 1);
2428 : :
2429 : : /* use the already deserialized value, if possible */
2430 : 70377 : ranges = (Ranges *) DatumGetPointer(column->bv_mem_value);
2431 : :
2432 : : /*
2433 : : * If this is the first non-null value, we need to initialize the range
2434 : : * list. Otherwise, just extract the existing range list from BrinValues.
2435 : : *
2436 : : * When starting with an empty range, we assume this is a batch mode and
2437 : : * we use a larger buffer. The buffer size is derived from the BRIN range
2438 : : * size, number of rows per page, with some sensible min/max values. A
2439 : : * small buffer would be bad for performance, but a large buffer might
2440 : : * require a lot of memory (because of keeping all the values).
2441 : : */
2442 [ + + ]: 70377 : if (column->bv_allnulls)
2443 : : {
2444 : : MemoryContext oldctx;
2445 : :
2446 : : int target_maxvalues;
2447 : : int maxvalues;
2448 [ + - - + : 2495 : BlockNumber pagesPerRange = BrinGetPagesPerRange(bdesc->bd_index);
+ + ]
2449 : :
2450 : : /* what was specified as a reloption? */
2451 : 2495 : target_maxvalues = brin_minmax_multi_get_values(bdesc, opts);
2452 : :
2453 : : /*
2454 : : * Determine the insert buffer size - we use 10x the target, capped to
2455 : : * the maximum number of values in the heap range. This is more than
2456 : : * enough, considering the actual number of rows per page is likely
2457 : : * much lower, but meh.
2458 : : */
2459 : 2495 : maxvalues = Min(target_maxvalues * MINMAX_BUFFER_FACTOR,
2460 : : MaxHeapTuplesPerPage * pagesPerRange);
2461 : :
2462 : : /* but always at least the original value */
2463 : 2495 : maxvalues = Max(maxvalues, target_maxvalues);
2464 : :
2465 : : /* always cap by MIN/MAX */
2466 : 2495 : maxvalues = Max(maxvalues, MINMAX_BUFFER_MIN);
2467 : 2495 : maxvalues = Min(maxvalues, MINMAX_BUFFER_MAX);
2468 : :
2469 : 2495 : oldctx = MemoryContextSwitchTo(column->bv_context);
2470 : 2495 : ranges = minmax_multi_init(maxvalues);
2471 : 2495 : ranges->attno = attno;
2472 : 2495 : ranges->colloid = colloid;
2473 : 2495 : ranges->typid = attr->atttypid;
2474 : 2495 : ranges->target_maxvalues = target_maxvalues;
2475 : :
2476 : : /* we'll certainly need the comparator, so just look it up now */
2477 : 2495 : ranges->cmp = minmax_multi_get_strategy_procinfo(bdesc, attno, attr->atttypid,
2478 : : BTLessStrategyNumber);
2479 : :
2480 : 2495 : MemoryContextSwitchTo(oldctx);
2481 : :
2482 : 2495 : column->bv_allnulls = false;
2483 : 2495 : modified = true;
2484 : :
2485 : 2495 : column->bv_mem_value = PointerGetDatum(ranges);
2486 : 2495 : column->bv_serialize = brin_minmax_multi_serialize;
2487 : : }
2488 [ + + ]: 67882 : else if (!ranges)
2489 : : {
2490 : : MemoryContext oldctx;
2491 : :
2492 : : int maxvalues;
2493 [ + - - + : 7110 : BlockNumber pagesPerRange = BrinGetPagesPerRange(bdesc->bd_index);
+ + ]
2494 : :
2495 : 7110 : oldctx = MemoryContextSwitchTo(column->bv_context);
2496 : :
2497 : 7110 : serialized = (SerializedRanges *) PG_DETOAST_DATUM(column->bv_values[0]);
2498 : :
2499 : : /*
2500 : : * Determine the insert buffer size - we use 10x the target, capped to
2501 : : * the maximum number of values in the heap range. This is more than
2502 : : * enough, considering the actual number of rows per page is likely
2503 : : * much lower, but meh.
2504 : : */
2505 : 7110 : maxvalues = Min(serialized->maxvalues * MINMAX_BUFFER_FACTOR,
2506 : : MaxHeapTuplesPerPage * pagesPerRange);
2507 : :
2508 : : /* but always at least the original value */
2509 : 7110 : maxvalues = Max(maxvalues, serialized->maxvalues);
2510 : :
2511 : : /* always cap by MIN/MAX */
2512 : 7110 : maxvalues = Max(maxvalues, MINMAX_BUFFER_MIN);
2513 : 7110 : maxvalues = Min(maxvalues, MINMAX_BUFFER_MAX);
2514 : :
1525 peter@eisentraut.org 2515 : 7110 : ranges = brin_range_deserialize(maxvalues, serialized);
2516 : :
1815 tomas.vondra@postgre 2517 : 7110 : ranges->attno = attno;
2518 : 7110 : ranges->colloid = colloid;
2519 : 7110 : ranges->typid = attr->atttypid;
2520 : :
2521 : : /* we'll certainly need the comparator, so just look it up now */
2522 : 7110 : ranges->cmp = minmax_multi_get_strategy_procinfo(bdesc, attno, attr->atttypid,
2523 : : BTLessStrategyNumber);
2524 : :
2525 : 7110 : column->bv_mem_value = PointerGetDatum(ranges);
2526 : 7110 : column->bv_serialize = brin_minmax_multi_serialize;
2527 : :
2528 : 7110 : MemoryContextSwitchTo(oldctx);
2529 : : }
2530 : :
2531 : : /*
2532 : : * Try to add the new value to the range. We need to update the modified
2533 : : * flag, so that we serialize the updated summary later.
2534 : : */
2535 : 70377 : modified |= range_add_value(bdesc, colloid, attno, attr, ranges, newval);
2536 : :
2537 : :
2538 : 70377 : PG_RETURN_BOOL(modified);
2539 : : }
2540 : :
2541 : : /*
2542 : : * Given an index tuple corresponding to a certain page range and a scan key,
2543 : : * return whether the scan key is consistent with the index tuple's min/max
2544 : : * values. Return true if so, false otherwise.
2545 : : */
2546 : : Datum
2547 : 15693 : brin_minmax_multi_consistent(PG_FUNCTION_ARGS)
2548 : : {
2549 : 15693 : BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0);
2550 : 15693 : BrinValues *column = (BrinValues *) PG_GETARG_POINTER(1);
2551 : 15693 : ScanKey *keys = (ScanKey *) PG_GETARG_POINTER(2);
2552 : 15693 : int nkeys = PG_GETARG_INT32(3);
2553 : :
2554 : 15693 : Oid colloid = PG_GET_COLLATION(),
2555 : : subtype;
2556 : : AttrNumber attno;
2557 : : Datum value;
2558 : : FmgrInfo *finfo;
2559 : : SerializedRanges *serialized;
2560 : : Ranges *ranges;
2561 : : int keyno;
2562 : : int rangeno;
2563 : : int i;
2564 : :
2565 : 15693 : attno = column->bv_attno;
2566 : :
2567 : 15693 : serialized = (SerializedRanges *) PG_DETOAST_DATUM(column->bv_values[0]);
1525 peter@eisentraut.org 2568 : 15693 : ranges = brin_range_deserialize(serialized->maxvalues, serialized);
2569 : :
2570 : : /* inspect the ranges, and for each one evaluate the scan keys */
1815 tomas.vondra@postgre 2571 [ + + ]: 17004 : for (rangeno = 0; rangeno < ranges->nranges; rangeno++)
2572 : : {
2573 : 1656 : Datum minval = ranges->values[2 * rangeno];
2574 : 1656 : Datum maxval = ranges->values[2 * rangeno + 1];
2575 : :
2576 : : /* assume the range is matching, and we'll try to prove otherwise */
2577 : 1656 : bool matching = true;
2578 : :
2579 [ + + ]: 2001 : for (keyno = 0; keyno < nkeys; keyno++)
2580 : : {
2581 : : bool matches;
2582 : 1656 : ScanKey key = keys[keyno];
2583 : :
2584 : : /* NULL keys are handled and filtered-out in bringetbitmap */
2585 [ - + ]: 1656 : Assert(!(key->sk_flags & SK_ISNULL));
2586 : :
2587 : 1656 : attno = key->sk_attno;
2588 : 1656 : subtype = key->sk_subtype;
2589 : 1656 : value = key->sk_argument;
2590 [ + + + - ]: 1656 : switch (key->sk_strategy)
2591 : : {
2592 : 459 : case BTLessStrategyNumber:
2593 : : case BTLessEqualStrategyNumber:
2594 : 459 : finfo = minmax_multi_get_strategy_procinfo(bdesc, attno, subtype,
2595 : 459 : key->sk_strategy);
2596 : : /* first value from the array */
987 2597 : 459 : matches = DatumGetBool(FunctionCall2Coll(finfo, colloid, minval, value));
1815 2598 : 459 : break;
2599 : :
2600 : 495 : case BTEqualStrategyNumber:
2601 : : {
2602 : : Datum compar;
2603 : : FmgrInfo *cmpFn;
2604 : :
2605 : : /* by default this range does not match */
2606 : 495 : matches = false;
2607 : :
2608 : : /*
2609 : : * Otherwise, need to compare the new value with
2610 : : * boundaries of all the ranges. First check if it's
2611 : : * less than the absolute minimum, which is the first
2612 : : * value in the array.
2613 : : */
2614 : 495 : cmpFn = minmax_multi_get_strategy_procinfo(bdesc, attno, subtype,
2615 : : BTGreaterStrategyNumber);
1806 2616 : 495 : compar = FunctionCall2Coll(cmpFn, colloid, minval, value);
2617 : :
2618 : : /* smaller than the smallest value in this range */
1815 2619 [ + + ]: 495 : if (DatumGetBool(compar))
2620 : 60 : break;
2621 : :
2622 : 435 : cmpFn = minmax_multi_get_strategy_procinfo(bdesc, attno, subtype,
2623 : : BTLessStrategyNumber);
1806 2624 : 435 : compar = FunctionCall2Coll(cmpFn, colloid, maxval, value);
2625 : :
2626 : : /* larger than the largest value in this range */
1815 2627 [ + + ]: 435 : if (DatumGetBool(compar))
2628 : 411 : break;
2629 : :
2630 : : /*
2631 : : * We haven't managed to eliminate this range, so
2632 : : * consider it matching.
2633 : : */
2634 : 24 : matches = true;
2635 : :
2636 : 24 : break;
2637 : : }
2638 : 702 : case BTGreaterEqualStrategyNumber:
2639 : : case BTGreaterStrategyNumber:
2640 : 702 : finfo = minmax_multi_get_strategy_procinfo(bdesc, attno, subtype,
2641 : 702 : key->sk_strategy);
2642 : : /* last value from the array */
987 2643 : 702 : matches = DatumGetBool(FunctionCall2Coll(finfo, colloid, maxval, value));
1815 2644 : 702 : break;
2645 : :
1815 tomas.vondra@postgre 2646 :UBC 0 : default:
2647 : : /* shouldn't happen */
2648 [ # # ]: 0 : elog(ERROR, "invalid strategy number %d", key->sk_strategy);
2649 : : matches = false;
2650 : : break;
2651 : : }
2652 : :
2653 : : /* the range has to match all the scan keys */
987 tomas.vondra@postgre 2654 :CBC 1656 : matching &= matches;
2655 : :
2656 : : /* once we find a non-matching key, we're done */
1815 2657 [ + + ]: 1656 : if (!matching)
2658 : 1311 : break;
2659 : : }
2660 : :
2661 : : /*
2662 : : * have we found a range matching all scan keys? if yes, we're done
2663 : : */
2664 [ + + ]: 1656 : if (matching)
987 2665 : 345 : PG_RETURN_BOOL(true);
2666 : : }
2667 : :
2668 : : /*
2669 : : * And now inspect the values. We don't bother with doing a binary search
2670 : : * here, because we're dealing with serialized / fully compacted ranges,
2671 : : * so there should be only very few values.
2672 : : */
1815 2673 [ + + ]: 31144 : for (i = 0; i < ranges->nvalues; i++)
2674 : : {
2675 : 27691 : Datum val = ranges->values[2 * ranges->nranges + i];
2676 : :
2677 : : /* assume the range is matching, and we'll try to prove otherwise */
2678 : 27691 : bool matching = true;
2679 : :
2680 [ + + ]: 39586 : for (keyno = 0; keyno < nkeys; keyno++)
2681 : : {
2682 : : bool matches;
2683 : 27691 : ScanKey key = keys[keyno];
2684 : :
2685 : : /* we've already dealt with NULL keys at the beginning */
2686 [ - + ]: 27691 : if (key->sk_flags & SK_ISNULL)
1815 tomas.vondra@postgre 2687 :UBC 0 : continue;
2688 : :
1815 tomas.vondra@postgre 2689 :CBC 27691 : attno = key->sk_attno;
2690 : 27691 : subtype = key->sk_subtype;
2691 : 27691 : value = key->sk_argument;
2692 [ + - ]: 27691 : switch (key->sk_strategy)
2693 : : {
2694 : 27691 : case BTLessStrategyNumber:
2695 : : case BTLessEqualStrategyNumber:
2696 : : case BTEqualStrategyNumber:
2697 : : case BTGreaterEqualStrategyNumber:
2698 : : case BTGreaterStrategyNumber:
2699 : :
2700 : 27691 : finfo = minmax_multi_get_strategy_procinfo(bdesc, attno, subtype,
2701 : 27691 : key->sk_strategy);
987 2702 : 27691 : matches = DatumGetBool(FunctionCall2Coll(finfo, colloid, val, value));
1815 2703 : 27691 : break;
2704 : :
1815 tomas.vondra@postgre 2705 :UBC 0 : default:
2706 : : /* shouldn't happen */
2707 [ # # ]: 0 : elog(ERROR, "invalid strategy number %d", key->sk_strategy);
2708 : : matches = false;
2709 : : break;
2710 : : }
2711 : :
2712 : : /* the range has to match all the scan keys */
987 tomas.vondra@postgre 2713 :CBC 27691 : matching &= matches;
2714 : :
2715 : : /* once we find a non-matching key, we're done */
1815 2716 [ + + ]: 27691 : if (!matching)
2717 : 15796 : break;
2718 : : }
2719 : :
2720 : : /* have we found a range matching all scan keys? if yes, we're done */
2721 [ + + ]: 27691 : if (matching)
987 2722 : 11895 : PG_RETURN_BOOL(true);
2723 : : }
2724 : :
2725 : 3453 : PG_RETURN_BOOL(false);
2726 : : }
2727 : :
2728 : : /*
2729 : : * Given two BrinValues, update the first of them as a union of the summary
2730 : : * values contained in both. The second one is untouched.
2731 : : */
2732 : : Datum
1815 2733 : 17 : brin_minmax_multi_union(PG_FUNCTION_ARGS)
2734 : : {
2735 : 17 : BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0);
2736 : 17 : BrinValues *col_a = (BrinValues *) PG_GETARG_POINTER(1);
2737 : 17 : BrinValues *col_b = (BrinValues *) PG_GETARG_POINTER(2);
2738 : :
2739 : 17 : Oid colloid = PG_GET_COLLATION();
2740 : : SerializedRanges *serialized_a;
2741 : : SerializedRanges *serialized_b;
2742 : : Ranges *ranges_a;
2743 : : Ranges *ranges_b;
2744 : : AttrNumber attno;
2745 : : Form_pg_attribute attr;
2746 : : ExpandedRange *eranges;
2747 : : int neranges;
2748 : : FmgrInfo *cmpFn,
2749 : : *distanceFn;
2750 : : DistanceValue *distances;
2751 : : MemoryContext ctx;
2752 : : MemoryContext oldctx;
2753 : :
2754 [ - + ]: 17 : Assert(col_a->bv_attno == col_b->bv_attno);
2755 [ + - - + ]: 17 : Assert(!col_a->bv_allnulls && !col_b->bv_allnulls);
2756 : :
2757 : 17 : attno = col_a->bv_attno;
2758 : 17 : attr = TupleDescAttr(bdesc->bd_tupdesc, attno - 1);
2759 : :
2760 : 17 : serialized_a = (SerializedRanges *) PG_DETOAST_DATUM(col_a->bv_values[0]);
2761 : 17 : serialized_b = (SerializedRanges *) PG_DETOAST_DATUM(col_b->bv_values[0]);
2762 : :
1525 peter@eisentraut.org 2763 : 17 : ranges_a = brin_range_deserialize(serialized_a->maxvalues, serialized_a);
2764 : 17 : ranges_b = brin_range_deserialize(serialized_b->maxvalues, serialized_b);
2765 : :
2766 : : /* make sure neither of the ranges is NULL */
1815 tomas.vondra@postgre 2767 [ + - - + ]: 17 : Assert(ranges_a && ranges_b);
2768 : :
2769 : 17 : neranges = (ranges_a->nranges + ranges_a->nvalues) +
2770 : 17 : (ranges_b->nranges + ranges_b->nvalues);
2771 : :
2772 : : /*
2773 : : * The distanceFn calls (which may internally call e.g. numeric_le) may
2774 : : * allocate quite a bit of memory, and we must not leak it. Otherwise,
2775 : : * we'd have problems e.g. when building indexes. So we create a local
2776 : : * memory context and make sure we free the memory before leaving this
2777 : : * function (not after every call).
2778 : : */
2779 : 17 : ctx = AllocSetContextCreate(CurrentMemoryContext,
2780 : : "minmax-multi context",
2781 : : ALLOCSET_DEFAULT_SIZES);
2782 : :
2783 : 17 : oldctx = MemoryContextSwitchTo(ctx);
2784 : :
2785 : : /* allocate and fill */
2786 : 17 : eranges = (ExpandedRange *) palloc0(neranges * sizeof(ExpandedRange));
2787 : :
2788 : : /* fill the expanded ranges with entries for the first range */
2789 : 17 : fill_expanded_ranges(eranges, ranges_a->nranges + ranges_a->nvalues,
2790 : : ranges_a);
2791 : :
2792 : : /* and now add combine ranges for the second range */
2793 : 17 : fill_expanded_ranges(&eranges[ranges_a->nranges + ranges_a->nvalues],
2794 : 17 : ranges_b->nranges + ranges_b->nvalues,
2795 : : ranges_b);
2796 : :
2797 : 17 : cmpFn = minmax_multi_get_strategy_procinfo(bdesc, attno, attr->atttypid,
2798 : : BTLessStrategyNumber);
2799 : :
2800 : : /* sort the expanded ranges */
1806 2801 : 17 : neranges = sort_expanded_ranges(cmpFn, colloid, eranges, neranges);
2802 : :
2803 : : /*
2804 : : * We've loaded two different lists of expanded ranges, so some of them
2805 : : * may be overlapping. So walk through them and merge them.
2806 : : */
1815 2807 : 17 : neranges = merge_overlapping_ranges(cmpFn, colloid, eranges, neranges);
2808 : :
2809 : : /* check that the combine ranges are correct (no overlaps, ordering) */
2810 : 17 : AssertCheckExpandedRanges(bdesc, colloid, attno, attr, eranges, neranges);
2811 : :
2812 : : /*
2813 : : * If needed, reduce some of the ranges.
2814 : : *
2815 : : * XXX This may be fairly expensive, so maybe we should do it only when
2816 : : * it's actually needed (when we have too many ranges).
2817 : : */
2818 : :
2819 : : /* build array of gap distances and sort them in ascending order */
2820 : 17 : distanceFn = minmax_multi_get_procinfo(bdesc, attno, PROCNUM_DISTANCE);
2821 : 17 : distances = build_distances(distanceFn, colloid, eranges, neranges);
2822 : :
2823 : : /*
2824 : : * See how many values would be needed to store the current ranges, and if
2825 : : * needed combine as many of them to get below the threshold. The
2826 : : * collapsed ranges will be stored as a single value.
2827 : : *
2828 : : * XXX This does not apply the load factor, as we don't expect to add more
2829 : : * values to the range, so we prefer to keep as many ranges as possible.
2830 : : *
2831 : : * XXX Can the maxvalues be different in the two ranges? Perhaps we should
2832 : : * use maximum of those?
2833 : : */
2834 : 17 : neranges = reduce_expanded_ranges(eranges, neranges, distances,
2835 : : ranges_a->maxvalues,
2836 : : cmpFn, colloid);
2837 : :
2838 : : /* Is the result of reducing expanded ranges correct? */
987 2839 : 17 : AssertCheckExpandedRanges(bdesc, colloid, attno, attr, eranges, neranges);
2840 : :
2841 : : /* update the first range summary */
1815 2842 : 17 : store_expanded_ranges(ranges_a, eranges, neranges);
2843 : :
2844 : 17 : MemoryContextSwitchTo(oldctx);
2845 : 17 : MemoryContextDelete(ctx);
2846 : :
2847 : : /* cleanup and update the serialized value */
2848 : 17 : pfree(serialized_a);
1525 peter@eisentraut.org 2849 : 17 : col_a->bv_values[0] = PointerGetDatum(brin_range_serialize(ranges_a));
2850 : :
1815 tomas.vondra@postgre 2851 : 17 : PG_RETURN_VOID();
2852 : : }
2853 : :
2854 : : /*
2855 : : * Cache and return minmax multi opclass support procedure
2856 : : *
2857 : : * Return the procedure corresponding to the given function support number
2858 : : * or null if it does not exist.
2859 : : */
2860 : : static FmgrInfo *
2861 : 3207 : minmax_multi_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
2862 : : {
2863 : : MinmaxMultiOpaque *opaque;
2864 : 3207 : uint16 basenum = procnum - PROCNUM_BASE;
2865 : :
2866 : : /*
2867 : : * We cache these in the opaque struct, to avoid repetitive syscache
2868 : : * lookups.
2869 : : */
2870 : 3207 : opaque = (MinmaxMultiOpaque *) bdesc->bd_info[attno - 1]->oi_opaque;
2871 : :
2872 [ + + ]: 3207 : if (opaque->extra_procinfos[basenum].fn_oid == InvalidOid)
2873 : : {
2874 [ + - ]: 297 : if (RegProcedureIsValid(index_getprocid(bdesc->bd_index, attno,
2875 : : procnum)))
2876 : 297 : fmgr_info_copy(&opaque->extra_procinfos[basenum],
2877 : : index_getprocinfo(bdesc->bd_index, attno, procnum),
2878 : : bdesc->bd_context);
2879 : : else
369 alvherre@alvh.no-ip. 2880 [ # # ]:UBC 0 : ereport(ERROR,
2881 : : errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
2882 : : errmsg_internal("invalid opclass definition"),
2883 : : errdetail_internal("The operator class is missing support function %d for column %d.",
2884 : : procnum, attno));
2885 : : }
2886 : :
1815 tomas.vondra@postgre 2887 :CBC 3207 : return &opaque->extra_procinfos[basenum];
2888 : : }
2889 : :
2890 : : /*
2891 : : * Cache and return the procedure for the given strategy.
2892 : : *
2893 : : * Note: this function mirrors minmax_multi_get_strategy_procinfo; see notes
2894 : : * there. If changes are made here, see that function too.
2895 : : */
2896 : : static FmgrInfo *
2897 : 363248 : minmax_multi_get_strategy_procinfo(BrinDesc *bdesc, uint16 attno, Oid subtype,
2898 : : uint16 strategynum)
2899 : : {
2900 : : MinmaxMultiOpaque *opaque;
2901 : :
2902 [ + - - + ]: 363248 : Assert(strategynum >= 1 &&
2903 : : strategynum <= BTMaxStrategyNumber);
2904 : :
2905 : 363248 : opaque = (MinmaxMultiOpaque *) bdesc->bd_info[attno - 1]->oi_opaque;
2906 : :
2907 : : /*
2908 : : * We cache the procedures for the previous subtype in the opaque struct,
2909 : : * to avoid repetitive syscache lookups. If the subtype changed,
2910 : : * invalidate all the cached entries.
2911 : : */
2912 [ + + ]: 363248 : if (opaque->cached_subtype != subtype)
2913 : : {
2914 : : uint16 i;
2915 : :
2916 [ + + ]: 5904 : for (i = 1; i <= BTMaxStrategyNumber; i++)
2917 : 4920 : opaque->strategy_procinfos[i - 1].fn_oid = InvalidOid;
2918 : 984 : opaque->cached_subtype = subtype;
2919 : : }
2920 : :
2921 [ + + ]: 363248 : if (opaque->strategy_procinfos[strategynum - 1].fn_oid == InvalidOid)
2922 : : {
2923 : : Form_pg_attribute attr;
2924 : : HeapTuple tuple;
2925 : : Oid opfamily,
2926 : : oprid;
2927 : :
2928 : 1443 : opfamily = bdesc->bd_index->rd_opfamily[attno - 1];
2929 : 1443 : attr = TupleDescAttr(bdesc->bd_tupdesc, attno - 1);
2930 : 1443 : tuple = SearchSysCache4(AMOPSTRATEGY, ObjectIdGetDatum(opfamily),
2931 : : ObjectIdGetDatum(attr->atttypid),
2932 : : ObjectIdGetDatum(subtype),
2933 : : UInt16GetDatum(strategynum));
2934 [ - + ]: 1443 : if (!HeapTupleIsValid(tuple))
1815 tomas.vondra@postgre 2935 [ # # ]:UBC 0 : elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
2936 : : strategynum, attr->atttypid, subtype, opfamily);
2937 : :
1086 dgustafsson@postgres 2938 :CBC 1443 : oprid = DatumGetObjectId(SysCacheGetAttrNotNull(AMOPSTRATEGY, tuple,
2939 : : Anum_pg_amop_amopopr));
1815 tomas.vondra@postgre 2940 : 1443 : ReleaseSysCache(tuple);
1086 dgustafsson@postgres 2941 [ - + ]: 1443 : Assert(RegProcedureIsValid(oprid));
2942 : :
1815 tomas.vondra@postgre 2943 : 1443 : fmgr_info_cxt(get_opcode(oprid),
2944 : 1443 : &opaque->strategy_procinfos[strategynum - 1],
2945 : : bdesc->bd_context);
2946 : : }
2947 : :
2948 : 363248 : return &opaque->strategy_procinfos[strategynum - 1];
2949 : : }
2950 : :
2951 : : Datum
2952 : 732 : brin_minmax_multi_options(PG_FUNCTION_ARGS)
2953 : : {
2954 : 732 : local_relopts *relopts = (local_relopts *) PG_GETARG_POINTER(0);
2955 : :
2956 : 732 : init_local_reloptions(relopts, sizeof(MinMaxMultiOptions));
2957 : :
2958 : 732 : add_local_int_reloption(relopts, "values_per_range", "desc",
2959 : : MINMAX_MULTI_DEFAULT_VALUES_PER_PAGE, 8, 256,
2960 : : offsetof(MinMaxMultiOptions, valuesPerRange));
2961 : :
2962 : 732 : PG_RETURN_VOID();
2963 : : }
2964 : :
2965 : : /*
2966 : : * brin_minmax_multi_summary_in
2967 : : * - input routine for type brin_minmax_multi_summary.
2968 : : *
2969 : : * brin_minmax_multi_summary is only used internally to represent summaries
2970 : : * in BRIN minmax-multi indexes, so it has no operations of its own, and we
2971 : : * disallow input too.
2972 : : */
2973 : : Datum
1815 tomas.vondra@postgre 2974 :UBC 0 : brin_minmax_multi_summary_in(PG_FUNCTION_ARGS)
2975 : : {
2976 : : /*
2977 : : * brin_minmax_multi_summary stores the data in binary form and parsing
2978 : : * text input is not needed, so disallow this.
2979 : : */
2980 [ # # ]: 0 : ereport(ERROR,
2981 : : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2982 : : errmsg("cannot accept a value of type %s", "brin_minmax_multi_summary")));
2983 : :
2984 : : PG_RETURN_VOID(); /* keep compiler quiet */
2985 : : }
2986 : :
2987 : :
2988 : : /*
2989 : : * brin_minmax_multi_summary_out
2990 : : * - output routine for type brin_minmax_multi_summary.
2991 : : *
2992 : : * BRIN minmax-multi summaries are serialized into a bytea value, but we
2993 : : * want to output something nicer humans can understand.
2994 : : */
2995 : : Datum
1815 tomas.vondra@postgre 2996 :CBC 120 : brin_minmax_multi_summary_out(PG_FUNCTION_ARGS)
2997 : : {
2998 : : int i;
2999 : : int idx;
3000 : : SerializedRanges *ranges;
3001 : : Ranges *ranges_deserialized;
3002 : : StringInfoData str;
3003 : : bool isvarlena;
3004 : : Oid outfunc;
3005 : : FmgrInfo fmgrinfo;
3006 : 120 : ArrayBuildState *astate_values = NULL;
3007 : :
3008 : 120 : initStringInfo(&str);
3009 : 120 : appendStringInfoChar(&str, '{');
3010 : :
3011 : : /*
3012 : : * Detoast to get value with full 4B header (can't be stored in a toast
3013 : : * table, but can use 1B header).
3014 : : */
700 3015 : 120 : ranges = (SerializedRanges *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
3016 : :
3017 : : /* lookup output func for the type */
1815 3018 : 120 : getTypeOutputInfo(ranges->typid, &outfunc, &isvarlena);
3019 : 120 : fmgr_info(outfunc, &fmgrinfo);
3020 : :
3021 : : /* deserialize the range info easy-to-process pieces */
1525 peter@eisentraut.org 3022 : 120 : ranges_deserialized = brin_range_deserialize(ranges->maxvalues, ranges);
3023 : :
1656 3024 : 120 : appendStringInfo(&str, "nranges: %d nvalues: %d maxvalues: %d",
3025 : : ranges_deserialized->nranges,
3026 : : ranges_deserialized->nvalues,
3027 : : ranges_deserialized->maxvalues);
3028 : :
3029 : : /* serialize ranges */
1815 tomas.vondra@postgre 3030 : 120 : idx = 0;
3031 [ - + ]: 120 : for (i = 0; i < ranges_deserialized->nranges; i++)
3032 : : {
3033 : : char *a,
3034 : : *b;
3035 : : text *c;
3036 : : StringInfoData buf;
3037 : :
1257 drowley@postgresql.o 3038 :UBC 0 : initStringInfo(&buf);
3039 : :
1745 3040 : 0 : a = OutputFunctionCall(&fmgrinfo, ranges_deserialized->values[idx++]);
3041 : 0 : b = OutputFunctionCall(&fmgrinfo, ranges_deserialized->values[idx++]);
3042 : :
1257 3043 : 0 : appendStringInfo(&buf, "%s ... %s", a, b);
3044 : :
3045 : 0 : c = cstring_to_text_with_len(buf.data, buf.len);
3046 : :
1815 tomas.vondra@postgre 3047 : 0 : astate_values = accumArrayResult(astate_values,
3048 : : PointerGetDatum(c),
3049 : : false,
3050 : : TEXTOID,
3051 : : CurrentMemoryContext);
3052 : : }
3053 : :
1815 tomas.vondra@postgre 3054 [ - + ]:CBC 120 : if (ranges_deserialized->nranges > 0)
3055 : : {
3056 : : Oid typoutput;
3057 : : bool typIsVarlena;
3058 : : Datum val;
3059 : : char *extval;
3060 : :
1815 tomas.vondra@postgre 3061 :UBC 0 : getTypeOutputInfo(ANYARRAYOID, &typoutput, &typIsVarlena);
3062 : :
1295 peter@eisentraut.org 3063 : 0 : val = makeArrayResult(astate_values, CurrentMemoryContext);
3064 : :
1815 tomas.vondra@postgre 3065 : 0 : extval = OidOutputFunctionCall(typoutput, val);
3066 : :
3067 : 0 : appendStringInfo(&str, " ranges: %s", extval);
3068 : : }
3069 : :
3070 : : /* serialize individual values */
1815 tomas.vondra@postgre 3071 :CBC 120 : astate_values = NULL;
3072 : :
3073 [ + + ]: 1296 : for (i = 0; i < ranges_deserialized->nvalues; i++)
3074 : : {
3075 : : Datum a;
3076 : : text *b;
3077 : :
3078 : 1176 : a = FunctionCall1(&fmgrinfo, ranges_deserialized->values[idx++]);
1286 drowley@postgresql.o 3079 : 1176 : b = cstring_to_text(DatumGetCString(a));
3080 : :
1815 tomas.vondra@postgre 3081 : 1176 : astate_values = accumArrayResult(astate_values,
3082 : : PointerGetDatum(b),
3083 : : false,
3084 : : TEXTOID,
3085 : : CurrentMemoryContext);
3086 : : }
3087 : :
3088 [ + - ]: 120 : if (ranges_deserialized->nvalues > 0)
3089 : : {
3090 : : Oid typoutput;
3091 : : bool typIsVarlena;
3092 : : Datum val;
3093 : : char *extval;
3094 : :
3095 : 120 : getTypeOutputInfo(ANYARRAYOID, &typoutput, &typIsVarlena);
3096 : :
1295 peter@eisentraut.org 3097 : 120 : val = makeArrayResult(astate_values, CurrentMemoryContext);
3098 : :
1815 tomas.vondra@postgre 3099 : 120 : extval = OidOutputFunctionCall(typoutput, val);
3100 : :
3101 : 120 : appendStringInfo(&str, " values: %s", extval);
3102 : : }
3103 : :
3104 : :
3105 : 120 : appendStringInfoChar(&str, '}');
3106 : :
3107 : 120 : PG_RETURN_CSTRING(str.data);
3108 : : }
3109 : :
3110 : : /*
3111 : : * brin_minmax_multi_summary_recv
3112 : : * - binary input routine for type brin_minmax_multi_summary.
3113 : : */
3114 : : Datum
1815 tomas.vondra@postgre 3115 :UBC 0 : brin_minmax_multi_summary_recv(PG_FUNCTION_ARGS)
3116 : : {
3117 [ # # ]: 0 : ereport(ERROR,
3118 : : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
3119 : : errmsg("cannot accept a value of type %s", "brin_minmax_multi_summary")));
3120 : :
3121 : : PG_RETURN_VOID(); /* keep compiler quiet */
3122 : : }
3123 : :
3124 : : /*
3125 : : * brin_minmax_multi_summary_send
3126 : : * - binary output routine for type brin_minmax_multi_summary.
3127 : : *
3128 : : * BRIN minmax-multi summaries are serialized in a bytea value (although
3129 : : * the type is named differently), so let's just send that.
3130 : : */
3131 : : Datum
3132 : 0 : brin_minmax_multi_summary_send(PG_FUNCTION_ARGS)
3133 : : {
3134 : 0 : return byteasend(fcinfo);
3135 : : }
|
