Re: More FOR UPDATE/FOR SHARE problems

This post is a follow-up of an off-list discussion with Nathan Boley.
All references to FOR UPDATE apply to FOR SHARE as well.

create table a(i int, j int);
insert into a values(1, 10);
insert into a values(2, 10);
insert into a values(3, 10);
insert into a values(4, 20);
insert into a values(5, 20);
insert into a values(6, 20);

Session 1:
BEGIN;
UPDATE a SET j = (j - 10) WHERE i = 3 OR i = 4;

Session 2:
SELECT * FROM a WHERE j = 10 FOR UPDATE; -- blocks

Session 1:
COMMIT;

Session 2 (results):
i | j
---+----
1 | 10
2 | 10
(2 rows)

There you see a snapshot of the table that never existed. Either the
snapshot was taken before the UPDATE, in which case i=3 should be
included, or it was taken after the UPDATE, in which case i=4 should be
included. So atomicity is broken for WHERE.

So, FOR UPDATE produces known incorrect results for:
* WHERE
* ORDER BY:
http://archives.postgresql.org/pgsql-bugs/2009-01/msg00017.php
* LIMIT
* SAVEPOINT/ROLLBACK TO

And I expect we'll find more, as well.

It's not simply that FOR UPDATE works strangely in a couple isolated
edge cases, as the docs imply. It works contrary to the basic
assumptions that people familiar with PostgreSQL rely on. Furthermore,
the people using FOR UPDATE are likely to be the people who care about
these edge cases.

I think that FOR UPDATE deserves a jarring disclaimer in the docs if we
maintain the current behavior. Something along the lines of "this does
not follow normal transactional semantics and will produce incorrect
results". Existing users may find current FOR UPDATE behavior useful to
avoid full-table locks, but they should be properly warned.

If there is a fix, the only thing that I can imagine working (aside from
a full table lock) would be to iteratively acquire new snapshots and
re-run the query until no concurrent transaction interferes.

Regards,
Jeff Davis

There already is quite an extensive discussion of how FOR UPDATE
behaves including these kinds of violations.

What you propose is interesting though. It would have been impossible
before subtransactions but it's doable now. Still the performance
might be unusable for complex queries. It's basically generalizing the
logic a serializable transaction would take to a read committed command.

--
Greg

On 24 Jan 2009, at 18:50, Jeff Davis <pgsql(at)j-davis(dot)com> wrote:

> This post is a follow-up of an off-list discussion with Nathan Boley.
> All references to FOR UPDATE apply to FOR SHARE as well.
>
> create table a(i int, j int);
> insert into a values(1, 10);
> insert into a values(2, 10);
> insert into a values(3, 10);
> insert into a values(4, 20);
> insert into a values(5, 20);
> insert into a values(6, 20);
>
> Session 1:
> BEGIN;
> UPDATE a SET j = (j - 10) WHERE i = 3 OR i = 4;
>
> Session 2:
> SELECT * FROM a WHERE j = 10 FOR UPDATE; -- blocks
>
> Session 1:
> COMMIT;
>
> Session 2 (results):
> i | j
> ---+----
> 1 | 10
> 2 | 10
> (2 rows)
>
> There you see a snapshot of the table that never existed. Either the
> snapshot was taken before the UPDATE, in which case i=3 should be
> included, or it was taken after the UPDATE, in which case i=4 should
> be
> included. So atomicity is broken for WHERE.
>
> So, FOR UPDATE produces known incorrect results for:
> * WHERE
> * ORDER BY:
> http://archives.postgresql.org/pgsql-bugs/2009-01/msg00017.php
> * LIMIT
> * SAVEPOINT/ROLLBACK TO
>
> And I expect we'll find more, as well.
>
> It's not simply that FOR UPDATE works strangely in a couple isolated
> edge cases, as the docs imply. It works contrary to the basic
> assumptions that people familiar with PostgreSQL rely on. Furthermore,
> the people using FOR UPDATE are likely to be the people who care about
> these edge cases.
>
> I think that FOR UPDATE deserves a jarring disclaimer in the docs if
> we
> maintain the current behavior. Something along the lines of "this does
> not follow normal transactional semantics and will produce incorrect
> results". Existing users may find current FOR UPDATE behavior useful
> to
> avoid full-table locks, but they should be properly warned.
>
> If there is a fix, the only thing that I can imagine working (aside
> from
> a full table lock) would be to iteratively acquire new snapshots and
> re-run the query until no concurrent transaction interferes.
>
> Regards,
> Jeff Davis
>
>
>
> --
> 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

On Sat, 2009-01-24 at 19:45 +0000, Greg Stark wrote:
> There already is quite an extensive discussion of how FOR UPDATE
> behaves including these kinds of violations.

Not in the documentation, that I can see. And I think it's important
that it be there for the reasons I mentioned.

Can you refer me to the dicussion that you're talking about? I don't
remember any discussion that points out that FOR UPDATE/FOR SHARE is
broken in the simple case of a simple WHERE clause.

> What you propose is interesting though. It would have been impossible
> before subtransactions but it's doable now. Still the performance
> might be unusable for complex queries. It's basically generalizing the
> logic a serializable transaction would take to a read committed command.

