heapam_visibility.c

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * heapam_visibility.c
 *    Tuple visibility rules for tuples stored in heap.
 *
 * NOTE: all the HeapTupleSatisfies routines will update the tuple's
 * "hint" status bits if we see that the inserting or deleting transaction
 * has now committed or aborted (and it is safe to set the hint bits).
 * If the hint bits are changed, MarkBufferDirtyHint is called on
 * the passed-in buffer.  The caller must hold not only a pin, but at least
 * shared buffer content lock on the buffer containing the tuple.
 *
 * NOTE: When using a non-MVCC snapshot, we must check
 * TransactionIdIsInProgress (which looks in the PGPROC array) before
 * TransactionIdDidCommit (which look in pg_xact).  Otherwise we have a race
 * condition: we might decide that a just-committed transaction crashed,
 * because none of the tests succeed.  xact.c is careful to record
 * commit/abort in pg_xact before it unsets MyProc->xid in the PGPROC array.
 * That fixes that problem, but it also means there is a window where
 * TransactionIdIsInProgress and TransactionIdDidCommit will both return true.
 * If we check only TransactionIdDidCommit, we could consider a tuple
 * committed when a later GetSnapshotData call will still think the
 * originating transaction is in progress, which leads to application-level
 * inconsistency.  The upshot is that we gotta check TransactionIdIsInProgress
 * first in all code paths, except for a few cases where we are looking at
 * subtransactions of our own main transaction and so there can't be any race
 * condition.
 *
 * We can't use TransactionIdDidAbort here because it won't treat transactions
 * that were in progress during a crash as aborted.  We determine that
 * transactions aborted/crashed through process of elimination instead.
 *
 * When using an MVCC snapshot, we rely on XidInMVCCSnapshot rather than
 * TransactionIdIsInProgress, but the logic is otherwise the same: do not
 * check pg_xact until after deciding that the xact is no longer in progress.
 *
 *
 * Summary of visibility functions:
 *
 *   HeapTupleSatisfiesMVCC()
 *        visible to supplied snapshot, excludes current command
 *   HeapTupleSatisfiesUpdate()
 *        visible to instant snapshot, with user-supplied command
 *        counter and more complex result
 *   HeapTupleSatisfiesSelf()
 *        visible to instant snapshot and current command
 *   HeapTupleSatisfiesDirty()
 *        like HeapTupleSatisfiesSelf(), but includes open transactions
 *   HeapTupleSatisfiesVacuum()
 *        visible to any running transaction, used by VACUUM
 *   HeapTupleSatisfiesNonVacuumable()
 *        Snapshot-style API for HeapTupleSatisfiesVacuum
 *   HeapTupleSatisfiesToast()
 *        visible unless part of interrupted vacuum, used for TOAST
 *   HeapTupleSatisfiesAny()
 *        all tuples are visible
 *
 * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *    src/backend/access/heap/heapam_visibility.c
 *
 *-------------------------------------------------------------------------
 */
 
#include "postgres.h"
 
#include "access/heapam.h"
#include "access/htup_details.h"
#include "access/multixact.h"
#include "access/subtrans.h"
#include "access/tableam.h"
#include "access/transam.h"
#include "access/xact.h"
#include "access/xlog.h"
#include "storage/bufmgr.h"
#include "storage/procarray.h"
#include "utils/builtins.h"
#include "utils/combocid.h"
#include "utils/snapmgr.h"
 
 
/*
 * SetHintBits()
 *
 * Set commit/abort hint bits on a tuple, if appropriate at this time.
 *
 * It is only safe to set a transaction-committed hint bit if we know the
 * transaction's commit record is guaranteed to be flushed to disk before the
 * buffer, or if the table is temporary or unlogged and will be obliterated by
 * a crash anyway.  We cannot change the LSN of the page here, because we may
 * hold only a share lock on the buffer, so we can only use the LSN to
 * interlock this if the buffer's LSN already is newer than the commit LSN;
 * otherwise we have to just refrain from setting the hint bit until some
 * future re-examination of the tuple.
 *
 * We can always set hint bits when marking a transaction aborted.  (Some
 * code in heapam.c relies on that!)
 *
 * Also, if we are cleaning up HEAP_MOVED_IN or HEAP_MOVED_OFF entries, then
 * we can always set the hint bits, since pre-9.0 VACUUM FULL always used
 * synchronous commits and didn't move tuples that weren't previously
 * hinted.  (This is not known by this subroutine, but is applied by its
 * callers.)  Note: old-style VACUUM FULL is gone, but we have to keep this
 * module's support for MOVED_OFF/MOVED_IN flag bits for as long as we
 * support in-place update from pre-9.0 databases.
 *
 * Normal commits may be asynchronous, so for those we need to get the LSN
 * of the transaction and then check whether this is flushed.
 *
 * The caller should pass xid as the XID of the transaction to check, or
 * InvalidTransactionId if no check is needed.
 */
static inline void
SetHintBits(HeapTupleHeader tuple, Buffer buffer,
            uint16 infomask, TransactionId xid)
{
    if (TransactionIdIsValid(xid))
    {
        /* NB: xid must be known committed here! */
        XLogRecPtr  commitLSN = TransactionIdGetCommitLSN(xid);
 
        if (BufferIsPermanent(buffer) && XLogNeedsFlush(commitLSN) &&
            BufferGetLSNAtomic(buffer) < commitLSN)
        {
            /* not flushed and no LSN interlock, so don't set hint */
            return;
        }
    }
 
    tuple->t_infomask |= infomask;
    MarkBufferDirtyHint(buffer, true);
}
 
/*
 * HeapTupleSetHintBits --- exported version of SetHintBits()
 *
 * This must be separate because of C99's brain-dead notions about how to
 * implement inline functions.
 */
void
HeapTupleSetHintBits(HeapTupleHeader tuple, Buffer buffer,
                     uint16 infomask, TransactionId xid)
{
    SetHintBits(tuple, buffer, infomask, xid);
}
 
 
/*
 * HeapTupleSatisfiesSelf
 *      True iff heap tuple is valid "for itself".
 *
 * See SNAPSHOT_MVCC's definition for the intended behaviour.
 *
 * Note:
 *      Assumes heap tuple is valid.
 *
 * The satisfaction of "itself" requires the following:
 *
 * ((Xmin == my-transaction &&              the row was updated by the current transaction, and
 *      (Xmax is null                       it was not deleted
 *       [|| Xmax != my-transaction)])          [or it was deleted by another transaction]
 * ||
 *
 * (Xmin is committed &&                    the row was modified by a committed transaction, and
 *      (Xmax is null ||                    the row has not been deleted, or
 *          (Xmax != my-transaction &&          the row was deleted by another transaction
 *           Xmax is not committed)))           that has not been committed
 */
