nbtdedup.c File Reference

#include "postgres.h"
#include "access/nbtree.h"
#include "access/nbtxlog.h"
#include "access/xloginsert.h"
#include "miscadmin.h"
#include "utils/rel.h"

Include dependency graph for nbtdedup.c:

Go to the source code of this file.

Functions
static void	_bt_bottomupdel_finish_pending (Page page, BTDedupState state, TM_IndexDeleteOp *delstate)
static bool	_bt_do_singleval (Relation rel, Page page, BTDedupState state, OffsetNumber minoff, IndexTuple newitem)
static void	_bt_singleval_fillfactor (Page page, BTDedupState state, Size newitemsz)
void	_bt_dedup_pass (Relation rel, Buffer buf, IndexTuple newitem, Size newitemsz, bool bottomupdedup)
bool	_bt_bottomupdel_pass (Relation rel, Buffer buf, Relation heapRel, Size newitemsz)
void	_bt_dedup_start_pending (BTDedupState state, IndexTuple base, OffsetNumber baseoff)
bool	_bt_dedup_save_htid (BTDedupState state, IndexTuple itup)
Size	_bt_dedup_finish_pending (Page newpage, BTDedupState state)
IndexTuple	_bt_form_posting (IndexTuple base, ItemPointer htids, int nhtids)
void	_bt_update_posting (BTVacuumPosting vacposting)
IndexTuple	_bt_swap_posting (IndexTuple newitem, IndexTuple oposting, int postingoff)

Function Documentation

_bt_bottomupdel_finish_pending()

static void _bt_bottomupdel_finish_pending ( Page  page, BTDedupState  state, TM_IndexDeleteOp *  delstate  )

static

Definition at line 648 of file nbtdedup.c.

{
    bool        dupinterval = (state->nitems > 1);
 
    Assert(state->nitems > 0);
    Assert(state->nitems <= state->nhtids);
    Assert(state->intervals[state->nintervals].baseoff == state->baseoff);
 
    for (int i = 0; i < state->nitems; i++)
    {
        OffsetNumber offnum = state->baseoff + i;
        ItemId      itemid = PageGetItemId(page, offnum);
        IndexTuple  itup = (IndexTuple) PageGetItem(page, itemid);
        TM_IndexDelete *ideltid = &delstate->deltids[delstate->ndeltids];
        TM_IndexStatus *istatus = &delstate->status[delstate->ndeltids];
 
        if (!BTreeTupleIsPosting(itup))
        {
            /* Simple case: A plain non-pivot tuple */
            ideltid->tid = itup->t_tid;
            ideltid->id = delstate->ndeltids;
            istatus->idxoffnum = offnum;
            istatus->knowndeletable = false;    /* for now */
            istatus->promising = dupinterval;   /* simple rule */
            istatus->freespace = ItemIdGetLength(itemid) + sizeof(ItemIdData);
 
            delstate->ndeltids++;
        }
        else
        {
            /*
             * Complicated case: A posting list tuple.
             *
             * We make the conservative assumption that there can only be at
             * most one affected logical row per posting list tuple.  There
             * will be at most one promising entry in deltids to represent
             * this presumed lone logical row.  Note that this isn't even
             * considered unless the posting list tuple is also in an interval
             * of duplicates -- this complicated rule is just a variant of the
             * simple rule used to decide if plain index tuples are promising.
             */
            int         nitem = BTreeTupleGetNPosting(itup);
            bool        firstpromising = false;
            bool        lastpromising = false;
 
            Assert(_bt_posting_valid(itup));
 
            if (dupinterval)
            {
                /*
                 * Complicated rule: either the first or last TID in the
                 * posting list gets marked promising (if any at all)
                 */
                BlockNumber minblocklist,
                            midblocklist,
                            maxblocklist;
                ItemPointer mintid,
                            midtid,
                            maxtid;
 
                mintid = BTreeTupleGetHeapTID(itup);
                midtid = BTreeTupleGetPostingN(itup, nitem / 2);
                maxtid = BTreeTupleGetMaxHeapTID(itup);
                minblocklist = ItemPointerGetBlockNumber(mintid);
                midblocklist = ItemPointerGetBlockNumber(midtid);
                maxblocklist = ItemPointerGetBlockNumber(maxtid);
 
                /* Only entry with predominant table block can be promising */
                firstpromising = (minblocklist == midblocklist);
                lastpromising = (!firstpromising &&
                                 midblocklist == maxblocklist);
            }
 
            for (int p = 0; p < nitem; p++)
            {
                ItemPointer htid = BTreeTupleGetPostingN(itup, p);
 
                ideltid->tid = *htid;
                ideltid->id = delstate->ndeltids;
                istatus->idxoffnum = offnum;
                istatus->knowndeletable = false;    /* for now */
                istatus->promising = false;
                if ((firstpromising && p == 0) ||
                    (lastpromising && p == nitem - 1))
                    istatus->promising = true;
                istatus->freespace = sizeof(ItemPointerData);   /* at worst */
 
                ideltid++;
                istatus++;
                delstate->ndeltids++;
            }
        }
    }
 
    if (dupinterval)
    {
        state->intervals[state->nintervals].nitems = state->nitems;
        state->nintervals++;
    }
 
    /* Reset state for next interval */
    state->nhtids = 0;
    state->nitems = 0;
    state->phystupsize = 0;
}

