PostgreSQL Source Code  git master
brin_bloom.c File Reference
#include "postgres.h"
#include "access/genam.h"
#include "access/brin.h"
#include "access/brin_internal.h"
#include "access/brin_page.h"
#include "access/brin_tuple.h"
#include "access/hash.h"
#include "access/htup_details.h"
#include "access/reloptions.h"
#include "access/stratnum.h"
#include "catalog/pg_type.h"
#include "catalog/pg_amop.h"
#include "utils/builtins.h"
#include "utils/datum.h"
#include "utils/lsyscache.h"
#include "utils/rel.h"
#include "utils/syscache.h"
#include <math.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 197 of file brin_bloom.c.

◆ BLOOM_DEFAULT_NDISTINCT_PER_RANGE

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

Definition at line 179 of file brin_bloom.c.

◆ BLOOM_MAX_FALSE_POSITIVE_RATE

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

Definition at line 196 of file brin_bloom.c.

◆ BLOOM_MAX_PROCNUMS

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

Definition at line 145 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 195 of file brin_bloom.c.

◆ BLOOM_MIN_NDISTINCT_PER_RANGE

#define BLOOM_MIN_NDISTINCT_PER_RANGE   16

Definition at line 172 of file brin_bloom.c.

◆ BLOOM_SEED_1

#define BLOOM_SEED_1   0x71d924af

Definition at line 225 of file brin_bloom.c.

◆ BLOOM_SEED_2

#define BLOOM_SEED_2   0xba48b314

Definition at line 226 of file brin_bloom.c.

◆ BloomEqualStrategyNumber

#define BloomEqualStrategyNumber   1

Definition at line 136 of file brin_bloom.c.

◆ BloomGetFalsePositiveRate

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

Definition at line 204 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:179

Definition at line 199 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:213
#define MAXALIGN_DOWN(LEN)
Definition: c.h:812
#define MAXALIGN(LEN)
Definition: c.h:800

Definition at line 214 of file brin_bloom.c.

◆ PROCNUM_BASE

#define PROCNUM_BASE   11

Definition at line 152 of file brin_bloom.c.

◆ PROCNUM_HASH

#define PROCNUM_HASH   11 /* required */

Definition at line 146 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 374 of file brin_bloom.c.

375 {
376  int i;
377  uint64 h1,
378  h2;
379 
380  /* compute the hashes, used for the bloom filter */
383 
384  /* compute the requested number of hashes */
385  for (i = 0; i < filter->nhashes; i++)
386  {
387  /* h1 + h2 + f(i) */
388  uint32 h = (h1 + i * h2) % filter->nbits;
389  uint32 byte = (h / 8);
390  uint32 bit = (h % 8);
391 
392  /* if the bit is not set, set it and remember we did that */
393  if (!(filter->data[byte] & (0x01 << bit)))
394  {
395  filter->data[byte] |= (0x01 << bit);
396  filter->nbits_set++;
397  if (updated)
398  *updated = true;
399  }
400  }
401 
402  return filter;
403 }
#define BLOOM_SEED_1
Definition: brin_bloom.c:225
#define BLOOM_SEED_2
Definition: brin_bloom.c:226
unsigned int uint32
Definition: c.h:495
uint64 hash_bytes_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.c:631
static struct @148 value
int i
Definition: isn.c:73
uint8 nhashes
Definition: brin_bloom.c:254
char data[FLEXIBLE_ARRAY_MEMBER]
Definition: brin_bloom.c:259
uint32 nbits_set
Definition: brin_bloom.c:256
uint32 nbits
Definition: brin_bloom.c:255
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 411 of file brin_bloom.c.

412 {
413  int i;
414  uint64 h1,
415  h2;
416 
417  /* calculate the two hashes */
420 
421  /* compute the requested number of hashes */
422  for (i = 0; i < filter->nhashes; i++)
423  {
424  /* h1 + h2 + f(i) */
425  uint32 h = (h1 + i * h2) % filter->nbits;
426  uint32 byte = (h / 8);
427  uint32 bit = (h % 8);
428 
429  /* if the bit is not set, the value is not there */
430  if (!(filter->data[byte] & (0x01 << bit)))
431  return false;
432  }
433 
434  /* all hashes found in bloom filter */
435  return true;
436 }

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 274 of file brin_bloom.c.

