Обсуждение: incoherent view of serializable transactions

As I've understood limitations of the PostgreSQL implementation of
SERIALIZABLE transactions, at least the only example given in the
documentation, revolve around a rather unlikely situation:
Given concurrent transactions T1 and T2 and non-overlapping sets of
data A and B, T1 reads data including A and uses the data to modify B
while T2 reads data including B and uses that data to modify A, where
the modifications performed by either would affect the modifications
made by the other, if they were visible.
For reasons I'll omit here, that scenario didn't worry me for my
current uses of PostgreSQL.
I've found another form of deviation from the standard SERIALIZABLE
behavior, though, which does worry me.  Although the above appears to be
the only situation where the end result after everything commits is
inconsistent with standard SERIALIZABLE behavior, the PostgreSQL
implementation allows transactions to view the data in states which
would never be possible during the application of the transactions in
series in the order they will appear to have been applied after the
commit.
Imagine, as an example, a system which involves recording receipts,
each of which must go into a daily deposit.  There is a control table
with one row containing the current deposit date for receipts. 
Somewhere mid-afternoon that date is updated, all subsequent receipts
fall into the new day, and a report is run listing the receipts for the
day and giving the deposit total.
Under a standard-compliant implementation of SERIALIZABLE, this is
straightforward: a transaction which is inserting a receipt selects the
deposit date to use in its transaction, and any SELECT of receipts for a
date prior to the current deposit date will see the accurate, final
data.  Under the PostgreSQL implementation, although data eventually
gets to a coherent state, there can be a window of time where a SELECT
can return an incomplete list of receipts for a date which appears to be
closed, even if all transactions for modifying and viewing data are
SERIALIZABLE.
-- setup
create table ctl (k text not null primary key, deposit_date date not
null);
insert into ctl values ('receipt', date '2008-12-22');
create table receipt (receipt_no int not null primary key, deposit_date
date not null, amount numeric(13,2));
insert into receipt values (1, (select deposit_date from ctl where k =
'receipt'), 1.00);
insert into receipt values (2, (select deposit_date from ctl where k =
'receipt'), 2.00);

-- connection 1
start transaction isolation level serializable ;
insert into receipt values (3, (select deposit_date from ctl where k =
'receipt'), 4.00);

-- connection 2
start transaction isolation level serializable ;
update ctl set deposit_date = date '2008-12-23' where k = 'receipt';
commit transaction;
start transaction isolation level serializable ;
select * from ctl;
-- (deposit_date shows as 2008-12-23)
select * from receipt;
-- (Only receipts 1 and 2 show for 2008-12-22.)
commit;

-- connection 1
commit transaction;

-- connection 2
start transaction isolation level serializable ;
select * from receipt;
-- (All receipts for the 2008-12-22 deposit date now show.)
commit transaction;
At this point, SERIALIZABLE transactions appear to have worked, with
receipt 3 happening before the update of deposit_date; however, there
was a window of time when the update to deposit_date was visible and
receipt 3 was not.
This absolutely can't happen in a standard-compliant implementation.
At a minimum, this window where visible data lacks coherency should be
noted in the documentation.  I don't know if there's any way to fix
this without killing performance.
-Kevin

On Mon, Dec 22, 2008 at 11:00:53AM -0600, Kevin Grittner wrote:
> As I've understood limitations of the PostgreSQL implementation of
> SERIALIZABLE transactions, at least the only example given in the
> documentation, revolve around a rather unlikely situation:
>
> Given concurrent transactions T1 and T2 and non-overlapping sets of
> data A and B, T1 reads data including A and uses the data to modify B
> while T2 reads data including B and uses that data to modify A, where
> the modifications performed by either would affect the modifications
> made by the other, if they were visible.

In so far as the "modifications" are just INSERTs (no UPDATEs or
DELETEs), yes. This case is covered in the documentation.

> Imagine, as an example, a system which involves recording receipts,
> each of which must go into a daily deposit.  There is a control table
> with one row containing the current deposit date for receipts.
> Somewhere mid-afternoon that date is updated, all subsequent receipts
> fall into the new day, and a report is run listing the receipts for the
> day and giving the deposit total.

This is a variation of the above and has the same "proper" solution:
predicate locking. However, in this case the records in question are
already present so you can workaround it easily. First do a SELECT FOR
UPDATE on all the records you want to update. This will serialize all
parallel transactions to either before or after you. Then do your
update.

> This absolutely can't happen in a standard-compliant implementation.
> At a minimum, this window where visible data lacks coherency should be
> noted in the documentation.  I don't know if there's any way to fix
> this without killing performance.

Predicate locking is nasty and we don't try. I'm not sure if anybody
else does.

Have a nice day,
--
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> Please line up in a tree and maintain the heap invariant while
> boarding. Thank you for flying nlogn airlines.

>>> Martijn van Oosterhout <kleptog@svana.org> wrote:
> On Mon, Dec 22, 2008 at 11:00:53AM -0600, Kevin Grittner wrote:
>> As I've understood limitations of the PostgreSQL implementation of
>> SERIALIZABLE transactions, at least the only example given in the
>> documentation, revolve around a rather unlikely situation:
>>  
>> Given concurrent transactions T1 and T2 and non-overlapping sets of
>> data A and B, T1 reads data including A and uses the data to modify
B
>> while T2 reads data including B and uses that data to modify A,
where
>> the modifications performed by either would affect the
modifications
>> made by the other, if they were visible.
>
> In so far as the "modifications" are just INSERTs (no UPDATEs or
> DELETEs), yes. This case is covered in the documentation.
Let's not understate the scope of the issue.
UPDATEs and DELETEs count, too.  For example:
-- connection 1
cir=> create table mytab (class int not null, value int not null);
CREATE TABLE
cir=> copy mytab from stdin;
Enter data to be copied followed by a newline.
End with a backslash and a period on a line by itself.
>> 1    10
>> 1    20
>> 2    100
>> 2    200
>> \.
cir=> start transaction isolation level serializable;
START TRANSACTION
cir=> update mytab set value = (select sum(value) from mytab where
class = 2) where class = 1 and value = 10;
UPDATE 1
-- connection 2
cir=> start transaction isolation level serializable;
START TRANSACTION
cir=> update mytab set value = (select sum(value) from mytab where
class = 1) where class = 2 and value = 100;
UPDATE 1
cir=> commit transaction;
COMMIT
-- connection 1
cir=> commit transaction;
COMMIT
cir=> select * from mytab;class | value
-------+-------    1 |    20    2 |   200    1 |   300    2 |    30
(4 rows)
>> Imagine, as an example, a system which involves recording receipts,
>> each of which must go into a daily deposit.  There is a control
table
>> with one row containing the current deposit date for receipts. 
>> Somewhere mid-afternoon that date is updated, all subsequent
receipts
>> fall into the new day, and a report is run listing the receipts for
the
>> day and giving the deposit total.
>
> This is a variation of the above and has the same "proper" solution:
> predicate locking. However, in this case the records in question are
> already present so you can workaround it easily. First do a SELECT
FOR
> UPDATE on all the records you want to update. This will serialize
all
> parallel transactions to either before or after you. Then do your
> update.
My point isn't that there aren't workarounds, it is that people might
reasonably assume that SERIALIZABLE transactions provide sufficient
concurrency control for this, since the only example we give of a
problem is a rather contrived update anomaly.  The fact that even in
cases where the data settles into good form at commit leave windows
where race conditions could cause occasional bad results without extra
explicit locking is not obvious.
>> This absolutely can't happen in a standard-compliant
implementation.
>> At a minimum, this window where visible data lacks coherency should
be
>> noted in the documentation.  I don't know if there's any way to fix
>> this without killing performance.
>
> Predicate locking is nasty and we don't try. I'm not sure if anybody
> else does.
I know for a fact that Sybase ASE does.  I've heard from reasonably
reliable sources that DB2 does.  I know that Microsoft SQL Server did
for some time after the split from the Sybase code base, but I'm not
sure they've continued that; in fact there was a reference to
concurrency issues in wikipedia which implied that they no longer do.
The implementation is not pretty -- they do it by locking accessed
pages and insertion points, and in some cases entire tables.  It is so
ugly that at one point in discussing similar issues Tom said that it
couldn't really qualify as predicate locking, but in the face of the
fact that they have covered all the bases to provide true serializable
transactions, and that theory says that only predicate locking can do
that, he conceded that it was predicate locking -- but really ugly and
in a form he would never support.
Anyway, I didn't argue that we should provide truly serializable
transactions, just that we should provide a less contrived example of
where the PostgreSQL implementation can show anomalies, so that people
don't get burned through a false sense of security.
-Kevin

"Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
> At this point, SERIALIZABLE transactions appear to have worked, with
> receipt 3 happening before the update of deposit_date; however, there
> was a window of time when the update to deposit_date was visible and
> receipt 3 was not.
> This absolutely can't happen in a standard-compliant implementation.

I think you mean "you'd like to believe that can't happen in a
standard-compliant implementation".  It doesn't include any of the
specific behaviors that are forbidden by the spec, though, so I'm less
than convinced.

An appropriate way to prevent the problem is probably for the
transaction that changes the deposit_date to take out a write-excluding
lock on the receipts table before it does so.
        regards, tom lane

Kevin,

If you want to know how to build SERIALIZABLE with a database that 
provides SI (Snapshot Isolation), read 
http://portal.acm.org/citation.cfm?doid=1376616.137669
Note that in practice, READ COMMITTED is the most largely used isolation 
level and its limitations are relatively well understood by the average 
programmer that can program his application accordingly. I still don't 
get why people would use SERIALIZABLE since there is no efficient 
implementation of it.

My 2 cents.
Emmanuel