References Assert, BTreeTupleGetHeapTID(), BTreeTupleGetMaxHeapTID(), BTreeTupleGetNPosting(), BTreeTupleGetPostingN(), BTreeTupleIsPosting(), TM_IndexDeleteOp::deltids, TM_IndexStatus::freespace, i, TM_IndexDelete::id, TM_IndexStatus::idxoffnum, ItemIdGetLength, ItemPointerGetBlockNumber(), TM_IndexStatus::knowndeletable, TM_IndexDeleteOp::ndeltids, PageGetItem(), PageGetItemId(), TM_IndexStatus::promising, TM_IndexDeleteOp::status, IndexTupleData::t_tid, and TM_IndexDelete::tid.

Referenced by _bt_bottomupdel_pass().

_bt_bottomupdel_pass()

bool _bt_bottomupdel_pass	(	Relation	rel,
		Buffer	buf,
		Relation	heapRel,
		Size	newitemsz
	)

Definition at line 307 of file nbtdedup.c.

{
    OffsetNumber offnum,
                minoff,
                maxoff;
    Page        page = BufferGetPage(buf);
    BTPageOpaque opaque = BTPageGetOpaque(page);
    BTDedupState state;
    TM_IndexDeleteOp delstate;
    bool        neverdedup;
    int         nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
 
    /* Passed-in newitemsz is MAXALIGNED but does not include line pointer */
    newitemsz += sizeof(ItemIdData);
 
    /* Initialize deduplication state */
    state = (BTDedupState) palloc(sizeof(BTDedupStateData));
    state->deduplicate = true;
    state->nmaxitems = 0;
    state->maxpostingsize = BLCKSZ; /* We're not really deduplicating */
    state->base = NULL;
    state->baseoff = InvalidOffsetNumber;
    state->basetupsize = 0;
    state->htids = palloc(state->maxpostingsize);
    state->nhtids = 0;
    state->nitems = 0;
    state->phystupsize = 0;
    state->nintervals = 0;
 
    /*
     * Initialize tableam state that describes bottom-up index deletion
     * operation.
     *
     * We'll go on to ask the tableam to search for TIDs whose index tuples we
     * can safely delete.  The tableam will search until our leaf page space
     * target is satisfied, or until the cost of continuing with the tableam
     * operation seems too high.  It focuses its efforts on TIDs associated
     * with duplicate index tuples that we mark "promising".
     *
     * This space target is a little arbitrary.  The tableam must be able to
     * keep the costs and benefits in balance.  We provide the tableam with
     * exhaustive information about what might work, without directly
     * concerning ourselves with avoiding work during the tableam call.  Our
     * role in costing the bottom-up deletion process is strictly advisory.
     */
    delstate.irel = rel;
    delstate.iblknum = BufferGetBlockNumber(buf);
    delstate.bottomup = true;
    delstate.bottomupfreespace = Max(BLCKSZ / 16, newitemsz);
    delstate.ndeltids = 0;
    delstate.deltids = palloc(MaxTIDsPerBTreePage * sizeof(TM_IndexDelete));
    delstate.status = palloc(MaxTIDsPerBTreePage * sizeof(TM_IndexStatus));
 
    minoff = P_FIRSTDATAKEY(opaque);
    maxoff = PageGetMaxOffsetNumber(page);
    for (offnum = minoff;
         offnum <= maxoff;
         offnum = OffsetNumberNext(offnum))
    {
        ItemId      itemid = PageGetItemId(page, offnum);
        IndexTuple  itup = (IndexTuple) PageGetItem(page, itemid);
 
        Assert(!ItemIdIsDead(itemid));
 
        if (offnum == minoff)
        {
            /* itup starts first pending interval */
            _bt_dedup_start_pending(state, itup, offnum);
        }
        else if (_bt_keep_natts_fast(rel, state->base, itup) > nkeyatts &&
                 _bt_dedup_save_htid(state, itup))
        {
            /* Tuple is equal; just added its TIDs to pending interval */
        }
        else
        {
            /* Finalize interval -- move its TIDs to delete state */
            _bt_bottomupdel_finish_pending(page, state, &delstate);
 
            /* itup starts new pending interval */
            _bt_dedup_start_pending(state, itup, offnum);
        }
    }
    /* Finalize final interval -- move its TIDs to delete state */
    _bt_bottomupdel_finish_pending(page, state, &delstate);
 
    /*
     * We don't give up now in the event of having few (or even zero)
     * promising tuples for the tableam because it's not up to us as the index
     * AM to manage costs (note that the tableam might have heuristics of its
     * own that work out what to do).  We should at least avoid having our
     * caller do a useless deduplication pass after we return in the event of
     * zero promising tuples, though.
     */
    neverdedup = false;
    if (state->nintervals == 0)
        neverdedup = true;
 
    pfree(state->htids);
    pfree(state);
 
    /* Ask tableam which TIDs are deletable, then physically delete them */
    _bt_delitems_delete_check(rel, buf, heapRel, &delstate);
 
    pfree(delstate.deltids);
    pfree(delstate.status);
 
    /* Report "success" to caller unconditionally to avoid deduplication */
    if (neverdedup)
        return true;
 
    /* Don't dedup when we won't end up back here any time soon anyway */
    return PageGetExactFreeSpace(page) >= Max(BLCKSZ / 24, newitemsz);
}

