-
Notifications
You must be signed in to change notification settings - Fork 4.4k
/
brin_minmax_multi.c
3170 lines (2612 loc) · 86.8 KB
/
brin_minmax_multi.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* brin_minmax_multi.c
* Implementation of Multi Min/Max opclass for BRIN
*
* Portions Copyright (c) 1996-2021, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
*
* Implements a variant of minmax opclass, where the summary is composed of
* multiple smaller intervals. This allows us to handle outliers, which
* usually make the simple minmax opclass inefficient.
*
* Consider for example page range with simple minmax interval [1000,2000],
* and assume a new row gets inserted into the range with value 1000000.
* Due to that the interval gets [1000,1000000]. I.e. the minmax interval
* got 1000x wider and won't be useful to eliminate scan keys between 2001
* and 1000000.
*
* With minmax-multi opclass, we may have [1000,2000] interval initially,
* but after adding the new row we start tracking it as two interval:
*
* [1000,2000] and [1000000,1000000]
*
* This allows us to still eliminate the page range when the scan keys hit
* the gap between 2000 and 1000000, making it useful in cases when the
* simple minmax opclass gets inefficient.
*
* The number of intervals tracked per page range is somewhat flexible.
* What is restricted is the number of values per page range, and the limit
* is currently 32 (see values_per_range reloption). Collapsed intervals
* (with equal minimum and maximum value) are stored as a single value,
* while regular intervals require two values.
*
* When the number of values gets too high (by adding new values to the
* summary), we merge some of the intervals to free space for more values.
* This is done in a greedy way - we simply pick the two closest intervals,
* merge them, and repeat this until the number of values to store gets
* sufficiently low (below 50% of maximum values), but that is mostly
* arbitrary threshold and may be changed easily).
*
* To pick the closest intervals we use the "distance" support procedure,
* which measures space between two ranges (i.e. the length of an interval).
* The computed value may be an approximation - in the worst case we will
* merge two ranges that are slightly less optimal at that step, but the
* index should still produce correct results.
*
* The compactions (reducing the number of values) is fairly expensive, as
* it requires calling the distance functions, sorting etc. So when building
* the summary, we use a significantly larger buffer, and only enforce the
* exact limit at the very end. This improves performance, and it also helps
* with building better ranges (due to the greedy approach).
*
*
* IDENTIFICATION
* src/backend/access/brin/brin_minmax_multi.c
*/
#include "postgres.h"
/* needed for PGSQL_AF_INET */
#include <sys/socket.h>
#include "access/genam.h"
#include "access/brin.h"
#include "access/brin_internal.h"
#include "access/brin_tuple.h"
#include "access/reloptions.h"
#include "access/stratnum.h"
#include "access/htup_details.h"
#include "catalog/pg_type.h"
#include "catalog/pg_am.h"
#include "catalog/pg_amop.h"
#include "utils/array.h"
#include "utils/builtins.h"
#include "utils/date.h"
#include "utils/datum.h"
#include "utils/float.h"
#include "utils/inet.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/numeric.h"
#include "utils/pg_lsn.h"
#include "utils/rel.h"
#include "utils/syscache.h"
#include "utils/timestamp.h"
#include "utils/uuid.h"
/*
* Additional SQL level support functions
*
* Procedure numbers must not use values reserved for BRIN itself; see
* brin_internal.h.
*/
#define MINMAX_MAX_PROCNUMS 1 /* maximum support procs we need */
#define PROCNUM_DISTANCE 11 /* required, distance between values */
/*
* Subtract this from procnum to obtain index in MinmaxMultiOpaque arrays
* (Must be equal to minimum of private procnums).
*/
#define PROCNUM_BASE 11
/*
* Sizing the insert buffer - we use 10x the number of values specified
* in the reloption, but we cap it to 8192 not to get too large. When
* the buffer gets full, we reduce the number of values by half.
*/
#define MINMAX_BUFFER_FACTOR 10
#define MINMAX_BUFFER_MIN 256
#define MINMAX_BUFFER_MAX 8192
#define MINMAX_BUFFER_LOAD_FACTOR 0.5
typedef struct MinmaxMultiOpaque
{
FmgrInfo extra_procinfos[MINMAX_MAX_PROCNUMS];
bool extra_proc_missing[MINMAX_MAX_PROCNUMS];
Oid cached_subtype;
FmgrInfo strategy_procinfos[BTMaxStrategyNumber];
} MinmaxMultiOpaque;
/*
* Storage type for BRIN's minmax reloptions
*/
typedef struct MinMaxMultiOptions
{
int32 vl_len_; /* varlena header (do not touch directly!) */
int valuesPerRange; /* number of values per range */
} MinMaxMultiOptions;
#define MINMAX_MULTI_DEFAULT_VALUES_PER_PAGE 32
#define MinMaxMultiGetValuesPerRange(opts) \
((opts) && (((MinMaxMultiOptions *) (opts))->valuesPerRange != 0) ? \
((MinMaxMultiOptions *) (opts))->valuesPerRange : \
MINMAX_MULTI_DEFAULT_VALUES_PER_PAGE)
#define SAMESIGN(a,b) (((a) < 0) == ((b) < 0))
/*
* The summary of minmax-multi indexes has two representations - Ranges for
* convenient processing, and SerializedRanges for storage in bytea value.
*
* The Ranges struct stores the boundary values in a single array, but we
* treat regular and single-point ranges differently to save space. For
* regular ranges (with different boundary values) we have to store both
* the lower and upper bound of the range, while for "single-point ranges"
* we only need to store a single value.
*
* The 'values' array stores boundary values for regular ranges first (there
* are 2*nranges values to store), and then the nvalues boundary values for
* single-point ranges. That is, we have (2*nranges + nvalues) boundary
* values in the array.
*
* +-------------------------+----------------------------------+
* | ranges (2 * nranges of) | single point values (nvalues of) |
* +-------------------------+----------------------------------+
*
* This allows us to quickly add new values, and store outliers without
* having to widen any of the existing range values.
*
* 'nsorted' denotes how many of 'nvalues' in the values[] array are sorted.
* When nsorted == nvalues, all single point values are sorted.
*
* We never store more than maxvalues values (as set by values_per_range
* reloption). If needed we merge some of the ranges.
*
* To minimize palloc overhead, we always allocate the full array with
* space for maxvalues elements. This should be fine as long as the
* maxvalues is reasonably small (64 seems fine), which is the case
* thanks to values_per_range reloption being limited to 256.
*/
typedef struct Ranges
{
/* Cache information that we need quite often. */
Oid typid;
Oid colloid;
AttrNumber attno;
FmgrInfo *cmp;
/* (2*nranges + nvalues) <= maxvalues */
int nranges; /* number of ranges in the values[] array */
int nsorted; /* number of nvalues which are sorted */
int nvalues; /* number of point values in values[] array */
int maxvalues; /* number of elements in the values[] array */
/*
* We simply add the values into a large buffer, without any expensive
* steps (sorting, deduplication, ...). The buffer is a multiple of the
* target number of values, so the compaction happens less often,
* amortizing the costs. We keep the actual target and compact to the
* requested number of values at the very end, before serializing to
* on-disk representation.
*/
/* requested number of values */
int target_maxvalues;
/* values stored for this range - either raw values, or ranges */
Datum values[FLEXIBLE_ARRAY_MEMBER];
} Ranges;
/*
* On-disk the summary is stored as a bytea value, with a simple header
* with basic metadata, followed by the boundary values. It has a varlena
* header, so can be treated as varlena directly.
*
* See range_serialize/range_deserialize for serialization details.
*/
typedef struct SerializedRanges
{
/* varlena header (do not touch directly!) */
int32 vl_len_;
/* type of values stored in the data array */
Oid typid;
/* (2*nranges + nvalues) <= maxvalues */
int nranges; /* number of ranges in the array (stored) */
int nvalues; /* number of values in the data array (all) */
int maxvalues; /* maximum number of values (reloption) */
/* contains the actual data */
char data[FLEXIBLE_ARRAY_MEMBER];
} SerializedRanges;
static SerializedRanges *range_serialize(Ranges *range);
static Ranges *range_deserialize(int maxvalues, SerializedRanges *range);
/*
* Used to represent ranges expanded to make merging and combining easier.
*
* Each expanded range is essentially an interval, represented by min/max
* values, along with a flag whether it's a collapsed range (in which case
* the min and max values are equal). We have the flag to handle by-ref
* data types - we can't simply compare the datums, and this saves some
* calls to the type-specific comparator function.
*/
typedef struct ExpandedRange
{
Datum minval; /* lower boundary */
Datum maxval; /* upper boundary */
bool collapsed; /* true if minval==maxval */
} ExpandedRange;
/*
* Represents a distance between two ranges (identified by index into
* an array of extended ranges).
*/
typedef struct DistanceValue
{
int index;
double value;
} DistanceValue;
/* Cache for support and strategy procedures. */
static FmgrInfo *minmax_multi_get_procinfo(BrinDesc *bdesc, uint16 attno,
uint16 procnum);
static FmgrInfo *minmax_multi_get_strategy_procinfo(BrinDesc *bdesc,
uint16 attno, Oid subtype,
uint16 strategynum);
typedef struct compare_context
{
FmgrInfo *cmpFn;
Oid colloid;
} compare_context;
static int compare_values(const void *a, const void *b, void *arg);
#ifdef USE_ASSERT_CHECKING
/*
* Check that the order of the array values is correct, using the cmp
* function (which should be BTLessStrategyNumber).
*/
static void
AssertArrayOrder(FmgrInfo *cmp, Oid colloid, Datum *values, int nvalues)
{
int i;
Datum lt;
for (i = 0; i < (nvalues - 1); i++)
{
lt = FunctionCall2Coll(cmp, colloid, values[i], values[i + 1]);
Assert(DatumGetBool(lt));
}
}
#endif
/*
* Comprehensive check of the Ranges structure.
*/
static void
AssertCheckRanges(Ranges *ranges, FmgrInfo *cmpFn, Oid colloid)
{
#ifdef USE_ASSERT_CHECKING
int i;
/* some basic sanity checks */
Assert(ranges->nranges >= 0);
Assert(ranges->nsorted >= 0);
Assert(ranges->nvalues >= ranges->nsorted);
Assert(ranges->maxvalues >= 2 * ranges->nranges + ranges->nvalues);
Assert(ranges->typid != InvalidOid);
/*
* First the ranges - there are 2*nranges boundary values, and the values
* have to be strictly ordered (equal values would mean the range is
* collapsed, and should be stored as a point). This also guarantees that
* the ranges do not overlap.
*/
AssertArrayOrder(cmpFn, colloid, ranges->values, 2 * ranges->nranges);
/* then the single-point ranges (with nvalues boundar values ) */
AssertArrayOrder(cmpFn, colloid, &ranges->values[2 * ranges->nranges],
ranges->nsorted);
/*
* Check that none of the values are not covered by ranges (both sorted
* and unsorted)
*/
if (ranges->nranges > 0)
{
for (i = 0; i < ranges->nvalues; i++)
{
Datum compar;
int start,
end;
Datum minvalue = ranges->values[0];
Datum maxvalue = ranges->values[2 * ranges->nranges - 1];
Datum value = ranges->values[2 * ranges->nranges + i];
compar = FunctionCall2Coll(cmpFn, colloid, value, minvalue);
/*
* If the value is smaller than the lower bound in the first range
* then it cannot possibly be in any of the ranges.
*/
if (DatumGetBool(compar))
continue;
compar = FunctionCall2Coll(cmpFn, colloid, maxvalue, value);
/*
* Likewise, if the value is larger than the upper bound of the
* final range, then it cannot possibly be inside any of the
* ranges.
*/
if (DatumGetBool(compar))
continue;
/* bsearch the ranges to see if 'value' fits within any of them */
start = 0; /* first range */
end = ranges->nranges - 1; /* last range */
while (true)
{
int midpoint = (start + end) / 2;
/* this means we ran out of ranges in the last step */
if (start > end)
break;
/* copy the min/max values from the ranges */
minvalue = ranges->values[2 * midpoint];
maxvalue = ranges->values[2 * midpoint + 1];
/*
* Is the value smaller than the minval? If yes, we'll recurse
* to the left side of range array.
*/
compar = FunctionCall2Coll(cmpFn, colloid, value, minvalue);
/* smaller than the smallest value in this range */
if (DatumGetBool(compar))
{
end = (midpoint - 1);
continue;
}
/*
* Is the value greater than the minval? If yes, we'll recurse
* to the right side of range array.
*/
compar = FunctionCall2Coll(cmpFn, colloid, maxvalue, value);
/* larger than the largest value in this range */
if (DatumGetBool(compar))
{
start = (midpoint + 1);
continue;
}
/* hey, we found a matching range */
Assert(false);
}
}
}
/* and values in the unsorted part must not be in the sorted part */
if (ranges->nsorted > 0)
{
compare_context cxt;
cxt.colloid = ranges->colloid;
cxt.cmpFn = ranges->cmp;
for (i = ranges->nsorted; i < ranges->nvalues; i++)
{
Datum value = ranges->values[2 * ranges->nranges + i];
Assert(bsearch_arg(&value, &ranges->values[2 * ranges->nranges],
ranges->nsorted, sizeof(Datum),
compare_values, (void *) &cxt) == NULL);
}
}
#endif
}
/*
* Check that the expanded ranges (built when reducing the number of ranges
* by combining some of them) are correctly sorted and do not overlap.
*/
static void
AssertCheckExpandedRanges(BrinDesc *bdesc, Oid colloid, AttrNumber attno,
Form_pg_attribute attr, ExpandedRange *ranges,
int nranges)
{
#ifdef USE_ASSERT_CHECKING
int i;
FmgrInfo *eq;
FmgrInfo *lt;
eq = minmax_multi_get_strategy_procinfo(bdesc, attno, attr->atttypid,
BTEqualStrategyNumber);
lt = minmax_multi_get_strategy_procinfo(bdesc, attno, attr->atttypid,
BTLessStrategyNumber);
/*
* Each range independently should be valid, i.e. that for the boundary
* values (lower <= upper).
*/
for (i = 0; i < nranges; i++)
{
Datum r;
Datum minval = ranges[i].minval;
Datum maxval = ranges[i].maxval;
if (ranges[i].collapsed) /* collapsed: minval == maxval */
r = FunctionCall2Coll(eq, colloid, minval, maxval);
else /* non-collapsed: minval < maxval */
r = FunctionCall2Coll(lt, colloid, minval, maxval);
Assert(DatumGetBool(r));
}
/*
* And the ranges should be ordered and must not overlap, i.e. upper <
* lower for boundaries of consecutive ranges.
*/
for (i = 0; i < nranges - 1; i++)
{
Datum r;
Datum maxval = ranges[i].maxval;
Datum minval = ranges[i + 1].minval;
r = FunctionCall2Coll(lt, colloid, maxval, minval);
Assert(DatumGetBool(r));
}
#endif
}
/*
* minmax_multi_init
* Initialize the deserialized range list, allocate all the memory.
*
* This is only in-memory representation of the ranges, so we allocate
* enough space for the maximum number of values (so as not to have to do
* repallocs as the ranges grow).
*/
static Ranges *
minmax_multi_init(int maxvalues)
{
Size len;
Ranges *ranges;
Assert(maxvalues > 0);
len = offsetof(Ranges, values); /* fixed header */
len += maxvalues * sizeof(Datum); /* Datum values */
ranges = (Ranges *) palloc0(len);
ranges->maxvalues = maxvalues;
return ranges;
}
/*
* range_deduplicate_values
* Deduplicate the part with values in the simple points.
*
* This is meant to be a cheaper way of reducing the size of the ranges. It
* does not touch the ranges, and only sorts the other values - it does not
* call the distance functions, which may be quite expensive, etc.
*
* We do know the values are not duplicate with the ranges, because we check
* that before adding a new value. Same for the sorted part of values.
*/
static void
range_deduplicate_values(Ranges *range)
{
int i,
n;
int start;
compare_context cxt;
/*
* If there are no unsorted values, we're done (this probably can't
* happen, as we're adding values to unsorted part).
*/
if (range->nsorted == range->nvalues)
return;
/* sort the values */
cxt.colloid = range->colloid;
cxt.cmpFn = range->cmp;
/* the values start right after the ranges (which are always sorted) */
start = 2 * range->nranges;
/*
* XXX This might do a merge sort, to leverage that the first part of the
* array is already sorted. If the sorted part is large, it might be quite
* a bit faster.
*/
qsort_arg(&range->values[start],
range->nvalues, sizeof(Datum),
compare_values, (void *) &cxt);
n = 1;
for (i = 1; i < range->nvalues; i++)
{
/* same as preceding value, so store it */
if (compare_values(&range->values[start + i - 1],
&range->values[start + i],
(void *) &cxt) == 0)
continue;
range->values[start + n] = range->values[start + i];
n++;
}
/* now all the values are sorted */
range->nvalues = n;
range->nsorted = n;
AssertCheckRanges(range, range->cmp, range->colloid);
}
/*
* range_serialize
* Serialize the in-memory representation into a compact varlena value.
*
* Simply copy the header and then also the individual values, as stored
* in the in-memory value array.
*/
static SerializedRanges *
range_serialize(Ranges *range)
{
Size len;
int nvalues;
SerializedRanges *serialized;
Oid typid;
int typlen;
bool typbyval;
int i;
char *ptr;
/* simple sanity checks */
Assert(range->nranges >= 0);
Assert(range->nsorted >= 0);
Assert(range->nvalues >= 0);
Assert(range->maxvalues > 0);
Assert(range->target_maxvalues > 0);
/* at this point the range should be compacted to the target size */
Assert(2 * range->nranges + range->nvalues <= range->target_maxvalues);
Assert(range->target_maxvalues <= range->maxvalues);
/* range boundaries are always sorted */
Assert(range->nvalues >= range->nsorted);
/* deduplicate values, if there's unsorted part */
range_deduplicate_values(range);
/* see how many Datum values we actually have */
nvalues = 2 * range->nranges + range->nvalues;
typid = range->typid;
typbyval = get_typbyval(typid);
typlen = get_typlen(typid);
/* header is always needed */
len = offsetof(SerializedRanges, data);
/*
* The space needed depends on data type - for fixed-length data types
* (by-value and some by-reference) it's pretty simple, just multiply
* (attlen * nvalues) and we're done. For variable-length by-reference
* types we need to actually walk all the values and sum the lengths.
*/
if (typlen == -1) /* varlena */
{
int i;
for (i = 0; i < nvalues; i++)
{
len += VARSIZE_ANY(range->values[i]);
}
}
else if (typlen == -2) /* cstring */
{
int i;
for (i = 0; i < nvalues; i++)
{
/* don't forget to include the null terminator ;-) */
len += strlen(DatumGetCString(range->values[i])) + 1;
}
}
else /* fixed-length types (even by-reference) */
{
Assert(typlen > 0);
len += nvalues * typlen;
}
/*
* Allocate the serialized object, copy the basic information. The
* serialized object is a varlena, so update the header.
*/
serialized = (SerializedRanges *) palloc0(len);
SET_VARSIZE(serialized, len);
serialized->typid = typid;
serialized->nranges = range->nranges;
serialized->nvalues = range->nvalues;
serialized->maxvalues = range->target_maxvalues;
/*
* And now copy also the boundary values (like the length calculation this
* depends on the particular data type).
*/
ptr = serialized->data; /* start of the serialized data */
for (i = 0; i < nvalues; i++)
{
if (typbyval) /* simple by-value data types */
{
Datum tmp;
/*
* For byval types, we need to copy just the significant bytes -
* we can't use memcpy directly, as that assumes little-endian
* behavior. store_att_byval does almost what we need, but it
* requires a properly aligned buffer - the output buffer does not
* guarantee that. So we simply use a local Datum variable (which
* guarantees proper alignment), and then copy the value from it.
*/
store_att_byval(&tmp, range->values[i], typlen);
memcpy(ptr, &tmp, typlen);
ptr += typlen;
}
else if (typlen > 0) /* fixed-length by-ref types */
{
memcpy(ptr, DatumGetPointer(range->values[i]), typlen);
ptr += typlen;
}
else if (typlen == -1) /* varlena */
{
int tmp = VARSIZE_ANY(DatumGetPointer(range->values[i]));
memcpy(ptr, DatumGetPointer(range->values[i]), tmp);
ptr += tmp;
}
else if (typlen == -2) /* cstring */
{
int tmp = strlen(DatumGetCString(range->values[i])) + 1;
memcpy(ptr, DatumGetCString(range->values[i]), tmp);
ptr += tmp;
}
/* make sure we haven't overflown the buffer end */
Assert(ptr <= ((char *) serialized + len));
}
/* exact size */
Assert(ptr == ((char *) serialized + len));
return serialized;
}
/*
* range_deserialize
* Serialize the in-memory representation into a compact varlena value.
*
* Simply copy the header and then also the individual values, as stored
* in the in-memory value array.
*/
static Ranges *
range_deserialize(int maxvalues, SerializedRanges *serialized)
{
int i,
nvalues;
char *ptr,
*dataptr;
bool typbyval;
int typlen;
Size datalen;
Ranges *range;
Assert(serialized->nranges >= 0);
Assert(serialized->nvalues >= 0);
Assert(serialized->maxvalues > 0);
nvalues = 2 * serialized->nranges + serialized->nvalues;
Assert(nvalues <= serialized->maxvalues);
Assert(serialized->maxvalues <= maxvalues);
range = minmax_multi_init(maxvalues);
/* copy the header info */
range->nranges = serialized->nranges;
range->nvalues = serialized->nvalues;
range->nsorted = serialized->nvalues;
range->maxvalues = maxvalues;
range->target_maxvalues = serialized->maxvalues;
range->typid = serialized->typid;
typbyval = get_typbyval(serialized->typid);
typlen = get_typlen(serialized->typid);
/*
* And now deconstruct the values into Datum array. We have to copy the
* data because the serialized representation ignores alignment, and we
* don't want to rely on it being kept around anyway.
*/
ptr = serialized->data;
/*
* We don't want to allocate many pieces, so we just allocate everything
* in one chunk. How much space will we need?
*
* XXX We don't need to copy simple by-value data types.
*/
datalen = 0;
dataptr = NULL;
for (i = 0; (i < nvalues) && (!typbyval); i++)
{
if (typlen > 0) /* fixed-length by-ref types */
datalen += MAXALIGN(typlen);
else if (typlen == -1) /* varlena */
{
datalen += MAXALIGN(VARSIZE_ANY(DatumGetPointer(ptr)));
ptr += VARSIZE_ANY(DatumGetPointer(ptr));
}
else if (typlen == -2) /* cstring */
{
Size slen = strlen(DatumGetCString(ptr)) + 1;
datalen += MAXALIGN(slen);
ptr += slen;
}
}
if (datalen > 0)
dataptr = palloc(datalen);
/*
* Restore the source pointer (might have been modified when calculating
* the space we need to allocate).
*/
ptr = serialized->data;
for (i = 0; i < nvalues; i++)
{
if (typbyval) /* simple by-value data types */
{
Datum v = 0;
memcpy(&v, ptr, typlen);
range->values[i] = fetch_att(&v, true, typlen);
ptr += typlen;
}
else if (typlen > 0) /* fixed-length by-ref types */
{
range->values[i] = PointerGetDatum(dataptr);
memcpy(dataptr, ptr, typlen);
dataptr += MAXALIGN(typlen);
ptr += typlen;
}
else if (typlen == -1) /* varlena */
{
range->values[i] = PointerGetDatum(dataptr);
memcpy(dataptr, ptr, VARSIZE_ANY(ptr));
dataptr += MAXALIGN(VARSIZE_ANY(ptr));
ptr += VARSIZE_ANY(ptr);
}
else if (typlen == -2) /* cstring */
{
Size slen = strlen(ptr) + 1;
range->values[i] = PointerGetDatum(dataptr);
memcpy(dataptr, ptr, slen);
dataptr += MAXALIGN(slen);
ptr += slen;
}
/* make sure we haven't overflown the buffer end */
Assert(ptr <= ((char *) serialized + VARSIZE_ANY(serialized)));
}
/* should have consumed the whole input value exactly */
Assert(ptr == ((char *) serialized + VARSIZE_ANY(serialized)));
/* return the deserialized value */
return range;
}
/*
* compare_expanded_ranges
* Compare the expanded ranges - first by minimum, then by maximum.
*
* We do guarantee that ranges in a single Ranges object do not overlap, so it
* may seem strange that we don't order just by minimum. But when merging two
* Ranges (which happens in the union function), the ranges may in fact
* overlap. So we do compare both.
*/
static int
compare_expanded_ranges(const void *a, const void *b, void *arg)
{
ExpandedRange *ra = (ExpandedRange *) a;
ExpandedRange *rb = (ExpandedRange *) b;
Datum r;
compare_context *cxt = (compare_context *) arg;
/* first compare minvals */
r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, ra->minval, rb->minval);
if (DatumGetBool(r))
return -1;
r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, rb->minval, ra->minval);
if (DatumGetBool(r))
return 1;
/* then compare maxvals */
r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, ra->maxval, rb->maxval);
if (DatumGetBool(r))
return -1;
r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, rb->maxval, ra->maxval);
if (DatumGetBool(r))
return 1;
return 0;
}
/*
* compare_values
* Compare the values.
*/
static int
compare_values(const void *a, const void *b, void *arg)
{
Datum *da = (Datum *) a;
Datum *db = (Datum *) b;
Datum r;
compare_context *cxt = (compare_context *) arg;
r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *da, *db);
if (DatumGetBool(r))
return -1;
r = FunctionCall2Coll(cxt->cmpFn, cxt->colloid, *db, *da);
if (DatumGetBool(r))
return 1;
return 0;
}
/*
* Check if the new value matches one of the existing ranges.
*/
static bool
has_matching_range(BrinDesc *bdesc, Oid colloid, Ranges *ranges,
Datum newval, AttrNumber attno, Oid typid)
{
Datum compar;
Datum minvalue;
Datum maxvalue;
FmgrInfo *cmpLessFn;
FmgrInfo *cmpGreaterFn;
/* binary search on ranges */
int start,
end;
if (ranges->nranges == 0)
return false;
minvalue = ranges->values[0];
maxvalue = ranges->values[2 * ranges->nranges - 1];
/*
* Otherwise, need to compare the new value with boundaries of all the
* ranges. First check if it's less than the absolute minimum, which is
* the first value in the array.
*/
cmpLessFn = minmax_multi_get_strategy_procinfo(bdesc, attno, typid,
BTLessStrategyNumber);
compar = FunctionCall2Coll(cmpLessFn, colloid, newval, minvalue);
/* smaller than the smallest value in the range list */
if (DatumGetBool(compar))
return false;
/*
* And now compare it to the existing maximum (last value in the data
* array). But only if we haven't already ruled out a possible match in
* the minvalue check.
*/
cmpGreaterFn = minmax_multi_get_strategy_procinfo(bdesc, attno, typid,
BTGreaterStrategyNumber);
compar = FunctionCall2Coll(cmpGreaterFn, colloid, newval, maxvalue);
if (DatumGetBool(compar))
return false;
/*
* So we know it's in the general min/max, the question is whether it
* falls in one of the ranges or gaps. We'll do a binary search on
* individual ranges - for each range we check equality (value falls into
* the range), and then check ranges either above or below the current
* range.
*/
start = 0; /* first range */
end = (ranges->nranges - 1); /* last range */
while (true)
{
int midpoint = (start + end) / 2;
/* this means we ran out of ranges in the last step */
if (start > end)
return false;
/* copy the min/max values from the ranges */
minvalue = ranges->values[2 * midpoint];
maxvalue = ranges->values[2 * midpoint + 1];
/*
* Is the value smaller than the minval? If yes, we'll recurse to the
* left side of range array.
*/
compar = FunctionCall2Coll(cmpLessFn, colloid, newval, minvalue);
/* smaller than the smallest value in this range */
if (DatumGetBool(compar))
{
end = (midpoint - 1);
continue;