-----Original Message-----
From: Jon Grov [mailto:jon@linpro.no]
Sent: Friday, April 05, 2002 12:54 PM
To: Dann Corbit
Cc: Mike Mascari; Doug McNaught; pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Suggestion for optimization


"Dann Corbit" <DCorbit@connx.com> writes:

> That's interesting.  If Oracle is a MVCC database, how did they 
> manage to perform ANSI standard Isolation Levels?  It seems it ought
> to be impossible.

There's an excellent introduction to MVCC and snapshot isolation in
the PostgreSQL docs.

See
http://www2.no.postgresql.org/users-lounge/docs/7.2/postgres/mvcc.html
>>------------------------------------------------------------------
I have read these documents (and some others) now.  It seems that 
there is a serializable transaction level, and so the goal I was 
after can be reached anyway.  So never mind.  I am at peace again
(and breathing a heavy sigh of relief).

But I am a bit puzzled.  How can a serializable transaction be
performed in a MVCC system?  I realize the Oracle does it, and also
Postgresql, but I can't picture how that would work.
<<------------------------------------------------------------------

Fri, 5 Apr 2002 13:04:34 -0800
"Dann Corbit" <DCorbit@connx.com>
Re: Suggestion for optimization
(Sorry that my previous post did not reach the pgsql-hackers list, I
sent it from the wrong address and was thus not considered a
subscriber)

"Dann Corbit" <DCorbit@connx.com> writes:

> But I am a bit puzzled.  How can a serializable transaction be
> performed in a MVCC system?  I realize the Oracle does it, and also
> Postgresql, but I can't picture how that would work.

In short, snapshot isolation implies this (assuming all transactions
are assigned a monotonously growing timestamp, and that all updates
create a new, unique version of the object):

- A transactions reads the most recent version of an object that is
  written by a transaction who were committed at it's beginning.

- Two concurrent (i.e. at some point in time, they're both active)
  transactions need to have disjunct write sets.

This is probably best illustrated through an example:

Let x and y be columns in a table a. Initially, x = 20 and y = 5 in
the row where k = 1 (k is the primary key).

- Let T_1 be transaction as follows:

  BEGIN;
  SELECT x FROM a WHERE k = 1; SELECT y FROM a WHERE k = 1;
  END;

- Let T_2 be another transaction:

  BEGIN;
  UPDATE a SET x = 10 WHERE k = 1; UPDATE a SET y = 10 WHERE k = 1;
  END;

Then, if we have the following execution:

10 BEGIN; /* T_2 */

20 BEGIN; /* T_1 */

30 SELECT x FROM a WHERE k = 1; /* T_1 */

40 UPDATE a SET x = 10 WHERE k = 1; /* T_2 */

50 UPDATE y SET a = 10 WHERE k = 1; /* T_2 */

60 SELECT y FROM a WHERE k = 1; /* T_1 */

70 END; /* T_2 */

80 END; /* T_1 */

Clearly, this would not be serializable in a non-versioned
database. But under MVCC and snapshot isolation, T_1 reads from a
snapshot, i.e. it would not (under serialable isolation level, at
least) be allowed to read anything T_2 have written. The requirement
is that a transaction T reads values written by transactions committed
before T's beginning.

So T_1 would find that x = 20 and y = 5, just as it would if T_1 and
T_2 were executed serially with T_1 before T_2.

With two (or more) updating transactions, things get more complicated.

Assume we have the following to transactions:

T_1:

  BEGIN;
  UPDATE x SET x = x + 10;
  END;

T_2:

  BEGIN;
  UPDATE x SET x = x - 5;
  END;

and the following execution (assuming x = 20 before it starts):

10 BEGIN; /* T_1 */
20 BEGIN; /* T_2 */

30 UPDATE x SET x = x + 10; /* T_1 */

40 END; /* T_1 */

50 UPDATE x SET x = x - 5; /* T_2 */

60 END; /* T_2 *

Since a transaction is only allowed to read values written by
transactions committed before it's beginning, both T_1 and T_2 will
read x = 20. A transaction started after just this execution would
then read T_2's newly written value of x, that is 15, and line 40
would become a lost update. To avoid this, PostgreSQL offers two
solutions:

- Read committed isolation, where a statement on the form UPDATE
  <table> SET <column> = <column> + <value> is considered a special
  case and T_2 is allowed to read T_1's value.

- Serializable isolation, where T_2 would have to be aborted.

If line 40 and 50 were swapped, T_2 would wait to see what happens to
T_1. If it's aborted, it can safely read x = 20 regardless of the
isolation level, if it's committed, the result would again depend on
the selected isolation level.

Hopefully, this illustrates the basic concepts. An interesting article
concerning the subtleties of this subject was posted by Tom Lane a
couple of days ago:

http://groups.google.com/groups?q=postgresql+regression&hl=en&ie=utf-8&oe=utf-8&scoring=d&selm=11556.1017860660%40sss.pgh.pa.us&rnum=4

In addition, this seems to be the "canonical paper" on snapshot
isolation:

http://citeseer.nj.nec.com/berenson95critique.html


--
Jon Grov, Linpro as


06 Apr 2002 00:24:49 +0200
Jon Grov <jongr@ifi.uio.no>
Re: Suggestion for optimization
> In addition, this seems to be the "canonical paper" on snapshot
> isolation:
>
> http://citeseer.nj.nec.com/berenson95critique.html

There is an excellent, more recent paper, Generalized Isolation Level
Definitions (http://citeseer.nj.nec.com/adya00generalized.html).




Fri, 5 Apr 2002 22:48:57 -0500
"Ken Hirsch" <kenhirsch@myself.com>
Re: Suggestion for optimization