#include "postgres.h"
#include "access/amapi.h"
#include "access/generic_xlog.h"
#include "access/reloptions.h"
#include "bloom.h"
#include "catalog/index.h"
#include "commands/vacuum.h"
#include "miscadmin.h"
#include "storage/bufmgr.h"
#include "storage/freespace.h"
#include "storage/indexfsm.h"
#include "storage/lmgr.h"
#include "utils/memutils.h"

Include dependency graph for blutils.c:

Macros
#define	GETWORD(x, i) ( ( (BloomSignatureWord )(x) + ( (i) / SIGNWORDBITS ) ) )

#define	CLRBIT(x, i) GETWORD(x,i) &= ~( 0x01 << ( (i) % SIGNWORDBITS ) )

#define	SETBIT(x, i) GETWORD(x,i) \|= ( 0x01 << ( (i) % SIGNWORDBITS ) )

#define	GETBIT(x, i) ( (GETWORD(x,i) >> ( (i) % SIGNWORDBITS )) & 0x01 )

Functions
	PG_FUNCTION_INFO_V1 (blhandler)

static int32	myRand (void)

static void	mySrand (uint32 seed)

void	_PG_init (void)

static BloomOptions *	makeDefaultBloomOptions (void)

Datum	blhandler (PG_FUNCTION_ARGS)

void	initBloomState (BloomState *state, Relation index)

void	signValue (BloomState state, BloomSignatureWord sign, Datum value, int attno)

BloomTuple *	BloomFormTuple (BloomState state, ItemPointer iptr, Datum values, bool *isnull)

bool	BloomPageAddItem (BloomState state, Page page, BloomTuple tuple)

Buffer	BloomNewBuffer (Relation index)

void	BloomInitPage (Page page, uint16 flags)

void	BloomFillMetapage (Relation index, Page metaPage)

void	BloomInitMetapage (Relation index)

bytea *	bloptions (Datum reloptions, bool validate)

Variables
static relopt_kind	bl_relopt_kind

static relopt_parse_elt	bl_relopt_tab [INDEX_MAX_KEYS+1]

static int32	next

Macro Definition Documentation

◆ CLRBIT

#define CLRBIT	(	x,
		i
	)	GETWORD(x,i) &= ~( 0x01 << ( (i) % SIGNWORDBITS ) )

Definition at line 31 of file blutils.c.

◆ GETBIT

#define GETBIT	(	x,
		i
	)	( (GETWORD(x,i) >> ( (i) % SIGNWORDBITS )) & 0x01 )

Definition at line 33 of file blutils.c.

◆ GETWORD

#define GETWORD	(	x,
		i
	)	( ( (BloomSignatureWord )(x) + ( (i) / SIGNWORDBITS ) ) )

Definition at line 30 of file blutils.c.

◆ SETBIT

#define SETBIT	(	x,
		i
	)	GETWORD(x,i) \|= ( 0x01 << ( (i) % SIGNWORDBITS ) )

Definition at line 32 of file blutils.c.

Function Documentation

◆ _PG_init()

void _PG_init ( void )

Definition at line 52 of file blutils.c.

 {
     int         i;
     char        buf[16];
  
     bl_relopt_kind = add_reloption_kind();
  
     /* Option for length of signature */
     add_int_reloption(bl_relopt_kind, "length",
                       "Length of signature in bits",
                       DEFAULT_BLOOM_LENGTH, 1, MAX_BLOOM_LENGTH,
                       AccessExclusiveLock);
     bl_relopt_tab[0].optname = "length";
     bl_relopt_tab[0].opttype = RELOPT_TYPE_INT;
     bl_relopt_tab[0].offset = offsetof(BloomOptions, bloomLength);
  
     /* Number of bits for each possible index column: col1, col2, ... */
     for (i = 0; i < INDEX_MAX_KEYS; i++)
     {
         snprintf(buf, sizeof(buf), "col%d", i + 1);
         add_int_reloption(bl_relopt_kind, buf,
                           "Number of bits generated for each index column",
                           DEFAULT_BLOOM_BITS, 1, MAX_BLOOM_BITS,
                           AccessExclusiveLock);
         bl_relopt_tab[i + 1].optname = MemoryContextStrdup(TopMemoryContext,
                                                            buf);
         bl_relopt_tab[i + 1].opttype = RELOPT_TYPE_INT;
         bl_relopt_tab[i + 1].offset = offsetof(BloomOptions, bitSize[0]) + sizeof(int) * i;
     }
 }