static bool
HeapTupleSatisfiesSelf(HeapTuple htup, Snapshot snapshot, Buffer buffer)
{
    HeapTupleHeader tuple = htup->t_data;
 
    Assert(ItemPointerIsValid(&htup->t_self));
    Assert(htup->t_tableOid != InvalidOid);
 
    if (!HeapTupleHeaderXminCommitted(tuple))
    {
        if (HeapTupleHeaderXminInvalid(tuple))
            return false;
 
        /* Used by pre-9.0 binary upgrades */
        if (tuple->t_infomask & HEAP_MOVED_OFF)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (TransactionIdIsCurrentTransactionId(xvac))
                return false;
            if (!TransactionIdIsInProgress(xvac))
            {
                if (TransactionIdDidCommit(xvac))
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return false;
                }
                SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                            InvalidTransactionId);
            }
        }
        /* Used by pre-9.0 binary upgrades */
        else if (tuple->t_infomask & HEAP_MOVED_IN)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (!TransactionIdIsCurrentTransactionId(xvac))
            {
                if (TransactionIdIsInProgress(xvac))
                    return false;
                if (TransactionIdDidCommit(xvac))
                    SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                                InvalidTransactionId);
                else
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return false;
                }
            }
        }
        else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tuple)))
        {
            if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid */
                return true;
 
            if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))    /* not deleter */
                return true;
 
            if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
            {
                TransactionId xmax;
 
                xmax = HeapTupleGetUpdateXid(tuple);
 
                /* not LOCKED_ONLY, so it has to have an xmax */
                Assert(TransactionIdIsValid(xmax));
 
                /* updating subtransaction must have aborted */
                if (!TransactionIdIsCurrentTransactionId(xmax))
                    return true;
                else
                    return false;
            }
 
            if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
            {
                /* deleting subtransaction must have aborted */
                SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                            InvalidTransactionId);
                return true;
            }
 
            return false;
        }
        else if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmin(tuple)))
            return false;
        else if (TransactionIdDidCommit(HeapTupleHeaderGetRawXmin(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        HeapTupleHeaderGetRawXmin(tuple));
        else
        {
            /* it must have aborted or crashed */
            SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                        InvalidTransactionId);
            return false;
        }
    }
 
    /* by here, the inserting transaction has committed */
 
    if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid or aborted */
        return true;
 
    if (tuple->t_infomask & HEAP_XMAX_COMMITTED)
    {
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return true;
        return false;           /* updated by other */
    }
 
    if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
    {
        TransactionId xmax;
 
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return true;
 
        xmax = HeapTupleGetUpdateXid(tuple);
 
        /* not LOCKED_ONLY, so it has to have an xmax */
        Assert(TransactionIdIsValid(xmax));
 
        if (TransactionIdIsCurrentTransactionId(xmax))
            return false;
        if (TransactionIdIsInProgress(xmax))
            return true;
        if (TransactionIdDidCommit(xmax))
            return false;
        /* it must have aborted or crashed */
        return true;
    }
 
    if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
    {
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return true;
        return false;
    }
 
    if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmax(tuple)))
        return true;
 
    if (!TransactionIdDidCommit(HeapTupleHeaderGetRawXmax(tuple)))
    {
        /* it must have aborted or crashed */
        SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                    InvalidTransactionId);
        return true;
    }
 
    /* xmax transaction committed */
 
    if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
    {
        SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                    InvalidTransactionId);
        return true;
    }
 
    SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
                HeapTupleHeaderGetRawXmax(tuple));
    return false;
}
 
/*
 * HeapTupleSatisfiesAny
 *      Dummy "satisfies" routine: any tuple satisfies SnapshotAny.
 */
static bool
HeapTupleSatisfiesAny(HeapTuple htup, Snapshot snapshot, Buffer buffer)
{
    return true;
}
 
/*
 * HeapTupleSatisfiesToast
 *      True iff heap tuple is valid as a TOAST row.
 *
 * See SNAPSHOT_TOAST's definition for the intended behaviour.
 *
 * This is a simplified version that only checks for VACUUM moving conditions.
 * It's appropriate for TOAST usage because TOAST really doesn't want to do
 * its own time qual checks; if you can see the main table row that contains
 * a TOAST reference, you should be able to see the TOASTed value.  However,
 * vacuuming a TOAST table is independent of the main table, and in case such
 * a vacuum fails partway through, we'd better do this much checking.
 *
 * Among other things, this means you can't do UPDATEs of rows in a TOAST
 * table.
 */
static bool
HeapTupleSatisfiesToast(HeapTuple htup, Snapshot snapshot,
                        Buffer buffer)
{
    HeapTupleHeader tuple = htup->t_data;
 
    Assert(ItemPointerIsValid(&htup->t_self));
    Assert(htup->t_tableOid != InvalidOid);
 
    if (!HeapTupleHeaderXminCommitted(tuple))
    {
        if (HeapTupleHeaderXminInvalid(tuple))
            return false;
 
        /* Used by pre-9.0 binary upgrades */
        if (tuple->t_infomask & HEAP_MOVED_OFF)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (TransactionIdIsCurrentTransactionId(xvac))
                return false;
            if (!TransactionIdIsInProgress(xvac))
            {
                if (TransactionIdDidCommit(xvac))
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return false;
                }
                SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                            InvalidTransactionId);
            }
        }
        /* Used by pre-9.0 binary upgrades */
        else if (tuple->t_infomask & HEAP_MOVED_IN)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (!TransactionIdIsCurrentTransactionId(xvac))
            {
                if (TransactionIdIsInProgress(xvac))
                    return false;
                if (TransactionIdDidCommit(xvac))
                    SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                                InvalidTransactionId);
                else
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return false;
                }
            }
        }
 
        /*
         * An invalid Xmin can be left behind by a speculative insertion that
         * is canceled by super-deleting the tuple.  This also applies to
         * TOAST tuples created during speculative insertion.
         */
        else if (!TransactionIdIsValid(HeapTupleHeaderGetXmin(tuple)))
            return false;
    }
 
    /* otherwise assume the tuple is valid for TOAST. */
    return true;
}
 
/*
 * HeapTupleSatisfiesUpdate
 *
 *  This function returns a more detailed result code than most of the
 *  functions in this file, since UPDATE needs to know more than "is it
 *  visible?".  It also allows for user-supplied CommandId rather than
 *  relying on CurrentCommandId.
 *
 *  The possible return codes are:
 *
 *  TM_Invisible: the tuple didn't exist at all when the scan started, e.g. it
 *  was created by a later CommandId.
 *
 *  TM_Ok: The tuple is valid and visible, so it may be updated.
 *
 *  TM_SelfModified: The tuple was updated by the current transaction, after
 *  the current scan started.
 *
 *  TM_Updated: The tuple was updated by a committed transaction (including
 *  the case where the tuple was moved into a different partition).
 *
 *  TM_Deleted: The tuple was deleted by a committed transaction.
 *
 *  TM_BeingModified: The tuple is being updated by an in-progress transaction
 *  other than the current transaction.  (Note: this includes the case where
 *  the tuple is share-locked by a MultiXact, even if the MultiXact includes
 *  the current transaction.  Callers that want to distinguish that case must
 *  test for it themselves.)
 */
