PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
tidbitmap.h File Reference
#include "storage/itemptr.h"
Include dependency graph for tidbitmap.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  TBMIterateResult
 

Typedefs

typedef struct TIDBitmap TIDBitmap
 
typedef struct TBMIterator TBMIterator
 

Functions

TIDBitmaptbm_create (long maxbytes)
 
void tbm_free (TIDBitmap *tbm)
 
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)
 
TBMIterateResulttbm_iterate (TBMIterator *iterator)
 
void tbm_end_iterate (TBMIterator *iterator)
 

Typedef Documentation

Definition at line 35 of file tidbitmap.h.

Definition at line 32 of file tidbitmap.h.

Function Documentation

void tbm_add_page ( TIDBitmap tbm,
BlockNumber  pageno 
)

Definition at line 356 of file tidbitmap.c.

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

Referenced by bringetbitmap(), and gingetbitmap().

357 {
358  /* Enter the page in the bitmap, or mark it lossy if already present */
359  tbm_mark_page_lossy(tbm, pageno);
360  /* If we went over the memory limit, lossify some more pages */
361  if (tbm->nentries > tbm->maxentries)
362  tbm_lossify(tbm);
363 }
int maxentries
Definition: tidbitmap.c:133
static void tbm_lossify(TIDBitmap *tbm)
Definition: tidbitmap.c:984
static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:912
int nentries
Definition: tidbitmap.c:132
void tbm_add_tuples ( TIDBitmap tbm,
const ItemPointer  tids,
int  ntids,
bool  recheck 
)

Definition at line 290 of file tidbitmap.c.

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

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

292 {
294  PagetableEntry *page = NULL; /* only valid when currblk is valid */
295  int i;
296 
297  Assert(!tbm->iterating);
298  for (i = 0; i < ntids; i++)
299  {
300  BlockNumber blk = ItemPointerGetBlockNumber(tids + i);
302  int wordnum,
303  bitnum;
304 
305  /* safety check to ensure we don't overrun bit array bounds */
306  if (off < 1 || off > MAX_TUPLES_PER_PAGE)
307  elog(ERROR, "tuple offset out of range: %u", off);
308 
309  /*
310  * Look up target page unless we already did. This saves cycles when
311  * the input includes consecutive tuples on the same page, which is
312  * common enough to justify an extra test here.
313  */
314  if (blk != currblk)
315  {
316  if (tbm_page_is_lossy(tbm, blk))
317  page = NULL; /* remember page is lossy */
318  else
319  page = tbm_get_pageentry(tbm, blk);
320  currblk = blk;
321  }
322 
323  if (page == NULL)
324  continue; /* whole page is already marked */
325 
326  if (page->ischunk)
327  {
328  /* The page is a lossy chunk header, set bit for itself */
329  wordnum = bitnum = 0;
330  }
331  else
332  {
333  /* Page is exact, so set bit for individual tuple */
334  wordnum = WORDNUM(off - 1);
335  bitnum = BITNUM(off - 1);
336  }
337  page->words[wordnum] |= ((bitmapword) 1 << bitnum);
338  page->recheck |= recheck;
339 
340  if (tbm->nentries > tbm->maxentries)
341  {
342  tbm_lossify(tbm);
343  /* Page could have been converted to lossy, so force new lookup */
344  currblk = InvalidBlockNumber;
345  }
346  }
347 }
#define BITNUM(x)
Definition: tidbitmap.c:75
uint32 BlockNumber
Definition: block.h:31
uint32 bitmapword
Definition: bitmapset.h:29
uint16 OffsetNumber
Definition: off.h:24
#define ERROR
Definition: elog.h:43
int maxentries
Definition: tidbitmap.c:133
#define WORDNUM(x)
Definition: tidbitmap.c:74
bool iterating
Definition: tidbitmap.c:136
bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]
Definition: tidbitmap.c:102
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
#define InvalidBlockNumber
Definition: block.h:33
#define MAX_TUPLES_PER_PAGE
Definition: tidbitmap.c:53
#define ItemPointerGetOffsetNumber(pointer)
Definition: itemptr.h:76
static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:878
int i
static void tbm_lossify(TIDBitmap *tbm)
Definition: tidbitmap.c:984
static PagetableEntry * tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno)
Definition: tidbitmap.c:831
#define elog
Definition: elog.h:219
#define ItemPointerGetBlockNumber(pointer)
Definition: itemptr.h:66
int nentries
Definition: tidbitmap.c:132
TBMIterator* tbm_begin_iterate ( TIDBitmap tbm)