References AccessExclusiveLock, add_int_reloption(), add_reloption_kind(), bl_relopt_kind, bl_relopt_tab, buf, DEFAULT_BLOOM_BITS, DEFAULT_BLOOM_LENGTH, i, INDEX_MAX_KEYS, MAX_BLOOM_BITS, MAX_BLOOM_LENGTH, MemoryContextStrdup(), relopt_parse_elt::offset, relopt_parse_elt::optname, relopt_parse_elt::opttype, RELOPT_TYPE_INT, snprintf, and TopMemoryContext.

◆ blhandler()

Datum blhandler ( PG_FUNCTION_ARGS )

Definition at line 106 of file blutils.c.

 {
     IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
  
     amroutine->amstrategies = BLOOM_NSTRATEGIES;
     amroutine->amsupport = BLOOM_NPROC;
     amroutine->amoptsprocnum = BLOOM_OPTIONS_PROC;
     amroutine->amcanorder = false;
     amroutine->amcanorderbyop = false;
     amroutine->amcanbackward = false;
     amroutine->amcanunique = false;
     amroutine->amcanmulticol = true;
     amroutine->amoptionalkey = true;
     amroutine->amsearcharray = false;
     amroutine->amsearchnulls = false;
     amroutine->amstorage = false;
     amroutine->amclusterable = false;
     amroutine->ampredlocks = false;
     amroutine->amcanparallel = false;
     amroutine->amcaninclude = false;
     amroutine->amusemaintenanceworkmem = false;
     amroutine->amparallelvacuumoptions =
         VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_CLEANUP;
     amroutine->amkeytype = InvalidOid;
  
     amroutine->ambuild = blbuild;
     amroutine->ambuildempty = blbuildempty;
     amroutine->aminsert = blinsert;
     amroutine->ambulkdelete = blbulkdelete;
     amroutine->amvacuumcleanup = blvacuumcleanup;
     amroutine->amcanreturn = NULL;
     amroutine->amcostestimate = blcostestimate;
     amroutine->amoptions = bloptions;
     amroutine->amproperty = NULL;
     amroutine->ambuildphasename = NULL;
     amroutine->amvalidate = blvalidate;
     amroutine->amadjustmembers = NULL;
     amroutine->ambeginscan = blbeginscan;
     amroutine->amrescan = blrescan;
     amroutine->amgettuple = NULL;
     amroutine->amgetbitmap = blgetbitmap;
     amroutine->amendscan = blendscan;
     amroutine->ammarkpos = NULL;
     amroutine->amrestrpos = NULL;
     amroutine->amestimateparallelscan = NULL;
     amroutine->aminitparallelscan = NULL;
     amroutine->amparallelrescan = NULL;
  
     PG_RETURN_POINTER(amroutine);
 }

◆ BloomFillMetapage()

void BloomFillMetapage	(	Relation	index,
		Page	metaPage
	)

Definition at line 422 of file blutils.c.

 {
     BloomOptions *opts;
     BloomMetaPageData *metadata;
  
     /*
      * Choose the index's options.  If reloptions have been assigned, use
      * those, otherwise create default options.
      */
     opts = (BloomOptions *) index->rd_options;
     if (!opts)
         opts = makeDefaultBloomOptions();
  
     /*
      * Initialize contents of meta page, including a copy of the options,
      * which are now frozen for the life of the index.
      */
     BloomInitPage(metaPage, BLOOM_META);
     metadata = BloomPageGetMeta(metaPage);
     memset(metadata, 0, sizeof(BloomMetaPageData));
     metadata->magickNumber = BLOOM_MAGICK_NUMBER;
     metadata->opts = *opts;
     ((PageHeader) metaPage)->pd_lower += sizeof(BloomMetaPageData);
  
     /* If this fails, probably FreeBlockNumberArray size calc is wrong: */
     Assert(((PageHeader) metaPage)->pd_lower <= ((PageHeader) metaPage)->pd_upper);
 }

References Assert(), BLOOM_MAGICK_NUMBER, BLOOM_META, BloomInitPage(), BloomPageGetMeta, if(), BloomMetaPageData::magickNumber, makeDefaultBloomOptions(), BloomMetaPageData::opts, and opts.