TM_Result
HeapTupleSatisfiesUpdate(HeapTuple htup, CommandId curcid,
                         Buffer buffer)
{
    HeapTupleHeader tuple = htup->t_data;
 
    Assert(ItemPointerIsValid(&htup->t_self));
    Assert(htup->t_tableOid != InvalidOid);
 
    if (!HeapTupleHeaderXminCommitted(tuple))
    {
        if (HeapTupleHeaderXminInvalid(tuple))
            return TM_Invisible;
 
        /* Used by pre-9.0 binary upgrades */
        if (tuple->t_infomask & HEAP_MOVED_OFF)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (TransactionIdIsCurrentTransactionId(xvac))
                return TM_Invisible;
            if (!TransactionIdIsInProgress(xvac))
            {
                if (TransactionIdDidCommit(xvac))
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return TM_Invisible;
                }
                SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                            InvalidTransactionId);
            }
        }
        /* Used by pre-9.0 binary upgrades */
        else if (tuple->t_infomask & HEAP_MOVED_IN)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (!TransactionIdIsCurrentTransactionId(xvac))
            {
                if (TransactionIdIsInProgress(xvac))
                    return TM_Invisible;
                if (TransactionIdDidCommit(xvac))
                    SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                                InvalidTransactionId);
                else
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return TM_Invisible;
                }
            }
        }
        else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tuple)))
        {
            if (HeapTupleHeaderGetCmin(tuple) >= curcid)
                return TM_Invisible;    /* inserted after scan started */
 
            if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid */
                return TM_Ok;
 
            if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            {
                TransactionId xmax;
 
                xmax = HeapTupleHeaderGetRawXmax(tuple);
 
                /*
                 * Careful here: even though this tuple was created by our own
                 * transaction, it might be locked by other transactions, if
                 * the original version was key-share locked when we updated
                 * it.
                 */
 
                if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
                {
                    if (MultiXactIdIsRunning(xmax, true))
                        return TM_BeingModified;
                    else
                        return TM_Ok;
                }
 
                /*
                 * If the locker is gone, then there is nothing of interest
                 * left in this Xmax; otherwise, report the tuple as
                 * locked/updated.
                 */
                if (!TransactionIdIsInProgress(xmax))
                    return TM_Ok;
                return TM_BeingModified;
            }
 
            if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
            {
                TransactionId xmax;
 
                xmax = HeapTupleGetUpdateXid(tuple);
 
                /* not LOCKED_ONLY, so it has to have an xmax */
                Assert(TransactionIdIsValid(xmax));
 
                /* deleting subtransaction must have aborted */
                if (!TransactionIdIsCurrentTransactionId(xmax))
                {
                    if (MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple),
                                             false))
                        return TM_BeingModified;
                    return TM_Ok;
                }
                else
                {
                    if (HeapTupleHeaderGetCmax(tuple) >= curcid)
                        return TM_SelfModified; /* updated after scan started */
                    else
                        return TM_Invisible;    /* updated before scan started */
                }
            }
 
            if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
            {
                /* deleting subtransaction must have aborted */
                SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                            InvalidTransactionId);
                return TM_Ok;
            }
 
            if (HeapTupleHeaderGetCmax(tuple) >= curcid)
                return TM_SelfModified; /* updated after scan started */
            else
                return TM_Invisible;    /* updated before scan started */
        }
        else if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmin(tuple)))
            return TM_Invisible;
        else if (TransactionIdDidCommit(HeapTupleHeaderGetRawXmin(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        HeapTupleHeaderGetRawXmin(tuple));
        else
        {
            /* it must have aborted or crashed */
            SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                        InvalidTransactionId);
            return TM_Invisible;
        }
    }
 
    /* by here, the inserting transaction has committed */
 
    if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid or aborted */
        return TM_Ok;
 
    if (tuple->t_infomask & HEAP_XMAX_COMMITTED)
    {
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return TM_Ok;
        if (!ItemPointerEquals(&htup->t_self, &tuple->t_ctid))
            return TM_Updated;  /* updated by other */
        else
            return TM_Deleted;  /* deleted by other */
    }
 
    if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
    {
        TransactionId xmax;
 
        if (HEAP_LOCKED_UPGRADED(tuple->t_infomask))
            return TM_Ok;
 
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
        {
            if (MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple), true))
                return TM_BeingModified;
 
            SetHintBits(tuple, buffer, HEAP_XMAX_INVALID, InvalidTransactionId);
            return TM_Ok;
        }
 
        xmax = HeapTupleGetUpdateXid(tuple);
        if (!TransactionIdIsValid(xmax))
        {
            if (MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple), false))
                return TM_BeingModified;
        }
 
        /* not LOCKED_ONLY, so it has to have an xmax */
        Assert(TransactionIdIsValid(xmax));
 
        if (TransactionIdIsCurrentTransactionId(xmax))
        {
            if (HeapTupleHeaderGetCmax(tuple) >= curcid)
                return TM_SelfModified; /* updated after scan started */
            else
                return TM_Invisible;    /* updated before scan started */
        }
 
        if (MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple), false))
            return TM_BeingModified;
 
        if (TransactionIdDidCommit(xmax))
        {
            if (!ItemPointerEquals(&htup->t_self, &tuple->t_ctid))
                return TM_Updated;
            else
                return TM_Deleted;
        }
 
        /*
         * By here, the update in the Xmax is either aborted or crashed, but
         * what about the other members?
         */
 
        if (!MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple), false))
        {
            /*
             * There's no member, even just a locker, alive anymore, so we can
             * mark the Xmax as invalid.
             */
            SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                        InvalidTransactionId);
            return TM_Ok;
        }
        else
        {
            /* There are lockers running */
            return TM_BeingModified;
        }
    }
 
    if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
    {
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return TM_BeingModified;
        if (HeapTupleHeaderGetCmax(tuple) >= curcid)
            return TM_SelfModified; /* updated after scan started */
        else
            return TM_Invisible;    /* updated before scan started */
    }
 
    if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmax(tuple)))
        return TM_BeingModified;
 
    if (!TransactionIdDidCommit(HeapTupleHeaderGetRawXmax(tuple)))
    {
        /* it must have aborted or crashed */
        SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                    InvalidTransactionId);
        return TM_Ok;
    }
 
    /* xmax transaction committed */
 
    if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
    {
        SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                    InvalidTransactionId);
        return TM_Ok;
    }
 
    SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
                HeapTupleHeaderGetRawXmax(tuple));
    if (!ItemPointerEquals(&htup->t_self, &tuple->t_ctid))
        return TM_Updated;      /* updated by other */
    else
        return TM_Deleted;      /* deleted by other */
}
 