References _bt_bottomupdel_finish_pending(), _bt_dedup_save_htid(), _bt_dedup_start_pending(), _bt_delitems_delete_check(), _bt_keep_natts_fast(), Assert, TM_IndexDeleteOp::bottomup, TM_IndexDeleteOp::bottomupfreespace, BTPageGetOpaque, buf, BufferGetBlockNumber(), BufferGetPage(), TM_IndexDeleteOp::deltids, TM_IndexDeleteOp::iblknum, IndexRelationGetNumberOfKeyAttributes, InvalidOffsetNumber, TM_IndexDeleteOp::irel, ItemIdIsDead, Max, MaxTIDsPerBTreePage, TM_IndexDeleteOp::ndeltids, OffsetNumberNext, P_FIRSTDATAKEY, PageGetExactFreeSpace(), PageGetItem(), PageGetItemId(), PageGetMaxOffsetNumber(), palloc(), pfree(), and TM_IndexDeleteOp::status.

Referenced by _bt_delete_or_dedup_one_page().

_bt_dedup_finish_pending()

Size _bt_dedup_finish_pending	(	Page	newpage,
		BTDedupState	state
	)

Definition at line 555 of file nbtdedup.c.

{
    OffsetNumber tupoff;
    Size        tuplesz;
    Size        spacesaving;
 
    Assert(state->nitems > 0);
    Assert(state->nitems <= state->nhtids);
    Assert(state->intervals[state->nintervals].baseoff == state->baseoff);
 
    tupoff = OffsetNumberNext(PageGetMaxOffsetNumber(newpage));
    if (state->nitems == 1)
    {
        /* Use original, unchanged base tuple */
        tuplesz = IndexTupleSize(state->base);
        Assert(tuplesz == MAXALIGN(IndexTupleSize(state->base)));
        Assert(tuplesz <= BTMaxItemSize(newpage));
        if (PageAddItem(newpage, (Item) state->base, tuplesz, tupoff,
                        false, false) == InvalidOffsetNumber)
            elog(ERROR, "deduplication failed to add tuple to page");
 
        spacesaving = 0;
    }
    else
    {
        IndexTuple  final;
 
        /* Form a tuple with a posting list */
        final = _bt_form_posting(state->base, state->htids, state->nhtids);
        tuplesz = IndexTupleSize(final);
        Assert(tuplesz <= state->maxpostingsize);
 
        /* Save final number of items for posting list */
        state->intervals[state->nintervals].nitems = state->nitems;
 
        Assert(tuplesz == MAXALIGN(IndexTupleSize(final)));
        Assert(tuplesz <= BTMaxItemSize(newpage));
        if (PageAddItem(newpage, (Item) final, tuplesz, tupoff, false,
                        false) == InvalidOffsetNumber)
            elog(ERROR, "deduplication failed to add tuple to page");
 
        pfree(final);
        spacesaving = state->phystupsize - (tuplesz + sizeof(ItemIdData));
        /* Increment nintervals, since we wrote a new posting list tuple */
        state->nintervals++;
        Assert(spacesaving > 0 && spacesaving < BLCKSZ);
    }
 
    /* Reset state for next pending posting list */
    state->nhtids = 0;
    state->nitems = 0;
    state->phystupsize = 0;
 
    return spacesaving;
}

References _bt_form_posting(), Assert, BTMaxItemSize, elog, ERROR, IndexTupleSize, InvalidOffsetNumber, MAXALIGN, OffsetNumberNext, PageAddItem, PageGetMaxOffsetNumber(), and pfree().

Referenced by _bt_dedup_pass(), and btree_xlog_dedup().

_bt_dedup_pass()

void _bt_dedup_pass	(	Relation	rel,
		Buffer	buf,
		IndexTuple	newitem,
		Size	newitemsz,
		bool	bottomupdedup
	)

