#include "postgres.h"
#include "access/amapi.h"
#include "access/generic_xlog.h"
#include "catalog/index.h"
#include "storage/lmgr.h"
#include "miscadmin.h"
#include "storage/bufmgr.h"
#include "storage/indexfsm.h"
#include "utils/memutils.h"
#include "access/reloptions.h"
#include "storage/freespace.h"
#include "bloom.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

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

Definition at line 32 of file blutils.c.

Referenced by _hash_freeovflpage(), and hash_xlog_squeeze_page().

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

Definition at line 34 of file blutils.c.

Referenced by _intbig_contains(), _intbig_overlap(), checkcondition_bit(), cnt_sml_sign_common(), gist_qe(), gist_te(), and gtrgm_consistent().

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

Definition at line 31 of file blutils.c.

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

Definition at line 33 of file blutils.c.

Referenced by _hash_addovflpage(), hash_xlog_add_ovfl_page(), makesign(), and signValue().

Function Documentation

void _PG_init ( void )

Definition at line 53 of file blutils.c.

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

 {
     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);
     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);
         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;
     }
 }

Datum blhandler ( PG_FUNCTION_ARGS )

Definition at line 105 of file blutils.c.

 {
     IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
 
     amroutine->amstrategies = BLOOM_NSTRATEGIES;
     amroutine->amsupport = BLOOM_NPROC;
     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->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->amvalidate = blvalidate;
     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);
 }

void BloomFillMetapage	(	Relation	index,
		Page	metaPage
	)

Definition at line 414 of file blutils.c.

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

Referenced by blbuildempty(), and BloomInitMetapage().

 {
     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);
 }

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

Definition at line 284 of file blutils.c.

References BloomTuple::heapPtr, i, BloomState::nColumns, palloc0(), BloomTuple::sign, signValue(), and BloomState::sizeOfBloomTuple.

Referenced by blinsert(), and bloomBuildCallback().

 {
     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;
 }

void BloomInitMetapage ( Relation index )

Definition at line 446 of file blutils.c.

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

Referenced by blbuild().

 {
     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);
 }

void BloomInitPage	(	Page	page,
		uint16	flags
	)

Definition at line 398 of file blutils.c.

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

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

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

Buffer BloomNewBuffer ( Relation index )

Definition at line 344 of file blutils.c.

References BloomPageIsDeleted, buffer, 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().

 {
     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;
 }

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

Definition at line 309 of file blutils.c.

References Assert, BloomPageGetFreeSpace, BloomPageGetOpaque, BloomPageGetTuple, BloomPageIsDeleted, BloomPageOpaqueData::maxoff, PageIsNew, and BloomState::sizeOfBloomTuple.

Referenced by blinsert(), and bloomBuildCallback().

 {
     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;
 }

bytea* bloptions	(	Datum	reloptions,
		bool	validate
	)

Definition at line 473 of file blutils.c.

References allocateReloptStruct(), bl_relopt_kind, BloomOptions::bloomLength, fillRelOptions(), lengthof, options, parseRelOptions(), and SIGNWORDBITS.

Referenced by blhandler().

 {
     relopt_value *options;
     int         numoptions;
     BloomOptions *rdopts;
 
     /* Parse the user-given reloptions */
     options = parseRelOptions(reloptions, validate, bl_relopt_kind, &numoptions);
     rdopts = allocateReloptStruct(sizeof(BloomOptions), options, numoptions);
     fillRelOptions((void *) rdopts, sizeof(BloomOptions), options, numoptions,
                    validate, bl_relopt_tab, lengthof(bl_relopt_tab));
 
     /* Convert signature length from # of bits to # to words, rounding up */
     rdopts->bloomLength = (rdopts->bloomLength + SIGNWORDBITS - 1) / SIGNWORDBITS;
 
     return (bytea *) rdopts;
 }

void initBloomState	(	BloomState *	state,
		Relation	index
	)

Definition at line 153 of file blutils.c.

