#include "storage/itemptr.h"

Include dependency graph for tidbitmap.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	TBMIterateResult
Typedefs
typedef struct TIDBitmap	TIDBitmap
typedef struct TBMIterator	TBMIterator
Functions
TIDBitmap *	tbm_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)
TBMIterator *	tbm_begin_iterate (TIDBitmap *tbm)
TBMIterateResult *	tbm_iterate (TBMIterator *iterator)
void	tbm_end_iterate (TBMIterator *iterator)

Typedef Documentation

typedef struct TBMIterator TBMIterator

Definition at line 35 of file tidbitmap.h.

typedef struct TIDBitmap TIDBitmap

Definition at line 32 of file tidbitmap.h.

Function Documentation

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;
}

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;
}

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);
}

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().

{
    if (tbm->pagetable)
        hash_destroy(tbm->pagetable);
    if (tbm->spages)
        pfree(tbm->spages);
    if (tbm->schunks)
        pfree(tbm->schunks);
    pfree(tbm);
}

void tbm_intersect	(	TIDBitmap *	a,
		const TIDBitmap *	b
	)

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");
            }
        }
    }
}

bool tbm_is_empty ( const TIDBitmap * tbm )

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;
}

void tbm_union	(	TIDBitmap *	a,
		const TIDBitmap *	b
	)

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);
    }
}

Header And Logo

tidbitmap.h File Reference

Data Structures

Typedefs

Functions

Typedef Documentation

Function Documentation