4

Some database features, such as SELECT ... FOR UPDATE and ON DELETE CASCADE, are implicitly vulnerable to deadlocks because the database does not specify what locking order will be used. I found two discussions that hint that this behavior isn't specified by the SQL standard, not to mention specific implementations. As such, I'm operating under the assumption that we cannot control the locking order (at least, it's not obvious how to do so).

How are we supposed to avoid database deadlocks if we cannot rely on the locking order?

If we're not supposed to avoid deadlocks (you're going to have to fight very hard to convince me of this) then what are we supposed to do?

This question is meant to be database-agnostic so please don't ask me which database I'm using.

Gili
  • 86,244
  • 97
  • 390
  • 689
  • Deadlocks are caused by faults in application programs. You just need to sort out your applications and use the database properly. Don't try to "roll your own" concurrency controls - leave it to the database. Here's an interesting AskTom question on Oracle dealock handling. http://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11_QUESTION_ID:1068032649872 – Lord Peter Jan 05 '13 at 10:45
  • The point I am making is: You don't need to know what locking order "on cascade delete" uses. The DBMS takes care of locking and concurrency during the delete and cascade, cancelling transactions/rolling back if needed. As far as you are concerned, the delete and cascade is an atomic operation. – Lord Peter Jan 05 '13 at 11:16
  • 1
    @LordPeter, My goal is to write an application that is guaranteed to operate without deadlocks. I see no indication that the database guarantees no deadlock will occur whereas if I roll my own concurrency control I **can** make such a guarantee. Rolling back the transaction is not acceptable; the deadlock shouldn't occur in the first place. – Gili Jan 05 '13 at 11:24
  • 1
    I'm not communicating the issue properly. A deadlock IS BY DEFINITION AN APPLICATION BUG which the DBMS will resolve by sniping/killing one of the deadlocking sessions. A deadlock will ONLY occur if the application is buggy. Roll your own concurrency controls if you must, but Microsoft, Oracle, IBM and a whole crowd of OSS people have been refining theirs for decades - use what they have built for you! – Lord Peter Jan 05 '13 at 11:48
  • @LordPeter, a deadlock can only be an application bug if the application controls the order in which locks are established. Either provide an explanation of the lock order I can expect, or provide an example of a buggy application behavior so I know what to avoid. – Gili Jan 05 '13 at 12:26
  • @Lord Peter is correct. Here is an example http://www.oracle-base.com/articles/misc/deadlocks.php Deadlock will occur when you have a cyclic dependency between two different transactions due to inconsistent order of table access/update. – OldProgrammer Jan 15 '13 at 03:18
  • @LeorA, as I mentioned in the question, it's not clear how to specify the locking order. http://hoopercharles.wordpress.com/2011/11/21/select-for-update-in-what-order-are-the-rows-locked/ is an example that locking order isn't necessarily what you'd expect. – Gili Jan 15 '13 at 03:23

2 Answers2

0

Just don't use those features which can cause deadlocks. ON DELETE CASCADE can be re-written in a way that forces an order and thus avoids deadlocks.

SELECT ... FOR UPDATE is specifically designed to allow you to avoid locks -- it lets you select and lock a row so you can keep a consistent order on all threads.

You do have to be careful how you use it, it could cause a deadlock if you don't understand the locking order of all your updates.