Kevin Grittner wrote:
> As I've understood limitations of the PostgreSQL implementation of
> SERIALIZABLE transactions, at least the only example given in the
> documentation, revolve around a rather unlikely situation:
>  
> Given concurrent transactions T1 and T2 and non-overlapping sets of
> data A and B, T1 reads data including A and uses the data to modify B
> while T2 reads data including B and uses that data to modify A, where
> the modifications performed by either would affect the modifications
> made by the other, if they were visible.
>  
> For reasons I'll omit here, that scenario didn't worry me for my
> current uses of PostgreSQL.
>  
> I've found another form of deviation from the standard SERIALIZABLE
> behavior, though, which does worry me.  Although the above appears to be
> the only situation where the end result after everything commits is
> inconsistent with standard SERIALIZABLE behavior, the PostgreSQL
> implementation allows transactions to view the data in states which
> would never be possible during the application of the transactions in
> series in the order they will appear to have been applied after the
> commit.
>  
> Imagine, as an example, a system which involves recording receipts,
> each of which must go into a daily deposit.  There is a control table
> with one row containing the current deposit date for receipts. 
> Somewhere mid-afternoon that date is updated, all subsequent receipts
> fall into the new day, and a report is run listing the receipts for the
> day and giving the deposit total.
>  
> Under a standard-compliant implementation of SERIALIZABLE, this is
> straightforward: a transaction which is inserting a receipt selects the
> deposit date to use in its transaction, and any SELECT of receipts for a
> date prior to the current deposit date will see the accurate, final
> data.  Under the PostgreSQL implementation, although data eventually
> gets to a coherent state, there can be a window of time where a SELECT
> can return an incomplete list of receipts for a date which appears to be
> closed, even if all transactions for modifying and viewing data are
> SERIALIZABLE.
>  
> -- setup
> create table ctl (k text not null primary key, deposit_date date not
> null);
> insert into ctl values ('receipt', date '2008-12-22');
> create table receipt (receipt_no int not null primary key, deposit_date
> date not null, amount numeric(13,2));
> insert into receipt values (1, (select deposit_date from ctl where k =
> 'receipt'), 1.00);
> insert into receipt values (2, (select deposit_date from ctl where k =
> 'receipt'), 2.00);
>
> -- connection 1
> start transaction isolation level serializable ;
> insert into receipt values (3, (select deposit_date from ctl where k =
> 'receipt'), 4.00);
>
> -- connection 2
> start transaction isolation level serializable ;
> update ctl set deposit_date = date '2008-12-23' where k = 'receipt';
> commit transaction;
> start transaction isolation level serializable ;
> select * from ctl;
> -- (deposit_date shows as 2008-12-23)
> select * from receipt;
> -- (Only receipts 1 and 2 show for 2008-12-22.)
> commit;
>
> -- connection 1
> commit transaction;
>
> -- connection 2
> start transaction isolation level serializable ;
> select * from receipt;
> -- (All receipts for the 2008-12-22 deposit date now show.)
> commit transaction;
>  
> At this point, SERIALIZABLE transactions appear to have worked, with
> receipt 3 happening before the update of deposit_date; however, there
> was a window of time when the update to deposit_date was visible and
> receipt 3 was not.
>  
> This absolutely can't happen in a standard-compliant implementation.
> At a minimum, this window where visible data lacks coherency should be
> noted in the documentation.  I don't know if there's any way to fix
> this without killing performance.
>  
> -Kevin
>
>   


-- 
Emmanuel Cecchet
FTO @ Frog Thinker 
Open Source Development & Consulting
--
Web: http://www.frogthinker.org
email: manu@frogthinker.org
Skype: emmanuel_cecchet

>>> Tom Lane <tgl@sss.pgh.pa.us> wrote: 
> "Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
>> At this point, SERIALIZABLE transactions appear to have worked,
with
>> receipt 3 happening before the update of deposit_date; however,
there
>> was a window of time when the update to deposit_date was visible
and
>> receipt 3 was not.
>  
>> This absolutely can't happen in a standard-compliant
implementation.
> 
> I think you mean "you'd like to believe that can't happen in a
> standard-compliant implementation".
"The execution of concurrent SQL-transactions at isolation level
SERIALIZABLE is guaranteed to be serializable. A serializable
execution is defined to be an execution of the operations of
concurrently executing SQL-transactions that produces the same
effect as some serial execution of those same SQL-transactions. A
serial execution is one in which each SQL-transaction executes to
completion before the next SQL-transaction begins."
If you look at the serializable queries in the original post for this
thread, it's not hard to see that this standard is not met.  The
insert of receipt 3 appears to happen before the update of the control
record, since it has the old deposit date.  The transaction which
selects from both tables sees the update to the control record, so it
must come after that.  Yet it doesn't see the results of the first
transaction.  There is no sequence of serial execution which is
consistent with the behavior.
Perhaps you are suggesting that it's not possible in a practical sense
for a DBMS to meet this standard?  See below.
> It doesn't include any of the
> specific behaviors that are forbidden by the spec, though, so I'm
less
> than convinced.
Following the diagram of specific behaviors allowed at each
level is good evidence that these phenomena don't *define*
serializable:
"NOTE 53 * The exclusion of these phenomena for SQL-transactions
executing at isolation level SERIALIZABLE is a consequence of the
requirement that such transactions be serializable."
> An appropriate way to prevent the problem is probably for the
> transaction that changes the deposit_date to take out a
write-excluding
> lock on the receipts table before it does so.
Well, a serializable transaction operating to standard would probably
take out a write-excluding lock on the control table row when it is
read.  This would block the update to the control table until
completion of any pending receipts on the old date.  The blocked
update would then take out a read-excluding lock before updating the
row, which would then block receipt transactions looking to check the
date.  As soon as the update to the control table is committed, you
can see the new date, and you can have confidence that the old date's
receipts will all show on a SELECT.
Again, I'm not suggesting that we change the behavior of PostgreSQL to
match this, but that we document the difference so that those looking
to switch to PostgreSQL from databases which provide true serializable
transactions know that they have to explicitly lock rows to maintain a
coherent view of the data.  In the queries shown in the original post,
the INSERT of the receipts could read the deposit date FOR SHARE to
provide the equivalent functionality, although they would have to be
rejiggered a bit, since that isn't allowed in subqueries.
This isn't some hypothetical "maybe some day some product might
implement this, but it'll never catch on" sort of thing -- Microsoft
and Sybase SQL Server had this from version 1.  I used it from 1990
until the conversion to PostgreSQL over the last couple years. 
Serializable transactions worked as advertised.  Was there more
blocking than PostgreSQL?  Yes.  Were there more deadlocks than
PostgreSQL?  Yes.  Did it impact performance?  Well, PostgreSQL is
faster by enough that users commented that the applications seemed
"snappier" when we switched the database underneath them from Sybase
to PostgreSQL.
I'm going on second-hand information here, but I'm told that IBM DB2
has used similar techniques to provide true serializable transactions
for even longer.
I'm somewhat mystified at the reaction this topic gets here.  :-/
-Kevin

Kevin Grittner wrote:
> This isn't some hypothetical "maybe some day some product might
> implement this, but it'll never catch on" sort of thing -- Microsoft
> and Sybase SQL Server had this from version 1.  I used it from 1990
> until the conversion to PostgreSQL over the last couple years. 
>   
Have you ever used serializable transactions with Sybase? The locking is 
actually based on memory-pages and you end-up with deadlocks if you 
don't pad your data structures to prevent false sharing. Oracle also 
provides SI like Postgres and I don't think they are doing that bad.
> I'm going on second-hand information here, but I'm told that IBM DB2
> has used similar techniques to provide true serializable transactions
> for even longer.
>  
> I'm somewhat mystified at the reaction this topic gets here.  :-
I am somewhat mystified by the interest some people still have in 
serializable transactions. Why don't users program the application to 
deal with a lower isolation (actually I think they do)?

But I am probably missing the point which was to fix the doc?
Emmanuel

-- 
Emmanuel Cecchet
FTO @ Frog Thinker 
Open Source Development & Consulting
--
Web: http://www.frogthinker.org
email: manu@frogthinker.org
Skype: emmanuel_cecchet

>>> Emmanuel Cecchet <manu@frogthinker.org> 12/23/08 8:59 AM >>> 
> Kevin Grittner wrote:
>> This isn't some hypothetical "maybe some day some product might
>> implement this, but it'll never catch on" sort of thing --
Microsoft
>> and Sybase SQL Server had this from version 1.  I used it from 1990
>> until the conversion to PostgreSQL over the last couple years. 
>
> Have you ever used serializable transactions with Sybase?
Every day for over 15 years.
> The locking is 
> actually based on memory-pages and you end-up with deadlocks if you 
> don't pad your data structures to prevent false sharing.
We only padded one table, which we were using to assign sequence
numbers.  Eventually they did come out with support for row level
locking, which could be chosen on a table by table basis, which
eliminated the need for the padding columns.  We didn't go to
row-level locking for all tables because the performance hit was
significant -- worse than the blocking.  Blocking was occasionally an
issue.  Deadlocks were initially a problem, but they can be handled
automatically with resubmit, which we eventually covered gracefully,
and they weren't an issue for us after that.
> Oracle also 
> provides SI like Postgres and I don't think they are doing that bad.
I don't quire understand.  Could you clarify? 
>> I'm going on second-hand information here, but I'm told that IBM
DB2
>> has used similar techniques to provide true serializable
transactions
>> for even longer.
>>
>> I'm somewhat mystified at the reaction this topic gets here.  :-
> I am somewhat mystified by the interest some people still have in 
> serializable transactions. Why don't users program the application to

> deal with a lower isolation (actually I think they do)?
There really are good reasons.  I'm not up to going through that now,
but if there is genuine interest in the topic perhaps I can follow up
later.
> But I am probably missing the point which was to fix the doc?
Thank you!
-Kevin

Kevin Grittner wrote:
>>>> Emmanuel Cecchet <manu@frogthinker.org> 12/23/08 8:59 AM >>> 
>> I am somewhat mystified by the interest some people still have in 
>> serializable transactions. Why don't users program the application to
> 
>> deal with a lower isolation (actually I think they do)?
>  
> There really are good reasons.  I'm not up to going through that now,
> but if there is genuine interest in the topic perhaps I can follow up
> later.

