tqual.c

Go to the documentation of this file.

/*-------------------------------------------------------------------------
 *
 * tqual.c
 *    POSTGRES "time qualification" code, ie, tuple visibility rules.
 *
 * 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: must check TransactionIdIsInProgress (which looks in PGXACT array)
 * before TransactionIdDidCommit/TransactionIdDidAbort (which look in
 * pg_clog).  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_clog before it unsets
 * MyPgXact->xid in PGXACT 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.
 *
 * Summary of visibility functions:
 *
 *   HeapTupleSatisfiesMVCC()
 *        visible to supplied snapshot, excludes current command
 *   HeapTupleSatisfiesNow()
 *        visible to instant snapshot, excludes current command
 *   HeapTupleSatisfiesUpdate()
 *        like HeapTupleSatisfiesNow(), but 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
 *   HeapTupleSatisfiesToast()
 *        visible unless part of interrupted vacuum, used for TOAST
 *   HeapTupleSatisfiesAny()
 *        all tuples are visible
 *
 * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *    src/backend/utils/time/tqual.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/htup_details.h"
#include "access/multixact.h"
#include "access/subtrans.h"
#include "access/transam.h"
#include "access/xact.h"
#include "storage/bufmgr.h"
#include "storage/procarray.h"
#include "utils/tqual.h"


/* Static variables representing various special snapshot semantics */
SnapshotData SnapshotNowData = {HeapTupleSatisfiesNow};
SnapshotData SnapshotSelfData = {HeapTupleSatisfiesSelf};
SnapshotData SnapshotAnyData = {HeapTupleSatisfiesAny};
SnapshotData SnapshotToastData = {HeapTupleSatisfiesToast};

/* local functions */
static bool XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot);


/*
 * 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 has been flushed to disk, 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't use the LSN to interlock this; 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 (XLogNeedsFlush(commitLSN) && BufferIsPermanent(buffer))
            return;             /* not flushed yet, so don't set hint */
    }

    tuple->t_infomask |= infomask;
    MarkBufferDirtyHint(buffer);
}

/*
 * 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".
 *
 *  Here, we consider the effects of:
 *      all committed transactions (as of the current instant)
 *      previous commands of this transaction
 *      changes made by the current command
 *
 * 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
 */