Definition at line 58 of file nbtdedup.c.

{
    OffsetNumber offnum,
                minoff,
                maxoff;
    Page        page = BufferGetPage(buf);
    BTPageOpaque opaque = BTPageGetOpaque(page);
    Page        newpage;
    BTDedupState state;
    Size        pagesaving PG_USED_FOR_ASSERTS_ONLY = 0;
    bool        singlevalstrat = false;
    int         nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
 
    /* Passed-in newitemsz is MAXALIGNED but does not include line pointer */
    newitemsz += sizeof(ItemIdData);
 
    /*
     * Initialize deduplication state.
     *
     * It would be possible for maxpostingsize (limit on posting list tuple
     * size) to be set to one third of the page.  However, it seems like a
     * good idea to limit the size of posting lists to one sixth of a page.
     * That ought to leave us with a good split point when pages full of
     * duplicates can be split several times.
     */
    state = (BTDedupState) palloc(sizeof(BTDedupStateData));
    state->deduplicate = true;
    state->nmaxitems = 0;
    state->maxpostingsize = Min(BTMaxItemSize(page) / 2, INDEX_SIZE_MASK);
    /* Metadata about base tuple of current pending posting list */
    state->base = NULL;
    state->baseoff = InvalidOffsetNumber;
    state->basetupsize = 0;
    /* Metadata about current pending posting list TIDs */
    state->htids = palloc(state->maxpostingsize);
    state->nhtids = 0;
    state->nitems = 0;
    /* Size of all physical tuples to be replaced by pending posting list */
    state->phystupsize = 0;
    /* nintervals should be initialized to zero */
    state->nintervals = 0;
 
    minoff = P_FIRSTDATAKEY(opaque);
    maxoff = PageGetMaxOffsetNumber(page);
 
    /*
     * Consider applying "single value" strategy, though only if the page
     * seems likely to be split in the near future
     */
    if (!bottomupdedup)
        singlevalstrat = _bt_do_singleval(rel, page, state, minoff, newitem);
 
    /*
     * Deduplicate items from page, and write them to newpage.
     *
     * Copy the original page's LSN into newpage copy.  This will become the
     * updated version of the page.  We need this because XLogInsert will
     * examine the LSN and possibly dump it in a page image.
     */
    newpage = PageGetTempPageCopySpecial(page);
    PageSetLSN(newpage, PageGetLSN(page));
 
    /* Copy high key, if any */
    if (!P_RIGHTMOST(opaque))
    {
        ItemId      hitemid = PageGetItemId(page, P_HIKEY);
        Size        hitemsz = ItemIdGetLength(hitemid);
        IndexTuple  hitem = (IndexTuple) PageGetItem(page, hitemid);
 
        if (PageAddItem(newpage, (Item) hitem, hitemsz, P_HIKEY,
                        false, false) == InvalidOffsetNumber)
            elog(ERROR, "deduplication failed to add highkey");
    }
 
    for (offnum = minoff;
         offnum <= maxoff;
         offnum = OffsetNumberNext(offnum))
    {
        ItemId      itemid = PageGetItemId(page, offnum);
        IndexTuple  itup = (IndexTuple) PageGetItem(page, itemid);
 
        Assert(!ItemIdIsDead(itemid));
 
        if (offnum == minoff)
        {
            /*
             * No previous/base tuple for the data item -- use the data item
             * as base tuple of pending posting list
             */
            _bt_dedup_start_pending(state, itup, offnum);
        }
        else if (state->deduplicate &&
                 _bt_keep_natts_fast(rel, state->base, itup) > nkeyatts &&
                 _bt_dedup_save_htid(state, itup))
        {
            /*
             * Tuple is equal to base tuple of pending posting list.  Heap
             * TID(s) for itup have been saved in state.
             */
        }
        else
        {
            /*
             * Tuple is not equal to pending posting list tuple, or
             * _bt_dedup_save_htid() opted to not merge current item into
             * pending posting list for some other reason (e.g., adding more
             * TIDs would have caused posting list to exceed current
             * maxpostingsize).
             *
             * If state contains pending posting list with more than one item,
             * form new posting tuple and add it to our temp page (newpage).
             * Else add pending interval's base tuple to the temp page as-is.
             */
            pagesaving += _bt_dedup_finish_pending(newpage, state);
 
            if (singlevalstrat)
            {
                /*
                 * Single value strategy's extra steps.
                 *
                 * Lower maxpostingsize for sixth and final large posting list
                 * tuple at the point where 5 maxpostingsize-capped tuples
                 * have either been formed or observed.
                 *
                 * When a sixth maxpostingsize-capped item is formed/observed,
                 * stop merging together tuples altogether.  The few tuples
                 * that remain at the end of the page won't be merged together
                 * at all (at least not until after a future page split takes
                 * place, when this page's newly allocated right sibling page
                 * gets its first deduplication pass).
                 */
                if (state->nmaxitems == 5)
                    _bt_singleval_fillfactor(page, state, newitemsz);
                else if (state->nmaxitems == 6)
                {
                    state->deduplicate = false;
                    singlevalstrat = false; /* won't be back here */
                }
            }
 
            /* itup starts new pending posting list */
            _bt_dedup_start_pending(state, itup, offnum);
        }
    }
 
    /* Handle the last item */
    pagesaving += _bt_dedup_finish_pending(newpage, state);
 
    /*
     * If no items suitable for deduplication were found, newpage must be
     * exactly the same as the original page, so just return from function.
     *
     * We could determine whether or not to proceed on the basis the space
     * savings being sufficient to avoid an immediate page split instead.  We
     * don't do that because there is some small value in nbtsplitloc.c always
     * operating against a page that is fully deduplicated (apart from
     * newitem).  Besides, most of the cost has already been paid.
     */
    if (state->nintervals == 0)
    {
        /* cannot leak memory here */
        pfree(newpage);
        pfree(state->htids);
        pfree(state);
        return;
    }
 
    /*
     * By here, it's clear that deduplication will definitely go ahead.
     *
     * Clear the BTP_HAS_GARBAGE page flag.  The index must be a heapkeyspace
     * index, and as such we'll never pay attention to BTP_HAS_GARBAGE anyway.
     * But keep things tidy.
     */
    if (P_HAS_GARBAGE(opaque))
    {
        BTPageOpaque nopaque = BTPageGetOpaque(newpage);
 
        nopaque->btpo_flags &= ~BTP_HAS_GARBAGE;
    }
 
    START_CRIT_SECTION();
 
    PageRestoreTempPage(newpage, page);
    MarkBufferDirty(buf);
 
    /* XLOG stuff */
    if (RelationNeedsWAL(rel))
    {
        XLogRecPtr  recptr;
        xl_btree_dedup xlrec_dedup;
 
        xlrec_dedup.nintervals = state->nintervals;
 
        XLogBeginInsert();
        XLogRegisterBuffer(0, buf, REGBUF_STANDARD);
        XLogRegisterData((char *) &xlrec_dedup, SizeOfBtreeDedup);
 
        /*
         * The intervals array is not in the buffer, but pretend that it is.
         * When XLogInsert stores the whole buffer, the array need not be
         * stored too.
         */
        XLogRegisterBufData(0, (char *) state->intervals,
                            state->nintervals * sizeof(BTDedupInterval));
 
        recptr = XLogInsert(RM_BTREE_ID, XLOG_BTREE_DEDUP);
 
        PageSetLSN(page, recptr);
    }
 
    END_CRIT_SECTION();
 
    /* Local space accounting should agree with page accounting */
    Assert(pagesaving < newitemsz || PageGetExactFreeSpace(page) >= newitemsz);
 
    /* cannot leak memory here */
    pfree(state->htids);
    pfree(state);
}

