Re: SSI predicate locking on heap -- tuple or row? - Mailing list pgsql-hackers

Dan Ports <drkp@csail.mit.edu> wrote:
> [I think it's similar to the argument you were making.]
Similar, but you found a simpler, shorter way to the end, which
should make Robert happy.  ;-)
> On Sat, May 21, 2011 at 03:09:12PM -0500, Kevin Grittner wrote:
>> The issue can be rephrased to this: 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?
> 
> OK, that's a good way to phrase the question. Does it matter
> whether this edge T1 -> T3 is there?
> 
> 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.
I had to pause a moment on that because you didn't mention the
"early enough commit" aspects; but certainly if T3 commits early
enough to cause a problem then T2 does, so this is solid.
> 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.)
Agreed.
> 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)
> 
> That means T0 committed before T3 started,
[scribbles diagrams]  Yep.
> and therefore there can't be a rw-conflict from T3 to T0.
No overlap means no rw-conflict; so that has to be true.
> In both cases, we didn't need the T1 -> T3 edge.
> 
> 
> Does that make sense to you?
Makes sense to me.  Like the proof I offered, you have shown that
there is no cycle which can develop with the locks copied which
isn't there anyway if we don't copy the locks.
> Unless anyone can poke a hole in that reasoning, I think we can
> get rid of the code to handle later versions,
Actually, we now have two independent proofs which don't have much
in common beyond the initial statement of the problem.  Someone
would need to show a flaw in that premise or punch holes in both
proofs.  I think we can get by with just the shorter proof (yours)
in the README file, though.
-Kevin