Header And Logo
|
#include "postgres.h"#include <limits.h>#include "access/htup_details.h"#include "nodes/bitmapset.h"#include "nodes/tidbitmap.h"#include "utils/hsearch.h"
Go to the source code of this file.
Data Structures | |
| struct | PagetableEntry |
| struct | TIDBitmap |
| struct | TBMIterator |
Defines | |
| #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) |
Typedefs | |
| typedef struct PagetableEntry | PagetableEntry |
Enumerations | |
| enum | TBMStatus { TBM_EMPTY, TBM_ONE_PAGE, TBM_HASH } |
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 PagetableEntry * | tbm_find_pageentry (const TIDBitmap *tbm, BlockNumber pageno) |
| static PagetableEntry * | tbm_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) |
| TIDBitmap * | tbm_create (long maxbytes) |
| static void | tbm_create_pagetable (TIDBitmap *tbm) |
| 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) |
| TBMIterator * | tbm_begin_iterate (TIDBitmap *tbm) |
| TBMIterateResult * | tbm_iterate (TBMIterator *iterator) |
| void | tbm_end_iterate (TBMIterator *iterator) |
| #define BITNUM | ( | x | ) | ((x) % BITS_PER_BITMAPWORD) |
Definition at line 76 of file tidbitmap.c.
Referenced by tbm_add_tuples(), tbm_iterate(), tbm_mark_page_lossy(), and tbm_page_is_lossy().
| #define MAX_TUPLES_PER_PAGE MaxHeapTuplesPerPage |
Definition at line 54 of file tidbitmap.c.
Referenced by tbm_add_tuples(), and tbm_begin_iterate().
| #define PAGES_PER_CHUNK (BLCKSZ / 32) |
Definition at line 71 of file tidbitmap.c.
Referenced by tbm_iterate(), and tbm_lossify().
| #define WORDNUM | ( | x | ) | ((x) / BITS_PER_BITMAPWORD) |
Definition at line 75 of file tidbitmap.c.
Referenced by tbm_add_tuples(), tbm_iterate(), tbm_mark_page_lossy(), and tbm_page_is_lossy().
| #define WORDS_PER_CHUNK ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1) |
Definition at line 81 of file tidbitmap.c.
| #define WORDS_PER_PAGE ((MAX_TUPLES_PER_PAGE - 1) / BITS_PER_BITMAPWORD + 1) |
Definition at line 79 of file tidbitmap.c.
| typedef struct PagetableEntry PagetableEntry |
| enum TBMStatus |
Definition at line 116 of file tidbitmap.c.
{
TBM_EMPTY, /* no hashtable, nentries == 0 */
TBM_ONE_PAGE, /* entry1 contains the single entry */
TBM_HASH /* pagetable is valid, entry1 is not */
} TBMStatus;
| void tbm_add_page | ( | TIDBitmap * | tbm, | |
| BlockNumber | pageno | |||
| ) |
Definition at line 318 of file tidbitmap.c.
References TIDBitmap::maxentries, TIDBitmap::nentries, tbm_lossify(), and tbm_mark_page_lossy().
Referenced by gingetbitmap().
{
/* Enter the page in the bitmap, or mark it lossy if already present */
tbm_mark_page_lossy(tbm, pageno);
/* If we went over the memory limit, lossify some more pages */
if (tbm->nentries > tbm->maxentries)
tbm_lossify(tbm);
}
| void tbm_add_tuples | ( | TIDBitmap * | tbm, | |
| const ItemPointer | tids, | |||
| int | ntids, | |||
| bool | recheck | |||
| ) |
Definition at line 269 of file tidbitmap.c.
References Assert, BITNUM, elog, ERROR, i, PagetableEntry::ischunk, ItemPointerGetBlockNumber, ItemPointerGetOffsetNumber, TIDBitmap::iterating, MAX_TUPLES_PER_PAGE, TIDBitmap::maxentries, TIDBitmap::nentries, PagetableEntry::recheck, tbm_get_pageentry(), tbm_lossify(), tbm_page_is_lossy(), WORDNUM, and PagetableEntry::words.
Referenced by btgetbitmap(), collectMatchBitmap(), gingetbitmap(), gistScanPage(), hashgetbitmap(), scanPendingInsert(), scanPostingTree(), and storeBitmap().
{
int i;
Assert(!tbm->iterating);
for (i = 0; i < ntids; i++)
{
BlockNumber blk = ItemPointerGetBlockNumber(tids + i);
OffsetNumber off = ItemPointerGetOffsetNumber(tids + i);
PagetableEntry *page;
int wordnum,
bitnum;
/* safety check to ensure we don't overrun bit array bounds */
if (off < 1 || off > MAX_TUPLES_PER_PAGE)
elog(ERROR, "tuple offset out of range: %u", off);
if (tbm_page_is_lossy(tbm, blk))
continue; /* whole page is already marked */
page = tbm_get_pageentry(tbm, blk);
if (page->ischunk)
{
/* The page is a lossy chunk header, set bit for itself */
wordnum = bitnum = 0;
}
else
{
/* Page is exact, so set bit for individual tuple */
wordnum = WORDNUM(off - 1);
bitnum = BITNUM(off - 1);
}
page->words[wordnum] |= ((bitmapword) 1 << bitnum);
page->recheck |= recheck;
if (tbm->nentries > tbm->maxentries)
tbm_lossify(tbm);
}
}
| TBMIterator* tbm_begin_iterate | ( | TIDBitmap * | tbm | ) |
Definition at line 566 of file tidbitmap.c.
References Assert, hash_seq_init(), hash_seq_search(), 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().
{
TBMIterator *iterator;
/*
* Create the TBMIterator struct, with enough trailing space to serve the
* needs of the TBMIterateResult sub-struct.
*/
iterator = (TBMIterator *) palloc(sizeof(TBMIterator) +
MAX_TUPLES_PER_PAGE * sizeof(OffsetNumber));
iterator->tbm = tbm;
/*
* Initialize iteration pointers.
*/
iterator->spageptr = 0;
iterator->schunkptr = 0;
iterator->schunkbit = 0;
/*
* If we have a hashtable, create and fill the sorted page lists, unless
* we already did that for a previous iterator. Note that the lists are
* attached to the bitmap not the iterator, so they can be used by more
* than one iterator.
*/
if (tbm->status == TBM_HASH && !tbm->iterating)
{
HASH_SEQ_STATUS status;
PagetableEntry *page;
int npages;
int nchunks;
if (!tbm->spages && tbm->npages > 0)
tbm->spages = (PagetableEntry **)
MemoryContextAlloc(tbm->mcxt,
tbm->npages * sizeof(PagetableEntry *));
if (!tbm->schunks && tbm->nchunks > 0)
tbm->schunks = (PagetableEntry **)
MemoryContextAlloc(tbm->mcxt,
tbm->nchunks * sizeof(PagetableEntry *));
hash_seq_init(&status, tbm->pagetable);
npages = nchunks = 0;
while ((page = (PagetableEntry *) hash_seq_search(&status)) != NULL)
{
if (page->ischunk)
tbm->schunks[nchunks++] = page;
else
tbm->spages[npages++] = page;
}
Assert(npages == tbm->npages);
Assert(nchunks == tbm->nchunks);
if (npages > 1)
qsort(tbm->spages, npages, sizeof(PagetableEntry *),
tbm_comparator);
if (nchunks > 1)
qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
tbm_comparator);
}
tbm->iterating = true;
return iterator;
}
| static int tbm_comparator | ( | const void * | left, | |
| const void * | right | |||
| ) | [static] |
Definition at line 1012 of file tidbitmap.c.
Referenced by tbm_begin_iterate().
{
BlockNumber l = (*((PagetableEntry *const *) left))->blockno;
BlockNumber r = (*((PagetableEntry *const *) right))->blockno;
if (l < r)
return -1;
else if (l > r)
return 1;
return 0;
}
| TIDBitmap* tbm_create | ( | long | maxbytes | ) |
Definition at line 180 of file tidbitmap.c.
References CurrentMemoryContext, makeNode, Max, MAXALIGN, TIDBitmap::maxentries, TIDBitmap::mcxt, Min, and TIDBitmap::status.
Referenced by collectMatchBitmap(), MultiExecBitmapIndexScan(), and MultiExecBitmapOr().
{
TIDBitmap *tbm;
long nbuckets;
/* Create the TIDBitmap struct and zero all its fields */
tbm = makeNode(TIDBitmap);
tbm->mcxt = CurrentMemoryContext;
tbm->status = TBM_EMPTY;
/*
* Estimate number of hashtable entries we can have within maxbytes. This
* estimates the hash overhead at MAXALIGN(sizeof(HASHELEMENT)) plus a
* pointer per hash entry, which is crude but good enough for our purpose.
* Also count an extra Pointer per entry for the arrays created during
* iteration readout.
*/
nbuckets = maxbytes /
(MAXALIGN(sizeof(HASHELEMENT)) + MAXALIGN(sizeof(PagetableEntry))
+ sizeof(Pointer) + sizeof(Pointer));
nbuckets = Min(nbuckets, INT_MAX - 1); /* safety limit */
nbuckets = Max(nbuckets, 16); /* sanity limit */
tbm->maxentries = (int) nbuckets;
return tbm;
}
| static void tbm_create_pagetable | ( | TIDBitmap * | tbm | ) | [static] |
Definition at line 213 of file tidbitmap.c.
References Assert, PagetableEntry::blockno, TIDBitmap::entry1, HASHCTL::entrysize, HASHCTL::hash, HASH_CONTEXT, hash_create(), HASH_ELEM, HASH_FUNCTION, hash_search(), HASHCTL::hcxt, HASHCTL::keysize, TIDBitmap::mcxt, MemSet, NULL, TIDBitmap::pagetable, TIDBitmap::status, TBM_HASH, and TBM_ONE_PAGE.
Referenced by tbm_get_pageentry(), and tbm_mark_page_lossy().
{
HASHCTL hash_ctl;
Assert(tbm->status != TBM_HASH);
Assert(tbm->pagetable == NULL);
/* Create the hashtable proper */
MemSet(&hash_ctl, 0, sizeof(hash_ctl));
hash_ctl.keysize = sizeof(BlockNumber);
hash_ctl.entrysize = sizeof(PagetableEntry);
hash_ctl.hash = tag_hash;
hash_ctl.hcxt = tbm->mcxt;
tbm->pagetable = hash_create("TIDBitmap",
128, /* start small and extend */
&hash_ctl,
HASH_ELEM | HASH_FUNCTION | HASH_CONTEXT);
/* If entry1 is valid, push it into the hashtable */
if (tbm->status == TBM_ONE_PAGE)
{
PagetableEntry *page;
bool found;
page = (PagetableEntry *) hash_search(tbm->pagetable,
(void *) &tbm->entry1.blockno,
HASH_ENTER, &found);
Assert(!found);
memcpy(page, &tbm->entry1, sizeof(PagetableEntry));
}
tbm->status = TBM_HASH;
}
| void tbm_end_iterate | ( | TBMIterator * | iterator | ) |
Definition at line 751 of file tidbitmap.c.
References pfree().
Referenced by BitmapHeapNext(), entryGetItem(), ExecEndBitmapHeapScan(), ExecReScanBitmapHeapScan(), freeScanKeys(), and startScanEntry().
{
pfree(iterator);
}
| static const PagetableEntry * tbm_find_pageentry | ( | const TIDBitmap * | tbm, | |
| BlockNumber | pageno | |||
| ) | [static] |
Definition at line 762 of file tidbitmap.c.
References Assert, PagetableEntry::blockno, TIDBitmap::entry1, hash_search(), PagetableEntry::ischunk, TIDBitmap::nentries, NULL, TIDBitmap::pagetable, TIDBitmap::status, and TBM_ONE_PAGE.
Referenced by tbm_intersect_page().
{
const PagetableEntry *page;
if (tbm->nentries == 0) /* in case pagetable doesn't exist */
return NULL;
if (tbm->status == TBM_ONE_PAGE)
{
page = &tbm->entry1;
if (page->blockno != pageno)
return NULL;
Assert(!page->ischunk);
return page;
}
page = (PagetableEntry *) hash_search(tbm->pagetable,
(void *) &pageno,
HASH_FIND, NULL);
if (page == NULL)
return NULL;
if (page->ischunk)
return NULL; /* don't want a lossy chunk header */
return page;
}
| void tbm_free | ( | TIDBitmap * | tbm | ) |
Definition at line 251 of file tidbitmap.c.
References hash_destroy(), TIDBitmap::pagetable, pfree(), TIDBitmap::schunks, and TIDBitmap::spages.
Referenced by ExecEndBitmapHeapScan(), ExecReScanBitmapHeapScan(), freeScanKeys(), MultiExecBitmapAnd(), MultiExecBitmapOr(), and startScanEntry().
| static PagetableEntry * tbm_get_pageentry | ( | TIDBitmap * | tbm, | |
| BlockNumber | pageno | |||
| ) | [static] |
Definition at line 797 of file tidbitmap.c.
References PagetableEntry::blockno, TIDBitmap::entry1, hash_search(), MemSet, TIDBitmap::nentries, TIDBitmap::npages, TIDBitmap::pagetable, TIDBitmap::status, tbm_create_pagetable(), TBM_EMPTY, and TBM_ONE_PAGE.
Referenced by tbm_add_tuples(), and tbm_union_page().
{
PagetableEntry *page;
bool found;
if (tbm->status == TBM_EMPTY)
{
/* Use the fixed slot */
page = &tbm->entry1;
found = false;
tbm->status = TBM_ONE_PAGE;
}
else
{
if (tbm->status == TBM_ONE_PAGE)
{
page = &tbm->entry1;
if (page->blockno == pageno)
return page;
/* Time to switch from one page to a hashtable */
tbm_create_pagetable(tbm);
}
/* Look up or create an entry */
page = (PagetableEntry *) hash_search(tbm->pagetable,
(void *) &pageno,
HASH_ENTER, &found);
}
/* Initialize it if not present before */
if (!found)
{
MemSet(page, 0, sizeof(PagetableEntry));
page->blockno = pageno;
/* must count it too */
tbm->nentries++;
tbm->npages++;
}
return page;
}
Definition at line 415 of file tidbitmap.c.
References Assert, PagetableEntry::blockno, elog, TIDBitmap::entry1, ERROR, HASH_REMOVE, hash_search(), hash_seq_init(), hash_seq_search(), PagetableEntry::ischunk, TIDBitmap::iterating, TIDBitmap::nchunks, TIDBitmap::nentries, TIDBitmap::npages, NULL, TIDBitmap::pagetable, TIDBitmap::status, TBM_HASH, tbm_intersect_page(), and TBM_ONE_PAGE.
Referenced by MultiExecBitmapAnd().
{
Assert(!a->iterating);
/* Nothing to do if a is empty */
if (a->nentries == 0)
return;
/* Scan through chunks and pages in a, try to match to b */
if (a->status == TBM_ONE_PAGE)
{
if (tbm_intersect_page(a, &a->entry1, b))
{
/* Page is now empty, remove it from a */
Assert(!a->entry1.ischunk);
a->npages--;
a->nentries--;
Assert(a->nentries == 0);
a->status = TBM_EMPTY;
}
}
else
{
HASH_SEQ_STATUS status;
PagetableEntry *apage;
Assert(a->status == TBM_HASH);
hash_seq_init(&status, a->pagetable);
while ((apage = (PagetableEntry *) hash_seq_search(&status)) != NULL)
{
if (tbm_intersect_page(a, apage, b))
{
/* Page or chunk is now empty, remove it from a */
if (apage->ischunk)
a->nchunks--;
else
a->npages--;
a->nentries--;
if (hash_search(a->pagetable,
(void *) &apage->blockno,
HASH_REMOVE, NULL) == NULL)
elog(ERROR, "hash table corrupted");
}
}
}
}
| static bool tbm_intersect_page | ( | TIDBitmap * | a, | |
| PagetableEntry * | apage, | |||
| const TIDBitmap * | b | |||
| ) | [static] |
Definition at line 466 of file tidbitmap.c.
References Assert, PagetableEntry::blockno, PagetableEntry::ischunk, NULL, PagetableEntry::recheck, tbm_find_pageentry(), tbm_page_is_lossy(), and PagetableEntry::words.
Referenced by tbm_intersect().
{
const PagetableEntry *bpage;
int wordnum;
if (apage->ischunk)
{
/* Scan each bit in chunk, try to clear */
bool candelete = true;
for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
{
bitmapword w = apage->words[wordnum];
if (w != 0)
{
bitmapword neww = w;
BlockNumber pg;
int bitnum;
pg = apage->blockno + (wordnum * BITS_PER_BITMAPWORD);
bitnum = 0;
while (w != 0)
{
if (w & 1)
{
if (!tbm_page_is_lossy(b, pg) &&
tbm_find_pageentry(b, pg) == NULL)
{
/* Page is not in b at all, lose lossy bit */
neww &= ~((bitmapword) 1 << bitnum);
}
}
pg++;
bitnum++;
w >>= 1;
}
apage->words[wordnum] = neww;
if (neww != 0)
candelete = false;
}
}
return candelete;
}
else if (tbm_page_is_lossy(b, apage->blockno))
{
/*
* Some of the tuples in 'a' might not satisfy the quals for 'b', but
* because the page 'b' is lossy, we don't know which ones. Therefore
* we mark 'a' as requiring rechecks, to indicate that at most those
* tuples set in 'a' are matches.
*/
apage->recheck = true;
return false;
}
else
{
bool candelete = true;
bpage = tbm_find_pageentry(b, apage->blockno);
if (bpage != NULL)
{
/* Both pages are exact, merge at the bit level */
Assert(!bpage->ischunk);
for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
{
apage->words[wordnum] &= bpage->words[wordnum];
if (apage->words[wordnum] != 0)
candelete = false;
}
apage->recheck |= bpage->recheck;
}
/* If there is no matching b page, we can just delete the a page */
return candelete;
}
}
Definition at line 547 of file tidbitmap.c.
References TIDBitmap::nentries.
Referenced by MultiExecBitmapAnd(), and startScanEntry().
{
return (tbm->nentries == 0);
}
| TBMIterateResult* tbm_iterate | ( | TBMIterator * | iterator | ) |
Definition at line 644 of file tidbitmap.c.
References Assert, BITNUM, BITS_PER_BITMAPWORD, TBMIterateResult::blockno, PagetableEntry::blockno, TIDBitmap::entry1, TIDBitmap::iterating, TIDBitmap::nchunks, TIDBitmap::npages, TBMIterateResult::ntuples, TBMIterateResult::offsets, TBMIterator::output, output(), PAGES_PER_CHUNK, PagetableEntry::recheck, TBMIterateResult::recheck, TBMIterator::schunkbit, TBMIterator::schunkptr, TIDBitmap::schunks, TBMIterator::spageptr, TIDBitmap::spages, TIDBitmap::status, TBMIterator::tbm, TBM_ONE_PAGE, WORDNUM, and PagetableEntry::words.
Referenced by BitmapHeapNext(), and entryGetItem().
{
TIDBitmap *tbm = iterator->tbm;
TBMIterateResult *output = &(iterator->output);
Assert(tbm->iterating);
/*
* If lossy chunk pages remain, make sure we've advanced schunkptr/
* schunkbit to the next set bit.
*/
while (iterator->schunkptr < tbm->nchunks)
{
PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
int schunkbit = iterator->schunkbit;
while (schunkbit < PAGES_PER_CHUNK)
{
int wordnum = WORDNUM(schunkbit);
int bitnum = BITNUM(schunkbit);
if ((chunk->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
break;
schunkbit++;
}
if (schunkbit < PAGES_PER_CHUNK)
{
iterator->schunkbit = schunkbit;
break;
}
/* advance to next chunk */
iterator->schunkptr++;
iterator->schunkbit = 0;
}
/*
* If both chunk and per-page data remain, must output the numerically
* earlier page.
*/
if (iterator->schunkptr < tbm->nchunks)
{
PagetableEntry *chunk = tbm->schunks[iterator->schunkptr];
BlockNumber chunk_blockno;
chunk_blockno = chunk->blockno + iterator->schunkbit;
if (iterator->spageptr >= tbm->npages ||
chunk_blockno < tbm->spages[iterator->spageptr]->blockno)
{
/* Return a lossy page indicator from the chunk */
output->blockno = chunk_blockno;
output->ntuples = -1;
output->recheck = true;
iterator->schunkbit++;
return output;
}
}
if (iterator->spageptr < tbm->npages)
{
PagetableEntry *page;
int ntuples;
int wordnum;
/* In ONE_PAGE state, we don't allocate an spages[] array */
if (tbm->status == TBM_ONE_PAGE)
page = &tbm->entry1;
else
page = tbm->spages[iterator->spageptr];
/* scan bitmap to extract individual offset numbers */
ntuples = 0;
for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
{
bitmapword w = page->words[wordnum];
if (w != 0)
{
int off = wordnum * BITS_PER_BITMAPWORD + 1;
while (w != 0)
{
if (w & 1)
output->offsets[ntuples++] = (OffsetNumber) off;
off++;
w >>= 1;
}
}
}
output->blockno = page->blockno;
output->ntuples = ntuples;
output->recheck = page->recheck;
iterator->spageptr++;
return output;
}
/* Nothing more in the bitmap */
return NULL;
}
| static void tbm_lossify | ( | TIDBitmap * | tbm | ) | [static] |
Definition at line 947 of file tidbitmap.c.
References Assert, PagetableEntry::blockno, hash_seq_init(), hash_seq_search(), hash_seq_term(), PagetableEntry::ischunk, TIDBitmap::iterating, TIDBitmap::maxentries, Min, TIDBitmap::nentries, NULL, PAGES_PER_CHUNK, TIDBitmap::pagetable, TIDBitmap::status, TBM_HASH, and tbm_mark_page_lossy().
Referenced by tbm_add_page(), tbm_add_tuples(), and tbm_union_page().
{
HASH_SEQ_STATUS status;
PagetableEntry *page;
/*
* XXX Really stupid implementation: this just lossifies pages in
* essentially random order. We should be paying some attention to the
* number of bits set in each page, instead.
*
* Since we are called as soon as nentries exceeds maxentries, we should
* push nentries down to significantly less than maxentries, or else we'll
* just end up doing this again very soon. We shoot for maxentries/2.
*/
Assert(!tbm->iterating);
Assert(tbm->status == TBM_HASH);
hash_seq_init(&status, tbm->pagetable);
while ((page = (PagetableEntry *) hash_seq_search(&status)) != NULL)
{
if (page->ischunk)
continue; /* already a chunk header */
/*
* If the page would become a chunk header, we won't save anything by
* converting it to lossy, so skip it.
*/
if ((page->blockno % PAGES_PER_CHUNK) == 0)
continue;
/* This does the dirty work ... */
tbm_mark_page_lossy(tbm, page->blockno);
if (tbm->nentries <= tbm->maxentries / 2)
{
/* we have done enough */
hash_seq_term(&status);
break;
}
/*
* Note: tbm_mark_page_lossy may have inserted a lossy chunk into the
* hashtable. We can continue the same seq_search scan since we do
* not care whether we visit lossy chunks or not.
*/
}
/*
* With a big bitmap and small work_mem, it's possible that we cannot get
* under maxentries. Again, if that happens, we'd end up uselessly
* calling tbm_lossify over and over. To prevent this from becoming a
* performance sink, force maxentries up to at least double the current
* number of entries. (In essence, we're admitting inability to fit
* within work_mem when we do this.) Note that this test will not fire if
* we broke out of the loop early; and if we didn't, the current number of
* entries is simply not reducible any further.
*/
if (tbm->nentries > tbm->maxentries / 2)
tbm->maxentries = Min(tbm->nentries, (INT_MAX - 1) / 2) * 2;
}
| static void tbm_mark_page_lossy | ( | TIDBitmap * | tbm, | |
| BlockNumber | pageno | |||
| ) | [static] |
Definition at line 877 of file tidbitmap.c.
References BITNUM, PagetableEntry::blockno, HASH_REMOVE, hash_search(), PagetableEntry::ischunk, MemSet, TIDBitmap::nchunks, TIDBitmap::nentries, TIDBitmap::npages, NULL, TIDBitmap::pagetable, TIDBitmap::status, tbm_create_pagetable(), TBM_HASH, WORDNUM, and PagetableEntry::words.
Referenced by tbm_add_page(), tbm_lossify(), and tbm_union_page().
{
PagetableEntry *page;
bool found;
BlockNumber chunk_pageno;
int bitno;
int wordnum;
int bitnum;
/* We force the bitmap into hashtable mode whenever it's lossy */
if (tbm->status != TBM_HASH)
tbm_create_pagetable(tbm);
bitno = pageno % PAGES_PER_CHUNK;
chunk_pageno = pageno - bitno;
/*
* Remove any extant non-lossy entry for the page. If the page is its own
* chunk header, however, we skip this and handle the case below.
*/
if (bitno != 0)
{
if (hash_search(tbm->pagetable,
(void *) &pageno,
HASH_REMOVE, NULL) != NULL)
{
/* It was present, so adjust counts */
tbm->nentries--;
tbm->npages--; /* assume it must have been non-lossy */
}
}
/* Look up or create entry for chunk-header page */
page = (PagetableEntry *) hash_search(tbm->pagetable,
(void *) &chunk_pageno,
HASH_ENTER, &found);
/* Initialize it if not present before */
if (!found)
{
MemSet(page, 0, sizeof(PagetableEntry));
page->blockno = chunk_pageno;
page->ischunk = true;
/* must count it too */
tbm->nentries++;
tbm->nchunks++;
}
else if (!page->ischunk)
{
/* chunk header page was formerly non-lossy, make it lossy */
MemSet(page, 0, sizeof(PagetableEntry));
page->blockno = chunk_pageno;
page->ischunk = true;
/* we assume it had some tuple bit(s) set, so mark it lossy */
page->words[0] = ((bitmapword) 1 << 0);
/* adjust counts */
tbm->nchunks++;
tbm->npages--;
}
/* Now set the original target page's bit */
wordnum = WORDNUM(bitno);
bitnum = BITNUM(bitno);
page->words[wordnum] |= ((bitmapword) 1 << bitnum);
}
| static bool tbm_page_is_lossy | ( | const TIDBitmap * | tbm, | |
| BlockNumber | pageno | |||
| ) | [static] |
Definition at line 843 of file tidbitmap.c.
References Assert, BITNUM, hash_search(), PagetableEntry::ischunk, TIDBitmap::nchunks, NULL, TIDBitmap::pagetable, TIDBitmap::status, TBM_HASH, WORDNUM, and PagetableEntry::words.
Referenced by tbm_add_tuples(), tbm_intersect_page(), and tbm_union_page().
{
PagetableEntry *page;
BlockNumber chunk_pageno;
int bitno;
/* we can skip the lookup if there are no lossy chunks */
if (tbm->nchunks == 0)
return false;
Assert(tbm->status == TBM_HASH);
bitno = pageno % PAGES_PER_CHUNK;
chunk_pageno = pageno - bitno;
page = (PagetableEntry *) hash_search(tbm->pagetable,
(void *) &chunk_pageno,
HASH_FIND, NULL);
if (page != NULL && page->ischunk)
{
int wordnum = WORDNUM(bitno);
int bitnum = BITNUM(bitno);
if ((page->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
return true;
}
return false;
}
Definition at line 333 of file tidbitmap.c.
References Assert, TIDBitmap::entry1, hash_seq_init(), hash_seq_search(), TIDBitmap::iterating, TIDBitmap::nentries, NULL, TIDBitmap::pagetable, TIDBitmap::status, TBM_HASH, TBM_ONE_PAGE, and tbm_union_page().
Referenced by MultiExecBitmapOr().
{
Assert(!a->iterating);
/* Nothing to do if b is empty */
if (b->nentries == 0)
return;
/* Scan through chunks and pages in b, merge into a */
if (b->status == TBM_ONE_PAGE)
tbm_union_page(a, &b->entry1);
else
{
HASH_SEQ_STATUS status;
PagetableEntry *bpage;
Assert(b->status == TBM_HASH);
hash_seq_init(&status, b->pagetable);
while ((bpage = (PagetableEntry *) hash_seq_search(&status)) != NULL)
tbm_union_page(a, bpage);
}
}
| static void tbm_union_page | ( | TIDBitmap * | a, | |
| const PagetableEntry * | bpage | |||
| ) | [static] |
Definition at line 356 of file tidbitmap.c.
References PagetableEntry::blockno, PagetableEntry::ischunk, TIDBitmap::maxentries, TIDBitmap::nentries, PagetableEntry::recheck, tbm_get_pageentry(), tbm_lossify(), tbm_mark_page_lossy(), tbm_page_is_lossy(), and PagetableEntry::words.
Referenced by tbm_union().
{
PagetableEntry *apage;
int wordnum;
if (bpage->ischunk)
{
/* Scan b's chunk, mark each indicated page lossy in a */
for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
{
bitmapword w = bpage->words[wordnum];
if (w != 0)
{
BlockNumber pg;
pg = bpage->blockno + (wordnum * BITS_PER_BITMAPWORD);
while (w != 0)
{
if (w & 1)
tbm_mark_page_lossy(a, pg);
pg++;
w >>= 1;
}
}
}
}
else if (tbm_page_is_lossy(a, bpage->blockno))
{
/* page is already lossy in a, nothing to do */
return;
}
else
{
apage = tbm_get_pageentry(a, bpage->blockno);
if (apage->ischunk)
{
/* The page is a lossy chunk header, set bit for itself */
apage->words[0] |= ((bitmapword) 1 << 0);
}
else
{
/* Both pages are exact, merge at the bit level */
for (wordnum = 0; wordnum < WORDS_PER_PAGE; wordnum++)
apage->words[wordnum] |= bpage->words[wordnum];
apage->recheck |= bpage->recheck;
}
}
if (a->nentries > a->maxentries)
tbm_lossify(a);
}
1.7.1