References _bt_dedup_finish_pending(), _bt_dedup_save_htid(), _bt_dedup_start_pending(), _bt_do_singleval(), _bt_keep_natts_fast(), _bt_singleval_fillfactor(), Assert, BTMaxItemSize, BTPageGetOpaque, BTPageOpaqueData::btpo_flags, buf, BufferGetPage(), elog, END_CRIT_SECTION, ERROR, INDEX_SIZE_MASK, IndexRelationGetNumberOfKeyAttributes, InvalidOffsetNumber, ItemIdGetLength, ItemIdIsDead, MarkBufferDirty(), Min, xl_btree_dedup::nintervals, OffsetNumberNext, P_FIRSTDATAKEY, P_HAS_GARBAGE, P_HIKEY, P_RIGHTMOST, PageAddItem, PageGetExactFreeSpace(), PageGetItem(), PageGetItemId(), PageGetLSN(), PageGetMaxOffsetNumber(), PageGetTempPageCopySpecial(), PageRestoreTempPage(), PageSetLSN(), palloc(), pfree(), PG_USED_FOR_ASSERTS_ONLY, REGBUF_STANDARD, RelationNeedsWAL, SizeOfBtreeDedup, START_CRIT_SECTION, XLOG_BTREE_DEDUP, XLogBeginInsert(), XLogInsert(), XLogRegisterBufData(), XLogRegisterBuffer(), and XLogRegisterData().

Referenced by _bt_delete_or_dedup_one_page().

_bt_dedup_save_htid()

bool _bt_dedup_save_htid	(	BTDedupState	state,
		IndexTuple	itup
	)

Definition at line 484 of file nbtdedup.c.

