#include "postgres.h"
#include <limits.h>
#include "access/htup_details.h"
#include "common/hashfn.h"
#include "common/int.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:

Data Structures
struct	PagetableEntry

struct	PTEntryArray

struct	TIDBitmap

struct	TBMPrivateIterator

struct	TBMSharedIteratorState

struct	PTIterationArray

struct	TBMSharedIterator

Macros
#define	PAGES_PER_CHUNK (BLCKSZ / 32)

#define	WORDNUM(x) ((x) / BITS_PER_BITMAPWORD)

#define	BITNUM(x) ((x) % BITS_PER_BITMAPWORD)

#define	WORDS_PER_PAGE ((TBM_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 (Size 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 ItemPointerData 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)

TBMPrivateIterator *	tbm_begin_private_iterate (TIDBitmap *tbm)

dsa_pointer	tbm_prepare_shared_iterate (TIDBitmap *tbm)

int	tbm_extract_page_tuple (TBMIterateResult iteritem, OffsetNumber offsets, uint32 max_offsets)

static void	tbm_advance_schunkbit (PagetableEntry chunk, int schunkbitp)

bool	tbm_private_iterate (TBMPrivateIterator iterator, TBMIterateResult tbmres)

bool	tbm_shared_iterate (TBMSharedIterator iterator, TBMIterateResult tbmres)

void	tbm_end_private_iterate (TBMPrivateIterator *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)

int	tbm_calculate_entries (Size maxbytes)

TBMIterator	tbm_begin_iterate (TIDBitmap tbm, dsa_area dsa, dsa_pointer dsp)

void	tbm_end_iterate (TBMIterator *iterator)

bool	tbm_iterate (TBMIterator iterator, TBMIterateResult tbmres)

Macro Definition Documentation

◆ BITNUM

#define BITNUM ( x ) ((x) % BITS_PER_BITMAPWORD)

Definition at line 71 of file tidbitmap.c.

◆ PAGES_PER_CHUNK

#define PAGES_PER_CHUNK (BLCKSZ / 32)

Definition at line 66 of file tidbitmap.c.

◆ SH_DECLARE

#define SH_DECLARE

Definition at line 242 of file tidbitmap.c.

◆ SH_DEFINE

#define SH_DEFINE

Definition at line 241 of file tidbitmap.c.

◆ SH_ELEMENT_TYPE

#define SH_ELEMENT_TYPE PagetableEntry

Definition at line 235 of file tidbitmap.c.

◆ SH_EQUAL

#define SH_EQUAL	(	tb,
		a,
		b
	)	a == b

Definition at line 239 of file tidbitmap.c.

◆ SH_HASH_KEY

#define SH_HASH_KEY	(	tb,
		key
	)	murmurhash32(key)

Definition at line 238 of file tidbitmap.c.

◆ SH_KEY

#define SH_KEY blockno

Definition at line 237 of file tidbitmap.c.

◆ SH_KEY_TYPE

#define SH_KEY_TYPE BlockNumber

Definition at line 236 of file tidbitmap.c.

◆ SH_PREFIX

#define SH_PREFIX pagetable

Definition at line 234 of file tidbitmap.c.

◆ SH_SCOPE

#define SH_SCOPE static inline

Definition at line 240 of file tidbitmap.c.

◆ SH_USE_NONDEFAULT_ALLOCATOR

#define SH_USE_NONDEFAULT_ALLOCATOR

Definition at line 233 of file tidbitmap.c.

◆ WORDNUM

#define WORDNUM ( x ) ((x) / BITS_PER_BITMAPWORD)

Definition at line 70 of file tidbitmap.c.

◆ WORDS_PER_CHUNK

#define WORDS_PER_CHUNK ((PAGES_PER_CHUNK - 1) / BITS_PER_BITMAPWORD + 1)

Definition at line 76 of file tidbitmap.c.

◆ WORDS_PER_PAGE

#define WORDS_PER_PAGE ((TBM_MAX_TUPLES_PER_PAGE - 1) / BITS_PER_BITMAPWORD + 1)

Definition at line 74 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 131 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 121 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 1494 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 1522 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 432 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 ItemPointerData *	tids,
		int	ntids,
		bool	recheck
	)

Definition at line 367 of file tidbitmap.c.

