Re: Serializable Isolation without blocking

Greg Stark wrote:

> aaah... I think I see where we've gone off track in previous
> discussions...you think postgres keeps row level locks in a shared
> memory data structure. It doesn't it stores all row level locks
> *in* the tuple itself. It only stores the lock in memory briefly
> while actually acquiring the lock. Once it acquires it the only
> record of the lock is the xid in the tuple itself.

> This means there are no memory limits on the number of records
> locked by a transaction.

> storing the lock data in the tuples won't work for you at all
> because you need to lock rows that don't exist yet at all.that's
> why "where to store the lock" is a critical blocking issue to
> figure out to know whether the plan is feasible at all.

I'm probably not quite as clueless as you think on this; I realize
that keeping SIREAD locks in memory will require many more slots for
locks, escalation from tuple level to page or coarser when there are
many on a table, or (most likely) both. Please have patience while I
try to work out the details; until I get a bit farther, everyone will
be spinning their wheels if we try to get too far into details -- it
will all be speculation and/or hand-waving, with much mayhem to straw
men.

This much is fairly firm in my head, so I probably should share:

What I do think is that the structures for regular locks seem usable
to track the information I need without having to burden read
operations with disk output, which I see as absolutely necessary for
adequate performance. It also gives me somewhere to store locks
related to search ranges where data doesn't currently exist, and the
ability to store read locks from many transactions against the same
data.

An open question in my mind is whether I might need to keep write
locks for serializable transactions in the shared memory lock hash
table until commit or rollback; I rather suspect that I will, with
similar granularity escalation policies. That's likely to raise a
hue and cry, but like I've said before -- I won't try to force
anybody to use this, and the structures involved are of reasonable
size to allow using many of them. I suppose these more persistent
write locks should be kept out of the DEFAULT lock method, too....

Thanks, and Happy New Year!

-Kevin

Hi,

Kevin Grittner wrote:
> I'm probably not quite as clueless as you think on this; I realize
> that keeping SIREAD locks in memory will require many more slots for
> locks, escalation from tuple level to page or coarser when there are
> many on a table, or (most likely) both.

..oh, there's the dynamic adjustment idea again. Cool!

> What I do think is that the structures for regular locks seem usable
> to track the information I need without having to burden read
> operations with disk output, which I see as absolutely necessary for
> adequate performance.

I certainly agree that SIREAD locks should never hit the disk. However,
thinking of SIREAD more as marks or hints, I'm not so sure the current
locking structures are appropriate.

If we are talking about table level locks, those are not fine grained
enough and have different semantics (i.e. a user can acquire these
locks, which certainly doesn't make any sense for SIREAD). My gut
feeling is that adjusting them for use with SIREAD is more work than
implementing your own shared memory area for SIREAD marks.

Row level locks are very fine grained, but those are spilled to disk in
its current implementation. So those are an even worse fit for the needs
of SIREAD.

> It also gives me somewhere to store locks
> related to search ranges where data doesn't currently exist, and the
> ability to store read locks from many transactions against the same
> data.

Isn't a hash table in shared memory enough to store the SIREAD locks
(and a lot simpler to manage)?

> An open question in my mind is whether I might need to keep write
> locks for serializable transactions in the shared memory lock hash
> table until commit or rollback

IIUC row level locks are kept in the tuple header until the end of the
transaction (and even beyond). Is this really a problem?

> I suppose these more persistent
> write locks should be kept out of the DEFAULT lock method, too....

I fail to understand that part. What's the DEFAULT lock method?

Regards

Markus Wanner

On Thu, Jan 7, 2010 at 11:08 AM, Markus Wanner <markus(at)bluegap(dot)ch> wrote:
> Row level locks are very fine grained, but those are spilled to disk in
> its current implementation. So those are an even worse fit for the needs
> of SIREAD.
>

I think we're still talking past the issue. Predicate locks are not
row level, nor page level, nor table level. They're locks on
predicates. Ie, you have to lock against values which aren't actually
currently in the table at all. You need to be able to detect a
conflict between a transaction which read rows "WHERE i BETWEEN 1 AND
10" and one which tries to insert a row with i=1 even if the first
transaction didn't see any rows with i=1 (or indeed even if the first
transaction found no rows at all).

That's the hard part. How do you represent such a lock in a way that I
can efficiently find it and check for the conflict when it comes time
for me to do my insert.

And how do you do that without tying the implementation to specific
details of how our planner, table scans, and index access methods
work?

