PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
brin_bloom.c File Reference
#include "postgres.h"
#include <math.h>
#include "access/brin.h"
#include "access/brin_internal.h"
#include "access/brin_page.h"
#include "access/brin_tuple.h"
#include "access/genam.h"
#include "access/htup_details.h"
#include "access/reloptions.h"
#include "catalog/pg_am.h"
#include "catalog/pg_type.h"
#include "common/hashfn.h"
#include "utils/fmgrprotos.h"
#include "utils/rel.h"
Include dependency graph for brin_bloom.c:

Go to the source code of this file.

Data Structures

struct  BloomOptions
 
struct  BloomFilter
 
struct  BloomOpaque
 

Macros

#define BloomEqualStrategyNumber   1
 
#define BLOOM_MAX_PROCNUMS   1 /* maximum support procs we need */
 
#define PROCNUM_HASH   11 /* required */
 
#define PROCNUM_BASE   11
 
#define BLOOM_MIN_NDISTINCT_PER_RANGE   16
 
#define BLOOM_DEFAULT_NDISTINCT_PER_RANGE   -0.1 /* 10% of values */
 
#define BLOOM_MIN_FALSE_POSITIVE_RATE   0.0001 /* 0.01% fp rate */
 
#define BLOOM_MAX_FALSE_POSITIVE_RATE   0.25 /* 25% fp rate */
 
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE   0.01 /* 1% fp rate */
 
#define BloomGetNDistinctPerRange(opts)
 
#define BloomGetFalsePositiveRate(opts)
 
#define BloomMaxFilterSize
 
#define BLOOM_SEED_1   0x71d924af
 
#define BLOOM_SEED_2   0xba48b314
 

Typedefs

typedef struct BloomOptions BloomOptions
 
typedef struct BloomFilter BloomFilter
 
typedef struct BloomOpaque BloomOpaque
 

Functions

static void bloom_filter_size (int ndistinct, double false_positive_rate, int *nbytesp, int *nbitsp, int *nhashesp)
 
static BloomFilterbloom_init (int ndistinct, double false_positive_rate)
 
static BloomFilterbloom_add_value (BloomFilter *filter, uint32 value, bool *updated)
 
static bool bloom_contains_value (BloomFilter *filter, uint32 value)
 
static FmgrInfobloom_get_procinfo (BrinDesc *bdesc, uint16 attno, uint16 procnum)
 
Datum brin_bloom_opcinfo (PG_FUNCTION_ARGS)
 
static int brin_bloom_get_ndistinct (BrinDesc *bdesc, BloomOptions *opts)
 
Datum brin_bloom_add_value (PG_FUNCTION_ARGS)
 
Datum brin_bloom_consistent (PG_FUNCTION_ARGS)
 
Datum brin_bloom_union (PG_FUNCTION_ARGS)
 
Datum brin_bloom_options (PG_FUNCTION_ARGS)
 
Datum brin_bloom_summary_in (PG_FUNCTION_ARGS)
 
Datum brin_bloom_summary_out (PG_FUNCTION_ARGS)
 
Datum brin_bloom_summary_recv (PG_FUNCTION_ARGS)
 
Datum brin_bloom_summary_send (PG_FUNCTION_ARGS)
 

Macro Definition Documentation

◆ BLOOM_DEFAULT_FALSE_POSITIVE_RATE

#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE   0.01 /* 1% fp rate */

Definition at line 193 of file brin_bloom.c.

◆ BLOOM_DEFAULT_NDISTINCT_PER_RANGE

#define BLOOM_DEFAULT_NDISTINCT_PER_RANGE   -0.1 /* 10% of values */

Definition at line 175 of file brin_bloom.c.

◆ BLOOM_MAX_FALSE_POSITIVE_RATE

#define BLOOM_MAX_FALSE_POSITIVE_RATE   0.25 /* 25% fp rate */

Definition at line 192 of file brin_bloom.c.

◆ BLOOM_MAX_PROCNUMS

#define BLOOM_MAX_PROCNUMS   1 /* maximum support procs we need */

Definition at line 141 of file brin_bloom.c.

◆ BLOOM_MIN_FALSE_POSITIVE_RATE

#define BLOOM_MIN_FALSE_POSITIVE_RATE   0.0001 /* 0.01% fp rate */

Definition at line 191 of file brin_bloom.c.

◆ BLOOM_MIN_NDISTINCT_PER_RANGE

#define BLOOM_MIN_NDISTINCT_PER_RANGE   16