It might be effective for queries that are highly selective on large
tables. Still has strange deadlock possibilities, but I think that's the
case already.

Regards,
Jeff Davis

Jeff Davis <pgsql(at)j-davis(dot)com> writes:
> There you see a snapshot of the table that never existed. Either the
> snapshot was taken before the UPDATE, in which case i=3 should be
> included, or it was taken after the UPDATE, in which case i=4 should be
> included. So atomicity is broken for WHERE.

This assertion is based on a misunderstanding of what FOR UPDATE in
read-committed mode is defined to do. It is supposed to give you the
latest available rows.

regards, tom lane

Jeff Davis <pgsql(at)j-davis(dot)com> writes:

> On Sat, 2009-01-24 at 19:45 +0000, Greg Stark wrote:
>> There already is quite an extensive discussion of how FOR UPDATE
>> behaves including these kinds of violations.
>
> Not in the documentation, that I can see. And I think it's important
> that it be there for the reasons I mentioned.
>
> Can you refer me to the dicussion that you're talking about? I don't
> remember any discussion that points out that FOR UPDATE/FOR SHARE is
> broken in the simple case of a simple WHERE clause.

http://www.postgresql.org/docs/8.3/static/transaction-iso.html#XACT-READ-COMMITTED

Because of the above rule, it is possible for an updating command to see an
inconsistent snapshot: it can see the effects of concurrent updating commands
that affected the same rows it is trying to update, but it does not see
effects of those commands on other rows in the database. This behavior makes
Read Committed mode unsuitable for commands that involve complex search
conditions. However, it is just right for simpler cases. For example, consider
updating bank balances with transactions like
...

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

>>> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Jeff Davis <pgsql(at)j-davis(dot)com> writes:
>> There you see a snapshot of the table that never existed. Either
the
>> snapshot was taken before the UPDATE, in which case i=3 should be
>> included, or it was taken after the UPDATE, in which case i=4 should
be
>> included. So atomicity is broken for WHERE.
>
> This assertion is based on a misunderstanding of what FOR UPDATE in
> read-committed mode is defined to do. It is supposed to give you
the
> latest available rows.

Well, technically it's violating the Isolation part of ACID, not the
Atomicity, since the UPDATE transaction will either commit or roll
back in its entirety, but another transaction can see it in an
intermediate (partially applied) state.[1]

I guess the issue of whether this violation of ACID properties should
be considered a bug or a feature is a separate discussion, but calling
it a feature seems like a hard sell to me.

-Kevin

[1] http://en.wikipedia.org/wiki/ACID

On Mon, 2009-01-26 at 10:48 -0600, Kevin Grittner wrote:
> I guess the issue of whether this violation of ACID properties should
> be considered a bug or a feature is a separate discussion, but calling
> it a feature seems like a hard sell to me.
>

I think I understand the other perspective on this now: SELECT FOR
UPDATE/SHARE is an entirely separate command that is more similar (in
transactional semantics) to UPDATE than to SELECT.

In fact, it's probably most similar to UPDATE ... RETURNING, which will
give the same result (that breaks atomicity or isolation, depending on
your point of view), which is correct for READ COMMITTED isolation
level.

Because the command begins with SELECT, I would expect it to follow the
rules of SELECT with the side effect of locking. I would think that the
standard would have something to say about this*.

I certainly don't think it's intuitive behavior.

Regards,
Jeff Davis.

*: It appears that SELECT ... FOR UPDATE is not in the standard, which
would indicate to me that the SELECT statement should still behave
according to SELECT isolation/snapshot rules. But when I guess about the
standard, I'm usually wrong.

>>> Jeff Davis <pgsql(at)j-davis(dot)com> wrote:
> In fact, it's probably most similar to UPDATE ... RETURNING, which
will
> give the same result (that breaks atomicity or isolation, depending
on
> your point of view), which is correct for READ COMMITTED isolation
> level.

READ COMMITTED is not supposed to be able to view the work of a
concurrent transactions as PARTLY applied and PARTLY committed, which
is what's happening here. If one statement in a READ COMMITTED
transaction sees the uncommitted view of the data and the next
statement sees the committed view, that's compliant. It may not
surprise someone who is intimately familiar with PostgreSQL internals
for a single SELECT statement to see PART of a transactions work, but
it would surprise most users, and is certainly not compliant with the
standard.

-Kevin

On 2009-01-26, at 17:34, Kevin Grittner wrote:
> . It may not
> surprise someone who is intimately familiar with PostgreSQL internals
> for a single SELECT statement to see PART of a transactions work, but
> it would surprise most users, and is certainly not compliant with the
> standard.
+1000

On Mon, 2009-01-26 at 11:34 -0600, Kevin Grittner wrote:
> READ COMMITTED is not supposed to be able to view the work of a
> concurrent transactions as PARTLY applied and PARTLY committed, which
> is what's happening here. If one statement in a READ COMMITTED
> transaction sees the uncommitted view of the data and the next
> statement sees the committed view, that's compliant. It may not
> surprise someone who is intimately familiar with PostgreSQL internals
> for a single SELECT statement to see PART of a transactions work, but
> it would surprise most users, and is certainly not compliant with the
> standard.

