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