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