Re: [BUGS] Status of issue 4593

This may not be the appropriate place to check this, but when I filed
the bug with the tracking number 4593, in relation to some sort order
behavior which seemed erroneous to me. I didn't know how I would be
notified if this was actually considered a bug, etc. so I thought I'd
post here and see what I came up with. If there is a more appropriate
means of tracking bugs by number, please let me know.

Thank you,

Lee McKeeman

"Lee McKeeman" <lmckeeman(at)opushealthcare(dot)com> writes:
> This may not be the appropriate place to check this, but when I filed
> the bug with the tracking number 4593, in relation to some sort order
> behavior which seemed erroneous to me.

That bug number never came by here --- might've gotten eaten by spam
filters? Anyway, we've seen many many complaints about strange sort
ordering, and every one of them boiled down to Postgres doing what
the LC_COLLATE locale setting told it to. Try "show lc_collate".
If it's not "C" you might wish to re-initdb in C locale.

regards, tom lane

I got a "stalled post" message because at the time of filing I was not
on this list. I don't know when moderators would look at it, and if
perhaps they deemed that it should not be posted, so it was discarded
without me being notified. I have the text that was generated by the web
form, and can send it again now that I am on the list, but I don't want
to do so if that's bad form.

To add a little detail, this wasn't that I believed a sort wasn't
correct alphabetically, lexicographically, numerically, etc., but rather
when the sort was being performed.

-Lee

-----Original Message-----
From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
Sent: Monday, January 05, 2009 8:39 AM
To: Lee McKeeman
Cc: pgsql-bugs(at)postgresql(dot)org
Subject: Re: [BUGS] Status of issue 4593

"Lee McKeeman" <lmckeeman(at)opushealthcare(dot)com> writes:
> This may not be the appropriate place to check this, but when I filed
> the bug with the tracking number 4593, in relation to some sort order
> behavior which seemed erroneous to me.

That bug number never came by here --- might've gotten eaten by spam
filters? Anyway, we've seen many many complaints about strange sort
ordering, and every one of them boiled down to Postgres doing what
the LC_COLLATE locale setting told it to. Try "show lc_collate".
If it's not "C" you might wish to re-initdb in C locale.

regards, tom lane

On Mon, Jan 5, 2009 at 2:47 PM, Lee McKeeman
<lmckeeman(at)opushealthcare(dot)com> wrote:
> I got a "stalled post" message because at the time of filing I was not
> on this list. I don't know when moderators would look at it, and if
> perhaps they deemed that it should not be posted, so it was discarded
> without me being notified.

We don't moderate bug reports, except to weed out spam. My guess is
that yours was dropped in error.

--
Dave Page
EnterpriseDB UK: http://www.enterprisedb.com

In that case, I will paste what I got back when I entered the bug via
the web form:
- - - - - -
The following bug has been logged online:

Bug reference: 4593
Logged by: Lee McKeeman
Email address: lmckeeman(at)opushealthcare(dot)com
PostgreSQL version: 8.3.4, 8.2.6
Operating system: Red Hat Enterprise Linux Server release 5
Description: order by is not honored after select ... for update
when
row-lock is encountered
Details:

Some brief background: our application depends on the ordering of
results in a number of cases, and we have been relying on the order by
clause to provide this.

Steps to reproduce:
First, steps need to be performed via two connections. I will provide
the SQL to set up the database state, then the steps, in order, to be
performed on each connections.

Setup:
create table test (value int, key int primary key); insert into test
(key,value) values (1,20); insert into test (key,value) values (2,25);
insert into test (key,value) values (3,30); insert into test (key,value)
values (4,500);

Seemingly erroneous scenario:
From connection 1:
begin;
select * from test order by value for update; Return value:
value | key
-------+-----
20 | 1
25 | 2
30 | 3
500 | 4
(4 rows)

From connection 2:
begin;
select * from test order by value for update; At this point,
connection 2 waits on connection 1.

From connection 1:
update test set value = 40 where key = 1;
commit;

From connection 2:
previous query now returns:
value | key
-------+-----
40 | 1
25 | 2
30 | 3
500 | 4
(4 rows)

At this point the transaction on connection 2 can be ended, this is all
that is necessary to demonstrate this behavior. The order by clause was
not honored insofar as the data returned does not match the order the
rows are returned in. The order is, instead, in the order the rows would
have been in before the transaction on connection 1 was completed.

