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

[The first attempt to send this shows as undeliverable to the list.
Resending for completeness and coherency of archives. Apologies to
those getting duplicates.]

> Heikki Linnakangas wrote:
> On 26.05.2011 06:19, Kevin Grittner wrote:
>
>> /*
>> * Check whether the writer has become a pivot with an
>> * out-conflict committed transaction, while neither reader
>> * nor writer is committed. If the reader is a READ ONLY
>> * transaction, there is only a serialization failure if an
>> * out-conflict transaction causing the pivot committed
>> * before the reader acquired its snapshot. (That is, the
>> * reader must not have been concurrent with the out-conflict
>> * transaction.)
>> */
>
> The comment is not in sync with the code. The code is not checking
> that "neither reader or writer has committed", but something more
> complicated.

True. We changed the code but not the comment. Sorry for missing
that. Basically the quoted clause would be correct by changing it to
"neither reader nor writer committed first." (Your rewrite,
discussed below, is better, though.)

> I find it helps tremendously to draw the dangerous structures being
> checked, in addition to just explaining them in text.

Agreed -- I spent many an hour with the "dangerous structure" diagram
in front of me when thinking through the mechanics of implementation.

> Ascii art is a bit clunky, but I think we have to do it here.

OK.

> I did some of that in the comments, and I think I understand it
> now. See attached patch. Does that look right to you?

! * A serialization failure can only occur if there is a dangerous
! * structure in the dependency graph:
! *
! * Tin ------> Tpivot ------> Tout
! * rw rw
! *
! * Furthermore, Tout must commit first.

I agree that this is easier to read and understand than just straight
text; but you dropped one other condition, which we use rather
heavily. We should probably add back something like:

* If Tin is declared READ ONLY (or commits without writing), we can
* only have a problem if Tout committed before Tin acquired its
* snapshot.

> * XXX: Where does that last condition come from?

This optimization is an original one, not yet appearing in any
academic papers; Dan and I are both convinced it is safe, and in
off-list correspondence with Michael Cahill after he left Oracle, he
said that he discussed this with Alan Fekete and they both concur
that it is a safe and good optimization.

This optimization is mentioned in the README-SSI file in the
"Innovations" section. Do you think that file needs to have more on
the topic?

> * XXX: for an anomaly to occur, T2 must've committed before W.
> * Couldn't we easily check that here, or does the fact that W
> * committed already somehow imply it?

The flags and macros should probably be renamed to make it more
obvious that this is covered. The flag which SxactHasConflictOut is
based on is only set when the conflict out is to a transaction which
committed ahead of the flagged transaction. Regarding the other
test -- since we have two transactions (Tin and Tout) which have not
been summarized, and transactions are summarized in order of commit,
SxactHasSummaryConflictOut implies that the transaction with the flag
set has not committed before the transaction to which it has a
rw-conflict out.

The problem is coming up with a more accurate name which isn't really
long. The best I can think of is SxactHasConflictOutToEarlierCommit,
which is a little long. If nobody has a better idea, I guess it's
better to have a long name than a misleading one. Do you think we
need to rename SxactHasSummaryConflictOut or just add a comment on
that use that a summarized transaction will always be committed ahead
of any transactions which are not summarized?

> (note that I swapped the second and third check in the function, I
> think it's more straightforward that way).

It doesn't matter to me either way, so if it seems clearer to you,
that's a win.

> Should we say "Cancelled on identification as pivot, during ...",
> or "Cancelled on identification as a pivot, during ..." ? We seem
> to use both in the error messages.

Consistency is good. I think it sounds better with the indefinite
article in there.

Do you want me to post another patch based on this, or are these
changes from what you posted small enough that you would prefer to
just do it as part of the commit?

Thanks for taking the time to work through this. As always, your
ideas improve things.

-Kevin