granicus.if.org Git - postgresql/blob - contrib/bloom/blutils.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * blutils.c
   4  *              Bloom index utilities.
   5  *
   6  * Portions Copyright (c) 2016-2019, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1990-1993, Regents of the University of California
   8  *
   9  * IDENTIFICATION
  10  *        contrib/bloom/blutils.c
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include "postgres.h"
  15
  16 #include "access/amapi.h"
  17 #include "access/generic_xlog.h"
  18 #include "access/reloptions.h"
  19 #include "bloom.h"
  20 #include "catalog/index.h"
  21 #include "miscadmin.h"
  22 #include "storage/bufmgr.h"
  23 #include "storage/freespace.h"
  24 #include "storage/indexfsm.h"
  25 #include "storage/lmgr.h"
  26 #include "utils/memutils.h"
  27
  28 /* Signature dealing macros - note i is assumed to be of type int */
  29 #define GETWORD(x,i) ( *( (BloomSignatureWord *)(x) + ( (i) / SIGNWORDBITS ) ) )
  30 #define CLRBIT(x,i)   GETWORD(x,i) &= ~( 0x01 << ( (i) % SIGNWORDBITS ) )
  31 #define SETBIT(x,i)   GETWORD(x,i) |=  ( 0x01 << ( (i) % SIGNWORDBITS ) )
  32 #define GETBIT(x,i) ( (GETWORD(x,i) >> ( (i) % SIGNWORDBITS )) & 0x01 )
  33
  34 PG_FUNCTION_INFO_V1(blhandler);
  35
  36 /* Kind of relation options for bloom index */
  37 static relopt_kind bl_relopt_kind;
  38
  39 /* parse table for fillRelOptions */
  40 static relopt_parse_elt bl_relopt_tab[INDEX_MAX_KEYS + 1];
  41
  42 static int32 myRand(void);
  43 static void mySrand(uint32 seed);
  44
  45 /*
  46  * Module initialize function: initialize info about Bloom relation options.
  47  *
  48  * Note: keep this in sync with makeDefaultBloomOptions().
  49  */
  50 void
  51 _PG_init(void)
  52 {
  53         int                     i;
  54         char            buf[16];
  55
  56         bl_relopt_kind = add_reloption_kind();
  57
  58         /* Option for length of signature */
  59         add_int_reloption(bl_relopt_kind, "length",
  60                                           "Length of signature in bits",
  61                                           DEFAULT_BLOOM_LENGTH, 1, MAX_BLOOM_LENGTH,
  62                                           AccessExclusiveLock);
  63         bl_relopt_tab[0].optname = "length";
  64         bl_relopt_tab[0].opttype = RELOPT_TYPE_INT;
  65         bl_relopt_tab[0].offset = offsetof(BloomOptions, bloomLength);
  66
  67         /* Number of bits for each possible index column: col1, col2, ... */
  68         for (i = 0; i < INDEX_MAX_KEYS; i++)
  69         {
  70                 snprintf(buf, sizeof(buf), "col%d", i + 1);
  71                 add_int_reloption(bl_relopt_kind, buf,
  72                                                   "Number of bits generated for each index column",
  73                                                   DEFAULT_BLOOM_BITS, 1, MAX_BLOOM_BITS,
  74                                                   AccessExclusiveLock);
  75                 bl_relopt_tab[i + 1].optname = MemoryContextStrdup(TopMemoryContext,
  76                                                                                                                    buf);
  77                 bl_relopt_tab[i + 1].opttype = RELOPT_TYPE_INT;
  78                 bl_relopt_tab[i + 1].offset = offsetof(BloomOptions, bitSize[0]) + sizeof(int) * i;
  79         }
  80 }
  81
  82 /*
  83  * Construct a default set of Bloom options.
  84  */
  85 static BloomOptions *
  86 makeDefaultBloomOptions(void)
  87 {
  88         BloomOptions *opts;
  89         int                     i;
  90
  91         opts = (BloomOptions *) palloc0(sizeof(BloomOptions));
  92         /* Convert DEFAULT_BLOOM_LENGTH from # of bits to # of words */
  93         opts->bloomLength = (DEFAULT_BLOOM_LENGTH + SIGNWORDBITS - 1) / SIGNWORDBITS;
  94         for (i = 0; i < INDEX_MAX_KEYS; i++)
  95                 opts->bitSize[i] = DEFAULT_BLOOM_BITS;
  96         SET_VARSIZE(opts, sizeof(BloomOptions));
  97         return opts;
  98 }
  99
 100 /*
 101  * Bloom handler function: return IndexAmRoutine with access method parameters
 102  * and callbacks.
 103  */
 104 Datum
 105 blhandler(PG_FUNCTION_ARGS)
 106 {
 107         IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
 108
 109         amroutine->amstrategies = BLOOM_NSTRATEGIES;
 110         amroutine->amsupport = BLOOM_NPROC;
 111         amroutine->amcanorder = false;
 112         amroutine->amcanorderbyop = false;
 113         amroutine->amcanbackward = false;
 114         amroutine->amcanunique = false;
 115         amroutine->amcanmulticol = true;
 116         amroutine->amoptionalkey = true;
 117         amroutine->amsearcharray = false;
 118         amroutine->amsearchnulls = false;
 119         amroutine->amstorage = false;
 120         amroutine->amclusterable = false;
 121         amroutine->ampredlocks = false;
 122         amroutine->amcanparallel = false;
 123         amroutine->amcaninclude = false;
 124         amroutine->amkeytype = InvalidOid;
 125
 126         amroutine->ambuild = blbuild;
 127         amroutine->ambuildempty = blbuildempty;
 128         amroutine->aminsert = blinsert;
 129         amroutine->ambulkdelete = blbulkdelete;
 130         amroutine->amvacuumcleanup = blvacuumcleanup;
 131         amroutine->amcanreturn = NULL;
 132         amroutine->amcostestimate = blcostestimate;
 133         amroutine->amoptions = bloptions;
 134         amroutine->amproperty = NULL;
 135         amroutine->ambuildphasename = NULL;
 136         amroutine->amvalidate = blvalidate;
 137         amroutine->ambeginscan = blbeginscan;
 138         amroutine->amrescan = blrescan;
 139         amroutine->amgettuple = NULL;
 140         amroutine->amgetbitmap = blgetbitmap;
 141         amroutine->amendscan = blendscan;
 142         amroutine->ammarkpos = NULL;
 143         amroutine->amrestrpos = NULL;
 144         amroutine->amestimateparallelscan = NULL;
 145         amroutine->aminitparallelscan = NULL;
 146         amroutine->amparallelrescan = NULL;
 147
 148         PG_RETURN_POINTER(amroutine);
 149 }
 150
 151 /*
 152  * Fill BloomState structure for particular index.
 153  */
 154 void
 155 initBloomState(BloomState *state, Relation index)
 156 {
 157         int                     i;
 158
 159         state->nColumns = index->rd_att->natts;
 160
 161         /* Initialize hash function for each attribute */
 162         for (i = 0; i < index->rd_att->natts; i++)
 163         {
 164                 fmgr_info_copy(&(state->hashFn[i]),
 165                                            index_getprocinfo(index, i + 1, BLOOM_HASH_PROC),
 166                                            CurrentMemoryContext);
 167                 state->collations[i] = index->rd_indcollation[i];
 168         }
 169
 170         /* Initialize amcache if needed with options from metapage */
 171         if (!index->rd_amcache)
 172         {
 173                 Buffer          buffer;
 174                 Page            page;
 175                 BloomMetaPageData *meta;
 176                 BloomOptions *opts;
 177
 178                 opts = MemoryContextAlloc(index->rd_indexcxt, sizeof(BloomOptions));
 179
 180                 buffer = ReadBuffer(index, BLOOM_METAPAGE_BLKNO);
 181                 LockBuffer(buffer, BUFFER_LOCK_SHARE);
 182
 183                 page = BufferGetPage(buffer);
 184
 185                 if (!BloomPageIsMeta(page))
 186                         elog(ERROR, "Relation is not a bloom index");
 187                 meta = BloomPageGetMeta(BufferGetPage(buffer));
 188
 189                 if (meta->magickNumber != BLOOM_MAGICK_NUMBER)
 190                         elog(ERROR, "Relation is not a bloom index");
 191
 192                 *opts = meta->opts;
 193
 194                 UnlockReleaseBuffer(buffer);
 195
 196                 index->rd_amcache = (void *) opts;
 197         }
 198
 199         memcpy(&state->opts, index->rd_amcache, sizeof(state->opts));
 200         state->sizeOfBloomTuple = BLOOMTUPLEHDRSZ +
 201                 sizeof(BloomSignatureWord) * state->opts.bloomLength;
 202 }
 203
 204 /*
 205  * Random generator copied from FreeBSD.  Using own random generator here for
 206  * two reasons:
 207  *
 208  * 1) In this case random numbers are used for on-disk storage.  Usage of
 209  *        PostgreSQL number generator would obstruct it from all possible changes.
 210  * 2) Changing seed of PostgreSQL random generator would be undesirable side
 211  *        effect.
 212  */
 213 static int32 next;
 214
 215 static int32
 216 myRand(void)
 217 {
 218         /*----------
 219          * Compute x = (7^5 * x) mod (2^31 - 1)
 220          * without overflowing 31 bits:
 221          *              (2^31 - 1) = 127773 * (7^5) + 2836
 222          * From "Random number generators: good ones are hard to find",
 223          * Park and Miller, Communications of the ACM, vol. 31, no. 10,
 224          * October 1988, p. 1195.
 225          *----------
 226          */
 227         int32           hi,
 228                                 lo,
 229                                 x;
 230
 231         /* Must be in [1, 0x7ffffffe] range at this point. */
 232         hi = next / 127773;
 233         lo = next % 127773;
 234         x = 16807 * lo - 2836 * hi;
 235         if (x < 0)
 236                 x += 0x7fffffff;
 237         next = x;
 238         /* Transform to [0, 0x7ffffffd] range. */
 239         return (x - 1);
 240 }
 241
 242 static void
 243 mySrand(uint32 seed)
 244 {
 245         next = seed;
 246         /* Transform to [1, 0x7ffffffe] range. */
 247         next = (next % 0x7ffffffe) + 1;
 248 }
 249
 250 /*
 251  * Add bits of given value to the signature.
 252  */
 253 void
 254 signValue(BloomState *state, BloomSignatureWord *sign, Datum value, int attno)
 255 {
 256         uint32          hashVal;
 257         int                     nBit,
 258                                 j;
 259
 260         /*
 261          * init generator with "column's" number to get "hashed" seed for new
 262          * value. We don't want to map the same numbers from different columns
 263          * into the same bits!
 264          */
 265         mySrand(attno);
 266
 267         /*
 268          * Init hash sequence to map our value into bits. the same values in
 269          * different columns will be mapped into different bits because of step
 270          * above
 271          */
 272         hashVal = DatumGetInt32(FunctionCall1Coll(&state->hashFn[attno], state->collations[attno], value));
 273         mySrand(hashVal ^ myRand());
 274
 275         for (j = 0; j < state->opts.bitSize[attno]; j++)
 276         {
 277                 /* prevent multiple evaluation in SETBIT macro */
 278                 nBit = myRand() % (state->opts.bloomLength * SIGNWORDBITS);
 279                 SETBIT(sign, nBit);
 280         }
 281 }
 282
 283 /*
 284  * Make bloom tuple from values.
 285  */
 286 BloomTuple *
 287 BloomFormTuple(BloomState *state, ItemPointer iptr, Datum *values, bool *isnull)
 288 {
 289         int                     i;
 290         BloomTuple *res = (BloomTuple *) palloc0(state->sizeOfBloomTuple);
 291
 292         res->heapPtr = *iptr;
 293
 294         /* Blooming each column */
 295         for (i = 0; i < state->nColumns; i++)
 296         {
 297                 /* skip nulls */
 298                 if (isnull[i])
 299                         continue;
 300
 301                 signValue(state, res->sign, values[i], i);
 302         }
 303
 304         return res;
 305 }
 306
 307 /*
 308  * Add new bloom tuple to the page.  Returns true if new tuple was successfully
 309  * added to the page.  Returns false if it doesn't fit on the page.
 310  */
 311 bool
 312 BloomPageAddItem(BloomState *state, Page page, BloomTuple *tuple)
 313 {
 314         BloomTuple *itup;
 315         BloomPageOpaque opaque;
 316         Pointer         ptr;
 317
 318         /* We shouldn't be pointed to an invalid page */
 319         Assert(!PageIsNew(page) && !BloomPageIsDeleted(page));
 320
 321         /* Does new tuple fit on the page? */
 322         if (BloomPageGetFreeSpace(state, page) < state->sizeOfBloomTuple)
 323                 return false;
 324
 325         /* Copy new tuple to the end of page */
 326         opaque = BloomPageGetOpaque(page);
 327         itup = BloomPageGetTuple(state, page, opaque->maxoff + 1);
 328         memcpy((Pointer) itup, (Pointer) tuple, state->sizeOfBloomTuple);
 329
 330         /* Adjust maxoff and pd_lower */
 331         opaque->maxoff++;
 332         ptr = (Pointer) BloomPageGetTuple(state, page, opaque->maxoff + 1);
 333         ((PageHeader) page)->pd_lower = ptr - page;
 334
 335         /* Assert we didn't overrun available space */
 336         Assert(((PageHeader) page)->pd_lower <= ((PageHeader) page)->pd_upper);
 337
 338         return true;
 339 }
 340
 341 /*
 342  * Allocate a new page (either by recycling, or by extending the index file)
 343  * The returned buffer is already pinned and exclusive-locked
 344  * Caller is responsible for initializing the page by calling BloomInitPage
 345  */
 346 Buffer
 347 BloomNewBuffer(Relation index)
 348 {
 349         Buffer          buffer;
 350         bool            needLock;
 351
 352         /* First, try to get a page from FSM */
 353         for (;;)
 354         {
 355                 BlockNumber blkno = GetFreeIndexPage(index);
 356
 357                 if (blkno == InvalidBlockNumber)
 358                         break;
 359
 360                 buffer = ReadBuffer(index, blkno);
 361
 362                 /*
 363                  * We have to guard against the possibility that someone else already
 364                  * recycled this page; the buffer may be locked if so.
 365                  */
 366                 if (ConditionalLockBuffer(buffer))
 367                 {
 368                         Page            page = BufferGetPage(buffer);
 369
 370                         if (PageIsNew(page))
 371                                 return buffer;  /* OK to use, if never initialized */
 372
 373                         if (BloomPageIsDeleted(page))
 374                                 return buffer;  /* OK to use */
 375
 376                         LockBuffer(buffer, BUFFER_LOCK_UNLOCK);
 377                 }
 378
 379                 /* Can't use it, so release buffer and try again */
 380                 ReleaseBuffer(buffer);
 381         }
 382
 383         /* Must extend the file */
 384         needLock = !RELATION_IS_LOCAL(index);
 385         if (needLock)
 386                 LockRelationForExtension(index, ExclusiveLock);
 387
 388         buffer = ReadBuffer(index, P_NEW);
 389         LockBuffer(buffer, BUFFER_LOCK_EXCLUSIVE);
 390
 391         if (needLock)
 392                 UnlockRelationForExtension(index, ExclusiveLock);
 393
 394         return buffer;
 395 }
 396
 397 /*
 398  * Initialize any page of a bloom index.
 399  */
 400 void
 401 BloomInitPage(Page page, uint16 flags)
 402 {
 403         BloomPageOpaque opaque;
 404
 405         PageInit(page, BLCKSZ, sizeof(BloomPageOpaqueData));
 406
 407         opaque = BloomPageGetOpaque(page);
 408         memset(opaque, 0, sizeof(BloomPageOpaqueData));
 409         opaque->flags = flags;
 410         opaque->bloom_page_id = BLOOM_PAGE_ID;
 411 }
 412
 413 /*
 414  * Fill in metapage for bloom index.
 415  */
 416 void
 417 BloomFillMetapage(Relation index, Page metaPage)
 418 {
 419         BloomOptions *opts;
 420         BloomMetaPageData *metadata;
 421
 422         /*
 423          * Choose the index's options.  If reloptions have been assigned, use
 424          * those, otherwise create default options.
 425          */
 426         opts = (BloomOptions *) index->rd_options;
 427         if (!opts)
 428                 opts = makeDefaultBloomOptions();
 429
 430         /*
 431          * Initialize contents of meta page, including a copy of the options,
 432          * which are now frozen for the life of the index.
 433          */
 434         BloomInitPage(metaPage, BLOOM_META);
 435         metadata = BloomPageGetMeta(metaPage);
 436         memset(metadata, 0, sizeof(BloomMetaPageData));
 437         metadata->magickNumber = BLOOM_MAGICK_NUMBER;
 438         metadata->opts = *opts;
 439         ((PageHeader) metaPage)->pd_lower += sizeof(BloomMetaPageData);
 440
 441         /* If this fails, probably FreeBlockNumberArray size calc is wrong: */
 442         Assert(((PageHeader) metaPage)->pd_lower <= ((PageHeader) metaPage)->pd_upper);
 443 }
 444
 445 /*
 446  * Initialize metapage for bloom index.
 447  */
 448 void
 449 BloomInitMetapage(Relation index)
 450 {
 451         Buffer          metaBuffer;
 452         Page            metaPage;
 453         GenericXLogState *state;
 454
 455         /*
 456          * Make a new page; since it is first page it should be associated with
 457          * block number 0 (BLOOM_METAPAGE_BLKNO).
 458          */
 459         metaBuffer = BloomNewBuffer(index);
 460         Assert(BufferGetBlockNumber(metaBuffer) == BLOOM_METAPAGE_BLKNO);
 461
 462         /* Initialize contents of meta page */
 463         state = GenericXLogStart(index);
 464         metaPage = GenericXLogRegisterBuffer(state, metaBuffer,
 465                                                                                  GENERIC_XLOG_FULL_IMAGE);
 466         BloomFillMetapage(index, metaPage);
 467         GenericXLogFinish(state);
 468
 469         UnlockReleaseBuffer(metaBuffer);
 470 }
 471
 472 /*
 473  * Parse reloptions for bloom index, producing a BloomOptions struct.
 474  */
 475 bytea *
 476 bloptions(Datum reloptions, bool validate)
 477 {
 478         relopt_value *options;
 479         int                     numoptions;
 480         BloomOptions *rdopts;
 481
 482         /* Parse the user-given reloptions */
 483         options = parseRelOptions(reloptions, validate, bl_relopt_kind, &numoptions);
 484         rdopts = allocateReloptStruct(sizeof(BloomOptions), options, numoptions);
 485         fillRelOptions((void *) rdopts, sizeof(BloomOptions), options, numoptions,
 486                                    validate, bl_relopt_tab, lengthof(bl_relopt_tab));
 487
 488         /* Convert signature length from # of bits to # to words, rounding up */
 489         rdopts->bloomLength = (rdopts->bloomLength + SIGNWORDBITS - 1) / SIGNWORDBITS;
 490
 491         return (bytea *) rdopts;
 492 }