276 {
277  double k;
278  int nbits,
279  nbytes;
280 
281  /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
282  nbits = ceil(-(ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
283 
284  /* round m to whole bytes */
285  nbytes = ((nbits + 7) / 8);
286  nbits = nbytes * 8;
287 
288  /*
289  * round(log(2.0) * m / ndistinct), but assume round() may not be
290  * available on Windows
291  */
292  k = log(2.0) * nbits / ndistinct;
293  k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
294 
295  if (nbytesp)
296  *nbytesp = nbytes;
297 
298  if (nbitsp)
299  *nbitsp = nbits;
300 
301  if (nhashesp)
302  *nhashesp = (int) k;
303 }

Referenced by bloom_init().

◆ bloom_get_procinfo()

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

Definition at line 708 of file brin_bloom.c.

709 {
710  BloomOpaque *opaque;
711  uint16 basenum = procnum - PROCNUM_BASE;
712 
713  /*
714  * We cache these in the opaque struct, to avoid repetitive syscache
715  * lookups.
716  */
717  opaque = (BloomOpaque *) bdesc->bd_info[attno - 1]->oi_opaque;
718 
719  /*
720  * If we already searched for this proc and didn't find it, don't bother
721  * searching again.
722  */
723  if (opaque->extra_proc_missing[basenum])
724  return NULL;
725 
726  if (opaque->extra_procinfos[basenum].fn_oid == InvalidOid)
727  {
728  if (RegProcedureIsValid(index_getprocid(bdesc->bd_index, attno,
729  procnum)))
730  {
731  fmgr_info_copy(&opaque->extra_procinfos[basenum],
732  index_getprocinfo(bdesc->bd_index, attno, procnum),
733  bdesc->bd_context);
734  }
735  else
736  {
737  opaque->extra_proc_missing[basenum] = true;
738  return NULL;
739  }
740  }
741 
742  return &opaque->extra_procinfos[basenum];
743 }
#define PROCNUM_BASE
Definition: brin_bloom.c:152
unsigned short uint16
Definition: c.h:494
#define RegProcedureIsValid(p)
Definition: c.h:766
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:811
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:777
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
#define InvalidOid
Definition: postgres_ext.h:36
FmgrInfo extra_procinfos[BLOOM_MAX_PROCNUMS]
Definition: brin_bloom.c:445
bool extra_proc_missing[BLOOM_MAX_PROCNUMS]
Definition: brin_bloom.c:446
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 313 of file brin_bloom.c.

314 {
315  Size len;
316  BloomFilter *filter;
317 
318  int nbits; /* size of filter / number of bits */
319  int nbytes; /* size of filter / number of bytes */
320  int nhashes; /* number of hash functions */
321 
322  Assert(ndistinct > 0);
323  Assert((false_positive_rate >= BLOOM_MIN_FALSE_POSITIVE_RATE) &&
324  (false_positive_rate < BLOOM_MAX_FALSE_POSITIVE_RATE));
325 
326  /* calculate bloom filter size / parameters */
327  bloom_filter_size(ndistinct, false_positive_rate,
328  &nbytes, &nbits, &nhashes);
329 
330  /*
331  * Reject filters that are obviously too large to store on a page.
332  *
333  * Initially the bloom filter is just zeroes and so very compressible, but
334  * as we add values it gets more and more random, and so less and less
335  * compressible. So initially everything fits on the page, but we might
336  * get surprising failures later - we want to prevent that, so we reject
337  * bloom filter that are obviously too large.
338  *
339  * XXX It's not uncommon to oversize the bloom filter a bit, to defend
340  * against unexpected data anomalies (parts of table with more distinct
341  * values per range etc.). But we still need to make sure even the
342  * oversized filter fits on page, if such need arises.
343  *
344  * XXX This check is not perfect, because the index may have multiple
345  * filters that are small individually, but too large when combined.
346  */
347  if (nbytes > BloomMaxFilterSize)
348  elog(ERROR, "the bloom filter is too large (%d > %zu)", nbytes,
350 
351  /*
352  * We allocate the whole filter. Most of it is going to be 0 bits, so the
353  * varlena is easy to compress.
354  */
355  len = offsetof(BloomFilter, data) + nbytes;
356 
357  filter = (BloomFilter *) palloc0(len);
358 
359  filter->flags = 0;
360  filter->nhashes = nhashes;
361  filter->nbits = nbits;
362 
363  SET_VARSIZE(filter, len);
364 
365  return filter;
366 }
static void bloom_filter_size(int ndistinct, double false_positive_rate, int *nbytesp, int *nbitsp, int *nhashesp)
Definition: brin_bloom.c:274
#define BLOOM_MAX_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:196
#define BloomMaxFilterSize
Definition: brin_bloom.c:214
#define BLOOM_MIN_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:195
size_t Size
Definition: c.h:594
#define ERROR
Definition: elog.h:39
Assert(fmt[strlen(fmt) - 1] !='\n')
void * palloc0(Size size)
Definition: mcxt.c:1257
const void size_t len
const void * data
uint16 flags
Definition: brin_bloom.c:251
#define SET_VARSIZE(PTR, len)
Definition: varatt.h:305

References Assert(), bloom_filter_size(), BLOOM_MAX_FALSE_POSITIVE_RATE, BLOOM_MIN_FALSE_POSITIVE_RATE, 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 544 of file brin_bloom.c.

545 {
546  BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0);
547  BrinValues *column = (BrinValues *) PG_GETARG_POINTER(1);
549  bool isnull PG_USED_FOR_ASSERTS_ONLY = PG_GETARG_DATUM(3);
551  Oid colloid = PG_GET_COLLATION();
552  FmgrInfo *hashFn;
553  uint32 hashValue;
554  bool updated = false;
555  AttrNumber attno;
556  BloomFilter *filter;
557 
558  Assert(!isnull);
559 
560  attno = column->bv_attno;
561 
562  /*
563  * If this is the first non-null value, we need to initialize the bloom
564  * filter. Otherwise just extract the existing bloom filter from
565  * BrinValues.
566  */
567  if (column->bv_allnulls)
568  {
569  filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
571  column->bv_values[0] = PointerGetDatum(filter);
572  column->bv_allnulls = false;
573  updated = true;
574  }
575  else
576  filter = (BloomFilter *) PG_DETOAST_DATUM(column->bv_values[0]);
577 
578  /*
579  * Compute the hash of the new value, using the supplied hash function,
580  * and then add the hash value to the bloom filter.
581  */
582  hashFn = bloom_get_procinfo(bdesc, attno, PROCNUM_HASH);
583 
584  hashValue = DatumGetUInt32(FunctionCall1Coll(hashFn, colloid, newval));
585 
586  filter = bloom_add_value(filter, hashValue, &updated);
587 
588  column->bv_values[0] = PointerGetDatum(filter);
589 
590  PG_RETURN_BOOL(updated);
591 }
int16 AttrNumber
Definition: attnum.h:21
static int brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
Definition: brin_bloom.c:501
#define PROCNUM_HASH
Definition: brin_bloom.c:146
static BloomFilter * bloom_init(int ndistinct, double false_positive_rate)
Definition: brin_bloom.c:313
#define BloomGetFalsePositiveRate(opts)
Definition: brin_bloom.c:204
static BloomFilter * bloom_add_value(BloomFilter *filter, uint32 value, bool *updated)
Definition: brin_bloom.c:374
static FmgrInfo * bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
Definition: brin_bloom.c:708
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:171
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
Definition: fmgr.c:1112
#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 599 of file brin_bloom.c.

600 {
601  BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0);
602  BrinValues *column = (BrinValues *) PG_GETARG_POINTER(1);
603  ScanKey *keys = (ScanKey *) PG_GETARG_POINTER(2);
604  int nkeys = PG_GETARG_INT32(3);
605  Oid colloid = PG_GET_COLLATION();
606  AttrNumber attno;
607  Datum value;
608  bool matches;
609  FmgrInfo *finfo;
610  uint32 hashValue;
611  BloomFilter *filter;
612  int keyno;
613 
614  filter = (BloomFilter *) PG_DETOAST_DATUM(column->bv_values[0]);
615 
616  Assert(filter);
617 
618  /*
619  * Assume all scan keys match. We'll be searching for a scan key
620  * eliminating the page range (we can stop on the first such key).
621  */
622  matches = true;
623 
624  for (keyno = 0; keyno < nkeys; keyno++)
625  {
626  ScanKey key = keys[keyno];
627 
628  /* NULL keys are handled and filtered-out in bringetbitmap */
629  Assert(!(key->sk_flags & SK_ISNULL));
630 
631  attno = key->sk_attno;
632  value = key->sk_argument;
633 
634  switch (key->sk_strategy)
635  {
637 
638  /*
639  * We want to return the current page range if the bloom
640  * filter seems to contain the value.
641  */
642  finfo = bloom_get_procinfo(bdesc, attno, PROCNUM_HASH);
643 
644  hashValue = DatumGetUInt32(FunctionCall1Coll(finfo, colloid, value));
645  matches &= bloom_contains_value(filter, hashValue);
646 
647  break;
648  default:
649  /* shouldn't happen */
650  elog(ERROR, "invalid strategy number %d", key->sk_strategy);
651  matches = false;
652  break;
653  }
654 
655  if (!matches)
656  break;
657  }
658 
659  PG_RETURN_BOOL(matches);
660 }
static bool bloom_contains_value(BloomFilter *filter, uint32 value)
Definition: brin_bloom.c:411
#define BloomEqualStrategyNumber
Definition: brin_bloom.c:136
#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 501 of file brin_bloom.c.

502 {
503  double ndistinct;
504  double maxtuples;
505  BlockNumber pagesPerRange;
506 
507  pagesPerRange = BrinGetPagesPerRange(bdesc->bd_index);
508  ndistinct = BloomGetNDistinctPerRange(opts);
509 
510  Assert(BlockNumberIsValid(pagesPerRange));
511 
512  maxtuples = MaxHeapTuplesPerPage * pagesPerRange;
513 
514  /*
515  * Similarly to n_distinct, negative values are relative - in this case to
516  * maximum number of tuples in the page range (maxtuples).
517  */
518  if (ndistinct < 0)
519  ndistinct = (-ndistinct) * maxtuples;
520 
521  /*
522  * Positive values are to be used directly, but we still apply a couple of
523  * safeties to avoid using unreasonably small bloom filters.
524  */
525  ndistinct = Max(ndistinct, BLOOM_MIN_NDISTINCT_PER_RANGE);
526 
527  /*
528  * And don't use more than the maximum possible number of tuples, in the
529  * range, which would be entirely wasteful.
530  */
531  ndistinct = Min(ndistinct, maxtuples);
532 
533  return (int) ndistinct;
534 }
uint32 BlockNumber
Definition: block.h:31
static bool BlockNumberIsValid(BlockNumber blockNumber)
Definition: block.h:71
#define BrinGetPagesPerRange(relation)
Definition: brin.h:39
#define BloomGetNDistinctPerRange(opts)
Definition: brin_bloom.c:199
#define BLOOM_MIN_NDISTINCT_PER_RANGE
Definition: brin_bloom.c:172
#define Min(x, y)
Definition: c.h:993
#define Max(x, y)
Definition: c.h:987
#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 454 of file brin_bloom.c.

455 {
456  BrinOpcInfo *result;
457 
458  /*
459  * opaque->strategy_procinfos is initialized lazily; here it is set to
460  * all-uninitialized by palloc0 which sets fn_oid to InvalidOid.
461  *
462  * bloom indexes only store the filter as a single BYTEA column
463  */
464 
465  result = palloc0(MAXALIGN(SizeofBrinOpcInfo(1)) +
466  sizeof(BloomOpaque));
467  result->oi_nstored = 1;
468  result->oi_regular_nulls = true;
469  result->oi_opaque = (BloomOpaque *)
470  MAXALIGN((char *) result + SizeofBrinOpcInfo(1));
471  result->oi_typcache[0] = lookup_type_cache(PG_BRIN_BLOOM_SUMMARYOID, 0);
472 
473  PG_RETURN_POINTER(result);
474 }
#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:344

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 746 of file brin_bloom.c.

747 {
749 
750  init_local_reloptions(relopts, sizeof(BloomOptions));
751 
752  add_local_real_reloption(relopts, "n_distinct_per_range",
753  "number of distinct items expected in a BRIN page range",
755  -1.0, INT_MAX, offsetof(BloomOptions, nDistinctPerRange));
756 
757  add_local_real_reloption(relopts, "false_positive_rate",
758  "desired false-positive rate for the bloom filters",
762  offsetof(BloomOptions, falsePositiveRate));
763 
764  PG_RETURN_VOID();
765 }
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:197
#define PG_RETURN_VOID()
Definition: fmgr.h:349
void init_local_reloptions(local_relopts *relopts, Size relopt_struct_size)
Definition: reloptions.c:736
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:974

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 776 of file brin_bloom.c.

777 {
778  /*
779  * brin_bloom_summary stores the data in binary form and parsing text
780  * input is not needed, so disallow this.
781  */
782  ereport(ERROR,
783  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
784  errmsg("cannot accept a value of type %s", "pg_brin_bloom_summary")));
785 
786  PG_RETURN_VOID(); /* keep compiler quiet */
787 }
int errcode(int sqlerrcode)
Definition: elog.c:858
int errmsg(const char *fmt,...)
Definition: elog.c:1069
#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 798 of file brin_bloom.c.

