Thread: Make HeapTupleSatisfiesMVCC more concurrent

Jeff Janes <jeff.janes@gmail.com> writes:
> When we check a tuple for MVCC, it has to pass checks that the inserting
> transaction has committed, and that it committed before our snapshot
> began.  And similarly that the deleting transaction hasn't committed, or
> did so after our snapshot.

> XidInMVCCSnapshot is (or can be) very much cheaper
> than TransactionIdIsInProgress, because the former touches only local
> memory while the latter takes a highly contended lock and inspects shared
> memory.  We do the slow one first, but we could do the fast one first and
> sometimes short-circuit the slow one.  If the transaction is in our
> snapshot, it doesn't matter if it is still in progress or not.

> This was discussed back in 2013 (
> http://www.postgresql.org/message-id/CAMkU=1yy-YEQVvqj2xJitT1EFkyuFk7uTV_hrOMGyGMxpU=N+Q@mail.gmail.com),
> and I wanted to revive it. The recent lwlock atomic changes haven't made
> the problem irrelevant.

> This patch swaps the order of the checks under some conditions.

Just thinking about this ... I wonder why we need to call
TransactionIdIsInProgress() at all rather than believing the answer from
the snapshot?  Under what circumstances could TransactionIdIsInProgress()
return true where XidInMVCCSnapshot() had not?

I'm thinking maybe TransactionIdIsInProgress is only needed for non-MVCC
snapshot types.
        regards, tom lane

I wrote:
> Just thinking about this ... I wonder why we need to call
> TransactionIdIsInProgress() at all rather than believing the answer from
> the snapshot?  Under what circumstances could TransactionIdIsInProgress()
> return true where XidInMVCCSnapshot() had not?

I experimented with the attached patch, which replaces
HeapTupleSatisfiesMVCC's calls of TransactionIdIsInProgress with
XidInMVCCSnapshot, and then as a cross-check has all the "return false"
exits from XidInMVCCSnapshot assert !TransactionIdIsInProgress().
The asserts did not fire in the standard regression tests nor in a
pgbench run, which is surely not proof of anything but it suggests
that I'm not totally nuts.

I wouldn't commit the changes in XidInMVCCSnapshot for real, but
otherwise this is a possibly committable patch.

            regards, tom lane

diff --git a/src/backend/utils/time/tqual.c b/src/backend/utils/time/tqual.c
index de7b3fc..c8f59f7 100644
*** a/src/backend/utils/time/tqual.c
--- b/src/backend/utils/time/tqual.c
***************
*** 10,21 ****
   * 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
--- 10,22 ----
   * 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 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 the 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
***************
*** 26,31 ****
--- 27,37 ----
   * subtransactions of our own main transaction and so there can't be any
   * race condition.
   *
+  * When using an MVCC snapshot, we rely on XidInMVCCSnapshot rather than
+  * TransactionIdIsInProgress, but the logic is otherwise the same: do not
+  * check pg_clog until after deciding that the xact is no longer in progress.
+  *
+  *
   * Summary of visibility functions:
   *
   *     HeapTupleSatisfiesMVCC()
*************** HeapTupleSatisfiesMVCC(HeapTuple htup, S
*** 961,967 ****

              if (TransactionIdIsCurrentTransactionId(xvac))
                  return false;
!             if (!TransactionIdIsInProgress(xvac))
              {
                  if (TransactionIdDidCommit(xvac))
                  {
--- 967,973 ----

              if (TransactionIdIsCurrentTransactionId(xvac))
                  return false;
!             if (!XidInMVCCSnapshot(xvac, snapshot))
              {
                  if (TransactionIdDidCommit(xvac))
                  {
*************** HeapTupleSatisfiesMVCC(HeapTuple htup, S
*** 980,986 ****

              if (!TransactionIdIsCurrentTransactionId(xvac))
              {
!                 if (TransactionIdIsInProgress(xvac))
                      return false;
                  if (TransactionIdDidCommit(xvac))
                      SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
--- 986,992 ----

              if (!TransactionIdIsCurrentTransactionId(xvac))
              {
!                 if (XidInMVCCSnapshot(xvac, snapshot))
                      return false;
                  if (TransactionIdDidCommit(xvac))
                      SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
*************** HeapTupleSatisfiesMVCC(HeapTuple htup, S
*** 1035,1041 ****
              else
                  return false;    /* deleted before scan started */
          }
!         else if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmin(tuple)))
              return false;
          else if (TransactionIdDidCommit(HeapTupleHeaderGetRawXmin(tuple)))
              SetHintBits(tuple, buffer, HEAP_XMIN_COMMITTED,
--- 1041,1047 ----
              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,
*************** HeapTupleSatisfiesMVCC(HeapTuple htup, S
*** 1048,1061 ****
              return false;
          }
      }

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

      if (tuple->t_infomask & HEAP_XMAX_INVALID)    /* xid invalid or aborted */
          return true;
--- 1054,1068 ----
              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;
*************** HeapTupleSatisfiesMVCC(HeapTuple htup, S
*** 1082,1096 ****
              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;
!         }
          /* it must have aborted or crashed */
          return true;
      }
--- 1089,1098 ----
              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;
      }
*************** HeapTupleSatisfiesMVCC(HeapTuple htup, S
*** 1105,1111 ****
                  return false;    /* deleted before scan started */
          }

!         if (TransactionIdIsInProgress(HeapTupleHeaderGetRawXmax(tuple)))
              return true;

          if (!TransactionIdDidCommit(HeapTupleHeaderGetRawXmax(tuple)))
--- 1107,1113 ----
                  return false;    /* deleted before scan started */
          }

!         if (XidInMVCCSnapshot(HeapTupleHeaderGetRawXmax(tuple), snapshot))
              return true;

          if (!TransactionIdDidCommit(HeapTupleHeaderGetRawXmax(tuple)))
*************** HeapTupleSatisfiesMVCC(HeapTuple htup, S
*** 1120,1131 ****
          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;
  }
--- 1122,1135 ----
          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;
  }
*************** XidInMVCCSnapshot(TransactionId xid, Sna
*** 1461,1467 ****
--- 1465,1474 ----

      /* Any xid < xmin is not in-progress */
      if (TransactionIdPrecedes(xid, snapshot->xmin))
+     {
+         Assert(!TransactionIdIsInProgress(xid));
          return false;
+     }
      /* Any xid >= xmax is in-progress */
      if (TransactionIdFollowsOrEquals(xid, snapshot->xmax))
          return true;
*************** XidInMVCCSnapshot(TransactionId xid, Sna
*** 1503,1509 ****
--- 1510,1519 ----
               * xmax.
               */
              if (TransactionIdPrecedes(xid, snapshot->xmin))
+             {
+                 Assert(!TransactionIdIsInProgress(xid));
                  return false;
+             }
          }

          for (i = 0; i < snapshot->xcnt; i++)
*************** XidInMVCCSnapshot(TransactionId xid, Sna
*** 1534,1540 ****
--- 1544,1553 ----
               * xmax.
               */
              if (TransactionIdPrecedes(xid, snapshot->xmin))
+             {
+                 Assert(!TransactionIdIsInProgress(xid));
                  return false;
+             }
          }

          /*
*************** XidInMVCCSnapshot(TransactionId xid, Sna
*** 1549,1554 ****
--- 1562,1568 ----
          }
      }

+     Assert(!TransactionIdIsInProgress(xid));
      return false;
  }

On 2015-08-18 20:36:13 -0400, Tom Lane wrote:
> I wrote:
> > Just thinking about this ... I wonder why we need to call
> > TransactionIdIsInProgress() at all rather than believing the answer from
> > the snapshot?  Under what circumstances could TransactionIdIsInProgress()
> > return true where XidInMVCCSnapshot() had not?
> 
> I experimented with the attached patch, which replaces
> HeapTupleSatisfiesMVCC's calls of TransactionIdIsInProgress with
> XidInMVCCSnapshot, and then as a cross-check has all the "return false"
> exits from XidInMVCCSnapshot assert !TransactionIdIsInProgress().

I'm not sure about it, but it might be worthwhile to add a
TransactionIdIsKnownCompleted() check before the more expensive parts of
XidInMVCCSnapshot(). Neither the array search nor, much more so, the
subtrans lookups are free.

- Andres

Andres Freund <andres@anarazel.de> writes:
> On 2015-08-18 20:36:13 -0400, Tom Lane wrote:
>> I experimented with the attached patch, which replaces
>> HeapTupleSatisfiesMVCC's calls of TransactionIdIsInProgress with
>> XidInMVCCSnapshot, and then as a cross-check has all the "return false"
>> exits from XidInMVCCSnapshot assert !TransactionIdIsInProgress().

> I'm not sure about it, but it might be worthwhile to add a
> TransactionIdIsKnownCompleted() check before the more expensive parts of
> XidInMVCCSnapshot(). Neither the array search nor, much more so, the
> subtrans lookups are free.

Hmmm... the comment for TransactionIdIsKnownCompleted says it's to
short-circuit calls of TransactionIdIsInProgress, which we wouldn't be
doing anymore.  Maybe it's useful anyway but I'm not convinced.

In any case, the big picture here is that XidInMVCCSnapshot should on
average be looking at just about the same number of xids and subtrans ids
as TransactionIdIsInProgress does --- only the latter is looking at them
in the PGPROC array, so it needs a lock, and iterating over that data
structure is more complex than scanning an array too.

My own thought about reducing the cost of XidInMVCCSnapshot, if that
proves necessary, is that maybe it would be worth the trouble to sort the
arrays so we could use binary search.  That would increase the cost of
snapshot acquisition noticeably though.
        regards, tom lane

On 2015-08-19 10:55:00 -0400, Tom Lane wrote:
> My own thought about reducing the cost of XidInMVCCSnapshot, if that
> proves necessary, is that maybe it would be worth the trouble to sort
> the arrays so we could use binary search.  That would increase the
> cost of snapshot acquisition noticeably though.

It's also considerably more expensive for search in many cases because
it's very hard to predict (branching and prefetching). I doubt it'd be
worthwhile.

I wrote:
> Andres Freund <andres@anarazel.de> writes:
>> I'm not sure about it, but it might be worthwhile to add a
>> TransactionIdIsKnownCompleted() check before the more expensive parts of
>> XidInMVCCSnapshot(). Neither the array search nor, much more so, the
>> subtrans lookups are free.

> Hmmm... the comment for TransactionIdIsKnownCompleted says it's to
> short-circuit calls of TransactionIdIsInProgress, which we wouldn't be
> doing anymore.  Maybe it's useful anyway but I'm not convinced.

After further thought, the right way to implement the equivalent
optimization would be to add a couple of fields to struct Snapshot that
would cache the xid last checked against that snapshot and the outcome of
that check; this would be independent of TransactionIdIsKnownCompleted.
There would be no need to use that cache for xids below xmin or above
xmax, which would improve its chance of being applicable to in-doubt xids.

Not entirely sure it's worth doing, but if someone wants to do the
legwork, this would be an independent optimization possibility.
        regards, tom lane

On Tue, Aug 18, 2015 at 8:36 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I wrote:
>> Just thinking about this ... I wonder why we need to call
>> TransactionIdIsInProgress() at all rather than believing the answer from
>> the snapshot?  Under what circumstances could TransactionIdIsInProgress()
>> return true where XidInMVCCSnapshot() had not?
>
> I experimented with the attached patch, which replaces
> HeapTupleSatisfiesMVCC's calls of TransactionIdIsInProgress with
> XidInMVCCSnapshot, and then as a cross-check has all the "return false"
> exits from XidInMVCCSnapshot assert !TransactionIdIsInProgress().
> The asserts did not fire in the standard regression tests nor in a
> pgbench run, which is surely not proof of anything but it suggests
> that I'm not totally nuts.
>
> I wouldn't commit the changes in XidInMVCCSnapshot for real, but
> otherwise this is a possibly committable patch.

Like Jeff's approach, this will set hint bits less aggressively.
Suppose there are 10 processes concurrently scanning a whole bunch of
dead tuples.  Furthermore, suppose those dead tuples were created by a
transaction that began after those processes took their snapshot and
later aborted.  Without the patch, the first one should notice that
the tuples are in fact dead and hint them HEAP_XMIN_INVALID.  With the
patch, the backends will see those transactions as in-progress rather
than aborted, so they won't be hinted.

Now that probably isn't a reason not to do this.  Anything that cuts
down on ProcArrayLock acquisition and cache-line bouncing in shared
memory is likely to be a win even if it burns a few more cycles
elsewhere.  And I think the scenario I just mentioned probably doesn't
happen that often, and probably wouldn't cost that much if it did.
But it's worth thinking about, and at the least we should document in
the commit message or the comments that this change has this effect.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Wed, Aug 19, 2015 at 2:53 AM, Amit Kapila <amit.kapila16@gmail.com> wrote:
> I think one case where the patch can impact is for aborted transactions.
> In TransactionIdIsInProgress(), we check for aborted transactions before
> consulting pg_subtrans whereas with patch it will consult pg_subtrans
> without aborted transaction check.  Now it could be better to first check
> pg_subtrans if we found that the corresponding top transaction is
> in-progress as that will save extra pg_clog lookup, but I just mentioned
> because that is one difference that I could see with this patch.
>
> Another minor point is, I think we should modify function level comment
> for XidInMVCCSnapshot() where it says that this applies to known-
> committed XIDs which will no longer be true after this patch.

But only if the snapshot has overflowed, right?  That should affect
only a small minority of cases.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:
> On Tue, Aug 18, 2015 at 8:36 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I experimented with the attached patch, which replaces
>> HeapTupleSatisfiesMVCC's calls of TransactionIdIsInProgress with
>> XidInMVCCSnapshot, and then as a cross-check has all the "return false"
>> exits from XidInMVCCSnapshot assert !TransactionIdIsInProgress().

> Like Jeff's approach, this will set hint bits less aggressively.

Only very marginally so, though: we will not set a hint bit in the case
where the updating transaction has committed/aborted but it is still shown
as running by our snapshot.  As soon as a reader comes along with a
snapshot taken after the updater ended, that transaction will set the hint
bit.

Note that in the case where the updating transaction committed, setting
the hint bit early wouldn't save anything anyway, since we'd still need
to run XidInMVCCSnapshot().  It is true that if the updater aborted,
we could save cycles by hinting earlier; but I believe the general project
policy about such choices is not to optimize for the abort case.  Also
note that the cycles wasted will now be in XidInMVCCSnapshot(), not in
ProcArray access, so they won't be as much of a scalability problem.

> But it's worth thinking about, and at the least we should document in
> the commit message or the comments that this change has this effect.

Agreed, there is a tradeoff being made.
        regards, tom lane

Amit Kapila <amit.kapila16@gmail.com> writes:
> On Fri, Aug 21, 2015 at 8:22 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>> On Wed, Aug 19, 2015 at 2:53 AM, Amit Kapila <amit.kapila16@gmail.com>
>>> Another minor point is, I think we should modify function level comment
>>> for XidInMVCCSnapshot() where it says that this applies to known-
>>> committed XIDs which will no longer be true after this patch.

Yeah, that comment would certainly be out of date, and I think it may not
be the only one.  I'll check around some more.

> I am wondering that is there any harm in calling TransactionIdDidAbort()
> in slow path before calling SubTransGetTopmostTransaction(), that can
> also maintain consistency of checks in both the functions?

I think this is probably a bad idea.  It adds a pg_clog lookup that we
would otherwise not do at all, in hopes of avoiding a pg_subtrans lookup.
It's not exactly clear that that's a win even if we successfully avoid
the subtrans lookup (which we often would not).  And even if it does win,
that would only happen if the other transaction has aborted, which isn't
generally the case we prefer to optimize for.

I don't mean to dismiss the potential for further optimization inside
XidInMVCCSnapshot (for instance, the one-XID-cache idea sounds promising);
but I think that's material for further research and a separate patch.

It's not clear to me if anyone wanted to do further review/testing of
this patch, or if I should go ahead and push it (after fixing whatever
comments need to be fixed).
        regards, tom lane

Tom Lane wrote:
> Amit Kapila <amit.kapila16@gmail.com> writes:

> > I am wondering that is there any harm in calling TransactionIdDidAbort()
> > in slow path before calling SubTransGetTopmostTransaction(), that can
> > also maintain consistency of checks in both the functions?
> 
> I think this is probably a bad idea.  It adds a pg_clog lookup that we
> would otherwise not do at all, in hopes of avoiding a pg_subtrans lookup.
> It's not exactly clear that that's a win even if we successfully avoid
> the subtrans lookup (which we often would not).  And even if it does win,
> that would only happen if the other transaction has aborted, which isn't
> generally the case we prefer to optimize for.

It's probably key to this idea that TransactionIdDidAbort returns in a
single slru lookup, whereas SubTransGetTopmostTransaction needs to
iterate possibly many layers of subxacts.  But the point about this
being a win only for aborted xacts makes it probably pointless, I agree.

-- 
Álvaro Herrera                http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Simon Riggs <simon@2ndQuadrant.com> writes:
> On 25 August 2015 at 21:51, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I don't mean to dismiss the potential for further optimization inside
>> XidInMVCCSnapshot (for instance, the one-XID-cache idea sounds promising);
>> but I think that's material for further research and a separate patch.

> Patch attached. Doesn't seem worth a separate thread.

This doesn't seem right to me: it only caches the case where the XID is
found to be present in the snapshot, whereas I think probably we should
remember the result in both cases (present or not).

Moreover, in the subxip-overflowed case where we replace an
originally-inquired-of subxact xid with its parent, what you're caching is
the parent xid, which will fail to match subsequent queries.  Shouldn't we
cache the originally inquired-of xid?

The question of whether to cache "false" results perhaps requires some
performance testing.
        regards, tom lane