/*
 * HeapTupleSatisfiesDirty
 *      True iff heap tuple is valid including effects of open transactions.
 *
 * See SNAPSHOT_DIRTY's definition for the intended behaviour.
 *
 * This is essentially like HeapTupleSatisfiesSelf as far as effects of
 * the current transaction and committed/aborted xacts are concerned.
 * However, we also include the effects of other xacts still in progress.
 *
 * A special hack is that the passed-in snapshot struct is used as an
 * output argument to return the xids of concurrent xacts that affected the
 * tuple.  snapshot->xmin is set to the tuple's xmin if that is another
 * transaction that's still in progress; or to InvalidTransactionId if the
 * tuple's xmin is committed good, committed dead, or my own xact.
 * Similarly for snapshot->xmax and the tuple's xmax.  If the tuple was
 * inserted speculatively, meaning that the inserter might still back down
 * on the insertion without aborting the whole transaction, the associated
 * token is also returned in snapshot->speculativeToken.
 */
static bool
HeapTupleSatisfiesDirty(HeapTuple htup, Snapshot snapshot,
                        Buffer buffer)
{
    HeapTupleHeader tuple = htup->t_data;
 
    Assert(ItemPointerIsValid(&htup->t_self));
    Assert(htup->t_tableOid != InvalidOid);
 
    snapshot->xmin = snapshot->xmax = InvalidTransactionId;
    snapshot->speculativeToken = 0;
 
    if (!HeapTupleHeaderXminCommitted(tuple))
    {
        if (HeapTupleHeaderXminInvalid(tuple))
            return false;
 
        /* Used by pre-9.0 binary upgrades */
        if (tuple->t_infomask & HEAP_MOVED_OFF)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (TransactionIdIsCurrentTransactionId(xvac))
                return false;
            if (!TransactionIdIsInProgress(xvac))
            {
                if (TransactionIdDidCommit(xvac))
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return false;
                }
                SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                            InvalidTransactionId);
            }
        }
        /* Used by pre-9.0 binary upgrades */
        else if (tuple->t_infomask & HEAP_MOVED_IN)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (!TransactionIdIsCurrentTransactionId(xvac))
            {
                if (TransactionIdIsInProgress(xvac))
                    return false;
                if (TransactionIdDidCommit(xvac))
                    SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                                InvalidTransactionId);
                else
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return false;
                }
            }
        }
        else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tuple)))
        {
            if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid */
                return true;
 
            if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))    /* not deleter */
                return true;
 
            if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
            {
                TransactionId xmax;
 
                xmax = HeapTupleGetUpdateXid(tuple);
 
                /* not LOCKED_ONLY, so it has to have an xmax */
                Assert(TransactionIdIsValid(xmax));
 
                /* updating subtransaction must have aborted */
                if (!TransactionIdIsCurrentTransactionId(xmax))
                    return true;
                else
                    return false;
            }
 
            if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
            {
                /* deleting subtransaction must have aborted */
                SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                            InvalidTransactionId);
                return true;
            }
 
            return false;
        }
        else if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmin(tuple)))
        {
            /*
             * Return the speculative token to caller.  Caller can worry about
             * xmax, since it requires a conclusively locked row version, and
             * a concurrent update to this tuple is a conflict of its
             * purposes.
             */
            if (HeapTupleHeaderIsSpeculative(tuple))
            {
                snapshot->speculativeToken =
                    HeapTupleHeaderGetSpeculativeToken(tuple);
 
                Assert(snapshot->speculativeToken != 0);
            }
 
            snapshot->xmin = HeapTupleHeaderGetRawXmin(tuple);
            /* XXX shouldn't we fall through to look at xmax? */
            return true;        /* in insertion by other */
        }
        else if (TransactionIdDidCommit(HeapTupleHeaderGetRawXmin(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        HeapTupleHeaderGetRawXmin(tuple));
        else
        {
            /* it must have aborted or crashed */
            SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                        InvalidTransactionId);
            return false;
        }
    }
 
    /* by here, the inserting transaction has committed */
 
    if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid or aborted */
        return true;
 
    if (tuple->t_infomask & HEAP_XMAX_COMMITTED)
    {
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return true;
        return false;           /* updated by other */
    }
 
    if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
    {
        TransactionId xmax;
 
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return true;
 
        xmax = HeapTupleGetUpdateXid(tuple);
 
        /* not LOCKED_ONLY, so it has to have an xmax */
        Assert(TransactionIdIsValid(xmax));
 
        if (TransactionIdIsCurrentTransactionId(xmax))
            return false;
        if (TransactionIdIsInProgress(xmax))
        {
            snapshot->xmax = xmax;
            return true;
        }
        if (TransactionIdDidCommit(xmax))
            return false;
        /* it must have aborted or crashed */
        return true;
    }
 
    if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
    {
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return true;
        return false;
    }
 
    if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmax(tuple)))
    {
        if (!HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            snapshot->xmax = HeapTupleHeaderGetRawXmax(tuple);
        return true;
    }
 
    if (!TransactionIdDidCommit(HeapTupleHeaderGetRawXmax(tuple)))
    {
        /* it must have aborted or crashed */
        SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                    InvalidTransactionId);
        return true;
    }
 
    /* xmax transaction committed */
 
    if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
    {
        SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                    InvalidTransactionId);
        return true;
    }
 
    SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
                HeapTupleHeaderGetRawXmax(tuple));
    return false;               /* updated by other */
}
 
/*
 * HeapTupleSatisfiesMVCC
 *      True iff heap tuple is valid for the given MVCC snapshot.
 *
 * See SNAPSHOT_MVCC's definition for the intended behaviour.
 *
 * Notice that here, we will not update the tuple status hint bits if the
 * inserting/deleting transaction is still running according to our snapshot,
 * even if in reality it's committed or aborted by now.  This is intentional.
 * Checking the true transaction state would require access to high-traffic
 * shared data structures, creating contention we'd rather do without, and it
 * would not change the result of our visibility check anyway.  The hint bits
 * will be updated by the first visitor that has a snapshot new enough to see
 * the inserting/deleting transaction as done.  In the meantime, the cost of
 * leaving the hint bits unset is basically that each HeapTupleSatisfiesMVCC
 * call will need to run TransactionIdIsCurrentTransactionId in addition to
 * XidInMVCCSnapshot (but it would have to do the latter anyway).  In the old
 * coding where we tried to set the hint bits as soon as possible, we instead
 * did TransactionIdIsInProgress in each call --- to no avail, as long as the
 * inserting/deleting transaction was still running --- which was more cycles
 * and more contention on ProcArrayLock.
 */