I visited #postgresql on FreeNode on Friday and was told that this was
not a bug, and I needed to use:
set transaction isolation level serializable; then handle the possible:
"could not serialize access due to concurrent update"
errors. I also read:
http://www.postgresql.org/docs/8.3/interactive/transaction-iso.html

I did not see anything that indicated to me that order by may not be
handled properly at the read committed isolation level, so I do believe
this to be erroneous behavior, and therefore a bug. I have attempted
this in 8.3.4 and
8.2.6 as I have ready access to installations of these versions. I can
likely get access to an 8.3.5 installation if necessary for this bug to
be investigated, but don't have one available to me at this time.

I am currently working on a work-around in our software using the
serializable isolation level, but it obviously adds complexity.
Apologies if this is indeed expected behavior, but having the data by
which a result set should be ordered by failing to match the actual
order returned does seem like a bug from my perspective.

If clarification is needed, please contact me at the address provided.

Thank you,
Lee McKeeman
- - - - -

I don't know how issue numbers are assigned, and I can re-enter this via
the web form if that would be helpful.

-Lee

-----Original Message-----
From: Dave Page [mailto:dpage(at)pgadmin(dot)org]
Sent: Monday, January 05, 2009 8:57 AM
To: Lee McKeeman
Cc: pgsql-bugs(at)postgresql(dot)org
Subject: Re: [BUGS] Status of issue 4593

On Mon, Jan 5, 2009 at 2:47 PM, Lee McKeeman
<lmckeeman(at)opushealthcare(dot)com> wrote:
> I got a "stalled post" message because at the time of filing I was not
> on this list. I don't know when moderators would look at it, and if
> perhaps they deemed that it should not be posted, so it was discarded
> without me being notified.

We don't moderate bug reports, except to weed out spam. My guess is
that yours was dropped in error.

--
Dave Page
EnterpriseDB UK: http://www.enterprisedb.com

On Mon, 2009-01-05 at 09:03 -0600, Lee McKeeman wrote:
> I did not see anything that indicated to me that order by may not be
> handled properly at the read committed isolation level, so I do believe
> this to be erroneous behavior, and therefore a bug. I have attempted
> this in 8.3.4 and
> 8.2.6 as I have ready access to installations of these versions. I can
> likely get access to an 8.3.5 installation if necessary for this bug to
> be investigated, but don't have one available to me at this time.

This looks like a bug to me, as well. Transaction isolation affects
visibility of tuples, but ORDER BY should still work. Your example also
works if using FOR SHARE in connection 2.

The manual does have this to say about FOR UPDATE/SHARE:

"It is possible for a SELECT command using both LIMIT and FOR
UPDATE/SHARE clauses to return fewer rows than specified by LIMIT. This
is because LIMIT is applied first. The command selects the specified
number of rows, but might then block trying to obtain lock on one or
more of them. Once the SELECT unblocks, the row might have been deleted
or updated so that it does not meet the query WHERE condition anymore,
in which case it will not be returned."
-- http://www.postgresql.org/docs/8.3/static/sql-select.html

I'm sure something very similar is happening with ORDER BY, so it should
be documented at a minimum.

However, I think we should consider your issue more serious, because I
think this it a violation of the SQL standard. I've been wrong about the
SQL standard plenty of times though, so don't take my word for it ;)

Regards,
Jeff Davis

"Lee McKeeman" <lmckeeman(at)opushealthcare(dot)com> writes:
> Description: order by is not honored after select ... for update

The reason for this behavior is that SELECT FOR UPDATE substitutes the
latest version of the row at the time the row lock is acquired, which is
the very last step after the selection and ordering have been done.
In your example, what the ORDER BY sees is 20/25/30/300, and it sorts on
that basis, and then the 20/1 row is discovered not to be live anymore
so the 40/1 row is locked and substituted.

The only way to avoid this would be to lock before the sort, which could
have the effect of locking more rows than are returned (if you also use
LIMIT); or to repeat the sort operation after locking the rows, which I
doubt anyone is going to want it to do. I suggest sorting on the client
side if you really need this to work in this particular way.

[ thinks for awhile... ] Actually you could make it work entirely on
the server if you were willing to interpose a SQL function, along the
lines of

create function foo () returns setof test as
$$ select * from test order by value for update $$
language sql;

select * from foo() order by value;

which would accomplish the desired result of having two levels of sort.
(You might or might not need the ORDER BY inside the function --- does
your real case use ORDER BY/LIMIT, or does it really lock every row
of the table?)

regards, tom lane

Tom,

