Quelle  heapam_visibility.c

/*-------------------------------------------------------------------------
 *
 * 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-2025, 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/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/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 that the caller has registered the snapshot.  This function
  * doesn't care about the registration as such, but in general you
  * shouldn't try to use a snapshot without registration because it might
  * get invalidated while it's still in use, and this is a convenient place
  * to check for that.
 */
 Assert(snapshot->regd_count > 0 || snapshot->active_count > 0);

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