See 13.2.1:
http://www.postgresql.org/docs/8.3/static/transaction-iso.html

That explanation seems to be the behavior I would expect from UPDATE in
read committed mode. Perhaps I'm just used to PostgreSQL -- what do
other database systems do?

And what does the standard say? I can't find anything in the standard
that handles UPDATEs differently, so that seems to support your
position.

After the concurrent transaction commits, you basically have three
options:
1. Get a new snapshot, and re-run the entire query to find new rows
that might match the search condition that were committed between the
time you took the original snapshot for UPDATE and the time that the
concurrent transaction committed.
2. Blindly proceed with the original snapshot. This would mean that two
concurrent updates like "set i = i+1" might both see the same value,
let's say 5, and both update it to 6, and then commit. However, a serial
execution would produce 7.
3. Find the latest version of the same tuples you found from the
original snapshot in the original search, and if they still match the
search condition, update based on the new version. This is what
PostgreSQL currently does.

I don't think this is PostgreSQL-specific, I think non-MVCC database
systems face this same choice (although the terminology would be
different).

#3 has a certain intuition about it (i.e. "produces the expected result
most of the time in simple cases"), but in my opinion, that intuition
only holds for UPDATE, it doesn't hold for SELECT.

Regards,
Jeff Davis

>>> Jeff Davis <pgsql(at)j-davis(dot)com> wrote:
> I don't think this is PostgreSQL-specific, I think non-MVCC database
> systems face this same choice (although the terminology would be
> different).

A somewhat dated description for Sybase (it predates their support of
row level locks and the related predicate locks on indexes) is here:

http://manuals.sybase.com/onlinebooks/group-asarc/srv10024/sag/@Generic__BookTextView/41766;pt=41535/*

Simplified, in a READ COMMITTED transaction a SELECT takes a lock
which conflicts with update before reading, and holds it until the
executing statement is done with that table; an UPDATE takes a lock
which conflicts with any access (read or write) before it updates a
row, and holds it until COMMIT or ROLLBACK. This guarantees that the
SELECT doesn't see the results of an incomplete UPDATE, at the expense
of taking locks, blocking, and possible serialization failures (in the
form of deadlocks).

-Kevin

>>> I wrote:
> Simplified, in a READ COMMITTED transaction a SELECT takes a lock
> which conflicts with update before reading, and holds it until the
> executing statement is done with that table;

That should have said "until after the executing statement completes."

Apologies, but but I just know someone would have picked up on the
hole my misstatement left....

-Kevin

On Mon, 2009-01-26 at 13:50 -0600, Kevin Grittner wrote:
> A somewhat dated description for Sybase (it predates their support of
> row level locks and the related predicate locks on indexes) is here:
>
> http://manuals.sybase.com/onlinebooks/group-asarc/srv10024/sag/@Generic__BookTextView/41766;pt=41535/*
>
> Simplified, in a READ COMMITTED transaction a SELECT takes a lock
> which conflicts with update before reading, and holds it until the
> executing statement is done with that table; an UPDATE takes a lock
> which conflicts with any access (read or write) before it updates a
> row, and holds it until COMMIT or ROLLBACK. This guarantees that the
> SELECT doesn't see the results of an incomplete UPDATE, at the expense
> of taking locks, blocking, and possible serialization failures (in the
> form of deadlocks).
>

That doesn't quite answer the question about UPDATE specifically.
Pretend for a second that SELECT ... FOR UPDATE is like UPDATE ...
RETURNING. The example in my original email can be easily changed to use
UPDATE ... RETURNING.

The tricky part is when an UPDATE with a search condition reads,
modifies, and writes a value that is used in a search condition for
another UPDATE.

Every DBMS will block waiting for the first UPDATE to finish. Then what?
Do you re-run the query to find new tuples that might now satisfy the
search condition that didn't before? Do you update the new value in all
the tuples you originally found, regardless of whether they still match
the search condition? Do you update the new value in all the tuples that
you found that still match the search condition? Do you update the old
value, perhaps overwriting changes made by the first UPDATE?

What does sybase do in that case?

Regards,
Jeff Davis

>>> Jeff Davis <pgsql(at)j-davis(dot)com> wrote:
> The tricky part is when an UPDATE with a search condition reads,
> modifies, and writes a value that is used in a search condition for
> another UPDATE.
>
> Every DBMS will block waiting for the first UPDATE to finish. Then
> what?

Either it's totally safe to proceed, or the second UPDATE was rolled
back.

> Do you re-run the query to find new tuples that might now satisfy
> the search condition that didn't before?

There can't be any. Blocks taken during the reading of rows so far
have not been released, and would preclude the update from changing
results read so far.

> Do you update the new value in all the tuples you originally found,
> regardless of whether they still match the search condition?

They have to still match, your locks would preclude their
modification.

> Do you update the new value in all the tuples that
> you found that still match the search condition?

They can't have a new value. Locks.

> Do you update the old value, perhaps overwriting changes made by the
> first UPDATE?

If you haven't gotten to reading rows yet, you're still OK by the time
the other transaction's locks are released. Look over those rules and
try some thought experiments to convince yourself. It really is safe,
if potentially slow.

-Kevin