Well, the reason why people rely on isolation provided by database in 
general is to make it easier to develop applications. One less thing to 
worry about. That's why people use RDBMS, transactions, etc. to begin with.

>> But I am probably missing the point which was to fix the doc?
>  
> Thank you!

If you have a concrete suggestion (= patch) for the documentation, I'm 
all ears.

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

>>> Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> 12/23/08
9:47 AM >>> 
> Kevin Grittner wrote:
>>>>> Emmanuel Cecchet <manu@frogthinker.org> 12/23/08 8:59 AM >>> 
>>> Why don't users program the application to
>>> deal with a lower isolation (actually I think they do)?
>>  
>> There really are good reasons.  I'm not up to going through that
now,
>> but if there is genuine interest in the topic perhaps I can follow
up
>> later.
> 
> Well, the reason why people rely on isolation provided by database in

> general is to make it easier to develop applications. One less thing
to 
> worry about. That's why people use RDBMS, transactions, etc. to begin
with.
This is the heart of it.  The argument is getting made that you don't
need serializable transactions because you can duplicate the
concurrency control with a combination of read_committed transactions
and explicit lock requests.  I could also duplicate the functionality
of a DBMS with a bunch of disk files and custom, hard-coded access
logic, but I sure wouldn't want to do so.
> If you have a concrete suggestion (= patch) for the documentation,
I'm 
> all ears.
Well, I figured I should try to get a consensus here before submitting
a patch.  Last time I tried submitting a simple patch to remove the
line about the PostgreSQL community not knowing about any other
databases which use predicate locking, I got shot down hard.
Does the phantom receipt example from the original post seem like a
reasonable thing to include in the doc patch?  Does someone have a
more comprehensive summary of where the issues are than I've been able
to generate so far?
The patch should also include information on workarounds.  I'd be
inclined to frame them in terms of how to duplicate the behavior of
serializable transactions on other databases from which the reader
might be converting, which would start with using SELECT FOR SHARE for
any SELECT within a serializable transaction.  That doesn't cover
everything, because, unlike Sybase, et al, it doesn't block
conflicting INSERTs.  I'm not sure I have a firm conceptual grasp on
when and how that renders the SELECT FOR SHARE technique incomplete,
but I could try to think it through.  If someone already has
comprehensive guidelines on that, it would save time and might improve
the quality of the docs.
-Kevin

"Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:

>>>> Emmanuel Cecchet <manu@frogthinker.org> 12/23/08 8:59 AM >>> 
>> Have you ever used serializable transactions with Sybase?
>  
> Every day for over 15 years.

Afaict doing a few google searches Sybase doesn't do predicate locking either.
It would very much surprise me if they did since they've always had the most
primitive locking infrastructure of the three major databases. Locking records
or pages isn't going to provide true standards-compliant serializable
transactions in the way you're describing.

Predicate locking means being able to lock records which don't actually exist
yet. Ie, locking all records "WHERE COLUMN=0" even if there are no such
records. This has to block any other transaction from inserting such a record
or updating another record to set COLUMN to 0.

>> Oracle also provides SI like Postgres and I don't think they are doing that
>> bad.
>  
> I don't quire understand.  Could you clarify?

The point is Oracle doesn't provide this kind of true serializable isolation
and people still find it useful. In fact Sybase and DB2 also don't provide
true serializable transactions -- nobody does. It's a fantasy.

> There really are good reasons.  I'm not up to going through that now,
> but if there is genuine interest in the topic perhaps I can follow up
> later.

I suppose I'm curious whether you're mistaken and your app isn't safe on
Sybase because it's depending on truly serializable transactions and Sybase
isn't doing that, or if you have examples of transactions which Sybase
provides proper serialized semantics for but Postgres doesn't.

>> But I am probably missing the point which was to fix the doc?

But missing the point and having pointless arguments is so much more fun than
documentation writing :)

--  Gregory Stark EnterpriseDB          http://www.enterprisedb.com Ask me about EnterpriseDB's RemoteDBA services!