Hogan
  • 69,564
  • 10
  • 76
  • 117
  • I understand how to replace `ON DELETE CASCADE`, but what do you replace `SELECT ... FOR UPDATE` with? – Gili Jan 15 '13 at 03:32
  • Are there any other SQL features that are susceptible to deadlocks and need to be rewritten this way? – Gili Jan 15 '13 at 04:31
  • @Gili - probably, there are many non-standard sql features (`cascade` is just one of them). It depends on which stack you are using. – Hogan Jan 15 '13 at 05:06
  • I scanned the SQL 99 standard. I believe `cascade` is standardized because it's mentioned many times, however I didn't see any discussion what-so-ever of locking order for **any** feature. Is that normal? – Gili Jan 15 '13 at 16:53
  • **UPDATE**: According to http://stackoverflow.com/a/112256/14731 you cannot prevent deadlocks, only reduce their frequency. So perhaps we're better off using `ON DELETE CASCADE` in order to provide the database with more information and hope that it'll use an appropriate locking order under the hood. – Gili May 14 '13 at 21:51
  • @Gili - This is a straw man. CASCADE is still a bad idea IMHO except when you don't have a multi-user system, it gives you no control. – Hogan May 15 '13 at 10:17
  • Hogan, what control do you lose? True, you no longer control the order in which tables are accessed, but if doing so doesn't prevent deadlocks then what is the point of having this control? – Gili May 15 '13 at 15:39
  • The order is what causes deadlocks. – Hogan May 16 '13 at 00:48
  • Hogan, according to http://stackoverflow.com/a/112256/14731 it is technically impossible to control locking order, so I fail to see how manual CASCADE is beneficial. The point is that locking order is an implementation-detail of a database's execution plan (which may change over time). – Gili May 16 '13 at 23:39
  • @Gili - That is not how I read that link. I read that link as "it is hard, if you select more than one table at a time in which case use `sp_lock` to be sure", it was only your comment which said it was impossible. Hard <> Impossible. Another thing to remember, SQLServer will give a deadlock message in cases that are not deadlocks, just slow code. – Hogan May 17 '13 at 00:20
  • The point is, the SQL standard does not mandate locking order, rather this is chosen by the implementation-specific execution plan. Who says that the execution plan won't change over time? `sp_lock` only works for SQLServer and even then it only tells you what works today. It doesn't guarantee that locking order will remain the same in the future. – Gili May 17 '13 at 00:44
  • Look, this is simple. Start a transaction, lock each row in multiple tables in an order you pick -- you may have to use platform specific commands at this stage or not, depending on what functionality you are trying to perform -- end the transaction. IF you use select statements or cascades or other functionality that does not have a defined order, you will run into trouble. If you don't you won't. Simple as that. Don't use stuff that will cause locks. Lamenting that such things might cause problems won't make a robust system. – Hogan May 18 '13 at 12:50
  • 1. `Don't use stuff that will cause locks`: All operations will cause (read or write) locks. The fact that they are released after the statement does not change this fact. 2. `If you use [statements] ... that does not have a defined order, you will run into trouble.`: The SQL standard does not guarantee the locking order that you'll get. You can issue the same `SELECT` statement multiple times and end up with a different locking order depending on the execution plan. – Gili May 18 '13 at 16:50
  • @Gili - not if each select statement only accesses one table. In any platform you can define the transaction to hold the locks for the lifetime of the transaction, thus you use single table select statements in an order to know the order -- if you use statement (select or otherwise) that does not have an order then you are in trouble, don't do this. Yes if you do it wrong it won't work. Don't use select against multiple tables or other statements that don't guarantee order unless the table has been locked in the transaction. – Hogan May 18 '13 at 19:18
  • SELECT ... FOR UPDATE is bad cause you get a runaway when it will kill the table. You should use mvcc in postgress to avoid + Redis resouce locking to avoid too many concurrent operations – aligatorr89 Dec 09 '22 at 17:03
-1

A few years wiser, I am revising the accepted answer to state that database deadlocks cannot be prevented.

If you are lucky enough to be able to break down database operations to only interact with a single table at a time (something that isn't always possible) then you are forced to choose between poor performance and the possibility of deadlocks. Pick your poison.

Gili
  • 86,244
  • 97
  • 390
  • 689
  • Would it not be closer to the truth to say that lock order cannot be determined at the *statement* level? It can certainly be determined at the block level by the order of statements. It is simply the case then that any cascaded deletes must be done as part of a procedure (with locks held between statements as appropriate) rather than in terms of a constraint. – Steve Dec 31 '17 at 13:07
  • @Steve I assume that your definition of a block is a collection of statements. If so, how can lock order be determined at a block level if it cannot be determined at a statement level? Adding locks will not help because individual statements will trigger a deadlock on their own. (This discussion assumes that individual statements have to multiple tables and this cannot be divided across multiple statements.) – Gili Dec 31 '17 at 13:11
  • 1
    Individual statements cannot (unless I'm seriously missing something) trigger deadlocks on their own. It always requires two separate statements, in separate transactions, to be interacting concurrently. Also, a statement does not *have* to select multiple tables - I can lock one table, then the other, and *then* start the work that involves the pair of tables. I don't doubt that this approach, if applied consistently, would soon have developers begging for mercy, but such are the inherent complexities of concurrent programming if deadlocks *absolutely cannot* be afforded. – Steve Dec 31 '17 at 13:26
  • @Steve Seeing as you have no control over a statement's execution plan, and that the same statement could deadlock against a itself running in a different thread (with a different execution plan) what you are essentially advocating is running in `SERIALIZABLE` transaction isolation. Further, I would point out that some statements cannot be broken down without risking race-conditions (e.g. `SELECT employee.name, employer.name FROM employee ee, employer er, WHERE ee.employer_id = er.id`). Finally, see https://stackoverflow.com/a/25694525/14731 "[..] Read-only rows can [...] cause deadlocks" – Gili Dec 31 '17 at 13:32
  • Even `SERIALIZABLE` transactions can deadlock. But the same statement cannot deadlock against itself, unless what you mean is an identical statement executed separately and concurrently in a different transaction. The whole point of acquiring locks in a set order, then, is to prevent any other transaction proceeding past the first hurdle, until a previous transaction has finished it's work. E.g. lock t1, lock t2, perform work on t1 & t2. A second transaction executing an identical block, won't be able to acquire the t1 lock (the first step) until the first transaction finishes. – Steve Dec 31 '17 at 13:38