Re: SKIP LOCKED DATA

Hi

Apologies for posting about new vapourware features for distant
future releases at a very busy time in the cycle for 9.2...

I am wondering out loud whether I am brave enough to try to propose
SKIP LOCKED DATA support and would be grateful for any feedback and/or
{en|dis}couragement. I don't see it on the todo list, and didn't find
signs of others working on this (did I miss something?), but there are
examples of users asking for this feature (by various names) on the
mailing lists. Has the idea already been rejected, is it
fundamentally infeasible for some glaring reason, or far too
complicated for new players?

What it is:

Like the existing NOWAIT option, it means your query doesn't wait for
others sessions when trying to get an exclusive lock. However, rather
than returning an error if it would block, it simply skips over the
rows that couldn't be locked.

What it looks like in other RDBMSs:

DB2 (z/OS only): FOR UPDATE SKIP LOCKED DATA
Oracle: FOR UPDATE SKIP LOCKED
Sybase: FOR UPDATE READPAST
MS SQL Server: FOR UPDATE WITH (READPAST)

(I'm not 100% sure about the last two, which I found by googling for
equivalents of the first two, and there are no doubt subtle differences
among these).

What it's for:

A common usage for this is to increase parallelism in systems with
multiple workers taking jobs from a queue. I've used it for this
purpose myself on another RDBMS, having seen it recommended for some
types of work queue implementation. It may have other uses.

How it might be implemented in PostgreSQL:

1. Extend the grammar and parser to support SKIP LOCKED DATA (or some
other choice of words) in the same place that NOWAIT can appear.

2. Modify heap_lock_tuple so that the boolean 'nowait' argument is
replaced by an enumeration LockWaitPolicy with values
LOCK_WAIT_POLICY_WAIT (= what false currently does),
LOCK_WAIT_POLICY_LOCK_OR_ERROR (= what true currently does),
LOCK_WAIT_POLICY_LOCK_OR_SKIP (= new behaviour). Where currently
'nowait' is handled, the new case would also be handled, cleaning up
resources and returning a new HTSU_Result enumerator
HeapTupleWouldBlock.

3. Modify ExecLockRows to pass the appropriate value to
heap_lock_tuple (presumably received via ExecRowMark, as nowait is
received currently). Modify the switch on the result of that call,
treating the new case HeapTupleWouldBlock the same way that
HeapTupleSelfUpdated is treated -- that is, goto lnext to fetch the
next tuple.

4. Probably some changes to handle table-level locks too.

5. Probably many other things that I'm not aware of right now and
won't discover until I dig/ask further and/or run into a brick wall!

Useful? Doable?

Thanks,

Thomas Munro

Thomas Munro <munro(at)ip9(dot)org> writes:
> I am wondering out loud whether I am brave enough to try to propose
> SKIP LOCKED DATA support and would be grateful for any feedback and/or
> {en|dis}couragement. I don't see it on the todo list, and didn't find
> signs of others working on this (did I miss something?), but there are
> examples of users asking for this feature (by various names) on the
> mailing lists. Has the idea already been rejected, is it
> fundamentally infeasible for some glaring reason, or far too
> complicated for new players?

It sounds to me like "silently give the wrong answers". Are you sure
there are not better, more deterministic ways to solve your problem?