--
greg

On Thu, Jan 7, 2010 at 2:40 PM, Greg Stark <gsstark(at)mit(dot)edu> wrote:
> On Thu, Jan 7, 2010 at 11:08 AM, Markus Wanner <markus(at)bluegap(dot)ch> wrote:
>> Row level locks are very fine grained, but those are spilled to disk in
>> its current implementation. So those are an even worse fit for the needs
>> of SIREAD.
>
> I think we're still talking past the issue. Predicate locks are not
> row level, nor page level, nor table level.

They're not? They're just floating out in space somewhere? There are
several possible ways to implement predicate locks, but every possible
method I can think of involves attaching them at one of those places.

> And how do you do that without tying the implementation to specific
> details of how our planner, table scans, and index access methods
> work?

You don't. You add additional methods to the index AMs to support
predicate locks, just lilke we do when we want them to support
anything else (bitmap index scans, index-only scans, etc.).

...Robert

On Thu, 2010-01-07 at 15:02 -0500, Robert Haas wrote:
> > I think we're still talking past the issue. Predicate locks are not
> > row level, nor page level, nor table level.
>
> They're not? They're just floating out in space somewhere? There are
> several possible ways to implement predicate locks, but every possible
> method I can think of involves attaching them at one of those places.

Consider an exclusion constraint, which is a kind of predicate lock. You
could say that the lock is in the index (now) -- but my first
implementation used a shared memory structure instead, so it's clearly
not required to exist in the index. You could also say that the lock is
really attached to the table, because there are catalog entries
connected to the table that express the constraint -- but I think that's
splitting hairs.

What Greg is saying (as I understand it) is that the lock conflicts with
tuples that don't even exist yet. We can tack them on to any structure
that's convenient, of course. But just because you want to implement
them by locking a few index pages (assuming there is an index) doesn't
mean we should reject Greg's line of thinking.

Regards,
Jeff Davis

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

> Consider an exclusion constraint, which is a kind of predicate
> lock. You could say that the lock is in the index (now) -- but my
> first implementation used a shared memory structure instead, so
> it's clearly not required to exist in the index. You could also
> say that the lock is really attached to the table, because there
> are catalog entries connected to the table that express the
> constraint -- but I think that's splitting hairs.

Well, we're starting by locking entire tables (as a very simple way
to get correctness), then reducing the granularity where we can find
a way to do that. I'll not exclusion constraints as an area needing
R&D. Thanks for pointing it out.

> What Greg is saying (as I understand it) is that the lock
> conflicts with tuples that don't even exist yet. We can tack them
> on to any structure that's convenient, of course. But just because
> you want to implement them by locking a few index pages (assuming
> there is an index) doesn't mean we should reject Greg's line of
> thinking.

As I understand it, Greg's line of thinking is that we should use a
technique which has never proven practical on a large scale:
matching database changes against a list of predicate lock
expressions. It's not that I want to do it any particular way, it's
that I want to get it working in the simplest possible way and then
find things which can be shown to improve overall performance of
meaningful work loads until we have something which has acceptable
performance. I don't reject "pure" predicate tracking, per se -- I
just won't put any time into it, since I don't expect it to work. I
would be overjoyed if Greg or anybody else could prove that wrong
with an optimization patch, say six to twelve months from now when
we hit that phase.

-Kevin

On Thu, 2010-01-07 at 15:01 -0600, Kevin Grittner wrote:
> As I understand it, Greg's line of thinking is that we should use a
> technique which has never proven practical on a large scale:
> matching database changes against a list of predicate lock
> expressions. It's not that I want to do it any particular way, it's
> that I want to get it working in the simplest possible way and then
> find things which can be shown to improve overall performance of
> meaningful work loads until we have something which has acceptable
> performance. I don't reject "pure" predicate tracking, per se -- I
> just won't put any time into it, since I don't expect it to work. I
> would be overjoyed if Greg or anybody else could prove that wrong
> with an optimization patch, say six to twelve months from now when
> we hit that phase.

I think we are in agreement. I was responding to Robert Haas's comment,
because it sounded like he didn't understand Greg Stark's point.

Regards,
Jeff Davis

Hi,

Greg Stark wrote:
> I think we're still talking past the issue. Predicate locks are not
> row level, nor page level, nor table level. They're locks on
> predicates. Ie, you have to lock against values which aren't actually
> currently in the table at all. You need to be able to detect a
> conflict between a transaction which read rows "WHERE i BETWEEN 1 AND
> 10" and one which tries to insert a row with i=1 even if the first
> transaction didn't see any rows with i=1 (or indeed even if the first
> transaction found no rows at all).