Referenced by blbuildempty(), and BloomInitMetapage().

◆ BloomFormTuple()

BloomTuple* BloomFormTuple	(	BloomState *	state,
		ItemPointer	iptr,
		Datum *	values,
		bool *	isnull
	)

Definition at line 293 of file blutils.c.

 {
     int         i;
     BloomTuple *res = (BloomTuple *) palloc0(state->sizeOfBloomTuple);
  
     res->heapPtr = *iptr;
  
     /* Blooming each column */
     for (i = 0; i < state->nColumns; i++)
     {
         /* skip nulls */
         if (isnull[i])
             continue;
  
         signValue(state, res->sign, values[i], i);
     }
  
     return res;
 }

References i, palloc0(), res, signValue(), and values.

Referenced by blinsert(), and bloomBuildCallback().

◆ BloomInitMetapage()

void BloomInitMetapage ( Relation index )

Definition at line 454 of file blutils.c.

 {
     Buffer      metaBuffer;
     Page        metaPage;
     GenericXLogState *state;
  
     /*
      * Make a new page; since it is first page it should be associated with
      * block number 0 (BLOOM_METAPAGE_BLKNO).
      */
     metaBuffer = BloomNewBuffer(index);
     Assert(BufferGetBlockNumber(metaBuffer) == BLOOM_METAPAGE_BLKNO);
  
     /* Initialize contents of meta page */
     state = GenericXLogStart(index);
     metaPage = GenericXLogRegisterBuffer(state, metaBuffer,
                                          GENERIC_XLOG_FULL_IMAGE);
     BloomFillMetapage(index, metaPage);
     GenericXLogFinish(state);
  
     UnlockReleaseBuffer(metaBuffer);
 }

References Assert(), BLOOM_METAPAGE_BLKNO, BloomFillMetapage(), BloomNewBuffer(), BufferGetBlockNumber(), GENERIC_XLOG_FULL_IMAGE, GenericXLogFinish(), GenericXLogRegisterBuffer(), GenericXLogStart(), and UnlockReleaseBuffer().

Referenced by blbuild().

◆ BloomInitPage()

void BloomInitPage	(	Page	page,
		uint16	flags
	)

Definition at line 407 of file blutils.c.

 {
     BloomPageOpaque opaque;
  
     PageInit(page, BLCKSZ, sizeof(BloomPageOpaqueData));
  
     opaque = BloomPageGetOpaque(page);
     opaque->flags = flags;
     opaque->bloom_page_id = BLOOM_PAGE_ID;
 }

References BloomPageOpaqueData::bloom_page_id, BLOOM_PAGE_ID, BloomPageGetOpaque, BloomPageOpaqueData::flags, and PageInit().

Referenced by blinsert(), BloomFillMetapage(), and initCachedPage().

◆ BloomNewBuffer()

Buffer BloomNewBuffer ( Relation index )

Definition at line 353 of file blutils.c.

 {
     Buffer      buffer;
     bool        needLock;
  
     /* First, try to get a page from FSM */
     for (;;)
     {
         BlockNumber blkno = GetFreeIndexPage(index);
  
         if (blkno == InvalidBlockNumber)
             break;
  
         buffer = ReadBuffer(index, blkno);
  
         /*
          * We have to guard against the possibility that someone else already
          * recycled this page; the buffer may be locked if so.
          */
         if (ConditionalLockBuffer(buffer))
         {
             Page        page = BufferGetPage(buffer);
  
             if (PageIsNew(page))
                 return buffer;  /* OK to use, if never initialized */
  
             if (BloomPageIsDeleted(page))
                 return buffer;  /* OK to use */
  
             LockBuffer(buffer, BUFFER_LOCK_UNLOCK);
         }
  
         /* Can't use it, so release buffer and try again */
         ReleaseBuffer(buffer);
     }
  
     /* Must extend the file */
     needLock = !RELATION_IS_LOCAL(index);
     if (needLock)
         LockRelationForExtension(index, ExclusiveLock);
  
     buffer = ReadBuffer(index, P_NEW);
     LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);
  
     if (needLock)
         UnlockRelationForExtension(index, ExclusiveLock);
  
     return buffer;
 }