{
    int         nhtids;
    ItemPointer htids;
    Size        mergedtupsz;
 
    Assert(!BTreeTupleIsPivot(itup));
 
    if (!BTreeTupleIsPosting(itup))
    {
        nhtids = 1;
        htids = &itup->t_tid;
    }
    else
    {
        nhtids = BTreeTupleGetNPosting(itup);
        htids = BTreeTupleGetPosting(itup);
    }
 
    /*
     * Don't append (have caller finish pending posting list as-is) if
     * appending heap TID(s) from itup would put us over maxpostingsize limit.
     *
     * This calculation needs to match the code used within _bt_form_posting()
     * for new posting list tuples.
     */
    mergedtupsz = MAXALIGN(state->basetupsize +
                           (state->nhtids + nhtids) * sizeof(ItemPointerData));
 
    if (mergedtupsz > state->maxpostingsize)
    {
        /*
         * Count this as an oversized item for single value strategy, though
         * only when there are 50 TIDs in the final posting list tuple.  This
         * limit (which is fairly arbitrary) avoids confusion about how many
         * 1/6 of a page tuples have been encountered/created by the current
         * deduplication pass.
         *
         * Note: We deliberately don't consider which deduplication pass
         * merged together tuples to create this item (could be a previous
         * deduplication pass, or current pass).  See _bt_do_singleval()
         * comments.
         */
        if (state->nhtids > 50)
            state->nmaxitems++;
 
        return false;
    }
 
    /*
     * Save heap TIDs to pending posting list tuple -- itup can be merged into
     * pending posting list
     */
    state->nitems++;
    memcpy(state->htids + state->nhtids, htids,
           sizeof(ItemPointerData) * nhtids);
    state->nhtids += nhtids;
    state->phystupsize += MAXALIGN(IndexTupleSize(itup)) + sizeof(ItemIdData);
 
    return true;
}

References Assert, BTreeTupleGetNPosting(), BTreeTupleGetPosting(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), IndexTupleSize, MAXALIGN, and IndexTupleData::t_tid.

Referenced by _bt_bottomupdel_pass(), _bt_dedup_pass(), _bt_load(), and btree_xlog_dedup().

_bt_dedup_start_pending()

void _bt_dedup_start_pending	(	BTDedupState	state,
		IndexTuple	base,
		OffsetNumber	baseoff
	)

Definition at line 433 of file nbtdedup.c.

{
    Assert(state->nhtids == 0);
    Assert(state->nitems == 0);
    Assert(!BTreeTupleIsPivot(base));
 
    /*
     * Copy heap TID(s) from new base tuple for new candidate posting list
     * into working state's array
     */
    if (!BTreeTupleIsPosting(base))
    {
        memcpy(state->htids, &base->t_tid, sizeof(ItemPointerData));
        state->nhtids = 1;
        state->basetupsize = IndexTupleSize(base);
    }
    else
    {
        int         nposting;
 
        nposting = BTreeTupleGetNPosting(base);
        memcpy(state->htids, BTreeTupleGetPosting(base),
               sizeof(ItemPointerData) * nposting);
        state->nhtids = nposting;
        /* basetupsize should not include existing posting list */
        state->basetupsize = BTreeTupleGetPostingOffset(base);
    }
 
    /*
     * Save new base tuple itself -- it'll be needed if we actually create a
     * new posting list from new pending posting list.
     *
     * Must maintain physical size of all existing tuples (including line
     * pointer overhead) so that we can calculate space savings on page.
     */
    state->nitems = 1;
    state->base = base;
    state->baseoff = baseoff;
    state->phystupsize = MAXALIGN(IndexTupleSize(base)) + sizeof(ItemIdData);
    /* Also save baseoff in pending state for interval */
    state->intervals[state->nintervals].baseoff = state->baseoff;
}

References Assert, BTreeTupleGetNPosting(), BTreeTupleGetPosting(), BTreeTupleGetPostingOffset(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), IndexTupleSize, MAXALIGN, and IndexTupleData::t_tid.

Referenced by _bt_bottomupdel_pass(), _bt_dedup_pass(), _bt_load(), and btree_xlog_dedup().

_bt_do_singleval()

static bool _bt_do_singleval ( Relation  rel, Page  page, BTDedupState  state, OffsetNumber  minoff, IndexTuple  newitem  )

static

Definition at line 782 of file nbtdedup.c.

{
    int         nkeyatts = IndexRelationGetNumberOfKeyAttributes(rel);
    ItemId      itemid;
    IndexTuple  itup;
 
    itemid = PageGetItemId(page, minoff);
    itup = (IndexTuple) PageGetItem(page, itemid);
 
    if (_bt_keep_natts_fast(rel, newitem, itup) > nkeyatts)
    {
        itemid = PageGetItemId(page, PageGetMaxOffsetNumber(page));
        itup = (IndexTuple) PageGetItem(page, itemid);
 
        if (_bt_keep_natts_fast(rel, newitem, itup) > nkeyatts)
            return true;
    }
 
    return false;
}