Definition at line 168 of file brin_bloom.c.

◆ BLOOM_SEED_1

#define BLOOM_SEED_1   0x71d924af

Definition at line 221 of file brin_bloom.c.

◆ BLOOM_SEED_2

#define BLOOM_SEED_2   0xba48b314

Definition at line 222 of file brin_bloom.c.

◆ BloomEqualStrategyNumber

#define BloomEqualStrategyNumber   1

Definition at line 132 of file brin_bloom.c.

◆ BloomGetFalsePositiveRate

#define BloomGetFalsePositiveRate (   opts)
Value:
((opts) && (((BloomOptions *) (opts))->falsePositiveRate != 0.0) ? \
(((BloomOptions *) (opts))->falsePositiveRate) : \
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:193
static AmcheckOptions opts
Definition: pg_amcheck.c:112

Definition at line 200 of file brin_bloom.c.

◆ BloomGetNDistinctPerRange

#define BloomGetNDistinctPerRange (   opts)
Value:
((opts) && (((BloomOptions *) (opts))->nDistinctPerRange != 0) ? \
(((BloomOptions *) (opts))->nDistinctPerRange) : \
#define BLOOM_DEFAULT_NDISTINCT_PER_RANGE
Definition: brin_bloom.c:175

Definition at line 195 of file brin_bloom.c.

◆ BloomMaxFilterSize

#define BloomMaxFilterSize
Value:
MAXALIGN_DOWN(BLCKSZ - \
sizeof(ItemIdData)) + \
#define SizeOfBrinTuple
Definition: brin_tuple.h:80
#define SizeOfPageHeaderData
Definition: bufpage.h:216
#define MAXALIGN_DOWN(LEN)
Definition: c.h:777
#define MAXALIGN(LEN)
Definition: c.h:765

Definition at line 210 of file brin_bloom.c.

◆ PROCNUM_BASE

#define PROCNUM_BASE   11

Definition at line 148 of file brin_bloom.c.

◆ PROCNUM_HASH

#define PROCNUM_HASH   11 /* required */

Definition at line 142 of file brin_bloom.c.

Typedef Documentation

◆ BloomFilter

typedef struct BloomFilter BloomFilter

◆ BloomOpaque

typedef struct BloomOpaque BloomOpaque

◆ BloomOptions

typedef struct BloomOptions BloomOptions

Function Documentation

◆ bloom_add_value()

static BloomFilter * bloom_add_value ( BloomFilter filter,
uint32  value,
bool *  updated 
)
static

Definition at line 369 of file brin_bloom.c.

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}
#define BLOOM_SEED_1
Definition: brin_bloom.c:221
#define BLOOM_SEED_2
Definition: brin_bloom.c:222
uint64_t uint64
Definition: c.h:486
uint32_t uint32
Definition: c.h:485
uint64 hash_bytes_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.c:631
static struct @161 value
int i
Definition: isn.c:72
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
Datum bit(PG_FUNCTION_ARGS)
Definition: varbit.c:391

References bit(), BLOOM_SEED_1, BLOOM_SEED_2, BloomFilter::data, hash_bytes_uint32_extended(), i, BloomFilter::nbits, BloomFilter::nbits_set, BloomFilter::nhashes, and value.

Referenced by brin_bloom_add_value().

◆ bloom_contains_value()

static bool bloom_contains_value ( BloomFilter filter,
uint32  value 
)
static

Definition at line 406 of file brin_bloom.c.

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}

References bit(), BLOOM_SEED_1, BLOOM_SEED_2, BloomFilter::data, hash_bytes_uint32_extended(), i, BloomFilter::nbits, BloomFilter::nhashes, and value.

Referenced by brin_bloom_consistent().

◆ bloom_filter_size()

static void bloom_filter_size ( int  ndistinct,
double  false_positive_rate,
int *  nbytesp,
int *  nbitsp,
int *  nhashesp 
)
static

Definition at line 270 of file brin_bloom.c.

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}

Referenced by bloom_init().

◆ bloom_get_procinfo()

static FmgrInfo * bloom_get_procinfo ( BrinDesc bdesc,
uint16  attno,
uint16  procnum 
)
static

Definition at line 706 of file brin_bloom.c.

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}
#define PROCNUM_BASE
Definition: brin_bloom.c:148
#define RegProcedureIsValid(p)
Definition: c.h:731
uint16_t uint16
Definition: c.h:484
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:580
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
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:76
#define InvalidOid
Definition: postgres_ext.h:36
FmgrInfo extra_procinfos[BLOOM_MAX_PROCNUMS]
Definition: brin_bloom.c:440
bool extra_proc_missing[BLOOM_MAX_PROCNUMS]
Definition: brin_bloom.c:441
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
void * oi_opaque
Definition: brin_internal.h:34
Oid fn_oid
Definition: fmgr.h:59