>>> Gregory Stark <stark@enterprisedb.com> wrote: 
> "Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
>>>>> Emmanuel Cecchet <manu@frogthinker.org> 12/23/08 8:59 AM >>> 
>>> Have you ever used serializable transactions with Sybase?
>>  
>> Every day for over 15 years.
> 
> Afaict doing a few google searches Sybase doesn't do predicate
locking 
> either.
> It would very much surprise me if they did since they've always had
the most
> primitive locking infrastructure of the three major databases.
Locking 
> records
> or pages isn't going to provide true standards-compliant
serializable
> transactions in the way you're describing.
> 
> Predicate locking means being able to lock records which don't
actually 
> exist
> yet. Ie, locking all records "WHERE COLUMN=0" even if there are no
such
> records. This has to block any other transaction from inserting such
a 
> record
> or updating another record to set COLUMN to 0.
The page locking provides this because every index page or data page
the serializable transaction looks at is locked against updates until
the end of the transaction.  If it can see all the COLUMN=0 rows
through an index, the index locks protect the transaction.  If a table
scan is required, the entire table is locked against all
modifications.  (That's right, it is not unusual to have entire tables
locked against any modification until the end of a database
transaction.)
>>> Oracle also provides SI like Postgres and I don't think they are
doing that
>>> bad.
>>  
>> I don't quire understand.  Could you clarify?
> 
> The point is Oracle doesn't provide this kind of true serializable
isolation
> and people still find it useful.
Sure, and I find PostgreSQL useful.  I'm not proposing to change it.
> In fact Sybase and DB2 also don't provide
> true serializable transactions -- nobody does. It's a fantasy.
They do.  They have for over 15 years.  If people will read it, I'll
try to find the a web page where they give all the details of the
strategy.
>> There really are good reasons.  I'm not up to going through that
now,
>> but if there is genuine interest in the topic perhaps I can follow
up
>> later.
> 
> I suppose I'm curious whether you're mistaken and your app isn't safe
on
> Sybase because it's depending on truly serializable transactions and
Sybase
> isn't doing that, or if you have examples of transactions which
Sybase
> provides proper serialized semantics for but Postgres doesn't.
All the examples provided in this thread would be handled by Sybase
with proper serializable semantics.  When I proposed changing the docs
to omit the reference to our lack of knowledge about other database
products, there was a full example of code that didn't serialize
according to the mathematical definition.  I cut and pasted into
Sybase and provided the results -- a deadlock.
Can you provide any example or logical explanation of where the
technique I outline above (locking against modification for every
index and data page read during the transaction until the end of the
transaction) would NOT provide true serializable behavior?  (Keep in
mind that that's the broad stroke overview -- the full details include
various lock escalation techniques, etc.)
>>> But I am probably missing the point which was to fix the doc?
> 
> But missing the point and having pointless arguments is so much more
fun 
> than
> documentation writing :)
Frankly, I prefer other sports.   :-(
-Kevin

Reading the spec it does seem our initial statement "The SQL standard defines
four levels of transaction isolation in terms of three phenomena that must be
prevented between concurrent transactions" is not accurate.

The spec defines the first three modes in terms of P1,P2,P3 but serializable
is defined, as Kevin describes, as literally serializable. It is included in
the table but with the note:
 NOTE 71 — The exclusion of these phenomena for SQL-transactions executing at isolation level SERIALIZABLE is a
consequenceof the requirement that such transactions be serializable. 

So it's clear that that's not the definition. Excluding P1,P2,P3 is necessary
but not sufficient to meet the spec's definition of Serializable.



"Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:

>>>> Gregory Stark <stark@enterprisedb.com> wrote:
>> Afaict doing a few google searches Sybase doesn't do predicate locking >
>> either.
>
> The page locking provides this because every index page or data page
> the serializable transaction looks at is locked against updates until
> the end of the transaction.  If it can see all the COLUMN=0 rows
> through an index, the index locks protect the transaction.  If a table
> scan is required, the entire table is locked against all
> modifications.  (That's right, it is not unusual to have entire tables
> locked against any modification until the end of a database
> transaction.)


Ah, so they don't actually use the term predicate locking which is why my
google-fu was inadequate. I'm not sure if this is technically "predicate
locking" or not. It sounds like it locks a whole lot more than just the
predicate.

> All the examples provided in this thread would be handled by Sybase
> with proper serializable semantics.  When I proposed changing the docs
> to omit the reference to our lack of knowledge about other database
> products, there was a full example of code that didn't serialize
> according to the mathematical definition.  I cut and pasted into
> Sybase and provided the results -- a deadlock.
>
> Can you provide any example or logical explanation of where the
> technique I outline above (locking against modification for every
> index and data page read during the transaction until the end of the
> transaction) would NOT provide true serializable behavior?  (Keep in
> mind that that's the broad stroke overview -- the full details include
> various lock escalation techniques, etc.)

I imagine they preemptively escalate to locking the table if you're going to
do a sequential scan? Otherwise an inserter might insert on a page you haven't
read yet (and therefore haven't locked yet)?

--  Gregory Stark EnterpriseDB          http://www.enterprisedb.com Ask me about EnterpriseDB's RemoteDBA services!

On Tue, 23 Dec 2008, Kevin Grittner wrote:

> The page locking provides this because every index page or data page
> the serializable transaction looks at is locked against updates until
> the end of the transaction.  If it can see all the COLUMN=0 rows
> through an index, the index locks protect the transaction.  If a table
> scan is required, the entire table is locked against all
> modifications.  (That's right, it is not unusual to have entire tables
> locked against any modification until the end of a database
> transaction.)

Well, predicate locking for serializable also should only lock the
appropriate conditions. Getting a deadlock between two serializable
transactions for conditions that can be serialized would seemingly also be
disallowed by the definition of serializable since there would exist no
serial ordering of the transactions that has that effect.

>>> Gregory Stark <stark@enterprisedb.com> wrote: 
> "Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
>>>>> Gregory Stark <stark@enterprisedb.com> wrote: 
>>> Afaict doing a few google searches Sybase doesn't do predicate
locking >
>>> either.
>>  
>> The page locking provides this because every index page or data
page
>> the serializable transaction looks at is locked against updates
until
>> the end of the transaction.  If it can see all the COLUMN=0 rows
>> through an index, the index locks protect the transaction.  If a
table
>> scan is required, the entire table is locked against all
>> modifications.  (That's right, it is not unusual to have entire
tables
>> locked against any modification until the end of a database
>> transaction.)
> 
> Ah, so they don't actually use the term predicate locking which is
why my
> google-fu was inadequate. I'm not sure if this is technically
"predicate
> locking" or not. It sounds like it locks a whole lot more than just
the
> predicate.
Well, I'm not sure whether it is or not; it's a matter of definition. 
If predicate locking is required for true serializable transactions,
and this provides true serializable transactions, it must be, eh? 
Also, an argument could be made that if it locks every page which must
be viewed for execution based on the search predicates, it is doing
predicate locking -- if only indirectly.
>> All the examples provided in this thread would be handled by Sybase
>> with proper serializable semantics.  When I proposed changing the
docs
>> to omit the reference to our lack of knowledge about other database
>> products, there was a full example of code that didn't serialize
>> according to the mathematical definition.  I cut and pasted into
>> Sybase and provided the results -- a deadlock.
>>  
>> Can you provide any example or logical explanation of where the
>> technique I outline above (locking against modification for every
>> index and data page read during the transaction until the end of
the
>> transaction) would NOT provide true serializable behavior?  (Keep
in
>> mind that that's the broad stroke overview -- the full details
include
>> various lock escalation techniques, etc.)
> 
> I imagine they preemptively escalate to locking the table if you're
going to
> do a sequential scan? Otherwise an inserter might insert on a page
you 
> haven't
> read yet (and therefore haven't locked yet)?
I believe they do go straight to the table lock for a table scan, but
it isn't necessary for full semantics that the transaction lock all
pages in advance.  For most purposes the serializable transaction can
proceed to lock pages as it gets to them.  It will block or deadlock
if a conflict arises.  The transaction may serialize behind a
transaction which started later and read some page it hadn't gotten to
yet, but that doesn't violate the spec or cause any anomalies.  The
key phrase in the spec here is "produces the same effect as *some*
serial execution" [emphasis added].
It will escalate from page locks to a table lock if a (configurable)
number or percentage of a table's pages get locked.
-Kevin

>>> Stephan Szabo <sszabo@megazone.bigpanda.com> wrote: 
> On Tue, 23 Dec 2008, Kevin Grittner wrote:
> 
>> The page locking provides this because every index page or data
page
>> the serializable transaction looks at is locked against updates
until
>> the end of the transaction.  If it can see all the COLUMN=0 rows
>> through an index, the index locks protect the transaction.  If a
table
>> scan is required, the entire table is locked against all
>> modifications.  (That's right, it is not unusual to have entire
tables
>> locked against any modification until the end of a database
>> transaction.)
> 
> Well, predicate locking for serializable also should only lock the
> appropriate conditions. Getting a deadlock between two serializable
> transactions for conditions that can be serialized would seemingly
also be
> disallowed by the definition of serializable since there would exist
no
> serial ordering of the transactions that has that effect.
Clever.  If a DBMS is capable of reporting that it was unable to
serialize a transaction in a situation where there is a logical
possibility that a different implementation might have succeeded, it
hasn't implemented true serializable transactions?  That strikes me as
being on a level with Codd's assertion that any database which takes
two different statements which can be proven to be logically identical
and runs one with a different plan than the other should not be called
relational.  (i.e., possibly true from a technical perspective, but
hardly useful in the real world.)
Perhaps it would be best to accept this as proof that there is no
current DBMS implementing true serializable transactions and move on
to the issue of documenting real difference between PostgreSQL other
products which come closer to compliance, so that real people
converting from those products don't suffer real production problems. 
As I see it, that's what matters.
-Kevin

On Tue, 2008-12-23 at 00:42 -0500, Emmanuel Cecchet wrote:
> I still don't 
> get why people would use SERIALIZABLE since there is no efficient 
> implementation of it.

If they need true serializable transactions, and don't care about
efficiency.

Regards,Jeff Davis

> The page locking provides this because every index page or data page
> the serializable transaction looks at is locked against updates until
> the end of the transaction.  If it can see all the COLUMN=0 rows
> through an index, the index locks protect the transaction.  If a table
> scan is required, the entire table is locked against all
> modifications.  (That's right, it is not unusual to have entire tables
> locked against any modification until the end of a database
> transaction.)

You've mentioned a couple of times that you're surprised by the
reaction of the community to your proposed documentation changes.  I
have (a more muted version of) the same reaction as several previous
posters, and I think in the context of this paragraph I can explain
why.

If we were to construct a database that had one giant lock for the
entire database so that only a single query could execute at one time,
transactions would be serializable (because they'd in fact be
serialized).  However, performance would suck.  Therefore, database
developers and researchers have spent the last twenty (or more?) years
trying to come up with ways to allow multiple transactions to execute
in parallel while maintaining the appearance of serialization.
They've done this by introducing lower level locks: table-level,
page-level, row-level.  For most users, the artifacts that have been
introduced by these fine-grained locks are outweighed by the
performance benefits of greater concurrency - but, as you point out,
not necessarily always.

I don't think I can overstate the extent to which fine-grained locking
is viewed as a good thing.  It wouldn't surprise me to find out that
the locking behavior that you're relying on in Sybase is one which
some group of Sybase developers (if there still are any) are busily
laboring to eliminate.  I think you can see this reflected in Greg
Stark's comment as well: "It would very much surprise me if they did
since they've always had the most primitive locking infrastructure of
the three major databases."

With respect to predicate locking, what you're describing is NOT
predicate locking.  It's coarse-grained locking that largely or
completely obviates the need for predicate locking by greatly reducing
concurrency.  Now, from the point of view of the application developer
who needs very strong serializability guarantees but doesn't care
about concurrency, that's six of one, half a dozen of the other, but
to me that's the opposite of the typical situation.  Maybe our
documentation could say something along the lines of "PostgreSQL's
MVCC framework and row-level locking permit a greater degree of
concurrency than some other databases.  Even when the transaction
isolation level is set to serializable, serialization anomalies can
occur in the following situations.  When it is important to prevent
these anomalies, explicit row-level or table-level locking can be used
at the expense of reduced concurrency."

...Robert

On Tue, 2008-12-23 at 10:10 -0600, Kevin Grittner wrote:

> Well, I figured I should try to get a consensus here before submitting
> a patch.  Last time I tried submitting a simple patch to remove the
> line about the PostgreSQL community not knowing about any other
> databases which use predicate locking, I got shot down hard.

The docs got changed though.

I think the current docs make too much of a deal about how hard it is to
do predicate locking in databases. Most RDBMS use predicate locking via
indexes, ie the locking happens in the index. One might also argue that
it is potentially more efficient design, as TPC-C shows, though such
cases of application scalability are rare in the extreme and the utility
of MVCC is by far the best general approach in terms of ease of use and
performance.

The example in the docs is not a realistic example, so your new one is
useful.

I would want you to update it though to show how use of row level locks
can be used to enforce correct behaviour when required, so provide a
problem and its solution. It will b useful for people moving from
systems like Sybase that use locking often fall foul of the *lack* of
locking in MVCC and write programs that won't work correctly as a
result.

-- Simon Riggs           www.2ndQuadrant.comPostgreSQL Training, Services and Support

>>> "Robert Haas" <robertmhaas@gmail.com> wrote: 
> For most users, the artifacts that have been
> introduced by these fine-grained locks are outweighed by the
> performance benefits of greater concurrency - but, as you point out,
> not necessarily always.
That's what I don't understand.  I never did point that out.  I never
suggested it.  I never requested a change to the software.  I just
suggested that we document the artifacts.
Ah, well; thanks for the feedback.
> With respect to predicate locking, what you're describing is NOT
> predicate locking.
I never would have considered it to be such except for some people
insisting that a true serializable implementation is impossible
without predicate locking.  Either that assertion is false or this is
a form of predicate locking, crude as it might be.
> Maybe our
> documentation could say something along the lines of "PostgreSQL's
> MVCC framework and row-level locking permit a greater degree of
> concurrency than some other databases.  Even when the transaction
> isolation level is set to serializable, serialization anomalies can
> occur in the following situations.  When it is important to prevent
> these anomalies, explicit row-level or table-level locking can be
used
> at the expense of reduced concurrency."
That's responsive to my concern and nicely worded.  Thanks.
-Kevin

>>> Simon Riggs <simon@2ndQuadrant.com> wrote: 

> On Tue, 2008-12-23 at 10:10 -0600, Kevin Grittner wrote:
> 
> I think the current docs make too much of a deal about how hard it is
to
> do predicate locking in databases. Most RDBMS use predicate locking
via
> indexes, ie the locking happens in the index. One might also argue
that
> it is potentially more efficient design, as TPC-C shows, though such
> cases of application scalability are rare in the extreme and the
utility
> of MVCC is by far the best general approach in terms of ease of use
and
> performance.
> 
> The example in the docs is not a realistic example, so your new one
is
> useful.
The one currently in the docs is the simplest case I can see of an
anomaly which leaves the database in the wrong state after all the
commits go through.  I think it should probably be kept for that
reason.  The out-of-sequence appearance of changes before all commits
happen seems much more likely to bite people, though.  Agreed?
> I would want you to update it though to show how use of row level
locks
> can be used to enforce correct behaviour when required, so provide a
> problem and its solution. It will b useful for people moving from
> systems like Sybase that use locking often fall foul of the *lack*
of
> locking in MVCC and write programs that won't work correctly as a
> result.
Understood and agreed.
-Kevin

Jeff Davis wrote:
> On Tue, 2008-12-23 at 00:42 -0500, Emmanuel Cecchet wrote:
>   
>> I still don't 
>> get why people would use SERIALIZABLE since there is no efficient 
>> implementation of it.
>>     
>
> If they need true serializable transactions, and don't care about
> efficiency.
>   
Is there such people who really understand the thing and don't complain 
about the performance? ;-)

Happy holidays,
Emmanuel

>>> Emmanuel Cecchet <manu@frogthinker.org> 12/22/08 11:42 PM >>>
> If you want to know how to build SERIALIZABLE with a database that 
> provides SI (Snapshot Isolation), read 
> http://portal.acm.org/citation.cfm?doid=1376616.137669
The link didn't seem to work for me, but I think I found the article
you meant:  "Serializable Isolation for Snapshot Databases"
by Michael J. Cahill, et al

An interesting work.  If nothing else, it will help flesh out the
documentation of anomalies.  If the PostgreSQL community ever
does want to better approach true serializable behavior, this
should provide a good theoretical basis.
Thanks very much for the cite.
> I still don't 
> get why people would use SERIALIZABLE since there is no efficient 
> implementation of it.
Read the last paragraph of the secion 1 (Introduction)
of the article you just cited.
-Kevin

Hi Kevin,

> The link didn't seem to work for me, but I think I found the article
> you meant:  "Serializable Isolation for Snapshot Databases"
> by Michael J. Cahill, et al
>
> An interesting work.  If nothing else, it will help flesh out the
> documentation of anomalies.  If the PostgreSQL community ever
> does want to better approach true serializable behavior, this
> should provide a good theoretical basis.
>   
Sorry for the broken link. Yes this is the paper.
Note that the paper was not necessarily enthusiastically received by the 
community when presented at the conference. While this is an interesting 
academic paper, it's practicality left a majority of the audience 
perplex. There was an interesting comment by Oracle folks: Oracle does 
not provide serializability but only snapshot isolation, and still users 
prefer to 'downgrade' to read committed for better performance. The 
Oracle guys experience seemed to indicate that there was no need for 
serializability (well, that's also less work for them ;-)) in their 
customer base.
Having both a foot in academia and in industry, I understand the 
intellectual interest for serializability on the academic side, but I 
still have not seen a single use case in industry where this was a 
requirement (but my db experience is probably narrow).

Have nice serializable holidays ;-)
manu

-- 
Emmanuel Cecchet
FTO @ Frog Thinker 
Open Source Development & Consulting
--
Web: http://www.frogthinker.org
email: manu@frogthinker.org
Skype: emmanuel_cecchet

Robert Haas wrote:
>> ... serializable transaction ...
> If we were to construct a database that had one giant lock for the
> entire database so that only a single query could execute at one time,
> transactions would be serializable (because they'd in fact be
> serialized).  However, performance would suck.  

I wonder if this giant-lock-for-isolation-level-serializable
is a mode postgres should support.  ISTM it would meet the
letter of the spec, and at least some of the people using
"transaction isolation level serializable" are doing so precisely
because they *want* the database to deal with all possible
serialization issues, and accepting performance penalties.

On Dec 24, 2008, at 6:46 PM, Ron Mayer <rm_pg@cheapcomplexdevices.com>  
wrote:

> Robert Haas wrote:
>>> ... serializable transaction ...
>> If we were to construct a database that had one giant lock for the
>> entire database so that only a single query could execute at one  
>> time,
>> transactions would be serializable (because they'd in fact be
>> serialized).  However, performance would suck.
>
> I wonder if this giant-lock-for-isolation-level-serializable
> is a mode postgres should support.  ISTM it would meet the
> letter of the spec, and at least some of the people using
> "transaction isolation level serializable" are doing so precisely
> because they *want* the database to deal with all possible
> serialization issues, and accepting performance penalties.

No. :-)

Cheers,

...Robert

>>> Emmanuel Cecchet <manu@frogthinker.org> wrote: 
> There was an interesting comment by Oracle folks: Oracle does 
> not provide serializability but only snapshot isolation, and still
users 
> prefer to 'downgrade' to read committed for better performance. The 
> Oracle guys experience seemed to indicate that there was no need for

> serializability (well, that's also less work for them ;-)) in their 
> customer base.
Although I note that, while this work was done in 2006 at the
University of Sidney, Mr. Cahill is now an employee of Oracle
Corporation....
The interesting thing about this technique is that it works without
the kind of blocking which is the bane of other implementation
techniques.  Reads don't block writes or vice versa.  In my receipt
example, the fact that there is a transitory state where the view of
the data would not be consistent would cause no problems unless
someone actually tried to view the data within that (probably very
small) window of time.
-Kevin

On Tuesday 23 December 2008 16:51:03 Kevin Grittner wrote:
> If you look at the serializable queries in the original post for this
> thread, it's not hard to see that this standard is not met.  The
> insert of receipt 3 appears to happen before the update of the control
> record, since it has the old deposit date.  The transaction which
> selects from both tables sees the update to the control record, so it
> must come after that.  Yet it doesn't see the results of the first
> transaction.  There is no sequence of serial execution which is
> consistent with the behavior.

I am not sure yet whether or not your complaint is valid, but your arguments
are not very rigid.

Serializability is not defined in terms of what is visible, but what the state
of the database is.  If you can order the transactions without overlap so
that the state of the database is the same as in your original schedule, the
schedule is serializable.  It is not of concern what was "visible" in
between.  You may, however, be able to transform that argument to proving
that a phantom read is possible, which is how the SQL standard ultimately
defines serializability.

Also note that discussing what is visible necessarily implies the existence of
another transaction that does the reading, and that transaction does not
appear to be defined in your arguments.

>>> Peter Eisentraut <peter_e@gmx.net> wrote:
> On Tuesday 23 December 2008 16:51:03 Kevin Grittner wrote:
>> If you look at the serializable queries in the original post for
this
>> thread, it's not hard to see that this standard is not met.  The
>> insert of receipt 3 appears to happen before the update of the
control
>> record, since it has the old deposit date.  The transaction which
>> selects from both tables sees the update to the control record, so
it
>> must come after that.  Yet it doesn't see the results of the first
>> transaction.  There is no sequence of serial execution which is
>> consistent with the behavior.
> 
> I am not sure yet whether or not your complaint is valid, but your
arguments 
> are not very rigid.
> 
> Serializability is not defined in terms of what is visible, but what
the 
> state of the database is.
I don't read the standard that way.
I'll repeat the relevant part of the standard:
"The execution of concurrent SQL-transactions at isolation level
SERIALIZABLE is guaranteed to be serializable. A serializable
execution is defined to be an execution of the operations of
concurrently executing SQL-transactions that produces the same
effect as some serial execution of those same SQL-transactions. A
serial execution is one in which each SQL-transaction executes to
completion before the next SQL-transaction begins."
There is no end-to-end sequence in which the transactions listed in my
original email can be run that will produce the same effect that you
get within PostgreSQL, at least if you consider the results of a
SELECT statement to be significant.  (I do.)
> If you can order the transactions without overlap so 
> that the state of the database is the same as in your original
schedule, the 
> schedule is serializable.  It is not of concern what was "visible" in

> between.
On what do you base that assertion?
> You may, however, be able to transform that argument to proving 
> that a phantom read is possible, which is how the SQL standard
ultimately 
> defines serializability.
No it isn't.  The above quoted text is.
> Also note that discussing what is visible necessarily implies the
existence 
> of 
> another transaction that does the reading, and that transaction does
not 
> appear to be defined in your arguments.
It was this one, in my original post:
start transaction isolation level serializable ;
select * from ctl;
-- (deposit_date shows as 2008-12-23)
select * from receipt;
-- (Only receipts 1 and 2 show for 2008-12-22.)
commit;
-Kevin

>>> Peter Eisentraut <peter_e@gmx.net> wrote:
> Serializability is not defined in terms of what is visible, but what
the 
> state of the database is.
A belated thought on this: It would be easy enough to add a
daily_receipt_total table to the example to capture the result of the
query, instead of assuming that it merely prints on the daily bank
deposit report.  That would certainly meet your test of ending with an
invalid database state after all the transactions commit.
-Kevin

Sorry for top posting -- damn phone.

The standard defines all the *other* transaction isolations in terms  
of phantom reads, dirty reads, and, uh one other phenomenon. But it  
defines serializability literally, as the transactions having the same  
effect as ift they were run serially. It explicitly says the fact that  
phantom reads can't occur in serializable is only a consequence of tfe  
definition.

And I don't see why you discard "visibility" as unimportant. All the  
transaction isolations are defined in terms of the results if the  
transactions. Those results include both the database state and the  
data returned by the queries. Otherwise "phantom read" is a  
meaningless concept.

-- 
Greg


On 29 Dec 2008, at 07:20, Peter Eisentraut <peter_e@gmx.net> wrote:

> On Tuesday 23 December 2008 16:51:03 Kevin Grittner wrote:
>> If you look at the serializable queries in the original post for this
>> thread, it's not hard to see that this standard is not met.  The
>> insert of receipt 3 appears to happen before the update of the  
>> control
>> record, since it has the old deposit date.  The transaction which
>> selects from both tables sees the update to the control record, so it
>> must come after that.  Yet it doesn't see the results of the first
>> transaction.  There is no sequence of serial execution which is
>> consistent with the behavior.
>
> I am not sure yet whether or not your complaint is valid, but your  
> arguments
> are not very rigid.
>
> Serializability is not defined in terms of what is visible, but what  
> the state
> of the database is.  If you can order the transactions without  
> overlap so
> that the state of the database is the same as in your original  
> schedule, the
> schedule is serializable.  It is not of concern what was "visible" in
> between.  You may, however, be able to transform that argument to  
> proving
> that a phantom read is possible, which is how the SQL standard  
> ultimately
> defines serializability.
>
> Also note that discussing what is visible necessarily implies the  
> existence of
> another transaction that does the reading, and that transaction does  
> not
> appear to be defined in your arguments.
>
> -- 
> Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers

Greg Stark wrote:
> And I don't see why you discard "visibility" as unimportant. All the 
> transaction isolations are defined in terms of the results if the 
> transactions. Those results include both the database state and the data 
> returned by the queries. Otherwise "phantom read" is a meaningless concept.

Basically, if he wants to make a rigid argument that some scenario 
violates the serializability promise, then it is necessary to prove:

(1) There is no serial schedule for the set of transactions that 
achieves the same outcome.  (This proof is probably hard to work out, as 
many "there is no" proofs are.)

- or -

(2) A phantom read situation occurs.

His original argument uses terms like "window" where something is 
"visible" (to whom?), which can probably be transformed into a proof for 
(2), but is not convincing (to me) by itself.

>>> Peter Eisentraut <peter_e@gmx.net> wrote: 
> Greg Stark wrote:
>> And I don't see why you discard "visibility" as unimportant. All
>> the transaction isolations are defined in terms of the results if
>> the transactions. Those results include both the database state and
>> the data returned by the queries. Otherwise "phantom read" is a
>> meaningless concept.
> 
> Basically, if he wants to make a rigid argument that some scenario 
> violates the serializability promise, then it is necessary to prove:
> 
> (1) There is no serial schedule for the set of transactions that 
> achieves the same outcome.
> 
> - or -
> 
> (2) A phantom read situation occurs.
Agreed, except that (2) is a subset of (1), so (1) alone is
sufficient.  (How can a read not be repeatable if there are no
concurrent transactions?)
I feel that I did provide a proof that the transactions couldn't
represent any serial execution in my original email.  This seems to be
disputed with the argument that a SELECT from a database is not
required to provide coherent data that represents some point in the
serializable stream of transactions.  I disagree, but as I pointed out
previously, it is trivial to capture the results of any such query
into a table and thereby persist the problem within the database.
Here we go.  I've labeled the transactions consistently with new
thread I started trying to characterize the full scope of issues and
workarounds.
-- setup
drop if exists ctl, receipt, receipt_totals;
create table ctl (k text not null primary key, deposit_date date not
null);
insert into ctl values ('receipt', date '2008-12-22');
create table receipt (receipt_no int not null primary key,
deposit_date date not null, amount numeric(13,2));
insert into receipt values (1, (select deposit_date from ctl where k =
'receipt'), 1.00);
insert into receipt values (2, (select deposit_date from ctl where k =
'receipt'), 2.00);
create table receipt_totals (deposit_date date not null primary key,
next_date date not null, deposit_total numeric(13,2) not null);

-- connection 1 (start of T0)
start transaction isolation level serializable;
insert into receipt values (3, (select deposit_date from ctl where k =
'receipt'), 4.00);

-- connection 2 (T1)
start transaction isolation level serializable;
update ctl set deposit_date = date '2008-12-23' where k = 'receipt';
commit transaction;

-- connection 2 (TN version 1)
start transaction isolation level serializable;
select * from ctl;
-- (deposit_date shows as 2008-12-23)
select * from receipt where deposit_date = date '2008-12-22';
-- (Only receipts 1 and 2 show for 2008-12-22.)
commit transaction;

-- connection 2 (TN version 2)
start transaction isolation level serializable;
insert into receipt_totals select r.deposit_date, c.deposit_date, sum(amount)   from ctl c join receipt r     on (
r.deposit_date< c.deposit_date      and not exists          (            select * from receipt r2              where
r2.deposit_date< c.deposit_date                and r2.deposit_date > r.deposit_date          )        )   group by
r.deposit_date,c.deposit_date;
 
commit transaction;

-- connection 1 (end of T0)
commit transaction;
After all this is done, a select from receipt_totals shows:deposit_date | next_date  | deposit_total
--------------+------------+---------------2008-12-22   | 2008-12-23 |          3.00
(1 row)
Here goes the proof, although I'm not going to be overly formal in the
language.
(1)  If these transactions were serialized, T0 must come before T1,
because T0 uses the ctl.deposit_date before it is updated by T1.

(2)  If these transactions were serialized, T1 must come before TN
(either version), because the TN transactions see the ctl.deposit_date
set by T1.
(3)  If these transactions were serialized, the TN transactions must
come before T0, since they don't see the row inserted by T0.
(4)  Since serialization requires that T0 < T1 < TN < T0 (comparing
time sequence) the transactions cannot be considered serialized.
-Kevin

>>> Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> wrote:
> If you have a concrete suggestion (= patch) for the documentation,
I'm
> all ears.

I'm still working on section "Serializable Isolation versus True
Serializability", but here are all the changes I can see which precede
it.  Has the review of the SQL specs convinced everyone that this much
is appropriate?

It also seems like the "Data Consistency Checks at the Application
Level" section could use a little more detail.  Since referential
integrity checks are so well understood, and don't work reliably under
snapshot serialization without explicit locks, perhaps that could be
added?

-Kevin

On Wednesday 31 December 2008 02:33:26 Kevin Grittner wrote:
> I'm still working on section "Serializable Isolation versus True
> Serializability", but here are all the changes I can see which precede
> it.  Has the review of the SQL specs convinced everyone that this much
> is appropriate?

I don't agree with these changes.  You make it sound like serializability is 
an additional condition on the serializable isolation level on top of the 
no-phantom-reads condition.  I think that is not true, both mathematically 
and from the wording of the SQL standard.  It is an equivalent condition or a 
consequence, depending on how you view it.

On Tuesday 30 December 2008 19:28:01 Kevin Grittner wrote:
> Here we go.  I've labeled the transactions consistently with new
> thread I started trying to characterize the full scope of issues and
> workarounds.

OK, I believe it now. :-)

The missing predicate locking is again at fault here.  Because this ...

> -- connection 1 (start of T0)
> start transaction isolation level serializable;
> insert into receipt values (3, (select deposit_date from ctl where k =
> 'receipt'), 4.00);

... would lock ctl where k = 'receipt' ...

> -- connection 2 (T1)
> start transaction isolation level serializable;
> update ctl set deposit_date = date '2008-12-23' where k = 'receipt';
> commit transaction;

... and then this would have to wait ...

> -- connection 2 (TN version 2)
> start transaction isolation level serializable;
> insert into receipt_totals
>   select r.deposit_date, c.deposit_date, sum(amount)
>     from ctl c join receipt r
>       on ( r.deposit_date < c.deposit_date
>        and not exists
>            (
>              select * from receipt r2
>                where r2.deposit_date < c.deposit_date
>                  and r2.deposit_date > r.deposit_date
>            )
>          )
>     group by r.deposit_date, c.deposit_date;
> commit transaction;

... and this could never be executed before T0 commits.

Peter Eisentraut <peter_e@gmx.net> writes:

> On Wednesday 31 December 2008 02:33:26 Kevin Grittner wrote:
>> I'm still working on section "Serializable Isolation versus True
>> Serializability", but here are all the changes I can see which precede
>> it.  Has the review of the SQL specs convinced everyone that this much
>> is appropriate?
>
> I don't agree with these changes.  You make it sound like serializability is 
> an additional condition on the serializable isolation level on top of the 
> no-phantom-reads condition.  I think that is not true, both mathematically 
> and from the wording of the SQL standard.  It is an equivalent condition or a 
> consequence, depending on how you view it.

The standard explicitly says that the no-phantom-reads condition is a
consequence of the serializability constraint. Did you miss that whole
discussion this past week?

--  Gregory Stark EnterpriseDB          http://www.enterprisedb.com Ask me about EnterpriseDB's PostGIS support!

On Sunday 04 January 2009 00:53:51 Gregory Stark wrote:
> Peter Eisentraut <peter_e@gmx.net> writes:
> > On Wednesday 31 December 2008 02:33:26 Kevin Grittner wrote:
> >> I'm still working on section "Serializable Isolation versus True
> >> Serializability", but here are all the changes I can see which precede
> >> it.  Has the review of the SQL specs convinced everyone that this much
> >> is appropriate?
> >
> > I don't agree with these changes.  You make it sound like serializability
> > is an additional condition on the serializable isolation level on top of
> > the no-phantom-reads condition.  I think that is not true, both
> > mathematically and from the wording of the SQL standard.  It is an
> > equivalent condition or a consequence, depending on how you view it.
>
> The standard explicitly says that the no-phantom-reads condition is a
> consequence of the serializability constraint. Did you miss that whole
> discussion this past week?

The SQL standard says it in about three different ways, and textbooks might 
define it an three more ways.  That still doesn't negate my concern with the 
way his patch phrases the issue.

A language lawyer might also point out that the note that contains 
the "explicitness" isn't actually part of the formal standard.  The only 
thing that the standard formally defines are the excluded phenomena.

More to the point, think about how a user might want to think about these 
issues.

"The standard also requires that serializable transactions behave as though 
[...]" --- User: The standard requires it, but is it also implemented?  
(Apparently not, but that is explained somewhere else.)

"is a natural consequence of the fact" --- There is nothing natural about any 
of this.  Why is it a consequence and how?

>>> Peter Eisentraut <peter_e@gmx.net> wrote:
> A language lawyer might also point out that the note that contains 
> the "explicitness" isn't actually part of the formal standard.  The
only 
> thing that the standard formally defines are the excluded phenomena.
Previously quoted, from the standard:
"The execution of concurrent SQL-transactions at isolation level
SERIALIZABLE is guaranteed to be serializable. A serializable
execution is defined to be an execution of the operations of
concurrently executing SQL-transactions that produces the same
effect as some serial execution of those same SQL-transactions. A
serial execution is one in which each SQL-transaction executes to
completion before the next SQL-transaction begins."
> More to the point, think about how a user might want to think about
these 
> issues.
> 
> "The standard also requires that serializable transactions behave as
though 
> [...]" --- User: The standard requires it, but is it also
implemented?  
> (Apparently not, but that is explained somewhere else.)
That's something I thought about, but failed to find a good way to
incorporate at that point, and I thought the discussion in the
following sections covered it.  Perhaps a reference to those following
sections at the point of definition?
> "is a natural consequence of the fact" --- There is nothing natural
> about any of this.  Why is it a consequence and how?
How could you possibly get any of those phenomena if there are no
concurrent transactions?
-Kevin

Sorry if I'm restating the obvious, however I don't understand the
confusion, as it seems the standard's definition isn't mysterious; it
simply requires that the resulting state from the concurrent execution
of transactions (and implicitly any subset) designated to occur at the
isolation level SERIALIZABLE be equivalent to SOME LITERALLY SERIAL
execution of said transactions.

Thereby although of course transactions literally executed serially
comply; they need not be executed literally serially, as long as some
mechanism is used to warrant that the state resulting from the completion
of every such transaction in some sequence be equivalent to the literally
serial execution of the transactions in the same sequence.

Thereby even if only a subset of such concurrently executed transactions
may be complete at some point in time, any potentially remaining such
transactions may be restarted for whatever reason and remain compliant
(as the resulting state from the concurrent execution of such transactions
will be equivalent to some literal serial execution of said transactions
upon the completion of each so executed transaction; correspondingly any
implementation which can not warrant the same, is simply non-compliant).

Thereby although no pre-specified completion order exists per-se, the
order of completion of transactions implicitly determine if incomplete
transactions may need to be restarted if dependant on a preceding completed
transaction's resulting mutated state (or alternatively allowed to proceed
if previously blocked on said potentially mutated state).

