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 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)
static int	tbm_shared_comparator (const void *left, const void *right, void *arg)
TIDBitmap *	tbm_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)
TBMIterator *	tbm_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)
TBMIterateResult *	tbm_iterate (TBMIterator *iterator)
TBMIterateResult *	tbm_shared_iterate (TBMSharedIterator *iterator)
void	tbm_end_iterate (TBMIterator *iterator)
void	tbm_end_shared_iterate (TBMSharedIterator *iterator)
TBMSharedIterator *	tbm_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

typedef struct PagetableEntry PagetableEntry

PTEntryArray

typedef struct PTEntryArray PTEntryArray

PTIterationArray

typedef struct PTIterationArray PTIterationArray

TBMSharedIteratorState

typedef struct TBMSharedIteratorState TBMSharedIteratorState

Enumeration Type Documentation

TBMIteratingState

enum TBMIteratingState

Enumerator
TBM_NOT_ITERATING
TBM_ITERATING_PRIVATE
TBM_ITERATING_SHARED

Definition at line 138 of file tidbitmap.c.

{
    TBM_NOT_ITERATING,          /* not yet converted to page and chunk array */
    TBM_ITERATING_PRIVATE,      /* converted to local page and chunk array */
    TBM_ITERATING_SHARED        /* converted to shared page and chunk array */
} TBMIteratingState;

TBMStatus

enum TBMStatus

Enumerator
TBM_EMPTY
TBM_ONE_PAGE
TBM_HASH

Definition at line 128 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

pagetable_allocate()

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

inlinestatic

Definition at line 1497 of file tidbitmap.c.

{
    TIDBitmap  *tbm = (TIDBitmap *) pagetable->private_data;
    PTEntryArray *ptbase;
 
    if (tbm->dsa == NULL)
        return MemoryContextAllocExtended(pagetable->ctx, size,
                                          MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO);
 
    /*
     * Save the dsapagetable reference in dsapagetableold before allocating
     * new memory so that pagetable_free can free the old entry.
     */
    tbm->dsapagetableold = tbm->dsapagetable;
    tbm->dsapagetable = dsa_allocate_extended(tbm->dsa,
                                              sizeof(PTEntryArray) + size,
                                              DSA_ALLOC_HUGE | DSA_ALLOC_ZERO);
    ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
 
    return ptbase->ptentry;
}

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.

{
    TIDBitmap  *tbm = (TIDBitmap *) pagetable->private_data;
 
    /* pfree the input pointer if DSA is not available */
    if (tbm->dsa == NULL)
        pfree(pointer);
    else if (DsaPointerIsValid(tbm->dsapagetableold))
    {
        dsa_free(tbm->dsa, tbm->dsapagetableold);
        tbm->dsapagetableold = InvalidDsaPointer;
    }
}

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.

{
    /* 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);
}

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.

{
    BlockNumber currblk = InvalidBlockNumber;
    PagetableEntry *page = NULL;    /* only valid when currblk is valid */
    int         i;
 
    Assert(tbm->iterating == TBM_NOT_ITERATING);
    for (i = 0; i < ntids; i++)
    {
        BlockNumber blk = ItemPointerGetBlockNumber(tids + i);
        OffsetNumber off = ItemPointerGetOffsetNumber(tids + i);
        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);
 
        /*
         * Look up target page unless we already did.  This saves cycles when
         * the input includes consecutive tuples on the same page, which is
         * common enough to justify an extra test here.
         */
        if (blk != currblk)
        {
            if (tbm_page_is_lossy(tbm, blk))
                page = NULL;    /* remember page is lossy */
            else
                page = tbm_get_pageentry(tbm, blk);
            currblk = blk;
        }
 
        if (page == NULL)
            continue;           /* whole page is already marked */
 
        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);
            /* Page could have been converted to lossy, so force new lookup */
            currblk = InvalidBlockNumber;
        }
    }
}

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.

{
    int         schunkbit = *schunkbitp;
 
    while (schunkbit < PAGES_PER_CHUNK)
    {
        int         wordnum = WORDNUM(schunkbit);
        int         bitnum = BITNUM(schunkbit);
 
        if ((chunk->words[wordnum] & ((bitmapword) 1 << bitnum)) != 0)
            break;
        schunkbit++;
    }
 
    *schunkbitp = schunkbit;
}

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.