static bool
HeapTupleSatisfiesMVCC(HeapTuple htup, Snapshot snapshot,
                       Buffer buffer)
{
    HeapTupleHeader tuple = htup->t_data;
 
    Assert(ItemPointerIsValid(&htup->t_self));
    Assert(htup->t_tableOid != InvalidOid);
 
    if (!HeapTupleHeaderXminCommitted(tuple))
    {
        if (HeapTupleHeaderXminInvalid(tuple))
            return false;
 
        /* Used by pre-9.0 binary upgrades */
        if (tuple->t_infomask & HEAP_MOVED_OFF)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (TransactionIdIsCurrentTransactionId(xvac))
                return false;
            if (!XidInMVCCSnapshot(xvac, snapshot))
            {
                if (TransactionIdDidCommit(xvac))
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return false;
                }
                SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                            InvalidTransactionId);
            }
        }
        /* Used by pre-9.0 binary upgrades */
        else if (tuple->t_infomask & HEAP_MOVED_IN)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (!TransactionIdIsCurrentTransactionId(xvac))
            {
                if (XidInMVCCSnapshot(xvac, snapshot))
                    return false;
                if (TransactionIdDidCommit(xvac))
                    SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                                InvalidTransactionId);
                else
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return false;
                }
            }
        }
        else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tuple)))
        {
            if (HeapTupleHeaderGetCmin(tuple) >= snapshot->curcid)
                return false;   /* inserted after scan started */
 
            if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid */
                return true;
 
            if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))    /* not deleter */
                return true;
 
            if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
            {
                TransactionId xmax;
 
                xmax = HeapTupleGetUpdateXid(tuple);
 
                /* not LOCKED_ONLY, so it has to have an xmax */
                Assert(TransactionIdIsValid(xmax));
 
                /* updating subtransaction must have aborted */
                if (!TransactionIdIsCurrentTransactionId(xmax))
                    return true;
                else if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
                    return true;    /* updated after scan started */
                else
                    return false;   /* updated before scan started */
            }
 
            if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
            {
                /* deleting subtransaction must have aborted */
                SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                            InvalidTransactionId);
                return true;
            }
 
            if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
                return true;    /* deleted after scan started */
            else
                return false;   /* deleted before scan started */
        }
        else if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmin(tuple), snapshot))
            return false;
        else if (TransactionIdDidCommit(HeapTupleHeaderGetRawXmin(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        HeapTupleHeaderGetRawXmin(tuple));
        else
        {
            /* it must have aborted or crashed */
            SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                        InvalidTransactionId);
            return false;
        }
    }
    else
    {
        /* xmin is committed, but maybe not according to our snapshot */
        if (!HeapTupleHeaderXminFrozen(tuple) &&
            XidInMVCCSnapshot(HeapTupleHeaderGetRawXmin(tuple), snapshot))
            return false;       /* treat as still in progress */
    }
 
    /* by here, the inserting transaction has committed */
 
    if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid or aborted */
        return true;
 
    if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
        return true;
 
    if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
    {
        TransactionId xmax;
 
        /* already checked above */
        Assert(!HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask));
 
        xmax = HeapTupleGetUpdateXid(tuple);
 
        /* not LOCKED_ONLY, so it has to have an xmax */
        Assert(TransactionIdIsValid(xmax));
 
        if (TransactionIdIsCurrentTransactionId(xmax))
        {
            if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
                return true;    /* deleted after scan started */
            else
                return false;   /* deleted before scan started */
        }
        if (XidInMVCCSnapshot(xmax, snapshot))
            return true;
        if (TransactionIdDidCommit(xmax))
            return false;       /* updating transaction committed */
        /* it must have aborted or crashed */
        return true;
    }
 
    if (!(tuple->t_infomask & HEAP_XMAX_COMMITTED))
    {
        if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
        {
            if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
                return true;    /* deleted after scan started */
            else
                return false;   /* deleted before scan started */
        }
 
        if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmax(tuple), snapshot))
            return true;
 
        if (!TransactionIdDidCommit(HeapTupleHeaderGetRawXmax(tuple)))
        {
            /* it must have aborted or crashed */
            SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                        InvalidTransactionId);
            return true;
        }
 
        /* xmax transaction committed */
        SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
                    HeapTupleHeaderGetRawXmax(tuple));
    }
    else
    {
        /* xmax is committed, but maybe not according to our snapshot */
        if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmax(tuple), snapshot))
            return true;        /* treat as still in progress */
    }
 
    /* xmax transaction committed */
 
    return false;
}
 
 
/*
 * HeapTupleSatisfiesVacuum
 *
 *  Determine the status of tuples for VACUUM purposes.  Here, what
 *  we mainly want to know is if a tuple is potentially visible to *any*
 *  running transaction.  If so, it can't be removed yet by VACUUM.
 *
 * OldestXmin is a cutoff XID (obtained from
 * GetOldestNonRemovableTransactionId()).  Tuples deleted by XIDs >=
 * OldestXmin are deemed "recently dead"; they might still be visible to some
 * open transaction, so we can't remove them, even if we see that the deleting
 * transaction has committed.
 */
HTSV_Result
HeapTupleSatisfiesVacuum(HeapTuple htup, TransactionId OldestXmin,
                         Buffer buffer)
{
    TransactionId dead_after = InvalidTransactionId;
    HTSV_Result res;
 
    res = HeapTupleSatisfiesVacuumHorizon(htup, buffer, &dead_after);
 
    if (res == HEAPTUPLE_RECENTLY_DEAD)
    {
        Assert(TransactionIdIsValid(dead_after));
 
        if (TransactionIdPrecedes(dead_after, OldestXmin))
            res = HEAPTUPLE_DEAD;
    }
    else
        Assert(!TransactionIdIsValid(dead_after));
 
    return res;
}
 
/*
 * Work horse for HeapTupleSatisfiesVacuum and similar routines.
 *
 * In contrast to HeapTupleSatisfiesVacuum this routine, when encountering a
 * tuple that could still be visible to some backend, stores the xid that
 * needs to be compared with the horizon in *dead_after, and returns
 * HEAPTUPLE_RECENTLY_DEAD. The caller then can perform the comparison with
 * the horizon.  This is e.g. useful when comparing with different horizons.
 *
 * Note: HEAPTUPLE_DEAD can still be returned here, e.g. if the inserting
 * transaction aborted.
 */