{
    BlockNumber currblk = InvalidBlockNumber;
    PagetableEntry *page = NULL;    /* only valid when currblk is valid */
 
    Assert(tbm->iterating == TBM_NOT_ITERATING);
    for (int 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 > TBM_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, TIDBitmap::maxentries, TIDBitmap::nentries, PagetableEntry::recheck, tbm_get_pageentry(), tbm_lossify(), TBM_MAX_TUPLES_PER_PAGE, 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 935 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_private_iterate(), and tbm_shared_iterate().

◆ tbm_attach_shared_iterate()

TBMSharedIterator * tbm_attach_shared_iterate	(	dsa_area *	dsa,
		dsa_pointer	dp
	)

Definition at line 1462 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));
 
    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(), TBMSharedIteratorState::nchunks, TBMSharedIteratorState::npages, TBMSharedIteratorState::pagetable, palloc0(), TBMSharedIterator::ptbase, TBMSharedIterator::ptchunks, TBMSharedIterator::ptpages, TBMSharedIteratorState::schunks, TBMSharedIteratorState::spages, and TBMSharedIterator::state.

Referenced by tbm_begin_iterate().

◆ tbm_begin_iterate()

TBMIterator tbm_begin_iterate	(	TIDBitmap *	tbm,
		dsa_area *	dsa,
		dsa_pointer	dsp
	)

Definition at line 1571 of file tidbitmap.c.

{
    TBMIterator iterator = {0};
 
    /* Allocate a private iterator and attach the shared state to it */
    if (DsaPointerIsValid(dsp))
    {
        iterator.shared = true;
        iterator.i.shared_iterator = tbm_attach_shared_iterate(dsa, dsp);
    }
    else
    {
        iterator.shared = false;
        iterator.i.private_iterator = tbm_begin_private_iterate(tbm);
    }
 
    return iterator;
}

References DsaPointerIsValid, TBMIterator::i, TBMIterator::private_iterator, TBMIterator::shared, TBMIterator::shared_iterator, tbm_attach_shared_iterate(), and tbm_begin_private_iterate().

Referenced by BitmapTableScanSetup().

◆ tbm_begin_private_iterate()

TBMPrivateIterator * tbm_begin_private_iterate ( TIDBitmap * tbm )

Definition at line 676 of file tidbitmap.c.

{
    TBMPrivateIterator *iterator;
 
    Assert(tbm->iterating != TBM_ITERATING_SHARED);
 
    /*
     * Create the TBMPrivateIterator struct, with enough trailing space to
     * serve the needs of the TBMIterateResult sub-struct.
     */
    iterator = (TBMPrivateIterator *) palloc(sizeof(TBMPrivateIterator));
    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, TIDBitmap::mcxt, MemoryContextAlloc(), TIDBitmap::nchunks, TIDBitmap::npages, TIDBitmap::pagetable, palloc(), qsort, TBMPrivateIterator::schunkbit, TBMPrivateIterator::schunkptr, TIDBitmap::schunks, TBMPrivateIterator::spageptr, TIDBitmap::spages, TIDBitmap::status, TBMPrivateIterator::tbm, tbm_comparator(), TBM_HASH, TBM_ITERATING_PRIVATE, TBM_ITERATING_SHARED, and TBM_NOT_ITERATING.

Referenced by startScanEntry(), and tbm_begin_iterate().

◆ tbm_calculate_entries()

int tbm_calculate_entries ( Size maxbytes )

Definition at line 1542 of file tidbitmap.c.

{
    Size        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 (int) 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 1425 of file tidbitmap.c.

{
    BlockNumber l = (*((PagetableEntry *const *) left))->blockno;
    BlockNumber r = (*((PagetableEntry *const *) right))->blockno;
 
    return pg_cmp_u32(l, r);
}

References pg_cmp_u32().

Referenced by tbm_begin_private_iterate().

◆ tbm_create()

TIDBitmap * tbm_create	(	Size	maxbytes,
		dsa_area *	dsa
	)

Definition at line 256 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 = 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 282 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 1594 of file tidbitmap.c.

{
    Assert(iterator && !tbm_exhausted(iterator));
 
    if (iterator->shared)
        tbm_end_shared_iterate(iterator->i.shared_iterator);
    else
        tbm_end_private_iterate(iterator->i.private_iterator);
 
    *iterator = (TBMIterator)
    {
        0
    };
}

References Assert(), TBMIterator::i, TBMIterator::private_iterator, TBMIterator::shared, TBMIterator::shared_iterator, tbm_end_private_iterate(), tbm_end_shared_iterate(), and tbm_exhausted().

Referenced by ExecEndBitmapHeapScan(), and ExecReScanBitmapHeapScan().

◆ tbm_end_private_iterate()

void tbm_end_private_iterate ( TBMPrivateIterator * iterator )

Definition at line 1147 of file tidbitmap.c.

{
    pfree(iterator);
}

References pfree().

Referenced by entryGetItem(), ginFreeScanKeys(), startScanEntry(), and tbm_end_iterate().

◆ tbm_end_shared_iterate()

void tbm_end_shared_iterate ( TBMSharedIterator * iterator )

Definition at line 1159 of file tidbitmap.c.

{
    pfree(iterator);
}

References pfree().

Referenced by tbm_end_iterate().

◆ tbm_extract_page_tuple()

int tbm_extract_page_tuple	(	TBMIterateResult *	iteritem,
		OffsetNumber *	offsets,
		uint32	max_offsets
	)

Definition at line 899 of file tidbitmap.c.

{
    PagetableEntry *page = iteritem->internal_page;
    int         ntuples = 0;
 
    for (int 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)
                {
                    if (ntuples < max_offsets)
                        offsets[ntuples] = (OffsetNumber) off;
                    ntuples++;
                }
                off++;
                w >>= 1;
            }
        }
    }
 
    return ntuples;
}