References BrinDesc::bd_context, BrinDesc::bd_index, BrinDesc::bd_info, BloomOpaque::extra_proc_missing, BloomOpaque::extra_procinfos, fmgr_info_copy(), FmgrInfo::fn_oid, if(), index_getprocid(), index_getprocinfo(), InvalidOid, BrinOpcInfo::oi_opaque, PROCNUM_BASE, and RegProcedureIsValid.

Referenced by brin_bloom_add_value(), and brin_bloom_consistent().

◆ bloom_init()

static BloomFilter * bloom_init ( int  ndistinct,
double  false_positive_rate 
)
static

Definition at line 309 of file brin_bloom.c.

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}
static void bloom_filter_size(int ndistinct, double false_positive_rate, int *nbytesp, int *nbitsp, int *nhashesp)
Definition: brin_bloom.c:270
#define BloomMaxFilterSize
Definition: brin_bloom.c:210
#define Assert(condition)
Definition: c.h:812
size_t Size
Definition: c.h:559
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
void * palloc0(Size size)
Definition: mcxt.c:1347
const void size_t len
const void * data
uint16 flags
Definition: brin_bloom.c:247
#define SET_VARSIZE(PTR, len)
Definition: varatt.h:305

References Assert, bloom_filter_size(), BloomMaxFilterSize, data, elog, ERROR, BloomFilter::flags, len, BloomFilter::nbits, BloomFilter::nhashes, palloc0(), and SET_VARSIZE.

Referenced by brin_bloom_add_value().

◆ brin_bloom_add_value()

Datum brin_bloom_add_value ( PG_FUNCTION_ARGS  )

Definition at line 539 of file brin_bloom.c.

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}
int16 AttrNumber
Definition: attnum.h:21
static int brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
Definition: brin_bloom.c:496
#define PROCNUM_HASH
Definition: brin_bloom.c:142
static BloomFilter * bloom_init(int ndistinct, double false_positive_rate)
Definition: brin_bloom.c:309
#define BloomGetFalsePositiveRate(opts)
Definition: brin_bloom.c:200
static FmgrInfo * bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
Definition: brin_bloom.c:706
static BloomFilter * bloom_add_value(BloomFilter *filter, uint32 value, bool *updated)
Definition: brin_bloom.c:369
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:201
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
Definition: fmgr.c:1129
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#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_GET_COLLATION()
Definition: fmgr.h:198
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
#define newval
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
unsigned int Oid
Definition: postgres_ext.h:31
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

References Assert, bloom_add_value(), bloom_get_procinfo(), bloom_init(), BloomGetFalsePositiveRate, brin_bloom_get_ndistinct(), BrinValues::bv_allnulls, BrinValues::bv_attno, BrinValues::bv_values, DatumGetUInt32(), FunctionCall1Coll(), newval, opts, PG_DETOAST_DATUM, PG_GET_COLLATION, PG_GET_OPCLASS_OPTIONS, PG_GETARG_DATUM, PG_GETARG_POINTER, PG_RETURN_BOOL, PG_USED_FOR_ASSERTS_ONLY, PointerGetDatum(), and PROCNUM_HASH.

◆ brin_bloom_consistent()

Datum brin_bloom_consistent ( PG_FUNCTION_ARGS  )

Definition at line 594 of file brin_bloom.c.

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}
static bool bloom_contains_value(BloomFilter *filter, uint32 value)
Definition: brin_bloom.c:406
#define BloomEqualStrategyNumber
Definition: brin_bloom.c:132
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
#define SK_ISNULL
Definition: skey.h:115

References Assert, bloom_contains_value(), bloom_get_procinfo(), BloomEqualStrategyNumber, BrinValues::bv_values, DatumGetUInt32(), elog, ERROR, FunctionCall1Coll(), sort-test::key, PG_DETOAST_DATUM, PG_GET_COLLATION, PG_GETARG_INT32, PG_GETARG_POINTER, PG_RETURN_BOOL, PROCNUM_HASH, SK_ISNULL, and value.

◆ brin_bloom_get_ndistinct()

static int brin_bloom_get_ndistinct ( BrinDesc bdesc,
BloomOptions opts 
)
static