799 {
800  BloomFilter *filter;
802 
803  /* detoast the data to get value with a full 4B header */
805 
807  appendStringInfoChar(&str, '{');
808 
809  appendStringInfo(&str, "mode: hashed nhashes: %u nbits: %u nbits_set: %u",
810  filter->nhashes, filter->nbits, filter->nbits_set);
811 
812  appendStringInfoChar(&str, '}');
813 
814  PG_RETURN_CSTRING(str.data);
815 }
#define PG_RETURN_CSTRING(x)
Definition: fmgr.h:362
#define PG_DETOAST_DATUM_PACKED(datum)
Definition: fmgr.h:248
void appendStringInfo(StringInfo str, const char *fmt,...)
Definition: stringinfo.c:91
void appendStringInfoChar(StringInfo str, char ch)
Definition: stringinfo.c:188
void initStringInfo(StringInfo str)
Definition: stringinfo.c:59

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

◆ brin_bloom_summary_recv()

Datum brin_bloom_summary_recv ( PG_FUNCTION_ARGS  )

Definition at line 822 of file brin_bloom.c.

823 {
824  ereport(ERROR,
825  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
826  errmsg("cannot accept a value of type %s", "pg_brin_bloom_summary")));
827 
828  PG_RETURN_VOID(); /* keep compiler quiet */
829 }

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

