Thread

1. SKIP LOCKED DATA

   Thomas Munro <munro@ip9.org> — 2012-01-15T23:01:44Z

   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
   
   

2. Re: SKIP LOCKED DATA

   Tom Lane <tgl@sss.pgh.pa.us> — 2012-01-16T05:33:29Z

   Thomas Munro <munro@ip9.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
   
   

3. Re: SKIP LOCKED DATA

   Ilya Kosmodemiansky <hydrobiont@gmail.com> — 2012-01-16T08:06:21Z

   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@sss.pgh.pa.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@postgresql.org)
   > To make changes to your subscription:
   > http://www.postgresql.org/mailpref/pgsql-hackers
   
   

4. Re: SKIP LOCKED DATA

   Simon Riggs <simon@2ndquadrant.com> — 2012-01-16T08:51:45Z

   On Mon, Jan 16, 2012 at 5:33 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
   > Thomas Munro <munro@ip9.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
   
   

5. Re: SKIP LOCKED DATA

   Dimitri Fontaine <dimitri@2ndquadrant.fr> — 2012-01-16T20:43:02Z

   Thomas Munro <munro@ip9.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
   
   

6. Re: SKIP LOCKED DATA

   Josh Berkus <josh@agliodbs.com> — 2012-01-16T21:30:51Z

   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
   
   

7. Re: SKIP LOCKED DATA

   Thomas Munro <munro@ip9.org> — 2012-01-17T21:55:30Z

   On 16 January 2012 08:06, Ilya Kosmodemiansky <hydrobiont@gmail.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.
   
   

8. Re: SKIP LOCKED DATA

   Thomas Munro <munro@ip9.org> — 2012-02-04T11:38:56Z

   On 16 January 2012 21:30, Josh Berkus <josh@agliodbs.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
   

9. Re: SKIP LOCKED DATA

   Merlin Moncure <mmoncure@gmail.com> — 2012-02-06T18:03:36Z

   On Sat, Feb 4, 2012 at 5:38 AM, Thomas Munro <munro@ip9.org> wrote:
   > On 16 January 2012 21:30, Josh Berkus <josh@agliodbs.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