References BITS_PER_BITMAPWORD, TBMIterateResult::internal_page, PagetableEntry::words, and WORDS_PER_PAGE.

Referenced by BitmapHeapScanNextBlock(), and entryGetItem().

◆ tbm_find_pageentry()

static const PagetableEntry * tbm_find_pageentry	(	const TIDBitmap *	tbm,
		BlockNumber	pageno
	)

static

Definition at line 1170 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 312 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 331 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 1203 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 528 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 577 of file tidbitmap.c.

{
    const PagetableEntry *bpage;
 
    if (apage->ischunk)
    {
        /* Scan each bit in chunk, try to clear */
        bool        candelete = true;
 
        for (int 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 (int 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 657 of file tidbitmap.c.

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

References TIDBitmap::nentries.

Referenced by MultiExecBitmapAnd(), and startScanEntry().

◆ tbm_iterate()

bool tbm_iterate	(	TBMIterator *	iterator,
		TBMIterateResult *	tbmres
	)

Definition at line 1614 of file tidbitmap.c.

{
    Assert(iterator);
    Assert(tbmres);
 
    if (iterator->shared)
        return tbm_shared_iterate(iterator->i.shared_iterator, tbmres);
    else
        return tbm_private_iterate(iterator->i.private_iterator, tbmres);
}

References Assert(), TBMIterator::i, TBMIterator::private_iterator, TBMIterator::shared, TBMIterator::shared_iterator, tbm_private_iterate(), and tbm_shared_iterate().

Referenced by bitmapheap_stream_read_next().

◆ tbm_lossify()

static void tbm_lossify ( TIDBitmap * tbm )

static

Definition at line 1356 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 1284 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 1250 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 752 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;
}

Referenced by BitmapTableScanSetup().

◆ tbm_private_iterate()

bool tbm_private_iterate	(	TBMPrivateIterator *	iterator,
		TBMIterateResult *	tbmres
	)

Definition at line 974 of file tidbitmap.c.

{
    TIDBitmap  *tbm = iterator->tbm;
 
    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 */
            tbmres->blockno = chunk_blockno;
            tbmres->lossy = true;
            tbmres->recheck = true;
            tbmres->internal_page = NULL;
            iterator->schunkbit++;
            return true;
        }
    }
 
    if (iterator->spageptr < tbm->npages)
    {
        PagetableEntry *page;
 
        /* 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];
 
        tbmres->internal_page = page;
        tbmres->blockno = page->blockno;
        tbmres->lossy = false;
        tbmres->recheck = page->recheck;
        iterator->spageptr++;
        return true;
    }
 
    /* Nothing more in the bitmap */
    tbmres->blockno = InvalidBlockNumber;
    return false;
}

References Assert(), PagetableEntry::blockno, TBMIterateResult::blockno, TIDBitmap::entry1, TBMIterateResult::internal_page, InvalidBlockNumber, TIDBitmap::iterating, TBMIterateResult::lossy, TIDBitmap::nchunks, TIDBitmap::npages, PAGES_PER_CHUNK, PagetableEntry::recheck, TBMIterateResult::recheck, TBMPrivateIterator::schunkbit, TBMPrivateIterator::schunkptr, TIDBitmap::schunks, TBMPrivateIterator::spageptr, TIDBitmap::spages, TIDBitmap::status, TBMPrivateIterator::tbm, tbm_advance_schunkbit(), TBM_ITERATING_PRIVATE, and TBM_ONE_PAGE.

Referenced by entryGetItem(), and tbm_iterate().

◆ tbm_shared_comparator()

static int tbm_shared_comparator	(	const void *	left,
		const void *	right,
		void *	arg
	)

static

Definition at line 1439 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()

bool tbm_shared_iterate	(	TBMSharedIterator *	iterator,
		TBMIterateResult *	tbmres
	)

Definition at line 1054 of file tidbitmap.c.

{
    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 */
            tbmres->blockno = chunk_blockno;
            tbmres->lossy = true;
            tbmres->recheck = true;
            tbmres->internal_page = NULL;
            istate->schunkbit++;
 
            LWLockRelease(&istate->lock);
            return true;
        }
    }
 
    if (istate->spageptr < istate->npages)
    {
        PagetableEntry *page = &ptbase[idxpages[istate->spageptr]];
 
        tbmres->internal_page = page;
        tbmres->blockno = page->blockno;
        tbmres->lossy = false;
        tbmres->recheck = page->recheck;
        istate->spageptr++;
 
        LWLockRelease(&istate->lock);
 
        return true;
    }
 
    LWLockRelease(&istate->lock);
 
    /* Nothing more in the bitmap */
    tbmres->blockno = InvalidBlockNumber;
    return false;
}