bool
HeapTupleSatisfiesSelf(HeapTupleHeader tuple, Snapshot snapshot, Buffer buffer)
{
    if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
    {
        if (tuple->t_infomask & HEAP_XMIN_INVALID)
            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(HeapTupleHeaderGetXmin(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);
                if (!TransactionIdIsValid(xmax))
                    return true;

                /* 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(HeapTupleHeaderGetXmin(tuple)))
            return false;
        else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        HeapTupleHeaderGetXmin(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);
        if (!TransactionIdIsValid(xmax))
            return true;
        if (TransactionIdIsCurrentTransactionId(xmax))
            return false;
        if (TransactionIdIsInProgress(xmax))
            return true;
        if (TransactionIdDidCommit(xmax))
            return false;
        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;
}

/*
 * HeapTupleSatisfiesNow
 *      True iff heap tuple is valid "now".
 *
 *  Here, we consider the effects of:
 *      all committed transactions (as of the current instant)
 *      previous commands of this transaction
 *
 * Note we do _not_ include changes made by the current command.  This
 * solves the "Halloween problem" wherein an UPDATE might try to re-update
 * its own output tuples, http://en.wikipedia.org/wiki/Halloween_Problem.
 *
 * Note:
 *      Assumes heap tuple is valid.
 *
 * The satisfaction of "now" requires the following:
 *
 * ((Xmin == my-transaction &&              inserted by the current transaction
 *   Cmin < my-command &&                   before this command, and
 *   (Xmax is null ||                       the row has not been deleted, or
 *    (Xmax == my-transaction &&            it was deleted by the current transaction
 *     Cmax >= my-command)))                but not before this command,
 * ||                                       or
 *  (Xmin is committed &&                   the row was inserted by a committed transaction, and
 *      (Xmax is null ||                    the row has not been deleted, or
 *       (Xmax == my-transaction &&         the row is being deleted by this transaction
 *        Cmax >= my-command) ||            but it's not deleted "yet", or
 *       (Xmax != my-transaction &&         the row was deleted by another transaction
 *        Xmax is not committed))))         that has not been committed
 *
 */
bool
HeapTupleSatisfiesNow(HeapTupleHeader tuple, Snapshot snapshot, Buffer buffer)
{
    if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
    {
        if (tuple->t_infomask & HEAP_XMIN_INVALID)
            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(HeapTupleHeaderGetXmin(tuple)))
        {
            if (HeapTupleHeaderGetCmin(tuple) >= GetCurrentCommandId(false))
                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);
                if (!TransactionIdIsValid(xmax))
                    return true;

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

            if (HeapTupleHeaderGetCmax(tuple) >= GetCurrentCommandId(false))
                return true;    /* deleted after scan started */
            else
                return false;   /* deleted before scan started */
        }
        else if (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
            return false;
        else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        HeapTupleHeaderGetXmin(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;
    }

    if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
    {
        TransactionId   xmax;

        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return true;

        xmax = HeapTupleGetUpdateXid(tuple);
        if (!TransactionIdIsValid(xmax))
            return true;
        if (TransactionIdIsCurrentTransactionId(xmax))
        {
            if (HeapTupleHeaderGetCmax(tuple) >= GetCurrentCommandId(false))
                return true;    /* deleted after scan started */
            else
                return false;   /* deleted before scan started */
        }
        if (TransactionIdIsInProgress(xmax))
            return true;
        if (TransactionIdDidCommit(xmax))
            return false;
        return true;
    }

    if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
    {
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return true;
        if (HeapTupleHeaderGetCmax(tuple) >= GetCurrentCommandId(false))
            return true;        /* deleted after scan started */
        else
            return false;       /* deleted before scan started */
    }

    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.
 */
bool
HeapTupleSatisfiesAny(HeapTupleHeader tuple, Snapshot snapshot, Buffer buffer)
{
    return true;
}

/*
 * HeapTupleSatisfiesToast
 *      True iff heap tuple is valid as a TOAST row.
 *
 * 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.
 */
bool
HeapTupleSatisfiesToast(HeapTupleHeader tuple, Snapshot snapshot,
                        Buffer buffer)
{
    if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
    {
        if (tuple->t_infomask & HEAP_XMIN_INVALID)
            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;
                }
            }
        }
    }

    /* otherwise assume the tuple is valid for TOAST. */
    return true;
}

/*
 * HeapTupleSatisfiesUpdate
 *
 *  Same logic as HeapTupleSatisfiesNow, but returns a more detailed result
 *  code, since UPDATE needs to know more than "is it visible?".  Also,
 *  tuples of my own xact are tested against the passed CommandId not
 *  CurrentCommandId.
 *
 *  The possible return codes are:
 *
 *  HeapTupleInvisible: the tuple didn't exist at all when the scan started,
 *  e.g. it was created by a later CommandId.
 *
 *  HeapTupleMayBeUpdated: The tuple is valid and visible, so it may be
 *  updated.
 *
 *  HeapTupleSelfUpdated: The tuple was updated by the current transaction,
 *  after the current scan started.
 *
 *  HeapTupleUpdated: The tuple was updated by a committed transaction.
 *
 *  HeapTupleBeingUpdated: 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.)
 */
HTSU_Result
HeapTupleSatisfiesUpdate(HeapTupleHeader tuple, CommandId curcid,
                         Buffer buffer)
{
    if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
    {
        if (tuple->t_infomask & HEAP_XMIN_INVALID)
            return HeapTupleInvisible;

        /* Used by pre-9.0 binary upgrades */
        if (tuple->t_infomask & HEAP_MOVED_OFF)
        {
            TransactionId xvac = HeapTupleHeaderGetXvac(tuple);

            if (TransactionIdIsCurrentTransactionId(xvac))
                return HeapTupleInvisible;
            if (!TransactionIdIsInProgress(xvac))
            {
                if (TransactionIdDidCommit(xvac))
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return HeapTupleInvisible;
                }
                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 HeapTupleInvisible;
                if (TransactionIdDidCommit(xvac))
                    SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                                InvalidTransactionId);
                else
                {
                    SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                                InvalidTransactionId);
                    return HeapTupleInvisible;
                }
            }
        }
        else if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetXmin(tuple)))
        {
            if (HeapTupleHeaderGetCmin(tuple) >= curcid)
                return HeapTupleInvisible;      /* inserted after scan started */

            if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid */
                return HeapTupleMayBeUpdated;

            if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))         /* not deleter */
                return HeapTupleMayBeUpdated;

            if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
            {
                TransactionId   xmax;

                xmax = HeapTupleGetUpdateXid(tuple);
                if (!TransactionIdIsValid(xmax))
                    return HeapTupleMayBeUpdated;

                /* updating subtransaction must have aborted */
                if (!TransactionIdIsCurrentTransactionId(xmax))
                    return HeapTupleMayBeUpdated;
                else
                {
                    if (HeapTupleHeaderGetCmax(tuple) >= curcid)
                        return HeapTupleSelfUpdated;    /* updated after scan started */
                    else
                        return HeapTupleInvisible;  /* updated before scan started */
                }
            }

            if (!TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
            {
                /* deleting subtransaction must have aborted */
                SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                            InvalidTransactionId);
                return HeapTupleMayBeUpdated;
            }

            if (HeapTupleHeaderGetCmax(tuple) >= curcid)
                return HeapTupleSelfUpdated;    /* updated after scan started */
            else
                return HeapTupleInvisible;      /* updated before scan started */
        }
        else if (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
            return HeapTupleInvisible;
        else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        HeapTupleHeaderGetXmin(tuple));
        else
        {
            /* it must have aborted or crashed */
            SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                        InvalidTransactionId);
            return HeapTupleInvisible;
        }
    }

    /* by here, the inserting transaction has committed */

    if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid or aborted */
        return HeapTupleMayBeUpdated;

    if (tuple->t_infomask & HEAP_XMAX_COMMITTED)
    {
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return HeapTupleMayBeUpdated;
        return HeapTupleUpdated;    /* updated by other */
    }

    if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
    {
        TransactionId   xmax;

        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
        {
            /*
             * If it's only locked but neither EXCL_LOCK nor KEYSHR_LOCK
             * is set, it cannot possibly be running.  Otherwise need to
             * check.
             */
            if ((tuple->t_infomask & (HEAP_XMAX_EXCL_LOCK |
                                      HEAP_XMAX_KEYSHR_LOCK)) &&
                MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple)))
                return HeapTupleBeingUpdated;

            SetHintBits(tuple, buffer, HEAP_XMAX_INVALID, InvalidTransactionId);
            return HeapTupleMayBeUpdated;
        }

        xmax = HeapTupleGetUpdateXid(tuple);
        if (!TransactionIdIsValid(xmax))
        {
            if (MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple)))
                return HeapTupleBeingUpdated;

            SetHintBits(tuple, buffer, HEAP_XMAX_INVALID, InvalidTransactionId);
            return HeapTupleMayBeUpdated;
        }

        if (TransactionIdIsCurrentTransactionId(xmax))
        {
            if (HeapTupleHeaderGetCmax(tuple) >= curcid)
                return HeapTupleSelfUpdated;        /* updated after scan started */
            else
                return HeapTupleInvisible;  /* updated before scan started */
        }

        if (MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple)))
            return HeapTupleBeingUpdated;

        if (TransactionIdDidCommit(xmax))
            return HeapTupleUpdated;
        /* it must have aborted or crashed */
        SetHintBits(tuple, buffer, HEAP_XMAX_INVALID, InvalidTransactionId);
        return HeapTupleMayBeUpdated;
    }

    if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
    {
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return HeapTupleMayBeUpdated;
        if (HeapTupleHeaderGetCmax(tuple) >= curcid)
            return HeapTupleSelfUpdated;        /* updated after scan started */
        else
            return HeapTupleInvisible;  /* updated before scan started */
    }

    if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmax(tuple)))
        return HeapTupleBeingUpdated;

    if (!TransactionIdDidCommit(HeapTupleHeaderGetRawXmax(tuple)))
    {
        /* it must have aborted or crashed */
        SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                    InvalidTransactionId);
        return HeapTupleMayBeUpdated;
    }

    /* xmax transaction committed */

    if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
    {
        SetHintBits(tuple, buffer, HEAP_XMAX_INVALID,
                    InvalidTransactionId);
        return HeapTupleMayBeUpdated;
    }

    SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
                HeapTupleHeaderGetRawXmax(tuple));
    return HeapTupleUpdated;    /* updated by other */
}