Thereby although a collection of such concurrently executed transactions
my have mutual interdependencies, each subsequent complete transaction in
effect break dependency deadlocks as may otherwise logically exist; and
thereby may affect optimal logical execution order of remaining such
transactions potentially concurrently; and be warranted to never deadlock.
I believe IMHO.

>>> Paul Schlie <schlie@comcast.net> wrote: 
> Sorry if I'm restating the obvious, however I don't understand the
> confusion, as it seems the standard's definition isn't mysterious;
> it simply requires that the resulting state from the concurrent
> execution of transactions (and implicitly any subset) designated to
> occur at the isolation level SERIALIZABLE be equivalent to SOME
> LITERALLY SERIAL execution of said transactions.
I think that some of the confusion may result from changes in the
standard.  As far as I can recall, the language requiring that the
SERIALIZABLE transaction isolation level be truly serializable was not
in early versions of the standard, and it may be that there is some
reluctance to concede that a shift in the standard has rendered
PostgreSQL out of compliance on this point.
As I see it, the discussion on this thread is around recognition of
the requirements of the current standard within the PostgreSQL
documentation.
There is a related thread on which I'm attempting to come up with
documentation to assist those familiar with true serializable behavior
who are attempting to recognize application coding patterns where the
differences between that and snapshot isolation are material, with
tips on how to handle these differences.  There seems to be some
question whether the patterns in which anomalies occur are common
enough to merit comment.
If you could reference any concise and accessible work on these
anomalies and practical workarounds in application code, it would be
much appreciated.
-Kevin

