PostgreSQL Source Code  git master
tidbitmap.c File Reference
#include "postgres.h"
#include <limits.h>
#include "access/htup_details.h"
#include "common/hashfn.h"
#include "nodes/bitmapset.h"
#include "nodes/tidbitmap.h"
#include "storage/lwlock.h"
#include "utils/dsa.h"
#include "lib/simplehash.h"
Include dependency graph for tidbitmap.c:

Go to the source code of this file.

Data Structures

struct  PagetableEntry
 
struct  PTEntryArray
 
struct  TIDBitmap
 
struct  TBMIterator
 
struct  TBMSharedIteratorState
 
struct  PTIterationArray
 
struct  TBMSharedIterator
 

Macros

#define MAX_TUPLES_PER_PAGE   MaxHeapTuplesPerPage
 
#define PAGES_PER_CHUNK   (BLCKSZ / 32)
 
#define WORDNUM(x)   ((x) / BITS_PER_BITMAPWORD)
 
#define BITNUM(x)   ((x) % BITS_PER_BITMAPWORD)
 
#define WORDS_PER_PAGE   ((MAX_TUPLES_PER_PAGE - 1) / BITS_PER_BITMAPWORD + 1)
 
#define WORDS_PER_CHUNK   ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1)
 
#define SH_USE_NONDEFAULT_ALLOCATOR
 
#define SH_PREFIX   pagetable
 
#define SH_ELEMENT_TYPE   PagetableEntry
 
#define SH_KEY_TYPE   BlockNumber
 
#define SH_KEY   blockno
 
#define SH_HASH_KEY(tb, key)   murmurhash32(key)
 
#define SH_EQUAL(tb, a, b)   a == b
 
#define SH_SCOPE   static inline
 
#define SH_DEFINE
 
#define SH_DECLARE
 

Typedefs

typedef struct PagetableEntry PagetableEntry
 
typedef struct PTEntryArray PTEntryArray
 
typedef struct TBMSharedIteratorState TBMSharedIteratorState
 
typedef struct PTIterationArray PTIterationArray
 

Enumerations

enum  TBMStatus { TBM_EMPTY , TBM_ONE_PAGE , TBM_HASH }
 
enum  TBMIteratingState { TBM_NOT_ITERATING , TBM_ITERATING_PRIVATE , TBM_ITERATING_SHARED }
 

Functions

static void tbm_union_page (TIDBitmap *a, const PagetableEntry *bpage)
 
static bool tbm_intersect_page (TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
 
static const PagetableEntrytbm_find_pageentry (const TIDBitmap *tbm, BlockNumber pageno)
 
static PagetableEntrytbm_get_pageentry (TIDBitmap *tbm, BlockNumber pageno)
 
static bool tbm_page_is_lossy (const TIDBitmap *tbm, BlockNumber pageno)
 
static void tbm_mark_page_lossy (TIDBitmap *tbm, BlockNumber pageno)
 
static void tbm_lossify (TIDBitmap *tbm)
 
static int tbm_comparator (const void *left, const void *right)
 
static int tbm_shared_comparator (const void *left, const void *right, void *arg)
 
TIDBitmaptbm_create (long maxbytes, dsa_area *dsa)
 
static void tbm_create_pagetable (TIDBitmap *tbm)
 
void tbm_free (TIDBitmap *tbm)
 
void tbm_free_shared_area (dsa_area *dsa, dsa_pointer dp)
 
void tbm_add_tuples (TIDBitmap *tbm, const ItemPointer tids, int ntids, bool recheck)
 
void tbm_add_page (TIDBitmap *tbm, BlockNumber pageno)
 
void tbm_union (TIDBitmap *a, const TIDBitmap *b)
 
void tbm_intersect (TIDBitmap *a, const TIDBitmap *b)
 
bool tbm_is_empty (const TIDBitmap *tbm)
 
TBMIteratortbm_begin_iterate (TIDBitmap *tbm)
 
dsa_pointer tbm_prepare_shared_iterate (TIDBitmap *tbm)
 
static int tbm_extract_page_tuple (PagetableEntry *page, TBMIterateResult *output)
 
static void tbm_advance_schunkbit (PagetableEntry *chunk, int *schunkbitp)
 
TBMIterateResulttbm_iterate (TBMIterator *iterator)
 
TBMIterateResulttbm_shared_iterate (TBMSharedIterator *iterator)
 
void tbm_end_iterate (TBMIterator *iterator)
 
void tbm_end_shared_iterate (TBMSharedIterator *iterator)
 
TBMSharedIteratortbm_attach_shared_iterate (dsa_area *dsa, dsa_pointer dp)
 
static void * pagetable_allocate (pagetable_hash *pagetable, Size size)
 
static void pagetable_free (pagetable_hash *pagetable, void *pointer)
 
long tbm_calculate_entries (double maxbytes)
 

Macro Definition Documentation

◆ BITNUM

#define BITNUM (   x)    ((x) % BITS_PER_BITMAPWORD)

Definition at line 78 of file tidbitmap.c.

◆ MAX_TUPLES_PER_PAGE

#define MAX_TUPLES_PER_PAGE   MaxHeapTuplesPerPage

Definition at line 56 of file tidbitmap.c.

◆ PAGES_PER_CHUNK

#define PAGES_PER_CHUNK   (BLCKSZ / 32)

Definition at line 73 of file tidbitmap.c.

◆ SH_DECLARE

#define SH_DECLARE

Definition at line 251 of file tidbitmap.c.

◆ SH_DEFINE

#define SH_DEFINE

Definition at line 250 of file tidbitmap.c.

◆ SH_ELEMENT_TYPE

#define SH_ELEMENT_TYPE   PagetableEntry

Definition at line 244 of file tidbitmap.c.

◆ SH_EQUAL

#define SH_EQUAL (   tb,
  a,
  b 
)    a == b

Definition at line 248 of file tidbitmap.c.

◆ SH_HASH_KEY

#define SH_HASH_KEY (   tb,
  key 
)    murmurhash32(key)

Definition at line 247 of file tidbitmap.c.

◆ SH_KEY

#define SH_KEY   blockno

Definition at line 246 of file tidbitmap.c.

◆ SH_KEY_TYPE

#define SH_KEY_TYPE   BlockNumber

Definition at line 245 of file tidbitmap.c.

◆ SH_PREFIX

#define SH_PREFIX   pagetable

Definition at line 243 of file tidbitmap.c.

◆ SH_SCOPE

#define SH_SCOPE   static inline

Definition at line 249 of file tidbitmap.c.

◆ SH_USE_NONDEFAULT_ALLOCATOR

#define SH_USE_NONDEFAULT_ALLOCATOR

Definition at line 242 of file tidbitmap.c.

◆ WORDNUM

#define WORDNUM (   x)    ((x) / BITS_PER_BITMAPWORD)

Definition at line 77 of file tidbitmap.c.

◆ WORDS_PER_CHUNK

#define WORDS_PER_CHUNK   ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1)

Definition at line 83 of file tidbitmap.c.

◆ WORDS_PER_PAGE

#define WORDS_PER_PAGE   ((MAX_TUPLES_PER_PAGE - 1) / BITS_PER_BITMAPWORD + 1)

Definition at line 81 of file tidbitmap.c.

Typedef Documentation

◆ PagetableEntry

◆ PTEntryArray

typedef struct PTEntryArray PTEntryArray

◆ PTIterationArray

◆ TBMSharedIteratorState

Enumeration Type Documentation

◆ TBMIteratingState

Enumerator
TBM_NOT_ITERATING 
TBM_ITERATING_PRIVATE 
TBM_ITERATING_SHARED 

Definition at line 138 of file tidbitmap.c.