I absolutely agree to that. That's about predicate locks. I've been
talking about SIREAD, which is a different thing (and which I don't
consider to be a lock). The SIREAD thingie certainly doesn't help
implement predicate locks. And predicate locking isn't necessarily
sufficient to implement truly serializable isolation.

> That's the hard part. How do you represent such a lock in a way that I
> can efficiently find it and check for the conflict when it comes time
> for me to do my insert.

As it's not really a lock, but rather a mark or a tag, SIREAD may or may
not be implemented atop existing or non-existent locking structures, IMO.

I've made my points about implementing SIREAD atop table level or row
level locking structures. With (non-existent) predicate locking, I'm
still unsure. It might help to implement SIREAD atop such a predicate as
well. Predicate tagging?

Regards

Markus Wanner

Hi,

Kevin Grittner wrote:
> As I understand it, Greg's line of thinking is that we should use a
> technique which has never proven practical on a large scale:
> matching database changes against a list of predicate lock
> expressions.

I find that approach to predicate locking pretty interesting. However,
unlike others, it scales with the number of concurrently held locks. And
with the current trend towards multi-multi-core platforms, that might
get worse and worse (as concurrency must increase to efficiently use
these cores).

Regards

Markus Wanner

On Thursday, January 7, 2010, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Thu, Jan 7, 2010 at 2:40 PM, Greg Stark <gsstark(at)mit(dot)edu> wrote:
>> On Thu, Jan 7, 2010 at 11:08 AM, Markus Wanner <markus(at)bluegap(dot)ch> wrote:
>>> Row level locks are very fine grained, but those are spilled to disk in
>>> its current implementation. So those are an even worse fit for the needs
>>> of SIREAD.
>>
>> I think we're still talking past the issue. Predicate locks are not
>> row level, nor page level, nor table level.
>
> They're not?  They're just floating out in space somewhere?  There are
> several possible ways to implement predicate locks, but every possible
> method I can think of involves attaching them at one of those places.

well the one place you *cannot* attach them is on the tuples. because
you need to new able to lock hypothetical new tuples which don't exist
yet.

yes the implementation could work by attach them to tables or indexes
but it's representing an abstract concept which is just hanging out in
space.

>
>> And how do you do that without tying the implementation to specific
>> details of how our planner, table scans, and index access methods
>> work?
>
> You don't.  You add additional methods to the index AMs to support
> predicate locks, just lilke we do when we want them to support
> anything else (bitmap index scans, index-only scans, etc.).
>
> ...Robert
>

--
greg

On Fri, Jan 8, 2010 at 7:34 AM, Greg Stark <gsstark(at)mit(dot)edu> wrote:
> On Thursday, January 7, 2010, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> On Thu, Jan 7, 2010 at 2:40 PM, Greg Stark <gsstark(at)mit(dot)edu> wrote:
>>> On Thu, Jan 7, 2010 at 11:08 AM, Markus Wanner <markus(at)bluegap(dot)ch> wrote:
>>>> Row level locks are very fine grained, but those are spilled to disk in
>>>> its current implementation. So those are an even worse fit for the needs
>>>> of SIREAD.
>>>
>>> I think we're still talking past the issue. Predicate locks are not
>>> row level, nor page level, nor table level.
>>
>> They're not?  They're just floating out in space somewhere?  There are
>> several possible ways to implement predicate locks, but every possible
>> method I can think of involves attaching them at one of those places.
>
> well the one place you *cannot* attach them is on the tuples. because
> you need to new able to lock hypothetical new tuples which don't exist
> yet.

Well, index tuples maybe, for next-key locking...

> yes the implementation could work by attach them to tables or indexes
> but it's representing an abstract concept which is just hanging out in
> space.

Yeah, I understand that the concept is abstract, but I'm not sure it's
bad to be talking about other kinds of locks because that's how it
will be implemented. I think a lot of this is going to end up falling
on the index AMs - we could lock have locks on GIST pages, next-key
locks on btree tuples. We'll ask each index AM if it can help with the
predicate that we're trying to lock against and if they all say no
then we lock the whole table... or that's what I'm thinking, anyway.

...Robert

Markus Wanner <markus(at)bluegap(dot)ch> wrote:
> Greg Stark wrote:

> That's about predicate locks. I've been talking about SIREAD,
> which is a different thing (and which I don't consider to be a
> lock). The SIREAD thingie certainly doesn't help implement
> predicate locks. And predicate locking isn't necessarily
> sufficient to implement truly serializable isolation.

SIREAD locks need to be acquired according to the exact same rules
as "normal" read locks in predicate locking schemes. We're just
using a lock level where the set of locks which conflict with it is
empty. ;-) Predicate locking is clearly necessary and clearly not
sufficient to implement serializable isolation. Was some part of
the Cahill paper unclear on that?

>> That's the hard part. How do you represent such a lock in a way
>> that I can efficiently find it and check for the conflict when it
>> comes time for me to do my insert.
>
> As it's not really a lock, but rather a mark or a tag, SIREAD may
> or may not be implemented atop existing or non-existent locking
> structures, IMO.

Well, the development plan calls for it to start there. Whether a
better way is found during optimization is anybody's guess at this
point.

> I've made my points about implementing SIREAD atop table level or
> row level locking structures. With (non-existent) predicate
> locking, I'm still unsure. It might help to implement SIREAD atop
> such a predicate as well. Predicate tagging?

It seems both respectful and less confusing to adopt the terminology
of those who developed SSI techniques. I could invent new terms for
"vulnerable edges", "dangerous structures", "pivots" and such which
are used in the relevant literature. But I won't. It would just
serve to confuse those who have spent the time to read and
understand the literature.

I'm not quite sure I followed what you were getting at with the
"(non-existent) predicate locking" phrase -- was that just an
acknowledgment that it is exactly what is under development and, as
such, doesn't yet exist; or were you getting at something else?

-Kevin

Markus Wanner <markus(at)bluegap(dot)ch> wrote:
> Kevin Grittner wrote:
>> As I understand it, Greg's line of thinking is that we should use
>> a technique which has never proven practical on a large scale:
>> matching database changes against a list of predicate lock
>> expressions.
>
> I find that approach to predicate locking pretty interesting.

Sure, I find it interesting, too. Just not practical.

> unlike others, it scales with the number of concurrently held
> locks.

Times the number of checks for conflicting locks. So, O(N^2).
No thanks.

Now if there is a breakthrough in that technology which allows it to
compete favorably with techniques which model the logical predicates
against database structures, I'm all ears.

-Kevin

Greg Stark <gsstark(at)mit(dot)edu> wrote:

> well the one place you *cannot* attach them is on the tuples.

The predicate locking schemes I've been reading about do attach
locks to tuples, as *part* of a complete strategy.

> you need to new able to lock hypothetical new tuples which don't
> exist yet.

That, too. Which is where other granularities and objects come in,
as you later noted.

-Kevin

Hi,

Greg Stark wrote:
> well the one place you *cannot* attach them is on the tuples. because
> you need to new able to lock hypothetical new tuples which don't exist
> yet.

Well, maybe "attaching" here is meant in a more general or theoretical
sense. I think we all agree that adding them to the tuple header on disk
is not an option.

Regards

Markus Wanner

Hi,

Kevin Grittner wrote:
> SIREAD locks need to be acquired according to the exact same rules
> as "normal" read locks in predicate locking schemes.

Understood. I didn't take that into account at first. Thanks for
pointing it out. (Whatever "normal" read locks are...)

> We're just
> using a lock level where the set of locks which conflict with it is
> empty. ;-)

Which kind of defeats the purpose of a lock. Anyway, that's a bike-shed
discussion, so I might as well agree to calling it a lock.

> Well, the development plan calls for it to start there. Whether a
> better way is found during optimization is anybody's guess at this
> point.

Okay, so you know my guess ;-)

> It seems both respectful and less confusing to adopt the terminology
> of those who developed SSI techniques. I could invent new terms for
> "vulnerable edges", "dangerous structures", "pivots" and such which
> are used in the relevant literature. But I won't. It would just
> serve to confuse those who have spent the time to read and
> understand the literature.

I agree.

My intention was to "translate" the literature terms to Postgres hacker
slang. At least I had trouble to understand that SIREAD is a lock that
doesn't actually block anything.

> I'm not quite sure I followed what you were getting at with the
> "(non-existent) predicate locking" phrase -- was that just an
> acknowledgment that it is exactly what is under development and, as
> such, doesn't yet exist; or were you getting at something else?