HTSV_Result
HeapTupleSatisfiesVacuumHorizon(HeapTuple htup, Buffer buffer, TransactionId *dead_after)
{
    HeapTupleHeader tuple = htup->t_data;
 
    Assert(ItemPointerIsValid(&htup->t_self));
    Assert(htup->t_tableOid != InvalidOid);
    Assert(dead_after != NULL);
 
    *dead_after = InvalidTransactionId;
 
    /*
     * Has inserting transaction committed?
     *
     * If the inserting transaction aborted, then the tuple was never visible
     * to any other transaction, so we can delete it immediately.
     */
    if (!HeapTupleHeaderXminCommitted(tuple))
    {
        if (HeapTupleHeaderXminInvalid(tuple))
            return HEAPTUPLE_DEAD;
        /* Used by pre-9.0 binary upgrades */
        else if (tuple->t_infomask & HEAP_MOVED_OFF)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (TransactionIdIsCurrentTransactionId(xvac))
                return HEAPTUPLE_DELETE_IN_PROGRESS;
            if (TransactionIdIsInProgress(xvac))
                return HEAPTUPLE_DELETE_IN_PROGRESS;
            if (TransactionIdDidCommit(xvac))
            {
                SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                            InvalidTransactionId);
                return HEAPTUPLE_DEAD;
            }
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        InvalidTransactionId);
        }
        /* Used by pre-9.0 binary upgrades */
        else if (tuple->t_infomask & HEAP_MOVED_IN)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);
 
            if (TransactionIdIsCurrentTransactionId(xvac))
                return HEAPTUPLE_INSERT_IN_PROGRESS;
            if (TransactionIdIsInProgress(xvac))
                return HEAPTUPLE_INSERT_IN_PROGRESS;
            if (TransactionIdDidCommit(xvac))
                SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                            InvalidTransactionId);
            else
            {
                SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                            InvalidTransactionId);
                return HEAPTUPLE_DEAD;
            }
        }
        else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmin(tuple)))
        {
            if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid */
                return HEAPTUPLE_INSERT_IN_PROGRESS;
            /* only locked? run infomask-only check first, for performance */
            if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask) ||
                HeapTupleHeaderIsOnlyLocked(tuple))
                return HEAPTUPLE_INSERT_IN_PROGRESS;
            /* inserted and then deleted by same xact */
            if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetUpdateXid(tuple)))
                return HEAPTUPLE_DELETE_IN_PROGRESS;
            /* deleting subtransaction must have aborted */
            return HEAPTUPLE_INSERT_IN_PROGRESS;
        }
        else if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmin(tuple)))
        {
            /*
             * It'd be possible to discern between INSERT/DELETE in progress
             * here by looking at xmax - but that doesn't seem beneficial for
             * the majority of callers and even detrimental for some. We'd
             * rather have callers look at/wait for xmin than xmax. It's
             * always correct to return INSERT_IN_PROGRESS because that's
             * what's happening from the view of other backends.
             */
            return HEAPTUPLE_INSERT_IN_PROGRESS;
        }
        else if (TransactionIdDidCommit(HeapTupleHeaderGetRawXmin(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        HeapTupleHeaderGetRawXmin(tuple));
        else
        {
            /*
             * Not in Progress, Not Committed, so either Aborted or crashed
             */
            SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                        InvalidTransactionId);
            return HEAPTUPLE_DEAD;
        }
 
        /*
         * At this point the xmin is known committed, but we might not have
         * been able to set the hint bit yet; so we can no longer Assert that
         * it's set.
         */
    }
 
    /*
     * Okay, the inserter committed, so it was good at some point.  Now what
     * about the deleting transaction?
     */
    if (tuple->t_infomask & HEAP_XMAX_INVALID)
        return HEAPTUPLE_LIVE;
 
    if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
    {
        /*
         * "Deleting" xact really only locked it, so the tuple is live in any
         * case.  However, we should make sure that either XMAX_COMMITTED or
         * XMAX_INVALID gets set once the xact is gone, to reduce the costs of
         * examining the tuple for future xacts.
         */
        if (!(tuple->t_infomask & HEAP_XMAX_COMMITTED))
        {
            if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
            {
                /*
                 * If it's a pre-pg_upgrade tuple, the multixact cannot
                 * possibly be running; otherwise have to check.
                 */
                if (!HEAP_LOCKED_UPGRADED(tuple->t_infomask) &&
                    MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple),
                                         true))
                    return HEAPTUPLE_LIVE;
                SetHintBits(tuple, buffer, HEAP_XMAX_INVALID, InvalidTransactionId);
            }
            else
            {
                if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmax(tuple)))
                    return HEAPTUPLE_LIVE;
                SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                            InvalidTransactionId);
            }
        }
 
        /*
         * We don't really care whether xmax did commit, abort or crash. We
         * know that xmax did lock the tuple, but it did not and will never
         * actually update it.
         */
 
        return HEAPTUPLE_LIVE;
    }
 
    if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
    {
        TransactionId xmax = HeapTupleGetUpdateXid(tuple);
 
        /* already checked above */
        Assert(!HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask));
 
        /* not LOCKED_ONLY, so it has to have an xmax */
        Assert(TransactionIdIsValid(xmax));
 
        if (TransactionIdIsInProgress(xmax))
            return HEAPTUPLE_DELETE_IN_PROGRESS;
        else if (TransactionIdDidCommit(xmax))
        {
            /*
             * The multixact might still be running due to lockers.  Need to
             * allow for pruning if below the xid horizon regardless --
             * otherwise we could end up with a tuple where the updater has to
             * be removed due to the horizon, but is not pruned away.  It's
             * not a problem to prune that tuple, because any remaining
             * lockers will also be present in newer tuple versions.
             */
            *dead_after = xmax;
            return HEAPTUPLE_RECENTLY_DEAD;
        }
        else if (!MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple), false))
        {
            /*
             * Not in Progress, Not Committed, so either Aborted or crashed.
             * Mark the Xmax as invalid.
             */
            SetHintBits(tuple, buffer, HEAP_XMAX_INVALID, InvalidTransactionId);
        }
 
        return HEAPTUPLE_LIVE;
    }
 
    if (!(tuple->t_infomask & HEAP_XMAX_COMMITTED))
    {
        if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmax(tuple)))
            return HEAPTUPLE_DELETE_IN_PROGRESS;
        else if (TransactionIdDidCommit(HeapTupleHeaderGetRawXmax(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
                        HeapTupleHeaderGetRawXmax(tuple));
        else
        {
            /*
             * Not in Progress, Not Committed, so either Aborted or crashed
             */
            SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                        InvalidTransactionId);
            return HEAPTUPLE_LIVE;
        }
 
        /*
         * At this point the xmax is known committed, but we might not have
         * been able to set the hint bit yet; so we can no longer Assert that
         * it's set.
         */
    }
 
    /*
     * Deleter committed, allow caller to check if it was recent enough that
     * some open transactions could still see the tuple.
     */
    *dead_after = HeapTupleHeaderGetRawXmax(tuple);
    return HEAPTUPLE_RECENTLY_DEAD;
}
 
 
/*
 * HeapTupleSatisfiesNonVacuumable
 *
 *  True if tuple might be visible to some transaction; false if it's
 *  surely dead to everyone, ie, vacuumable.
 *
 *  See SNAPSHOT_NON_VACUUMABLE's definition for the intended behaviour.
 *
 *  This is an interface to HeapTupleSatisfiesVacuum that's callable via
 *  HeapTupleSatisfiesSnapshot, so it can be used through a Snapshot.
 *  snapshot->vistest must have been set up with the horizon to use.
 */