Definition at line 602 of file tidbitmap.c.

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

Referenced by BitmapHeapNext(), and startScanEntry().

603 {
604  TBMIterator *iterator;
605 
606  /*
607  * Create the TBMIterator struct, with enough trailing space to serve the
608  * needs of the TBMIterateResult sub-struct.
609  */
610  iterator = (TBMIterator *) palloc(sizeof(TBMIterator) +
612  iterator->tbm = tbm;
613 
614  /*
615  * Initialize iteration pointers.
616  */
617  iterator->spageptr = 0;
618  iterator->schunkptr = 0;
619  iterator->schunkbit = 0;
620 
621  /*
622  * If we have a hashtable, create and fill the sorted page lists, unless
623  * we already did that for a previous iterator. Note that the lists are
624  * attached to the bitmap not the iterator, so they can be used by more
625  * than one iterator.
626  */
627  if (tbm->status == TBM_HASH && !tbm->iterating)
628  {
629  pagetable_iterator i;
630  PagetableEntry *page;
631  int npages;
632  int nchunks;
633 
634  if (!tbm->spages && tbm->npages > 0)
635  tbm->spages = (PagetableEntry **)
637  tbm->npages * sizeof(PagetableEntry *));
638  if (!tbm->schunks && tbm->nchunks > 0)
639  tbm->schunks = (PagetableEntry **)
641  tbm->nchunks * sizeof(PagetableEntry *));
642 
643  npages = nchunks = 0;
644  pagetable_start_iterate(tbm->pagetable, &i);
645  while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
646  {
647  if (page->ischunk)
648  tbm->schunks[nchunks++] = page;
649  else
650  tbm->spages[npages++] = page;
651  }
652  Assert(npages == tbm->npages);
653  Assert(nchunks == tbm->nchunks);
654  if (npages > 1)
655  qsort(tbm->spages, npages, sizeof(PagetableEntry *),
657  if (nchunks > 1)
658  qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
660  }
661 
662  tbm->iterating = true;
663 
664  return iterator;
665 }
static int tbm_comparator(const void *left, const void *right)
Definition: tidbitmap.c:1053
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
uint16 OffsetNumber
Definition: off.h:24
MemoryContext mcxt
Definition: tidbitmap.c:129
int schunkptr
Definition: tidbitmap.c:154
int spageptr
Definition: tidbitmap.c:153
TIDBitmap * tbm
Definition: tidbitmap.c:152
int nchunks
Definition: tidbitmap.c:135
PagetableEntry ** spages
Definition: tidbitmap.c:140
bool iterating
Definition: tidbitmap.c:136
int npages
Definition: tidbitmap.c:134
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
PagetableEntry ** schunks
Definition: tidbitmap.c:141
TBMStatus status
Definition: tidbitmap.c:130
#define MAX_TUPLES_PER_PAGE
Definition: tidbitmap.c:53
void * palloc(Size size)
Definition: mcxt.c:891
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:749
int i
int schunkbit
Definition: tidbitmap.c:155
#define qsort(a, b, c, d)
Definition: port.h:440
TIDBitmap* tbm_create ( long  maxbytes)

Definition at line 210 of file tidbitmap.c.

References CurrentMemoryContext, TIDBitmap::lossify_start, makeNode, Max, TIDBitmap::maxentries, TIDBitmap::mcxt, Min, TIDBitmap::status, and TBM_EMPTY.

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

