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 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.

Referenced by brin_bloom_options().

◆ 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.

Referenced by brin_bloom_options().

◆ 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.

Referenced by bloom_init(), and brin_bloom_options().

◆ 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.

Referenced by bloom_init(), and brin_bloom_options().

◆ BLOOM_MIN_NDISTINCT_PER_RANGE

#define BLOOM_MIN_NDISTINCT_PER_RANGE   16

Definition at line 172 of file brin_bloom.c.

Referenced by brin_bloom_get_ndistinct().

◆ BLOOM_SEED_1

#define BLOOM_SEED_1   0x71d924af

Definition at line 225 of file brin_bloom.c.

Referenced by bloom_add_value(), and bloom_contains_value().

◆ BLOOM_SEED_2

#define BLOOM_SEED_2   0xba48b314

Definition at line 226 of file brin_bloom.c.

Referenced by bloom_add_value(), and bloom_contains_value().

◆ BloomEqualStrategyNumber

#define BloomEqualStrategyNumber   1

Definition at line 136 of file brin_bloom.c.

Referenced by brin_bloom_consistent().

◆ 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.

Referenced by brin_bloom_add_value().

◆ BloomGetNDistinctPerRange

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

Definition at line 199 of file brin_bloom.c.

Referenced by brin_bloom_get_ndistinct().

◆ BloomMaxFilterSize

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

Definition at line 214 of file brin_bloom.c.

Referenced by bloom_init().

◆ PROCNUM_BASE

#define PROCNUM_BASE   11

Definition at line 152 of file brin_bloom.c.

Referenced by bloom_get_procinfo().

◆ PROCNUM_HASH

#define PROCNUM_HASH   11 /* required */

Definition at line 146 of file brin_bloom.c.

Referenced by brin_bloom_add_value(), and brin_bloom_consistent().

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

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

Referenced by brin_bloom_add_value().

345 {
346  int i;
347  uint64 h1,
348  h2;
349 
350  /* compute the hashes, used for the bloom filter */
353 
354  /* compute the requested number of hashes */
355  for (i = 0; i < filter->nhashes; i++)
356  {
357  /* h1 + h2 + f(i) */
358  uint32 h = (h1 + i * h2) % filter->nbits;
359  uint32 byte = (h / 8);
360  uint32 bit = (h % 8);
361 
362  /* if the bit is not set, set it and remember we did that */
363  if (!(filter->data[byte] & (0x01 << bit)))
364  {
365  filter->data[byte] |= (0x01 << bit);
366  filter->nbits_set++;
367  if (updated)
368  *updated = true;
369  }
370  }
371 
372  return filter;
373 }
uint64 hash_bytes_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.c:631
char data[FLEXIBLE_ARRAY_MEMBER]
Definition: brin_bloom.c:259
uint32 nbits_set
Definition: brin_bloom.c:256
uint8 nhashes
Definition: brin_bloom.c:254
#define BLOOM_SEED_2
Definition: brin_bloom.c:226
unsigned int uint32
Definition: c.h:441
#define byte(x, n)
Definition: rijndael.c:68
uint32 nbits
Definition: brin_bloom.c:255
static struct @143 value
Datum bit(PG_FUNCTION_ARGS)
Definition: varbit.c:391
int i
#define BLOOM_SEED_1
Definition: brin_bloom.c:225

◆ bloom_contains_value()

static bool bloom_contains_value ( BloomFilter filter,
uint32  value 
)
static

Definition at line 381 of file brin_bloom.c.

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

Referenced by brin_bloom_consistent().

382 {
383  int i;
384  uint64 h1,
385  h2;
386 
387  /* calculate the two hashes */
390 
391  /* compute the requested number of hashes */
392  for (i = 0; i < filter->nhashes; i++)
393  {
394  /* h1 + h2 + f(i) */
395  uint32 h = (h1 + i * h2) % filter->nbits;
396  uint32 byte = (h / 8);
397  uint32 bit = (h % 8);
398 
399  /* if the bit is not set, the value is not there */
400  if (!(filter->data[byte] & (0x01 << bit)))
401  return false;
402  }
403 
404  /* all hashes found in bloom filter */
405  return true;
406 }
uint64 hash_bytes_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.c:631
char data[FLEXIBLE_ARRAY_MEMBER]
Definition: brin_bloom.c:259
uint8 nhashes
Definition: brin_bloom.c:254
#define BLOOM_SEED_2
Definition: brin_bloom.c:226
unsigned int uint32
Definition: c.h:441
#define byte(x, n)
Definition: rijndael.c:68
uint32 nbits
Definition: brin_bloom.c:255
static struct @143 value
Datum bit(PG_FUNCTION_ARGS)
Definition: varbit.c:391
int i
#define BLOOM_SEED_1
Definition: brin_bloom.c:225

