Re: patch: update README-SSI

On 15.06.2011 23:28, Dan Ports wrote:
> +SSI is based on the observation [2] that each snapshot isolation
> +anomaly corresponds to a cycle that contains a "dangerous structure"
> +of two adjacent rw-conflict edges:
> +
> +      Tin ------> Tpivot ------> Tout
> +            rw             rw
> +
> +SSI works by watching for this dangerous structure, and rolling
> +back a transaction when needed to prevent any anomaly. This means it
> +only needs to track rw-conflicts between concurrent transactions, not
> +wr- and ww-dependencies. It also means there is a risk of false
> +positives, because not every dangerous structure corresponds to an
> +actual serialization failure.
> +
> +The PostgreSQL implementation uses two additional optimizations:
> +
> +* Tout must commit before any other transaction in the cycle
> +  (see proof of Theorem 2.1 of [2]). We only roll back a transaction
> +  if Tout commits before Tpivot and Tin.
> +
> +* if Tin is read-only, there can only be an anomaly if Tout committed
> +  before Tin takes its snapshot. This optimization is an original
> +  one. Proof:
> +
> +  - Because there is a cycle, there must be some transaction T0 that
> +    precedes Tin in the serial order. (T0 might be the same as Tout).
> +
> +  - The dependency between T0 and Tin can't be a rw-conflict,
> +    because T1 was read-only, so it must be a ww- or wr-dependency.
> +    Those can only occur if T0 committed before T1 started.

There's no mention on what T1 is. I believe it's supposed to be Tin, in 
the terminology used in the graph.

I don't see how there can be a ww-dependency between T0 and Tin. There 
can't be a rw-conflict because Tin is read-only, so surely there can't 
be a ww-conflict either?

(the proof is still valid, though)

> +  - Because Tout must commit before any other transaction in the
> +    cycle, it must commit before T0 commits -- and thus before T1
> +    starts.

Another reference to T1.

Patch looks good otherwise.

--   Heikki Linnakangas  EnterpriseDB   http://www.enterprisedb.com