Header And Logo

PostgreSQL
| The world's most advanced open source database.

Data Structures | Defines | Typedefs | Enumerations | Functions

tidbitmap.c File Reference

#include "postgres.h"
#include <limits.h>
#include "access/htup_details.h"
#include "nodes/bitmapset.h"
#include "nodes/tidbitmap.h"
#include "utils/hsearch.h"
Include dependency graph for tidbitmap.c:

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 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)
TIDBitmaptbm_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)
TBMIteratortbm_begin_iterate (TIDBitmap *tbm)
TBMIterateResulttbm_iterate (TBMIterator *iterator)
void tbm_end_iterate (TBMIterator *iterator)

Define Documentation

#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 Documentation


Enumeration Type Documentation

enum TBMStatus
Enumerator:
TBM_EMPTY 
TBM_ONE_PAGE 
TBM_HASH 

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;


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

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

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

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

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

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

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

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