On Mon, 2009-01-26 at 14:31 -0600, Kevin Grittner wrote:
> > Do you re-run the query to find new tuples that might now satisfy
> > the search condition that didn't before?
>
> There can't be any. Blocks taken during the reading of rows so far
> have not been released, and would preclude the update from changing
> results read so far.

Let's say the sequence is:

Data:
i j
--------
1 10
2 10
3 20
4 20

Session1:
BEGIN;
UPDATE a SET j = (j - 10) WHERE i = 2 OR i = 3;

Session2:
BEGIN;
UPDATE a SET j = j + 100 WHERE j = 10;

Session1:
COMMIT;

Session2:
COMMIT;

In PostgreSQL, the result is:

i | j
---+-----
4 | 20
2 | 0
3 | 10
1 | 110
(4 rows)

Which cannot be obtained by any serial execution. What is the result in
Sybase, Oracle, etc.?

It seems like it would be a challenge to know that the tuple with i=3
would be updated to a value that matches the search condition j=10. So
can you tell me a little more about the mechanism by which Sybase solves
this problem?

Regards,
Jeff Davis

>>> Jeff Davis <pgsql(at)j-davis(dot)com> wrote:
> On Mon, 2009-01-26 at 14:31 -0600, Kevin Grittner wrote:
>> > Do you re-run the query to find new tuples that might now satisfy
>> > the search condition that didn't before?
>>
>> There can't be any. Blocks taken during the reading of rows so far
>> have not been released, and would preclude the update from changing
>> results read so far.
>
> Let's say the sequence is:
>
> Data:
> i j
> --------
> 1 10
> 2 10
> 3 20
> 4 20
>
> Session1:
> BEGIN;
> UPDATE a SET j = (j - 10) WHERE i = 2 OR i = 3;

OK, the description would be trivial if we assume page level locks
(the default), so I'll assume row level locks. I'll also assume READ
COMMITTED. (In SERIALIZABLE, no lock is ever released until COMMIT or
ROLLBACK, although the update locks can be downgraded or upgraded.)

Simplified a bit, this places an exclusive lock on rows 2 and 3 and
then updates these two rows in place (no new tuples are created).

> Session2:
> BEGIN;
> UPDATE a SET j = j + 100 WHERE j = 10;

This might update row 1 before blocking on the attempt to read row 2.
Let's say, for sake of argument, that it does. So it is holding an
exclusive lock on row 1 and attempting to acquire an update lock to
read row 2. (It will upgrade this to an exclusive lock if it decides
to update it, or downgrade it to shared if it decides not to do so.)
Session2 is blocked for now.

> Session1:
> COMMIT;

After the COMMIT succeeds, the locks from Session1 are released.
Session2 acquires its update lock and reads row 2, finds that it
doesn't match its update criteria, downgrades the lock to shared,
acquires an update lock on row 3, finds that it does match the
selection criteria, upgrades the lock to exclusive, updates it,
acquires and update lock on row 4 finds that it doesn't match the
update criteria, downgrades the lock to shared, hits the end of table,
releases the shared locks.

> Session2:
> COMMIT;

After the COMMIT succeeds, the locks from Session2 are released.

> In PostgreSQL, the result is:
>
> i | j
> ---+-----
> 4 | 20
> 2 | 0
> 3 | 10
> 1 | 110
> (4 rows)
>
> Which cannot be obtained by any serial execution. What is the result
> in Sybase, Oracle, etc.?

I can't be sure about Oracle, but I think its results would match
PostgreSQL. In Sybase, with either READ COMMITTED or SERIALIZABLE,
the result would be:

i | j
---+-----
1 | 110
2 | 0
3 | 110
4 | 20
(4 rows)

If that explanation wasn't clear, let me know.

Let me restate -- I don't propose that PostgreSQL implement this
locking scheme. I think it can and should do better in approaching
compliance with the standard, and with ACID properties, without
compromising concurrency and performance to the degree required by
this sort of locking and blocking.

-Kevin

Jeff Davis <pgsql(at)j-davis(dot)com> writes:

> It seems like it would be a challenge to know that the tuple with i=3
> would be updated to a value that matches the search condition j=10. So
> can you tell me a little more about the mechanism by which Sybase solves
> this problem?

This example is a case of the same issue we were discussing earlier involving
"predicate locking". To solve it you need a way to lock records that your
query *isn't* accessing and may not even exist yet to prevent them from being
turned into (or inserted as) records your query should be accessing.

As Kevin described it earlier Sybase locks the index pages containing the key
range you're accessing preventing anyone from inserting new index pointers in
that range. If there's no index it locks the entire table on every select to
prevent any updates or inserts in the table until your transaction finishes.