(Or in other words: the fact that Oracle has it isn't enough to persuade
me it's a good idea.)

regards, tom lane

That is quite useful feature to implement smth. like message queues
based on database and so on.
Now there is possibility to jump over luck of such feature in Postgres
using current advisory lock implementation (pg_try_advisory_xact_lock
to determine if somebody already acquired log on particular row).
So Im not sure this is an urgent matter.

Best regards,
Ilya

On Mon, Jan 16, 2012 at 6:33 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> It sounds to me like "silently give the wrong answers".  Are you sure
> there are not better, more deterministic ways to solve your problem?
>
> (Or in other words: the fact that Oracle has it isn't enough to persuade
> me it's a good idea.)
>
>                        regards, tom lane
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers

On Mon, Jan 16, 2012 at 5:33 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Thomas Munro <munro(at)ip9(dot)org> writes:
>> I am wondering out loud whether I am brave enough to try to propose
>> SKIP LOCKED DATA support and would be grateful for any feedback and/or
>> {en|dis}couragement.  I don't see it on the todo list, and didn't find
>> signs of others working on this (did I miss something?), but there are
>> examples of users asking for this feature (by various names) on the
>> mailing lists.  Has the idea already been rejected, is it
>> fundamentally infeasible for some glaring reason, or far too
>> complicated for new players?
>
> It sounds to me like "silently give the wrong answers".  Are you sure
> there are not better, more deterministic ways to solve your problem?

The name is misleading.

It means "open a cursor on a query, when you fetch if you see a locked
row return quickly from the fetch".

The idea is that if its locked it is still being written and therefore
not interesting (yet).

Sounds reasonable request.

--
 Simon Riggs                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

Thomas Munro <munro(at)ip9(dot)org> writes:
> A common usage for this is to increase parallelism in systems with
> multiple workers taking jobs from a queue. I've used it for this
> purpose myself on another RDBMS, having seen it recommended for some
> types of work queue implementation. It may have other uses.

To attack this problem in PostgreSQL we also have PGQ, which is
Skytools3 has support for cooperative consumers.

Regards,
--
Dimitri Fontaine
http://2ndQuadrant.fr PostgreSQL : Expertise, Formation et Support

On 1/15/12 3:01 PM, Thomas Munro wrote:
> 5. Probably many other things that I'm not aware of right now and
> won't discover until I dig/ask further and/or run into a brick wall!
>
> Useful? Doable?

Useful, yes. Harder than it looks, probably. I tried to mock up a
version of this years ago for a project where I needed it, and ran into
all kinds of race conditions.

Anyway, if it could be made to work, this is extremely useful for any
application which needs queueing behavior (with is a large plurality, if
not a majority, of applications).

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On 16 January 2012 08:06, Ilya Kosmodemiansky <hydrobiont(at)gmail(dot)com> wrote:
> That is quite useful feature to implement smth. like message queues
> based on database and so on.
> Now there is possibility to jump over luck of such feature in Postgres
> using current advisory lock implementation (pg_try_advisory_xact_lock
> to determine if somebody already acquired log on particular row).
> So Im not sure this is an urgent matter.

Thanks Ilya. I knew about advisory locks but hadn't though of using
them like this. I tried some simple examples using SELECT ... FROM
... WHERE pg_try_advisory_xact_lock(id) [FOR UPDATE] LIMIT 1 in
transactions from a couple of different sessions and it achieves the
right effect. I could imagine that in theory there might be order of
evaluation subtleties in some cases where you have more things in your
WHERE clause though. I guess you want the pg_try_advisory_xact_lock
to be tested last after all other conditions are satisfied (ie for
minimal lock contention, avoiding false positives).

So I guess the question is whether it's worth implementing an explicit
feature to match other RDMBSs, complement NOWAIT and avoid theoretical
order of evaluation problems, or if this technique is enough.

On 16 January 2012 21:30, Josh Berkus <josh(at)agliodbs(dot)com> wrote:

> Useful, yes.  Harder than it looks, probably.  I tried to mock up a
> version of this years ago for a project where I needed it, and ran into
> all kinds of race conditions.

Can you remember any details about those race conditions?

> Anyway, if it could be made to work, this is extremely useful for any
> application which needs queueing behavior (with is a large plurality, if
> not a majority, of applications).

Ok, based on this feedback I decided to push further and try
implementating this. See POC/WIP patch attached. It seems to work
for simple examples but I haven't yet tried to break it or see how it
interacts with more complicated queries or high concurrency levels.
It probably contains at least a few rookie mistakes! Any feedback
gratefully received.

The approach is described in my original email. Short version:
heap_lock_tuple now takes an enum called wait_policy instead of a
boolean called nowait, with the following values:

LockWaitBlock: wait for lock (like nowait = false before),

LockWaitError: error if not immediately lockable (like nowait = true
before)

LockWaitSkip: give up and return HeapTupleWouldBlock if not
immediately lockable (this is a new policy)

The rest of the patch is about getting the appropriate value down to
that function call, following the example of the existing nowait
support, and skipping rows if you said SKIP LOCKED DATA and you got
HeapTupleWouldBlock.

Compared to one very popular commercial database's implementation, I
think this is a little bit friendlier for the user who wants to
distribute work. Let's say you want to lock one row without lock
contention, which this patch allows with FETCH FIRST 1 ROW ONLY FOR
UPDATE SKIP LOCKED DATA in an SQL query. In that other system, the
mechanism for limiting the number of rows fetched is done in the WHERE
clause, and therefore the N rows are counted *before* checking if the
lock can be obtained, so users sometimes have to resort to stored
procedures so they can control the FETCH from a cursor imperatively.
In another popular commercial database from Redmond, you can ask for
the top (first) N rows while using the equivalent of SKIP LOCKED DATA
and it has the same effect as this patch as far as I can tell, and
another large blue system is the same.

As discussed in another branch of this thread, you can probably get
the same effect with transactional advisory locks. But I personally
like row skipping better as an explicit feature because:

(1) I think there might be an order-of-evaluation problem with a WHERE
clause containing both lock testing and row filtering expressions (ie
it is undefined right?) which you might need subselects to work around
(ie to be sure to avoid false positive locks, not sure about this).

(2) The advisory technique requires you to introduce an integer
identifier if you didn't already have one and then lock that despite
having already said which rows you want to try to lock in standard row
filtering expressions.

(3) The advisory technique requires all users of the table to
participate in the advisory lock protocol even if they don't want to
use the option to skip lock.

(4) It complements NOWAIT (which could also have been done with
transactional advisory locks, with a function like try_lock_or_fail).

(5) I like the idea of directly porting applications from other
databases with this feature (that is what led me here).

I can also imagine some other arguments against SKIP LOCKED DATA: "the
type of applications that would use this technique generate too much
dead tuple churn for PostgreSQL anyway" (for example, compared to the
update-tuples-in-place systems like DB2 z/OS edition where SKIP LOCKED
DATA is used to distribute work efficiently), and "databases shouldn't
be used as queues anyway, for that we have $X", and "skipping rows
provides an inconsistent view of the data" (ie a result set that never
strictly existed).