211 {
212  TIDBitmap *tbm;
213  long nbuckets;
214 
215  /* Create the TIDBitmap struct and zero all its fields */
216  tbm = makeNode(TIDBitmap);
217 
218  tbm->mcxt = CurrentMemoryContext;
219  tbm->status = TBM_EMPTY;
220 
221  /*
222  * Estimate number of hashtable entries we can have within maxbytes. This
223  * estimates the hash cost as sizeof(PagetableEntry), which is good enough
224  * for our purpose. Also count an extra Pointer per entry for the arrays
225  * created during iteration readout.
226  */
227  nbuckets = maxbytes /
228  (sizeof(PagetableEntry) + sizeof(Pointer) + sizeof(Pointer));
229  nbuckets = Min(nbuckets, INT_MAX - 1); /* safety limit */
230  nbuckets = Max(nbuckets, 16); /* sanity limit */
231  tbm->maxentries = (int) nbuckets;
232  tbm->lossify_start = 0;
233 
234  return tbm;
235 }
#define Min(x, y)
Definition: c.h:802
uint32 lossify_start
Definition: tidbitmap.c:137
MemoryContext mcxt
Definition: tidbitmap.c:129
char * Pointer
Definition: c.h:242
int maxentries
Definition: tidbitmap.c:133
MemoryContext CurrentMemoryContext
Definition: mcxt.c:37
#define Max(x, y)
Definition: c.h:796
#define makeNode(_type_)
Definition: nodes.h:557
TBMStatus status
Definition: tidbitmap.c:130
struct PagetableEntry PagetableEntry
void tbm_end_iterate ( TBMIterator iterator)

Definition at line 787 of file tidbitmap.c.

References pfree().

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

788 {
789  pfree(iterator);
790 }
void pfree(void *pointer)
Definition: mcxt.c:992
void tbm_free ( TIDBitmap tbm)

Definition at line 272 of file tidbitmap.c.

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

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

273 {
274  if (tbm->pagetable)
275  pagetable_destroy(tbm->pagetable);
276  if (tbm->spages)
277  pfree(tbm->spages);
278  if (tbm->schunks)
279  pfree(tbm->schunks);
280  pfree(tbm);
281 }
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
void pfree(void *pointer)
Definition: mcxt.c:992
PagetableEntry ** spages
Definition: tidbitmap.c:140
PagetableEntry ** schunks
Definition: tidbitmap.c:141
void tbm_intersect ( TIDBitmap a,
const TIDBitmap b 
)

Definition at line 453 of file tidbitmap.c.

References Assert, PagetableEntry::blockno, elog, TIDBitmap::entry1, ERROR, i, PagetableEntry::ischunk, TIDBitmap::iterating, TIDBitmap::nchunks, TIDBitmap::nentries, TIDBitmap::npages, NULL, TIDBitmap::pagetable, TIDBitmap::status, TBM_EMPTY, TBM_HASH, tbm_intersect_page(), and TBM_ONE_PAGE.

Referenced by MultiExecBitmapAnd().

454 {
455  Assert(!a->iterating);
456  /* Nothing to do if a is empty */
457  if (a->nentries == 0)
458  return;
459  /* Scan through chunks and pages in a, try to match to b */
460  if (a->status == TBM_ONE_PAGE)
461  {
462  if (tbm_intersect_page(a, &a->entry1, b))
463  {
464  /* Page is now empty, remove it from a */
465  Assert(!a->entry1.ischunk);
466  a->npages--;
467  a->nentries--;
468  Assert(a->nentries == 0);
469  a->status = TBM_EMPTY;
470  }
471  }
472  else
473  {
474  pagetable_iterator i;
475  PagetableEntry *apage;
476 
477  Assert(a->status == TBM_HASH);
478  pagetable_start_iterate(a->pagetable, &i);
479  while ((apage = pagetable_iterate(a->pagetable, &i)) != NULL)
480  {
481  if (tbm_intersect_page(a, apage, b))
482  {
483  /* Page or chunk is now empty, remove it from a */
484  if (apage->ischunk)
485  a->nchunks--;
486  else
487  a->npages--;
488  a->nentries--;
489  if (!pagetable_delete(a->pagetable, apage->blockno))
490  elog(ERROR, "hash table corrupted");
491  }
492  }
493  }
494 }
static bool tbm_intersect_page(TIDBitmap *a, PagetableEntry *apage, const TIDBitmap *b)
Definition: tidbitmap.c:502
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
PagetableEntry entry1
Definition: tidbitmap.c:138
#define ERROR
Definition: elog.h:43
BlockNumber blockno
Definition: tidbitmap.c:98
int nchunks
Definition: tidbitmap.c:135
bool iterating
Definition: tidbitmap.c:136
int npages
Definition: tidbitmap.c:134
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
TBMStatus status
Definition: tidbitmap.c:130
int i
#define elog
Definition: elog.h:219
int nentries
Definition: tidbitmap.c:132
bool tbm_is_empty ( const TIDBitmap tbm)

