ssi-readme-tuple-lock.patch

*** a/src/backend/storage/lmgr/README-SSI
--- b/src/backend/storage/lmgr/README-SSI
***************
*** 402,407 **** is based on the top level xid.  When looking at an xid that comes
--- 402,455 ----
  from a tuple's xmin or xmax, for example, we always call
  SubTransGetTopmostTransaction() before doing much else with it.
  
+     * PostgreSQL does not use "update in place" with a rollback log
+ for its MVCC implementation.  Where possible it uses "HOT" updates on
+ the same page (if there is room and no indexed value is changed).
+ For non-HOT updates the old tuple is expired in place and a new tuple
+ is inserted at a new location.  Because of this difference, a tuple
+ lock in PostgreSQL doesn't automatically lock any other versions of a
+ row.  We don't try to copy or expand a tuple lock to any other
+ versions of the row, based on the following proof that any additional
+ serialization failures we would get from that would be false
+ positives:
+ 
+           o If transaction T1 reads a row (thus acquiring a predicate
+ lock on it) and a second transaction T2 updates that row, must a
+ third transaction T3 which updates the new version of the row have a
+ rw-conflict in from T1 to prevent anomalies?  In other words, does it
+ matter whether this edge T1 -> T3 is there?
+ 
+           o If T1 has a conflict in, it certainly doesn't. Adding the
+ edge T1 -> T3 would create a dangerous structure, but we already had
+ one from the edge T1 -> T2, so we would have aborted something
+ anyway.
+ 
+           o Now let's consider the case where T1 doesn't have a
+ conflict in. If that's the case, for this edge T1 -> T3 to make a
+ difference, T3 must have a rw-conflict out that induces a cycle in
+ the dependency graph, i.e. a conflict out to some transaction
+ preceding T1 in the serial order. (A conflict out to T1 would work
+ too, but that would mean T1 has a conflict in and we would have
+ rolled back.)
+ 
+           o So now we're trying to figure out if there can be an
+ rw-conflict edge T3 -> T0, where T0 is some transaction that precedes
+ T1. For T0 to precede T1, there has to be has to be some edge, or
+ sequence of edges, from T0 to T1. At least the last edge has to be a
+ wr-dependency or ww-dependency rather than a rw-conflict, because T1
+ doesn't have a rw-conflict in. And that gives us enough information
+ about the order of transactions to see that T3 can't have a
+ rw-dependency to T0:
+  - T0 committed before T1 started (the wr/ww-dependency implies this)
+  - T1 started before T2 committed (the T1->T2 rw-conflict implies this)
+  - T2 committed before T3 started (otherwise, T3 would be aborted
+                                    because of an update conflict)
+ 
+           o That means T0 committed before T3 started, and therefore
+ there can't be a rw-conflict from T3 to T0.
+ 
+           o In both cases, we didn't need the T1 -> T3 edge.
+ 
      * Predicate locking in PostgreSQL will start at the tuple level
  when possible, with automatic conversion of multiple fine-grained
  locks to coarser granularity as need to avoid resource exhaustion.