We don't actually select * without a where clause in our actual use
case, I just wrote as concise a test case as I thought I could to
demonstrate the behavior. We have a where clause that limits the rows
that are locked (otherwise we could just do a table lock rather than
using row-level locking). In our actual case, the order by uses a
function that generates ordinality based on some external values. If we
were to use your function suggestion, it could accept two arguments that
would be used in the where clause, and the select ... for update in the
function would not need to do any ordering (there is no limit involved
here), then when selecting from the function the order by could be
applied (I think). It's something we could work with.

Right now we are selecting twice to work around this, because once we
have the rows locked in our transaction, the order (as far as I can
imagine) should not change after the lock is acquired. This is somewhat
inefficient, but the where clause uses two indexed columns, so it isn't
terrible. The initial select ... for update at this point is not using
an order, so it is a bit faster, then the second does use the order and
should always be correct since the rows are locked.

Based on your explanation I understand the reason for this behavior
which was what I and my colleagues had guessed, but you didn't assert
that this is expected/correct behavior. Is it?

Ultimately, if we were to use your function suggestion, we would have
something like:

create function mytablefunction(integer,integer) returns setof mytable
as
$$ select * from mytable where col1 > $1 and col2 = $2 for update $$
language sql;

select * from mytablefunction(10,1000) order by sortfunc(col3);

I don't know if, in the select, a column from the resulting rowset can
be used in a function in the order by clause. I've never tried it
before, but don't see why it wouldn't work.

This seems workable, and wouldn't add a terrible amount of complexity.

Also, it is certainly valid to do the sort in our app, but we had simply
come to depend on ORDER BY, and built up the necessary infrastructure in
the database(functions, etc.) to do all the ordering there. We certainly
could pull the sorting into the app, it would just be much uglier than
using the database.

Thanks,
-Lee

-----Original Message-----
From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
Sent: Monday, January 05, 2009 2:42 PM
To: Lee McKeeman
Cc: pgsql-bugs(at)postgresql(dot)org
Subject: Re: [BUGS] Status of issue 4593

"Lee McKeeman" <lmckeeman(at)opushealthcare(dot)com> writes:
> Description: order by is not honored after select ... for
update

The reason for this behavior is that SELECT FOR UPDATE substitutes the
latest version of the row at the time the row lock is acquired, which is
the very last step after the selection and ordering have been done.
In your example, what the ORDER BY sees is 20/25/30/300, and it sorts on
that basis, and then the 20/1 row is discovered not to be live anymore
so the 40/1 row is locked and substituted.

The only way to avoid this would be to lock before the sort, which could
have the effect of locking more rows than are returned (if you also use
LIMIT); or to repeat the sort operation after locking the rows, which I
doubt anyone is going to want it to do. I suggest sorting on the client
side if you really need this to work in this particular way.

[ thinks for awhile... ] Actually you could make it work entirely on
the server if you were willing to interpose a SQL function, along the
lines of

create function foo () returns setof test as
$$ select * from test order by value for update $$
language sql;

select * from foo() order by value;

which would accomplish the desired result of having two levels of sort.
(You might or might not need the ORDER BY inside the function --- does
your real case use ORDER BY/LIMIT, or does it really lock every row
of the table?)

regards, tom lane

On Mon, 2009-01-05 at 15:42 -0500, Tom Lane wrote:
> The only way to avoid this would be to lock before the sort, which could
> have the effect of locking more rows than are returned (if you also use
> LIMIT);

How would that work in the case of an index scan sort?

Regards,
Jeff Davis

Jeff Davis <pgsql(at)j-davis(dot)com> writes:
> On Mon, 2009-01-05 at 15:42 -0500, Tom Lane wrote:
>> The only way to avoid this would be to lock before the sort, which could
>> have the effect of locking more rows than are returned (if you also use
>> LIMIT);

> How would that work in the case of an index scan sort?

It wouldn't, which is one of the problems with doing it any other way...

I don't think there's a bug here, at least not in the sense that it
isn't Operating As Designed. But it does seem like we could do with
some more/better documentation about exactly how FOR UPDATE works.
The sequence of operations is evidently a bit more user-visible than
I'd realized.

regards, tom lane

On Tuesday 06 January 2009 02:03:14 Tom Lane wrote:
> I don't think there's a bug here, at least not in the sense that it
> isn't Operating As Designed.  But it does seem like we could do with
> some more/better documentation about exactly how FOR UPDATE works.
> The sequence of operations is evidently a bit more user-visible than
> I'd realized.