References PagetableEntry::blockno, TBMIterateResult::blockno, PTIterationArray::index, TBMIterateResult::internal_page, InvalidBlockNumber, TBMSharedIteratorState::lock, TBMIterateResult::lossy, LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), TBMSharedIteratorState::nchunks, TBMSharedIteratorState::npages, PAGES_PER_CHUNK, TBMSharedIterator::ptbase, TBMSharedIterator::ptchunks, PTEntryArray::ptentry, TBMSharedIterator::ptpages, PagetableEntry::recheck, TBMIterateResult::recheck, TBMSharedIteratorState::schunkbit, TBMSharedIteratorState::schunkptr, TBMSharedIteratorState::spageptr, TBMSharedIterator::state, and tbm_advance_schunkbit().

Referenced by tbm_iterate().

◆ tbm_union()

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

Definition at line 447 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 470 of file tidbitmap.c.

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

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ BITNUM

◆ PAGES_PER_CHUNK

◆ SH_DECLARE

◆ SH_DEFINE

◆ SH_ELEMENT_TYPE

◆ SH_EQUAL

◆ SH_HASH_KEY

◆ SH_KEY

◆ SH_KEY_TYPE

◆ SH_PREFIX

◆ SH_SCOPE

◆ SH_USE_NONDEFAULT_ALLOCATOR

◆ WORDNUM

◆ WORDS_PER_CHUNK

◆ WORDS_PER_PAGE

Typedef Documentation

◆ PagetableEntry

◆ PTEntryArray

◆ PTIterationArray

◆ TBMSharedIteratorState

Enumeration Type Documentation

◆ TBMIteratingState

◆ TBMStatus

Function Documentation

◆ pagetable_allocate()

◆ pagetable_free()

◆ tbm_add_page()

◆ tbm_add_tuples()

◆ tbm_advance_schunkbit()

◆ tbm_attach_shared_iterate()

◆ tbm_begin_iterate()

◆ tbm_begin_private_iterate()

◆ tbm_calculate_entries()

◆ tbm_comparator()

◆ tbm_create()

◆ tbm_create_pagetable()

◆ tbm_end_iterate()

◆ tbm_end_private_iterate()

◆ tbm_end_shared_iterate()

◆ tbm_extract_page_tuple()

◆ tbm_find_pageentry()

◆ tbm_free()

◆ tbm_free_shared_area()

◆ tbm_get_pageentry()

◆ tbm_intersect()

◆ tbm_intersect_page()

◆ tbm_is_empty()

◆ tbm_iterate()

◆ tbm_lossify()

◆ tbm_mark_page_lossy()

◆ tbm_page_is_lossy()

◆ tbm_prepare_shared_iterate()

◆ tbm_private_iterate()

◆ tbm_shared_comparator()

◆ tbm_shared_iterate()

◆ tbm_union()

◆ tbm_union_page()