Thread: Concurrent MERGE
Looks like MERGE is progressing well. At 2010 Dev Mtg, we put me down to work on making merge work concurrently. That was garbled slightly and had me down as working on predicate locking which is the general solution to the problem. Do we still need me to work on concurrent MERGE, or is that included in the current MERGE patch (can't see it), or is that covered elsewhere (for example Kevin Grittner's recent work)? Still happy to do work as proposed, just checking still required. Thanks, -- Simon Riggs www.2ndQuadrant.comPostgreSQL Development, 24x7 Support, Training and Services
On Thu, Aug 5, 2010 at 11:43 AM, Simon Riggs <simon@2ndquadrant.com> wrote: > Looks like MERGE is progressing well. > > At 2010 Dev Mtg, we put me down to work on making merge work > concurrently. That was garbled slightly and had me down as working on > predicate locking which is the general solution to the problem. > > Do we still need me to work on concurrent MERGE, or is that included in > the current MERGE patch (can't see it), or is that covered elsewhere > (for example Kevin Grittner's recent work)? > > Still happy to do work as proposed, just checking still required. I suspect Kevin's patch will solve it if using a sufficiently high transaction isolation level, but something else might be needed otherwise. However, I confess to ignorance as to the underlying issues? Why is MERGE worse in this regard than, say, UPDATE? -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise Postgres Company
On 05/08/10 18:43, Simon Riggs wrote: > Do we still need me to work on concurrent MERGE, or is that included in > the current MERGE patch (can't see it), or ... It's not in the current MERGE patch. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com
On 05/08/10 18:57, Robert Haas wrote: > On Thu, Aug 5, 2010 at 11:43 AM, Simon Riggs<simon@2ndquadrant.com> wrote: >> Looks like MERGE is progressing well. >> >> At 2010 Dev Mtg, we put me down to work on making merge work >> concurrently. That was garbled slightly and had me down as working on >> predicate locking which is the general solution to the problem. >> >> Do we still need me to work on concurrent MERGE, or is that included in >> the current MERGE patch (can't see it), or is that covered elsewhere >> (for example Kevin Grittner's recent work)? >> >> Still happy to do work as proposed, just checking still required. > > I suspect Kevin's patch will solve it if using a sufficiently high > transaction isolation level, but something else might be needed > otherwise. With truly serializable isolation I think you'll get a serialization failure error. > However, I confess to ignorance as to the underlying > issues? Why is MERGE worse in this regard than, say, UPDATE? MERGE can be used to implement "upsert", where a row is updated if it exists and inserted if it doesn't. I don't think Kevin's patch will suffice for that. You don't usually want a serialization failure error when you run two upserts at the same time, you want both of them to succeed, one doing an insert and the other one doing an update. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com
Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> wrote: >> However, I confess to ignorance as to the underlying >> issues? Why is MERGE worse in this regard than, say, UPDATE? > > MERGE can be used to implement "upsert", where a row is updated if > it exists and inserted if it doesn't. I don't think Kevin's patch > will suffice for that. You don't usually want a serialization > failure error when you run two upserts at the same time, you want > both of them to succeed, one doing an insert and the other one > doing an update. The patch Dan and I are working on won't block anything that snapshot isolation doesn't already block, so if the behavior you want is that one is held up until the other is done with something, it's not going to help. What it would do is detect whether two concurrent upserts are behaving in a way that is consistent with some serial execution of the two upserts; it would do nothing if there was a consistent interpretation, but roll one back if each appeared to come before the other in some respect. All of that, of course, with the usual caveats that it would have *no* impact unless both were run at the SERIALIZABLE isolation level, there could be false positives, and the MERGE code might possibly need to add a few calls to the functions added in the serializable patch. I hope that clarified rather than muddied the waters.... -Kevin
robertmhaas@gmail.com (Robert Haas) writes: > On Thu, Aug 5, 2010 at 11:43 AM, Simon Riggs <simon@2ndquadrant.com> wrote: >> Looks like MERGE is progressing well. >> >> At 2010 Dev Mtg, we put me down to work on making merge work >> concurrently. That was garbled slightly and had me down as working on >> predicate locking which is the general solution to the problem. >> >> Do we still need me to work on concurrent MERGE, or is that included in >> the current MERGE patch (can't see it), or is that covered elsewhere >> (for example Kevin Grittner's recent work)? >> >> Still happy to do work as proposed, just checking still required. > > I suspect Kevin's patch will solve it if using a sufficiently high > transaction isolation level, but something else might be needed > otherwise. However, I confess to ignorance as to the underlying > issues? Why is MERGE worse in this regard than, say, UPDATE? It's worse than UPDATE because- It could be an INSERT, if the data's new, but- If the data's there, it becomes an UPDATE,but- If some concurrent update has just DELETEd the data that's there, it becomes an INSERT again, but- Oops, thatDELETE rolled bac, so it's an UPDATE again... Recurse as needed to make it more undecidable as to whether it's really an INSERT or an UPDATE :-). -- Rules of the Evil Overlord #208. "Members of my Legion of Terror will attend seminars on Sensitivity Training. It's good public relations for them to be kind and courteous to the general population when not actively engaged in sowing chaos and destruction."
Chris Browne <cbbrowne@acm.org> wrote: > robertmhaas@gmail.com (Robert Haas) writes: >> I suspect Kevin's patch will solve it if using a sufficiently >> high transaction isolation level, but something else might be >> needed otherwise. However, I confess to ignorance as to the >> underlying issues? Why is MERGE worse in this regard than, say, >> UPDATE? > > It's worse than UPDATE because > - It could be an INSERT, if the data's new, but > - If the data's there, it becomes an UPDATE, but > - If some concurrent update has just DELETEd the data that's > there, it becomes an INSERT again, but > - Oops, that DELETE rolled bac, so it's an UPDATE again... > > Recurse as needed to make it more undecidable as to whether it's > really an INSERT or an UPDATE :-). Not to get too far into the serializable issues, but the server won't do any such recursion with the serializable patch. Each serializable transaction would have its own snapshot where the row was there or it wasn't, and would act accordingly. If they took conflicting actions on the same row, one of them might be rolled back with a serialization failure. The client is likely to want to retry the operation based on the SQLSTATE indicating serialization failure, which (as the patch stands now) could result in some head-banging if the client doesn't introduce some delay first. I have an optimization in mind (described on the Wiki page) which could help with that, but its impact on overall performance is uncertain, so I don't want to mess with that until we have more benchmarks in place for realistic loads which might use serializable isolation. So... No, it's not directly a problem on the server itself. Yes, a client can make it a problem by resubmitting failed queries "too quickly". But, we might be able to fix that with additional work. -Kevin
> At 2010 Dev Mtg, we put me down to work on making merge work
> concurrently. That was garbled slightly and had me down as working on
> predicate locking which is the general solution to the problem.
Well, we *still* want predicate locking regardless of what MERGE
supports. It's useful in about 9 different ways.
-- -- Josh Berkus PostgreSQL Experts Inc.
http://www.pgexperts.com
I wrote: > So... No, it's not directly a problem on the server itself. I just had a thought -- the MERGE code isn't doing anything fancy with snapshots, is it? I haven't been tracking that discussion too closely or read the patch. My previous comments assume that the *snapshot* is stable for the duration of a MERGE command, at least if the transaction isolation level is serializable. -Kevin
Josh Berkus <josh@agliodbs.com> wrote: > Well, we *still* want predicate locking regardless of what MERGE > supports. It's useful in about 9 different ways. I don't know whether this is the right time to discuss those 9 different uses, but just so everyone knows, the SIRead locks needed for the SSI implementation in the current serializable patch have some characteristics which may be exactly what you want (if you want cache invalidation or some such) or may render them totally useless from some purposes. (1) They don't block anything. Ever. Conflicts with writes are detected, and right now that is used to mark rw-conflicts between serializable transactions. I assume we may want to add listeners who can be signaled on such conflicts, too; but that isn't there now. (2) They are only acquired by serializable transactions. (3) They can survive the transaction which acquired them, and even the termination of the process which ran the transaction. Right now they go away when the last serializable transaction which overlapped the acquiring serializable transaction completes. If we add listeners, I assume we'd want to keep them as long as a listener was registered, probably with some timeout feature. Just so everyone knows what is and isn't there right now. -Kevin
On 8/5/10 12:33 PM, Kevin Grittner wrote:
> I don't know whether this is the right time to discuss those 9
> different uses, but just so everyone knows, the SIRead locks needed
> for the SSI implementation in the current serializable patch have
> some characteristics which may be exactly what you want (if you want
> cache invalidation or some such) or may render them totally useless
> from some purposes.
Yeah, I haven't wrapped my head around your stuff enough yet. I would
say that having such locks available only for serializable transactions
limits some of the uses I'm thinking of.
Anyway, here's some of the uses I'm thinking of:
(1) Pre-insert lock: you know that you're going to insert a record with
PK="X" later in a long-running SP, so you want to lock out other inserts
of PK="X" at the beginning of the procedure.
(2) FK Locking: you plan to modify or delete a parent FK record in this
transaction, so you want to prevent any updates or inserts on its
related child records. (in my experience, FK-releated sharelocks are the
#1 cause of deadlocking).
(3) No-duplicate queueing: you want to create a queue table which
doesn't accept duplicate events, but you don't want it to be a source of
deadlocks. This is a variant of (1), but a common case.
(4) Blackouts: records of type "x" aren't supposed to be created during
period "y to y1" or while procedure "z" is running. Predicate locking
can be used to prevent this more easily than adding and removing a trigger.
(5) Debugging: (variant of 4) records of type "x" keep getting inserted
in the table, and you don't know where they're coming from. You can
predicate lock to force an error and debug it.
... that's off the top of my head.
-- -- Josh Berkus PostgreSQL Experts Inc.
http://www.pgexperts.com
Josh Berkus <josh@agliodbs.com> wrote: > Anyway, here's some of the uses I'm thinking of: > > (1) Pre-insert lock: you know that you're going to insert a record > with PK="X" later in a long-running SP, so you want to lock out > other inserts of PK="X" at the beginning of the procedure. Well, if we added a listener, you could SELECT the desired key, and be notified of a conflicting insert, but that's not really what you're looking for. It does seem to me that you could solve this one by inserting the tuple and then updating it at the end, but I suppose you're looking to avoid the resulting dead tuple. Perhaps a listener could be fed to a "cancel the conflicting query" routine? In any event, the only resolution to such a conflict is to kill something, right? And right now, a write/write conflict would occur which would resolve it, you just want to be able to "reserve" the slot up front, so your transaction isn't canceled after doing a bunch of work, right? > (2) FK Locking: you plan to modify or delete a parent FK record in > this transaction, so you want to prevent any updates or inserts on > its related child records. (in my experience, FK-releated > sharelocks are the #1 cause of deadlocking). I don't see how that can be resolved without killing something, do you? You would just have to replace the current deadlock with some other form of serialization failure. (And no, I will never give up the position that a deadlock *is* one of many forms of serialization failure.) > (3) No-duplicate queueing: you want to create a queue table which > doesn't accept duplicate events, but you don't want it to be a > source of deadlocks. This is a variant of (1), but a common case. I must be missing something. Please explain how this would work *without* serialization failures. As far as I can see, you can replace deadlocks with some other form, but I don't see the point. Basically, I think we should change the deadlock SQLSTATE to '40001' and any code which needs to deal with such things treats that SQLSTATE as meaning "that wasn't a good time to try that transaction, try again in a bit." Or, if you just want it to do nothing if the row already exists, perhaps the new MERGE code would work? > (4) Blackouts: records of type "x" aren't supposed to be created > during period "y to y1" or while procedure "z" is running. > Predicate locking can be used to prevent this more easily than > adding and removing a trigger. I would have thought that advisory locks covered this. In what way do they fall short for this use case? > (5) Debugging: (variant of 4) records of type "x" keep getting > inserted in the table, and you don't know where they're coming > from. You can predicate lock to force an error and debug it. Hmmmm.... Assuming fine enough granularity (like from an index for which a range could be locked to detect the conflict) adding a listener to the SIRead lock handling would be good for this. Well, as long as the transactions were serializable. -Kevin
Kevin,
Overall, you're missing the point: there are workarounds for all of
these things now. However, they are *workarounds*, which means that
they are awkward, expensive, and/or hard to administrate; having
predicate locks would make things much easier.
> I don't see how that can be resolved without killing something, do
> you? You would just have to replace the current deadlock with some
> other form of serialization failure. (And no, I will never give up
> the position that a deadlock *is* one of many forms of serialization
> failure.)
If you're in lock nowait mode, you could get back a "can't lock" error
message immediately rather than waiting for the procedure to time out.
There's certainly going to be an error regardless; it's a question of
how expensive it is for the application and the database server.
Deadlocks are *very* expensive, especially since our deadlock detector
doesn't always figure them out successfully (which means the deadlock
has to be resolved by the DBA). So any other type of serialization
failure or error is better than deadlocking.
> I must be missing something. Please explain how this would work
> *without* serialization failures. As far as I can see, you can
> replace deadlocks with some other form, but I don't see the point.
See above.
>> (4) Blackouts: records of type "x" aren't supposed to be created
>> during period "y to y1" or while procedure "z" is running.
>> Predicate locking can be used to prevent this more easily than
>> adding and removing a trigger.
>
> I would have thought that advisory locks covered this. In what way
> do they fall short for this use case?
Currently, I do use advisory locks for this case. However, they require
a fair amount of administrative design and monitoring overhead.
> Hmmmm.... Assuming fine enough granularity (like from an index for
> which a range could be locked to detect the conflict) adding a
> listener to the SIRead lock handling would be good for this. Well,
> as long as the transactions were serializable.
Yeah, it's that last caveat which makes SIRead locks not as flexible as
the theoretical predicate lock. Of course, any eventual actual
implemenation of predicate locks might be equally inflexible.
-- -- Josh Berkus PostgreSQL Experts Inc.
http://www.pgexperts.com
Josh Berkus <josh@agliodbs.com> wrote: > Overall, you're missing the point: there are workarounds for all > of these things now. However, they are *workarounds*, which means > that they are awkward, expensive, and/or hard to administrate; > having predicate locks would make things much easier. Well, if some form of the SSI patch goes in most of your use cases can be solved just by making the transactions serializable and letting the chips fall where they may. That's the whole point of it. I'll say it again: with true serializable transactions, if you can show that your transaction will do the right thing if there are no concurrent transactions, it will do the right thing in any mix of serializable transactions or be rolled back with a serialization failure. Full stop. No need to explicitly lock anything (with or without NOWAIT), no need to SELECT FOR UPDATE/SHARE, no need to "reserve" anything -- I consider all of those to be awkward workarounds. You just systematically retry transactions which fail with SQLSTATE '40001'. If your software isn't set up so that this can be done once, in one place, you need to rethink your design. I'm not at all clear how any form of predicate locking can help with the "blackouts" example. Perhaps if you explained how you see that working I might get it. Oh, and if deadlocks are that broken, it's a bit scary that we have let that go. Is it the problem that technically intractable? -Kevin
On 8/5/10 1:59 PM, Kevin Grittner wrote:
> Oh, and if deadlocks are that broken, it's a bit scary that we have
> let that go. Is it the problem that technically intractable?
Yes; it's a major project. Our detector works pretty well for deadlocks
which are 2-process locks or even several processes all locking against
the same first process. However, triangular and quadralateral deadlocks
(which I've seen more than once) it completely cannot handle, and some
types of activity which can cause deadlocks (like autovacuum or DDL
activity) also seem to be outside its purview. The latter is probably
fixable if I can create some good test cases.
However, the "circular" deadlock problem has an n! issue with detecting it.
Also, even where the deadlock detector does its job, it's still the most
expensive type of serialization failure:
1. the detector will wait at least 1 second to check, so we're usually
looking at a couple seconds to resolve the deadlock;
2. since deadlocks don't happen in testing, most applicaiton error
handling isn't set up for them;
3. deadlocks can, and do, result in cancelling several transactions
instead of just one; there is no "winner" which is allowed to complete.
-- -- Josh Berkus PostgreSQL Experts Inc.
http://www.pgexperts.com
Josh Berkus <josh@agliodbs.com> writes:
> Yes; it's a major project. Our detector works pretty well for deadlocks
> which are 2-process locks or even several processes all locking against
> the same first process. However, triangular and quadralateral deadlocks
> (which I've seen more than once) it completely cannot handle,
Hm? Please explain what you're talking about.
> and some
> types of activity which can cause deadlocks (like autovacuum or DDL
> activity) also seem to be outside its purview.
There's some known issues with deadlocks involving LWLocks as well as
regular locks, which I agree aren't fixable without some significant
rework. But I don't believe there's anything fundamentally wrong with
the deadlock detector --- the real problem there is stretching LWLocks
beyond their design intention, namely to be used only for situations
where deadlock is impossible.
> Also, even where the deadlock detector does its job, it's still the most
> expensive type of serialization failure:
Well, that's certainly true --- you don't want deadlock recovery to be
part of any high-performance path.
> 3. deadlocks can, and do, result in cancelling several transactions
> instead of just one; there is no "winner" which is allowed to complete.
Not sure I believe this either; one deadlock kills one transaction.
If you lose multiple transactions I think you had multiple deadlocks.
regards, tom lane
> Hm? Please explain what you're talking about.
Transaction A locks 1 and wants a lock on 2
Transaction B locks 2 and wants a lock on 3
Transaction C locks 3 and wants a lock on 1
I've never had the deadlock detector successfully deal with the above.
Let alone a 4-way.
> Not sure I believe this either; one deadlock kills one transaction.
> If you lose multiple transactions I think you had multiple deadlocks.
Deadlock termination kills *all* of the transactions involved in the
deadlock; what else could it do? This is as opposed to serialization
failures, in which usually only one of the transactions involved fails.
-- -- Josh Berkus PostgreSQL Experts Inc.
http://www.pgexperts.com
On 06/08/10 10:49, Josh Berkus wrote: > >> Hm? Please explain what you're talking about. >> > Transaction A locks 1 and wants a lock on 2 > Transaction B locks 2 and wants a lock on 3 > Transaction C locks 3 and wants a lock on 1 > > I've never had the deadlock detector successfully deal with the above. > Let alone a 4-way. > > Hmm - seems to work ok for me (8.3.11 with pgbench schema updating branches table by bid): UPDATE branches SET filler='filled' WHERE bid=:x I get transaction A succeeds, B is rolled back by the deadlock detector, C left waiting for A to commit or rollback. What do you find? Cheers Mark
On Thu, Aug 05, 2010 at 03:49:05PM -0700, Josh Berkus wrote: > > > Hm? Please explain what you're talking about. > > Transaction A locks 1 and wants a lock on 2 > Transaction B locks 2 and wants a lock on 3 > Transaction C locks 3 and wants a lock on 1 > > I've never had the deadlock detector successfully deal with the above. > Let alone a 4-way. Hm. I have seen 5way deadlocks getting resolved just recently. I can find the relevant if you find it interesting, but I doubt it is. > > Not sure I believe this either; one deadlock kills one transaction. > > If you lose multiple transactions I think you had multiple deadlocks. > > Deadlock termination kills *all* of the transactions involved in the > deadlock; what else could it do? This is as opposed to serialization > failures, in which usually only one of the transactions involved fails. Uhm: postgres=# CREATE TABLE a(); CREATE TABLE postgres=# CREATE TABLE b(); CREATE TABLE a: postgres=# BEGIN;LOCK a; b: postgres=# BEGIN;LOCK b; BEGIN;LOCK a; a: postgres=# lock b; b: ERROR: deadlock detected DETAIL: Process 12016 waits for AccessExclusiveLock on relation 24585 of database 11564; blocked by process 12011. Process 12011 waits for AccessExclusiveLock on relation 24588 of database 11564; blocked by process 12016. HINT: See server log for query details Afaik it worked like that for years. Andres
Josh Berkus <josh@agliodbs.com> writes:
>> Hm? Please explain what you're talking about.
> Transaction A locks 1 and wants a lock on 2
> Transaction B locks 2 and wants a lock on 3
> Transaction C locks 3 and wants a lock on 1
> I've never had the deadlock detector successfully deal with the above.
> Let alone a 4-way.
>> Not sure I believe this either; one deadlock kills one transaction.
>> If you lose multiple transactions I think you had multiple deadlocks.
> Deadlock termination kills *all* of the transactions involved in the
> deadlock; what else could it do? This is as opposed to serialization
> failures, in which usually only one of the transactions involved fails.
I'm not sure whose deadlock detector you're talking about, but it's
not Postgres'.
regards, tom lane
>> I've never had the deadlock detector successfully deal with the above.
>> Let alone a 4-way.
> Hm. I have seen 5way deadlocks getting resolved just recently. I can
> find the relevant if you find it interesting, but I doubt it is.
Ah, I didn't know that it was even *supposed* to resolve
larger-than-2-way deadlocks, so I didn't attempt to look for more
granular information. Next time I need to resolve one of these, I'll
get analysis information about exactly which kinds of locks are being
held where. I've seen it happen at multiple sites running 8.3 and 8.4,
so whatever code is supposed to resolve circular deadlocks doesn't work
all the time.
-- -- Josh Berkus PostgreSQL Experts Inc.
http://www.pgexperts.com
On Thu, 2010-08-05 at 19:39 +0300, Heikki Linnakangas wrote: > On 05/08/10 18:43, Simon Riggs wrote: > > Do we still need me to work on concurrent MERGE, or is that included in > > the current MERGE patch (can't see it), or ... > > It's not in the current MERGE patch. OK, I will work on it, eventually, in this release. -- Simon Riggs www.2ndQuadrant.comPostgreSQL Development, 24x7 Support, Training and Services