Definition at line 583 of file tidbitmap.c.

References TIDBitmap::nentries.

Referenced by MultiExecBitmapAnd(), and startScanEntry().

584 {
585  return (tbm->nentries == 0);
586 }
int nentries
Definition: tidbitmap.c:132
TBMIterateResult* tbm_iterate ( TBMIterator iterator)

Definition at line 680 of file tidbitmap.c.

References Assert, BITNUM, BITS_PER_BITMAPWORD, TBMIterateResult::blockno, PagetableEntry::blockno, TIDBitmap::entry1, TIDBitmap::iterating, TIDBitmap::nchunks, TIDBitmap::npages, TBMIterateResult::ntuples, NULL, TBMIterateResult::offsets, output(), TBMIterator::output, PAGES_PER_CHUNK, TBMIterateResult::recheck, PagetableEntry::recheck, TBMIterator::schunkbit, TBMIterator::schunkptr, TIDBitmap::schunks, TBMIterator::spageptr, TIDBitmap::spages, TIDBitmap::status, TBMIterator::tbm, TBM_ONE_PAGE, WORDNUM, PagetableEntry::words, and WORDS_PER_PAGE.

Referenced by BitmapHeapNext(), and entryGetItem().

681 {
682  TIDBitmap *tbm = iterator->tbm;
683  TBMIterateResult *output = &(iterator->output);
684 
685  Assert(tbm->iterating);
686 
687  /*
688  * If lossy chunk pages remain, make sure we've advanced schunkptr/
689  * schunkbit to the next set bit.
690  */
691  while (iterator->schunkptr < tbm->nchunks)
692  {
693  PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
694  int schunkbit = iterator->schunkbit;
695 
696  while (schunkbit < PAGES_PER_CHUNK)
697  {
698  int wordnum = WORDNUM(schunkbit);
699  int bitnum = BITNUM(schunkbit);
700 
701  if ((chunk->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
702  break;
703  schunkbit++;
704  }
705  if (schunkbit < PAGES_PER_CHUNK)
706  {
707  iterator->schunkbit = schunkbit;
708  break;
709  }
710  /* advance to next chunk */
711  iterator->schunkptr++;
712  iterator->schunkbit = 0;
713  }
714 
715  /*
716  * If both chunk and per-page data remain, must output the numerically
717  * earlier page.
718  */
719  if (iterator->schunkptr < tbm->nchunks)
720  {
721  PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
722  BlockNumber chunk_blockno;
723 
724  chunk_blockno = chunk->blockno + iterator->schunkbit;
725  if (iterator->spageptr >= tbm->npages ||
726  chunk_blockno < tbm->spages[iterator->spageptr]->blockno)
727  {
728  /* Return a lossy page indicator from the chunk */
729  output->blockno = chunk_blockno;
730  output->ntuples = -1;
731  output->recheck = true;
732  iterator->schunkbit++;
733  return output;
734  }
735  }
736 
737  if (iterator->spageptr < tbm->npages)
738  {
739  PagetableEntry *page;
740  int ntuples;
741  int wordnum;
742 
743  /* In ONE_PAGE state, we don't allocate an spages[] array */
744  if (tbm->status == TBM_ONE_PAGE)
745  page = &tbm->entry1;
746  else
747  page = tbm->spages[iterator->spageptr];
748 
749  /* scan bitmap to extract individual offset numbers */
750  ntuples = 0;
751  for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
752  {
753  bitmapword w = page->words[wordnum];
754 
755  if (w != 0)
756  {
757  int off = wordnum * BITS_PER_BITMAPWORD + 1;
758 
759  while (w != 0)
760  {
761  if (w & 1)
762  output->offsets[ntuples++] = (OffsetNumber) off;
763  off++;
764  w >>= 1;
765  }
766  }
767  }
768  output->blockno = page->blockno;
769  output->ntuples = ntuples;
770  output->recheck = page->recheck;
771  iterator->spageptr++;
772  return output;
773  }
774 
775  /* Nothing more in the bitmap */
776  return NULL;
777 }
static void output(uint64 loop_count)
#define BITNUM(x)
Definition: tidbitmap.c:75
uint32 BlockNumber
Definition: block.h:31
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:28
uint32 bitmapword
Definition: bitmapset.h:29
#define WORDS_PER_PAGE
Definition: tidbitmap.c:78
uint16 OffsetNumber
Definition: off.h:24
PagetableEntry entry1
Definition: tidbitmap.c:138
BlockNumber blockno
Definition: tidbitmap.h:40
int schunkptr
Definition: tidbitmap.c:154
BlockNumber blockno
Definition: tidbitmap.c:98
int spageptr
Definition: tidbitmap.c:153
OffsetNumber offsets[FLEXIBLE_ARRAY_MEMBER]
Definition: tidbitmap.h:44
#define WORDNUM(x)
Definition: tidbitmap.c:74
TIDBitmap * tbm
Definition: tidbitmap.c:152
int nchunks
Definition: tidbitmap.c:135
PagetableEntry ** spages
Definition: tidbitmap.c:140
bool iterating
Definition: tidbitmap.c:136
#define PAGES_PER_CHUNK
Definition: tidbitmap.c:70
bitmapword words[Max(WORDS_PER_PAGE, WORDS_PER_CHUNK)]
Definition: tidbitmap.c:102
int npages
Definition: tidbitmap.c:134
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
PagetableEntry ** schunks
Definition: tidbitmap.c:141
TBMIterateResult output
Definition: tidbitmap.c:156
TBMStatus status
Definition: tidbitmap.c:130
int schunkbit
Definition: tidbitmap.c:155
void tbm_union ( TIDBitmap a,
const TIDBitmap b 
)

Definition at line 371 of file tidbitmap.c.

References Assert, TIDBitmap::entry1, i, TIDBitmap::iterating, TIDBitmap::nentries, NULL, TIDBitmap::pagetable, TIDBitmap::status, TBM_HASH, TBM_ONE_PAGE, and tbm_union_page().

Referenced by MultiExecBitmapOr().

372 {
373  Assert(!a->iterating);
374  /* Nothing to do if b is empty */
375  if (b->nentries == 0)
376  return;
377  /* Scan through chunks and pages in b, merge into a */
378  if (b->status == TBM_ONE_PAGE)
379  tbm_union_page(a, &b->entry1);
380  else
381  {
382  pagetable_iterator i;
383  PagetableEntry *bpage;
384 
385  Assert(b->status == TBM_HASH);
386  pagetable_start_iterate(b->pagetable, &i);
387  while ((bpage = pagetable_iterate(b->pagetable, &i)) != NULL)
388  tbm_union_page(a, bpage);
389  }
390 }
struct pagetable_hash * pagetable
Definition: tidbitmap.c:131
static void tbm_union_page(TIDBitmap *a, const PagetableEntry *bpage)
Definition: tidbitmap.c:394
PagetableEntry entry1
Definition: tidbitmap.c:138
bool iterating
Definition: tidbitmap.c:136
#define NULL
Definition: c.h:226
#define Assert(condition)
Definition: c.h:671
TBMStatus status
Definition: tidbitmap.c:130
int i
int nentries
Definition: tidbitmap.c:132