Re: Potential G2-item cycles under serializable isolation

On 6/3/20 7:51 AM, Daniel Verite wrote:
> But it doesn't say that the *only* difference between RR and > Serializable is avoiding P3. When defining P1, P2, P3, it doesn't > explicitly say that these are the only anomalies that can arise from > concurrency.
Ah, yes, now I understand. I've been working with Berenson/Adya too long--I've taken their conclusions for granted. You're right: the spec comes awfully close, but doesn't say these are the *only* phenomena possible:

> The following phenomena are possible: [description of P1, P2, and > P3] > The isolation levels are different with respect to phenomena P1, P2, > and P3.
Berenson et al., in "A Critique of ANSI SQL Isolation Levels", identified this as a key challenge in interpreting the spec:

> The isolation levels are defined by the phenomena they are forbidden > to experience.
But also:

> The prominence of the table compared to this extra proviso leads to > a common misconception that disallowing the three phenomena implies > serializability.
Which led Berenson et al. to claim that the SQL spec's definitions are a.) ambiguous and b.) incomplete. They argue that the "strict" (or, in Adya, the "anomaly") interpretation is incorrect, and construct a "broad" (Adya: "preventative") interpretation in terms of a new phenomenon (P0: dirty writes), and more general forms of P1, P2, and P3. The bulk of section 3 demonstrates that the anomaly interpretations lead to weird results, and that what the ANSI spec *intended* was the preventative interpretations.

> Strict interpretations A1, A2, and A3 have unintended weaknesses. > The correct interpretations are the Broad ones. We assume in what > follows that ANSI meant to define P1, P2, and P3.

For a more concise overview of this, see Adya's thesis, section 2.3. Adya goes on to show that the preventative interpretation forbids some serializable histories, and redefines the ANSI levels again in terms of generalized, MVCC-friendly phenomena G0, G1, and G2. When I say Postgres violates repeatable read, I mean in the sense that it allows G2-item, which is prevented by Adya PL-2.99: repeatable read. See Adya 3.2.4 for his formulation of repeatable read, which *does* differ from serializability only in terms of predicate-related phenomena.

http://pmg.csail.mit.edu/papers/adya-phd.pdf

For a compact version of this argument and formalism, see Adya, Liskov, & O'Neil's "Generalized Isolation Level Definitions": http://bnrg.cs.berkeley.edu/~adj/cs262/papers/icde00.pdf.

That's why I was asking a few days ago whether Postgres had adopted the anomaly interpretation--Since Postgres implements SI, it made sense that y'all would have followed Berenson et al. in using the preventative interpretation, or Adya in using generalized definitions. But... in the Postgres docs, and your comments in this thread, it seems like y'all are going with the anomaly interpretation instead. That'd explain why there's this extra "serialization anomaly" difference between RR and serializable. That'd also explain why the Postgres docs imply RR << SI, even though Berenson et al. and Adya both say RR >><< SI.

Is... that the right way to understand things?
--Kyle