Well, if the effect of ORDER BY + FOR UPDATE is "it might in fact not be
ordered", then it's pretty broken IMO. It would be pretty silly by analogy
for example, if the effect of GROUP BY + FOR UPDATE were "depending on
concurrent events, it may or may not be fully grouped".

Peter Eisentraut wrote:
> On Tuesday 06 January 2009 02:03:14 Tom Lane wrote:
>> I don't think there's a bug here, at least not in the sense that it
>> isn't Operating As Designed. But it does seem like we could do with
>> some more/better documentation about exactly how FOR UPDATE works.
>> The sequence of operations is evidently a bit more user-visible than
>> I'd realized.
>
> Well, if the effect of ORDER BY + FOR UPDATE is "it might in fact not be
> ordered", then it's pretty broken IMO. It would be pretty silly by analogy
> for example, if the effect of GROUP BY + FOR UPDATE were "depending on
> concurrent events, it may or may not be fully grouped".

I can see two ways forward:

1) We document bluntly that ORDER BY + FOR UPDATE can return unordered
results, or

2) We prohibit ORDER BY + FOR UPDATE, like we do with a number of other
clauses. (There would be no loss of functionality, because you can run
the query a second time in the transaction with ORDER BY.)

Comments?

Peter Eisentraut <peter_e(at)gmx(dot)net> writes:
> I can see two ways forward:

> 1) We document bluntly that ORDER BY + FOR UPDATE can return unordered
> results, or

> 2) We prohibit ORDER BY + FOR UPDATE, like we do with a number of other
> clauses. (There would be no loss of functionality, because you can run
> the query a second time in the transaction with ORDER BY.)

That code has been working like this for eight or ten years now and this
is the first complaint, so taking away functionality on the grounds that
someone might happen to update the ordering column doesn't seem like the
answer to me.

regards, tom lane

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> Peter Eisentraut <peter_e(at)gmx(dot)net> writes:
>> I can see two ways forward:
>
>> 1) We document bluntly that ORDER BY + FOR UPDATE can return unordered
>> results, or
>
>> 2) We prohibit ORDER BY + FOR UPDATE, like we do with a number of other
>> clauses. (There would be no loss of functionality, because you can run
>> the query a second time in the transaction with ORDER BY.)
>
> That code has been working like this for eight or ten years now and this
> is the first complaint, so taking away functionality on the grounds that
> someone might happen to update the ordering column doesn't seem like the
> answer to me.

Can we detect it at run-time? If a recheck happens can we somehow know which
columns could be problematic to find updated and check that they're unchanged?
I'm pretty sure the answer is no, but I figured I would throw it out there in
case it gives anyone an idea.

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

While this behavior may be very old, I would still contend that it is
incorrect (or at least inconsistent with one's expectations). If it will
not be changed, some additional documentation might be helpful. Perhaps
a WARNING could be raised (unconditionally, as it might be a bit
intensive to detect when the problem has occurred)?

It may be nice, though it would obviously be an extension, to have
session-level settings that will cause 2 queries to be run
independently, first the for update, second the order by when both are
present, so one doesn't have to handle this every place they want to
perform queries with these two clauses. Alternatively, since two queries
is less efficient, perhaps if this setting is active a temporary
function can be created to implement the work-around Tom mentioned
earlier in the thread automatically (though perhaps creating and
compiling the function would be slower than the second select in some
cases). Again, this would allow for correct behavior without a great
deal of schema and code modification.

I guess my real point is that while no one else has complained about it,
I'm confident others do and will continue to use these two clauses in
the same query. In general, when one uses ORDER BY, they expect their
results ordered based on the data returned. Being able to explain the
reason for this inconsistency is nice, but it certainly doesn't
invalidate the problem.

-Lee

-----Original Message-----
From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
Sent: Monday, January 12, 2009 7:33 AM
To: Peter Eisentraut
Cc: PG Hackers; Jeff Davis; Lee McKeeman
Subject: Re: [BUGS] Status of issue 4593

Peter Eisentraut <peter_e(at)gmx(dot)net> writes:
> I can see two ways forward:

> 1) We document bluntly that ORDER BY + FOR UPDATE can return unordered

> results, or

> 2) We prohibit ORDER BY + FOR UPDATE, like we do with a number of
other
> clauses. (There would be no loss of functionality, because you can
run
> the query a second time in the transaction with ORDER BY.)

That code has been working like this for eight or ten years now and this
is the first complaint, so taking away functionality on the grounds that
someone might happen to update the ordering column doesn't seem like the
answer to me.

regards, tom lane

