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