Thread: 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@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
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
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
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
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@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.
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
Attachment
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