static bool
HeapTupleSatisfiesNonVacuumable(HeapTuple htup, Snapshot snapshot,
                                Buffer buffer)
{
    TransactionId dead_after = InvalidTransactionId;
    HTSV_Result res;
 
    res = HeapTupleSatisfiesVacuumHorizon(htup, buffer, &dead_after);
 
    if (res == HEAPTUPLE_RECENTLY_DEAD)
    {
        Assert(TransactionIdIsValid(dead_after));
 
        if (GlobalVisTestIsRemovableXid(snapshot->vistest, dead_after))
            res = HEAPTUPLE_DEAD;
    }
    else
        Assert(!TransactionIdIsValid(dead_after));
 
    return res != HEAPTUPLE_DEAD;
}
 
 
/*
 * HeapTupleIsSurelyDead
 *
 *  Cheaply determine whether a tuple is surely dead to all onlookers.
 *  We sometimes use this in lieu of HeapTupleSatisfiesVacuum when the
 *  tuple has just been tested by another visibility routine (usually
 *  HeapTupleSatisfiesMVCC) and, therefore, any hint bits that can be set
 *  should already be set.  We assume that if no hint bits are set, the xmin
 *  or xmax transaction is still running.  This is therefore faster than
 *  HeapTupleSatisfiesVacuum, because we consult neither procarray nor CLOG.
 *  It's okay to return false when in doubt, but we must return true only
 *  if the tuple is removable.
 */
bool
HeapTupleIsSurelyDead(HeapTuple htup, GlobalVisState *vistest)
{
    HeapTupleHeader tuple = htup->t_data;
 
    Assert(ItemPointerIsValid(&htup->t_self));
    Assert(htup->t_tableOid != InvalidOid);
 
    /*
     * If the inserting transaction is marked invalid, then it aborted, and
     * the tuple is definitely dead.  If it's marked neither committed nor
     * invalid, then we assume it's still alive (since the presumption is that
     * all relevant hint bits were just set moments ago).
     */
    if (!HeapTupleHeaderXminCommitted(tuple))
        return HeapTupleHeaderXminInvalid(tuple);
 
    /*
     * If the inserting transaction committed, but any deleting transaction
     * aborted, the tuple is still alive.
     */
    if (tuple->t_infomask & HEAP_XMAX_INVALID)
        return false;
 
    /*
     * If the XMAX is just a lock, the tuple is still alive.
     */
    if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
        return false;
 
    /*
     * If the Xmax is a MultiXact, it might be dead or alive, but we cannot
     * know without checking pg_multixact.
     */
    if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
        return false;
 
    /* If deleter isn't known to have committed, assume it's still running. */
    if (!(tuple->t_infomask & HEAP_XMAX_COMMITTED))
        return false;
 
    /* Deleter committed, so tuple is dead if the XID is old enough. */
    return GlobalVisTestIsRemovableXid(vistest,
                                       HeapTupleHeaderGetRawXmax(tuple));
}
 
/*
 * Is the tuple really only locked?  That is, is it not updated?
 *
 * It's easy to check just infomask bits if the locker is not a multi; but
 * otherwise we need to verify that the updating transaction has not aborted.
 *
 * This function is here because it follows the same visibility rules laid out
 * at the top of this file.
 */
bool
HeapTupleHeaderIsOnlyLocked(HeapTupleHeader tuple)
{
    TransactionId xmax;
 
    /* if there's no valid Xmax, then there's obviously no update either */
    if (tuple->t_infomask & HEAP_XMAX_INVALID)
        return true;
 
    if (tuple->t_infomask & HEAP_XMAX_LOCK_ONLY)
        return true;
 
    /* invalid xmax means no update */
    if (!TransactionIdIsValid(HeapTupleHeaderGetRawXmax(tuple)))
        return true;
 
    /*
     * if HEAP_XMAX_LOCK_ONLY is not set and not a multi, then this must
     * necessarily have been updated
     */
    if (!(tuple->t_infomask & HEAP_XMAX_IS_MULTI))
        return false;
 
    /* ... but if it's a multi, then perhaps the updating Xid aborted. */
    xmax = HeapTupleGetUpdateXid(tuple);
 
    /* not LOCKED_ONLY, so it has to have an xmax */
    Assert(TransactionIdIsValid(xmax));
 
    if (TransactionIdIsCurrentTransactionId(xmax))
        return false;
    if (TransactionIdIsInProgress(xmax))
        return false;
    if (TransactionIdDidCommit(xmax))
        return false;
 
    /*
     * not current, not in progress, not committed -- must have aborted or
     * crashed
     */
    return true;
}
 
/*
 * check whether the transaction id 'xid' is in the pre-sorted array 'xip'.
 */
static bool
TransactionIdInArray(TransactionId xid, TransactionId *xip, Size num)
{
    return num > 0 &&
        bsearch(&xid, xip, num, sizeof(TransactionId), xidComparator) != NULL;
}
 
/*
 * See the comments for HeapTupleSatisfiesMVCC for the semantics this function
 * obeys.
 *
 * Only usable on tuples from catalog tables!
 *
 * We don't need to support HEAP_MOVED_(IN|OFF) for now because we only support
 * reading catalog pages which couldn't have been created in an older version.
 *
 * We don't set any hint bits in here as it seems unlikely to be beneficial as
 * those should already be set by normal access and it seems to be too
 * dangerous to do so as the semantics of doing so during timetravel are more
 * complicated than when dealing "only" with the present.
 */
