diff options
Diffstat (limited to 'contrib/bloom/blutils.c')
| -rw-r--r-- | contrib/bloom/blutils.c | 497 |
1 files changed, 497 insertions, 0 deletions
diff --git a/contrib/bloom/blutils.c b/contrib/bloom/blutils.c new file mode 100644 index 0000000..d3bf866 --- /dev/null +++ b/contrib/bloom/blutils.c @@ -0,0 +1,497 @@ +/*------------------------------------------------------------------------- + * + * blutils.c + * Bloom index utilities. + * + * Portions Copyright (c) 2016-2020, PostgreSQL Global Development Group + * Portions Copyright (c) 1990-1993, Regents of the University of California + * + * IDENTIFICATION + * contrib/bloom/blutils.c + * + *------------------------------------------------------------------------- + */ +#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" + +/* Signature dealing macros - note i is assumed to be of type int */ +#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 ) + +PG_FUNCTION_INFO_V1(blhandler); + +/* Kind of relation options for bloom index */ +static relopt_kind bl_relopt_kind; + +/* parse table for fillRelOptions */ +static relopt_parse_elt bl_relopt_tab[INDEX_MAX_KEYS + 1]; + +static int32 myRand(void); +static void mySrand(uint32 seed); + +/* + * Module initialize function: initialize info about Bloom relation options. + * + * Note: keep this in sync with makeDefaultBloomOptions(). + */ +void +_PG_init(void) +{ + 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; + } +} + +/* + * Construct a default set of Bloom options. + */ +static BloomOptions * +makeDefaultBloomOptions(void) +{ + 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; +} + +/* + * Bloom handler function: return IndexAmRoutine with access method parameters + * and callbacks. + */ +Datum +blhandler(PG_FUNCTION_ARGS) +{ + 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->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); +} + +/* + * Fill BloomState structure for particular index. + */ +void +initBloomState(BloomState *state, Relation index) +{ + 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; +} + +/* + * Random generator copied from FreeBSD. Using own random generator here for + * two reasons: + * + * 1) In this case random numbers are used for on-disk storage. Usage of + * PostgreSQL number generator would obstruct it from all possible changes. + * 2) Changing seed of PostgreSQL random generator would be undesirable side + * effect. + */ +static int32 next; + +static int32 +myRand(void) +{ + /*---------- + * 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) +{ + next = seed; + /* Transform to [1, 0x7ffffffe] range. */ + next = (next % 0x7ffffffe) + 1; +} + +/* + * Add bits of given value to the signature. + */ +void +signValue(BloomState *state, BloomSignatureWord *sign, Datum value, int attno) +{ + 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); + } +} + +/* + * Make bloom tuple from values. + */ +BloomTuple * +BloomFormTuple(BloomState *state, ItemPointer iptr, Datum *values, bool *isnull) +{ + 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; +} + +/* + * Add new bloom tuple to the page. Returns true if new tuple was successfully + * added to the page. Returns false if it doesn't fit on the page. + */ +bool +BloomPageAddItem(BloomState *state, Page page, BloomTuple *tuple) +{ + 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; +} + +/* + * Allocate a new page (either by recycling, or by extending the index file) + * The returned buffer is already pinned and exclusive-locked + * Caller is responsible for initializing the page by calling BloomInitPage + */ +Buffer +BloomNewBuffer(Relation index) +{ + 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; +} + +/* + * Initialize any page of a bloom index. + */ +void +BloomInitPage(Page page, uint16 flags) +{ + 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; +} + +/* + * Fill in metapage for bloom index. + */ +void +BloomFillMetapage(Relation index, Page metaPage) +{ + 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); +} + +/* + * Initialize metapage for bloom index. + */ +void +BloomInitMetapage(Relation index) +{ + 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); +} + +/* + * Parse reloptions for bloom index, producing a BloomOptions struct. + */ +bytea * +bloptions(Datum reloptions, bool validate) +{ + 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; +} |