References _bt_keep_natts_fast(), IndexRelationGetNumberOfKeyAttributes, PageGetItem(), PageGetItemId(), and PageGetMaxOffsetNumber().

Referenced by _bt_dedup_pass().

_bt_form_posting()

IndexTuple _bt_form_posting	(	IndexTuple	base,
		ItemPointer	htids,
		int	nhtids
	)

Definition at line 864 of file nbtdedup.c.

{
    uint32      keysize,
                newsize;
    IndexTuple  itup;
 
    if (BTreeTupleIsPosting(base))
        keysize = BTreeTupleGetPostingOffset(base);
    else
        keysize = IndexTupleSize(base);
 
    Assert(!BTreeTupleIsPivot(base));
    Assert(nhtids > 0 && nhtids <= PG_UINT16_MAX);
    Assert(keysize == MAXALIGN(keysize));
 
    /* Determine final size of new tuple */
    if (nhtids > 1)
        newsize = MAXALIGN(keysize +
                           nhtids * sizeof(ItemPointerData));
    else
        newsize = keysize;
 
    Assert(newsize <= INDEX_SIZE_MASK);
    Assert(newsize == MAXALIGN(newsize));
 
    /* Allocate memory using palloc0() (matches index_form_tuple()) */
    itup = palloc0(newsize);
    memcpy(itup, base, keysize);
    itup->t_info &= ~INDEX_SIZE_MASK;
    itup->t_info |= newsize;
    if (nhtids > 1)
    {
        /* Form posting list tuple */
        BTreeTupleSetPosting(itup, nhtids, keysize);
        memcpy(BTreeTupleGetPosting(itup), htids,
               sizeof(ItemPointerData) * nhtids);
        Assert(_bt_posting_valid(itup));
    }
    else
    {
        /* Form standard non-pivot tuple */
        itup->t_info &= ~INDEX_ALT_TID_MASK;
        ItemPointerCopy(htids, &itup->t_tid);
        Assert(ItemPointerIsValid(&itup->t_tid));
    }
 
    return itup;
}

References Assert, BTreeTupleGetPosting(), BTreeTupleGetPostingOffset(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), BTreeTupleSetPosting(), INDEX_SIZE_MASK, IndexTupleSize, ItemPointerCopy(), ItemPointerIsValid(), MAXALIGN, palloc0(), PG_UINT16_MAX, IndexTupleData::t_info, and IndexTupleData::t_tid.

Referenced by _bt_dedup_finish_pending(), _bt_sort_dedup_finish_pending(), and bt_posting_plain_tuple().

_bt_singleval_fillfactor()

static void _bt_singleval_fillfactor ( Page  page, BTDedupState  state, Size  newitemsz  )

static

Definition at line 822 of file nbtdedup.c.

{
    Size        leftfree;
    int         reduction;
 
    /* This calculation needs to match nbtsplitloc.c */
    leftfree = PageGetPageSize(page) - SizeOfPageHeaderData -
        MAXALIGN(sizeof(BTPageOpaqueData));
    /* Subtract size of new high key (includes pivot heap TID space) */
    leftfree -= newitemsz + MAXALIGN(sizeof(ItemPointerData));
 
    /*
     * Reduce maxpostingsize by an amount equal to target free space on left
     * half of page
     */
    reduction = leftfree * ((100 - BTREE_SINGLEVAL_FILLFACTOR) / 100.0);
    if (state->maxpostingsize > reduction)
        state->maxpostingsize -= reduction;
    else
        state->maxpostingsize = 0;
}

References BTREE_SINGLEVAL_FILLFACTOR, MAXALIGN, PageGetPageSize(), and SizeOfPageHeaderData.

Referenced by _bt_dedup_pass().

_bt_swap_posting()

IndexTuple _bt_swap_posting	(	IndexTuple	newitem,
		IndexTuple	oposting,
		int	postingoff
	)

Definition at line 1022 of file nbtdedup.c.

