Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * tidbitmap.c
4 : * PostgreSQL tuple-id (TID) bitmap package
5 : *
6 : * This module provides bitmap data structures that are spiritually
7 : * similar to Bitmapsets, but are specially adapted to store sets of
8 : * tuple identifiers (TIDs), or ItemPointers. In particular, the division
9 : * of an ItemPointer into BlockNumber and OffsetNumber is catered for.
10 : * Also, since we wish to be able to store very large tuple sets in
11 : * memory with this data structure, we support "lossy" storage, in which
12 : * we no longer remember individual tuple offsets on a page but only the
13 : * fact that a particular page needs to be visited.
14 : *
15 : * The "lossy" storage uses one bit per disk page, so at the standard 8K
16 : * BLCKSZ, we can represent all pages in 64Gb of disk space in about 1Mb
17 : * of memory. People pushing around tables of that size should have a
18 : * couple of Mb to spare, so we don't worry about providing a second level
19 : * of lossiness. In theory we could fall back to page ranges at some
20 : * point, but for now that seems useless complexity.
21 : *
22 : * We also support the notion of candidate matches, or rechecking. This
23 : * means we know that a search need visit only some tuples on a page,
24 : * but we are not certain that all of those tuples are real matches.
25 : * So the eventual heap scan must recheck the quals for these tuples only,
26 : * rather than rechecking the quals for all tuples on the page as in the
27 : * lossy-bitmap case. Rechecking can be specified when TIDs are inserted
28 : * into a bitmap, and it can also happen internally when we AND a lossy
29 : * and a non-lossy page.
30 : *
31 : *
32 : * Copyright (c) 2003-2026, PostgreSQL Global Development Group
33 : *
34 : * IDENTIFICATION
35 : * src/backend/nodes/tidbitmap.c
36 : *
37 : *-------------------------------------------------------------------------
38 : */
39 : #include "postgres.h"
40 :
41 : #include <limits.h>
42 :
43 : #include "access/htup_details.h"
44 : #include "common/hashfn.h"
45 : #include "common/int.h"
46 : #include "nodes/bitmapset.h"
47 : #include "nodes/tidbitmap.h"
48 : #include "storage/lwlock.h"
49 : #include "utils/dsa.h"
50 :
51 : /*
52 : * When we have to switch over to lossy storage, we use a data structure
53 : * with one bit per page, where all pages having the same number DIV
54 : * PAGES_PER_CHUNK are aggregated into one chunk. When a chunk is present
55 : * and has the bit set for a given page, there must not be a per-page entry
56 : * for that page in the page table.
57 : *
58 : * We actually store both exact pages and lossy chunks in the same hash
59 : * table, using identical data structures. (This is because the memory
60 : * management for hashtables doesn't easily/efficiently allow space to be
61 : * transferred easily from one hashtable to another.) Therefore it's best
62 : * if PAGES_PER_CHUNK is the same as TBM_MAX_TUPLES_PER_PAGE, or at least not
63 : * too different. But we also want PAGES_PER_CHUNK to be a power of 2 to
64 : * avoid expensive integer remainder operations. So, define it like this:
65 : */
66 : #define PAGES_PER_CHUNK (BLCKSZ / 32)
67 :
68 : /* We use BITS_PER_BITMAPWORD and typedef bitmapword from nodes/bitmapset.h */
69 :
70 : #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)
71 : #define BITNUM(x) ((x) % BITS_PER_BITMAPWORD)
72 :
73 : /* number of active words for an exact page: */
74 : #define WORDS_PER_PAGE ((TBM_MAX_TUPLES_PER_PAGE - 1) / BITS_PER_BITMAPWORD + 1)
75 : /* number of active words for a lossy chunk: */
76 : #define WORDS_PER_CHUNK ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1)
77 :
78 : /*
79 : * The hashtable entries are represented by this data structure. For
80 : * an exact page, blockno is the page number and bit k of the bitmap
81 : * represents tuple offset k+1. For a lossy chunk, blockno is the first
82 : * page in the chunk (this must be a multiple of PAGES_PER_CHUNK) and
83 : * bit k represents page blockno+k. Note that it is not possible to
84 : * have exact storage for the first page of a chunk if we are using
85 : * lossy storage for any page in the chunk's range, since the same
86 : * hashtable entry has to serve both purposes.
87 : *
88 : * recheck is used only on exact pages --- it indicates that although
89 : * only the stated tuples need be checked, the full index qual condition
90 : * must be checked for each (ie, these are candidate matches).
91 : */
92 : typedef struct PagetableEntry
93 : {
94 : BlockNumber blockno; /* page number (hashtable key) */
95 : char status; /* hash entry status */
96 : bool ischunk; /* T = lossy storage, F = exact */
97 : bool recheck; /* should the tuples be rechecked? */
98 : bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)];
99 : } PagetableEntry;
100 :
101 : /*
102 : * Holds array of pagetable entries.
103 : */
104 : typedef struct PTEntryArray
105 : {
106 : pg_atomic_uint32 refcount; /* no. of iterator attached */
107 : PagetableEntry ptentry[FLEXIBLE_ARRAY_MEMBER];
108 : } PTEntryArray;
109 :
110 : /*
111 : * We want to avoid the overhead of creating the hashtable, which is
112 : * comparatively large, when not necessary. Particularly when we are using a
113 : * bitmap scan on the inside of a nestloop join: a bitmap may well live only
114 : * long enough to accumulate one entry in such cases. We therefore avoid
115 : * creating an actual hashtable until we need two pagetable entries. When
116 : * just one pagetable entry is needed, we store it in a fixed field of
117 : * TIDBitMap. (NOTE: we don't get rid of the hashtable if the bitmap later
118 : * shrinks down to zero or one page again. So, status can be TBM_HASH even
119 : * when nentries is zero or one.)
120 : */
121 : typedef enum
122 : {
123 : TBM_EMPTY, /* no hashtable, nentries == 0 */
124 : TBM_ONE_PAGE, /* entry1 contains the single entry */
125 : TBM_HASH, /* pagetable is valid, entry1 is not */
126 : } TBMStatus;
127 :
128 : /*
129 : * Current iterating state of the TBM.
130 : */
131 : typedef enum
132 : {
133 : TBM_NOT_ITERATING, /* not yet converted to page and chunk array */
134 : TBM_ITERATING_PRIVATE, /* converted to local page and chunk array */
135 : TBM_ITERATING_SHARED, /* converted to shared page and chunk array */
136 : } TBMIteratingState;
137 :
138 : /*
139 : * Here is the representation for a whole TIDBitMap:
140 : */
141 : struct TIDBitmap
142 : {
143 : NodeTag type; /* to make it a valid Node */
144 : MemoryContext mcxt; /* memory context containing me */
145 : TBMStatus status; /* see codes above */
146 : struct pagetable_hash *pagetable; /* hash table of PagetableEntry's */
147 : int nentries; /* number of entries in pagetable */
148 : int maxentries; /* limit on same to meet maxbytes */
149 : int npages; /* number of exact entries in pagetable */
150 : int nchunks; /* number of lossy entries in pagetable */
151 : TBMIteratingState iterating; /* tbm_begin_iterate called? */
152 : uint32 lossify_start; /* offset to start lossifying hashtable at */
153 : PagetableEntry entry1; /* used when status == TBM_ONE_PAGE */
154 : /* these are valid when iterating is true: */
155 : PagetableEntry **spages; /* sorted exact-page list, or NULL */
156 : PagetableEntry **schunks; /* sorted lossy-chunk list, or NULL */
157 : dsa_pointer dsapagetable; /* dsa_pointer to the element array */
158 : dsa_pointer dsapagetableold; /* dsa_pointer to the old element array */
159 : dsa_pointer ptpages; /* dsa_pointer to the page array */
160 : dsa_pointer ptchunks; /* dsa_pointer to the chunk array */
161 : dsa_area *dsa; /* reference to per-query dsa area */
162 : };
163 :
164 : /*
165 : * When iterating over a backend-local bitmap in sorted order, a
166 : * TBMPrivateIterator is used to track our progress. There can be several
167 : * iterators scanning the same bitmap concurrently. Note that the bitmap
168 : * becomes read-only as soon as any iterator is created.
169 : */
170 : struct TBMPrivateIterator
171 : {
172 : TIDBitmap *tbm; /* TIDBitmap we're iterating over */
173 : int spageptr; /* next spages index */
174 : int schunkptr; /* next schunks index */
175 : int schunkbit; /* next bit to check in current schunk */
176 : };
177 :
178 : /*
179 : * Holds the shared members of the iterator so that multiple processes
180 : * can jointly iterate.
181 : */
182 : typedef struct TBMSharedIteratorState
183 : {
184 : int nentries; /* number of entries in pagetable */
185 : int maxentries; /* limit on same to meet maxbytes */
186 : int npages; /* number of exact entries in pagetable */
187 : int nchunks; /* number of lossy entries in pagetable */
188 : dsa_pointer pagetable; /* dsa pointers to head of pagetable data */
189 : dsa_pointer spages; /* dsa pointer to page array */
190 : dsa_pointer schunks; /* dsa pointer to chunk array */
191 : LWLock lock; /* lock to protect below members */
192 : int spageptr; /* next spages index */
193 : int schunkptr; /* next schunks index */
194 : int schunkbit; /* next bit to check in current schunk */
195 : } TBMSharedIteratorState;
196 :
197 : /*
198 : * pagetable iteration array.
199 : */
200 : typedef struct PTIterationArray
201 : {
202 : pg_atomic_uint32 refcount; /* no. of iterator attached */
203 : int index[FLEXIBLE_ARRAY_MEMBER]; /* index array */
204 : } PTIterationArray;
205 :
206 : /*
207 : * same as TBMPrivateIterator, but it is used for joint iteration, therefore
208 : * this also holds a reference to the shared state.
209 : */
210 : struct TBMSharedIterator
211 : {
212 : TBMSharedIteratorState *state; /* shared state */
213 : PTEntryArray *ptbase; /* pagetable element array */
214 : PTIterationArray *ptpages; /* sorted exact page index list */
215 : PTIterationArray *ptchunks; /* sorted lossy page index list */
216 : };
217 :
218 : /* Local function prototypes */
219 : static void tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage);
220 : static bool tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage,
221 : const TIDBitmap *b);
222 : static const PagetableEntry *tbm_find_pageentry(const TIDBitmap *tbm,
223 : BlockNumber pageno);
224 : static PagetableEntry *tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno);
225 : static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno);
226 : static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno);
227 : static void tbm_lossify(TIDBitmap *tbm);
228 : static int tbm_comparator(const void *left, const void *right);
229 : static int tbm_shared_comparator(const void *left, const void *right,
230 : void *arg);
231 :
232 : /* define hashtable mapping block numbers to PagetableEntry's */
233 : #define SH_USE_NONDEFAULT_ALLOCATOR
234 : #define SH_PREFIX pagetable
235 : #define SH_ELEMENT_TYPE PagetableEntry
236 : #define SH_KEY_TYPE BlockNumber
237 : #define SH_KEY blockno
238 : #define SH_HASH_KEY(tb, key) murmurhash32(key)
239 : #define SH_EQUAL(tb, a, b) a == b
240 : #define SH_SCOPE static inline
241 : #define SH_DEFINE
242 : #define SH_DECLARE
243 : #include "lib/simplehash.h"
244 :
245 :
246 : /*
247 : * tbm_create - create an initially-empty bitmap
248 : *
249 : * The bitmap will live in the memory context that is CurrentMemoryContext
250 : * at the time of this call. It will be limited to (approximately) maxbytes
251 : * total memory consumption. If the DSA passed to this function is not NULL
252 : * then the memory for storing elements of the underlying page table will
253 : * be allocated from the DSA.
254 : */
255 : TIDBitmap *
256 13650 : tbm_create(Size maxbytes, dsa_area *dsa)
257 : {
258 : TIDBitmap *tbm;
259 :
260 : /* Create the TIDBitmap struct and zero all its fields */
261 13650 : tbm = makeNode(TIDBitmap);
262 :
263 13650 : tbm->mcxt = CurrentMemoryContext;
264 13650 : tbm->status = TBM_EMPTY;
265 :
266 13650 : tbm->maxentries = tbm_calculate_entries(maxbytes);
267 13650 : tbm->lossify_start = 0;
268 13650 : tbm->dsa = dsa;
269 13650 : tbm->dsapagetable = InvalidDsaPointer;
270 13650 : tbm->dsapagetableold = InvalidDsaPointer;
271 13650 : tbm->ptpages = InvalidDsaPointer;
272 13650 : tbm->ptchunks = InvalidDsaPointer;
273 :
274 13650 : return tbm;
275 : }
276 :
277 : /*
278 : * Actually create the hashtable. Since this is a moderately expensive
279 : * proposition, we don't do it until we have to.
280 : */
281 : static void
282 4964 : tbm_create_pagetable(TIDBitmap *tbm)
283 : {
284 : Assert(tbm->status != TBM_HASH);
285 : Assert(tbm->pagetable == NULL);
286 :
287 4964 : tbm->pagetable = pagetable_create(tbm->mcxt, 128, tbm);
288 :
289 : /* If entry1 is valid, push it into the hashtable */
290 4964 : if (tbm->status == TBM_ONE_PAGE)
291 : {
292 : PagetableEntry *page;
293 : bool found;
294 : char oldstatus;
295 :
296 3530 : page = pagetable_insert(tbm->pagetable,
297 : tbm->entry1.blockno,
298 : &found);
299 : Assert(!found);
300 3530 : oldstatus = page->status;
301 3530 : memcpy(page, &tbm->entry1, sizeof(PagetableEntry));
302 3530 : page->status = oldstatus;
303 : }
304 :
305 4964 : tbm->status = TBM_HASH;
306 4964 : }
307 :
308 : /*
309 : * tbm_free - free a TIDBitmap
310 : */
311 : void
312 13593 : tbm_free(TIDBitmap *tbm)
313 : {
314 13593 : if (tbm->pagetable)
315 4962 : pagetable_destroy(tbm->pagetable);
316 13593 : if (tbm->spages)
317 3388 : pfree(tbm->spages);
318 13593 : if (tbm->schunks)
319 1443 : pfree(tbm->schunks);
320 13593 : pfree(tbm);
321 13593 : }
322 :
323 : /*
324 : * tbm_free_shared_area - free shared state
325 : *
326 : * Free shared iterator state, Also free shared pagetable and iterator arrays
327 : * memory if they are not referred by any of the shared iterator i.e recount
328 : * is becomes 0.
329 : */
330 : void
331 27 : tbm_free_shared_area(dsa_area *dsa, dsa_pointer dp)
332 : {
333 27 : TBMSharedIteratorState *istate = dsa_get_address(dsa, dp);
334 : PTEntryArray *ptbase;
335 : PTIterationArray *ptpages;
336 : PTIterationArray *ptchunks;
337 :
338 27 : if (DsaPointerIsValid(istate->pagetable))
339 : {
340 27 : ptbase = dsa_get_address(dsa, istate->pagetable);
341 27 : if (pg_atomic_sub_fetch_u32(&ptbase->refcount, 1) == 0)
342 27 : dsa_free(dsa, istate->pagetable);
343 : }
344 27 : if (DsaPointerIsValid(istate->spages))
345 : {
346 27 : ptpages = dsa_get_address(dsa, istate->spages);
347 27 : if (pg_atomic_sub_fetch_u32(&ptpages->refcount, 1) == 0)
348 27 : dsa_free(dsa, istate->spages);
349 : }
350 27 : if (DsaPointerIsValid(istate->schunks))
351 : {
352 0 : ptchunks = dsa_get_address(dsa, istate->schunks);
353 0 : if (pg_atomic_sub_fetch_u32(&ptchunks->refcount, 1) == 0)
354 0 : dsa_free(dsa, istate->schunks);
355 : }
356 :
357 27 : dsa_free(dsa, dp);
358 27 : }
359 :
360 : /*
361 : * tbm_add_tuples - add some tuple IDs to a TIDBitmap
362 : *
363 : * If recheck is true, then the recheck flag will be set in the
364 : * TBMIterateResult when any of these tuples are reported out.
365 : */
366 : void
367 3394920 : tbm_add_tuples(TIDBitmap *tbm, const ItemPointerData *tids, int ntids,
368 : bool recheck)
369 : {
370 3394920 : BlockNumber currblk = InvalidBlockNumber;
371 3394920 : PagetableEntry *page = NULL; /* only valid when currblk is valid */
372 :
373 : Assert(tbm->iterating == TBM_NOT_ITERATING);
374 7880569 : for (int i = 0; i < ntids; i++)
375 : {
376 4485649 : BlockNumber blk = ItemPointerGetBlockNumber(tids + i);
377 4485649 : OffsetNumber off = ItemPointerGetOffsetNumber(tids + i);
378 : int wordnum,
379 : bitnum;
380 :
381 : /* safety check to ensure we don't overrun bit array bounds */
382 4485649 : if (off < 1 || off > TBM_MAX_TUPLES_PER_PAGE)
383 0 : elog(ERROR, "tuple offset out of range: %u", off);
384 :
385 : /*
386 : * Look up target page unless we already did. This saves cycles when
387 : * the input includes consecutive tuples on the same page, which is
388 : * common enough to justify an extra test here.
389 : */
390 4485649 : if (blk != currblk)
391 : {
392 3783275 : if (tbm_page_is_lossy(tbm, blk))
393 1428 : page = NULL; /* remember page is lossy */
394 : else
395 3781847 : page = tbm_get_pageentry(tbm, blk);
396 3783275 : currblk = blk;
397 : }
398 :
399 4485649 : if (page == NULL)
400 1428 : continue; /* whole page is already marked */
401 :
402 4484221 : if (page->ischunk)
403 : {
404 : /* The page is a lossy chunk header, set bit for itself */
405 0 : wordnum = bitnum = 0;
406 : }
407 : else
408 : {
409 : /* Page is exact, so set bit for individual tuple */
410 4484221 : wordnum = WORDNUM(off - 1);
411 4484221 : bitnum = BITNUM(off - 1);
412 : }
413 4484221 : page->words[wordnum] |= ((bitmapword) 1 << bitnum);
414 4484221 : page->recheck |= recheck;
415 :
416 4484221 : if (tbm->nentries > tbm->maxentries)
417 : {
418 18 : tbm_lossify(tbm);
419 : /* Page could have been converted to lossy, so force new lookup */
420 18 : currblk = InvalidBlockNumber;
421 : }
422 : }
423 3394920 : }
424 :
425 : /*
426 : * tbm_add_page - add a whole page to a TIDBitmap
427 : *
428 : * This causes the whole page to be reported (with the recheck flag)
429 : * when the TIDBitmap is scanned.
430 : */
431 : void
432 73990 : tbm_add_page(TIDBitmap *tbm, BlockNumber pageno)
433 : {
434 : /* Enter the page in the bitmap, or mark it lossy if already present */
435 73990 : tbm_mark_page_lossy(tbm, pageno);
436 : /* If we went over the memory limit, lossify some more pages */
437 73990 : if (tbm->nentries > tbm->maxentries)
438 0 : tbm_lossify(tbm);
439 73990 : }
440 :
441 : /*
442 : * tbm_union - set union
443 : *
444 : * a is modified in-place, b is not changed
445 : */
446 : void
447 0 : tbm_union(TIDBitmap *a, const TIDBitmap *b)
448 : {
449 : Assert(!a->iterating);
450 : /* Nothing to do if b is empty */
451 0 : if (b->nentries == 0)
452 0 : return;
453 : /* Scan through chunks and pages in b, merge into a */
454 0 : if (b->status == TBM_ONE_PAGE)
455 0 : tbm_union_page(a, &b->entry1);
456 : else
457 : {
458 : pagetable_iterator i;
459 : PagetableEntry *bpage;
460 :
461 : Assert(b->status == TBM_HASH);
462 0 : pagetable_start_iterate(b->pagetable, &i);
463 0 : while ((bpage = pagetable_iterate(b->pagetable, &i)) != NULL)
464 0 : tbm_union_page(a, bpage);
465 : }
466 : }
467 :
468 : /* Process one page of b during a union op */
469 : static void
470 0 : tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage)
471 : {
472 : PagetableEntry *apage;
473 :
474 0 : if (bpage->ischunk)
475 : {
476 : /* Scan b's chunk, mark each indicated page lossy in a */
477 0 : for (int wordnum = 0; wordnum < WORDS_PER_CHUNK; wordnum++)
478 : {
479 0 : bitmapword w = bpage->words[wordnum];
480 :
481 0 : if (w != 0)
482 : {
483 : BlockNumber pg;
484 :
485 0 : pg = bpage->blockno + (wordnum * BITS_PER_BITMAPWORD);
486 0 : while (w != 0)
487 : {
488 0 : if (w & 1)
489 0 : tbm_mark_page_lossy(a, pg);
490 0 : pg++;
491 0 : w >>= 1;
492 : }
493 : }
494 : }
495 : }
496 0 : else if (tbm_page_is_lossy(a, bpage->blockno))
497 : {
498 : /* page is already lossy in a, nothing to do */
499 0 : return;
500 : }
501 : else
502 : {
503 0 : apage = tbm_get_pageentry(a, bpage->blockno);
504 0 : if (apage->ischunk)
505 : {
506 : /* The page is a lossy chunk header, set bit for itself */
507 0 : apage->words[0] |= ((bitmapword) 1 << 0);
508 : }
509 : else
510 : {
511 : /* Both pages are exact, merge at the bit level */
512 0 : for (int wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
513 0 : apage->words[wordnum] |= bpage->words[wordnum];
514 0 : apage->recheck |= bpage->recheck;
515 : }
516 : }
517 :
518 0 : if (a->nentries > a->maxentries)
519 0 : tbm_lossify(a);
520 : }
521 :
522 : /*
523 : * tbm_intersect - set intersection
524 : *
525 : * a is modified in-place, b is not changed
526 : */
527 : void
528 101 : tbm_intersect(TIDBitmap *a, const TIDBitmap *b)
529 : {
530 : Assert(!a->iterating);
531 : /* Nothing to do if a is empty */
532 101 : if (a->nentries == 0)
533 0 : return;
534 : /* Scan through chunks and pages in a, try to match to b */
535 101 : if (a->status == TBM_ONE_PAGE)
536 : {
537 0 : if (tbm_intersect_page(a, &a->entry1, b))
538 : {
539 : /* Page is now empty, remove it from a */
540 : Assert(!a->entry1.ischunk);
541 0 : a->npages--;
542 0 : a->nentries--;
543 : Assert(a->nentries == 0);
544 0 : a->status = TBM_EMPTY;
545 : }
546 : }
547 : else
548 : {
549 : pagetable_iterator i;
550 : PagetableEntry *apage;
551 :
552 : Assert(a->status == TBM_HASH);
553 101 : pagetable_start_iterate(a->pagetable, &i);
554 5899 : while ((apage = pagetable_iterate(a->pagetable, &i)) != NULL)
555 : {
556 5697 : if (tbm_intersect_page(a, apage, b))
557 : {
558 : /* Page or chunk is now empty, remove it from a */
559 5275 : if (apage->ischunk)
560 0 : a->nchunks--;
561 : else
562 5275 : a->npages--;
563 5275 : a->nentries--;
564 5275 : if (!pagetable_delete(a->pagetable, apage->blockno))
565 0 : elog(ERROR, "hash table corrupted");
566 : }
567 : }
568 : }
569 : }
570 :
571 : /*
572 : * Process one page of a during an intersection op
573 : *
574 : * Returns true if apage is now empty and should be deleted from a
575 : */
576 : static bool
577 5697 : tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
578 : {
579 : const PagetableEntry *bpage;
580 :
581 5697 : if (apage->ischunk)
582 : {
583 : /* Scan each bit in chunk, try to clear */
584 30 : bool candelete = true;
585 :
586 150 : for (int wordnum = 0; wordnum < WORDS_PER_CHUNK; wordnum++)
587 : {
588 120 : bitmapword w = apage->words[wordnum];
589 :
590 120 : if (w != 0)
591 : {
592 108 : bitmapword neww = w;
593 : BlockNumber pg;
594 : int bitnum;
595 :
596 108 : pg = apage->blockno + (wordnum * BITS_PER_BITMAPWORD);
597 108 : bitnum = 0;
598 6606 : while (w != 0)
599 : {
600 6498 : if (w & 1)
601 : {
602 3360 : if (!tbm_page_is_lossy(b, pg) &&
603 252 : tbm_find_pageentry(b, pg) == NULL)
604 : {
605 : /* Page is not in b at all, lose lossy bit */
606 0 : neww &= ~((bitmapword) 1 << bitnum);
607 : }
608 : }
609 6498 : pg++;
610 6498 : bitnum++;
611 6498 : w >>= 1;
612 : }
613 108 : apage->words[wordnum] = neww;
614 108 : if (neww != 0)
615 108 : candelete = false;
616 : }
617 : }
618 30 : return candelete;
619 : }
620 5667 : else if (tbm_page_is_lossy(b, apage->blockno))
621 : {
622 : /*
623 : * Some of the tuples in 'a' might not satisfy the quals for 'b', but
624 : * because the page 'b' is lossy, we don't know which ones. Therefore
625 : * we mark 'a' as requiring rechecks, to indicate that at most those
626 : * tuples set in 'a' are matches.
627 : */
628 0 : apage->recheck = true;
629 0 : return false;
630 : }
631 : else
632 : {
633 5667 : bool candelete = true;
634 :
635 5667 : bpage = tbm_find_pageentry(b, apage->blockno);
636 5667 : if (bpage != NULL)
637 : {
638 : /* Both pages are exact, merge at the bit level */
639 : Assert(!bpage->ischunk);
640 28044 : for (int wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
641 : {
642 23370 : apage->words[wordnum] &= bpage->words[wordnum];
643 23370 : if (apage->words[wordnum] != 0)
644 392 : candelete = false;
645 : }
646 4674 : apage->recheck |= bpage->recheck;
647 : }
648 : /* If there is no matching b page, we can just delete the a page */
649 5667 : return candelete;
650 : }
651 : }
652 :
653 : /*
654 : * tbm_is_empty - is a TIDBitmap completely empty?
655 : */
656 : bool
657 642 : tbm_is_empty(const TIDBitmap *tbm)
658 : {
659 642 : return (tbm->nentries == 0);
660 : }
661 :
662 : /*
663 : * tbm_begin_private_iterate - prepare to iterate through a TIDBitmap
664 : *
665 : * The TBMPrivateIterator struct is created in the caller's memory context.
666 : * For a clean shutdown of the iteration, call tbm_end_private_iterate; but
667 : * it's okay to just allow the memory context to be released, too. It is
668 : * caller's responsibility not to touch the TBMPrivateIterator anymore once
669 : * the TIDBitmap is freed.
670 : *
671 : * NB: after this is called, it is no longer allowed to modify the contents
672 : * of the bitmap. However, you can call this multiple times to scan the
673 : * contents repeatedly, including parallel scans.
674 : */
675 : TBMPrivateIterator *
676 13433 : tbm_begin_private_iterate(TIDBitmap *tbm)
677 : {
678 : TBMPrivateIterator *iterator;
679 :
680 : Assert(tbm->iterating != TBM_ITERATING_SHARED);
681 :
682 : /*
683 : * Create the TBMPrivateIterator struct, with enough trailing space to
684 : * serve the needs of the TBMIterateResult sub-struct.
685 : */
686 13433 : iterator = palloc_object(TBMPrivateIterator);
687 13433 : iterator->tbm = tbm;
688 :
689 : /*
690 : * Initialize iteration pointers.
691 : */
692 13433 : iterator->spageptr = 0;
693 13433 : iterator->schunkptr = 0;
694 13433 : iterator->schunkbit = 0;
695 :
696 : /*
697 : * If we have a hashtable, create and fill the sorted page lists, unless
698 : * we already did that for a previous iterator. Note that the lists are
699 : * attached to the bitmap not the iterator, so they can be used by more
700 : * than one iterator.
701 : */
702 13433 : if (tbm->status == TBM_HASH && tbm->iterating == TBM_NOT_ITERATING)
703 : {
704 : pagetable_iterator i;
705 : PagetableEntry *page;
706 : int npages;
707 : int nchunks;
708 :
709 4827 : if (!tbm->spages && tbm->npages > 0)
710 3390 : tbm->spages = (PagetableEntry **)
711 3390 : MemoryContextAlloc(tbm->mcxt,
712 3390 : tbm->npages * sizeof(PagetableEntry *));
713 4827 : if (!tbm->schunks && tbm->nchunks > 0)
714 1443 : tbm->schunks = (PagetableEntry **)
715 1443 : MemoryContextAlloc(tbm->mcxt,
716 1443 : tbm->nchunks * sizeof(PagetableEntry *));
717 :
718 4827 : npages = nchunks = 0;
719 4827 : pagetable_start_iterate(tbm->pagetable, &i);
720 113368 : while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
721 : {
722 108541 : if (page->ischunk)
723 1476 : tbm->schunks[nchunks++] = page;
724 : else
725 107065 : tbm->spages[npages++] = page;
726 : }
727 : Assert(npages == tbm->npages);
728 : Assert(nchunks == tbm->nchunks);
729 4827 : if (npages > 1)
730 3390 : qsort(tbm->spages, npages, sizeof(PagetableEntry *),
731 : tbm_comparator);
732 4827 : if (nchunks > 1)
733 9 : qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
734 : tbm_comparator);
735 : }
736 :
737 13433 : tbm->iterating = TBM_ITERATING_PRIVATE;
738 :
739 13433 : return iterator;
740 : }
741 :
742 : /*
743 : * tbm_prepare_shared_iterate - prepare shared iteration state for a TIDBitmap.
744 : *
745 : * The necessary shared state will be allocated from the DSA passed to
746 : * tbm_create, so that multiple processes can attach to it and iterate jointly.
747 : *
748 : * This will convert the pagetable hash into page and chunk array of the index
749 : * into pagetable array.
750 : */
751 : dsa_pointer
752 36 : tbm_prepare_shared_iterate(TIDBitmap *tbm)
753 : {
754 : dsa_pointer dp;
755 : TBMSharedIteratorState *istate;
756 36 : PTEntryArray *ptbase = NULL;
757 36 : PTIterationArray *ptpages = NULL;
758 36 : PTIterationArray *ptchunks = NULL;
759 :
760 : Assert(tbm->dsa != NULL);
761 : Assert(tbm->iterating != TBM_ITERATING_PRIVATE);
762 :
763 : /*
764 : * Allocate TBMSharedIteratorState from DSA to hold the shared members and
765 : * lock, this will also be used by multiple worker for shared iterate.
766 : */
767 36 : dp = dsa_allocate0(tbm->dsa, sizeof(TBMSharedIteratorState));
768 36 : istate = dsa_get_address(tbm->dsa, dp);
769 :
770 : /*
771 : * If we're not already iterating, create and fill the sorted page lists.
772 : * (If we are, the sorted page lists are already stored in the TIDBitmap,
773 : * and we can just reuse them.)
774 : */
775 36 : if (tbm->iterating == TBM_NOT_ITERATING)
776 : {
777 : pagetable_iterator i;
778 : PagetableEntry *page;
779 : int idx;
780 : int npages;
781 : int nchunks;
782 :
783 : /*
784 : * Allocate the page and chunk array memory from the DSA to share
785 : * across multiple processes.
786 : */
787 36 : if (tbm->npages)
788 : {
789 36 : tbm->ptpages = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
790 : tbm->npages * sizeof(int));
791 36 : ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
792 36 : pg_atomic_init_u32(&ptpages->refcount, 0);
793 : }
794 36 : if (tbm->nchunks)
795 : {
796 3 : tbm->ptchunks = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
797 : tbm->nchunks * sizeof(int));
798 3 : ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
799 3 : pg_atomic_init_u32(&ptchunks->refcount, 0);
800 : }
801 :
802 : /*
803 : * If TBM status is TBM_HASH then iterate over the pagetable and
804 : * convert it to page and chunk arrays. But if it's in the
805 : * TBM_ONE_PAGE mode then directly allocate the space for one entry
806 : * from the DSA.
807 : */
808 36 : npages = nchunks = 0;
809 36 : if (tbm->status == TBM_HASH)
810 : {
811 36 : ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
812 :
813 36 : pagetable_start_iterate(tbm->pagetable, &i);
814 13551 : while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
815 : {
816 13515 : idx = page - ptbase->ptentry;
817 13515 : if (page->ischunk)
818 12 : ptchunks->index[nchunks++] = idx;
819 : else
820 13503 : ptpages->index[npages++] = idx;
821 : }
822 :
823 : Assert(npages == tbm->npages);
824 : Assert(nchunks == tbm->nchunks);
825 : }
826 0 : else if (tbm->status == TBM_ONE_PAGE)
827 : {
828 : /*
829 : * In one page mode allocate the space for one pagetable entry,
830 : * initialize it, and directly store its index (i.e. 0) in the
831 : * page array.
832 : */
833 0 : tbm->dsapagetable = dsa_allocate(tbm->dsa, sizeof(PTEntryArray) +
834 : sizeof(PagetableEntry));
835 0 : ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
836 0 : memcpy(ptbase->ptentry, &tbm->entry1, sizeof(PagetableEntry));
837 0 : ptpages->index[0] = 0;
838 : }
839 :
840 36 : if (ptbase != NULL)
841 36 : pg_atomic_init_u32(&ptbase->refcount, 0);
842 36 : if (npages > 1)
843 36 : qsort_arg(ptpages->index, npages, sizeof(int),
844 36 : tbm_shared_comparator, ptbase->ptentry);
845 36 : if (nchunks > 1)
846 3 : qsort_arg(ptchunks->index, nchunks, sizeof(int),
847 3 : tbm_shared_comparator, ptbase->ptentry);
848 : }
849 :
850 : /*
851 : * Store the TBM members in the shared state so that we can share them
852 : * across multiple processes.
853 : */
854 36 : istate->nentries = tbm->nentries;
855 36 : istate->maxentries = tbm->maxentries;
856 36 : istate->npages = tbm->npages;
857 36 : istate->nchunks = tbm->nchunks;
858 36 : istate->pagetable = tbm->dsapagetable;
859 36 : istate->spages = tbm->ptpages;
860 36 : istate->schunks = tbm->ptchunks;
861 :
862 36 : ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
863 36 : ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
864 36 : ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
865 :
866 : /*
867 : * For every shared iterator referring to pagetable and iterator array,
868 : * increase the refcount by 1 so that while freeing the shared iterator we
869 : * don't free pagetable and iterator array until its refcount becomes 0.
870 : */
871 36 : if (ptbase != NULL)
872 36 : pg_atomic_add_fetch_u32(&ptbase->refcount, 1);
873 36 : if (ptpages != NULL)
874 36 : pg_atomic_add_fetch_u32(&ptpages->refcount, 1);
875 36 : if (ptchunks != NULL)
876 3 : pg_atomic_add_fetch_u32(&ptchunks->refcount, 1);
877 :
878 : /* Initialize the iterator lock */
879 36 : LWLockInitialize(&istate->lock, LWTRANCHE_SHARED_TIDBITMAP);
880 :
881 : /* Initialize the shared iterator state */
882 36 : istate->schunkbit = 0;
883 36 : istate->schunkptr = 0;
884 36 : istate->spageptr = 0;
885 :
886 36 : tbm->iterating = TBM_ITERATING_SHARED;
887 :
888 36 : return dp;
889 : }
890 :
891 : /*
892 : * tbm_extract_page_tuple - extract the tuple offsets from a page
893 : *
894 : * Returns the number of offsets it filled in if <= max_offsets. Otherwise,
895 : * fills in as many offsets as fit and returns the total number of offsets in
896 : * the page.
897 : */
898 : int
899 126482 : tbm_extract_page_tuple(TBMIterateResult *iteritem,
900 : OffsetNumber *offsets,
901 : uint32 max_offsets)
902 : {
903 126482 : PagetableEntry *page = iteritem->internal_page;
904 126482 : int ntuples = 0;
905 :
906 758892 : for (int wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
907 : {
908 632410 : bitmapword w = page->words[wordnum];
909 :
910 632410 : if (w != 0)
911 : {
912 288676 : int off = wordnum * BITS_PER_BITMAPWORD + 1;
913 :
914 12441381 : while (w != 0)
915 : {
916 12152705 : if (w & 1)
917 : {
918 3084518 : if (ntuples < max_offsets)
919 3084518 : offsets[ntuples] = (OffsetNumber) off;
920 3084518 : ntuples++;
921 : }
922 12152705 : off++;
923 12152705 : w >>= 1;
924 : }
925 : }
926 : }
927 :
928 126482 : return ntuples;
929 : }
930 :
931 : /*
932 : * tbm_advance_schunkbit - Advance the schunkbit
933 : */
934 : static inline void
935 84766 : tbm_advance_schunkbit(PagetableEntry *chunk, int *schunkbitp)
936 : {
937 84766 : int schunkbit = *schunkbitp;
938 :
939 385494 : while (schunkbit < PAGES_PER_CHUNK)
940 : {
941 384006 : int wordnum = WORDNUM(schunkbit);
942 384006 : int bitnum = BITNUM(schunkbit);
943 :
944 384006 : if ((chunk->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
945 83278 : break;
946 300728 : schunkbit++;
947 : }
948 :
949 84766 : *schunkbitp = schunkbit;
950 84766 : }
951 :
952 : /*
953 : * tbm_private_iterate - scan through next page of a TIDBitmap
954 : *
955 : * Caller must pass in a TBMIterateResult to be filled.
956 : *
957 : * Pages are guaranteed to be delivered in numerical order.
958 : *
959 : * Returns false when there are no more pages to scan and true otherwise. When
960 : * there are no more pages to scan, tbmres->blockno is set to
961 : * InvalidBlockNumber.
962 : *
963 : * If lossy is true, then the bitmap is "lossy" and failed to remember
964 : * the exact tuples to look at on this page --- the caller must examine all
965 : * tuples on the page and check if they meet the intended condition. If lossy
966 : * is false, the caller must later extract the tuple offsets from the page
967 : * pointed to by internal_page with tbm_extract_page_tuple.
968 : *
969 : * If tbmres->recheck is true, only the indicated tuples need be examined, but
970 : * the condition must be rechecked anyway. (For ease of testing, recheck is
971 : * always set true when lossy is true.)
972 : */
973 : bool
974 205061 : tbm_private_iterate(TBMPrivateIterator *iterator, TBMIterateResult *tbmres)
975 : {
976 205061 : TIDBitmap *tbm = iterator->tbm;
977 :
978 : Assert(tbm->iterating == TBM_ITERATING_PRIVATE);
979 :
980 : /*
981 : * If lossy chunk pages remain, make sure we've advanced schunkptr/
982 : * schunkbit to the next set bit.
983 : */
984 206537 : while (iterator->schunkptr < tbm->nchunks)
985 : {
986 81691 : PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
987 81691 : int schunkbit = iterator->schunkbit;
988 :
989 81691 : tbm_advance_schunkbit(chunk, &schunkbit);
990 81691 : if (schunkbit < PAGES_PER_CHUNK)
991 : {
992 80215 : iterator->schunkbit = schunkbit;
993 80215 : break;
994 : }
995 : /* advance to next chunk */
996 1476 : iterator->schunkptr++;
997 1476 : iterator->schunkbit = 0;
998 : }
999 :
1000 : /*
1001 : * If both chunk and per-page data remain, must output the numerically
1002 : * earlier page.
1003 : */
1004 205061 : if (iterator->schunkptr < tbm->nchunks)
1005 : {
1006 80215 : PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
1007 : BlockNumber chunk_blockno;
1008 :
1009 80215 : chunk_blockno = chunk->blockno + iterator->schunkbit;
1010 80215 : if (iterator->spageptr >= tbm->npages ||
1011 6225 : chunk_blockno < tbm->spages[iterator->spageptr]->blockno)
1012 : {
1013 : /* Return a lossy page indicator from the chunk */
1014 78649 : tbmres->blockno = chunk_blockno;
1015 78649 : tbmres->lossy = true;
1016 78649 : tbmres->recheck = true;
1017 78649 : tbmres->internal_page = NULL;
1018 78649 : iterator->schunkbit++;
1019 78649 : return true;
1020 : }
1021 : }
1022 :
1023 126412 : if (iterator->spageptr < tbm->npages)
1024 : {
1025 : PagetableEntry *page;
1026 :
1027 : /* In TBM_ONE_PAGE state, we don't allocate an spages[] array */
1028 112994 : if (tbm->status == TBM_ONE_PAGE)
1029 6578 : page = &tbm->entry1;
1030 : else
1031 106416 : page = tbm->spages[iterator->spageptr];
1032 :
1033 112994 : tbmres->internal_page = page;
1034 112994 : tbmres->blockno = page->blockno;
1035 112994 : tbmres->lossy = false;
1036 112994 : tbmres->recheck = page->recheck;
1037 112994 : iterator->spageptr++;
1038 112994 : return true;
1039 : }
1040 :
1041 : /* Nothing more in the bitmap */
1042 13418 : tbmres->blockno = InvalidBlockNumber;
1043 13418 : return false;
1044 : }
1045 :
1046 : /*
1047 : * tbm_shared_iterate - scan through next page of a TIDBitmap
1048 : *
1049 : * As above, but this will iterate using an iterator which is shared
1050 : * across multiple processes. We need to acquire the iterator LWLock,
1051 : * before accessing the shared members.
1052 : */
1053 : bool
1054 15225 : tbm_shared_iterate(TBMSharedIterator *iterator, TBMIterateResult *tbmres)
1055 : {
1056 15225 : TBMSharedIteratorState *istate = iterator->state;
1057 15225 : PagetableEntry *ptbase = NULL;
1058 15225 : int *idxpages = NULL;
1059 15225 : int *idxchunks = NULL;
1060 :
1061 15225 : if (iterator->ptbase != NULL)
1062 15225 : ptbase = iterator->ptbase->ptentry;
1063 15225 : if (iterator->ptpages != NULL)
1064 15225 : idxpages = iterator->ptpages->index;
1065 15225 : if (iterator->ptchunks != NULL)
1066 3720 : idxchunks = iterator->ptchunks->index;
1067 :
1068 : /* Acquire the LWLock before accessing the shared members */
1069 15225 : LWLockAcquire(&istate->lock, LW_EXCLUSIVE);
1070 :
1071 : /*
1072 : * If lossy chunk pages remain, make sure we've advanced schunkptr/
1073 : * schunkbit to the next set bit.
1074 : */
1075 15237 : while (istate->schunkptr < istate->nchunks)
1076 : {
1077 3075 : PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
1078 3075 : int schunkbit = istate->schunkbit;
1079 :
1080 3075 : tbm_advance_schunkbit(chunk, &schunkbit);
1081 3075 : if (schunkbit < PAGES_PER_CHUNK)
1082 : {
1083 3063 : istate->schunkbit = schunkbit;
1084 3063 : break;
1085 : }
1086 : /* advance to next chunk */
1087 12 : istate->schunkptr++;
1088 12 : istate->schunkbit = 0;
1089 : }
1090 :
1091 : /*
1092 : * If both chunk and per-page data remain, must output the numerically
1093 : * earlier page.
1094 : */
1095 15225 : if (istate->schunkptr < istate->nchunks)
1096 : {
1097 3063 : PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
1098 : BlockNumber chunk_blockno;
1099 :
1100 3063 : chunk_blockno = chunk->blockno + istate->schunkbit;
1101 :
1102 3063 : if (istate->spageptr >= istate->npages ||
1103 3063 : chunk_blockno < ptbase[idxpages[istate->spageptr]].blockno)
1104 : {
1105 : /* Return a lossy page indicator from the chunk */
1106 1551 : tbmres->blockno = chunk_blockno;
1107 1551 : tbmres->lossy = true;
1108 1551 : tbmres->recheck = true;
1109 1551 : tbmres->internal_page = NULL;
1110 1551 : istate->schunkbit++;
1111 :
1112 1551 : LWLockRelease(&istate->lock);
1113 1551 : return true;
1114 : }
1115 : }
1116 :
1117 13674 : if (istate->spageptr < istate->npages)
1118 : {
1119 13503 : PagetableEntry *page = &ptbase[idxpages[istate->spageptr]];
1120 :
1121 13503 : tbmres->internal_page = page;
1122 13503 : tbmres->blockno = page->blockno;
1123 13503 : tbmres->lossy = false;
1124 13503 : tbmres->recheck = page->recheck;
1125 13503 : istate->spageptr++;
1126 :
1127 13503 : LWLockRelease(&istate->lock);
1128 :
1129 13503 : return true;
1130 : }
1131 :
1132 171 : LWLockRelease(&istate->lock);
1133 :
1134 : /* Nothing more in the bitmap */
1135 171 : tbmres->blockno = InvalidBlockNumber;
1136 171 : return false;
1137 : }
1138 :
1139 : /*
1140 : * tbm_end_private_iterate - finish an iteration over a TIDBitmap
1141 : *
1142 : * Currently this is just a pfree, but it might do more someday. (For
1143 : * instance, it could be useful to count open iterators and allow the
1144 : * bitmap to return to read/write status when there are no more iterators.)
1145 : */
1146 : void
1147 13376 : tbm_end_private_iterate(TBMPrivateIterator *iterator)
1148 : {
1149 13376 : pfree(iterator);
1150 13376 : }
1151 :
1152 : /*
1153 : * tbm_end_shared_iterate - finish a shared iteration over a TIDBitmap
1154 : *
1155 : * This doesn't free any of the shared state associated with the iterator,
1156 : * just our backend-private state.
1157 : */
1158 : void
1159 171 : tbm_end_shared_iterate(TBMSharedIterator *iterator)
1160 : {
1161 171 : pfree(iterator);
1162 171 : }
1163 :
1164 : /*
1165 : * tbm_find_pageentry - find a PagetableEntry for the pageno
1166 : *
1167 : * Returns NULL if there is no non-lossy entry for the pageno.
1168 : */
1169 : static const PagetableEntry *
1170 5919 : tbm_find_pageentry(const TIDBitmap *tbm, BlockNumber pageno)
1171 : {
1172 : const PagetableEntry *page;
1173 :
1174 5919 : if (tbm->nentries == 0) /* in case pagetable doesn't exist */
1175 0 : return NULL;
1176 :
1177 5919 : if (tbm->status == TBM_ONE_PAGE)
1178 : {
1179 0 : page = &tbm->entry1;
1180 0 : if (page->blockno != pageno)
1181 0 : return NULL;
1182 : Assert(!page->ischunk);
1183 0 : return page;
1184 : }
1185 :
1186 5919 : page = pagetable_lookup(tbm->pagetable, pageno);
1187 5919 : if (page == NULL)
1188 993 : return NULL;
1189 4926 : if (page->ischunk)
1190 0 : return NULL; /* don't want a lossy chunk header */
1191 4926 : return page;
1192 : }
1193 :
1194 : /*
1195 : * tbm_get_pageentry - find or create a PagetableEntry for the pageno
1196 : *
1197 : * If new, the entry is marked as an exact (non-chunk) entry.
1198 : *
1199 : * This may cause the table to exceed the desired memory size. It is
1200 : * up to the caller to call tbm_lossify() at the next safe point if so.
1201 : */
1202 : static PagetableEntry *
1203 3781847 : tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
1204 : {
1205 : PagetableEntry *page;
1206 : bool found;
1207 :
1208 3781847 : if (tbm->status == TBM_EMPTY)
1209 : {
1210 : /* Use the fixed slot */
1211 10108 : page = &tbm->entry1;
1212 10108 : found = false;
1213 10108 : tbm->status = TBM_ONE_PAGE;
1214 : }
1215 : else
1216 : {
1217 3771739 : if (tbm->status == TBM_ONE_PAGE)
1218 : {
1219 127008 : page = &tbm->entry1;
1220 127008 : if (page->blockno == pageno)
1221 123478 : return page;
1222 : /* Time to switch from one page to a hashtable */
1223 3530 : tbm_create_pagetable(tbm);
1224 : }
1225 :
1226 : /* Look up or create an entry */
1227 3648261 : page = pagetable_insert(tbm->pagetable, pageno, &found);
1228 : }
1229 :
1230 : /* Initialize it if not present before */
1231 3658369 : if (!found)
1232 : {
1233 147817 : char oldstatus = page->status;
1234 :
1235 1034719 : MemSet(page, 0, sizeof(PagetableEntry));
1236 147817 : page->status = oldstatus;
1237 147817 : page->blockno = pageno;
1238 : /* must count it too */
1239 147817 : tbm->nentries++;
1240 147817 : tbm->npages++;
1241 : }
1242 :
1243 3658369 : return page;
1244 : }
1245 :
1246 : /*
1247 : * tbm_page_is_lossy - is the page marked as lossily stored?
1248 : */
1249 : static bool
1250 3792050 : tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno)
1251 : {
1252 : PagetableEntry *page;
1253 : BlockNumber chunk_pageno;
1254 : int bitno;
1255 :
1256 : /* we can skip the lookup if there are no lossy chunks */
1257 3792050 : if (tbm->nchunks == 0)
1258 3726917 : return false;
1259 : Assert(tbm->status == TBM_HASH);
1260 :
1261 65133 : bitno = pageno % PAGES_PER_CHUNK;
1262 65133 : chunk_pageno = pageno - bitno;
1263 :
1264 65133 : page = pagetable_lookup(tbm->pagetable, chunk_pageno);
1265 :
1266 65133 : if (page != NULL && page->ischunk)
1267 : {
1268 9567 : int wordnum = WORDNUM(bitno);
1269 9567 : int bitnum = BITNUM(bitno);
1270 :
1271 9567 : if ((page->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
1272 4284 : return true;
1273 : }
1274 60849 : return false;
1275 : }
1276 :
1277 : /*
1278 : * tbm_mark_page_lossy - mark the page number as lossily stored
1279 : *
1280 : * This may cause the table to exceed the desired memory size. It is
1281 : * up to the caller to call tbm_lossify() at the next safe point if so.
1282 : */
1283 : static void
1284 83224 : tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
1285 : {
1286 : PagetableEntry *page;
1287 : bool found;
1288 : BlockNumber chunk_pageno;
1289 : int bitno;
1290 : int wordnum;
1291 : int bitnum;
1292 :
1293 : /* We force the bitmap into hashtable mode whenever it's lossy */
1294 83224 : if (tbm->status != TBM_HASH)
1295 1434 : tbm_create_pagetable(tbm);
1296 :
1297 83224 : bitno = pageno % PAGES_PER_CHUNK;
1298 83224 : chunk_pageno = pageno - bitno;
1299 :
1300 : /*
1301 : * Remove any extant non-lossy entry for the page. If the page is its own
1302 : * chunk header, however, we skip this and handle the case below.
1303 : */
1304 83224 : if (bitno != 0)
1305 : {
1306 82060 : if (pagetable_delete(tbm->pagetable, pageno))
1307 : {
1308 : /* It was present, so adjust counts */
1309 9234 : tbm->nentries--;
1310 9234 : tbm->npages--; /* assume it must have been non-lossy */
1311 : }
1312 : }
1313 :
1314 : /* Look up or create entry for chunk-header page */
1315 83224 : page = pagetable_insert(tbm->pagetable, chunk_pageno, &found);
1316 :
1317 : /* Initialize it if not present before */
1318 83224 : if (!found)
1319 : {
1320 1434 : char oldstatus = page->status;
1321 :
1322 10038 : MemSet(page, 0, sizeof(PagetableEntry));
1323 1434 : page->status = oldstatus;
1324 1434 : page->blockno = chunk_pageno;
1325 1434 : page->ischunk = true;
1326 : /* must count it too */
1327 1434 : tbm->nentries++;
1328 1434 : tbm->nchunks++;
1329 : }
1330 81790 : else if (!page->ischunk)
1331 : {
1332 78 : char oldstatus = page->status;
1333 :
1334 : /* chunk header page was formerly non-lossy, make it lossy */
1335 546 : MemSet(page, 0, sizeof(PagetableEntry));
1336 78 : page->status = oldstatus;
1337 78 : page->blockno = chunk_pageno;
1338 78 : page->ischunk = true;
1339 : /* we assume it had some tuple bit(s) set, so mark it lossy */
1340 78 : page->words[0] = ((bitmapword) 1 << 0);
1341 : /* adjust counts */
1342 78 : tbm->nchunks++;
1343 78 : tbm->npages--;
1344 : }
1345 :
1346 : /* Now set the original target page's bit */
1347 83224 : wordnum = WORDNUM(bitno);
1348 83224 : bitnum = BITNUM(bitno);
1349 83224 : page->words[wordnum] |= ((bitmapword) 1 << bitnum);
1350 83224 : }
1351 :
1352 : /*
1353 : * tbm_lossify - lose some information to get back under the memory limit
1354 : */
1355 : static void
1356 18 : tbm_lossify(TIDBitmap *tbm)
1357 : {
1358 : pagetable_iterator i;
1359 : PagetableEntry *page;
1360 :
1361 : /*
1362 : * XXX Really stupid implementation: this just lossifies pages in
1363 : * essentially random order. We should be paying some attention to the
1364 : * number of bits set in each page, instead.
1365 : *
1366 : * Since we are called as soon as nentries exceeds maxentries, we should
1367 : * push nentries down to significantly less than maxentries, or else we'll
1368 : * just end up doing this again very soon. We shoot for maxentries/2.
1369 : */
1370 : Assert(tbm->iterating == TBM_NOT_ITERATING);
1371 : Assert(tbm->status == TBM_HASH);
1372 :
1373 18 : pagetable_start_iterate_at(tbm->pagetable, &i, tbm->lossify_start);
1374 9246 : while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
1375 : {
1376 9246 : if (page->ischunk)
1377 0 : continue; /* already a chunk header */
1378 :
1379 : /*
1380 : * If the page would become a chunk header, we won't save anything by
1381 : * converting it to lossy, so skip it.
1382 : */
1383 9246 : if ((page->blockno % PAGES_PER_CHUNK) == 0)
1384 12 : continue;
1385 :
1386 : /* This does the dirty work ... */
1387 9234 : tbm_mark_page_lossy(tbm, page->blockno);
1388 :
1389 9234 : if (tbm->nentries <= tbm->maxentries / 2)
1390 : {
1391 : /*
1392 : * We have made enough room. Remember where to start lossifying
1393 : * next round, so we evenly iterate over the hashtable.
1394 : */
1395 18 : tbm->lossify_start = i.cur;
1396 18 : break;
1397 : }
1398 :
1399 : /*
1400 : * Note: tbm_mark_page_lossy may have inserted a lossy chunk into the
1401 : * hashtable and may have deleted the non-lossy chunk. We can
1402 : * continue the same hash table scan, since failure to visit one
1403 : * element or visiting the newly inserted element, isn't fatal.
1404 : */
1405 : }
1406 :
1407 : /*
1408 : * With a big bitmap and small work_mem, it's possible that we cannot get
1409 : * under maxentries. Again, if that happens, we'd end up uselessly
1410 : * calling tbm_lossify over and over. To prevent this from becoming a
1411 : * performance sink, force maxentries up to at least double the current
1412 : * number of entries. (In essence, we're admitting inability to fit
1413 : * within work_mem when we do this.) Note that this test will not fire if
1414 : * we broke out of the loop early; and if we didn't, the current number of
1415 : * entries is simply not reducible any further.
1416 : */
1417 18 : if (tbm->nentries > tbm->maxentries / 2)
1418 0 : tbm->maxentries = Min(tbm->nentries, (INT_MAX - 1) / 2) * 2;
1419 18 : }
1420 :
1421 : /*
1422 : * qsort comparator to handle PagetableEntry pointers.
1423 : */
1424 : static int
1425 702555 : tbm_comparator(const void *left, const void *right)
1426 : {
1427 702555 : BlockNumber l = (*((PagetableEntry *const *) left))->blockno;
1428 702555 : BlockNumber r = (*((PagetableEntry *const *) right))->blockno;
1429 :
1430 702555 : return pg_cmp_u32(l, r);
1431 : }
1432 :
1433 : /*
1434 : * As above, but this will get index into PagetableEntry array. Therefore,
1435 : * it needs to get actual PagetableEntry using the index before comparing the
1436 : * blockno.
1437 : */
1438 : static int
1439 119145 : tbm_shared_comparator(const void *left, const void *right, void *arg)
1440 : {
1441 119145 : PagetableEntry *base = (PagetableEntry *) arg;
1442 119145 : PagetableEntry *lpage = &base[*(const int *) left];
1443 119145 : PagetableEntry *rpage = &base[*(const int *) right];
1444 :
1445 119145 : if (lpage->blockno < rpage->blockno)
1446 54483 : return -1;
1447 64662 : else if (lpage->blockno > rpage->blockno)
1448 64662 : return 1;
1449 0 : return 0;
1450 : }
1451 :
1452 : /*
1453 : * tbm_attach_shared_iterate
1454 : *
1455 : * Allocate a backend-private iterator and attach the shared iterator state
1456 : * to it so that multiple processed can iterate jointly.
1457 : *
1458 : * We also converts the DSA pointers to local pointers and store them into
1459 : * our private iterator.
1460 : */
1461 : TBMSharedIterator *
1462 171 : tbm_attach_shared_iterate(dsa_area *dsa, dsa_pointer dp)
1463 : {
1464 : TBMSharedIterator *iterator;
1465 : TBMSharedIteratorState *istate;
1466 :
1467 : /*
1468 : * Create the TBMSharedIterator struct, with enough trailing space to
1469 : * serve the needs of the TBMIterateResult sub-struct.
1470 : */
1471 171 : iterator = palloc0_object(TBMSharedIterator);
1472 :
1473 171 : istate = (TBMSharedIteratorState *) dsa_get_address(dsa, dp);
1474 :
1475 171 : iterator->state = istate;
1476 :
1477 171 : iterator->ptbase = dsa_get_address(dsa, istate->pagetable);
1478 :
1479 171 : if (istate->npages)
1480 171 : iterator->ptpages = dsa_get_address(dsa, istate->spages);
1481 171 : if (istate->nchunks)
1482 15 : iterator->ptchunks = dsa_get_address(dsa, istate->schunks);
1483 :
1484 171 : return iterator;
1485 : }
1486 :
1487 : /*
1488 : * pagetable_allocate
1489 : *
1490 : * Callback function for allocating the memory for hashtable elements.
1491 : * Allocate memory for hashtable elements, using DSA if available.
1492 : */
1493 : static inline void *
1494 5163 : pagetable_allocate(pagetable_hash *pagetable, Size size)
1495 : {
1496 5163 : TIDBitmap *tbm = (TIDBitmap *) pagetable->private_data;
1497 : PTEntryArray *ptbase;
1498 :
1499 5163 : if (tbm->dsa == NULL)
1500 5085 : return MemoryContextAllocExtended(pagetable->ctx, size,
1501 : MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO);
1502 :
1503 : /*
1504 : * Save the dsapagetable reference in dsapagetableold before allocating
1505 : * new memory so that pagetable_free can free the old entry.
1506 : */
1507 78 : tbm->dsapagetableold = tbm->dsapagetable;
1508 78 : tbm->dsapagetable = dsa_allocate_extended(tbm->dsa,
1509 : sizeof(PTEntryArray) + size,
1510 : DSA_ALLOC_HUGE | DSA_ALLOC_ZERO);
1511 78 : ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
1512 :
1513 78 : return ptbase->ptentry;
1514 : }
1515 :
1516 : /*
1517 : * pagetable_free
1518 : *
1519 : * Callback function for freeing hash table elements.
1520 : */
1521 : static inline void
1522 5161 : pagetable_free(pagetable_hash *pagetable, void *pointer)
1523 : {
1524 5161 : TIDBitmap *tbm = (TIDBitmap *) pagetable->private_data;
1525 :
1526 : /* pfree the input pointer if DSA is not available */
1527 5161 : if (tbm->dsa == NULL)
1528 5083 : pfree(pointer);
1529 78 : else if (DsaPointerIsValid(tbm->dsapagetableold))
1530 : {
1531 42 : dsa_free(tbm->dsa, tbm->dsapagetableold);
1532 42 : tbm->dsapagetableold = InvalidDsaPointer;
1533 : }
1534 5161 : }
1535 :
1536 : /*
1537 : * tbm_calculate_entries
1538 : *
1539 : * Estimate number of hashtable entries we can have within maxbytes.
1540 : */
1541 : int
1542 388272 : tbm_calculate_entries(Size maxbytes)
1543 : {
1544 : Size nbuckets;
1545 :
1546 : /*
1547 : * Estimate number of hashtable entries we can have within maxbytes. This
1548 : * estimates the hash cost as sizeof(PagetableEntry), which is good enough
1549 : * for our purpose. Also count an extra Pointer per entry for the arrays
1550 : * created during iteration readout.
1551 : */
1552 388272 : nbuckets = maxbytes /
1553 : (sizeof(PagetableEntry) + sizeof(Pointer) + sizeof(Pointer));
1554 388272 : nbuckets = Min(nbuckets, INT_MAX - 1); /* safety limit */
1555 388272 : nbuckets = Max(nbuckets, 16); /* sanity limit */
1556 :
1557 388272 : return (int) nbuckets;
1558 : }
1559 :
1560 : /*
1561 : * Create a shared or private bitmap iterator and start iteration.
1562 : *
1563 : * `tbm` is only used to create the private iterator and dsa and dsp are only
1564 : * used to create the shared iterator.
1565 : *
1566 : * Before invoking tbm_begin_iterate() to create a shared iterator, one
1567 : * process must already have invoked tbm_prepare_shared_iterate() to create
1568 : * and set up the TBMSharedIteratorState.
1569 : */
1570 : TBMIterator
1571 13244 : tbm_begin_iterate(TIDBitmap *tbm, dsa_area *dsa, dsa_pointer dsp)
1572 : {
1573 13244 : TBMIterator iterator = {0};
1574 :
1575 : /* Allocate a private iterator and attach the shared state to it */
1576 13244 : if (DsaPointerIsValid(dsp))
1577 : {
1578 171 : iterator.shared = true;
1579 171 : iterator.i.shared_iterator = tbm_attach_shared_iterate(dsa, dsp);
1580 : }
1581 : else
1582 : {
1583 13073 : iterator.shared = false;
1584 13073 : iterator.i.private_iterator = tbm_begin_private_iterate(tbm);
1585 : }
1586 :
1587 13244 : return iterator;
1588 : }
1589 :
1590 : /*
1591 : * Clean up shared or private bitmap iterator.
1592 : */
1593 : void
1594 13187 : tbm_end_iterate(TBMIterator *iterator)
1595 : {
1596 : Assert(iterator && !tbm_exhausted(iterator));
1597 :
1598 13187 : if (iterator->shared)
1599 171 : tbm_end_shared_iterate(iterator->i.shared_iterator);
1600 : else
1601 13016 : tbm_end_private_iterate(iterator->i.private_iterator);
1602 :
1603 13187 : *iterator = (TBMIterator)
1604 : {
1605 : 0
1606 : };
1607 13187 : }
1608 :
1609 : /*
1610 : * Populate the next TBMIterateResult using the shared or private bitmap
1611 : * iterator. Returns false when there is nothing more to scan.
1612 : */
1613 : bool
1614 217363 : tbm_iterate(TBMIterator *iterator, TBMIterateResult *tbmres)
1615 : {
1616 : Assert(iterator);
1617 : Assert(tbmres);
1618 :
1619 217363 : if (iterator->shared)
1620 15225 : return tbm_shared_iterate(iterator->i.shared_iterator, tbmres);
1621 : else
1622 202138 : return tbm_private_iterate(iterator->i.private_iterator, tbmres);
1623 : }
|
