Bug #48652 Deadlock due to Foreign Key constraint
Submitted: 9 Nov 2009 21:13 Modified: 10 Mar 2014 21:43
Reporter: Brandon Petty Email Updates:
Status: Verified Impact on me:
None 
Category:MySQL Server: Locking Severity:S4 (Feature request)
Version:5.1.39, 5.1.42 OS:Any (XP, Linux)
Assigned to: Ståle Deraas CPU Architecture:Any
Tags: foreignkey deadlock
Triage: Triaged: D5 (Feature request)

[9 Nov 2009 21:13] Brandon Petty
Description:
This is a very troubling deadlock scenario.

Table A has a Fkey constraint referencing the Pkey of Table B.  Two transactions insert data into Table A that contain the same FKey constraint value.  Each transaction then attempts to update the same row in Table B which was referenced by the constraint.  The first transaction gets blocked and the second transaction triggers a deadlock.

This is a very common operation for adding items, for example, into a queue via the inserts and then incrementing the queue count via an update.

I think this is more of an architectural bug.
We have been using MSSQL Server, Oracle, and DB2 with no problems.
MSQL Server, for example, lets the first UPDATE go through so it can be committed... thus never causing a deadlock.

How to repeat:
-- Session setting for each connection
set session transaction isolation level read committed;
set autocommit = 0;

-- Setup the database tables