On Mon, 2009-01-12 at 15:26 +0200, Peter Eisentraut wrote:
> 1) We document bluntly that ORDER BY + FOR UPDATE can return unordered
> results, or
>
> 2) We prohibit ORDER BY + FOR UPDATE, like we do with a number of other
> clauses. (There would be no loss of functionality, because you can run
> the query a second time in the transaction with ORDER BY.)
>

I like Lee's idea of a WARNING plus a documentation note -- seems like a
reasonable compromise. Maybe we can add the prohibition later if we
still don't have a fix for it.

Regards,
Jeff Davis

On Mon, Jan 12, 2009 at 8:32 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Peter Eisentraut <peter_e(at)gmx(dot)net> writes:
>> I can see two ways forward:
>
>> 1) We document bluntly that ORDER BY + FOR UPDATE can return unordered
>> results, or
>
>> 2) We prohibit ORDER BY + FOR UPDATE, like we do with a number of other
>> clauses. (There would be no loss of functionality, because you can run
>> the query a second time in the transaction with ORDER BY.)
>
> That code has been working like this for eight or ten years now and this
> is the first complaint, so taking away functionality on the grounds that
> someone might happen to update the ordering column doesn't seem like the
> answer to me.

If the only case where ORDER BY + FOR UPDATE are not strictly
compatible is when the columns being updated are the same as the
columns of the sort, a blanket prohibition against using the two
together seems like it prohibits an awful lot of useful things someone
might want to do. Saying that you can run the query a second time as
a workaround so there's no loss of functionality is true only if you
accept the proposition that performance is not a requirement.

...Robert

On Mon, 2009-01-12 at 08:32 -0500, Tom Lane wrote:
> That code has been working like this for eight or ten years now and this
> is the first complaint, so taking away functionality on the grounds that
> someone might happen to update the ordering column doesn't seem like the
> answer to me.
>

If they are using FOR UPDATE, they clearly expect concurrent updates. If
they're using ORDER BY, they clearly expect the results to be in order.

So who is the target user of this functionality we're trying to protect?

Regards,
Jeff Davis

On Mon, 2009-01-12 at 12:47 -0500, Robert Haas wrote:
> If the only case where ORDER BY + FOR UPDATE are not strictly
> compatible is when the columns being updated are the same as the
> columns of the sort, a blanket prohibition against using the two
> together seems like it prohibits an awful lot of useful things someone
> might want to do.

As long as the people using it are aware that they can't update the
ordering columns, it may make sense to leave that functionality in
there.

Can you expand on "an awful lot of useful things"? It seems like an edge
case to me, and the restriction it imposes is quite awkward to meet.
"OK, nobody ever update these fields in this table.".

Regards,
Jeff Davis

"Robert Haas" <robertmhaas(at)gmail(dot)com> writes:
> On Mon, Jan 12, 2009 at 8:32 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> That code has been working like this for eight or ten years now and this
>> is the first complaint, so taking away functionality on the grounds that
>> someone might happen to update the ordering column doesn't seem like the
>> answer to me.

> If the only case where ORDER BY + FOR UPDATE are not strictly
> compatible is when the columns being updated are the same as the
> columns of the sort, a blanket prohibition against using the two
> together seems like it prohibits an awful lot of useful things someone
> might want to do.

Exactly.

> Saying that you can run the query a second time as
> a workaround so there's no loss of functionality is true only if you
> accept the proposition that performance is not a requirement.

Right, and also I'm unconvinced that it is really equivalent. If you've
got something like an ORDER BY LIMIT and the ordering columns are
changing, you may very well get a different set of rows from the second
query ... not all of which got locked the first time, so there's going
to be some tail-chasing involved there.

A re-sort after locking doesn't really make things all nice and
intuitive either. Suppose that the values of X are 10,20,30,40,50
and we do SELECT ... ORDER BY x LIMIT 3 FOR UPDATE. Concurrently
someone updates the 20 to 100. The existing code locks the 10,20,30
rows, then notices the 20 got updated to 100, and returns you
10,100,30. If it re-sorted you would get 10,30,100, but on what
grounds is that the correct answer and not 10,20,40? If you want
to argue that 10,20,40 is the correct answer, how are you going to
arrive at it without locking more rows than are returned?

And just to bend your brain a bit more, what if the same update command
that changed 20 to 100 also changed 50 to 1? Surely if we take the one
row change into account in determining the sort order, we ought to
notice that one too. However, we aren't even going to *see* that row
unless we traverse the entire table.