/*
 * HeapTupleSatisfiesDirty
 *      True iff heap tuple is valid including effects of open transactions.
 *
 *  Here, we consider the effects of:
 *      all committed and in-progress transactions (as of the current instant)
 *      previous commands of this transaction
 *      changes made by the current command
 *
 * 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.
 */
bool
HeapTupleSatisfiesDirty(HeapTupleHeader tuple, Snapshot snapshot,
                        Buffer buffer)
{
    snapshot->xmin = snapshot->xmax = InvalidTransactionId;

    if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
    {
        if (tuple->t_infomask & HEAP_XMIN_INVALID)
            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(HeapTupleHeaderGetXmin(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);
                if (!TransactionIdIsValid(xmax))
                    return true;

                /* 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(HeapTupleHeaderGetXmin(tuple)))
        {
            snapshot->xmin = HeapTupleHeaderGetXmin(tuple);
            /* XXX shouldn't we fall through to look at xmax? */
            return true;        /* in insertion by other */
        }
        else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        HeapTupleHeaderGetXmin(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);
        if (!TransactionIdIsValid(xmax))
            return true;
        if (TransactionIdIsCurrentTransactionId(xmax))
            return false;
        if (TransactionIdIsInProgress(xmax))
        {
            snapshot->xmax = xmax;
            return true;
        }
        if (TransactionIdDidCommit(xmax))
            return false;
        return true;
    }

    if (TransactionIdIsCurrentTransactionId(HeapTupleHeaderGetRawXmax(tuple)))
    {
        if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
            return true;
        return false;
    }

    if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmax(tuple)))
    {
        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.
 *
 *  Here, we consider the effects of:
 *      all transactions committed as of the time of the given snapshot
 *      previous commands of this transaction
 *
 *  Does _not_ include:
 *      transactions shown as in-progress by the snapshot
 *      transactions started after the snapshot was taken
 *      changes made by the current command
 *
 * This is the same as HeapTupleSatisfiesNow, except that transactions that
 * were in progress or as yet unstarted when the snapshot was taken will
 * be treated as uncommitted, even if they have committed by now.
 *
 * (Notice, however, that the tuple status hint bits will be updated on the
 * basis of the true state of the transaction, even if we then pretend we
 * can't see it.)
 */
bool
HeapTupleSatisfiesMVCC(HeapTupleHeader tuple, Snapshot snapshot,
                       Buffer buffer)
{
    if (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
    {
        if (tuple->t_infomask & HEAP_XMIN_INVALID)
            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(HeapTupleHeaderGetXmin(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);
                if (!TransactionIdIsValid(xmax))
                    return true;

                /* 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 (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
            return false;
        else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        HeapTupleHeaderGetXmin(tuple));
        else
        {
            /* it must have aborted or crashed */
            SetHintBits(tuple, buffer, HEAP_XMIN_INVALID,
                        InvalidTransactionId);
            return false;
        }
    }

    /*
     * By here, the inserting transaction has committed - have to check
     * when...
     */
    if (XidInMVCCSnapshot(HeapTupleHeaderGetXmin(tuple), snapshot))
        return false;           /* treat as still in progress */

    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);
        if (!TransactionIdIsValid(xmax))
            return true;
        if (TransactionIdIsCurrentTransactionId(xmax))
        {
            if (HeapTupleHeaderGetCmax(tuple) >= snapshot->curcid)
                return true;    /* deleted after scan started */
            else
                return false;   /* deleted before scan started */
        }
        if (TransactionIdIsInProgress(xmax))
            return true;
        if (TransactionIdDidCommit(xmax))
        {
            /* updating transaction committed, but when? */
            if (XidInMVCCSnapshot(xmax, snapshot))
                return true;    /* treat as still in progress */
            return false;
        }
        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 (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 */
        SetHintBits(tuple, buffer, HEAP_XMAX_COMMITTED,
                    HeapTupleHeaderGetRawXmax(tuple));
    }

    /*
     * OK, the deleting transaction committed too ... but when?
     */
    if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmax(tuple), snapshot))
        return true;            /* treat as still in progress */

    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 GetOldestXmin()).  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(HeapTupleHeader tuple, TransactionId OldestXmin,
                         Buffer buffer)
{
    /*
     * 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 (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
    {
        if (tuple->t_infomask & HEAP_XMIN_INVALID)
            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 (TransactionIdIsInProgress(HeapTupleHeaderGetXmin(tuple)))
        {
            if (tuple->t_infomask & HEAP_XMAX_INVALID)  /* xid invalid */
                return HEAPTUPLE_INSERT_IN_PROGRESS;
            if (HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask))
                return HEAPTUPLE_INSERT_IN_PROGRESS;
            /* inserted and then deleted by same xact */
            return HEAPTUPLE_DELETE_IN_PROGRESS;
        }
        else if (TransactionIdDidCommit(HeapTupleHeaderGetXmin(tuple)))
            SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
                        HeapTupleHeaderGetXmin(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.  Also, marking dead
         * MultiXacts as invalid here provides defense against MultiXactId
         * wraparound (see also comments in heap_freeze_tuple()).
         */
        if (!(tuple->t_infomask & HEAP_XMAX_COMMITTED))
        {
            if (tuple->t_infomask & HEAP_XMAX_IS_MULTI)
            {
                /*
                 * If it's only locked but neither EXCL_LOCK nor KEYSHR_LOCK
                 * are set, it cannot possibly be running; otherwise have to
                 * check.
                 */
                if ((tuple->t_infomask & (HEAP_XMAX_EXCL_LOCK |
                                          HEAP_XMAX_KEYSHR_LOCK)) &&
                    MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple)))
                    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;

        if (MultiXactIdIsRunning(HeapTupleHeaderGetRawXmax(tuple)))
        {
            /* already checked above */
            Assert(!HEAP_XMAX_IS_LOCKED_ONLY(tuple->t_infomask));

            xmax = HeapTupleGetUpdateXid(tuple);
            if (!TransactionIdIsValid(xmax))
                return HEAPTUPLE_LIVE;
            if (TransactionIdIsInProgress(xmax))
                return HEAPTUPLE_DELETE_IN_PROGRESS;
            else if (TransactionIdDidCommit(xmax))
                /* there are still lockers around -- can't return DEAD here */
                return HEAPTUPLE_RECENTLY_DEAD;
            /* updating transaction aborted */
            return HEAPTUPLE_LIVE;
        }

        Assert(!(tuple->t_infomask & HEAP_XMAX_COMMITTED));

        xmax = HeapTupleGetUpdateXid(tuple);
        if (!TransactionIdIsValid(xmax))
            return HEAPTUPLE_LIVE;
        /* multi is not running -- updating xact cannot be */
        Assert(!TransactionIdIsInProgress(xmax));
        if (TransactionIdDidCommit(xmax))
        {
            if (!TransactionIdPrecedes(xmax, OldestXmin))
                return HEAPTUPLE_RECENTLY_DEAD;
            else
                return HEAPTUPLE_DEAD;
        }
        else
        {
            /*
             * Not in Progress, Not Committed, so either Aborted or crashed.
             */
            SetHintBits(tuple, buffer, HEAP_XMAX_INVALID, InvalidTransactionId);
            return HEAPTUPLE_LIVE;
        }

        /*
         * Deleter committed, but perhaps it was recent enough that some open
         * transactions could still see the tuple.
         */

        /* Otherwise, it's dead and removable */
        return HEAPTUPLE_DEAD;
    }

    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, but perhaps it was recent enough that some open
     * transactions could still see the tuple.
     */
    if (!TransactionIdPrecedes(HeapTupleHeaderGetRawXmax(tuple), OldestXmin))
        return HEAPTUPLE_RECENTLY_DEAD;

    /* Otherwise, it's dead and removable */
    return HEAPTUPLE_DEAD;
}