◆ bloom_get_procinfo()

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

Definition at line 675 of file brin_bloom.c.

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

Referenced by brin_bloom_add_value(), and brin_bloom_consistent().

676 {
677  BloomOpaque *opaque;
678  uint16 basenum = procnum - PROCNUM_BASE;
679 
680  /*
681  * We cache these in the opaque struct, to avoid repetitive syscache
682  * lookups.
683  */
684  opaque = (BloomOpaque *) bdesc->bd_info[attno - 1]->oi_opaque;
685 
686  /*
687  * If we already searched for this proc and didn't find it, don't bother
688  * searching again.
689  */
690  if (opaque->extra_proc_missing[basenum])
691  return NULL;
692 
693  if (opaque->extra_procinfos[basenum].fn_oid == InvalidOid)
694  {
695  if (RegProcedureIsValid(index_getprocid(bdesc->bd_index, attno,
696  procnum)))
697  {
698  fmgr_info_copy(&opaque->extra_procinfos[basenum],
699  index_getprocinfo(bdesc->bd_index, attno, procnum),
700  bdesc->bd_context);
701  }
702  else
703  {
704  opaque->extra_proc_missing[basenum] = true;
705  return NULL;
706  }
707  }
708 
709  return &opaque->extra_procinfos[basenum];
710 }
#define PROCNUM_BASE
Definition: brin_bloom.c:152
FmgrInfo * index_getprocinfo(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:803
unsigned short uint16
Definition: c.h:440
Relation bd_index
Definition: brin_internal.h:50
void fmgr_info_copy(FmgrInfo *dstinfo, FmgrInfo *srcinfo, MemoryContext destcxt)
Definition: fmgr.c:608
#define RegProcedureIsValid(p)
Definition: c.h:712
FmgrInfo extra_procinfos[BLOOM_MAX_PROCNUMS]
Definition: brin_bloom.c:415
void * oi_opaque
Definition: brin_internal.h:34
BrinOpcInfo * bd_info[FLEXIBLE_ARRAY_MEMBER]
Definition: brin_internal.h:62
#define InvalidOid
Definition: postgres_ext.h:36
Oid fn_oid
Definition: fmgr.h:59
MemoryContext bd_context
Definition: brin_internal.h:47
bool extra_proc_missing[BLOOM_MAX_PROCNUMS]
Definition: brin_bloom.c:416
RegProcedure index_getprocid(Relation irel, AttrNumber attnum, uint16 procnum)
Definition: indexam.c:769

◆ bloom_init()

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

Definition at line 272 of file brin_bloom.c.

References Assert, BLOOM_MAX_FALSE_POSITIVE_RATE, BLOOM_MIN_FALSE_POSITIVE_RATE, BloomMaxFilterSize, elog, ERROR, BloomFilter::flags, BloomFilter::nbits, BloomFilter::nhashes, offsetof, palloc0(), and SET_VARSIZE.

Referenced by brin_bloom_add_value().

273 {
274  Size len;
275  BloomFilter *filter;
276 
277  int nbits; /* size of filter / number of bits */
278  int nbytes; /* size of filter / number of bytes */
279 
280  double k; /* number of hash functions */
281 
282  Assert(ndistinct > 0);
283  Assert((false_positive_rate >= BLOOM_MIN_FALSE_POSITIVE_RATE) &&
284  (false_positive_rate < BLOOM_MAX_FALSE_POSITIVE_RATE));
285 
286  /* sizing bloom filter: -(n * ln(p)) / (ln(2))^2 */
287  nbits = ceil(-(ndistinct * log(false_positive_rate)) / pow(log(2.0), 2));
288 
289  /* round m to whole bytes */
290  nbytes = ((nbits + 7) / 8);
291  nbits = nbytes * 8;
292 
293  /*
294  * Reject filters that are obviously too large to store on a page.
295  *
296  * Initially the bloom filter is just zeroes and so very compressible, but
297  * as we add values it gets more and more random, and so less and less
298  * compressible. So initially everything fits on the page, but we might
299  * get surprising failures later - we want to prevent that, so we reject
300  * bloom filter that are obviously too large.
301  *
302  * XXX It's not uncommon to oversize the bloom filter a bit, to defend
303  * against unexpected data anomalies (parts of table with more distinct
304  * values per range etc.). But we still need to make sure even the
305  * oversized filter fits on page, if such need arises.
306  *
307  * XXX This check is not perfect, because the index may have multiple
308  * filters that are small individually, but too large when combined.
309  */
310  if (nbytes > BloomMaxFilterSize)
311  elog(ERROR, "the bloom filter is too large (%d > %zu)", nbytes,
313 
314  /*
315  * round(log(2.0) * m / ndistinct), but assume round() may not be
316  * available on Windows
317  */
318  k = log(2.0) * nbits / ndistinct;
319  k = (k - floor(k) >= 0.5) ? ceil(k) : floor(k);
320 
321  /*
322  * We allocate the whole filter. Most of it is going to be 0 bits, so the
323  * varlena is easy to compress.
324  */
325  len = offsetof(BloomFilter, data) + nbytes;
326 
327  filter = (BloomFilter *) palloc0(len);
328 
329  filter->flags = 0;
330  filter->nhashes = (int) k;
331  filter->nbits = nbits;
332 
333  SET_VARSIZE(filter, len);
334 
335  return filter;
336 }
#define BLOOM_MIN_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:195
#define ERROR
Definition: elog.h:46
uint8 nhashes
Definition: brin_bloom.c:254
uint16 flags
Definition: brin_bloom.c:251
#define BLOOM_MAX_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:196
void * palloc0(Size size)
Definition: mcxt.c:1093
uint32 nbits
Definition: brin_bloom.c:255
#define Assert(condition)
Definition: c.h:804
size_t Size
Definition: c.h:540
#define elog(elevel,...)
Definition: elog.h:232
#define SET_VARSIZE(PTR, len)
Definition: postgres.h:342
#define BloomMaxFilterSize
Definition: brin_bloom.c:214
#define offsetof(type, field)
Definition: c.h:727

◆ brin_bloom_add_value()

Datum brin_bloom_add_value ( PG_FUNCTION_ARGS  )

Definition at line 514 of file brin_bloom.c.

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.

515 {
516  BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0);
517  BrinValues *column = (BrinValues *) PG_GETARG_POINTER(1);
519  bool isnull PG_USED_FOR_ASSERTS_ONLY = PG_GETARG_DATUM(3);
521  Oid colloid = PG_GET_COLLATION();
522  FmgrInfo *hashFn;
523  uint32 hashValue;
524  bool updated = false;
525  AttrNumber attno;
526  BloomFilter *filter;
527 
528  Assert(!isnull);
529 
530  attno = column->bv_attno;
531 
532  /*
533  * If this is the first non-null value, we need to initialize the bloom
534  * filter. Otherwise just extract the existing bloom filter from
535  * BrinValues.
536  */
537  if (column->bv_allnulls)
538  {
539  filter = bloom_init(brin_bloom_get_ndistinct(bdesc, opts),
541  column->bv_values[0] = PointerGetDatum(filter);
542  column->bv_allnulls = false;
543  updated = true;
544  }
545  else
546  filter = (BloomFilter *) PG_DETOAST_DATUM(column->bv_values[0]);
547 
548  /*
549  * Compute the hash of the new value, using the supplied hash function,
550  * and then add the hash value to the bloom filter.
551  */
552  hashFn = bloom_get_procinfo(bdesc, attno, PROCNUM_HASH);
553 
554  hashValue = DatumGetUInt32(FunctionCall1Coll(hashFn, colloid, newval));
555 
556  filter = bloom_add_value(filter, hashValue, &updated);
557 
558  column->bv_values[0] = PointerGetDatum(filter);
559 
560  PG_RETURN_BOOL(updated);
561 }
#define DatumGetUInt32(X)
Definition: postgres.h:530
static BloomFilter * bloom_init(int ndistinct, double false_positive_rate)
Definition: brin_bloom.c:272
Definition: fmgr.h:56
#define PointerGetDatum(X)
Definition: postgres.h:600
#define PG_GETARG_DATUM(n)
Definition: fmgr.h:268
bool bv_allnulls
Definition: brin_tuple.h:33
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
static BloomFilter * bloom_add_value(BloomFilter *filter, uint32 value, bool *updated)
Definition: brin_bloom.c:344
unsigned int Oid
Definition: postgres_ext.h:31
#define PG_GET_COLLATION()
Definition: fmgr.h:198
#define PG_GET_OPCLASS_OPTIONS()
Definition: fmgr.h:342
#define BloomGetFalsePositiveRate(opts)
Definition: brin_bloom.c:204
AttrNumber bv_attno
Definition: brin_tuple.h:31
unsigned int uint32
Definition: c.h:441
static int brin_bloom_get_ndistinct(BrinDesc *bdesc, BloomOptions *opts)
Definition: brin_bloom.c:471
static AmcheckOptions opts
Definition: pg_amcheck.c:110
static FmgrInfo * bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
Definition: brin_bloom.c:675
#define PG_RETURN_BOOL(x)
Definition: fmgr.h:359
uintptr_t Datum
Definition: postgres.h:411
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
Definition: fmgr.c:1128
#define Assert(condition)
Definition: c.h:804
#define newval
#define PROCNUM_HASH
Definition: brin_bloom.c:146
#define PG_DETOAST_DATUM(datum)
Definition: fmgr.h:240
Datum * bv_values
Definition: brin_tuple.h:34
int16 AttrNumber
Definition: attnum.h:21
#define PG_USED_FOR_ASSERTS_ONLY
Definition: c.h:155

◆ brin_bloom_consistent()

Datum brin_bloom_consistent ( PG_FUNCTION_ARGS  )

Definition at line 569 of file brin_bloom.c.

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_DATUM, PROCNUM_HASH, ScanKeyData::sk_argument, ScanKeyData::sk_attno, ScanKeyData::sk_flags, SK_ISNULL, ScanKeyData::sk_strategy, and value.

570 {
571  BrinDesc *bdesc = (BrinDesc *) PG_GETARG_POINTER(0);
572  BrinValues *column = (BrinValues *) PG_GETARG_POINTER(1);
573  ScanKey *keys = (ScanKey *) PG_GETARG_POINTER(2);
574  int nkeys = PG_GETARG_INT32(3);
575  Oid colloid = PG_GET_COLLATION();
576  AttrNumber attno;
577  Datum value;
578  Datum matches;
579  FmgrInfo *finfo;
580  uint32 hashValue;
581  BloomFilter *filter;
582  int keyno;
583 
584  filter = (BloomFilter *) PG_DETOAST_DATUM(column->bv_values[0]);
585 
586  Assert(filter);
587 
588  matches = true;
589 
590  for (keyno = 0; keyno < nkeys; keyno++)
591  {
592  ScanKey key = keys[keyno];
593 
594  /* NULL keys are handled and filtered-out in bringetbitmap */
595  Assert(!(key->sk_flags & SK_ISNULL));
596 
597  attno = key->sk_attno;
598  value = key->sk_argument;
599 
600  switch (key->sk_strategy)
601  {
603 
604  /*
605  * In the equality case (WHERE col = someval), we want to
606  * return the current page range if the minimum value in the
607  * range <= scan key, and the maximum value >= scan key.
608  */
609  finfo = bloom_get_procinfo(bdesc, attno, PROCNUM_HASH);
610 
611  hashValue = DatumGetUInt32(FunctionCall1Coll(finfo, colloid, value));
612  matches &= bloom_contains_value(filter, hashValue);
613 
614  break;
615  default:
616  /* shouldn't happen */
617  elog(ERROR, "invalid strategy number %d", key->sk_strategy);
618  matches = 0;
619  break;
620  }
621 
622  if (!matches)
623  break;
624  }
625 
626  PG_RETURN_DATUM(matches);
627 }
#define DatumGetUInt32(X)
Definition: postgres.h:530
#define PG_GETARG_INT32(n)
Definition: fmgr.h:269
static bool bloom_contains_value(BloomFilter *filter, uint32 value)
Definition: brin_bloom.c:381
Definition: fmgr.h:56
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
unsigned int Oid
Definition: postgres_ext.h:31
#define PG_GET_COLLATION()
Definition: fmgr.h:198
#define ERROR
Definition: elog.h:46
StrategyNumber sk_strategy
Definition: skey.h:68
unsigned int uint32
Definition: c.h:441
#define SK_ISNULL
Definition: skey.h:115
#define BloomEqualStrategyNumber
Definition: brin_bloom.c:136
static FmgrInfo * bloom_get_procinfo(BrinDesc *bdesc, uint16 attno, uint16 procnum)
Definition: brin_bloom.c:675
uintptr_t Datum
Definition: postgres.h:411
#define PG_RETURN_DATUM(x)
Definition: fmgr.h:353
Datum FunctionCall1Coll(FmgrInfo *flinfo, Oid collation, Datum arg1)
Definition: fmgr.c:1128
static struct @143 value
int sk_flags
Definition: skey.h:66
#define Assert(condition)
Definition: c.h:804
#define PROCNUM_HASH
Definition: brin_bloom.c:146
#define elog(elevel,...)
Definition: elog.h:232
#define PG_DETOAST_DATUM(datum)
Definition: fmgr.h:240
Datum * bv_values
Definition: brin_tuple.h:34
Datum sk_argument
Definition: skey.h:72
int16 AttrNumber
Definition: attnum.h:21
AttrNumber sk_attno
Definition: skey.h:67

◆ brin_bloom_get_ndistinct()

static int brin_bloom_get_ndistinct ( BrinDesc bdesc,
BloomOptions opts 
)
static

Definition at line 471 of file brin_bloom.c.

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

Referenced by brin_bloom_add_value().

472 {
473  double ndistinct;
474  double maxtuples;
475  BlockNumber pagesPerRange;
476 
477  pagesPerRange = BrinGetPagesPerRange(bdesc->bd_index);
478  ndistinct = BloomGetNDistinctPerRange(opts);
479 
480  Assert(BlockNumberIsValid(pagesPerRange));
481 
482  maxtuples = MaxHeapTuplesPerPage * pagesPerRange;
483 
484  /*
485  * Similarly to n_distinct, negative values are relative - in this case to
486  * maximum number of tuples in the page range (maxtuples).
487  */
488  if (ndistinct < 0)
489  ndistinct = (-ndistinct) * maxtuples;
490 
491  /*
492  * Positive values are to be used directly, but we still apply a couple of
493  * safeties to avoid using unreasonably small bloom filters.
494  */
495  ndistinct = Max(ndistinct, BLOOM_MIN_NDISTINCT_PER_RANGE);
496 
497  /*
498  * And don't use more than the maximum possible number of tuples, in the
499  * range, which would be entirely wasteful.
500  */
501  ndistinct = Min(ndistinct, maxtuples);
502 
503  return (int) ndistinct;
504 }
#define BLOOM_MIN_NDISTINCT_PER_RANGE
Definition: brin_bloom.c:172
#define Min(x, y)
Definition: c.h:986
#define MaxHeapTuplesPerPage
Definition: htup_details.h:573
uint32 BlockNumber
Definition: block.h:31
#define BrinGetPagesPerRange(relation)
Definition: brin.h:39
Relation bd_index
Definition: brin_internal.h:50
#define BlockNumberIsValid(blockNumber)
Definition: block.h:70
#define Max(x, y)
Definition: c.h:980
#define Assert(condition)
Definition: c.h:804
#define BloomGetNDistinctPerRange(opts)
Definition: brin_bloom.c:199

◆ brin_bloom_opcinfo()

Datum brin_bloom_opcinfo ( PG_FUNCTION_ARGS  )

Definition at line 424 of file brin_bloom.c.

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

425 {
426  BrinOpcInfo *result;
427 
428  /*
429  * opaque->strategy_procinfos is initialized lazily; here it is set to
430  * all-uninitialized by palloc0 which sets fn_oid to InvalidOid.
431  *
432  * bloom indexes only store the filter as a single BYTEA column
433  */
434 
435  result = palloc0(MAXALIGN(SizeofBrinOpcInfo(1)) +
436  sizeof(BloomOpaque));
437  result->oi_nstored = 1;
438  result->oi_regular_nulls = true;
439  result->oi_opaque = (BloomOpaque *)
440  MAXALIGN((char *) result + SizeofBrinOpcInfo(1));
441  result->oi_typcache[0] = lookup_type_cache(PG_BRIN_BLOOM_SUMMARYOID, 0);
442 
443  PG_RETURN_POINTER(result);
444 }
#define PG_RETURN_POINTER(x)
Definition: fmgr.h:361
#define SizeofBrinOpcInfo(ncols)
Definition: brin_internal.h:41
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 * palloc0(Size size)
Definition: mcxt.c:1093
void * oi_opaque
Definition: brin_internal.h:34
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
Definition: typcache.c:339
#define MAXALIGN(LEN)
Definition: c.h:757

◆ brin_bloom_options()

Datum brin_bloom_options ( PG_FUNCTION_ARGS  )

Definition at line 713 of file brin_bloom.c.

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, BloomOptions::falsePositiveRate, init_local_reloptions(), BloomOptions::nDistinctPerRange, offsetof, PG_GETARG_POINTER, and PG_RETURN_VOID.

714 {
716 
717  init_local_reloptions(relopts, sizeof(BloomOptions));
718 
719  add_local_real_reloption(relopts, "n_distinct_per_range",
720  "number of distinct items expected in a BRIN page range",
722  -1.0, INT_MAX, offsetof(BloomOptions, nDistinctPerRange));
723 
724  add_local_real_reloption(relopts, "false_positive_rate",
725  "desired false-positive rate for the bloom filters",
729  offsetof(BloomOptions, falsePositiveRate));
730 
731  PG_RETURN_VOID();
732 }
#define BLOOM_MIN_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:195
void init_local_reloptions(local_relopts *opts, Size relopt_struct_size)
Definition: reloptions.c:727
#define BLOOM_DEFAULT_NDISTINCT_PER_RANGE
Definition: brin_bloom.c:179
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:965
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
#define BLOOM_DEFAULT_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:197
#define BLOOM_MAX_FALSE_POSITIVE_RATE
Definition: brin_bloom.c:196
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define offsetof(type, field)
Definition: c.h:727

◆ brin_bloom_summary_in()

Datum brin_bloom_summary_in ( PG_FUNCTION_ARGS  )

Definition at line 743 of file brin_bloom.c.

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

744 {
745  /*
746  * brin_bloom_summary stores the data in binary form and parsing text
747  * input is not needed, so disallow this.
748  */
749  ereport(ERROR,
750  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
751  errmsg("cannot accept a value of type %s", "pg_brin_bloom_summary")));
752 
753  PG_RETURN_VOID(); /* keep compiler quiet */
754 }
int errcode(int sqlerrcode)
Definition: elog.c:698
#define ERROR
Definition: elog.h:46
#define ereport(elevel,...)
Definition: elog.h:157
#define PG_RETURN_VOID()
Definition: fmgr.h:349
int errmsg(const char *fmt,...)
Definition: elog.c:909

◆ brin_bloom_summary_out()

Datum brin_bloom_summary_out ( PG_FUNCTION_ARGS  )

Definition at line 765 of file brin_bloom.c.

References appendStringInfo(), appendStringInfoChar(), StringInfoData::data, initStringInfo(), BloomFilter::nbits, BloomFilter::nbits_set, BloomFilter::nhashes, PG_DETOAST_DATUM, PG_GETARG_BYTEA_PP, PG_RETURN_CSTRING, and generate_unaccent_rules::str.

766 {
767  BloomFilter *filter;
769 
770  /* detoast the data to get value with a full 4B header */
772 
773  initStringInfo(&str);
774  appendStringInfoChar(&str, '{');
775 
776  appendStringInfo(&str, "mode: hashed nhashes: %u nbits: %u nbits_set: %u",
777  filter->nhashes, filter->nbits, filter->nbits_set);
778 
779  appendStringInfoChar(&str, '}');
780 
781  PG_RETURN_CSTRING(str.data);
782 }
uint32 nbits_set
Definition: brin_bloom.c:256
void appendStringInfo(StringInfo str, const char *fmt,...)
Definition: stringinfo.c:91
uint8 nhashes
Definition: brin_bloom.c:254
void appendStringInfoChar(StringInfo str, char ch)
Definition: stringinfo.c:188
void initStringInfo(StringInfo str)
Definition: stringinfo.c:59
uint32 nbits
Definition: brin_bloom.c:255
#define PG_RETURN_CSTRING(x)
Definition: fmgr.h:362
#define PG_GETARG_BYTEA_PP(n)
Definition: fmgr.h:308
#define PG_DETOAST_DATUM(datum)
Definition: fmgr.h:240

◆ brin_bloom_summary_recv()

Datum brin_bloom_summary_recv ( PG_FUNCTION_ARGS  )

Definition at line 789 of file brin_bloom.c.

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

790 {
791  ereport(ERROR,
792  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
793  errmsg("cannot accept a value of type %s", "pg_brin_bloom_summary")));
794 
795  PG_RETURN_VOID(); /* keep compiler quiet */
796 }
int errcode(int sqlerrcode)
Definition: elog.c:698
#define ERROR
Definition: elog.h:46
#define ereport(elevel,...)
Definition: elog.h:157
#define PG_RETURN_VOID()
Definition: fmgr.h:349
int errmsg(const char *fmt,...)
Definition: elog.c:909