I think the behavior Lee is expecting is only implementable with a
full-table write lock, which is exactly what FOR UPDATE is designed
to avoid. There are certain properties you don't get with a partial
lock, and in the end I think we can't do much except document them.
We have LOCK TABLE for those who need the other behavior.

regards, tom lane

>>> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> A re-sort after locking doesn't really make things all nice and
> intuitive either. Suppose that the values of X are 10,20,30,40,50
> and we do SELECT ... ORDER BY x LIMIT 3 FOR UPDATE. Concurrently
> someone updates the 20 to 100. The existing code locks the 10,20,30
> rows, then notices the 20 got updated to 100, and returns you
> 10,100,30. If it re-sorted you would get 10,30,100, but on what
> grounds is that the correct answer and not 10,20,40? If you want
> to argue that 10,20,40 is the correct answer, how are you going to
> arrive at it without locking more rows than are returned?

Would it make any sense to roll back and generate a
SERIALIZATION_FAILURE? In other databases I've seen this failure
code used for all situations where they can't perform the requested
operation due to concurrent transactions, regardless of transaction
isolation level.

That seems more intuitive to me than any of the alternatives discussed
so far, which all seem to involve quietly returning something other
than what was specified.

-Kevin

"Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> A re-sort after locking doesn't really make things all nice and
>> intuitive either.

> Would it make any sense to roll back and generate a
> SERIALIZATION_FAILURE?

If that's what you want then you run the transaction in serializable
mode. The point of doing it in READ COMMITTED mode is that you don't
want such a failure.

regards, tom lane

>>> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> "Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
>> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> A re-sort after locking doesn't really make things all nice and
>>> intuitive either.
>
>> Would it make any sense to roll back and generate a
>> SERIALIZATION_FAILURE?
>
> If that's what you want then you run the transaction in serializable
> mode. The point of doing it in READ COMMITTED mode is that you
don't
> want such a failure.

Well, that's a PostgreSQL-specific point of view, although I
understand the point of maintaining that guarantee. (In Microsoft SQL
Server and Sybase ASE we actually had to run our read-only web
application at the READ UNCOMMITTED transaction isolation level
because so many SELECT queries were rolled back when they deadlocked
with the traffic from replication when they were all running at READ
COMMITTED.)

If you run this at SERIALIZABLE transaction isolation level, would
PostgreSQL currently roll something back before returning rows in an
order different than that specified by the ORDER BY clause?

-Kevin

On Mon, 2009-01-12 at 13:35 -0500, Tom Lane wrote:
> I think the behavior Lee is expecting is only implementable with a
> full-table write lock, which is exactly what FOR UPDATE is designed
> to avoid. There are certain properties you don't get with a partial
> lock, and in the end I think we can't do much except document them.
> We have LOCK TABLE for those who need the other behavior.
>

Lee said specifically that he's not using LIMIT, and there's already a
pretty visible warning in the docs for using LIMIT with FOR UPDATE.
Also, using LIMIT + FOR UPDATE has a dangerous-looking quality to it (at
least to me) that would cause me to do a little more investigation
before relying on its behavior.

I'm not pushing for FOR UPDATE + ORDER BY to be blocked outright, but I
think it's strange enough that it should be considered some kind of
defect worse than the cases involving LIMIT that you mention.

Regards,
Jeff Davis

"Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> If that's what you want then you run the transaction in serializable
>> mode.

> If you run this at SERIALIZABLE transaction isolation level, would
> PostgreSQL currently roll something back before returning rows in an
> order different than that specified by the ORDER BY clause?

Yes, it would roll back as soon as it found that any of the selected
rows had been concurrently modified. The behavior where you get back
the updated version of the row is specific to READ COMMITTED mode.

regards, tom lane

Tom Lane wrote:
> "Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
>> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> A re-sort after locking doesn't really make things all nice and
>>> intuitive either.
>
>> Would it make any sense to roll back and generate a
>> SERIALIZATION_FAILURE?
>
> If that's what you want then you run the transaction in serializable
> mode. The point of doing it in READ COMMITTED mode is that you don't
> want such a failure.

Well, you can get deadlocks in read committed mode, so it is not like
this mode is totally free of concurrency related failure possibilities.

Both serialization errors and deadlocks assume a write operation though.

But could we detect this case at all? That is, when we are re-reading
the updated tuple, do we remember that we did some sorting earlier?

Kevin Grittner wrote:
> Well, that's a PostgreSQL-specific point of view, although I
> understand the point of maintaining that guarantee. (In Microsoft SQL
> Server and Sybase ASE we actually had to run our read-only web
> application at the READ UNCOMMITTED transaction isolation level
> because so many SELECT queries were rolled back when they deadlocked
> with the traffic from replication when they were all running at READ
> COMMITTED.)