/*
 * HeapTupleIsSurelyDead
 *
 *  Determine whether a tuple is surely dead.  We sometimes use this
 *  in lieu of HeapTupleSatisifesVacuum when the tuple has just been
 *  tested by HeapTupleSatisfiesMVCC and, therefore, any hint bits that
 *  can be set should already be set.  We assume that if no hint bits
 *  either for xmin or xmax, the transaction is still running.  This is
 *  therefore faster than HeapTupleSatisfiesVacuum, because we don't
 *  consult CLOG (and also because we don't need to give an exact answer,
 *  just whether or not the tuple is surely dead).
 */
bool
HeapTupleIsSurelyDead(HeapTupleHeader tuple, TransactionId OldestXmin)
{
    /*
     * 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 (!(tuple->t_infomask & HEAP_XMIN_COMMITTED))
        return (tuple->t_infomask & HEAP_XMIN_INVALID) != 0 ? true : false;

    /*
     * 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 TransactionIdPrecedes(HeapTupleHeaderGetRawXmax(tuple), OldestXmin);
}

/*
 * XidInMVCCSnapshot
 *      Is the given XID still-in-progress according to the snapshot?
 *
 * Note: GetSnapshotData never stores either top xid or subxids of our own
 * backend into a snapshot, so these xids will not be reported as "running"
 * by this function.  This is OK for current uses, because we actually only
 * apply this for known-committed XIDs.
 */
static bool
XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
{
    uint32      i;

    /*
     * Make a quick range check to eliminate most XIDs without looking at the
     * xip arrays.  Note that this is OK even if we convert a subxact XID to
     * its parent below, because a subxact with XID < xmin has surely also got
     * a parent with XID < xmin, while one with XID >= xmax must belong to a
     * parent that was not yet committed at the time of this snapshot.
     */

    /* Any xid < xmin is not in-progress */
    if (TransactionIdPrecedes(xid, snapshot->xmin))
        return false;
    /* Any xid >= xmax is in-progress */
    if (TransactionIdFollowsOrEquals(xid, snapshot->xmax))
        return true;

    /*
     * Snapshot information is stored slightly differently in snapshots taken
     * during recovery.
     */
    if (!snapshot->takenDuringRecovery)
    {
        /*
         * If the snapshot contains full subxact data, the fastest way to
         * check things is just to compare the given XID against both subxact
         * XIDs and top-level XIDs.  If the snapshot overflowed, we have to
         * use pg_subtrans to convert a subxact XID to its parent XID, but
         * then we need only look at top-level XIDs not subxacts.
         */
        if (!snapshot->suboverflowed)
        {
            /* full data, so search subxip */
            int32       j;

            for (j = 0; j < snapshot->subxcnt; j++)
            {
                if (TransactionIdEquals(xid, snapshot->subxip[j]))
                    return true;
            }

            /* not there, fall through to search xip[] */
        }
        else
        {
            /* overflowed, so convert xid to top-level */
            xid = SubTransGetTopmostTransaction(xid);

            /*
             * If xid was indeed a subxact, we might now have an xid < xmin,
             * so recheck to avoid an array scan.  No point in rechecking
             * xmax.
             */
            if (TransactionIdPrecedes(xid, snapshot->xmin))
                return false;
        }

        for (i = 0; i < snapshot->xcnt; i++)
        {
            if (TransactionIdEquals(xid, snapshot->xip[i]))
                return true;
        }
    }
    else
    {
        int32       j;

        /*
         * In recovery we store all xids in the subxact array because it is by
         * far the bigger array, and we mostly don't know which xids are
         * top-level and which are subxacts. The xip array is empty.
         *
         * We start by searching subtrans, if we overflowed.
         */
        if (snapshot->suboverflowed)
        {
            /* overflowed, so convert xid to top-level */
            xid = SubTransGetTopmostTransaction(xid);

            /*
             * If xid was indeed a subxact, we might now have an xid < xmin,
             * so recheck to avoid an array scan.  No point in rechecking
             * xmax.
             */
            if (TransactionIdPrecedes(xid, snapshot->xmin))
                return false;
        }

        /*
         * We now have either a top-level xid higher than xmin or an
         * indeterminate xid. We don't know whether it's top level or subxact
         * but it doesn't matter. If it's present, the xid is visible.
         */
        for (j = 0; j < snapshot->subxcnt; j++)
        {
            if (TransactionIdEquals(xid, snapshot->subxip[j]))
                return true;
        }
    }

    return false;
}

/*
 * 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 time qualification 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);
    if (!TransactionIdIsValid(xmax))    /* shouldn't happen .. */
        return true;

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