◆ brin_bloom_summary_send()

Datum brin_bloom_summary_send ( PG_FUNCTION_ARGS  )

Definition at line 839 of file brin_bloom.c.

840 {
841  return byteasend(fcinfo);
842 }
Datum byteasend(PG_FUNCTION_ARGS)
Definition: varlena.c:488

References byteasend().

◆ brin_bloom_union()

Datum brin_bloom_union ( PG_FUNCTION_ARGS  )

Definition at line 671 of file brin_bloom.c.

672 {
673  int i;
674  int nbytes;
675  BrinValues *col_a = (BrinValues *) PG_GETARG_POINTER(1);
676  BrinValues *col_b = (BrinValues *) PG_GETARG_POINTER(2);
677  BloomFilter *filter_a;
678  BloomFilter *filter_b;
679 
680  Assert(col_a->bv_attno == col_b->bv_attno);
681  Assert(!col_a->bv_allnulls && !col_b->bv_allnulls);
682 
683  filter_a = (BloomFilter *) PG_DETOAST_DATUM(col_a->bv_values[0]);
684  filter_b = (BloomFilter *) PG_DETOAST_DATUM(col_b->bv_values[0]);
685 
686  /* make sure the filters use the same parameters */
687  Assert(filter_a && filter_b);
688  Assert(filter_a->nbits == filter_b->nbits);
689  Assert(filter_a->nhashes == filter_b->nhashes);
690  Assert((filter_a->nbits > 0) && (filter_a->nbits % 8 == 0));
691 
692  nbytes = (filter_a->nbits) / 8;
693 
694  /* simply OR the bitmaps */
695  for (i = 0; i < nbytes; i++)
696  filter_a->data[i] |= filter_b->data[i];
697 
698  PG_RETURN_VOID();
699 }

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