SIREAD atop predicate locking serves detecting vulnerable edges (I hope
I'm using that term correctly here) between newly inserted tuples and
reads, right? I was trying to figure if it would make sense to use
predicate locking (instead of table or row level locking) as well for
detecting vulnerable edges between updated or deleted tuples and reads.

At least you'd be free with its granularity (which cannot be said for
row or table level locking, for obvious reasons). However, it certainly
depends a lot on the implementation of predicate locking, which we don't
have, yet, so that's all speculation...

Regards

Markus Wanner

2010/1/8 Markus Wanner <markus(at)bluegap(dot)ch>:

> SIREAD atop predicate locking serves detecting vulnerable edges (I hope
> I'm using that term correctly here) between newly inserted tuples and
> reads, right? I was trying to figure if it would make sense to use
> predicate locking (instead of table or row level locking) as well for
> detecting vulnerable edges between updated or deleted tuples and reads.

AFAICS, detecting a "rw" dependency where the read executes after the
write is rather easy: the writer has created a row version that is not
visible to the reader's snapshot. Therefore, any time a reader reads a
non-last version of a row, there is a rw dependency between it and the
creators of any newer versions.

Btw, rw dependencies are the only thing that needs to be checked under
SI, as "wr" and "ww" dependencies never lead to problems: one can only
see (or update) a certain row version using a transaction that has
taken its snapshot after the writing transaction already committed.
Therefore, the "must be before" relationship between such transactions
is trivially satisfied. (I assume here that PG's non-SI-compatible
behavior of not always rollbacking any transaction that writes to a
non-last version will be disabled in serializable mode.)

Nicolas

Nicolas Barbier <nicolas(dot)barbier(at)gmail(dot)com> wrote:

> AFAICS, detecting a "rw" dependency where the read executes after
> the write is rather easy: the writer has created a row version
> that is not visible to the reader's snapshot. Therefore, any time
> a reader reads a non-last version of a row, there is a rw
> dependency between it and the creators of any newer versions.

That *seems* safe on the face of it, but with HOT and such I wanted
to defer addressing that until I had the crude version working. I'm
probably being a bit paranoid, though. [thinks...] I should
probably try to satisfy myself that this is indeed safe before I
start populating the new locks. Basically, I have to confirm that
the read will see *all* new versions of a row without jumping out
early on any code path. If that pans out, it'll save some work;
it's not something which should wait until the optimization phase if
we can help it. Thanks.

> Btw, rw dependencies are the only thing that needs to be checked
> under SI, as "wr" and "ww" dependencies never lead to problems

Agreed; those are already covered by the underlying snapshot
isolation.

> I assume here that PG's non-SI-compatible behavior of not always
> rollbacking any transaction that writes to a non-last version will
> be disabled in serializable mode.

Can that currently happen in PostgreSQL's snapshot isolation?!? I
thought that was a READ COMMITTED issue. If I've missed something
there, I need to understand what. Anybody?

Thanks for your posts, by the way -- you clearly have a solid grasp
of the issues. I've been paying attention; I had just never felt
any of your posts needed any response from me before. :-)

-Kevin

Again, a somewhat tardy post from a question found in review.

Markus Wanner <markus(at)bluegap(dot)ch> wrote:

>> I suppose these more persistent write locks should
>> be kept out of the DEFAULT lock method, too....
>
> I fail to understand that part. What's the DEFAULT lock method?

With some adjustment of line wrapping for email...

>From src/include/storage/lock.h:

------------------------------------------------------------
/*
* Lock methods are identified by LOCKMETHODID. (Despite the
* declaration as uint16, we are constrained to 256 lockmethods by
* the layout of LOCKTAG.)
*/
typedef uint16 LOCKMETHODID;

/* These identify the known lock methods */
#define DEFAULT_LOCKMETHOD 1
#define USER_LOCKMETHOD 2
------------------------------------------------------------

>From the src/backend/storage/lmgr/README:

------------------------------------------------------------
Lock Data Structures
--------------------

Lock methods describe the overall locking behavior. Currently there
are two lock methods: DEFAULT and USER.

Lock modes describe the type of the lock (read/write or shared/
exclusive). In principle, each lock method can have its own set of
lock modes with different conflict rules, but currently DEFAULT and
USER methods use identical lock mode sets. See
src/tools/backend/index.html and src/include/storage/lock.h for more
details. (Lock modes are also called lock types in some places in
the code and documentation.)
------------------------------------------------------------

At least the initial implementation of the in-memory locks to
support detection of rw-dependencies will use the structures defined
in the lock.c file.

-Kevin

Hi,

Kevin Grittner wrote:
> Nicolas Barbier <nicolas(dot)barbier(at)gmail(dot)com> wrote:
>> AFAICS, detecting a "rw" dependency where the read executes after
>> the write is rather easy: the writer has created a row version
>> that is not visible to the reader's snapshot. Therefore, any time
>> a reader reads a non-last version of a row, there is a rw
>> dependency between it and the creators of any newer versions.

Sure.

As you have written below, we still need the SIREAD lock on the tuple
read to be able to detect rw dependencies (where the read executes
before the write).

I was trying to point out the difference between rw dependencies on
existing tuples (where the write is an update/delete) vs those on newly
created tuples (inserts) that *would* have been read. The later clearly
needs predicate locking. For the former, basing on table- as well as
row-level locking have been discussed so far.

What I'm thinking about is if it would make sense to use the very same
locking infrastructure for both, which needs to be some kind of
predicate locking. Maybe that was intended by Kevin and already clear to
others. It wasn't for me.

As we don't yet have predicate locking or tagging, let's check what SSI
needs from that building block. AFAICT we currently have the following
(long term) requirements:

A) reference rows that don't exist, yet
B) keep the lock (tag) until after the session that created it has
expired (yes, session, not only transaction).
C) fit in (shared) memory, no matter how many rows get tagged (thus
maybe use dynamical adjustment of granularity)

AFAICT using the existing locking structure will get complicated mainly
because of B), because we sometimes lack a PGPROC for the transaction
holding the lock. It's specific to SSI (not generally usable for
predicate locking).

A) and C) might be usable for a general purpose predicate locking
mechanism as well, but those requirements make it hard to map the object
to be locked to a LOCKTAG.

Unlike a general purpose predicate locking implementation, we don't need
to block on SIREAD locks, so we don't need waiting queues nor deadlock
detection for SSI.

> Basically, I have to confirm that
> the read will see *all* new versions of a row without jumping out
> early on any code path.

Well, a heap scan immediately returns the currently visible version of a
row to the caller, for example. That one may or may not continue the
scan. So I fear yes, current code paths jump out early very often (as
that's an optimization for the LIMIT case as well).

>> I assume here that PG's non-SI-compatible behavior of not always
>> rollbacking any transaction that writes to a non-last version will
>> be disabled in serializable mode.
>
> Can that currently happen in PostgreSQL's snapshot isolation?!? I
> thought that was a READ COMMITTED issue. If I've missed something
> there, I need to understand what. Anybody?

A write to a non-last (or non-head) version would lead to having
multiple "last" (or rather multiple head) versions, which is not
something that's ever supposed to happen in Postgres, IIRC.

Regards

Markus Wanner

2010/1/8 Kevin Grittner <Kevin(dot)Grittner(at)wicourts(dot)gov>:

> Nicolas Barbier <nicolas(dot)barbier(at)gmail(dot)com> wrote:
>
>> I assume here that PG's non-SI-compatible behavior of not always
>> rollbacking any transaction that writes to a non-last version will
>> be disabled in serializable mode.
>
> Can that currently happen in PostgreSQL's snapshot isolation?!?  I
> thought that was a READ COMMITTED issue.  If I've missed something
> there, I need to understand what.  Anybody?

Ah woops, you are right. The manual says in [1]:

---- >8 ----
13.2.2. Serializable Isolation Level

[..]

UPDATE, DELETE, SELECT FOR UPDATE, and SELECT FOR SHARE commands
behave the same as SELECT in terms of searching for target rows: they
will only find target rows that were committed as of the transaction
start time. However, such a target row might have already been updated
(or deleted or locked) by another concurrent transaction by the time
it is found. In this case, the serializable transaction will wait for
the first updating transaction to commit or roll back (if it is still
in progress). If the first updater rolls back, then its effects are
negated and the serializable transaction can proceed with updating the
originally found row. But if the first updater commits (and actually
updated or deleted the row, not just locked it) then the serializable
transaction will be rolled back with the message

ERROR: could not serialize access due to concurrent update
because a serializable transaction cannot modify or lock rows changed
by other transactions after the serializable transaction began.
---- 8< ----

Sorry for the noise,

Nicolas

[1] <URL:http://www.postgresql.org/docs/8.4/static/transaction-iso.html#XACT-SERIALIZABLE>