139 {
140  TBM_NOT_ITERATING, /* not yet converted to page and chunk array */
141  TBM_ITERATING_PRIVATE, /* converted to local page and chunk array */
142  TBM_ITERATING_SHARED /* converted to shared page and chunk array */
TBMIteratingState
Definition: tidbitmap.c:139
@ TBM_ITERATING_SHARED
Definition: tidbitmap.c:142
@ TBM_NOT_ITERATING
Definition: tidbitmap.c:140
@ TBM_ITERATING_PRIVATE
Definition: tidbitmap.c:141

◆ TBMStatus

enum TBMStatus
Enumerator
TBM_EMPTY 
TBM_ONE_PAGE 
TBM_HASH 

Definition at line 128 of file tidbitmap.c.

129 {
130  TBM_EMPTY, /* no hashtable, nentries == 0 */
131  TBM_ONE_PAGE, /* entry1 contains the single entry */
132  TBM_HASH /* pagetable is valid, entry1 is not */
133 } TBMStatus;
TBMStatus
Definition: tidbitmap.c:129
@ TBM_EMPTY
Definition: tidbitmap.c:130
@ TBM_ONE_PAGE
Definition: tidbitmap.c:131
@ TBM_HASH
Definition: tidbitmap.c:132

Function Documentation

◆ pagetable_allocate()

static void* pagetable_allocate ( pagetable_hash *  pagetable,
Size  size 
)
inlinestatic

Definition at line 1497 of file tidbitmap.c.

1498 {
1499  TIDBitmap *tbm = (TIDBitmap *) pagetable->private_data;
1500  PTEntryArray *ptbase;
1501 
1502  if (tbm->dsa == NULL)
1503  return MemoryContextAllocExtended(pagetable->ctx, size,
1505 
1506  /*
1507  * Save the dsapagetable reference in dsapagetableold before allocating
1508  * new memory so that pagetable_free can free the old entry.
1509  */
1510  tbm->dsapagetableold = tbm->dsapagetable;
1512  sizeof(PTEntryArray) + size,
1514  ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
1515 
1516  return ptbase->ptentry;
1517 }
dsa_pointer dsa_allocate_extended(dsa_area *area, size_t size, int flags)
Definition: dsa.c:678
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:949
#define DSA_ALLOC_HUGE
Definition: dsa.h:73
#define DSA_ALLOC_ZERO
Definition: dsa.h:75
#define MCXT_ALLOC_ZERO
Definition: fe_memutils.h:18
#define MCXT_ALLOC_HUGE
Definition: fe_memutils.h:16
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
void * MemoryContextAllocExtended(MemoryContext context, Size size, int flags)
Definition: mcxt.c:1137
dsa_pointer dsapagetableold
Definition: tidbitmap.c:165
dsa_area * dsa
Definition: tidbitmap.c:168
dsa_pointer dsapagetable
Definition: tidbitmap.c:164

References TIDBitmap::dsa, DSA_ALLOC_HUGE, DSA_ALLOC_ZERO, dsa_allocate_extended(), dsa_get_address(), TIDBitmap::dsapagetable, TIDBitmap::dsapagetableold, if(), MCXT_ALLOC_HUGE, MCXT_ALLOC_ZERO, and MemoryContextAllocExtended().

◆ pagetable_free()

static void pagetable_free ( pagetable_hash *  pagetable,
void *  pointer 
)
inlinestatic

Definition at line 1525 of file tidbitmap.c.

1526 {
1527  TIDBitmap *tbm = (TIDBitmap *) pagetable->private_data;
1528 
1529  /* pfree the input pointer if DSA is not available */
1530  if (tbm->dsa == NULL)
1531  pfree(pointer);
1532  else if (DsaPointerIsValid(tbm->dsapagetableold))
1533  {
1534  dsa_free(tbm->dsa, tbm->dsapagetableold);
1536  }
1537 }
void dsa_free(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:833
#define InvalidDsaPointer
Definition: dsa.h:78
#define DsaPointerIsValid(x)
Definition: dsa.h:81
void pfree(void *pointer)
Definition: mcxt.c:1456

References TIDBitmap::dsa, dsa_free(), TIDBitmap::dsapagetableold, DsaPointerIsValid, if(), InvalidDsaPointer, and pfree().

◆ tbm_add_page()

void tbm_add_page ( TIDBitmap tbm,
BlockNumber  pageno 
)

Definition at line 442 of file tidbitmap.c.

443 {
444  /* Enter the page in the bitmap, or mark it lossy if already present */
445  tbm_mark_page_lossy(tbm, pageno);
446  /* If we went over the memory limit, lossify some more pages */
447  if (tbm->nentries > tbm->maxentries)
448  tbm_lossify(tbm);
449 }
int nentries
Definition: tidbitmap.c:154
int maxentries
Definition: tidbitmap.c:155
static void tbm_lossify(TIDBitmap *tbm)
Definition: tidbitmap.c:1354
static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:1282

References TIDBitmap::maxentries, TIDBitmap::nentries, tbm_lossify(), and tbm_mark_page_lossy().

Referenced by bringetbitmap(), and gingetbitmap().

◆ tbm_add_tuples()

void tbm_add_tuples ( TIDBitmap tbm,
const ItemPointer  tids,
int  ntids,
bool  recheck 
)

Definition at line 376 of file tidbitmap.c.

378 {
380  PagetableEntry *page = NULL; /* only valid when currblk is valid */
381  int i;
382 
384  for (i = 0; i < ntids; i++)
385  {
388  int wordnum,
389  bitnum;
390 
391  /* safety check to ensure we don't overrun bit array bounds */
392  if (off < 1 || off > MAX_TUPLES_PER_PAGE)
393  elog(ERROR, "tuple offset out of range: %u", off);
394 
395  /*
396  * Look up target page unless we already did. This saves cycles when
397  * the input includes consecutive tuples on the same page, which is
398  * common enough to justify an extra test here.
399  */
400  if (blk != currblk)
401  {
402  if (tbm_page_is_lossy(tbm, blk))
403  page = NULL; /* remember page is lossy */
404  else
405  page = tbm_get_pageentry(tbm, blk);
406  currblk = blk;
407  }
408 
409  if (page == NULL)
410  continue; /* whole page is already marked */
411 
412  if (page->ischunk)
413  {
414  /* The page is a lossy chunk header, set bit for itself */
415  wordnum = bitnum = 0;
416  }
417  else
418  {
419  /* Page is exact, so set bit for individual tuple */
420  wordnum = WORDNUM(off - 1);
421  bitnum = BITNUM(off - 1);
422  }
423  page->words[wordnum] |= ((bitmapword) 1 << bitnum);
424  page->recheck |= recheck;
425 
426  if (tbm->nentries > tbm->maxentries)
427  {
428  tbm_lossify(tbm);
429  /* Page could have been converted to lossy, so force new lookup */
430  currblk = InvalidBlockNumber;
431  }
432  }
433 }
uint32 bitmapword
Definition: bitmapset.h:44
uint32 BlockNumber
Definition: block.h:31
#define InvalidBlockNumber
Definition: block.h:33
#define ERROR
Definition: elog.h:39
int i
Definition: isn.c:73
static OffsetNumber ItemPointerGetOffsetNumber(const ItemPointerData *pointer)
Definition: itemptr.h:124
static BlockNumber ItemPointerGetBlockNumber(const ItemPointerData *pointer)
Definition: itemptr.h:103
Assert(fmt[strlen(fmt) - 1] !='\n')
uint16 OffsetNumber
Definition: off.h:24
bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]
Definition: tidbitmap.c:105
TBMIteratingState iterating
Definition: tidbitmap.c:158
#define MAX_TUPLES_PER_PAGE
Definition: tidbitmap.c:56
#define WORDNUM(x)
Definition: tidbitmap.c:77
static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:1248
#define BITNUM(x)
Definition: tidbitmap.c:78
static PagetableEntry * tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:1201

References Assert(), BITNUM, elog(), ERROR, i, InvalidBlockNumber, PagetableEntry::ischunk, ItemPointerGetBlockNumber(), ItemPointerGetOffsetNumber(), TIDBitmap::iterating, MAX_TUPLES_PER_PAGE, TIDBitmap::maxentries, TIDBitmap::nentries, PagetableEntry::recheck, tbm_get_pageentry(), tbm_lossify(), TBM_NOT_ITERATING, tbm_page_is_lossy(), WORDNUM, and PagetableEntry::words.

Referenced by blgetbitmap(), btgetbitmap(), collectMatchBitmap(), GinDataLeafPageGetItemsToTbm(), gingetbitmap(), ginPostingListDecodeAllSegmentsToTbm(), gistScanPage(), hashgetbitmap(), scanPendingInsert(), and storeBitmap().

◆ tbm_advance_schunkbit()

static void tbm_advance_schunkbit ( PagetableEntry chunk,
int *  schunkbitp 
)
inlinestatic

Definition at line 940 of file tidbitmap.c.

941 {
942  int schunkbit = *schunkbitp;
943 
944  while (schunkbit < PAGES_PER_CHUNK)
945  {
946  int wordnum = WORDNUM(schunkbit);
947  int bitnum = BITNUM(schunkbit);
948 
949  if ((chunk->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
950  break;
951  schunkbit++;
952  }
953 
954  *schunkbitp = schunkbit;
955 }
#define PAGES_PER_CHUNK
Definition: tidbitmap.c:73

References BITNUM, PAGES_PER_CHUNK, WORDNUM, and PagetableEntry::words.

Referenced by tbm_iterate(), and tbm_shared_iterate().

◆ tbm_attach_shared_iterate()

TBMSharedIterator* tbm_attach_shared_iterate ( dsa_area dsa,
dsa_pointer  dp 
)

Definition at line 1464 of file tidbitmap.c.

1465 {
1466  TBMSharedIterator *iterator;
1467  TBMSharedIteratorState *istate;
1468 
1469  /*
1470  * Create the TBMSharedIterator struct, with enough trailing space to
1471  * serve the needs of the TBMIterateResult sub-struct.
1472  */
1473  iterator = (TBMSharedIterator *) palloc0(sizeof(TBMSharedIterator) +
1474  MAX_TUPLES_PER_PAGE * sizeof(OffsetNumber));
1475 
1476  istate = (TBMSharedIteratorState *) dsa_get_address(dsa, dp);
1477 
1478  iterator->state = istate;
1479 
1480  iterator->ptbase = dsa_get_address(dsa, istate->pagetable);
1481 
1482  if (istate->npages)
1483  iterator->ptpages = dsa_get_address(dsa, istate->spages);
1484  if (istate->nchunks)
1485  iterator->ptchunks = dsa_get_address(dsa, istate->schunks);
1486 
1487  return iterator;
1488 }
void * palloc0(Size size)
Definition: mcxt.c:1257
dsa_pointer pagetable
Definition: tidbitmap.c:196
dsa_pointer spages
Definition: tidbitmap.c:197
dsa_pointer schunks
Definition: tidbitmap.c:198
TBMSharedIteratorState * state
Definition: tidbitmap.c:220
PTEntryArray * ptbase
Definition: tidbitmap.c:221
PTIterationArray * ptchunks
Definition: tidbitmap.c:223
PTIterationArray * ptpages
Definition: tidbitmap.c:222

References dsa_get_address(), MAX_TUPLES_PER_PAGE, TBMSharedIteratorState::nchunks, TBMSharedIteratorState::npages, TBMSharedIteratorState::pagetable, palloc0(), TBMSharedIterator::ptbase, TBMSharedIterator::ptchunks, TBMSharedIterator::ptpages, TBMSharedIteratorState::schunks, TBMSharedIteratorState::spages, and TBMSharedIterator::state.

Referenced by BitmapHeapNext().

◆ tbm_begin_iterate()

TBMIterator* tbm_begin_iterate ( TIDBitmap tbm)

Definition at line 688 of file tidbitmap.c.

689 {
690  TBMIterator *iterator;
691 
693 
694  /*
695  * Create the TBMIterator struct, with enough trailing space to serve the
696  * needs of the TBMIterateResult sub-struct.
697  */
698  iterator = (TBMIterator *) palloc(sizeof(TBMIterator) +
700  iterator->tbm = tbm;
701 
702  /*
703  * Initialize iteration pointers.
704  */
705  iterator->spageptr = 0;
706  iterator->schunkptr = 0;
707  iterator->schunkbit = 0;
708 
709  /*
710  * If we have a hashtable, create and fill the sorted page lists, unless
711  * we already did that for a previous iterator. Note that the lists are
712  * attached to the bitmap not the iterator, so they can be used by more
713  * than one iterator.
714  */
715  if (tbm->status == TBM_HASH && tbm->iterating == TBM_NOT_ITERATING)
716  {
717  pagetable_iterator i;
718  PagetableEntry *page;
719  int npages;
720  int nchunks;
721 
722  if (!tbm->spages && tbm->npages > 0)
723  tbm->spages = (PagetableEntry **)
725  tbm->npages * sizeof(PagetableEntry *));
726  if (!tbm->schunks && tbm->nchunks > 0)
727  tbm->schunks = (PagetableEntry **)
729  tbm->nchunks * sizeof(PagetableEntry *));
730 
731  npages = nchunks = 0;
732  pagetable_start_iterate(tbm->pagetable, &i);
733  while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
734  {
735  if (page->ischunk)
736  tbm->schunks[nchunks++] = page;
737  else
738  tbm->spages[npages++] = page;
739  }
740  Assert(npages == tbm->npages);
741  Assert(nchunks == tbm->nchunks);
742  if (npages > 1)
743  qsort(tbm->spages, npages, sizeof(PagetableEntry *),
745  if (nchunks > 1)
746  qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
748  }
749 
751 
752  return iterator;
753 }
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1021
void * palloc(Size size)
Definition: mcxt.c:1226
#define qsort(a, b, c, d)
Definition: port.h:445
int spageptr
Definition: tidbitmap.c:180
TIDBitmap * tbm
Definition: tidbitmap.c:179
int schunkbit
Definition: tidbitmap.c:182
int schunkptr
Definition: tidbitmap.c:181
struct pagetable_hash * pagetable
Definition: tidbitmap.c:153
PagetableEntry ** schunks
Definition: tidbitmap.c:163
MemoryContext mcxt
Definition: tidbitmap.c:151
int npages
Definition: tidbitmap.c:156
int nchunks
Definition: tidbitmap.c:157
TBMStatus status
Definition: tidbitmap.c:152
PagetableEntry ** spages
Definition: tidbitmap.c:162
static int tbm_comparator(const void *left, const void *right)
Definition: tidbitmap.c:1423

References Assert(), i, PagetableEntry::ischunk, TIDBitmap::iterating, MAX_TUPLES_PER_PAGE, TIDBitmap::mcxt, MemoryContextAlloc(), TIDBitmap::nchunks, TIDBitmap::npages, TIDBitmap::pagetable, palloc(), qsort, TBMIterator::schunkbit, TBMIterator::schunkptr, TIDBitmap::schunks, TBMIterator::spageptr, TIDBitmap::spages, TIDBitmap::status, TBMIterator::tbm, tbm_comparator(), TBM_HASH, TBM_ITERATING_PRIVATE, TBM_ITERATING_SHARED, and TBM_NOT_ITERATING.

Referenced by BitmapHeapNext(), and startScanEntry().

◆ tbm_calculate_entries()

long tbm_calculate_entries ( double  maxbytes)

Definition at line 1545 of file tidbitmap.c.

1546 {
1547  long nbuckets;
1548 
1549  /*
1550  * Estimate number of hashtable entries we can have within maxbytes. This
1551  * estimates the hash cost as sizeof(PagetableEntry), which is good enough
1552  * for our purpose. Also count an extra Pointer per entry for the arrays
1553  * created during iteration readout.
1554  */
1555  nbuckets = maxbytes /
1556  (sizeof(PagetableEntry) + sizeof(Pointer) + sizeof(Pointer));
1557  nbuckets = Min(nbuckets, INT_MAX - 1); /* safety limit */
1558  nbuckets = Max(nbuckets, 16); /* sanity limit */
1559 
1560  return nbuckets;
1561 }
#define Min(x, y)
Definition: c.h:993
#define Max(x, y)
Definition: c.h:987
char * Pointer
Definition: c.h:472
struct PagetableEntry PagetableEntry

References Max, and Min.

Referenced by compute_bitmap_pages(), and tbm_create().

◆ tbm_comparator()

static int tbm_comparator ( const void *  left,
const void *  right 
)
static

Definition at line 1423 of file tidbitmap.c.

1424 {
1425  BlockNumber l = (*((PagetableEntry *const *) left))->blockno;
1426  BlockNumber r = (*((PagetableEntry *const *) right))->blockno;
1427 
1428  if (l < r)
1429  return -1;
1430  else if (l > r)
1431  return 1;
1432  return 0;
1433 }

Referenced by tbm_begin_iterate().

◆ tbm_create()

TIDBitmap* tbm_create ( long  maxbytes,
dsa_area dsa 
)

Definition at line 265 of file tidbitmap.c.

266 {
267  TIDBitmap *tbm;
268 
269  /* Create the TIDBitmap struct and zero all its fields */
270  tbm = makeNode(TIDBitmap);
271 
272  tbm->mcxt = CurrentMemoryContext;
273  tbm->status = TBM_EMPTY;
274 
275  tbm->maxentries = (int) tbm_calculate_entries(maxbytes);
276  tbm->lossify_start = 0;
277  tbm->dsa = dsa;
280  tbm->ptpages = InvalidDsaPointer;
282 
283  return tbm;
284 }
MemoryContext CurrentMemoryContext
Definition: mcxt.c:135
#define makeNode(_type_)
Definition: nodes.h:176
dsa_pointer ptpages
Definition: tidbitmap.c:166
uint32 lossify_start
Definition: tidbitmap.c:159
dsa_pointer ptchunks
Definition: tidbitmap.c:167
long tbm_calculate_entries(double maxbytes)
Definition: tidbitmap.c:1545

References CurrentMemoryContext, TIDBitmap::dsa, TIDBitmap::dsapagetable, TIDBitmap::dsapagetableold, InvalidDsaPointer, TIDBitmap::lossify_start, makeNode, TIDBitmap::maxentries, TIDBitmap::mcxt, TIDBitmap::ptchunks, TIDBitmap::ptpages, TIDBitmap::status, tbm_calculate_entries(), and TBM_EMPTY.

Referenced by collectMatchBitmap(), MultiExecBitmapIndexScan(), and MultiExecBitmapOr().

◆ tbm_create_pagetable()

static void tbm_create_pagetable ( TIDBitmap tbm)
static

Definition at line 291 of file tidbitmap.c.

292 {
293  Assert(tbm->status != TBM_HASH);
294  Assert(tbm->pagetable == NULL);
295 
296  tbm->pagetable = pagetable_create(tbm->mcxt, 128, tbm);
297 
298  /* If entry1 is valid, push it into the hashtable */
299  if (tbm->status == TBM_ONE_PAGE)
300  {
301  PagetableEntry *page;
302  bool found;
303  char oldstatus;
304 
305  page = pagetable_insert(tbm->pagetable,
306  tbm->entry1.blockno,
307  &found);
308  Assert(!found);
309  oldstatus = page->status;
310  memcpy(page, &tbm->entry1, sizeof(PagetableEntry));
311  page->status = oldstatus;
312  }
313 
314  tbm->status = TBM_HASH;
315 }
BlockNumber blockno
Definition: tidbitmap.c:101
PagetableEntry entry1
Definition: tidbitmap.c:160

References Assert(), PagetableEntry::blockno, TIDBitmap::entry1, TIDBitmap::mcxt, TIDBitmap::pagetable, PagetableEntry::status, TIDBitmap::status, TBM_HASH, and TBM_ONE_PAGE.

Referenced by tbm_get_pageentry(), and tbm_mark_page_lossy().

◆ tbm_end_iterate()

void tbm_end_iterate ( TBMIterator iterator)

Definition at line 1145 of file tidbitmap.c.

1146 {
1147  pfree(iterator);
1148 }

References pfree().

Referenced by BitmapPrefetch(), entryGetItem(), ExecEndBitmapHeapScan(), ExecReScanBitmapHeapScan(), ginFreeScanKeys(), and startScanEntry().

◆ tbm_end_shared_iterate()

void tbm_end_shared_iterate ( TBMSharedIterator iterator)

Definition at line 1157 of file tidbitmap.c.

1158 {
1159  pfree(iterator);
1160 }

References pfree().

Referenced by BitmapPrefetch(), ExecEndBitmapHeapScan(), and ExecReScanBitmapHeapScan().

◆ tbm_extract_page_tuple()

static int tbm_extract_page_tuple ( PagetableEntry page,
TBMIterateResult output 
)
inlinestatic

Definition at line 910 of file tidbitmap.c.

911 {
912  int wordnum;
913  int ntuples = 0;
914 
915  for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
916  {
917  bitmapword w = page->words[wordnum];
918 
919  if (w != 0)
920  {
921  int off = wordnum * BITS_PER_BITMAPWORD + 1;
922 
923  while (w != 0)
924  {
925  if (w & 1)
926  output->offsets[ntuples++] = (OffsetNumber) off;
927  off++;
928  w >>= 1;
929  }
930  }
931  }
932 
933  return ntuples;
934 }
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:43
FILE * output
#define WORDS_PER_PAGE
Definition: tidbitmap.c:81

References BITS_PER_BITMAPWORD, output, PagetableEntry::words, and WORDS_PER_PAGE.

Referenced by tbm_iterate(), and tbm_shared_iterate().

◆ tbm_find_pageentry()

static const PagetableEntry * tbm_find_pageentry ( const TIDBitmap tbm,
BlockNumber  pageno 
)
static

Definition at line 1168 of file tidbitmap.c.

1169 {
1170  const PagetableEntry *page;
1171 
1172  if (tbm->nentries == 0) /* in case pagetable doesn't exist */
1173  return NULL;
1174 
1175  if (tbm->status == TBM_ONE_PAGE)
1176  {
1177  page = &tbm->entry1;
1178  if (page->blockno != pageno)
1179  return NULL;
1180  Assert(!page->ischunk);
1181  return page;
1182  }
1183 
1184  page = pagetable_lookup(tbm->pagetable, pageno);
1185  if (page == NULL)
1186  return NULL;
1187  if (page->ischunk)
1188  return NULL; /* don't want a lossy chunk header */
1189  return page;
1190 }

References Assert(), PagetableEntry::blockno, TIDBitmap::entry1, PagetableEntry::ischunk, TIDBitmap::nentries, TIDBitmap::pagetable, TIDBitmap::status, and TBM_ONE_PAGE.

Referenced by tbm_intersect_page().

◆ tbm_free()

void tbm_free ( TIDBitmap tbm)

Definition at line 321 of file tidbitmap.c.

322 {
323  if (tbm->pagetable)
324  pagetable_destroy(tbm->pagetable);
325  if (tbm->spages)
326  pfree(tbm->spages);
327  if (tbm->schunks)
328  pfree(tbm->schunks);
329  pfree(tbm);
330 }

References TIDBitmap::pagetable, pfree(), TIDBitmap::schunks, and TIDBitmap::spages.

Referenced by ExecEndBitmapHeapScan(), ExecReScanBitmapHeapScan(), ginFreeScanKeys(), MultiExecBitmapAnd(), MultiExecBitmapOr(), and startScanEntry().

◆ tbm_free_shared_area()

void tbm_free_shared_area ( dsa_area dsa,
dsa_pointer  dp 
)

Definition at line 340 of file tidbitmap.c.

341 {
342  TBMSharedIteratorState *istate = dsa_get_address(dsa, dp);
343  PTEntryArray *ptbase;
344  PTIterationArray *ptpages;
345  PTIterationArray *ptchunks;
346 
347  if (DsaPointerIsValid(istate->pagetable))
348  {
349  ptbase = dsa_get_address(dsa, istate->pagetable);
350  if (pg_atomic_sub_fetch_u32(&ptbase->refcount, 1) == 0)
351  dsa_free(dsa, istate->pagetable);
352  }
353  if (DsaPointerIsValid(istate->spages))
354  {
355  ptpages = dsa_get_address(dsa, istate->spages);
356  if (pg_atomic_sub_fetch_u32(&ptpages->refcount, 1) == 0)
357  dsa_free(dsa, istate->spages);
358  }
359  if (DsaPointerIsValid(istate->schunks))
360  {
361  ptchunks = dsa_get_address(dsa, istate->schunks);
362  if (pg_atomic_sub_fetch_u32(&ptchunks->refcount, 1) == 0)
363  dsa_free(dsa, istate->schunks);
364  }
365 
366  dsa_free(dsa, dp);
367 }
static uint32 pg_atomic_sub_fetch_u32(volatile pg_atomic_uint32 *ptr, int32 sub_)
Definition: atomics.h:396
pg_atomic_uint32 refcount
Definition: tidbitmap.c:113
pg_atomic_uint32 refcount
Definition: tidbitmap.c:210

References dsa_free(), dsa_get_address(), DsaPointerIsValid, TBMSharedIteratorState::pagetable, pg_atomic_sub_fetch_u32(), PTEntryArray::refcount, PTIterationArray::refcount, TBMSharedIteratorState::schunks, and TBMSharedIteratorState::spages.

Referenced by ExecBitmapHeapReInitializeDSM().

◆ tbm_get_pageentry()

static PagetableEntry * tbm_get_pageentry ( TIDBitmap tbm,
BlockNumber  pageno 
)
static

Definition at line 1201 of file tidbitmap.c.

1202 {
1203  PagetableEntry *page;
1204  bool found;
1205 
1206  if (tbm->status == TBM_EMPTY)
1207  {
1208  /* Use the fixed slot */
1209  page = &tbm->entry1;
1210  found = false;
1211  tbm->status = TBM_ONE_PAGE;
1212  }
1213  else
1214  {
1215  if (tbm->status == TBM_ONE_PAGE)
1216  {
1217  page = &tbm->entry1;
1218  if (page->blockno == pageno)
1219  return page;
1220  /* Time to switch from one page to a hashtable */
1221  tbm_create_pagetable(tbm);
1222  }
1223 
1224  /* Look up or create an entry */
1225  page = pagetable_insert(tbm->pagetable, pageno, &found);
1226  }
1227 
1228  /* Initialize it if not present before */
1229  if (!found)
1230  {
1231  char oldstatus = page->status;
1232 
1233  MemSet(page, 0, sizeof(PagetableEntry));
1234  page->status = oldstatus;
1235  page->blockno = pageno;
1236  /* must count it too */
1237  tbm->nentries++;
1238  tbm->npages++;
1239  }
1240 
1241  return page;
1242 }
#define MemSet(start, val, len)
Definition: c.h:1009
static void tbm_create_pagetable(TIDBitmap *tbm)
Definition: tidbitmap.c:291

References PagetableEntry::blockno, TIDBitmap::entry1, MemSet, TIDBitmap::nentries, TIDBitmap::npages, TIDBitmap::pagetable, PagetableEntry::status, TIDBitmap::status, tbm_create_pagetable(), TBM_EMPTY, and TBM_ONE_PAGE.

Referenced by tbm_add_tuples(), and tbm_union_page().

◆ tbm_intersect()

void tbm_intersect ( TIDBitmap a,
const TIDBitmap b 
)

Definition at line 539 of file tidbitmap.c.

540 {
541  Assert(!a->iterating);
542  /* Nothing to do if a is empty */
543  if (a->nentries == 0)
544  return;
545  /* Scan through chunks and pages in a, try to match to b */
546  if (a->status == TBM_ONE_PAGE)
547  {
548  if (tbm_intersect_page(a, &a->entry1, b))
549  {
550  /* Page is now empty, remove it from a */
551  Assert(!a->entry1.ischunk);
552  a->npages--;
553  a->nentries--;
554  Assert(a->nentries == 0);
555  a->status = TBM_EMPTY;
556  }
557  }
558  else
559  {
560  pagetable_iterator i;
561  PagetableEntry *apage;
562 
563  Assert(a->status == TBM_HASH);
564  pagetable_start_iterate(a->pagetable, &i);
565  while ((apage = pagetable_iterate(a->pagetable, &i)) != NULL)
566  {
567  if (tbm_intersect_page(a, apage, b))
568  {
569  /* Page or chunk is now empty, remove it from a */
570  if (apage->ischunk)
571  a->nchunks--;
572  else
573  a->npages--;
574  a->nentries--;
575  if (!pagetable_delete(a->pagetable, apage->blockno))
576  elog(ERROR, "hash table corrupted");
577  }
578  }
579  }
580 }
int b
Definition: isn.c:70
int a
Definition: isn.c:69
static bool tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
Definition: tidbitmap.c:588

References a, Assert(), b, PagetableEntry::blockno, elog(), ERROR, i, PagetableEntry::ischunk, TBM_EMPTY, TBM_HASH, tbm_intersect_page(), and TBM_ONE_PAGE.

Referenced by MultiExecBitmapAnd().

◆ tbm_intersect_page()

static bool tbm_intersect_page ( TIDBitmap a,
PagetableEntry apage,
const TIDBitmap b 
)
static

Definition at line 588 of file tidbitmap.c.

589 {
590  const PagetableEntry *bpage;
591  int wordnum;
592 
593  if (apage->ischunk)
594  {
595  /* Scan each bit in chunk, try to clear */
596  bool candelete = true;
597 
598  for (wordnum = 0; wordnum < WORDS_PER_CHUNK; wordnum++)
599  {
600  bitmapword w = apage->words[wordnum];
601 
602  if (w != 0)
603  {
604  bitmapword neww = w;
605  BlockNumber pg;
606  int bitnum;
607 
608  pg = apage->blockno + (wordnum * BITS_PER_BITMAPWORD);
609  bitnum = 0;
610  while (w != 0)
611  {
612  if (w & 1)
613  {
614  if (!tbm_page_is_lossy(b, pg) &&
615  tbm_find_pageentry(b, pg) == NULL)
616  {
617  /* Page is not in b at all, lose lossy bit */
618  neww &= ~((bitmapword) 1 << bitnum);
619  }
620  }
621  pg++;
622  bitnum++;
623  w >>= 1;
624  }
625  apage->words[wordnum] = neww;
626  if (neww != 0)
627  candelete = false;
628  }
629  }
630  return candelete;
631  }
632  else if (tbm_page_is_lossy(b, apage->blockno))
633  {
634  /*
635  * Some of the tuples in 'a' might not satisfy the quals for 'b', but
636  * because the page 'b' is lossy, we don't know which ones. Therefore
637  * we mark 'a' as requiring rechecks, to indicate that at most those
638  * tuples set in 'a' are matches.
639  */
640  apage->recheck = true;
641  return false;
642  }
643  else
644  {
645  bool candelete = true;
646 
647  bpage = tbm_find_pageentry(b, apage->blockno);
648  if (bpage != NULL)
649  {
650  /* Both pages are exact, merge at the bit level */
651  Assert(!bpage->ischunk);
652  for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
653  {
654  apage->words[wordnum] &= bpage->words[wordnum];
655  if (apage->words[wordnum] != 0)
656  candelete = false;
657  }
658  apage->recheck |= bpage->recheck;
659  }
660  /* If there is no matching b page, we can just delete the a page */
661  return candelete;
662  }
663 }
static const PagetableEntry * tbm_find_pageentry(const TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:1168
#define WORDS_PER_CHUNK
Definition: tidbitmap.c:83

References Assert(), b, BITS_PER_BITMAPWORD, PagetableEntry::blockno, PagetableEntry::ischunk, PagetableEntry::recheck, tbm_find_pageentry(), tbm_page_is_lossy(), PagetableEntry::words, WORDS_PER_CHUNK, and WORDS_PER_PAGE.

Referenced by tbm_intersect().

◆ tbm_is_empty()

bool tbm_is_empty ( const TIDBitmap tbm)

Definition at line 669 of file tidbitmap.c.

670 {
671  return (tbm->nentries == 0);
672 }

References TIDBitmap::nentries.

Referenced by MultiExecBitmapAnd(), and startScanEntry().

◆ tbm_iterate()

TBMIterateResult* tbm_iterate ( TBMIterator iterator)

Definition at line 970 of file tidbitmap.c.

971 {
972  TIDBitmap *tbm = iterator->tbm;
973  TBMIterateResult *output = &(iterator->output);
974 
976 
977  /*
978  * If lossy chunk pages remain, make sure we've advanced schunkptr/
979  * schunkbit to the next set bit.
980  */
981  while (iterator->schunkptr < tbm->nchunks)
982  {
983  PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
984  int schunkbit = iterator->schunkbit;
985 
986  tbm_advance_schunkbit(chunk, &schunkbit);
987  if (schunkbit < PAGES_PER_CHUNK)
988  {
989  iterator->schunkbit = schunkbit;
990  break;
991  }
992  /* advance to next chunk */
993  iterator->schunkptr++;
994  iterator->schunkbit = 0;
995  }
996 
997  /*
998  * If both chunk and per-page data remain, must output the numerically
999  * earlier page.
1000  */
1001  if (iterator->schunkptr < tbm->nchunks)
1002  {
1003  PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
1004  BlockNumber chunk_blockno;
1005 
1006  chunk_blockno = chunk->blockno + iterator->schunkbit;
1007  if (iterator->spageptr >= tbm->npages ||
1008  chunk_blockno < tbm->spages[iterator->spageptr]->blockno)
1009  {
1010  /* Return a lossy page indicator from the chunk */
1011  output->blockno = chunk_blockno;
1012  output->ntuples = -1;
1013  output->recheck = true;
1014  iterator->schunkbit++;
1015  return output;
1016  }
1017  }
1018 
1019  if (iterator->spageptr < tbm->npages)
1020  {
1021  PagetableEntry *page;
1022  int ntuples;
1023 
1024  /* In TBM_ONE_PAGE state, we don't allocate an spages[] array */
1025  if (tbm->status == TBM_ONE_PAGE)
1026  page = &tbm->entry1;
1027  else
1028  page = tbm->spages[iterator->spageptr];
1029 
1030  /* scan bitmap to extract individual offset numbers */
1031  ntuples = tbm_extract_page_tuple(page, output);
1032  output->blockno = page->blockno;
1033  output->ntuples = ntuples;
1034  output->recheck = page->recheck;
1035  iterator->spageptr++;
1036  return output;
1037  }
1038 
1039  /* Nothing more in the bitmap */
1040  return NULL;
1041 }
TBMIterateResult output
Definition: tidbitmap.c:183
static void tbm_advance_schunkbit(PagetableEntry *chunk, int *schunkbitp)
Definition: tidbitmap.c:940
static int tbm_extract_page_tuple(PagetableEntry *page, TBMIterateResult *output)
Definition: tidbitmap.c:910

References Assert(), PagetableEntry::blockno, TIDBitmap::entry1, TIDBitmap::iterating, TIDBitmap::nchunks, TIDBitmap::npages, TBMIterator::output, output, PAGES_PER_CHUNK, PagetableEntry::recheck, TBMIterator::schunkbit, TBMIterator::schunkptr, TIDBitmap::schunks, TBMIterator::spageptr, TIDBitmap::spages, TIDBitmap::status, TBMIterator::tbm, tbm_advance_schunkbit(), tbm_extract_page_tuple(), TBM_ITERATING_PRIVATE, and TBM_ONE_PAGE.

Referenced by BitmapAdjustPrefetchIterator(), BitmapHeapNext(), BitmapPrefetch(), and entryGetItem().

◆ tbm_lossify()

static void tbm_lossify ( TIDBitmap tbm)
static

Definition at line 1354 of file tidbitmap.c.

1355 {
1356  pagetable_iterator i;
1357  PagetableEntry *page;
1358 
1359  /*
1360  * XXX Really stupid implementation: this just lossifies pages in
1361  * essentially random order. We should be paying some attention to the
1362  * number of bits set in each page, instead.
1363  *
1364  * Since we are called as soon as nentries exceeds maxentries, we should
1365  * push nentries down to significantly less than maxentries, or else we'll
1366  * just end up doing this again very soon. We shoot for maxentries/2.
1367  */
1369  Assert(tbm->status == TBM_HASH);
1370 
1371  pagetable_start_iterate_at(tbm->pagetable, &i, tbm->lossify_start);
1372  while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
1373  {
1374  if (page->ischunk)
1375  continue; /* already a chunk header */
1376 
1377  /*
1378  * If the page would become a chunk header, we won't save anything by
1379  * converting it to lossy, so skip it.
1380  */
1381  if ((page->blockno % PAGES_PER_CHUNK) == 0)
1382  continue;
1383 
1384  /* This does the dirty work ... */
1385  tbm_mark_page_lossy(tbm, page->blockno);
1386 
1387  if (tbm->nentries <= tbm->maxentries / 2)
1388  {
1389  /*
1390  * We have made enough room. Remember where to start lossifying
1391  * next round, so we evenly iterate over the hashtable.
1392  */
1393  tbm->lossify_start = i.cur;
1394  break;
1395  }
1396 
1397  /*
1398  * Note: tbm_mark_page_lossy may have inserted a lossy chunk into the
1399  * hashtable and may have deleted the non-lossy chunk. We can
1400  * continue the same hash table scan, since failure to visit one
1401  * element or visiting the newly inserted element, isn't fatal.
1402  */
1403  }
1404 
1405  /*
1406  * With a big bitmap and small work_mem, it's possible that we cannot get
1407  * under maxentries. Again, if that happens, we'd end up uselessly
1408  * calling tbm_lossify over and over. To prevent this from becoming a
1409  * performance sink, force maxentries up to at least double the current
1410  * number of entries. (In essence, we're admitting inability to fit
1411  * within work_mem when we do this.) Note that this test will not fire if
1412  * we broke out of the loop early; and if we didn't, the current number of
1413  * entries is simply not reducible any further.
1414  */
1415  if (tbm->nentries > tbm->maxentries / 2)
1416  tbm->maxentries = Min(tbm->nentries, (INT_MAX - 1) / 2) * 2;
1417 }

References Assert(), PagetableEntry::blockno, i, PagetableEntry::ischunk, TIDBitmap::iterating, TIDBitmap::lossify_start, TIDBitmap::maxentries, Min, TIDBitmap::nentries, PAGES_PER_CHUNK, TIDBitmap::pagetable, TIDBitmap::status, TBM_HASH, tbm_mark_page_lossy(), and TBM_NOT_ITERATING.

Referenced by tbm_add_page(), tbm_add_tuples(), and tbm_union_page().

◆ tbm_mark_page_lossy()

static void tbm_mark_page_lossy ( TIDBitmap tbm,
BlockNumber  pageno 
)
static

Definition at line 1282 of file tidbitmap.c.

1283 {
1284  PagetableEntry *page;
1285  bool found;
1286  BlockNumber chunk_pageno;
1287  int bitno;
1288  int wordnum;
1289  int bitnum;
1290 
1291  /* We force the bitmap into hashtable mode whenever it's lossy */
1292  if (tbm->status != TBM_HASH)
1293  tbm_create_pagetable(tbm);
1294 
1295  bitno = pageno % PAGES_PER_CHUNK;
1296  chunk_pageno = pageno - bitno;
1297 
1298  /*
1299  * Remove any extant non-lossy entry for the page. If the page is its own
1300  * chunk header, however, we skip this and handle the case below.
1301  */
1302  if (bitno != 0)
1303  {
1304  if (pagetable_delete(tbm->pagetable, pageno))
1305  {
1306  /* It was present, so adjust counts */
1307  tbm->nentries--;
1308  tbm->npages--; /* assume it must have been non-lossy */
1309  }
1310  }
1311 
1312  /* Look up or create entry for chunk-header page */
1313  page = pagetable_insert(tbm->pagetable, chunk_pageno, &found);
1314 
1315  /* Initialize it if not present before */
1316  if (!found)
1317  {
1318  char oldstatus = page->status;
1319 
1320  MemSet(page, 0, sizeof(PagetableEntry));
1321  page->status = oldstatus;
1322  page->blockno = chunk_pageno;
1323  page->ischunk = true;
1324  /* must count it too */
1325  tbm->nentries++;
1326  tbm->nchunks++;
1327  }
1328  else if (!page->ischunk)
1329  {
1330  char oldstatus = page->status;
1331 
1332  /* chunk header page was formerly non-lossy, make it lossy */
1333  MemSet(page, 0, sizeof(PagetableEntry));
1334  page->status = oldstatus;
1335  page->blockno = chunk_pageno;
1336  page->ischunk = true;
1337  /* we assume it had some tuple bit(s) set, so mark it lossy */
1338  page->words[0] = ((bitmapword) 1 << 0);
1339  /* adjust counts */
1340  tbm->nchunks++;
1341  tbm->npages--;
1342  }
1343 
1344  /* Now set the original target page's bit */
1345  wordnum = WORDNUM(bitno);
1346  bitnum = BITNUM(bitno);
1347  page->words[wordnum] |= ((bitmapword) 1 << bitnum);
1348 }

References BITNUM, PagetableEntry::blockno, PagetableEntry::ischunk, MemSet, TIDBitmap::nchunks, TIDBitmap::nentries, TIDBitmap::npages, PAGES_PER_CHUNK, TIDBitmap::pagetable, PagetableEntry::status, TIDBitmap::status, tbm_create_pagetable(), TBM_HASH, WORDNUM, and PagetableEntry::words.

Referenced by tbm_add_page(), tbm_lossify(), and tbm_union_page().

◆ tbm_page_is_lossy()

static bool tbm_page_is_lossy ( const TIDBitmap tbm,
BlockNumber  pageno 
)
static

Definition at line 1248 of file tidbitmap.c.

1249 {
1250  PagetableEntry *page;
1251  BlockNumber chunk_pageno;
1252  int bitno;
1253 
1254  /* we can skip the lookup if there are no lossy chunks */
1255  if (tbm->nchunks == 0)
1256  return false;
1257  Assert(tbm->status == TBM_HASH);
1258 
1259  bitno = pageno % PAGES_PER_CHUNK;
1260  chunk_pageno = pageno - bitno;
1261 
1262  page = pagetable_lookup(tbm->pagetable, chunk_pageno);
1263 
1264  if (page != NULL && page->ischunk)
1265  {
1266  int wordnum = WORDNUM(bitno);
1267  int bitnum = BITNUM(bitno);
1268 
1269  if ((page->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
1270  return true;
1271  }
1272  return false;
1273 }

References Assert(), BITNUM, PagetableEntry::ischunk, TIDBitmap::nchunks, PAGES_PER_CHUNK, TIDBitmap::pagetable, TIDBitmap::status, TBM_HASH, WORDNUM, and PagetableEntry::words.

Referenced by tbm_add_tuples(), tbm_intersect_page(), and tbm_union_page().

◆ tbm_prepare_shared_iterate()

dsa_pointer tbm_prepare_shared_iterate ( TIDBitmap tbm)

Definition at line 765 of file tidbitmap.c.

766 {
767  dsa_pointer dp;
768  TBMSharedIteratorState *istate;
769  PTEntryArray *ptbase = NULL;
770  PTIterationArray *ptpages = NULL;
771  PTIterationArray *ptchunks = NULL;
772 
773  Assert(tbm->dsa != NULL);
775 
776  /*
777  * Allocate TBMSharedIteratorState from DSA to hold the shared members and
778  * lock, this will also be used by multiple worker for shared iterate.
779  */
780  dp = dsa_allocate0(tbm->dsa, sizeof(TBMSharedIteratorState));
781  istate = dsa_get_address(tbm->dsa, dp);
782 
783  /*
784  * If we're not already iterating, create and fill the sorted page lists.
785  * (If we are, the sorted page lists are already stored in the TIDBitmap,
786  * and we can just reuse them.)
787  */
788  if (tbm->iterating == TBM_NOT_ITERATING)
789  {
790  pagetable_iterator i;
791  PagetableEntry *page;
792  int idx;
793  int npages;
794  int nchunks;
795 
796  /*
797  * Allocate the page and chunk array memory from the DSA to share
798  * across multiple processes.
799  */
800  if (tbm->npages)
801  {
802  tbm->ptpages = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
803  tbm->npages * sizeof(int));
804  ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
805  pg_atomic_init_u32(&ptpages->refcount, 0);
806  }
807  if (tbm->nchunks)
808  {
809  tbm->ptchunks = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
810  tbm->nchunks * sizeof(int));
811  ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
812  pg_atomic_init_u32(&ptchunks->refcount, 0);
813  }
814 
815  /*
816  * If TBM status is TBM_HASH then iterate over the pagetable and
817  * convert it to page and chunk arrays. But if it's in the
818  * TBM_ONE_PAGE mode then directly allocate the space for one entry
819  * from the DSA.
820  */
821  npages = nchunks = 0;
822  if (tbm->status == TBM_HASH)
823  {
824  ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
825 
826  pagetable_start_iterate(tbm->pagetable, &i);
827  while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
828  {
829  idx = page - ptbase->ptentry;
830  if (page->ischunk)
831  ptchunks->index[nchunks++] = idx;
832  else
833  ptpages->index[npages++] = idx;
834  }
835 
836  Assert(npages == tbm->npages);
837  Assert(nchunks == tbm->nchunks);
838  }
839  else if (tbm->status == TBM_ONE_PAGE)
840  {
841  /*
842  * In one page mode allocate the space for one pagetable entry,
843  * initialize it, and directly store its index (i.e. 0) in the
844  * page array.
845  */
846  tbm->dsapagetable = dsa_allocate(tbm->dsa, sizeof(PTEntryArray) +
847  sizeof(PagetableEntry));
848  ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
849  memcpy(ptbase->ptentry, &tbm->entry1, sizeof(PagetableEntry));
850  ptpages->index[0] = 0;
851  }
852 
853  if (ptbase != NULL)
854  pg_atomic_init_u32(&ptbase->refcount, 0);
855  if (npages > 1)
856  qsort_arg(ptpages->index, npages, sizeof(int),
857  tbm_shared_comparator, ptbase->ptentry);
858  if (nchunks > 1)
859  qsort_arg(ptchunks->index, nchunks, sizeof(int),
860  tbm_shared_comparator, ptbase->ptentry);
861  }
862 
863  /*
864  * Store the TBM members in the shared state so that we can share them
865  * across multiple processes.
866  */
867  istate->nentries = tbm->nentries;
868  istate->maxentries = tbm->maxentries;
869  istate->npages = tbm->npages;
870  istate->nchunks = tbm->nchunks;
871  istate->pagetable = tbm->dsapagetable;
872  istate->spages = tbm->ptpages;
873  istate->schunks = tbm->ptchunks;
874 
875  ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
876  ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
877  ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
878 
879  /*
880  * For every shared iterator, referring to pagetable and iterator array,
881  * increase the refcount by 1 so that while freeing the shared iterator we
882  * don't free pagetable and iterator array until its refcount becomes 0.
883  */
884  if (ptbase != NULL)
885  pg_atomic_add_fetch_u32(&ptbase->refcount, 1);
886  if (ptpages != NULL)
887  pg_atomic_add_fetch_u32(&ptpages->refcount, 1);
888  if (ptchunks != NULL)
889  pg_atomic_add_fetch_u32(&ptchunks->refcount, 1);
890 
891  /* Initialize the iterator lock */
893 
894  /* Initialize the shared iterator state */
895  istate->schunkbit = 0;
896  istate->schunkptr = 0;
897  istate->spageptr = 0;
898 
900 
901  return dp;
902 }
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:259
static void pg_atomic_init_u32(volatile pg_atomic_uint32 *ptr, uint32 val)
Definition: atomics.h:218
static uint32 pg_atomic_add_fetch_u32(volatile pg_atomic_uint32 *ptr, int32 add_)
Definition: atomics.h:381
#define dsa_allocate0(area, size)
Definition: dsa.h:88
uint64 dsa_pointer
Definition: dsa.h:62
#define dsa_allocate(area, size)
Definition: dsa.h:84
void LWLockInitialize(LWLock *lock, int tranche_id)
Definition: lwlock.c:730
@ LWTRANCHE_SHARED_TIDBITMAP
Definition: lwlock.h:202
void qsort_arg(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
PagetableEntry ptentry[FLEXIBLE_ARRAY_MEMBER]
Definition: tidbitmap.c:114
int index[FLEXIBLE_ARRAY_MEMBER]
Definition: tidbitmap.c:211
static int tbm_shared_comparator(const void *left, const void *right, void *arg)
Definition: tidbitmap.c:1441

References Assert(), TIDBitmap::dsa, dsa_allocate, dsa_allocate0, dsa_get_address(), TIDBitmap::dsapagetable, TIDBitmap::entry1, i, idx(), PTIterationArray::index, PagetableEntry::ischunk, TIDBitmap::iterating, TBMSharedIteratorState::lock, LWLockInitialize(), LWTRANCHE_SHARED_TIDBITMAP, TIDBitmap::maxentries, TBMSharedIteratorState::maxentries, TIDBitmap::nchunks, TBMSharedIteratorState::nchunks, TIDBitmap::nentries, TBMSharedIteratorState::nentries, TIDBitmap::npages, TBMSharedIteratorState::npages, TIDBitmap::pagetable, TBMSharedIteratorState::pagetable, pg_atomic_add_fetch_u32(), pg_atomic_init_u32(), TIDBitmap::ptchunks, PTEntryArray::ptentry, TIDBitmap::ptpages, qsort_arg(), PTEntryArray::refcount, PTIterationArray::refcount, TBMSharedIteratorState::schunkbit, TBMSharedIteratorState::schunkptr, TBMSharedIteratorState::schunks, TBMSharedIteratorState::spageptr, TBMSharedIteratorState::spages, TIDBitmap::status, TBM_HASH, TBM_ITERATING_PRIVATE, TBM_ITERATING_SHARED, TBM_NOT_ITERATING, TBM_ONE_PAGE, and tbm_shared_comparator().

Referenced by BitmapHeapNext().

◆ tbm_shared_comparator()

static int tbm_shared_comparator ( const void *  left,
const void *  right,
void *  arg 
)
static

Definition at line 1441 of file tidbitmap.c.

1442 {
1443  PagetableEntry *base = (PagetableEntry *) arg;
1444  PagetableEntry *lpage = &base[*(int *) left];
1445  PagetableEntry *rpage = &base[*(int *) right];
1446 
1447  if (lpage->blockno < rpage->blockno)
1448  return -1;
1449  else if (lpage->blockno > rpage->blockno)
1450  return 1;
1451  return 0;
1452 }
void * arg

References arg, and PagetableEntry::blockno.

Referenced by tbm_prepare_shared_iterate().

◆ tbm_shared_iterate()

TBMIterateResult* tbm_shared_iterate ( TBMSharedIterator iterator)

Definition at line 1051 of file tidbitmap.c.

1052 {
1053  TBMIterateResult *output = &iterator->output;
1054  TBMSharedIteratorState *istate = iterator->state;
1055  PagetableEntry *ptbase = NULL;
1056  int *idxpages = NULL;
1057  int *idxchunks = NULL;
1058 
1059  if (iterator->ptbase != NULL)
1060  ptbase = iterator->ptbase->ptentry;
1061  if (iterator->ptpages != NULL)
1062  idxpages = iterator->ptpages->index;
1063  if (iterator->ptchunks != NULL)
1064  idxchunks = iterator->ptchunks->index;
1065 
1066  /* Acquire the LWLock before accessing the shared members */
1067  LWLockAcquire(&istate->lock, LW_EXCLUSIVE);
1068 
1069  /*
1070  * If lossy chunk pages remain, make sure we've advanced schunkptr/
1071  * schunkbit to the next set bit.
1072  */
1073  while (istate->schunkptr < istate->nchunks)
1074  {
1075  PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
1076  int schunkbit = istate->schunkbit;
1077 
1078  tbm_advance_schunkbit(chunk, &schunkbit);
1079  if (schunkbit < PAGES_PER_CHUNK)
1080  {
1081  istate->schunkbit = schunkbit;
1082  break;
1083  }
1084  /* advance to next chunk */
1085  istate->schunkptr++;
1086  istate->schunkbit = 0;
1087  }
1088 
1089  /*
1090  * If both chunk and per-page data remain, must output the numerically
1091  * earlier page.
1092  */
1093  if (istate->schunkptr < istate->nchunks)
1094  {
1095  PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
1096  BlockNumber chunk_blockno;
1097 
1098  chunk_blockno = chunk->blockno + istate->schunkbit;
1099 
1100  if (istate->spageptr >= istate->npages ||
1101  chunk_blockno < ptbase[idxpages[istate->spageptr]].blockno)
1102  {
1103  /* Return a lossy page indicator from the chunk */
1104  output->blockno = chunk_blockno;
1105  output->ntuples = -1;
1106  output->recheck = true;
1107  istate->schunkbit++;
1108 
1109  LWLockRelease(&istate->lock);
1110  return output;
1111  }
1112  }
1113 
1114  if (istate->spageptr < istate->npages)
1115  {
1116  PagetableEntry *page = &ptbase[idxpages[istate->spageptr]];
1117  int ntuples;
1118 
1119  /* scan bitmap to extract individual offset numbers */
1120  ntuples = tbm_extract_page_tuple(page, output);
1121  output->blockno = page->blockno;
1122  output->ntuples = ntuples;
1123  output->recheck = page->recheck;
1124  istate->spageptr++;
1125 
1126  LWLockRelease(&istate->lock);
1127 
1128  return output;
1129  }
1130 
1131  LWLockRelease(&istate->lock);
1132 
1133  /* Nothing more in the bitmap */
1134  return NULL;
1135 }
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1195
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1808
@ LW_EXCLUSIVE
Definition: lwlock.h:116
TBMIterateResult output
Definition: tidbitmap.c:224

References PagetableEntry::blockno, PTIterationArray::index, TBMSharedIteratorState::lock, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), TBMSharedIteratorState::nchunks, TBMSharedIteratorState::npages, TBMSharedIterator::output, output, PAGES_PER_CHUNK, TBMSharedIterator::ptbase, TBMSharedIterator::ptchunks, PTEntryArray::ptentry, TBMSharedIterator::ptpages, PagetableEntry::recheck, TBMSharedIteratorState::schunkbit, TBMSharedIteratorState::schunkptr, TBMSharedIteratorState::spageptr, TBMSharedIterator::state, tbm_advance_schunkbit(), and tbm_extract_page_tuple().

Referenced by BitmapAdjustPrefetchIterator(), BitmapHeapNext(), and BitmapPrefetch().

◆ tbm_union()

void tbm_union ( TIDBitmap a,
const TIDBitmap b 
)

Definition at line 457 of file tidbitmap.c.

458 {
459  Assert(!a->iterating);
460  /* Nothing to do if b is empty */
461  if (b->nentries == 0)
462  return;
463  /* Scan through chunks and pages in b, merge into a */
464  if (b->status == TBM_ONE_PAGE)
465  tbm_union_page(a, &b->entry1);
466  else
467  {
468  pagetable_iterator i;
469  PagetableEntry *bpage;
470 
471  Assert(b->status == TBM_HASH);
472  pagetable_start_iterate(b->pagetable, &i);
473  while ((bpage = pagetable_iterate(b->pagetable, &i)) != NULL)
474  tbm_union_page(a, bpage);
475  }
476 }
static void tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage)
Definition: tidbitmap.c:480

References a, Assert(), b, i, TBM_HASH, TBM_ONE_PAGE, and tbm_union_page().

Referenced by MultiExecBitmapOr().

◆ tbm_union_page()

static void tbm_union_page ( TIDBitmap a,
const PagetableEntry bpage 
)
static

Definition at line 480 of file tidbitmap.c.

481 {
482  PagetableEntry *apage;
483  int wordnum;
484 
485  if (bpage->ischunk)
486  {
487  /* Scan b's chunk, mark each indicated page lossy in a */
488  for (wordnum = 0; wordnum < WORDS_PER_CHUNK; wordnum++)
489  {
490  bitmapword w = bpage->words[wordnum];
491 
492  if (w != 0)
493  {
494  BlockNumber pg;
495 
496  pg = bpage->blockno + (wordnum * BITS_PER_BITMAPWORD);
497  while (w != 0)
498  {
499  if (w & 1)
500  tbm_mark_page_lossy(a, pg);
501  pg++;
502  w >>= 1;
503  }
504  }
505  }
506  }
507  else if (tbm_page_is_lossy(a, bpage->blockno))
508  {
509  /* page is already lossy in a, nothing to do */
510  return;
511  }
512  else
513  {
514  apage = tbm_get_pageentry(a, bpage->blockno);
515  if (apage->ischunk)
516  {
517  /* The page is a lossy chunk header, set bit for itself */
518  apage->words[0] |= ((bitmapword) 1 << 0);
519  }
520  else
521  {
522  /* Both pages are exact, merge at the bit level */
523  for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
524  apage->words[wordnum] |= bpage->words[wordnum];
525  apage->recheck |= bpage->recheck;
526  }
527  }
528 
529  if (a->nentries > a->maxentries)
530  tbm_lossify(a);
531 }

References a, BITS_PER_BITMAPWORD, PagetableEntry::blockno, PagetableEntry::ischunk, PagetableEntry::recheck, tbm_get_pageentry(), tbm_lossify(), tbm_mark_page_lossy(), tbm_page_is_lossy(), PagetableEntry::words, WORDS_PER_CHUNK, and WORDS_PER_PAGE.

Referenced by tbm_union().