CREATE TABLE  `yourDB`.`tmp_tbl_1` (
  `TMP1_ID` varchar(23) NOT NULL,
  `ITEMS` int(11) DEFAULT NULL,
  PRIMARY KEY (`TMP1_ID`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

CREATE TABLE  `yourDB`.`tmp_tbl_2` (
  `TMP2_ID` varchar(23) NOT NULL,
  `ITEMS` int(11) DEFAULT NULL
[9 Nov 2009 22:30] Brandon Petty
Third try's the char
[9 Nov 2009 22:59] Miguel Solorzano
Thank you for the bug report. If you are having problems to paste the test case, then try to add it using a text file attaching it using the files tab. Thanks in advance.
[10 Nov 2009 17:04] Brandon Petty
Deadlock recreation code, and SHOW INNODB STATUS output

Attachment: MySQL_Deadlock.txt (text/plain), 6.40 KiB.

[11 Nov 2009 14:49] Brandon Petty
Attached is the feedback you are looking for.
Let me know if you need anything else.
[12 Nov 2009 5:26] Valeriy Kravchuk
Doesn't this quote from the manual explain why deadlock happens:

"If a FOREIGN KEY constraint is defined on a table, any insert, update, or delete that requires the constraint condition to be checked sets shared record-level locks on the records that it looks at to check the constraint. InnoDB also sets these locks in the case where the constraint fails."

See http://dev.mysql.com/doc/refman/5.1/en/innodb-locks-set.html.

On a single record of the first table you have: 

S lock from transaction 1 set, 
S lock from transaction 2 set, 
X lock from transaction 1 requested, blocked by S lock from transaction 2, 
X lock from transaction 2 requested, blocked by S lock from transaction 1
--> deadlock.
[13 Nov 2009 4:43] Brandon Petty
No, you are correct... the manual does say that.
But just because the manual acknowledges its own design limitations does not make it right, however.  This is a serious architectural problem... not so much because of the deadlock, but because it is a huge concurrency issue.  The update should never block in the first place.  Agreed?  I guess this is really a feature request ticket requesting the addition of "update locks".  Without them not only will MySQL deadlock needlessly, you wont be able to scale with high concurrency based applications that actually have a relational database schema!
[13 Nov 2009 5:03] Valeriy Kravchuk
Please, check if this is actually a duplicate of any of the following reports:

http://bugs.mysql.com/bug.php?id=21356
http://bugs.mysql.com/bug.php?id=39657
http://bugs.mysql.com/bug.php?id=9514

I do not see a direct request to add update locks though, but they are mentioned as possible solution.
[13 Nov 2009 6:13] Brandon Petty
Thanks Valeriy for the links.

Ticket 39657 is a duplicate of 21356... but my ticket describes a different situation.  Ticket 9514 is simply a SELECT FOR UPDATE NOWAIT feature request... which I'd love to see implemented.

We can turn this into an update lock feature request ticket if you think that is best, but with my limited db locking knowledge, that is the only way I know of to fix these situations... although there are probably many different strategies implemented by other databases to get around this.

I still feel this is a bug though... based only on the fact that no other commercial grade database I've tested blocks on the first update and then deadlocks on the second.  This should be, in my opinion, a functional requirement... and if a software product does behave as intended as defined by the requirement... it is a bug.
[13 Nov 2009 6:17] Brandon Petty
Sorry, I meant to say, "... if it does *NOT*
behave as intended as defined by the requirement... it is a bug."
[13 Nov 2009 9:09] Valeriy Kravchuk
I agree that this is a design problem, so we request a redesign. Let InnoDB/Oracle decide what exactly that should change/implement to prevent deadlocks in cases like this.
[17 Nov 2009 16:22] Heikki Tuuri
There is a workaround for this in the database application code. UPDATE FIRST the parent row counter:

UPDATE <parent row> SET count = count + 1;
INSERT <child row>; /* if the INSERT fails, roll back the trx */

Changing this to a feature request. Let me think if we could avoid this deadlock somehow in InnoDB itself...
[17 Nov 2009 16:30] Heikki Tuuri
Unfortunately, avoiding this kind of a deadlock would require some type of column level granularity record locking in InnoDB, which would add complexity to the InnoDB lock table. I recommend using the workaround in the application code.
[14 Sep 2010 17:19] Brandon Petty
I didn't know if there has been any further thought on this issue.
While the work around does indeed makes sense, you can not really apply it to complex production software.  Take our product for example... we have 353 tables in our *relational* database being accessed constantly by a server(s) that averages 15 - 50 worker threads depending on the customer.  Each worker thread is processing (usually) different requests for all of our clients.  Each request could contain any number and combination of sql queries and statements.  That is why we rely heavily on the database and why each database we support has to have a mature locking system.  We could theoretically mutex the living heck out of our product... but then we serialize it.  If you have 20K clients simultaneously hitting your server... you can't afford to serialize everything at the app level.  The database needs to be smart enough to optimally handle these situations... and most, like SQL Server, Sybase, DB2, CTreeSQL, and Oracle, do.  So while the example work-around does work for a very simple system, complex multithreaded systems can not implement it.
[3 Aug 2011 22:41] Sveta Smirnova
Bug #61965 was marked as duplicate of this one.
[22 Oct 2012 12:32] Marko Mäkelä
This is a problem in MySQL-level table locking.

Internally inside InnoDB, a FOREIGN KEY constraint check may read (or, with ON UPDATE or ON DELETE clause, write) parent or child tables.

Normally, table access is governed by the following locks:
1. MySQL meta-data lock
2. InnoDB table lock
3. InnoDB record locks

All these locks are held until the end of the transaction.

The InnoDB table and record locks are skipped in certain modes, but not during foreign key checks. The deadlock is caused because MySQL acquires the meta-data lock only for the table(s) that are explicitly mentioned in the SQL statements.

I guess that a workaround could be to access the child (or parent) tables at the start of the transaction, before the problematic FOREIGN KEY operation.
[19 Dec 2013 14:46] Pura Vida
I encountered the same issue and then found this bug report. I would like
post the little bit simpler reproducing procedure for people to see, and 
also I would like to ask: is the workaround is to reverse the order:
to do the update first and then insert? Thanks.

0 - set up

mysql> create table PAY_ARGMT (id int, b int, primary key (id));
Query OK, 0 rows affected (0.21 sec)

mysql> create table PAY_TRAN (id int, PAY_ARGMT_ID int, foreign key (PAY_ARGMT_ID) references PAY_ARGMT(id) );
Query OK, 0 rows affected (0.24 sec)

mysql> insert into PAY_ARGMT values (10,10);
Query OK, 1 row affected (0.00 sec)

mysql> commit;
Query OK, 0 rows affected (0.10 sec)

1 - dead lock

session 1:
mysql> insert into PAY_TRAN values (1, 10);
Query OK, 1 row affected (0.00 sec)

   session 2:
   mysql> insert into PAY_TRAN values (2, 10); # Lock PAY_ARGMT ID=10 because of FK
   Query OK, 1 row affected (0.00 sec)

session 1:
mysql> update PAY_ARGMT set b=11 where id=10;  # Locked by Session 2

   session 2:
   mysql> update PAY_ARGMT set b=12 where id=10;
   ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction
[19 Dec 2013 14:52] Pura Vida
Just want to add to above comment that reversing the order indeed prevents
the dead lock, but the second transaction is blocked (but not dead lock) by
the first. And when the first is committed, the second is unblocked. Is this
better than the dead lock?
[10 Mar 2014 21:43] Brandon Petty
I just thought I would share this link:

http://michael.otacoo.com/postgresql-2/postgres-9-3-feature-highlight-for-key-share-and-fo...

Hopefully this motivates Oracle.  This ticket is now 5 years old.