Here are some examples of previous requests or discussion of this
feature:

http://archives.postgresql.org/pgsql-general/2008-07/msg00442.php
http://archives.postgresql.org/pgsql-bugs/2003-12/msg00154.php
http://archives.postgresql.org/pgsql-general/2002-07/msg00744.php
http://blog.hydrobiont.com/2011/06/select-for-update-skip-locked-in.html

Thanks for reading!

Thomas

On Sat, Feb 4, 2012 at 5:38 AM, Thomas Munro <munro(at)ip9(dot)org> wrote:
> On 16 January 2012 21:30, Josh Berkus <josh(at)agliodbs(dot)com> wrote:
>
>> Useful, yes.  Harder than it looks, probably.  I tried to mock up a
>> version of this years ago for a project where I needed it, and ran into
>> all kinds of race conditions.
>
> Can you remember any details about those race conditions?
>
>> Anyway, if it could be made to work, this is extremely useful for any
>> application which needs queueing behavior (with is a large plurality, if
>> not a majority, of applications).
>
> Ok, based on this feedback I decided to push further and try
> implementating this.  See POC/WIP patch attached.  It seems to work
> for simple examples but I haven't yet tried to break it or see how it
> interacts with more complicated queries or high concurrency levels.
> It probably contains at least a few rookie mistakes!  Any feedback
> gratefully received.
>
> The approach is described in my original email.  Short version:
> heap_lock_tuple now takes an enum called wait_policy instead of a
> boolean called nowait, with the following values:
>
>  LockWaitBlock: wait for lock (like nowait = false before),
>
>  LockWaitError: error if not immediately lockable (like nowait = true
>                 before)
>
>  LockWaitSkip:  give up and return HeapTupleWouldBlock if not
>                 immediately lockable (this is a new policy)
>
> The rest of the patch is about getting the appropriate value down to
> that function call, following the example of the existing nowait
> support, and skipping rows if you said SKIP LOCKED DATA and you got
> HeapTupleWouldBlock.
>
> Compared to one very popular commercial database's implementation, I
> think this is a little bit friendlier for the user who wants to
> distribute work.  Let's say you want to lock one row without lock
> contention, which this patch allows with FETCH FIRST 1 ROW ONLY FOR
> UPDATE SKIP LOCKED DATA in an SQL query.  In that other system, the
> mechanism for limiting the number of rows fetched is done in the WHERE
> clause, and therefore the N rows are counted *before* checking if the
> lock can be obtained, so users sometimes have to resort to stored
> procedures so they can control the FETCH from a cursor imperatively.
> In another popular commercial database from Redmond, you can ask for
> the top (first) N rows while using the equivalent of SKIP LOCKED DATA
> and it has the same effect as this patch as far as I can tell, and
> another large blue system is the same.
>
> As discussed in another branch of this thread, you can probably get
> the same effect with transactional advisory locks.  But I personally
> like row skipping better as an explicit feature because:
>
> (1) I think there might be an order-of-evaluation problem with a WHERE
> clause containing both lock testing and row filtering expressions (ie
> it is undefined right?) which you might need subselects to work around
> (ie to be sure to avoid false positive locks, not sure about this).
>
> (2) The advisory technique requires you to introduce an integer
> identifier if you didn't already have one and then lock that despite
> having already said which rows you want to try to lock in standard row
> filtering expressions.
>
> (3) The advisory technique requires all users of the table to
> participate in the advisory lock protocol even if they don't want to
> use the option to skip lock.
>
> (4) It complements NOWAIT (which could also have been done with
> transactional advisory locks, with a function like try_lock_or_fail).
>
> (5) I like the idea of directly porting applications from other
> databases with this feature (that is what led me here).

Yeah -- also your stuff is also going to have much better interactions
with LIMIT. Your enhancements will beat an advisory lock
implementation all day long. the real competition is not advisory
locks, but the mvcc tricks played with PGQ. It's all about
implementing producer consumer queues (arguments that databases should
not do that are 100% bogus) and I can't help but wonder if that's a
better system.

merlin