20
20
Michael J. Cahill, Uwe Röhm, and Alan D. Fekete. 2008.
21
21
Serializable isolation for snapshot databases.
22
In SIGMOD ’08: Proceedings of the 2008 ACM SIGMOD
22
In SIGMOD '08: Proceedings of the 2008 ACM SIGMOD
23
23
international conference on Management of data,
24
pages 729–738, New York, NY, USA. ACM.
24
pages 729-738, New York, NY, USA. ACM.
25
25
http://doi.acm.org/10.1145/1376616.1376690
27
27
Michael James Cahill. 2009.
402
402
from a tuple's xmin or xmax, for example, we always call
403
403
SubTransGetTopmostTransaction() before doing much else with it.
405
* PostgreSQL does not use "update in place" with a rollback log
406
for its MVCC implementation. Where possible it uses "HOT" updates on
407
the same page (if there is room and no indexed value is changed).
408
For non-HOT updates the old tuple is expired in place and a new tuple
409
is inserted at a new location. Because of this difference, a tuple
410
lock in PostgreSQL doesn't automatically lock any other versions of a
411
row. We don't try to copy or expand a tuple lock to any other
412
versions of the row, based on the following proof that any additional
413
serialization failures we would get from that would be false
416
o If transaction T1 reads a row (thus acquiring a predicate
417
lock on it) and a second transaction T2 updates that row, must a
418
third transaction T3 which updates the new version of the row have a
419
rw-conflict in from T1 to prevent anomalies? In other words, does it
420
matter whether this edge T1 -> T3 is there?
422
o If T1 has a conflict in, it certainly doesn't. Adding the
423
edge T1 -> T3 would create a dangerous structure, but we already had
424
one from the edge T1 -> T2, so we would have aborted something
427
o Now let's consider the case where T1 doesn't have a
428
conflict in. If that's the case, for this edge T1 -> T3 to make a
429
difference, T3 must have a rw-conflict out that induces a cycle in
430
the dependency graph, i.e. a conflict out to some transaction
431
preceding T1 in the serial order. (A conflict out to T1 would work
432
too, but that would mean T1 has a conflict in and we would have
435
o So now we're trying to figure out if there can be an
436
rw-conflict edge T3 -> T0, where T0 is some transaction that precedes
437
T1. For T0 to precede T1, there has to be has to be some edge, or
438
sequence of edges, from T0 to T1. At least the last edge has to be a
439
wr-dependency or ww-dependency rather than a rw-conflict, because T1
440
doesn't have a rw-conflict in. And that gives us enough information
441
about the order of transactions to see that T3 can't have a
443
- T0 committed before T1 started (the wr/ww-dependency implies this)
444
- T1 started before T2 committed (the T1->T2 rw-conflict implies this)
445
- T2 committed before T3 started (otherwise, T3 would be aborted
446
because of an update conflict)
448
o That means T0 committed before T3 started, and therefore
449
there can't be a rw-conflict from T3 to T0.
451
o In both cases, we didn't need the T1 -> T3 edge.
405
453
* Predicate locking in PostgreSQL will start at the tuple level
406
454
when possible, with automatic conversion of multiple fine-grained
407
455
locks to coarser granularity as need to avoid resource exhaustion.