◆ brin_bloom_summary_send()

Datum brin_bloom_summary_send ( PG_FUNCTION_ARGS  )

Definition at line 806 of file brin_bloom.c.

References byteasend().

807 {
808  return byteasend(fcinfo);
809 }
Datum byteasend(PG_FUNCTION_ARGS)
Definition: varlena.c:493

◆ brin_bloom_union()

Datum brin_bloom_union ( PG_FUNCTION_ARGS  )

Definition at line 638 of file brin_bloom.c.

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.

639 {
640  int i;
641  int nbytes;
642  BrinValues *col_a = (BrinValues *) PG_GETARG_POINTER(1);
643  BrinValues *col_b = (BrinValues *) PG_GETARG_POINTER(2);
644  BloomFilter *filter_a;
645  BloomFilter *filter_b;
646 
647  Assert(col_a->bv_attno == col_b->bv_attno);
648  Assert(!col_a->bv_allnulls && !col_b->bv_allnulls);
649 
650  filter_a = (BloomFilter *) PG_DETOAST_DATUM(col_a->bv_values[0]);
651  filter_b = (BloomFilter *) PG_DETOAST_DATUM(col_b->bv_values[0]);
652 
653  /* make sure the filters use the same parameters */
654  Assert(filter_a && filter_b);
655  Assert(filter_a->nbits == filter_b->nbits);
656  Assert(filter_a->nhashes == filter_b->nhashes);
657  Assert((filter_a->nbits > 0) && (filter_a->nbits % 8 == 0));
658 
659  nbytes = (filter_a->nbits) / 8;
660 
661  /* simply OR the bitmaps */
662  for (i = 0; i < nbytes; i++)
663  filter_a->data[i] |= filter_b->data[i];
664 
665  PG_RETURN_VOID();
666 }
bool bv_allnulls
Definition: brin_tuple.h:33
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:276
char data[FLEXIBLE_ARRAY_MEMBER]
Definition: brin_bloom.c:259
AttrNumber bv_attno
Definition: brin_tuple.h:31
uint8 nhashes
Definition: brin_bloom.c:254
uint32 nbits
Definition: brin_bloom.c:255
#define PG_RETURN_VOID()
Definition: fmgr.h:349
#define Assert(condition)
Definition: c.h:804
int i
#define PG_DETOAST_DATUM(datum)
Definition: fmgr.h:240
Datum * bv_values
Definition: brin_tuple.h:34