In any case note that your example is not *serializable*. (Though in Postgres
it can happen even in serializable mode, so that's not much of a defence.) I'm
unclear what whether it manifests any of the phenomenon which are prohibited
for READ COMMITTED.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Get trained by Bruce Momjian - ask me about EnterpriseDB's PostgreSQL training!

>>> Gregory Stark <stark(at)enterprisedb(dot)com> wrote:
> This example is a case of the same issue we were discussing earlier
> involving "predicate locking". To solve it you need a way to lock
> records that your query *isn't* accessing and may not even exist yet
> to prevent them from being turned into (or inserted as) records your
> query should be accessing.
>
> As Kevin described it earlier Sybase locks the index pages
> containing the key range you're accessing preventing anyone from
> inserting new index pointers in that range. If there's no index it
> locks the entire table on every select to prevent any updates or
> inserts in the table until your transaction finishes.

Well, for READ COMMITTED in Sybase it's only until the end of the
statement.

Hmmm.... I'm clearly getting a bit rusty on my Sybase row level
locking rules. I got some details wrong in my example, but the
outcome would be the same. Broader locks though, leading to more
potential blocking.

> I'm unclear what whether it manifests any of the phenomenon which
> are prohibited for READ COMMITTED.

Interesting question. It's behavior not possible in 2 phase locking,
but not explicitly prohibited by the standard. Better watch that kind
of talk, though, or they may go and change the standard again. ;-)

-Kevin

On Mon, 2009-01-26 at 09:26 -0800, Jeff Davis wrote:
> On Mon, 2009-01-26 at 10:48 -0600, Kevin Grittner wrote:
> > I guess the issue of whether this violation of ACID properties should
> > be considered a bug or a feature is a separate discussion, but calling
> > it a feature seems like a hard sell to me.
> >
>
> I think I understand the other perspective on this now: SELECT FOR
> UPDATE/SHARE is an entirely separate command that is more similar (in
> transactional semantics) to UPDATE than to SELECT.

You can think of SELECT FOR UPDATE as first half of UPDATE command

UPDATE is in this case split in two
SELECT FOR UPDATE
UPDATE WHERE CURRENT

which means that yes, it has to follow UPDATE semantics to be of any use
in FOR UPDATE case.

> In fact, it's probably most similar to UPDATE ... RETURNING, which will
> give the same result (that breaks atomicity or isolation, depending on
> your point of view), which is correct for READ COMMITTED isolation
> level.
>
> Because the command begins with SELECT, I would expect it to follow the
> rules of SELECT with the side effect of locking. I would think that the
> standard would have something to say about this*.
>
> I certainly don't think it's intuitive behavior.
>
> Regards,
> Jeff Davis.
>
> *: It appears that SELECT ... FOR UPDATE is not in the standard, which
> would indicate to me that the SELECT statement should still behave
> according to SELECT isolation/snapshot rules. But when I guess about the
> standard, I'm usually wrong.
>

--
------------------------------------------
Hannu Krosing http://www.2ndQuadrant.com
PostgreSQL Scalability and Availability
Services, Consulting and Training

On Mon, 2009-01-26 at 15:46 -0600, Kevin Grittner wrote:
> After the COMMIT succeeds, the locks from Session1 are released.
> Session2 acquires its update lock and reads row 2, finds that it
> doesn't match its update criteria, downgrades the lock to shared,
> acquires an update lock on row 3, finds that it does match the
> selection criteria, upgrades the lock to exclusive, updates it,
> acquires and update lock on row 4 finds that it doesn't match the
> update criteria, downgrades the lock to shared, hits the end of table,
> releases the shared locks.

This is the part I'm having a problem with. This depends on row 3 being
read after row 2. If that weren't the case (say, with a more complex
update and a more complex search criteria), then the index scan would
have already passed by the value and would never know that it was
updated to a value that does match the search criteria.

Data:
i j
--------
1 20
2 40
3 50
4 80

S1:
BEGIN;
UPDATE a SET j = (j - 10) WHERE i = 2 OR i = 3;

S2:
BEGIN;
UPDATE a SET j = j + 100 WHERE j = 10 or j = 40;
-- Here, the index scan is already past j=10 by the time
-- it blocks on a concurrently-updated tuple

S1:
COMMIT;

S2:
COMMIT;

In PostgreSQL this sequence results in:
i | j
---+----
1 | 20
4 | 80
2 | 30
3 | 40

The second update matched no tuples at all.

> Let me restate -- I don't propose that PostgreSQL implement this
> locking scheme. I think it can and should do better in approaching
> compliance with the standard, and with ACID properties, without
> compromising concurrency and performance to the degree required by
> this sort of locking and blocking.

I think Greg has it right: without predicate locking we can't really
achieve the behavior you're expecting. So how would we better approach
the semantics you want without it?

Regards,
Jeff Davis

>>> Jeff Davis <pgsql(at)j-davis(dot)com> wrote:
> On Mon, 2009-01-26 at 15:46 -0600, Kevin Grittner wrote:
>> After the COMMIT succeeds, the locks from Session1 are released.
>> Session2 acquires its update lock and reads row 2, finds that it
>> doesn't match its update criteria, downgrades the lock to shared,
>> acquires an update lock on row 3, finds that it does match the
>> selection criteria, upgrades the lock to exclusive, updates it,
>> acquires and update lock on row 4 finds that it doesn't match the
>> update criteria, downgrades the lock to shared, hits the end of
table,
>> releases the shared locks.
>
> This is the part I'm having a problem with. This depends on row 3
being
> read after row 2. If that weren't the case (say, with a more complex
> update and a more complex search criteria), then the index scan
would
> have already passed by the value and would never know that it was
> updated to a value that does match the search criteria.