References BloomPageIsDeleted, BUFFER_LOCK_EXCLUSIVE, BUFFER_LOCK_UNLOCK, BufferGetPage(), ConditionalLockBuffer(), ExclusiveLock, GetFreeIndexPage(), InvalidBlockNumber, LockBuffer(), LockRelationForExtension(), P_NEW, PageIsNew(), ReadBuffer(), RELATION_IS_LOCAL, ReleaseBuffer(), and UnlockRelationForExtension().

Referenced by blinsert(), BloomInitMetapage(), and flushCachedPage().

◆ BloomPageAddItem()

bool BloomPageAddItem	(	BloomState *	state,
		Page	page,
		BloomTuple *	tuple
	)

Definition at line 318 of file blutils.c.

 {
     BloomTuple *itup;
     BloomPageOpaque opaque;
     Pointer     ptr;
  
     /* We shouldn't be pointed to an invalid page */
     Assert(!PageIsNew(page) && !BloomPageIsDeleted(page));
  
     /* Does new tuple fit on the page? */
     if (BloomPageGetFreeSpace(state, page) < state->sizeOfBloomTuple)
         return false;
  
     /* Copy new tuple to the end of page */
     opaque = BloomPageGetOpaque(page);
     itup = BloomPageGetTuple(state, page, opaque->maxoff + 1);
     memcpy((Pointer) itup, (Pointer) tuple, state->sizeOfBloomTuple);
  
     /* Adjust maxoff and pd_lower */
     opaque->maxoff++;
     ptr = (Pointer) BloomPageGetTuple(state, page, opaque->maxoff + 1);
     ((PageHeader) page)->pd_lower = ptr - page;
  
     /* Assert we didn't overrun available space */
     Assert(((PageHeader) page)->pd_lower <= ((PageHeader) page)->pd_upper);
  
     return true;
 }

References Assert(), BloomPageGetFreeSpace, BloomPageGetOpaque, BloomPageGetTuple, BloomPageIsDeleted, BloomPageOpaqueData::maxoff, and PageIsNew().

Referenced by blinsert(), and bloomBuildCallback().

◆ bloptions()

bytea* bloptions	(	Datum	reloptions,
		bool	validate
	)

Definition at line 481 of file blutils.c.

 {
     BloomOptions *rdopts;
  
     /* Parse the user-given reloptions */
     rdopts = (BloomOptions *) build_reloptions(reloptions, validate,
                                                bl_relopt_kind,
                                                sizeof(BloomOptions),
                                                bl_relopt_tab,
                                                lengthof(bl_relopt_tab));
  
     /* Convert signature length from # of bits to # to words, rounding up */
     if (rdopts)
         rdopts->bloomLength = (rdopts->bloomLength + SIGNWORDBITS - 1) / SIGNWORDBITS;
  
     return (bytea *) rdopts;
 }

References bl_relopt_kind, bl_relopt_tab, BloomOptions::bloomLength, build_reloptions(), lengthof, and SIGNWORDBITS.

Referenced by blhandler().

◆ initBloomState()

void initBloomState	(	BloomState *	state,
		Relation	index
	)

Definition at line 161 of file blutils.c.

 {
     int         i;
  
     state->nColumns = index->rd_att->natts;
  
     /* Initialize hash function for each attribute */
     for (i = 0; i < index->rd_att->natts; i++)
     {
         fmgr_info_copy(&(state->hashFn[i]),
                        index_getprocinfo(index, i + 1, BLOOM_HASH_PROC),
                        CurrentMemoryContext);
         state->collations[i] = index->rd_indcollation[i];
     }
  
     /* Initialize amcache if needed with options from metapage */
     if (!index->rd_amcache)
     {
         Buffer      buffer;
         Page        page;
         BloomMetaPageData *meta;
         BloomOptions *opts;
  
         opts = MemoryContextAlloc(index->rd_indexcxt, sizeof(BloomOptions));
  
         buffer = ReadBuffer(index, BLOOM_METAPAGE_BLKNO);
         LockBuffer(buffer, BUFFER_LOCK_SHARE);
  
         page = BufferGetPage(buffer);
  
         if (!BloomPageIsMeta(page))
             elog(ERROR, "Relation is not a bloom index");
         meta = BloomPageGetMeta(BufferGetPage(buffer));
  
         if (meta->magickNumber != BLOOM_MAGICK_NUMBER)
             elog(ERROR, "Relation is not a bloom index");
  
         *opts = meta->opts;
  
         UnlockReleaseBuffer(buffer);
  
         index->rd_amcache = (void *) opts;
     }
  
     memcpy(&state->opts, index->rd_amcache, sizeof(state->opts));
     state->sizeOfBloomTuple = BLOOMTUPLEHDRSZ +
         sizeof(BloomSignatureWord) * state->opts.bloomLength;
 }

