Re: 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(at)svana(dot)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(at)svana(dot)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(dot)Grittner(at)wicourts(dot)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(at)frogthinker(dot)org
Skype: emmanuel_cecchet

>>> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> "Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)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(at)frogthinker(dot)org
Skype: emmanuel_cecchet

>>> Emmanuel Cecchet <manu(at)frogthinker(dot)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(at)frogthinker(dot)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(dot)linnakangas(at)enterprisedb(dot)com> 12/23/08
9:47 AM >>>
> Kevin Grittner wrote:
>>>>> Emmanuel Cecchet <manu(at)frogthinker(dot)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(dot)Grittner(at)wicourts(dot)gov> writes:

>>>> Emmanuel Cecchet <manu(at)frogthinker(dot)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(at)enterprisedb(dot)com> wrote:
> "Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
>>>>> Emmanuel Cecchet <manu(at)frogthinker(dot)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 consequence of 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(dot)Grittner(at)wicourts(dot)gov> writes:

>>>> Gregory Stark <stark(at)enterprisedb(dot)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(at)enterprisedb(dot)com> wrote:
> "Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
>>>>> Gregory Stark <stark(at)enterprisedb(dot)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(at)megazone(dot)bigpanda(dot)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.com
PostgreSQL Training, Services and Support

>>> "Robert Haas" <robertmhaas(at)gmail(dot)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(at)2ndQuadrant(dot)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

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(at)cheapcomplexdevices(dot)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

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(at)gmx(dot)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(at)gmx(dot)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(at)gmx(dot)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(at)postgresql(dot)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(at)gmx(dot)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(dot)linnakangas(at)enterprisedb(dot)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(at)gmx(dot)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(at)gmx(dot)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(at)gmx(dot)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

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(at)gmx(dot)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(at)gmx(dot)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.