{
    int         nhtids;
    char       *replacepos;
    char       *replaceposright;
    Size        nmovebytes;
    IndexTuple  nposting;
 
    nhtids = BTreeTupleGetNPosting(oposting);
    Assert(_bt_posting_valid(oposting));
 
    /*
     * The postingoff argument originated as a _bt_binsrch_posting() return
     * value.  It will be 0 in the event of corruption that makes a leaf page
     * contain a non-pivot tuple that's somehow identical to newitem (no two
     * non-pivot tuples should ever have the same TID).  This has been known
     * to happen in the field from time to time.
     *
     * Perform a basic sanity check to catch this case now.
     */
    if (!(postingoff > 0 && postingoff < nhtids))
        elog(ERROR, "posting list tuple with %d items cannot be split at offset %d",
             nhtids, postingoff);
 
    /*
     * Move item pointers in posting list to make a gap for the new item's
     * heap TID.  We shift TIDs one place to the right, losing original
     * rightmost TID. (nmovebytes must not include TIDs to the left of
     * postingoff, nor the existing rightmost/max TID that gets overwritten.)
     */
    nposting = CopyIndexTuple(oposting);
    replacepos = (char *) BTreeTupleGetPostingN(nposting, postingoff);
    replaceposright = (char *) BTreeTupleGetPostingN(nposting, postingoff + 1);
    nmovebytes = (nhtids - postingoff - 1) * sizeof(ItemPointerData);
    memmove(replaceposright, replacepos, nmovebytes);
 
    /* Fill the gap at postingoff with TID of new item (original new TID) */
    Assert(!BTreeTupleIsPivot(newitem) && !BTreeTupleIsPosting(newitem));
    ItemPointerCopy(&newitem->t_tid, (ItemPointer) replacepos);
 
    /* Now copy oposting's rightmost/max TID into new item (final new TID) */
    ItemPointerCopy(BTreeTupleGetMaxHeapTID(oposting), &newitem->t_tid);
 
    Assert(ItemPointerCompare(BTreeTupleGetMaxHeapTID(nposting),
                              BTreeTupleGetHeapTID(newitem)) < 0);
    Assert(_bt_posting_valid(nposting));
 
    return nposting;
}

References Assert, BTreeTupleGetHeapTID(), BTreeTupleGetMaxHeapTID(), BTreeTupleGetNPosting(), BTreeTupleGetPostingN(), BTreeTupleIsPivot(), BTreeTupleIsPosting(), CopyIndexTuple(), elog, ERROR, ItemPointerCompare(), ItemPointerCopy(), and IndexTupleData::t_tid.

Referenced by _bt_insertonpg(), btree_xlog_insert(), and btree_xlog_split().

_bt_update_posting()

void _bt_update_posting

(

BTVacuumPosting

vacposting

)

Definition at line 924 of file nbtdedup.c.

{
    IndexTuple  origtuple = vacposting->itup;
    uint32      keysize,
                newsize;
    IndexTuple  itup;
    int         nhtids;
    int         ui,
                d;
    ItemPointer htids;
 
    nhtids = BTreeTupleGetNPosting(origtuple) - vacposting->ndeletedtids;
 
    Assert(_bt_posting_valid(origtuple));
    Assert(nhtids > 0 && nhtids < BTreeTupleGetNPosting(origtuple));
 
    /*
     * Determine final size of new tuple.
     *
     * This calculation needs to match the code used within _bt_form_posting()
     * for new posting list tuples.  We avoid calling _bt_form_posting() here
     * to save ourselves a second memory allocation for a htids workspace.
     */
    keysize = BTreeTupleGetPostingOffset(origtuple);
    if (nhtids > 1)
        newsize = MAXALIGN(keysize +
                           nhtids * sizeof(ItemPointerData));
    else
        newsize = keysize;
 
    Assert(newsize <= INDEX_SIZE_MASK);
    Assert(newsize == MAXALIGN(newsize));
 
    /* Allocate memory using palloc0() (matches index_form_tuple()) */
    itup = palloc0(newsize);
    memcpy(itup, origtuple, keysize);
    itup->t_info &= ~INDEX_SIZE_MASK;
    itup->t_info |= newsize;
 
    if (nhtids > 1)
    {
        /* Form posting list tuple */
        BTreeTupleSetPosting(itup, nhtids, keysize);
        htids = BTreeTupleGetPosting(itup);
    }
    else
    {
        /* Form standard non-pivot tuple */
        itup->t_info &= ~INDEX_ALT_TID_MASK;
        htids = &itup->t_tid;
    }
 
    ui = 0;
    d = 0;
    for (int i = 0; i < BTreeTupleGetNPosting(origtuple); i++)
    {
        if (d < vacposting->ndeletedtids && vacposting->deletetids[d] == i)
        {
            d++;
            continue;
        }
        htids[ui++] = *BTreeTupleGetPostingN(origtuple, i);
    }
    Assert(ui == nhtids);
    Assert(d == vacposting->ndeletedtids);
    Assert(nhtids == 1 || _bt_posting_valid(itup));
    Assert(nhtids > 1 || ItemPointerIsValid(&itup->t_tid));
 
    /* vacposting arg's itup will now point to updated version */
    vacposting->itup = itup;
}

References Assert, BTreeTupleGetNPosting(), BTreeTupleGetPosting(), BTreeTupleGetPostingN(), BTreeTupleGetPostingOffset(), BTreeTupleSetPosting(), BTVacuumPostingData::deletetids, i, INDEX_SIZE_MASK, ItemPointerIsValid(), BTVacuumPostingData::itup, MAXALIGN, BTVacuumPostingData::ndeletedtids, palloc0(), IndexTupleData::t_info, and IndexTupleData::t_tid.

Referenced by _bt_delitems_update(), and btree_xlog_updates().