References BLOOM_HASH_PROC, BLOOM_MAGICK_NUMBER, BLOOM_METAPAGE_BLKNO, BloomOptions::bloomLength, BloomPageGetMeta, BloomPageIsMeta, BLOOMTUPLEHDRSZ, buffer, BUFFER_LOCK_SHARE, BufferGetPage, CurrentMemoryContext, elog, ERROR, fmgr_info_copy(), BloomState::hashFn, i, index_getprocinfo(), LockBuffer(), BloomMetaPageData::magickNumber, MemoryContextAlloc(), tupleDesc::natts, BloomState::nColumns, BloomMetaPageData::opts, BloomState::opts, RelationData::rd_amcache, RelationData::rd_att, RelationData::rd_indexcxt, ReadBuffer(), BloomState::sizeOfBloomTuple, and UnlockReleaseBuffer().

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

 {
     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);
     }
 
     /* 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;
 }

static BloomOptions* makeDefaultBloomOptions ( void )

static

Definition at line 86 of file blutils.c.

References BloomOptions::bitSize, BloomOptions::bloomLength, DEFAULT_BLOOM_BITS, DEFAULT_BLOOM_LENGTH, i, INDEX_MAX_KEYS, palloc0(), SET_VARSIZE, and SIGNWORDBITS.

Referenced by BloomFillMetapage().

 {
     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;
 }

static int32 myRand ( void )

static

Definition at line 213 of file blutils.c.

References next.

Referenced by signValue().

 {
     /*----------
      * 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);
 }

static void mySrand ( uint32 seed )

static

Definition at line 240 of file blutils.c.

References next.

Referenced by signValue().

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

PG_FUNCTION_INFO_V1 ( blhandler )

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

Definition at line 251 of file blutils.c.

References BloomOptions::bitSize, BloomOptions::bloomLength, DatumGetInt32, FunctionCall1, BloomState::hashFn, myRand(), mySrand(), BloomState::opts, SETBIT, and SIGNWORDBITS.

Referenced by blgetbitmap(), and BloomFormTuple().

 {
     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(FunctionCall1(&state->hashFn[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);
     }
 }

Variable Documentation

relopt_kind bl_relopt_kind

static

Definition at line 39 of file blutils.c.

Referenced by _PG_init(), and bloptions().

relopt_parse_elt bl_relopt_tab[INDEX_MAX_KEYS+1]

static

Definition at line 42 of file blutils.c.

int32 next

static

Definition at line 210 of file blutils.c.

Referenced by addItemsToLeaf(), addKey(), AllocSetDelete(), AllocSetReset(), AlterTSDictionary(), AtEOSubXact_SPI(), AtSubAbort_Snapshot(), cipher_free_callback(), create_nestloop_plan(), deallocate_one(), digest_free_callback(), do_setval(), dsa_trim(), ECPGconnect(), filemap_list_to_array(), find_struct(), find_struct_member(), find_variable(), FreePageManagerGetInternal(), FreePagePopSpanLeader(), get_best_segment(), get_foreign_key_join_selectivity(), get_source_line(), get_typedef(), getNextFlagFromString(), GinDataLeafPageGetItems(), infer_arbiter_indexes(), IssuePendingWritebacks(), LagTrackerRead(), main(), make_new_segment(), merge_children(), MergeAttributes(), myRand(), mySrand(), nextval_internal(), pg_event_trigger_dropped_objects(), plpgsql_destroy_econtext(), plpgsql_subxact_cb(), PLySequence_ToArray(), PostPrepare_smgr(), prepare_common(), pushf_create(), reconsider_outer_join_clauses(), reduce_unique_semijoins(), RelationPreserveStorage(), RememberFsyncRequest(), remove_wi_from_list(), ReorderBufferIterTXNNext(), select_active_windows(), sepgsql_avc_reclaim(), sepgsql_subxact_callback(), SetClientEncoding(), setCompoundAffixFlagValue(), setval3_oid(), setval_oid(), smgrDoPendingDeletes(), SPI_freetuptable(), StandbyReleaseAllLocks(), StandbyReleaseLocks(), StandbyReleaseOldLocks(), SyncRepGetSyncStandbysPriority(), unicode_normalize_kc(), unlink_segment(), and unlink_span().

Macros

Functions

Variables

Macro Definition Documentation

Function Documentation

Variable Documentation