I think you're missing a fundamental point -- in Sybase, before a row
or range is read it is blocked against update by other transactions
until after the reading statement completes; before a row or range is
updated it is blocked against another transaction even reading it.
(For serializable transactions the locks are all held until commit or
rollback.) So, if an index scan for S2 had already passed a certain
point and blocked on an update by S1, and then S1 tried to update any
part of what S2 had read, there would be a deadlock and one of these
transactions would be rolled back with a serialization error.

> Data:
> i j
> --------
> 1 20
> 2 40
> 3 50
> 4 80
>
> S1:
> BEGIN;
> UPDATE a SET j = (j - 10) WHERE i = 2 OR i = 3;

S1 holds locks that prevent any other transaction reading anything
about these two rows, including index entries.

> S2:
> BEGIN;
> UPDATE a SET j = j + 100 WHERE j = 10 or j = 40;
> -- Here, the index scan is already past j=10 by the time
> -- it blocks on a concurrently-updated tuple

Assuming an index on j, S2 will block when it tries to read a modified
range, so yeah, it might read j=10 and find nothing, then attempt to
read j=40 and block. (Of course, in reality if the table had four
rows and the database had current statistics, these would all be done
with table scans and the locks would effectively be the same as table
locks. That being fairly obvious behavior, I'll stick to the
supposition that it's operating with row locks.)

> S1:
> COMMIT;

The index entries and data rows are updated in place. Locks are then
released. S2 now reads rows j=40 and finds i=3 as the only match.
(No "snapshot" exists. No old version of the tuple. It just sees
whatever is there when the locks are released.)

> S2:
> COMMIT;
>
> In PostgreSQL this sequence results in:
> i | j
> ---+----
> 1 | 20
> 4 | 80
> 2 | 30
> 3 | 40
>
> The second update matched no tuples at all.

In Sybase (and similar databases), the result would be:
i | j
---+-----
1 | 20
2 | 30
3 | 140
4 | 80

>> Let me restate -- I don't propose that PostgreSQL implement this
>> locking scheme. I think it can and should do better in approaching
>> compliance with the standard, and with ACID properties, without
>> compromising concurrency and performance to the degree required by
>> this sort of locking and blocking.
>
> I think Greg has it right: without predicate locking we can't really
> achieve the behavior you're expecting. So how would we better
approach
> the semantics you want without it?

Well, this thread was talking about dealing with situations where
queries using FOR UPDATE/FOR SHARE return something other than what is
requested, or results based on viewing only part of what was committed
by another transaction. My feeling is that we should be looking
harder at recognizing these cases and rolling back a transaction with
a serialization failure before returning bad data. When you are using
these clauses you are already vulnerable to deadlocks.

This doesn't seem to me to be that different from other situations
where people have said "It's easy to return results quickly if you
don't care whether they're accurate."

Regarding the broader issues -- during discussion of documentation for
the anomalies in snapshot isolation I was made aware of recent work,
published by the ACM last year, which provides techniques for a more
general and comprehensive solution. This has already been implemented
in at least two other MVCC databases, although these changes haven't
made it to a production release of anything yet. I've been trying to
wait until 8.4 hits beta testing to open a discussion of this.
Basically, though, this work outlines a way to provide real
serializable behavior in an MVCC database without any more blocking
than PostgreSQL already has. Stay tuned for a discussion of this once
8.4 is in beta.

-Kevin

"Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:

>> I think Greg has it right: without predicate locking we can't really
>> achieve the behavior you're expecting. So how would we better approach the
>> semantics you want without it?
>
> Well, this thread was talking about dealing with situations where
> queries using FOR UPDATE/FOR SHARE return something other than what is
> requested, or results based on viewing only part of what was committed
> by another transaction. My feeling is that we should be looking
> harder at recognizing these cases and rolling back a transaction with
> a serialization failure before returning bad data.

Well that's precisely what our SERIALIZABLE isolation mode does.

What I thought was intriguing was the thought of applying the serializable
logic to individual commands instead of the whole transaction. That is, repeat
the same command with a new snapshot instead of having to restart the whole
transaction over again. That's something you can't actually emulate right now.
The only way to get notified by Postgres that there's been an update is to be
in serializable mode which has to be set for the whole transaction, so even if
you catch the error you don't get a new snapshot.

> This doesn't seem to me to be that different from other situations
> where people have said "It's easy to return results quickly if you
> don't care whether they're accurate."

Well I think the fundamental point is that SELECT FOR UPDATE gives you the
right data *for a subsequent update* of that row. If you never actually peek
at that data except to use it in a subsequent update then you get the same
results as if you had just issued the UPDATE and the resulting data in the
table is reasonable. If you use the data for purposes external to that row
then strange things do indeed result.

> Regarding the broader issues -- during discussion of documentation for
> the anomalies in snapshot isolation I was made aware of recent work,
> published by the ACM last year, which provides techniques for a more
> general and comprehensive solution.

Hopefully it's not patent encumbered? Might be better not to check actually.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Get trained by Bruce Momjian - ask me about EnterpriseDB's PostgreSQL training!

>>> Gregory Stark <stark(at)enterprisedb(dot)com> wrote:
> Hopefully it's not patent encumbered? Might be better not to check
> actually.

I've been in correspondence with the authors. That is the first
question I asked them. The response (from Michael Cahill):

- There are no patent applications covering our work, as far as we are
- aware. That is, no patent applications have been lodged for our
- work, and no applications are planned. To the best of our
- knowledge, our work in this area was novel, so we are not aware of
- any prior patents that cover our work.

But seriously, I don't want this to lead to a discussion which pulls
people from getting 8.4 out the door.

-Kevin

Kevin Grittner wrote:
> >>> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> > Jeff Davis <pgsql(at)j-davis(dot)com> writes:
> >> There you see a snapshot of the table that never existed. Either
> the
> >> snapshot was taken before the UPDATE, in which case i=3 should be
> >> included, or it was taken after the UPDATE, in which case i=4 should
> be
> >> included. So atomicity is broken for WHERE.
> >
> > This assertion is based on a misunderstanding of what FOR UPDATE in
> > read-committed mode is defined to do. It is supposed to give you
> the
> > latest available rows.
>
> Well, technically it's violating the Isolation part of ACID, not the
> Atomicity, since the UPDATE transaction will either commit or roll
> back in its entirety, but another transaction can see it in an
> intermediate (partially applied) state.[1]
>
> I guess the issue of whether this violation of ACID properties should
> be considered a bug or a feature is a separate discussion, but calling
> it a feature seems like a hard sell to me.

In trying to get some closure on this issue, I started investigating
this myself. I realize there is the issue with serializable isolation
level that is already documented:

http://developer.postgresql.org/pgdocs/postgres/transaction-iso.html#XACT-SERIALIZABLE

Particularly, inserts by two transactions not seeing each other. OK, at
least it is documented.

There is also the problem of queries that add and remove rows from
SELECT FOR UPDATE sets:

http://archives.postgresql.org/pgsql-hackers/2009-01/msg01803.php

I have come up with a simpler example of that behavior:

S1:
test=> CREATE TABLE mvcc_test (status BOOLEAN);
CREATE TABLE
test=> INSERT INTO mvcc_test VALUES (true), (false);
INSERT 0 2
test=> BEGIN;
BEGIN
test=> UPDATE mvcc_test SET status = NOT status;
UPDATE 2

S2:
test=> SELECT * FROM mvcc_test WHERE status = true FOR UPDATE;

S1:
test=> COMMIT;

S2:
status
--------
(0 rows)

As you can see, the S2 SELECT FOR UPDATE returns zero rows, even though
one row would be returned before the UPDATE, and one row after the
update, and at no time were no rows matching its criteria ('true').

So, I thought, this is another SELECT FOR UPDATE problem, but then I was
able to duplicate it with just UPDATEs:

S1:
test=> CREATE TABLE mvcc_test (status BOOLEAN);
CREATE TABLE
test=> INSERT INTO mvcc_test VALUES (true), (false);
INSERT 0 2
test=> BEGIN;
BEGIN
test=> UPDATE mvcc_test SET status = NOT status;
UPDATE 2

S2:
test=> UPDATE mvcc_test SET status = true WHERE status = false;
UPDATE 0

S1:
test=> COMMIT;

S2:
test=> SELECT * FROM mvcc_test;
status
--------
t
f
(2 rows)

If the S2 UPDATE was run before or after the S1 UPDATE, it would have
set both rows to true, while you can see the two rows are different.

What is significant about this is that it isn't a serializable failure,
nor is it a SELECT FOR UPDATE failure.

The fundamental behavior above is that the S1 transaction is adding
_and_ removing rows from the S2 query's result set; S2 is seeing the
pre-query values that don't match its criteria and ignoring them and
blocking on a later row that does match its criteria. Once S1 commits,
the new row does not match its criteria and it skips it, making the
SELECT FOR UPDATE return zero rows, and the S2 UPDATE do nothing.

Serializable mode does prevent the problem outlined above.

Is this behavior documented already? If not, where should I add it?
Perhaps section 13.2.1., "Read Committed Isolation Level":

http://developer.postgresql.org/pgdocs/postgres/transaction-iso.html#XACT-SERIALIZABLE

That section vaguely suggests this might happen but doesn't give an
example.

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Bruce Momjian wrote:
> The fundamental behavior above is that the S1 transaction is adding
> _and_ removing rows from the S2 query's result set; S2 is seeing the
> pre-query values that don't match its criteria and ignoring them and
> blocking on a later row that does match its criteria. Once S1 commits,
> the new row does not match its criteria and it skips it, making the
> SELECT FOR UPDATE return zero rows, and the S2 UPDATE do nothing.
>
> Serializable mode does prevent the problem outlined above.

To clarify, serializable throws an error, as expected.

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Bruce Momjian wrote:
> The fundamental behavior above is that the S1 transaction is adding
> _and_ removing rows from the S2 query's result set; S2 is seeing the
> pre-query values that don't match its criteria and ignoring them and
> blocking on a later row that does match its criteria. Once S1 commits,
> the new row does not match its criteria and it skips it, making the
> SELECT FOR UPDATE return zero rows, and the S2 UPDATE do nothing.
>
> Serializable mode does prevent the problem outlined above.
>
> Is this behavior documented already? If not, where should I add it?
> Perhaps section 13.2.1., "Read Committed Isolation Level":
>
> http://developer.postgresql.org/pgdocs/postgres/transaction-iso.html#XACT-SERIALIZABLE
>
> That section vaguely suggests this might happen but doesn't give an
> example.

Well, with no one replying, :-(, I went ahead and added to the Read
Committed section of our manual to show a simple case where our read
committed mode produces undesirable results. I also did a little
cleanup at the same time.

You can see the resulting text here:

http://momjian.us/tmp/pgsql/transaction-iso.html#XACT-READ-COMMITTED

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

>>> Bruce Momjian <bruce(at)momjian(dot)us> wrote:
> Well, with no one replying, :-(, I went ahead and added to the Read
> Committed section of our manual to show a simple case where our read
> committed mode produces undesirable results. I also did a little
> cleanup at the same time.
>
> You can see the resulting text here:
>
>
http://momjian.us/tmp/pgsql/transaction-iso.html#XACT-READ-COMMITTED

So READ COMMITTED allows a single SQL statement to see and act upon a
database state which represents partial completion of a concurrent
database transaction? I'm not sure whether the SQL spec explicitly
prohibits that, but it does seem surprising and potentially dangerous.

At a minimum, the documentation you suggest seems wise. If that can
be prevented, I think it should be. Seriously, this would justify
giving up the guarantee that serialization failures can't happen in
PostgreSQL in READ COMMITTED mode. That guarantee is not required by
the standard, is not present in many databases, and to me it is less
important that accurate results.

-Kevin

Kevin Grittner wrote:
> >>> Bruce Momjian <bruce(at)momjian(dot)us> wrote:
> > Well, with no one replying, :-(, I went ahead and added to the Read
> > Committed section of our manual to show a simple case where our read
> > committed mode produces undesirable results. I also did a little
> > cleanup at the same time.
> >
> > You can see the resulting text here:
> >
> >
> http://momjian.us/tmp/pgsql/transaction-iso.html#XACT-READ-COMMITTED
>
> So READ COMMITTED allows a single SQL statement to see and act upon a
> database state which represents partial completion of a concurrent
> database transaction? I'm not sure whether the SQL spec explicitly
> prohibits that, but it does seem surprising and potentially dangerous.

We often get away with justifying our current behavior by saying the
behavior is correct if we see only the pre-update or post-update
snapshot. The only way I can see to show a clear failure is to see
parts of both, as I showed in the example.

> At a minimum, the documentation you suggest seems wise. If that can
> be prevented, I think it should be. Seriously, this would justify
> giving up the guarantee that serialization failures can't happen in
> PostgreSQL in READ COMMITTED mode. That guarantee is not required by
> the standard, is not present in many databases, and to me it is less
> important that accurate results.

We find adding documentation often helps people see the behavior more
clearly, even if we don't have a fix for it.

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

On Wed, 2009-02-04 at 11:11 -0500, Bruce Momjian wrote:
> Well, with no one replying, :-(, I went ahead and added to the Read
> Committed section of our manual to show a simple case where our read
> committed mode produces undesirable results. I also did a little
> cleanup at the same time.

We could also add something to the SELECT docs. For example:

"FOR SHARE/UPDATE causes the SELECT to behave with the same isolation
semantics as UPDATE or DELETE. You may see results that are impossible
to see using SELECT without FOR UPDATE/SHARE. See Chapter 13."

The current SELECT FOR UPDATE/SHARE docs do address the issue, but most
of the discussion revolves around locking semantics, not isolation. I
think the important missing piece is "...you may see results that are
impossible to see using SELECT...".

I've learned a few things during this discussion, but the most
surprising thing to me was that FOR SHARE/UPDATE really change the
isolation semantics, and that it's more like UPDATE than SELECT.

Regards,
Jeff Davis

Jeff Davis wrote:
> On Wed, 2009-02-04 at 11:11 -0500, Bruce Momjian wrote:
> > Well, with no one replying, :-(, I went ahead and added to the Read
> > Committed section of our manual to show a simple case where our read
> > committed mode produces undesirable results. I also did a little
> > cleanup at the same time.
>
> We could also add something to the SELECT docs. For example:
>
> "FOR SHARE/UPDATE causes the SELECT to behave with the same isolation
> semantics as UPDATE or DELETE. You may see results that are impossible
> to see using SELECT without FOR UPDATE/SHARE. See Chapter 13."
>
> The current SELECT FOR UPDATE/SHARE docs do address the issue, but most
> of the discussion revolves around locking semantics, not isolation. I
> think the important missing piece is "...you may see results that are
> impossible to see using SELECT...".

Well, I think the big issue is that the problem I found was in no way
unique to SELECT FOR UPDATE/SHARE; UPDATE and DELETE have the same
problem, as illustrated, so mentioning it only for SELECT FOR UPDATE
seems odd. I think the existing SELECT FOR UPDATE/SHARE mentions are
unique to SELECT FOR UPDATE/SHARE and should remain.

> I've learned a few things during this discussion, but the most
> surprising thing to me was that FOR SHARE/UPDATE really change the
> isolation semantics, and that it's more like UPDATE than SELECT.

I made that clearer in the read committed docs than it was in the past,
so hopefully that will help.

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +