Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + If your life is a hard drive, Christ can be your backup. + Index: doc/src/sgml/mvcc.sgml === RCS file: /cvsroot/pgsql/doc/src/sgml/mvcc.sgml,v retrieving revision 2.69 diff -c -c -r2.69 mvcc.sgml *** doc/src/sgml/mvcc.sgml 18 Feb 2007 01:21:49 - 2.69 --- doc/src/sgml/mvcc.sgml 4 Feb 2009 16:01:43 - *** *** 239,257 /indexterm para ! firsttermRead Committed/firstterm ! is the default isolation level in productnamePostgreSQL/productname. ! When a transaction runs on this isolation level, ! a commandSELECT/command query sees only data committed before the ! query began; it never sees either uncommitted data or changes committed ! during query execution by concurrent transactions. (However, the ! commandSELECT/command does see the effects of previous updates ! executed within its own transaction, even though they are not yet ! committed.) In effect, a commandSELECT/command query ! sees a snapshot of the database as of the instant that that query ! begins to run. Notice that two successive commandSELECT/command commands can ! see different data, even though they are within a single transaction, if ! other transactions commit changes during execution of the first commandSELECT/command. /para --- 239,257 /indexterm para ! firsttermRead Committed/firstterm is the default isolation ! level in productnamePostgreSQL/productname. When a transaction ! uses this isolation level, a commandSELECT/command query ! (without a literalFOR UPDATE/SHARE/ clause) sees only data ! committed before the query began; it never sees either uncommitted ! data or changes committed during query execution by concurrent ! transactions. In effect, a commandSELECT/command query sees ! a snapshot of the database as of the instant the query begins to ! run. However, commandSELECT/command does see the effects ! of previous updates executed within its own transaction, even ! though they are not yet committed. Also note that two successive ! commandSELECT/command commands can see different data, even ! though they are within a single transaction, if other transactions commit changes during execution of the first commandSELECT/command. /para *** *** 271,292 otherwise it will attempt to apply its operation to the updated version of the row. The search condition of the command (the literalWHERE/ clause) is re-evaluated to see if the updated version of the row still matches the ! search condition. If so, the second updater proceeds with its operation, ! starting from the updated version of the row. (In the case of commandSELECT FOR UPDATE/command and commandSELECT FOR ! SHARE/command, that means it is the updated version of the row that is ! locked and returned to the client.) /para para 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 screen BEGIN; --- 271,292 otherwise it will attempt to apply its operation to the updated version of the
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Bruce Momjian br...@momjian.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Kevin Grittner wrote: Bruce Momjian br...@momjian.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 br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + If your life is a hard drive, Christ can be your backup. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + If your life is a hard drive, Christ can be your backup. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Kevin Grittner wrote:
Tom Lane t...@sss.pgh.pa.us wrote:
Jeff Davis pg...@j-davis.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 br...@momjian.ushttp://momjian.us
EnterpriseDB http://enterprisedb.com
+ If your life is a hard drive, Christ can be your backup. +
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + If your life is a hard drive, Christ can be your backup. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Jeff Davis pg...@j-davis.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Kevin Grittner kevin.gritt...@wicourts.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! -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Gregory Stark st...@enterprisedb.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Tom Lane t...@sss.pgh.pa.us wrote: Jeff Davis pg...@j-davis.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Jeff Davis pg...@j-davis.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Jeff Davis pg...@j-davis.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Jeff Davis pg...@j-davis.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Jeff Davis pg...@j-davis.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Jeff Davis pg...@j-davis.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! -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Gregory Stark st...@enterprisedb.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
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 pg...@j-davis.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@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
On Sat, 2009-01-24 at 19:45 +, 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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Jeff Davis pg...@j-davis.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] More FOR UPDATE/FOR SHARE problems
Jeff Davis pg...@j-davis.com writes: On Sat, 2009-01-24 at 19:45 +, 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! -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