{
    TBMSharedIterator *iterator;
    TBMSharedIteratorState *istate;
 
    /*
     * Create the TBMSharedIterator struct, with enough trailing space to
     * serve the needs of the TBMIterateResult sub-struct.
     */
    iterator = (TBMSharedIterator *) palloc0(sizeof(TBMSharedIterator) +
                                             MAX_TUPLES_PER_PAGE * sizeof(OffsetNumber));
 
    istate = (TBMSharedIteratorState *) dsa_get_address(dsa, dp);
 
    iterator->state = istate;
 
    iterator->ptbase = dsa_get_address(dsa, istate->pagetable);
 
    if (istate->npages)
        iterator->ptpages = dsa_get_address(dsa, istate->spages);
    if (istate->nchunks)
        iterator->ptchunks = dsa_get_address(dsa, istate->schunks);
 
    return iterator;
}

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.

{
    TBMIterator *iterator;
 
    Assert(tbm->iterating != TBM_ITERATING_SHARED);
 
    /*
     * 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 == TBM_NOT_ITERATING)
    {
        pagetable_iterator i;
        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 *));
 
        npages = nchunks = 0;
        pagetable_start_iterate(tbm->pagetable, &i);
        while ((page = pagetable_iterate(tbm->pagetable, &i)) != 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 = TBM_ITERATING_PRIVATE;
 
    return iterator;
}

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.

{
    long        nbuckets;
 
    /*
     * Estimate number of hashtable entries we can have within maxbytes. This
     * estimates the hash cost as sizeof(PagetableEntry), which is good enough
     * for our purpose.  Also count an extra Pointer per entry for the arrays
     * created during iteration readout.
     */
    nbuckets = maxbytes /
        (sizeof(PagetableEntry) + sizeof(Pointer) + sizeof(Pointer));
    nbuckets = Min(nbuckets, INT_MAX - 1);  /* safety limit */
    nbuckets = Max(nbuckets, 16);   /* sanity limit */
 
    return nbuckets;
}

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.

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

Referenced by tbm_begin_iterate().

tbm_create()

TIDBitmap* tbm_create	(	long	maxbytes,
		dsa_area *	dsa
	)

Definition at line 265 of file tidbitmap.c.

{
    TIDBitmap  *tbm;
 
    /* Create the TIDBitmap struct and zero all its fields */
    tbm = makeNode(TIDBitmap);
 
    tbm->mcxt = CurrentMemoryContext;
    tbm->status = TBM_EMPTY;
 
    tbm->maxentries = (int) tbm_calculate_entries(maxbytes);
    tbm->lossify_start = 0;
    tbm->dsa = dsa;
    tbm->dsapagetable = InvalidDsaPointer;
    tbm->dsapagetableold = InvalidDsaPointer;
    tbm->ptpages = InvalidDsaPointer;
    tbm->ptchunks = InvalidDsaPointer;
 
    return tbm;
}

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.

{
    Assert(tbm->status != TBM_HASH);
    Assert(tbm->pagetable == NULL);
 
    tbm->pagetable = pagetable_create(tbm->mcxt, 128, tbm);
 
    /* If entry1 is valid, push it into the hashtable */
    if (tbm->status == TBM_ONE_PAGE)
    {
        PagetableEntry *page;
        bool        found;
        char        oldstatus;
 
        page = pagetable_insert(tbm->pagetable,
                                tbm->entry1.blockno,
                                &found);
        Assert(!found);
        oldstatus = page->status;
        memcpy(page, &tbm->entry1, sizeof(PagetableEntry));
        page->status = oldstatus;
    }
 
    tbm->status = TBM_HASH;
}

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.

{
    pfree(iterator);
}

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.

{
    pfree(iterator);
}

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.

{
    int         wordnum;
    int         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;
            }
        }
    }
 
    return ntuples;
}

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.

{
    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 = pagetable_lookup(tbm->pagetable, pageno);
    if (page == NULL)
        return NULL;
    if (page->ischunk)
        return NULL;            /* don't want a lossy chunk header */
    return page;
}

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.

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

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.

{
    TBMSharedIteratorState *istate = dsa_get_address(dsa, dp);
    PTEntryArray *ptbase;
    PTIterationArray *ptpages;
    PTIterationArray *ptchunks;
 
    if (DsaPointerIsValid(istate->pagetable))
    {
        ptbase = dsa_get_address(dsa, istate->pagetable);
        if (pg_atomic_sub_fetch_u32(&ptbase->refcount, 1) == 0)
            dsa_free(dsa, istate->pagetable);
    }
    if (DsaPointerIsValid(istate->spages))
    {
        ptpages = dsa_get_address(dsa, istate->spages);
        if (pg_atomic_sub_fetch_u32(&ptpages->refcount, 1) == 0)
            dsa_free(dsa, istate->spages);
    }
    if (DsaPointerIsValid(istate->schunks))
    {
        ptchunks = dsa_get_address(dsa, istate->schunks);
        if (pg_atomic_sub_fetch_u32(&ptchunks->refcount, 1) == 0)
            dsa_free(dsa, istate->schunks);
    }
 
    dsa_free(dsa, dp);
}

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.

{
    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 = pagetable_insert(tbm->pagetable, pageno, &found);
    }
 
    /* Initialize it if not present before */
    if (!found)
    {
        char        oldstatus = page->status;
 
        MemSet(page, 0, sizeof(PagetableEntry));
        page->status = oldstatus;
        page->blockno = pageno;
        /* must count it too */
        tbm->nentries++;
        tbm->npages++;
    }
 
    return page;
}

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.

{
    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
    {
        pagetable_iterator i;
        PagetableEntry *apage;
 
        Assert(a->status == TBM_HASH);
        pagetable_start_iterate(a->pagetable, &i);
        while ((apage = pagetable_iterate(a->pagetable, &i)) != 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 (!pagetable_delete(a->pagetable, apage->blockno))
                    elog(ERROR, "hash table corrupted");
            }
        }
    }
}

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.

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

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.

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

References TIDBitmap::nentries.

Referenced by MultiExecBitmapAnd(), and startScanEntry().

tbm_iterate()

TBMIterateResult* tbm_iterate

(

TBMIterator *

iterator

)

Definition at line 970 of file tidbitmap.c.

{
    TIDBitmap  *tbm = iterator->tbm;
    TBMIterateResult *output = &(iterator->output);
 
    Assert(tbm->iterating == TBM_ITERATING_PRIVATE);
 
    /*
     * 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;
 
        tbm_advance_schunkbit(chunk, &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;
 
        /* In TBM_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 = tbm_extract_page_tuple(page, output);
        output->blockno = page->blockno;
        output->ntuples = ntuples;
        output->recheck = page->recheck;
        iterator->spageptr++;
        return output;
    }
 
    /* Nothing more in the bitmap */
    return NULL;
}

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.

{
    pagetable_iterator i;
    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 == TBM_NOT_ITERATING);
    Assert(tbm->status == TBM_HASH);
 
    pagetable_start_iterate_at(tbm->pagetable, &i, tbm->lossify_start);
    while ((page = pagetable_iterate(tbm->pagetable, &i)) != 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 made enough room. Remember where to start lossifying
             * next round, so we evenly iterate over the hashtable.
             */
            tbm->lossify_start = i.cur;
            break;
        }
 
        /*
         * Note: tbm_mark_page_lossy may have inserted a lossy chunk into the
         * hashtable and may have deleted the non-lossy chunk.  We can
         * continue the same hash table scan, since failure to visit one
         * element or visiting the newly inserted element, isn't fatal.
         */
    }
 
    /*
     * 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;
}

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.

{
    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 (pagetable_delete(tbm->pagetable, pageno))
        {
            /* 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 = pagetable_insert(tbm->pagetable, chunk_pageno, &found);
 
    /* Initialize it if not present before */
    if (!found)
    {
        char        oldstatus = page->status;
 
        MemSet(page, 0, sizeof(PagetableEntry));
        page->status = oldstatus;
        page->blockno = chunk_pageno;
        page->ischunk = true;
        /* must count it too */
        tbm->nentries++;
        tbm->nchunks++;
    }
    else if (!page->ischunk)
    {
        char        oldstatus = page->status;
 
        /* chunk header page was formerly non-lossy, make it lossy */
        MemSet(page, 0, sizeof(PagetableEntry));
        page->status = oldstatus;
        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);
}

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.

{
    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 = pagetable_lookup(tbm->pagetable, chunk_pageno);
 
    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;
}

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.

{
    dsa_pointer dp;
    TBMSharedIteratorState *istate;
    PTEntryArray *ptbase = NULL;
    PTIterationArray *ptpages = NULL;
    PTIterationArray *ptchunks = NULL;
 
    Assert(tbm->dsa != NULL);
    Assert(tbm->iterating != TBM_ITERATING_PRIVATE);
 
    /*
     * Allocate TBMSharedIteratorState from DSA to hold the shared members and
     * lock, this will also be used by multiple worker for shared iterate.
     */
    dp = dsa_allocate0(tbm->dsa, sizeof(TBMSharedIteratorState));
    istate = dsa_get_address(tbm->dsa, dp);
 
    /*
     * If we're not already iterating, create and fill the sorted page lists.
     * (If we are, the sorted page lists are already stored in the TIDBitmap,
     * and we can just reuse them.)
     */
    if (tbm->iterating == TBM_NOT_ITERATING)
    {
        pagetable_iterator i;
        PagetableEntry *page;
        int         idx;
        int         npages;
        int         nchunks;
 
        /*
         * Allocate the page and chunk array memory from the DSA to share
         * across multiple processes.
         */
        if (tbm->npages)
        {
            tbm->ptpages = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
                                        tbm->npages * sizeof(int));
            ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
            pg_atomic_init_u32(&ptpages->refcount, 0);
        }
        if (tbm->nchunks)
        {
            tbm->ptchunks = dsa_allocate(tbm->dsa, sizeof(PTIterationArray) +
                                         tbm->nchunks * sizeof(int));
            ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
            pg_atomic_init_u32(&ptchunks->refcount, 0);
        }
 
        /*
         * If TBM status is TBM_HASH then iterate over the pagetable and
         * convert it to page and chunk arrays.  But if it's in the
         * TBM_ONE_PAGE mode then directly allocate the space for one entry
         * from the DSA.
         */
        npages = nchunks = 0;
        if (tbm->status == TBM_HASH)
        {
            ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
 
            pagetable_start_iterate(tbm->pagetable, &i);
            while ((page = pagetable_iterate(tbm->pagetable, &i)) != NULL)
            {
                idx = page - ptbase->ptentry;
                if (page->ischunk)
                    ptchunks->index[nchunks++] = idx;
                else
                    ptpages->index[npages++] = idx;
            }
 
            Assert(npages == tbm->npages);
            Assert(nchunks == tbm->nchunks);
        }
        else if (tbm->status == TBM_ONE_PAGE)
        {
            /*
             * In one page mode allocate the space for one pagetable entry,
             * initialize it, and directly store its index (i.e. 0) in the
             * page array.
             */
            tbm->dsapagetable = dsa_allocate(tbm->dsa, sizeof(PTEntryArray) +
                                             sizeof(PagetableEntry));
            ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
            memcpy(ptbase->ptentry, &tbm->entry1, sizeof(PagetableEntry));
            ptpages->index[0] = 0;
        }
 
        if (ptbase != NULL)
            pg_atomic_init_u32(&ptbase->refcount, 0);
        if (npages > 1)
            qsort_arg(ptpages->index, npages, sizeof(int),
                      tbm_shared_comparator, ptbase->ptentry);
        if (nchunks > 1)
            qsort_arg(ptchunks->index, nchunks, sizeof(int),
                      tbm_shared_comparator, ptbase->ptentry);
    }
 
    /*
     * Store the TBM members in the shared state so that we can share them
     * across multiple processes.
     */
    istate->nentries = tbm->nentries;
    istate->maxentries = tbm->maxentries;
    istate->npages = tbm->npages;
    istate->nchunks = tbm->nchunks;
    istate->pagetable = tbm->dsapagetable;
    istate->spages = tbm->ptpages;
    istate->schunks = tbm->ptchunks;
 
    ptbase = dsa_get_address(tbm->dsa, tbm->dsapagetable);
    ptpages = dsa_get_address(tbm->dsa, tbm->ptpages);
    ptchunks = dsa_get_address(tbm->dsa, tbm->ptchunks);
 
    /*
     * For every shared iterator, referring to pagetable and iterator array,
     * increase the refcount by 1 so that while freeing the shared iterator we
     * don't free pagetable and iterator array until its refcount becomes 0.
     */
    if (ptbase != NULL)
        pg_atomic_add_fetch_u32(&ptbase->refcount, 1);
    if (ptpages != NULL)
        pg_atomic_add_fetch_u32(&ptpages->refcount, 1);
    if (ptchunks != NULL)
        pg_atomic_add_fetch_u32(&ptchunks->refcount, 1);
 
    /* Initialize the iterator lock */
    LWLockInitialize(&istate->lock, LWTRANCHE_SHARED_TIDBITMAP);
 
    /* Initialize the shared iterator state */
    istate->schunkbit = 0;
    istate->schunkptr = 0;
    istate->spageptr = 0;
 
    tbm->iterating = TBM_ITERATING_SHARED;
 
    return dp;
}

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.

