Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * blutils.c
4 : * Bloom index utilities.
5 : *
6 : * Portions Copyright (c) 2016-2024, 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 194 : 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 190 : _PG_init(void)
50 : {
51 : int i;
52 : char buf[16];
53 :
54 190 : bl_relopt_kind = add_reloption_kind();
55 :
56 : /* Option for length of signature */
57 190 : add_int_reloption(bl_relopt_kind, "length",
58 : "Length of signature in bits",
59 : DEFAULT_BLOOM_LENGTH, 1, MAX_BLOOM_LENGTH,
60 : AccessExclusiveLock);
61 190 : bl_relopt_tab[0].optname = "length";
62 190 : bl_relopt_tab[0].opttype = RELOPT_TYPE_INT;
63 190 : bl_relopt_tab[0].offset = offsetof(BloomOptions, bloomLength);
64 :
65 : /* Number of bits for each possible index column: col1, col2, ... */
66 6270 : for (i = 0; i < INDEX_MAX_KEYS; i++)
67 : {
68 6080 : snprintf(buf, sizeof(buf), "col%d", i + 1);
69 6080 : 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 6080 : bl_relopt_tab[i + 1].optname = MemoryContextStrdup(TopMemoryContext,
74 : buf);
75 6080 : bl_relopt_tab[i + 1].opttype = RELOPT_TYPE_INT;
76 6080 : bl_relopt_tab[i + 1].offset = offsetof(BloomOptions, bitSize[0]) + sizeof(int) * i;
77 : }
78 190 : }
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 236 : blhandler(PG_FUNCTION_ARGS)
104 : {
105 236 : IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
106 :
107 236 : amroutine->amstrategies = BLOOM_NSTRATEGIES;
108 236 : amroutine->amsupport = BLOOM_NPROC;
109 236 : amroutine->amoptsprocnum = BLOOM_OPTIONS_PROC;
110 236 : amroutine->amcanorder = false;
111 236 : amroutine->amcanorderbyop = false;
112 236 : amroutine->amcanbackward = false;
113 236 : amroutine->amcanunique = false;
114 236 : amroutine->amcanmulticol = true;
115 236 : amroutine->amoptionalkey = true;
116 236 : amroutine->amsearcharray = false;
117 236 : amroutine->amsearchnulls = false;
118 236 : amroutine->amstorage = false;
119 236 : amroutine->amclusterable = false;
120 236 : amroutine->ampredlocks = false;
121 236 : amroutine->amcanparallel = false;
122 236 : amroutine->amcanbuildparallel = false;
123 236 : amroutine->amcaninclude = false;
124 236 : amroutine->amusemaintenanceworkmem = false;
125 236 : amroutine->amparallelvacuumoptions =
126 : VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_CLEANUP;
127 236 : amroutine->amkeytype = InvalidOid;
128 :
129 236 : amroutine->ambuild = blbuild;
130 236 : amroutine->ambuildempty = blbuildempty;
131 236 : amroutine->aminsert = blinsert;
132 236 : amroutine->aminsertcleanup = NULL;
133 236 : amroutine->ambulkdelete = blbulkdelete;
134 236 : amroutine->amvacuumcleanup = blvacuumcleanup;
135 236 : amroutine->amcanreturn = NULL;
136 236 : amroutine->amcostestimate = blcostestimate;
137 236 : amroutine->amgettreeheight = NULL;
138 236 : amroutine->amoptions = bloptions;
139 236 : amroutine->amproperty = NULL;
140 236 : amroutine->ambuildphasename = NULL;
141 236 : amroutine->amvalidate = blvalidate;
142 236 : amroutine->amadjustmembers = NULL;
143 236 : amroutine->ambeginscan = blbeginscan;
144 236 : amroutine->amrescan = blrescan;
145 236 : amroutine->amgettuple = NULL;
146 236 : amroutine->amgetbitmap = blgetbitmap;
147 236 : amroutine->amendscan = blendscan;
148 236 : amroutine->ammarkpos = NULL;
149 236 : amroutine->amrestrpos = NULL;
150 236 : amroutine->amestimateparallelscan = NULL;
151 236 : amroutine->aminitparallelscan = NULL;
152 236 : amroutine->amparallelrescan = NULL;
153 :
154 236 : PG_RETURN_POINTER(amroutine);
155 : }
156 :
157 : /*
158 : * Fill BloomState structure for particular index.
159 : */
160 : void
161 208806 : initBloomState(BloomState *state, Relation index)
162 : {
163 : int i;
164 :
165 208806 : state->nColumns = index->rd_att->natts;
166 :
167 : /* Initialize hash function for each attribute */
168 626418 : for (i = 0; i < index->rd_att->natts; i++)
169 : {
170 417612 : fmgr_info_copy(&(state->hashFn[i]),
171 417612 : index_getprocinfo(index, i + 1, BLOOM_HASH_PROC),
172 : CurrentMemoryContext);
173 417612 : state->collations[i] = index->rd_indcollation[i];
174 : }
175 :
176 : /* Initialize amcache if needed with options from metapage */
177 208806 : if (!index->rd_amcache)
178 : {
179 : Buffer buffer;
180 : Page page;
181 : BloomMetaPageData *meta;
182 : BloomOptions *opts;
183 :
184 182 : opts = MemoryContextAlloc(index->rd_indexcxt, sizeof(BloomOptions));
185 :
186 182 : buffer = ReadBuffer(index, BLOOM_METAPAGE_BLKNO);
187 182 : LockBuffer(buffer, BUFFER_LOCK_SHARE);
188 :
189 182 : page = BufferGetPage(buffer);
190 :
191 182 : if (!BloomPageIsMeta(page))
192 0 : elog(ERROR, "Relation is not a bloom index");
193 182 : meta = BloomPageGetMeta(BufferGetPage(buffer));
194 :
195 182 : if (meta->magickNumber != BLOOM_MAGICK_NUMBER)
196 0 : elog(ERROR, "Relation is not a bloom index");
197 :
198 182 : *opts = meta->opts;
199 :
200 182 : UnlockReleaseBuffer(buffer);
201 :
202 182 : index->rd_amcache = (void *) opts;
203 : }
204 :
205 208806 : memcpy(&state->opts, index->rd_amcache, sizeof(state->opts));
206 208806 : state->sizeOfBloomTuple = BLOOMTUPLEHDRSZ +
207 208806 : sizeof(BloomSignatureWord) * state->opts.bloomLength;
208 208806 : }
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
222 1730866 : 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. */
238 1730866 : hi = next / 127773;
239 1730866 : lo = next % 127773;
240 1730866 : x = 16807 * lo - 2836 * hi;
241 1730866 : if (x < 0)
242 350512 : x += 0x7fffffff;
243 1730866 : next = x;
244 : /* Transform to [0, 0x7ffffffd] range. */
245 1730866 : return (x - 1);
246 : }
247 :
248 : static void
249 984064 : mySrand(uint32 seed)
250 : {
251 984064 : next = seed;
252 : /* Transform to [1, 0x7ffffffe] range. */
253 984064 : next = (next % 0x7ffffffe) + 1;
254 984064 : }
255 :
256 : /*
257 : * Add bits of given value to the signature.
258 : */
259 : void
260 492032 : 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 : */
271 492032 : 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 : */
278 492032 : hashVal = DatumGetInt32(FunctionCall1Coll(&state->hashFn[attno], state->collations[attno], value));
279 492032 : mySrand(hashVal ^ myRand());
280 :
281 1730866 : for (j = 0; j < state->opts.bitSize[attno]; j++)
282 : {
283 : /* prevent multiple evaluation in SETBIT macro */
284 1238834 : nBit = myRand() % (state->opts.bloomLength * SIGNWORDBITS);
285 1238834 : SETBIT(sign, nBit);
286 : }
287 492032 : }
288 :
289 : /*
290 : * Make bloom tuple from values.
291 : */
292 : BloomTuple *
293 245500 : BloomFormTuple(BloomState *state, ItemPointer iptr, Datum *values, bool *isnull)
294 : {
295 : int i;
296 245500 : BloomTuple *res = (BloomTuple *) palloc0(state->sizeOfBloomTuple);
297 :
298 245500 : res->heapPtr = *iptr;
299 :
300 : /* Blooming each column */
301 736500 : for (i = 0; i < state->nColumns; i++)
302 : {
303 : /* skip nulls */
304 491000 : if (isnull[i])
305 0 : continue;
306 :
307 491000 : signValue(state, res->sign, values[i], i);
308 : }
309 :
310 245500 : 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 247076 : 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 */
325 : Assert(!PageIsNew(page) && !BloomPageIsDeleted(page));
326 :
327 : /* Does new tuple fit on the page? */
328 247076 : if (BloomPageGetFreeSpace(state, page) < state->sizeOfBloomTuple)
329 1576 : return false;
330 :
331 : /* Copy new tuple to the end of page */
332 245500 : opaque = BloomPageGetOpaque(page);
333 245500 : itup = BloomPageGetTuple(state, page, opaque->maxoff + 1);
334 245500 : memcpy((Pointer) itup, (Pointer) tuple, state->sizeOfBloomTuple);
335 :
336 : /* Adjust maxoff and pd_lower */
337 245500 : opaque->maxoff++;
338 245500 : ptr = (Pointer) BloomPageGetTuple(state, page, opaque->maxoff + 1);
339 245500 : ((PageHeader) page)->pd_lower = ptr - page;
340 :
341 : /* Assert we didn't overrun available space */
342 : Assert(((PageHeader) page)->pd_lower <= ((PageHeader) page)->pd_upper);
343 :
344 245500 : 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 298 : BloomNewBuffer(Relation index)
354 : {
355 : Buffer buffer;
356 :
357 : /* First, try to get a page from FSM */
358 : for (;;)
359 0 : {
360 298 : BlockNumber blkno = GetFreeIndexPage(index);
361 :
362 298 : if (blkno == InvalidBlockNumber)
363 296 : break;
364 :
365 2 : 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.
370 : */
371 2 : if (ConditionalLockBuffer(buffer))
372 : {
373 2 : Page page = BufferGetPage(buffer);
374 :
375 2 : if (PageIsNew(page))
376 0 : return buffer; /* OK to use, if never initialized */
377 :
378 2 : if (BloomPageIsDeleted(page))
379 2 : return buffer; /* OK to use */
380 :
381 0 : LockBuffer(buffer, BUFFER_LOCK_UNLOCK);
382 : }
383 :
384 : /* Can't use it, so release buffer and try again */
385 0 : ReleaseBuffer(buffer);
386 : }
387 :
388 : /* Must extend the file */
389 296 : buffer = ExtendBufferedRel(BMR_REL(index), MAIN_FORKNUM, NULL,
390 : EB_LOCK_FIRST);
391 :
392 296 : return buffer;
393 : }
394 :
395 : /*
396 : * Initialize any page of a bloom index.
397 : */
398 : void
399 310 : BloomInitPage(Page page, uint16 flags)
400 : {
401 : BloomPageOpaque opaque;
402 :
403 310 : PageInit(page, BLCKSZ, sizeof(BloomPageOpaqueData));
404 :
405 310 : opaque = BloomPageGetOpaque(page);
406 310 : opaque->flags = flags;
407 310 : opaque->bloom_page_id = BLOOM_PAGE_ID;
408 310 : }
409 :
410 : /*
411 : * Fill in metapage for bloom index.
412 : */
413 : void
414 12 : BloomFillMetapage(Relation index, Page metaPage)
415 : {
416 : BloomOptions *opts;
417 : BloomMetaPageData *metadata;
418 :
419 : /*
420 : * Choose the index's options. If reloptions have been assigned, use
421 : * those, otherwise create default options.
422 : */
423 12 : opts = (BloomOptions *) index->rd_options;
424 12 : if (!opts)
425 0 : opts = makeDefaultBloomOptions();
426 :
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 : */
431 12 : BloomInitPage(metaPage, BLOOM_META);
432 12 : metadata = BloomPageGetMeta(metaPage);
433 12 : memset(metadata, 0, sizeof(BloomMetaPageData));
434 12 : metadata->magickNumber = BLOOM_MAGICK_NUMBER;
435 12 : metadata->opts = *opts;
436 12 : ((PageHeader) metaPage)->pd_lower += sizeof(BloomMetaPageData);
437 :
438 : /* If this fails, probably FreeBlockNumberArray size calc is wrong: */
439 : Assert(((PageHeader) metaPage)->pd_lower <= ((PageHeader) metaPage)->pd_upper);
440 12 : }
441 :
442 : /*
443 : * Initialize metapage for bloom index.
444 : */
445 : void
446 12 : BloomInitMetapage(Relation index, ForkNumber forknum)
447 : {
448 : Buffer metaBuffer;
449 : Page metaPage;
450 : GenericXLogState *state;
451 :
452 : /*
453 : * Make a new page; since it is first page it should be associated with
454 : * block number 0 (BLOOM_METAPAGE_BLKNO). No need to hold the extension
455 : * lock because there cannot be concurrent inserters yet.
456 : */
457 12 : metaBuffer = ReadBufferExtended(index, forknum, P_NEW, RBM_NORMAL, NULL);
458 12 : LockBuffer(metaBuffer, BUFFER_LOCK_EXCLUSIVE);
459 : Assert(BufferGetBlockNumber(metaBuffer) == BLOOM_METAPAGE_BLKNO);
460 :
461 : /* Initialize contents of meta page */
462 12 : state = GenericXLogStart(index);
463 12 : metaPage = GenericXLogRegisterBuffer(state, metaBuffer,
464 : GENERIC_XLOG_FULL_IMAGE);
465 12 : BloomFillMetapage(index, metaPage);
466 12 : GenericXLogFinish(state);
467 :
468 12 : UnlockReleaseBuffer(metaBuffer);
469 12 : }
470 :
471 : /*
472 : * Parse reloptions for bloom index, producing a BloomOptions struct.
473 : */
474 : bytea *
475 266 : bloptions(Datum reloptions, bool validate)
476 : {
477 : BloomOptions *rdopts;
478 :
479 : /* Parse the user-given reloptions */
480 266 : rdopts = (BloomOptions *) build_reloptions(reloptions, validate,
481 : bl_relopt_kind,
482 : sizeof(BloomOptions),
483 : bl_relopt_tab,
484 : lengthof(bl_relopt_tab));
485 :
486 : /* Convert signature length from # of bits to # to words, rounding up */
487 262 : if (rdopts)
488 262 : rdopts->bloomLength = (rdopts->bloomLength + SIGNWORDBITS - 1) / SIGNWORDBITS;
489 :
490 262 : return (bytea *) rdopts;
491 : }
|
