Heikki Linnakangas <heikki.linnakan...@enterprisedb.com> wrote:
> Could you explain in the README, why it is safe to only take the
> lock on the visible row version, please?
Sure. I actually intended to do this last night but ran out of
steam and posted what I had, planning on following up with that.
The place it seemed to fit best was in the "Innovations" section,
since the SSI papers and their prototype implementations seemed
oriented toward "rows" -- certainly the SIREAD locks were at the row
level, versus a row version level.
Since this doesn't touch any of the files in yesterday's patch, and
it seems entirely within the realm of possibility that people will
want to argue about how best to document this more than the actual
fix, I'm posting it as a separate patch -- README-SSI only.
I mostly just copied from Dan's posted proof verbatim.
-Kevin
*** 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.
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
