PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
brin_bloom.c
Go to the documentation of this file.
1/*
2 * brin_bloom.c
3 * Implementation of Bloom opclass for BRIN
4 *
5 * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
6 * Portions Copyright (c) 1994, Regents of the University of California
7 *
8 *
9 * A BRIN opclass summarizing page range into a bloom filter.
10 *
11 * Bloom filters allow efficient testing whether a given page range contains
12 * a particular value. Therefore, if we summarize each page range into a small
13 * bloom filter, we can easily (and cheaply) test whether it contains values
14 * we get later.
15 *
16 * The index only supports equality operators, similarly to hash indexes.
17 * Bloom indexes are however much smaller, and support only bitmap scans.
18 *
19 * Note: Don't confuse this with bloom indexes, implemented in a contrib
20 * module. That extension implements an entirely new AM, building a bloom
21 * filter on multiple columns in a single row. This opclass works with an
22 * existing AM (BRIN) and builds bloom filter on a column.
23 *
24 *
25 * values vs. hashes
26 * -----------------
27 *
28 * The original column values are not used directly, but are first hashed
29 * using the regular type-specific hash function, producing a uint32 hash.
30 * And this hash value is then added to the summary - i.e. it's hashed
31 * again and added to the bloom filter.
32 *
33 * This allows the code to treat all data types (byval/byref/...) the same
34 * way, with only minimal space requirements, because we're working with
35 * hashes and not the original values. Everything is uint32.
36 *
37 * Of course, this assumes the built-in hash function is reasonably good,
38 * without too many collisions etc. But that does seem to be the case, at
39 * least based on past experience. After all, the same hash functions are
40 * used for hash indexes, hash partitioning and so on.
41 *
42 *
43 * hashing scheme
44 * --------------
45 *
46 * Bloom filters require a number of independent hash functions. There are
47 * different schemes how to construct them - for example we might use
48 * hash_uint32_extended with random seeds, but that seems fairly expensive.
49 * We use a scheme requiring only two functions described in this paper:
50 *
51 * Less Hashing, Same Performance:Building a Better Bloom Filter
52 * Adam Kirsch, Michael Mitzenmacher, Harvard School of Engineering and
53 * Applied Sciences, Cambridge, Massachusetts [DOI 10.1002/rsa.20208]
54 *
55 * The two hash functions h1 and h2 are calculated using hard-coded seeds,
56 * and then combined using (h1 + i * h2) to generate the hash functions.
57 *
58 *
59 * sizing the bloom filter
60 * -----------------------
61 *
62 * Size of a bloom filter depends on the number of distinct values we will
63 * store in it, and the desired false positive rate. The higher the number
64 * of distinct values and/or the lower the false positive rate, the larger
65 * the bloom filter. On the other hand, we want to keep the index as small
66 * as possible - that's one of the basic advantages of BRIN indexes.
67 *
68 * Although the number of distinct elements (in a page range) depends on
69 * the data, we can consider it fixed. This simplifies the trade-off to
70 * just false positive rate vs. size.
71 *
72 * At the page range level, false positive rate is a probability the bloom
73 * filter matches a random value. For the whole index (with sufficiently
74 * many page ranges) it represents the fraction of the index ranges (and
75 * thus fraction of the table to be scanned) matching the random value.
76 *
77 * Furthermore, the size of the bloom filter is subject to implementation
78 * limits - it has to fit onto a single index page (8kB by default). As
79 * the bitmap is inherently random (when "full" about half the bits is set
80 * to 1, randomly), compression can't help very much.
81 *
82 * To reduce the size of a filter (to fit to a page), we have to either
83 * accept higher false positive rate (undesirable), or reduce the number
84 * of distinct items to be stored in the filter. We can't alter the input
85 * data, of course, but we may make the BRIN page ranges smaller - instead
86 * of the default 128 pages (1MB) we may build index with 16-page ranges,
87 * or something like that. This should reduce the number of distinct values
88 * in the page range, making the filter smaller (with fixed false positive
89 * rate). Even for random data sets this should help, as the number of rows
90 * per heap page is limited (to ~290 with very narrow tables, likely ~20
91 * in practice).
92 *
93 * Of course, good sizing decisions depend on having the necessary data,
94 * i.e. number of distinct values in a page range (of a given size) and
95 * table size (to estimate cost change due to change in false positive
96 * rate due to having larger index vs. scanning larger indexes). We may
97 * not have that data - for example when building an index on empty table
98 * it's not really possible. And for some data we only have estimates for
99 * the whole table and we can only estimate per-range values (ndistinct).
100 *
101 * Another challenge is that while the bloom filter is per-column, it's
102 * the whole index tuple that has to fit into a page. And for multi-column
103 * indexes that may include pieces we have no control over (not necessarily
104 * bloom filters, the other columns may use other BRIN opclasses). So it's
105 * not entirely clear how to distribute the space between those columns.
106 *
107 * The current logic, implemented in brin_bloom_get_ndistinct, attempts to
108 * make some basic sizing decisions, based on the size of BRIN ranges, and
109 * the maximum number of rows per range.
110 *
111 *
112 * IDENTIFICATION
113 * src/backend/access/brin/brin_bloom.c
114 */
115#include "postgres.h"
116
117#include <math.h>
118
119#include "access/brin.h"
120#include "access/brin_internal.h"
121#include "access/brin_page.h"
122#include "access/brin_tuple.h"
123#include "access/genam.h"
124#include "access/htup_details.h"
125#include "access/reloptions.h"
126#include "catalog/pg_am.h"
127#include "catalog/pg_type.h"
128#include "common/hashfn.h"
129#include "utils/fmgrprotos.h"
130#include "utils/rel.h"
131
132#define BloomEqualStrategyNumber 1
133
134/*
135 * Additional SQL level support functions. We only have one, which is
136 * used to calculate hash of the input value.
137 *
138 * Procedure numbers must not use values reserved for BRIN itself; see
139 * brin_internal.h.
140 */
141#define BLOOM_MAX_PROCNUMS 1 /* maximum support procs we need */
142#define PROCNUM_HASH 11 /* required */
143
144/*
145 * Subtract this from procnum to obtain index in BloomOpaque arrays
146 * (Must be equal to minimum of private procnums).
147 */
148#define PROCNUM_BASE 11
149
150/*
151 * Storage type for BRIN's reloptions.
152 */
153typedef struct BloomOptions
154{
155 int32 vl_len_; /* varlena header (do not touch directly!) */
156 double nDistinctPerRange; /* number of distinct values per range */
157 double falsePositiveRate; /* false positive for bloom filter */
159
160/*
161 * The current min value (16) is somewhat arbitrary, but it's based
162 * on the fact that the filter header is ~20B alone, which is about
163 * the same as the filter bitmap for 16 distinct items with 1% false
164 * positive rate. So by allowing lower values we'd not gain much. In
165 * any case, the min should not be larger than MaxHeapTuplesPerPage
166 * (~290), which is the theoretical maximum for single-page ranges.
167 */
168#define BLOOM_MIN_NDISTINCT_PER_RANGE 16
169
170/*
171 * Used to determine number of distinct items, based on the number of rows
172 * in a page range. The 10% is somewhat similar to what estimate_num_groups
173 * does, so we use the same factor here.
174 */
175#define BLOOM_DEFAULT_NDISTINCT_PER_RANGE -0.1 /* 10% of values */
176
177/*
178 * Allowed range and default value for the false positive range. The exact
179 * values are somewhat arbitrary, but were chosen considering the various
180 * parameters (size of filter vs. page size, etc.).
181 *
182 * The lower the false-positive rate, the more accurate the filter is, but
183 * it also gets larger - at some point this eliminates the main advantage
184 * of BRIN indexes, which is the tiny size. At 0.01% the index is about
185 * 10% of the table (assuming 290 distinct values per 8kB page).
186 *
187 * On the other hand, as the false-positive rate increases, larger part of
188 * the table has to be scanned due to mismatches - at 25% we're probably
189 * close to sequential scan being cheaper.
190 */
191#define BLOOM_MIN_FALSE_POSITIVE_RATE 0.0001 /* 0.01% fp rate */
192#define BLOOM_MAX_FALSE_POSITIVE_RATE 0.25 /* 25% fp rate */
193#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE 0.01 /* 1% fp rate */
194
195#define BloomGetNDistinctPerRange(opts) \
196 ((opts) && (((BloomOptions *) (opts))->nDistinctPerRange != 0) ? \
197 (((BloomOptions *) (opts))->nDistinctPerRange) : \
198 BLOOM_DEFAULT_NDISTINCT_PER_RANGE)
199
200#define BloomGetFalsePositiveRate(opts) \
201 ((opts) && (((BloomOptions *) (opts))->falsePositiveRate != 0.0) ? \
202 (((BloomOptions *) (opts))->falsePositiveRate) : \
203 BLOOM_DEFAULT_FALSE_POSITIVE_RATE)
204
205/*
206 * And estimate of the largest bloom we can fit onto a page. This is not
207 * a perfect guarantee, for a couple of reasons. For example, the row may
208 * be larger because the index has multiple columns.
209 */
210#define BloomMaxFilterSize \
211 MAXALIGN_DOWN(BLCKSZ - \
212 (MAXALIGN(SizeOfPageHeaderData + \
213 sizeof(ItemIdData)) + \
214 MAXALIGN(sizeof(BrinSpecialSpace)) + \
215 SizeOfBrinTuple))
216
217/*
218 * Seeds used to calculate two hash functions h1 and h2, which are then used
219 * to generate k hashes using the (h1 + i * h2) scheme.
220 */
221#define BLOOM_SEED_1 0x71d924af
222#define BLOOM_SEED_2 0xba48b314
223
224/*
225 * Bloom Filter
226 *
227 * Represents a bloom filter, built on hashes of the indexed values. That is,
228 * we compute a uint32 hash of the value, and then store this hash into the
229 * bloom filter (and compute additional hashes on it).
230 *
231 * XXX We could implement "sparse" bloom filters, keeping only the bytes that
232 * are not entirely 0. But while indexes don't support TOAST, the varlena can
233 * still be compressed. So this seems unnecessary, because the compression
234 * should do the same job.
235 *
236 * XXX We can also watch the number of bits set in the bloom filter, and then
237 * stop using it (and not store the bitmap, to save space) when the false
238 * positive rate gets too high. But even if the false positive rate exceeds the
239 * desired value, it still can eliminate some page ranges.
240 */
241typedef struct BloomFilter
242{
243 /* varlena header (do not touch directly!) */
245
246 /* space for various flags (unused for now) */
248
249 /* fields for the HASHED phase */
250 uint8 nhashes; /* number of hash functions */
251 uint32 nbits; /* number of bits in the bitmap (size) */
252 uint32 nbits_set; /* number of bits set to 1 */
253
254 /* data of the bloom filter */
257
258/*
259 * bloom_filter_size
260 * Calculate Bloom filter parameters (nbits, nbytes, nhashes).
261 *
262 * Given expected number of distinct values and desired false positive rate,
263 * calculates the optimal parameters of the Bloom filter.
264 *
265 * The resulting parameters are returned through nbytesp (number of bytes),
266 * nbitsp (number of bits) and nhashesp (number of hash functions). If a
267 * pointer is NULL, the parameter is not returned.
268 */
269static void
270bloom_filter_size(int ndistinct, double false_positive_rate,
271 int *nbytesp, int *nbitsp, int *nhashesp)
272{
273 double k;
274 int nbits,
275 nbytes;
276
277 /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
278 nbits = ceil(-(ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
279
280 /* round m to whole bytes */
281 nbytes = ((nbits + 7) / 8);
282 nbits = nbytes * 8;
283
284 /*
285 * round(log(2.0) * m / ndistinct), but assume round() may not be
286 * available on Windows
287 */
288 k = log(2.0) * nbits / ndistinct;
289 k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
290
291 if (nbytesp)
292 *nbytesp = nbytes;
293
294 if (nbitsp)
295 *nbitsp = nbits;
296
297 if (nhashesp)
298 *nhashesp = (int) k;
299}
300
301/*
302 * bloom_init
303 * Initialize the Bloom Filter, allocate all the memory.
304 *
305 * The filter is initialized with optimal size for ndistinct expected values
306 * and the requested false positive rate. The filter is stored as varlena.
307 */
308static BloomFilter *
309bloom_init(int ndistinct, double false_positive_rate)
310{
311 Size len;
312 BloomFilter *filter;
313
314 int nbits; /* size of filter / number of bits */
315 int nbytes; /* size of filter / number of bytes */
316 int nhashes; /* number of hash functions */
317
318 Assert(ndistinct > 0);
319 Assert(false_positive_rate > 0 && false_positive_rate < 1);
320
321 /* calculate bloom filter size / parameters */
322 bloom_filter_size(ndistinct, false_positive_rate,
323 &nbytes, &nbits, &nhashes);
324
325 /*
326 * Reject filters that are obviously too large to store on a page.
327 *
328 * Initially the bloom filter is just zeroes and so very compressible, but
329 * as we add values it gets more and more random, and so less and less
330 * compressible. So initially everything fits on the page, but we might
331 * get surprising failures later - we want to prevent that, so we reject
332 * bloom filter that are obviously too large.
333 *
334 * XXX It's not uncommon to oversize the bloom filter a bit, to defend
335 * against unexpected data anomalies (parts of table with more distinct
336 * values per range etc.). But we still need to make sure even the
337 * oversized filter fits on page, if such need arises.
338 *
339 * XXX This check is not perfect, because the index may have multiple
340 * filters that are small individually, but too large when combined.
341 */
342 if (nbytes > BloomMaxFilterSize)
343 elog(ERROR, "the bloom filter is too large (%d > %zu)", nbytes,
345
346 /*
347 * We allocate the whole filter. Most of it is going to be 0 bits, so the
348 * varlena is easy to compress.
349 */
350 len = offsetof(BloomFilter, data) + nbytes;
351
352 filter = (BloomFilter *) palloc0(len);
353
354 filter->flags = 0;
355 filter->nhashes = nhashes;
356 filter->nbits = nbits;
357
358 SET_VARSIZE(filter, len);
359
360 return filter;
361}
362
363
364/*
365 * bloom_add_value
366 * Add value to the bloom filter.
367 */
368static BloomFilter *
369bloom_add_value(BloomFilter *filter, uint32 value, bool *updated)
370{
371 int i;
372 uint64 h1,
373 h2;
374
375 /* compute the hashes, used for the bloom filter */
378
379 /* compute the requested number of hashes */
380 for (i = 0; i < filter->nhashes; i++)
381 {
382 /* h1 + h2 + f(i) */
383 uint32 h = (h1 + i * h2) % filter->nbits;
384 uint32 byte = (h / 8);
385 uint32 bit = (h % 8);
386
387 /* if the bit is not set, set it and remember we did that */
388 if (!(filter->data[byte] & (0x01 << bit)))
389 {
390 filter->data[byte] |= (0x01 << bit);
391 filter->nbits_set++;
392 if (updated)
393 *updated = true;
394 }
395 }
396
397 return filter;
398}
399
400
401/*
402 * bloom_contains_value
403 * Check if the bloom filter contains a particular value.
404 */
405static bool
407{
408 int i;
409 uint64 h1,
410 h2;
411
412 /* calculate the two hashes */
415
416 /* compute the requested number of hashes */
417 for (i = 0; i < filter->nhashes; i++)
418 {
419 /* h1 + h2 + f(i) */
420 uint32 h = (h1 + i * h2) % filter->nbits;
421 uint32 byte = (h / 8);
422 uint32 bit = (h % 8);
423
424 /* if the bit is not set, the value is not there */
425 if (!(filter->data[byte] & (0x01 << bit)))
426 return false;
427 }
428
429 /* all hashes found in bloom filter */
430 return true;
431}
432
433typedef struct BloomOpaque
434{
435 /*
436 * XXX At this point we only need a single proc (to compute the hash), but
437 * let's keep the array just like inclusion and minmax opclasses, for
438 * consistency. We may need additional procs in the future.
439 */
443
444static FmgrInfo *bloom_get_procinfo(BrinDesc *bdesc, uint16 attno,
445 uint16 procnum);
446
447
448Datum
450{
451 BrinOpcInfo *result;
452
453 /*
454 * opaque->strategy_procinfos is initialized lazily; here it is set to
455 * all-uninitialized by palloc0 which sets fn_oid to InvalidOid.
456 *
457 * bloom indexes only store the filter as a single BYTEA column
458 */
459
460 result = palloc0(MAXALIGN(SizeofBrinOpcInfo(1)) +
461 sizeof(BloomOpaque));
462 result->oi_nstored = 1;
463 result->oi_regular_nulls = true;
464 result->oi_opaque = (BloomOpaque *)
465 MAXALIGN((char *) result + SizeofBrinOpcInfo(1));
466 result->oi_typcache[0] = lookup_type_cache(PG_BRIN_BLOOM_SUMMARYOID, 0);
467
468 PG_RETURN_POINTER(result);
469}
470
471/*
472 * brin_bloom_get_ndistinct
473 * Determine the ndistinct value used to size bloom filter.
474 *
475 * Adjust the ndistinct value based on the pagesPerRange value. First,
476 * if it's negative, it's assumed to be relative to maximum number of
477 * tuples in the range (assuming each page gets MaxHeapTuplesPerPage
478 * tuples, which is likely a significant over-estimate). We also clamp
479 * the value, not to over-size the bloom filter unnecessarily.
480 *
481 * XXX We can only do this when the pagesPerRange value was supplied.
482 * If it wasn't, it has to be a read-only access to the index, in which
483 * case we don't really care. But perhaps we should fall-back to the
484 * default pagesPerRange value?
485 *
486 * XXX We might also fetch info about ndistinct estimate for the column,
487 * and compute the expected number of distinct values in a range. But
488 * that may be tricky due to data being sorted in various ways, so it
489 * seems better to rely on the upper estimate.
490 *
491 * XXX We might also calculate a better estimate of rows per BRIN range,
492 * instead of using MaxHeapTuplesPerPage (which probably produces values
493 * much higher than reality).
494 */
495static int
497{
498 double ndistinct;
499 double maxtuples;
500 BlockNumber pagesPerRange;
501
502 pagesPerRange = BrinGetPagesPerRange(bdesc->bd_index);
503 ndistinct = BloomGetNDistinctPerRange(opts);
504
505 Assert(BlockNumberIsValid(pagesPerRange));
506
507 maxtuples = MaxHeapTuplesPerPage * pagesPerRange;
508
509 /*
510 * Similarly to n_distinct, negative values are relative - in this case to
511 * maximum number of tuples in the page range (maxtuples).
512 */
513 if (ndistinct < 0)
514 ndistinct = (-ndistinct) * maxtuples;
515
516 /*
517 * Positive values are to be used directly, but we still apply a couple of
518 * safeties to avoid using unreasonably small bloom filters.
519 */
520 ndistinct = Max(ndistinct, BLOOM_MIN_NDISTINCT_PER_RANGE);
521
522 /*
523 * And don't use more than the maximum possible number of tuples, in the
524 * range, which would be entirely wasteful.
525 */
526 ndistinct = Min(ndistinct, maxtuples);
527
528 return (int) ndistinct;
529}
530
531/*
532 * Examine the given index tuple (which contains partial status of a certain
533 * page range) by comparing it to the given value that comes from another heap
534 * tuple. If the new value is outside the bloom filter specified by the
535 * existing tuple values, update the index tuple and return true. Otherwise,
536 * return false and do not modify in this case.
537 */
538Datum
540{
541 BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0);
542 BrinValues *column = (BrinValues *) PG_GETARG_POINTER(1);
546 Oid colloid = PG_GET_COLLATION();
547 FmgrInfo *hashFn;
548 uint32 hashValue;
549 bool updated = false;
550 AttrNumber attno;
551 BloomFilter *filter;
552
553 Assert(!isnull);
554
555 attno = column->bv_attno;
556
557 /*
558 * If this is the first non-null value, we need to initialize the bloom
559 * filter. Otherwise just extract the existing bloom filter from
560 * BrinValues.
561 */
562 if (column->bv_allnulls)
563 {
566 column->bv_values[0] = PointerGetDatum(filter);
567 column->bv_allnulls = false;
568 updated = true;
569 }
570 else
571 filter = (BloomFilter *) PG_DETOAST_DATUM(column->bv_values[0]);
572
573 /*
574 * Compute the hash of the new value, using the supplied hash function,
575 * and then add the hash value to the bloom filter.
576 */
577 hashFn = bloom_get_procinfo(bdesc, attno, PROCNUM_HASH);
578
579 hashValue = DatumGetUInt32(FunctionCall1Coll(hashFn, colloid, newval));
580
581 filter = bloom_add_value(filter, hashValue, &updated);
582
583 column->bv_values[0] = PointerGetDatum(filter);
584
585 PG_RETURN_BOOL(updated);
586}
587
588/*
589 * Given an index tuple corresponding to a certain page range and a scan key,
590 * return whether the scan key is consistent with the index tuple's bloom
591 * filter. Return true if so, false otherwise.
592 */
593Datum
595{
596 BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0);
597 BrinValues *column = (BrinValues *) PG_GETARG_POINTER(1);
598 ScanKey *keys = (ScanKey *) PG_GETARG_POINTER(2);
599 int nkeys = PG_GETARG_INT32(3);
600 Oid colloid = PG_GET_COLLATION();
601 AttrNumber attno;
602 Datum value;
603 bool matches;
604 FmgrInfo *finfo;
605 uint32 hashValue;
606 BloomFilter *filter;
607 int keyno;
608
609 filter = (BloomFilter *) PG_DETOAST_DATUM(column->bv_values[0]);
610
611 Assert(filter);
612
613 /*
614 * Assume all scan keys match. We'll be searching for a scan key
615 * eliminating the page range (we can stop on the first such key).
616 */
617 matches = true;
618
619 for (keyno = 0; keyno < nkeys; keyno++)
620 {
621 ScanKey key = keys[keyno];
622
623 /* NULL keys are handled and filtered-out in bringetbitmap */
624 Assert(!(key->sk_flags & SK_ISNULL));
625
626 attno = key->sk_attno;
627 value = key->sk_argument;
628
629 switch (key->sk_strategy)
630 {
632
633 /*
634 * We want to return the current page range if the bloom
635 * filter seems to contain the value.
636 */
637 finfo = bloom_get_procinfo(bdesc, attno, PROCNUM_HASH);
638
639 hashValue = DatumGetUInt32(FunctionCall1Coll(finfo, colloid, value));
640 matches &= bloom_contains_value(filter, hashValue);
641
642 break;
643 default:
644 /* shouldn't happen */
645 elog(ERROR, "invalid strategy number %d", key->sk_strategy);
646 matches = false;
647 break;
648 }
649
650 if (!matches)
651 break;
652 }
653
654 PG_RETURN_BOOL(matches);
655}
656
657/*
658 * Given two BrinValues, update the first of them as a union of the summary
659 * values contained in both. The second one is untouched.
660 *
661 * XXX We assume the bloom filters have the same parameters for now. In the
662 * future we should have 'can union' function, to decide if we can combine
663 * two particular bloom filters.
664 */
665Datum
667{
668 int i;
669 int nbytes;
672 BloomFilter *filter_a;
673 BloomFilter *filter_b;
674
675 Assert(col_a->bv_attno == col_b->bv_attno);
676 Assert(!col_a->bv_allnulls && !col_b->bv_allnulls);
677
678 filter_a = (BloomFilter *) PG_DETOAST_DATUM(col_a->bv_values[0]);
679 filter_b = (BloomFilter *) PG_DETOAST_DATUM(col_b->bv_values[0]);
680
681 /* make sure the filters use the same parameters */
682 Assert(filter_a && filter_b);
683 Assert(filter_a->nbits == filter_b->nbits);
684 Assert(filter_a->nhashes == filter_b->nhashes);
685 Assert((filter_a->nbits > 0) && (filter_a->nbits % 8 == 0));
686
687 nbytes = (filter_a->nbits) / 8;
688
689 /* simply OR the bitmaps */
690 for (i = 0; i < nbytes; i++)
691 filter_a->data[i] |= filter_b->data[i];
692
693 /* update the number of bits set in the filter */
694 filter_a->nbits_set = pg_popcount((const char *) filter_a->data, nbytes);
695
697}
698
699/*
700 * Cache and return inclusion opclass support procedure
701 *
702 * Return the procedure corresponding to the given function support number
703 * or null if it does not exist.
704 */
705static FmgrInfo *
707{
708 BloomOpaque *opaque;
709 uint16 basenum = procnum - PROCNUM_BASE;
710
711 /*
712 * We cache these in the opaque struct, to avoid repetitive syscache
713 * lookups.
714 */
715 opaque = (BloomOpaque *) bdesc->bd_info[attno - 1]->oi_opaque;
716
717 /*
718 * If we already searched for this proc and didn't find it, don't bother
719 * searching again.
720 */
721 if (opaque->extra_proc_missing[basenum])
722 return NULL;
723
724 if (opaque->extra_procinfos[basenum].fn_oid == InvalidOid)
725 {
727 procnum)))
728 {
729 fmgr_info_copy(&opaque->extra_procinfos[basenum],
730 index_getprocinfo(bdesc->bd_index, attno, procnum),
731 bdesc->bd_context);
732 }
733 else
734 {
735 opaque->extra_proc_missing[basenum] = true;
736 return NULL;
737 }
738 }
739
740 return &opaque->extra_procinfos[basenum];
741}
742
743Datum
745{
747
748 init_local_reloptions(relopts, sizeof(BloomOptions));
749
750 add_local_real_reloption(relopts, "n_distinct_per_range",
751 "number of distinct items expected in a BRIN page range",
753 -1.0, INT_MAX, offsetof(BloomOptions, nDistinctPerRange));
754
755 add_local_real_reloption(relopts, "false_positive_rate",
756 "desired false-positive rate for the bloom filters",
760 offsetof(BloomOptions, falsePositiveRate));
761
763}
764
765/*
766 * brin_bloom_summary_in
767 * - input routine for type brin_bloom_summary.
768 *
769 * brin_bloom_summary is only used internally to represent summaries
770 * in BRIN bloom indexes, so it has no operations of its own, and we
771 * disallow input too.
772 */
773Datum
775{
776 /*
777 * brin_bloom_summary stores the data in binary form and parsing text
778 * input is not needed, so disallow this.
779 */
781 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
782 errmsg("cannot accept a value of type %s", "pg_brin_bloom_summary")));
783
784 PG_RETURN_VOID(); /* keep compiler quiet */
785}
786
787
788/*
789 * brin_bloom_summary_out
790 * - output routine for type brin_bloom_summary.
791 *
792 * BRIN bloom summaries are serialized into a bytea value, but we want
793 * to output something nicer humans can understand.
794 */
795Datum
797{
798 BloomFilter *filter;
800
801 /* detoast the data to get value with a full 4B header */
803
806
807 appendStringInfo(&str, "mode: hashed nhashes: %u nbits: %u nbits_set: %u",
808 filter->nhashes, filter->nbits, filter->nbits_set);
809
811
813}
814
815/*
816 * brin_bloom_summary_recv
817 * - binary input routine for type brin_bloom_summary.
818 */
819Datum
821{
823 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
824 errmsg("cannot accept a value of type %s", "pg_brin_bloom_summary")));
825
826 PG_RETURN_VOID(); /* keep compiler quiet */
827}
828
829/*
830 * brin_bloom_summary_send
831 * - binary output routine for type brin_bloom_summary.
832 *
833 * BRIN bloom summaries are serialized in a bytea value (although the
834 * type is named differently), so let's just send that.
835 */
836Datum
838{
839 return byteasend(fcinfo);
840}
int16 AttrNumber
Definition: attnum.h:21
uint32 BlockNumber
Definition: block.h:31
static bool BlockNumberIsValid(BlockNumber blockNumber)
Definition: block.h:71
#define BrinGetPagesPerRange(relation)
Definition: brin.h:40
static int brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
Definition: brin_bloom.c:496
#define PROCNUM_HASH
Definition: brin_bloom.c:142
#define BLOOM_SEED_1
Definition: brin_bloom.c:221
#define BLOOM_DEFAULT_NDISTINCT_PER_RANGE
Definition: brin_bloom.c:175
Datum brin_bloom_consistent(PG_FUNCTION_ARGS)
Definition: brin_bloom.c:594
static void bloom_filter_size(int ndistinct, double false_positive_rate, int *nbytesp, int *nbitsp, int *nhashesp)
Definition: brin_bloom.c:270
static BloomFilter * bloom_init(int ndistinct, double false_positive_rate)
Definition: brin_bloom.c:309
#define BloomGetNDistinctPerRange(opts)
Definition: brin_bloom.c:195
struct BloomFilter BloomFilter
Datum brin_bloom_options(PG_FUNCTION_ARGS)
Definition: brin_bloom.c:744
struct BloomOptions BloomOptions
#define BLOOM_MAX_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:192
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:193
static bool bloom_contains_value(BloomFilter *filter, uint32 value)
Definition: brin_bloom.c:406
#define BLOOM_MAX_PROCNUMS
Definition: brin_bloom.c:141
#define BloomGetFalsePositiveRate(opts)
Definition: brin_bloom.c:200
#define BloomMaxFilterSize
Definition: brin_bloom.c:210
#define BLOOM_MIN_NDISTINCT_PER_RANGE
Definition: brin_bloom.c:168
#define BloomEqualStrategyNumber
Definition: brin_bloom.c:132
struct BloomOpaque BloomOpaque
#define BLOOM_MIN_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:191
#define BLOOM_SEED_2
Definition: brin_bloom.c:222
#define PROCNUM_BASE
Definition: brin_bloom.c:148
Datum brin_bloom_union(PG_FUNCTION_ARGS)
Definition: brin_bloom.c:666
Datum brin_bloom_summary_send(PG_FUNCTION_ARGS)
Definition: brin_bloom.c:837
Datum brin_bloom_summary_out(PG_FUNCTION_ARGS)
Definition: brin_bloom.c:796
static FmgrInfo * bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
Definition: brin_bloom.c:706
Datum brin_bloom_add_value(PG_FUNCTION_ARGS)
Definition: brin_bloom.c:539
Datum brin_bloom_summary_in(PG_FUNCTION_ARGS)
Definition: brin_bloom.c:774
static BloomFilter * bloom_add_value(BloomFilter *filter, uint32 value, bool *updated)
Definition: brin_bloom.c:369
Datum brin_bloom_summary_recv(PG_FUNCTION_ARGS)
Definition: brin_bloom.c:820
Datum brin_bloom_opcinfo(PG_FUNCTION_ARGS)
Definition: brin_bloom.c:449
#define SizeofBrinOpcInfo(ncols)
Definition: brin_internal.h:41
#define RegProcedureIsValid(p)
Definition: c.h:731
#define Min(x, y)
Definition: c.h:958
#define MAXALIGN(LEN)
Definition: c.h:765
uint8_t uint8
Definition: c.h:483
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:201
#define Max(x, y)
Definition: c.h:952
#define Assert(condition)
Definition: c.h:812
#define FLEXIBLE_ARRAY_MEMBER
Definition: c.h:417
int32_t int32
Definition: c.h:481
uint64_t uint64
Definition: c.h:486
uint16_t uint16
Definition: c.h:484
uint32_t uint32
Definition: c.h:485
size_t Size
Definition: c.h:559
int errcode(int sqlerrcode)
Definition: elog.c:853
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
#define ereport(elevel,...)
Definition: elog.h:149
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
Definition: fmgr.c:1129
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:580
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define PG_RETURN_CSTRING(x)
Definition: fmgr.h:362
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
#define PG_GET_OPCLASS_OPTIONS()
Definition: fmgr.h:342
#define PG_DETOAST_DATUM(datum)
Definition: fmgr.h:240
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
#define PG_GET_COLLATION()
Definition: fmgr.h:198
#define PG_FUNCTION_ARGS
Definition: fmgr.h:193
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
#define newval
uint64 hash_bytes_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.c:631
const char * str
#define MaxHeapTuplesPerPage
Definition: htup_details.h:572
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:862
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:828
static struct @161 value
int i
Definition: isn.c:72
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:76
void * palloc0(Size size)
Definition: mcxt.c:1347
static AmcheckOptions opts
Definition: pg_amcheck.c:112
static uint64 pg_popcount(const char *buf, int bytes)
Definition: pg_bitutils.h:339
const void size_t len
const void * data
static uint32 DatumGetUInt32(Datum X)
Definition: postgres.h:222
static Datum PointerGetDatum(const void *X)
Definition: postgres.h:322
uintptr_t Datum
Definition: postgres.h:64
#define InvalidOid
Definition: postgres_ext.h:36
unsigned int Oid
Definition: postgres_ext.h:31
void init_local_reloptions(local_relopts *relopts, Size relopt_struct_size)
Definition: reloptions.c:734
void add_local_real_reloption(local_relopts *relopts, const char *name, const char *desc, double default_val, double min_val, double max_val, int offset)
Definition: reloptions.c:972
#define SK_ISNULL
Definition: skey.h:115
void appendStringInfo(StringInfo str, const char *fmt,...)
Definition: stringinfo.c:94
void appendStringInfoChar(StringInfo str, char ch)
Definition: stringinfo.c:191
void initStringInfo(StringInfo str)
Definition: stringinfo.c:56
uint8 nhashes
Definition: brin_bloom.c:250
char data[FLEXIBLE_ARRAY_MEMBER]
Definition: brin_bloom.c:255
uint32 nbits_set
Definition: brin_bloom.c:252
uint32 nbits
Definition: brin_bloom.c:251
uint16 flags
Definition: brin_bloom.c:247
int32 vl_len_
Definition: brin_bloom.c:244
FmgrInfo extra_procinfos[BLOOM_MAX_PROCNUMS]
Definition: brin_bloom.c:440
bool extra_proc_missing[BLOOM_MAX_PROCNUMS]
Definition: brin_bloom.c:441
double falsePositiveRate
Definition: brin_bloom.c:157
int32 vl_len_
Definition: bloom.h:103
double nDistinctPerRange
Definition: brin_bloom.c:156
BrinOpcInfo * bd_info[FLEXIBLE_ARRAY_MEMBER]
Definition: brin_internal.h:62
Relation bd_index
Definition: brin_internal.h:50
MemoryContext bd_context
Definition: brin_internal.h:47
TypeCacheEntry * oi_typcache[FLEXIBLE_ARRAY_MEMBER]
Definition: brin_internal.h:37
uint16 oi_nstored
Definition: brin_internal.h:28
bool oi_regular_nulls
Definition: brin_internal.h:31
void * oi_opaque
Definition: brin_internal.h:34
Datum * bv_values
Definition: brin_tuple.h:34
AttrNumber bv_attno
Definition: brin_tuple.h:31
bool bv_allnulls
Definition: brin_tuple.h:33
Definition: fmgr.h:57
Oid fn_oid
Definition: fmgr.h:59
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:386
#define SET_VARSIZE(PTR, len)
Definition: varatt.h:305
Datum bit(PG_FUNCTION_ARGS)
Definition: varbit.c:391
Datum byteasend(PG_FUNCTION_ARGS)
Definition: varlena.c:490