Definition at line 496 of file brin_bloom.c.

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}
uint32 BlockNumber
Definition: block.h:31
static bool BlockNumberIsValid(BlockNumber blockNumber)
Definition: block.h:71
#define BrinGetPagesPerRange(relation)
Definition: brin.h:40
#define BloomGetNDistinctPerRange(opts)
Definition: brin_bloom.c:195
#define BLOOM_MIN_NDISTINCT_PER_RANGE
Definition: brin_bloom.c:168
#define Min(x, y)
Definition: c.h:958
#define Max(x, y)
Definition: c.h:952
#define MaxHeapTuplesPerPage
Definition: htup_details.h:572

References Assert, BrinDesc::bd_index, BlockNumberIsValid(), BLOOM_MIN_NDISTINCT_PER_RANGE, BloomGetNDistinctPerRange, BrinGetPagesPerRange, Max, MaxHeapTuplesPerPage, Min, and opts.

Referenced by brin_bloom_add_value().

◆ brin_bloom_opcinfo()

Datum brin_bloom_opcinfo ( PG_FUNCTION_ARGS  )

Definition at line 449 of file brin_bloom.c.

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}
#define SizeofBrinOpcInfo(ncols)
Definition: brin_internal.h:41
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
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
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:386

References lookup_type_cache(), MAXALIGN, BrinOpcInfo::oi_nstored, BrinOpcInfo::oi_opaque, BrinOpcInfo::oi_regular_nulls, BrinOpcInfo::oi_typcache, palloc0(), PG_RETURN_POINTER, and SizeofBrinOpcInfo.

◆ brin_bloom_options()

Datum brin_bloom_options ( PG_FUNCTION_ARGS  )

Definition at line 744 of file brin_bloom.c.

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}
#define BLOOM_MAX_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:192
#define BLOOM_MIN_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:191
#define PG_RETURN_VOID()
Definition: fmgr.h:349
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

References add_local_real_reloption(), BLOOM_DEFAULT_FALSE_POSITIVE_RATE, BLOOM_DEFAULT_NDISTINCT_PER_RANGE, BLOOM_MAX_FALSE_POSITIVE_RATE, BLOOM_MIN_FALSE_POSITIVE_RATE, init_local_reloptions(), PG_GETARG_POINTER, and PG_RETURN_VOID.

◆ brin_bloom_summary_in()

Datum brin_bloom_summary_in ( PG_FUNCTION_ARGS  )

Definition at line 774 of file brin_bloom.c.

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}
int errcode(int sqlerrcode)
Definition: elog.c:853
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#define ereport(elevel,...)
Definition: elog.h:149

References ereport, errcode(), errmsg(), ERROR, and PG_RETURN_VOID.

◆ brin_bloom_summary_out()

Datum brin_bloom_summary_out ( PG_FUNCTION_ARGS  )

Definition at line 796 of file brin_bloom.c.

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}
#define PG_RETURN_CSTRING(x)
Definition: fmgr.h:362
const char * str
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

References appendStringInfo(), appendStringInfoChar(), initStringInfo(), BloomFilter::nbits, BloomFilter::nbits_set, BloomFilter::nhashes, PG_DETOAST_DATUM, PG_GETARG_DATUM, PG_RETURN_CSTRING, and str.

◆ brin_bloom_summary_recv()

Datum brin_bloom_summary_recv ( PG_FUNCTION_ARGS  )

Definition at line 820 of file brin_bloom.c.

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}

References ereport, errcode(), errmsg(), ERROR, and PG_RETURN_VOID.

◆ brin_bloom_summary_send()

Datum brin_bloom_summary_send ( PG_FUNCTION_ARGS  )

Definition at line 837 of file brin_bloom.c.

838{
839 return byteasend(fcinfo);
840}
Datum byteasend(PG_FUNCTION_ARGS)
Definition: varlena.c:490

References byteasend().

◆ brin_bloom_union()

Datum brin_bloom_union ( PG_FUNCTION_ARGS  )

Definition at line 666 of file brin_bloom.c.

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}
static uint64 pg_popcount(const char *buf, int bytes)
Definition: pg_bitutils.h:339

References Assert, BrinValues::bv_allnulls, BrinValues::bv_attno, BrinValues::bv_values, BloomFilter::data, i, BloomFilter::nbits, BloomFilter::nbits_set, BloomFilter::nhashes, PG_DETOAST_DATUM, PG_GETARG_POINTER, pg_popcount(), and PG_RETURN_VOID.