{
    PagetableEntry *base = (PagetableEntry *) arg;
    PagetableEntry *lpage = &base[*(int *) left];
    PagetableEntry *rpage = &base[*(int *) right];
 
    if (lpage->blockno < rpage->blockno)
        return -1;
    else if (lpage->blockno > rpage->blockno)
        return 1;
    return 0;
}

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.

{
    TBMIterateResult *output = &iterator->output;
    TBMSharedIteratorState *istate = iterator->state;
    PagetableEntry *ptbase = NULL;
    int        *idxpages = NULL;
    int        *idxchunks = NULL;
 
    if (iterator->ptbase != NULL)
        ptbase = iterator->ptbase->ptentry;
    if (iterator->ptpages != NULL)
        idxpages = iterator->ptpages->index;
    if (iterator->ptchunks != NULL)
        idxchunks = iterator->ptchunks->index;
 
    /* Acquire the LWLock before accessing the shared members */
    LWLockAcquire(&istate->lock, LW_EXCLUSIVE);
 
    /*
     * If lossy chunk pages remain, make sure we've advanced schunkptr/
     * schunkbit to the next set bit.
     */
    while (istate->schunkptr < istate->nchunks)
    {
        PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
        int         schunkbit = istate->schunkbit;
 
        tbm_advance_schunkbit(chunk, &schunkbit);
        if (schunkbit < PAGES_PER_CHUNK)
        {
            istate->schunkbit = schunkbit;
            break;
        }
        /* advance to next chunk */
        istate->schunkptr++;
        istate->schunkbit = 0;
    }
 
    /*
     * If both chunk and per-page data remain, must output the numerically
     * earlier page.
     */
    if (istate->schunkptr < istate->nchunks)
    {
        PagetableEntry *chunk = &ptbase[idxchunks[istate->schunkptr]];
        BlockNumber chunk_blockno;
 
        chunk_blockno = chunk->blockno + istate->schunkbit;
 
        if (istate->spageptr >= istate->npages ||
            chunk_blockno < ptbase[idxpages[istate->spageptr]].blockno)
        {
            /* Return a lossy page indicator from the chunk */
            output->blockno = chunk_blockno;
            output->ntuples = -1;
            output->recheck = true;
            istate->schunkbit++;
 
            LWLockRelease(&istate->lock);
            return output;
        }
    }
 
    if (istate->spageptr < istate->npages)
    {
        PagetableEntry *page = &ptbase[idxpages[istate->spageptr]];
        int         ntuples;
 
        /* scan bitmap to extract individual offset numbers */
        ntuples = tbm_extract_page_tuple(page, output);
        output->blockno = page->blockno;
        output->ntuples = ntuples;
        output->recheck = page->recheck;
        istate->spageptr++;
 
        LWLockRelease(&istate->lock);
 
        return output;
    }
 
    LWLockRelease(&istate->lock);
 
    /* Nothing more in the bitmap */
    return NULL;
}

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.

{
    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
    {
        pagetable_iterator i;
        PagetableEntry *bpage;
 
        Assert(b->status == TBM_HASH);
        pagetable_start_iterate(b->pagetable, &i);
        while ((bpage = pagetable_iterate(b->pagetable, &i)) != NULL)
            tbm_union_page(a, bpage);
    }
}

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.

{
    PagetableEntry *apage;
    int         wordnum;
 
    if (bpage->ischunk)
    {
        /* Scan b's chunk, mark each indicated page lossy in a */
        for (wordnum = 0; wordnum < WORDS_PER_CHUNK; 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);
}

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