Per SQL standard, READ UNCOMMITTED mode requires READ ONLY transaction
access mode, so you couldn't do FOR UPDATE there anyway. (Of course,
FOR UPDATE is not in the standard.)

> If you run this at SERIALIZABLE transaction isolation level, would
> PostgreSQL currently roll something back before returning rows in an
> order different than that specified by the ORDER BY clause?

Yes, but using FOR UPDATE is kind of pointless in serializable mode.

>>> Peter Eisentraut <peter_e(at)gmx(dot)net> wrote:
> Kevin Grittner wrote:
>> (In Microsoft SQL Server and Sybase ASE we actually had to run our
>> read-only web application at the READ UNCOMMITTED transaction
>> isolation level because so many SELECT queries were rolled back
>> when they deadlocked with the traffic from replication when they
>> were all running at READ COMMITTED.)
>
> Per SQL standard, READ UNCOMMITTED mode requires READ ONLY
transaction
> access mode, so you couldn't do FOR UPDATE there anyway.

My only point was that other DBMSs often generate serialization
failures on SELECT-only transactions in READ COMMITTED mode.
Sometimes quite a few of them. I also recognized that if PostgreSQL
can provide guarantees not required by the standard that such things
won't happen, I can see the value of that.

>> If you run this at SERIALIZABLE transaction isolation level, would
>> PostgreSQL currently roll something back before returning rows in
an
>> order different than that specified by the ORDER BY clause?
>
> Yes, but using FOR UPDATE is kind of pointless in serializable mode.

Well, for transactions which only SELECT, sure. Is there no use case
for them outside of that? (That's not rhetorical -- I'm not really
sure.)

-Kevin

>>> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> "Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
>> Would it make any sense to roll back and generate a
>> SERIALIZATION_FAILURE?
>
> If that's what you want then you run the transaction in serializable
> mode. The point of doing it in READ COMMITTED mode is that you
> don't want such a failure.

Wait a minute -- there is not such guarantee in PostgreSQL when you
start using WITH UPDATE on SELECT statements in READ COMMITTED mode.
By starting two transactions in READ COMMITTED, and having each do two
SELECTs WITH UPDATE (in opposite order) I was able to generate this:

ERROR: deadlock detected
DETAIL: Process 4945 waits for ShareLock on transaction 20234373;
blocked by process 5185.
Process 5185 waits for ShareLock on transaction 20233798; blocked by
process 4945.

So, wouldn't it be better, if it's actually feasible to detect the
problem situation, to make this another situation where SELECT FOR
UPDATE can cause serialization failures? That would allow
applications to count on getting the rows in the requested order if
the query completes successfully. If existing documentation doesn't
already cover the possibility of serialization failures when using FOR
UPDATE, it should. If we need to document something around the issue
of this thread, that seems like the place to do it.

-Kevin

"Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>> If that's what you want then you run the transaction in serializable
>> mode. The point of doing it in READ COMMITTED mode is that you
>> don't want such a failure.

> Wait a minute -- there is not such guarantee in PostgreSQL when you
> start using WITH UPDATE on SELECT statements in READ COMMITTED mode.
> By starting two transactions in READ COMMITTED, and having each do two
> SELECTs WITH UPDATE (in opposite order) I was able to generate this:
> ERROR: deadlock detected

Huh? Deadlocks were not the issue here. What you asked for was a
failure if someone else had updated the rows you're selecting for
update.

regards, tom lane

>>> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Huh? Deadlocks were not the issue here. What you asked for was a
> failure if someone else had updated the rows you're selecting for
> update.

Logically, these are both forms of serialization failure when doing
SELECT FOR UPDATE in READ COMMITTED mode. One currently deadlocks,
generating an error that requires a retry. The other quietly fails to
return the requested results. I'm suggesting that it would be better
to generate an error with an indication of the serialization failure.
You said that people use READ COMMITTED to avoid such errors. I'm
pointing out that they can currently get serialization failure errors
in READ COMMITTED if they choose to SELECT FOR UPDATE.

-Kevin

Kevin,

> So, wouldn't it be better, if it's actually feasible to detect the
> problem situation, to make this another situation where SELECT FOR
> UPDATE can cause serialization failures? That would allow
> applications to count on getting the rows in the requested order if
> the query completes successfully. If existing documentation doesn't
> already cover the possibility of serialization failures when using FOR
> UPDATE, it should. If we need to document something around the issue
> of this thread, that seems like the place to do it.