static bool
HeapTupleSatisfiesHistoricMVCC(HeapTuple htup, Snapshot snapshot,
                               Buffer buffer)
{
    HeapTupleHeader tuple = htup->t_data;
    TransactionId xmin = HeapTupleHeaderGetXmin(tuple);
    TransactionId xmax = HeapTupleHeaderGetRawXmax(tuple);
 
    Assert(ItemPointerIsValid(&htup->t_self));
    Assert(htup->t_tableOid != InvalidOid);
 
    /* inserting transaction aborted */
    if (HeapTupleHeaderXminInvalid(tuple))
    {
        Assert(!TransactionIdDidCommit(xmin));
        return false;
    }
    /* check if it's one of our txids, toplevel is also in there */
    else if (TransactionIdInArray(xmin, snapshot->subxip, snapshot->subxcnt))
    {
        bool        resolved;
        CommandId   cmin = HeapTupleHeaderGetRawCommandId(tuple);
        CommandId   cmax = InvalidCommandId;
 
        /*
         * another transaction might have (tried to) delete this tuple or
         * cmin/cmax was stored in a combo CID. So we need to lookup the
         * actual values externally.
         */
        resolved = ResolveCminCmaxDuringDecoding(HistoricSnapshotGetTupleCids(), snapshot,
                                                 htup, buffer,
                                                 &cmin, &cmax);
 
        /*
         * If we haven't resolved the combo CID to cmin/cmax, that means we
         * have not decoded the combo CID yet. That means the cmin is
         * definitely in the future, and we're not supposed to see the tuple
         * yet.
         *
         * XXX This only applies to decoding of in-progress transactions. In
         * regular logical decoding we only execute this code at commit time,
         * at which point we should have seen all relevant combo CIDs. So
         * ideally, we should error out in this case but in practice, this
         * won't happen. If we are too worried about this then we can add an
         * elog inside ResolveCminCmaxDuringDecoding.
         *
         * XXX For the streaming case, we can track the largest combo CID
         * assigned, and error out based on this (when unable to resolve combo
         * CID below that observed maximum value).
         */
        if (!resolved)
            return false;
 
        Assert(cmin != InvalidCommandId);
 
        if (cmin >= snapshot->curcid)
            return false;       /* inserted after scan started */
        /* fall through */
    }
    /* committed before our xmin horizon. Do a normal visibility check. */
    else if (TransactionIdPrecedes(xmin, snapshot->xmin))
    {
        Assert(!(HeapTupleHeaderXminCommitted(tuple) &&
                 !TransactionIdDidCommit(xmin)));
 
        /* check for hint bit first, consult clog afterwards */
        if (!HeapTupleHeaderXminCommitted(tuple) &&
            !TransactionIdDidCommit(xmin))
            return false;
        /* fall through */
    }
    /* beyond our xmax horizon, i.e. invisible */
    else if (TransactionIdFollowsOrEquals(xmin, snapshot->xmax))
    {
        return false;
    }
    /* check if it's a committed transaction in [xmin, xmax) */
    else if (TransactionIdInArray(xmin, snapshot->xip, snapshot->xcnt))
    {
        /* fall through */
    }
 
    /*
     * none of the above, i.e. between [xmin, xmax) but hasn't committed. I.e.
     * invisible.
     */
    else
    {
        return false;
    }
 
    /* at this point we know xmin is visible, go on to check xmax */
 
    /* xid invalid or aborted */
    if (tuple->t_infomask & HEAP_XMAX_INVALID)
        return true;
    /* locked tuples are always visible */
    else if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
        return true;
 
    /*
     * We can see multis here if we're looking at user tables or if somebody
     * SELECT ... FOR SHARE/UPDATE a system table.
     */
    else if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
    {
        xmax = HeapTupleGetUpdateXid(tuple);
    }
 
    /* check if it's one of our txids, toplevel is also in there */
    if (TransactionIdInArray(xmax, snapshot->subxip, snapshot->subxcnt))
    {
        bool        resolved;
        CommandId   cmin;
        CommandId   cmax = HeapTupleHeaderGetRawCommandId(tuple);
 
        /* Lookup actual cmin/cmax values */
        resolved = ResolveCminCmaxDuringDecoding(HistoricSnapshotGetTupleCids(), snapshot,
                                                 htup, buffer,
                                                 &cmin, &cmax);
 
        /*
         * If we haven't resolved the combo CID to cmin/cmax, that means we
         * have not decoded the combo CID yet. That means the cmax is
         * definitely in the future, and we're still supposed to see the
         * tuple.
         *
         * XXX This only applies to decoding of in-progress transactions. In
         * regular logical decoding we only execute this code at commit time,
         * at which point we should have seen all relevant combo CIDs. So
         * ideally, we should error out in this case but in practice, this
         * won't happen. If we are too worried about this then we can add an
         * elog inside ResolveCminCmaxDuringDecoding.
         *
         * XXX For the streaming case, we can track the largest combo CID
         * assigned, and error out based on this (when unable to resolve combo
         * CID below that observed maximum value).
         */
        if (!resolved || cmax == InvalidCommandId)
            return true;
 
        if (cmax >= snapshot->curcid)
            return true;        /* deleted after scan started */
        else
            return false;       /* deleted before scan started */
    }
    /* below xmin horizon, normal transaction state is valid */
    else if (TransactionIdPrecedes(xmax, snapshot->xmin))
    {
        Assert(!(tuple->t_infomask & HEAP_XMAX_COMMITTED &&
                 !TransactionIdDidCommit(xmax)));
 
        /* check hint bit first */
        if (tuple->t_infomask & HEAP_XMAX_COMMITTED)
            return false;
 
        /* check clog */
        return !TransactionIdDidCommit(xmax);
    }
    /* above xmax horizon, we cannot possibly see the deleting transaction */
    else if (TransactionIdFollowsOrEquals(xmax, snapshot->xmax))
        return true;
    /* xmax is between [xmin, xmax), check known committed array */
    else if (TransactionIdInArray(xmax, snapshot->xip, snapshot->xcnt))
        return false;
    /* xmax is between [xmin, xmax), but known not to have committed yet */
    else
        return true;
}
 
/*
 * HeapTupleSatisfiesVisibility
 *      True iff heap tuple satisfies a time qual.
 *
 * Notes:
 *  Assumes heap tuple is valid, and buffer at least share locked.
 *
 *  Hint bits in the HeapTuple's t_infomask may be updated as a side effect;
 *  if so, the indicated buffer is marked dirty.
 */
bool
HeapTupleSatisfiesVisibility(HeapTuple htup, Snapshot snapshot, Buffer buffer)
{
    switch (snapshot->snapshot_type)
    {
        case SNAPSHOT_MVCC:
            return HeapTupleSatisfiesMVCC(htup, snapshot, buffer);
        case SNAPSHOT_SELF:
            return HeapTupleSatisfiesSelf(htup, snapshot, buffer);
        case SNAPSHOT_ANY:
            return HeapTupleSatisfiesAny(htup, snapshot, buffer);
        case SNAPSHOT_TOAST:
            return HeapTupleSatisfiesToast(htup, snapshot, buffer);
        case SNAPSHOT_DIRTY:
            return HeapTupleSatisfiesDirty(htup, snapshot, buffer);
        case SNAPSHOT_HISTORIC_MVCC:
            return HeapTupleSatisfiesHistoricMVCC(htup, snapshot, buffer);
        case SNAPSHOT_NON_VACUUMABLE:
            return HeapTupleSatisfiesNonVacuumable(htup, snapshot, buffer);
    }
 
    return false;               /* keep compiler quiet */
}