Re: SSI predicate locking on heap -- tuple or row?

I have thought about this quite a bit and am fairly certain we do not need
to track this linkage between row versions. One strong hint to this
is that all the work I've seen on multiversion serializability
theory defines a rw-conflict to be one transaction reading an object
and the other writing *the next version* of the same object.

But maybe that doesn't answer the question conclusively -- after all,
the differences between an object, a tuple, and a row are subtle. So
see the argument below:
[I think it's similar to the argument you were making.]

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.

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.)

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, and therefore there can't be
a rw-conflict from T3 to T0.

In both cases, we didn't need the T1 -> T3 edge.

Does that make sense to you? Unless anyone can poke a hole in that
reasoning, I think we can get rid of the code to handle later versions,
which would make me happy for many reasons. It will not be missed.

Dan

--
Dan R. K. Ports MIT CSAIL http://drkp.net/