> Kevin Grittner <Kevin.Grittner@wicourts.gov> wrote:
>>>> Paul Schlie <schlie@comcast.net> wrote:
>> Sorry if I'm restating the obvious, however I don't understand the
>> confusion, as it seems the standard's definition isn't mysterious;
>> it simply requires that the resulting state from the concurrent
>> execution of transactions (and implicitly any subset) designated to
>> occur at the isolation level SERIALIZABLE be equivalent to SOME
>> LITERALLY SERIAL execution of said transactions.
>  
> I think that some of the confusion may result from changes in the
> standard.  As far as I can recall, the language requiring that the
> SERIALIZABLE transaction isolation level be truly serializable was not
> in early versions of the standard, and it may be that there is some
> reluctance to concede that a shift in the standard has rendered
> PostgreSQL out of compliance on this point.
>  
> As I see it, the discussion on this thread is around recognition of
> the requirements of the current standard within the PostgreSQL
> documentation.
>  
> There is a related thread on which I'm attempting to come up with
> documentation to assist those familiar with true serializable behavior
> who are attempting to recognize application coding patterns where the
> differences between that and snapshot isolation are material, with
> tips on how to handle these differences.  There seems to be some
> question whether the patterns in which anomalies occur are common
> enough to merit comment.
>  
> If you could reference any concise and accessible work on these
> anomalies and practical workarounds in application code, it would be
> much appreciated.