That's not how SELECT FOR UPDATE works. SFU is pessimistic manual
locking, which is supposed to *wait* for the rows to be exclusively
available. The deadlock timeout you encountered is the correct
behaviour, not "serialization failure", which is what happens at commit
time when the engine realizes that concurrent transactions are not
serializably recreateable.

--Josh

>>> Josh Berkus <josh(at)agliodbs(dot)com> wrote:
> That's not how SELECT FOR UPDATE works. SFU is pessimistic manual
> locking, which is supposed to *wait* for the rows to be exclusively
> available. The deadlock timeout you encountered is the correct
> behaviour, not "serialization failure", which is what happens at
commit
> time when the engine realizes that concurrent transactions are not
> serializably recreateable.

Deadlocks like this are the only kind of serialization error possible
under "traditional" (non-MVCC) databases. These are much more rare in
MVCC than update conflicts, but that doesn't mean they aren't
serialization failures there, too. I think it is a violation of the
standard for PostgreSQL not to report them with SQLSTATE '40001'.

-Kevin

> Deadlocks like this are the only kind of serialization error possible
> under "traditional" (non-MVCC) databases. These are much more rare in
> MVCC than update conflicts, but that doesn't mean they aren't
> serialization failures there, too. I think it is a violation of the
> standard for PostgreSQL not to report them with SQLSTATE '40001'.

I'm not sure that inductive reasoning applies to the SQL standard. And
we'd break 100,000 existing Java applications if we changed the error.
In my opinion, this falls under the heading of "it would be a nice thing
to do if we were starting over, but not now."

--Josh

>>> Josh Berkus <josh(at)agliodbs(dot)com> wrote:
> we'd break 100,000 existing Java applications if we changed the
error.

In what way would an application want to treat deadlocks and update
conflicts differently? Both result from conflicts with concurrent
transactions and can be retried automatically. It seems like an
implementation detail with little chance of impact on applications to
me. Can anyone provide a contrary example or argument?

-Kevin

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

>>>> Josh Berkus <josh(at)agliodbs(dot)com> wrote:
>> we'd break 100,000 existing Java applications if we changed the
> error.
>
> In what way would an application want to treat deadlocks and update
> conflicts differently? Both result from conflicts with concurrent
> transactions and can be retried automatically. It seems like an
> implementation detail with little chance of impact on applications to
> me. Can anyone provide a contrary example or argument?

Well generally deadlocks are treated differently in that they are treated by
rewriting the application to not cause deadlocks.

--
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:
> "Kevin Grittner" <Kevin(dot)Grittner(at)wicourts(dot)gov> writes:
>> In what way would an application want to treat deadlocks and update
>> conflicts differently? Both result from conflicts with concurrent
>> transactions and can be retried automatically. It seems like an
>> implementation detail with little chance of impact on applications
to
>> me. Can anyone provide a contrary example or argument?
>
> Well generally deadlocks are treated differently in that they are
treated by
> rewriting the application to not cause deadlocks.

I certainly don't propose changing the PostgreSQL error number or the
content of what is logged. Just the SQLSTATE. How would that make
what you suggest harder? It would certainly allow applications and
frameworks which are SQLSTATE-aware to automatically recover from
these until the rewrite is complete, which can hardly be considered a
bad thing.

-Kevin

Jeff Davis wrote:
> On Mon, 2009-01-12 at 13:35 -0500, Tom Lane wrote:
> > I think the behavior Lee is expecting is only implementable with a
> > full-table write lock, which is exactly what FOR UPDATE is designed
> > to avoid. There are certain properties you don't get with a partial
> > lock, and in the end I think we can't do much except document them.
> > We have LOCK TABLE for those who need the other behavior.
> >
>
> Lee said specifically that he's not using LIMIT, and there's already a
> pretty visible warning in the docs for using LIMIT with FOR UPDATE.
> Also, using LIMIT + FOR UPDATE has a dangerous-looking quality to it (at
> least to me) that would cause me to do a little more investigation
> before relying on its behavior.
>
> I'm not pushing for FOR UPDATE + ORDER BY to be blocked outright, but I
> think it's strange enough that it should be considered some kind of
> defect worse than the cases involving LIMIT that you mention.

I have added the attached documentation mention to CVS HEAD and 8.3.X.
If people want a TODO entry or to issue a WARNING message on use, please
let me know. This does seem similar to the FOR UPDATE / LIMIT issue so
I handled it similarly.

--
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. +