References BLOOM_HASH_PROC, BLOOM_MAGICK_NUMBER, BLOOM_METAPAGE_BLKNO, BloomPageGetMeta, BloomPageIsMeta, BLOOMTUPLEHDRSZ, BUFFER_LOCK_SHARE, BufferGetPage(), CurrentMemoryContext, elog(), ERROR, fmgr_info_copy(), i, index_getprocinfo(), LockBuffer(), BloomMetaPageData::magickNumber, MemoryContextAlloc(), BloomMetaPageData::opts, opts, ReadBuffer(), and UnlockReleaseBuffer().

Referenced by blbeginscan(), blbuild(), blbulkdelete(), and blinsert().

◆ makeDefaultBloomOptions()

static BloomOptions* makeDefaultBloomOptions ( void )

static

Definition at line 87 of file blutils.c.

 {
     BloomOptions *opts;
     int         i;
  
     opts = (BloomOptions *) palloc0(sizeof(BloomOptions));
     /* Convert DEFAULT_BLOOM_LENGTH from # of bits to # of words */
     opts->bloomLength = (DEFAULT_BLOOM_LENGTH + SIGNWORDBITS - 1) / SIGNWORDBITS;
     for (i = 0; i < INDEX_MAX_KEYS; i++)
         opts->bitSize[i] = DEFAULT_BLOOM_BITS;
     SET_VARSIZE(opts, sizeof(BloomOptions));
     return opts;
 }

References DEFAULT_BLOOM_BITS, DEFAULT_BLOOM_LENGTH, i, INDEX_MAX_KEYS, opts, palloc0(), SET_VARSIZE, and SIGNWORDBITS.

Referenced by BloomFillMetapage().

◆ myRand()

static int32 myRand ( void )

static

Definition at line 222 of file blutils.c.

 {
     /*----------
      * Compute x = (7^5 * x) mod (2^31 - 1)
      * without overflowing 31 bits:
      *      (2^31 - 1) = 127773 * (7^5) + 2836
      * From "Random number generators: good ones are hard to find",
      * Park and Miller, Communications of the ACM, vol. 31, no. 10,
      * October 1988, p. 1195.
      *----------
      */
     int32       hi,
                 lo,
                 x;
  
     /* Must be in [1, 0x7ffffffe] range at this point. */
     hi = next / 127773;
     lo = next % 127773;
     x = 16807 * lo - 2836 * hi;
     if (x < 0)
         x += 0x7fffffff;
     next = x;
     /* Transform to [0, 0x7ffffffd] range. */
     return (x - 1);
 }

References next, and x.

Referenced by signValue().

◆ mySrand()

static void mySrand ( uint32 seed )

static

Definition at line 249 of file blutils.c.

 {
     next = seed;
     /* Transform to [1, 0x7ffffffe] range. */
     next = (next % 0x7ffffffe) + 1;
 }

References next.

Referenced by signValue().

◆ PG_FUNCTION_INFO_V1()

PG_FUNCTION_INFO_V1 ( blhandler )

◆ signValue()

void signValue	(	BloomState *	state,
		BloomSignatureWord *	sign,
		Datum	value,
		int	attno
	)

Definition at line 260 of file blutils.c.

 {
     uint32      hashVal;
     int         nBit,
                 j;
  
     /*
      * init generator with "column's" number to get "hashed" seed for new
      * value. We don't want to map the same numbers from different columns
      * into the same bits!
      */
     mySrand(attno);
  
     /*
      * Init hash sequence to map our value into bits. the same values in
      * different columns will be mapped into different bits because of step
      * above
      */
     hashVal = DatumGetInt32(FunctionCall1Coll(&state->hashFn[attno], state->collations[attno], value));
     mySrand(hashVal ^ myRand());
  
     for (j = 0; j < state->opts.bitSize[attno]; j++)
     {
         /* prevent multiple evaluation in SETBIT macro */
         nBit = myRand() % (state->opts.bloomLength * SIGNWORDBITS);
         SETBIT(sign, nBit);
     }
 }