Personally; although compliance may reduce the execution performance of
such so designated transactions, it will correspondingly warrant correct
results, and should be the goal rather than documenting non-conformance;
as those who wish to embed more direct control over transaction evaluation
into their specification to enable their improved concurrent execution
efficiency by utilizing more relaxed evaluation semantics, remain free to
do without penalty. (Simple examples of the risk of non-compliance already
seem sufficiently identified in your example and first reference cited).

Merely documenting that transactions designated to be evaluated at the
isolation level SERIALIZABLE may not yield expected results, as currently
identified, seems sufficient in the short term; and as/if enough interest
develops otherwise, so may an effort to warrant compliance; I suspect.

(as that known to most often be fine, can't be relied upon in practice)

>>> Paul Schlie <schlie@comcast.net> wrote: 
>>  Kevin Grittner <Kevin.Grittner@wicourts.gov> wrote:
>> There is a related thread on which I'm attempting to come up with
>> documentation to assist those familiar with true serializable
>> behavior who are attempting to recognize application coding
>> patterns where the differences between that and snapshot isolation
>> are material, with tips on how to handle these differences.  There
>> seems to be some question whether the patterns in which anomalies
>> occur are common enough to merit comment.
>>  
>> If you could reference any concise and accessible work on these
>> anomalies and practical workarounds in application code, it would
>> be much appreciated.
> 
> Personally; although compliance may reduce the execution performance
> of such so designated transactions, it will correspondingly warrant
> correct results, and should be the goal rather than documenting
> non-conformance; as those who wish to embed more direct control over
> transaction evaluation into their specification to enable their
> improved concurrent execution efficiency by utilizing more relaxed
> evaluation semantics, remain free to do without penalty. (Simple
> examples of the risk of non-compliance already seem sufficiently
> identified in your example and first reference cited).
> 
> Merely documenting that transactions designated to be evaluated at
> the isolation level SERIALIZABLE may not yield expected results, as
> currently identified, seems sufficient in the short term; and as/if
> enough interest develops otherwise, so may an effort to warrant
> compliance; I suspect.
> 
> (as that known to most often be fine, can't be relied upon in
> practice)
Thank you for your perspective.  I'm not sure that I totally followed
you, so let me restate to see if it sounds right to you.  You are
suggesting that minimal discussion of the problem, the initial example
I provided, and more discussion of how to ensure correct semantics
would be what is needed?  Filling in more detail if interest is
expressed by users?
If so, the draft of a partial replacement for the partial replacement
of text in "Serializable Isolation versus True Serializability" may be
close to what you're suggesting -- if additional guidance on when to
use what additional locks is provided.  I'll paste below my signature
for comment.  It's a little rough yet, but looking to see if I'm on
the right track.
The first paragraph is a slightly modified form of a suggestion from
Robert Haas in:
http://archives.postgresql.org/pgsql-hackers/2008-12/msg01732.php
-Kevin
PostgreSQL's MVCC framework, snapshot isolation, and limited automatic
row-level locking permit a greater degree of concurrency than some
other databases; however, even when the transaction isolation level is
set to serializable, serialization anomalies can occur in some
situations.  When it is important to prevent these anomalies, explicit
row-level or table-level locking can be used at the expense of reduced
concurrency.
Since PostgreSQL protects a serializable transaction against changes
in the view of the data, and uses locks to prevent modification of
data which is being modified by a concurrent transaction, the
anomalies can only occur when a transaction reads data which is
modified by a concurrent transaction, and uses that as the basis of
database modifications which are read by a concurrent transaction. 
Data consistency checks at the application level have a problem with
this in general, and are addressed in section 13.4.  Some examples of
other types of anomalies follow, with suggestions on how to use
explicit locking to prevent the anomalies where needed.
Consider a system which involves recording receipts, each of which
must go into a daily deposit.  There is a control table with one row
containing the current deposit date for receipts.  Each transaction
which is inserting a receipt selects the deposit date from the control
table within its transaction, and uses it for the receipt's deposit
date.  Somewhere mid-afternoon the control table's date is updated,
all subsequent receipts should fall into the new day, and a report is
run listing the receipts for the day and giving the deposit total.
If all transactions involved were truly serializable, any SELECT of
receipts for a date prior to the deposit date of the control table
would see the complete, final set of receipts.  Under the PostgreSQL
implementation, unless explicit locking is used, although data
eventually gets to that state there can be a window of time during
which a SELECT can return an incomplete list of receipts for a date
which appears to be closed, even if all transactions for modifying and
viewing data are SERIALIZABLE.  This window of time runs from the
commit of the transaction which updated the control table until the
commit of any pending transactions which are inserting receipts and
which obtained a snapshot before the update of the control table.
To prevent this anomaly, a lock can be taken out on the receipt table
to block all modification to that table.  This should be done in the
transaction which will update the control table, and should be
acquired before the transaction selects or modifies any data.

Kevin Grittner wrote:
>> "is a natural consequence of the fact" --- There is nothing natural
>> about any of this.  Why is it a consequence and how?
>  
> How could you possibly get any of those phenomena if there are no
> concurrent transactions?

I see what you mean now, but you could write out that logic in more detail.

>>> Peter Eisentraut <peter_e@gmx.net> wrote: 
> Kevin Grittner wrote:
>>> "is a natural consequence of the fact" --- There is nothing
>>> natural about any of this.  Why is it a consequence and how?
>>  
>> How could you possibly get any of those phenomena if there are no
>> concurrent transactions?
> 
> I see what you mean now, but you could write out that logic in more
> detail.
Those weren't my words; I was quoting the SQL spec.  It came about
half a page after they had defined serializable transactions by saying
that they must produce the same effect as if they had been run (in
some order) one at a time.  The spec then defined "phenomena that can
occur during the execution of concurrent SQL-transactions" and gave a
table of which phenomena could occur at which transaction isolation
level.  Immediately after the table was the note about "natural
consequence".
Since these phenomena are defined in terms of the visibility of the
effects of concurrent transactions, and serializable transactions must
have the same effect as if they were run one at a time, a natural
consequence is that none of the effects can occur.  What gaps in the
logic to you see?
-Kevin

>>> I wrote: 
>>>> Peter Eisentraut <peter_e@gmx.net> wrote: 
>> Kevin Grittner wrote:
>>>> "is a natural consequence of the fact" --- There is nothing
>>>> natural about any of this.  Why is it a consequence and how?
>>>  
>>> How could you possibly get any of those phenomena if there are no
>>> concurrent transactions?
>> 
>> I see what you mean now, but you could write out that logic in more
>> detail.
>  
> Those weren't my words; I was quoting the SQL spec.
Last night I was reviewing my proposed patch from this thread, to try
to address other expressed concerns, and noticed that I had used this
language from the SQL spec in the patch.  I see your point now. 
Without the same context as the spec, and when intended for a
different audience, this language probably isn't the best.  It now
also occurs to me that the spec is a copyrighted work, and it probably
isn't appropriate to copy a chunk that big into PostgreSQL docs.
I'll write something in my own words to replace this.
Thanks for the input, and sorry for misunderstanding.
-Kevin

Here's a shot at a more radical revision, to try to address concerns
raised over my failure in the previous (very minimal) suggested patch
to address PostgreSQL behavior close to where the spec's behavior is
described, and my dragging in of language directly from the spec in a
confusing context.  I'd appreciate any corrections or suggestions
before I massage it into sgml.
Also, I don't know if I should leave it with the one example or
whether there should be more.  I could leave in the old example,
although the popular example of reversing updates (one transaction
updates all card rows to 'face-up' where they are 'face-down' and vice
versa) seems easier to understand.  One or both of these?  Other
suggestions?
Also, I tried using SELECT FOR SHARE and SELECT FOR HOLD as the
complete solution or instead of one of the table locks, but was able
to generate anomalies in all such cases.  If someone has a less
extreme technique for blocking the anomalies in the receipt example
(even when the SELECT of the deposit date for a receipt is in a
separate statement earlier in the transaction), please let me know, so
that I can include it.
If time permits I might take a stab at expanding the section on data
consistency checks at the application level; however, that seems less
urgent than correcting the obsolescent discussions of the SQL standard
and describing some of the anomalies not covered by a discussion of
consistency checks.
Thanks,
-Kevin
13.2. Transaction Isolation
The SQL standard defines four levels of transaction isolation in terms
of three phenomena that must be prevented between concurrent
transactions, with additional constraints on Serializable
transactions. These undesirable phenomena are: 
dirty read 
A transaction reads data written by a concurrent uncommitted
transaction. 
nonrepeatable read 
A transaction re-reads data it has previously read and finds that data
has been modified by another transaction (that committed since the
initial read). 
phantom read 
A transaction re-executes a query returning a set of rows that satisfy
a search condition and finds that the set of rows satisfying the
condition has changed due to another recently-committed transaction.
The four transaction isolation levels and the corresponding behaviors
are described in Table 13-1.
Table 13-1. SQL Transaction Isolation Levels
<table here>
The standard also requires that serializable transactions behave as
though they were run one at a time, even though their execution may
actually overlap. Since the phenomena described above relate to the
visibility of the effects of concurrent transactions, and each
serializable transaction must behave as though it were run in its
entirety either before or after every other transaction, none of the
above phenomena can occur within a serializable transaction.
In practice there is another popular transaction isolation level, not
mentioned in the standard, generally known as Snapshot isolation
level.  A transaction executed at this transaction isolation level
sees a consistent view of the data; changes made by other transactions
are not visible to it.  Because of this, none of the phenomena
described above are possible.  Additionally, when concurrent
transactions running at this level attempt to modify the same data,
the update conflict causes causes transaction rollback to prevent many
forms of update anomalies.  Still, data may be viewed or stored in a
state which is not consistent with any serial execution of
transactions run at this level, so although it is more strict than
required for Repeatable Read, it does not meet the standard's
definition of the Serializable transaction isolation level.
In PostgreSQL you can request any of the four standard transaction
isolation levels, but internally there are only two distinct isolation
levels, which correspond to the levels Read Committed and Snapshot.
When you select the level Read Uncommitted you really get Read
Committed, and when you select Repeatable Read or Serializable you
really get Snapshot.  Since the standard does not provide for the
Snapshot isolation level, PostgreSQL reports it as Serializable.  The
behavior of the available isolation levels is detailed in the
following subsections. 
To set the transaction isolation level of a transaction, use the
command SET TRANSACTION. or specify the desired transaction isolation
level on a BEGIN TRANSACTION or START TRANSACTION statement.
13.2.1. Read Committed Isolation Level
<unchanged>
13.2.2. Snapshot Isolation Level
The Snapshot level (reported as Serializable) provides the strictest
transaction isolation available in PostgreSQL. This level approximates
serial transaction execution, as if transactions had been executed one
after another, serially, rather than concurrently. However,
applications using this level must be prepared to retry transactions
due to serialization failures.
When a transaction is on the this level, a SELECT query sees only data
committed before the transaction began; it never sees either
uncommitted data or changes committed during transaction execution by
concurrent transactions. (However, the SELECT does see the effects of
previous updates executed within its own transaction, even though they
are not yet committed.) This is different from Read Committed in that
the SELECT sees a snapshot as of the start of the transaction, not as
of the start of the current query within the transaction. Thus,
successive SELECT commands within a single transaction always see the
same data.
UPDATE, DELETE, SELECT FOR UPDATE, and SELECT FOR SHARE commands
behave the same as SELECT in terms of searching for target rows: they
will only find target rows that were committed as of the transaction
start time. However, such a target row might have already been updated
(or deleted or locked) by another concurrent transaction by the time
it is found. In this case, the transaction will wait for the first
updating transaction to commit or roll back (if it is still in
progress). If the first updater rolls back, then its effects are
negated and the transaction can proceed with updating the originally
found row. But if the first updater commits (and actually updated or
deleted the row, not just locked it) then the transaction will be
rolled back with the message
ERROR:  could not serialize access due to concurrent update
because a snapshot transaction cannot modify or lock rows changed by
other transactions after the transaction began.
When the application receives this error message, it should abort the
current transaction and then retry the whole transaction from the
beginning. The second time through, the transaction sees the
previously-committed change as part of its initial view of the
database, so there is no logical conflict in using the new version of
the row as the starting point for the new transaction's update.
Note that only updating transactions might need to be retried;
read-only transactions will never have serialization conflicts.
The Snapshot mode provides a rigorous guarantee that each transaction
sees and modifies an unchanging view of the database. However, the
application has to be prepared to retry transactions when concurrent
updates make it impossible to update the original snapshot. Since the
cost of redoing complex transactions might be significant, this mode
is recommended only when updating transactions contain logic
sufficiently complex that they might give wrong answers in Read
Committed mode. Most commonly, Snapshot mode is necessary when a
transaction executes several successive commands that must see
identical views of the database. 
13.2.2.1. PostgreSQL Serializable Isolation versus True
Serializability
With true serializability, any database transaction which can be shown
to be correct and safe if run by itself is automatically safe when run
in any mix of serializable transactions.  PostgreSQL's MVCC framework,
snapshot isolation, and limited automatic row-level locking permit a
greater degree of concurrency than some other databases; however, even
when the transaction isolation level is set to serializable,
serialization anomalies can occur in some situations. When it is
important to prevent these anomalies, explicit row-level or
table-level locking can be used at the expense of reduced concurrency.
Since PostgreSQL protects a Serializable transaction against changes
in the view of the data, and uses locks to prevent modification of
data which is being modified by a concurrent transaction, the
anomalies can only occur when a transaction reads data which is
modified by a concurrent transaction, and uses that as the basis for
database modifications which are read by a concurrent transaction.
Data consistency checks at the application level have a problem with
this in general, and are addressed in section 13.4.  Some examples of
other types of anomalies follow, with suggestions on how to use
explicit locking to prevent the anomalies where needed.
Consider a system which records receipts, each of which must go into a
daily deposit. There is a control table with one row containing the
current deposit date for receipts. Each transaction which is inserting
a receipt selects the deposit date from the control table within its
transaction, and uses it for the receipt's deposit date. Somewhere
mid-afternoon the control table's date is updated, all subsequent
receipts should fall into the new day, and a report is run listing the
receipts for the day and giving the deposit total.  Serializable
transaction isolation mode is requested for every transaction
involved.
If all transactions involved were truly serializable, any successful
SELECT of receipts for a date prior to the deposit date of the control
table (as shown by a SELECT in the same transaction) would see the
complete, final set of receipts for the completed deposit date.  To
preserve this view of the data, one or more transactions might need to
block until the commit or rollback of other transactions, and one or
more transaction might need to be rolled back and run again from the
start.
Under the PostgreSQL implementation there is no blocking and no chance
of rollbacks; however, there can be a window of time during which a
SELECT can return an incomplete list of receipts for a date which
appears to be closed, even if Serializable mode is requested for all
transactions modifying and viewing data. This window of time runs from
the commit of the transaction which updated the control table until
the commit of any pending transactions which are inserting receipts
and which obtained a snapshot before the update of the control table. 
A database transaction, even if declared Serializable, which selects
the sum of the receipts for the closed date and saves it into a daily
deposit table, will persist an inaccurate value if run during this
same window of time.
Alarming as this might sound, if the transactions which insert
receipts commit very quickly after the snapshot is obtained, this
anomaly might never appear in a real-life system.  If the risk is
acceptable, or can be controlled by external means, such as delaying
the run of the daily receipt report for a few seconds after the update
of the control table, no further action is required.  It is up to the
software developer to recognize where the risk is unacceptable and to
decide on a technique to control each known conflict.
To prevent the anomaly described above, transactions which insert
receipts and transactions which advance the deposit date must both
acquire a common lock as their first step.  This lock could be
acquired on either the control table or the receipt table.