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