MySQL Bugs: #15136: Deadlock on tables with foreign key reference

Bug #15136	Deadlock on tables with foreign key reference
Submitted:	22 Nov 2005 14:52	Modified:	23 Nov 2005 10:07
Reporter:	Maxim M	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server: InnoDB storage engine	Severity:	S2 (Serious)
Version:	5.0.15-standard-log,4.1.15,possible all	OS:	Linux (RH AS3, AS4,possible all)
Assigned to:	Bugs System	CPU Architecture:	Any

Description:
Deadlock happens when more than 2 transactions runnig SELECT/DELETE/INSERT queries on table with foreign key reference to another table. 

How to repeat:
I can't reproduce it step-by-step (cause bug is race condition, i guess), but it easily reproducable with next steps:

1) Create and init database:
-------------------------------------------------------------------------------
CREATE DATABASE IF NOT EXISTS deadlock;
USE deadlock;

CREATE TABLE test (
  id bigint(20) NOT NULL auto_increment,
  value bigint(20) NOT NULL,
  PRIMARY KEY (id),
  INDEX (value)
) ENGINE=InnoDB;

CREATE TABLE test1 (
  id bigint(20) NOT NULL auto_increment,
  value bigint(20) NOT NULL,
  test_id_ref bigint(20) NOT NULL,
  FOREIGN KEY (test_id_ref) REFERENCES test (id) on delete cascade,
  PRIMARY KEY (id),
  INDEX (test_id_ref)
) ENGINE=InnoDB;

INSERT INTO test VALUES (1, 1);
INSERT INTO test VALUES (2, 2);
INSERT INTO test VALUES (3, 3);
INSERT INTO test VALUES (4, 4);
INSERT INTO test VALUES (5, 5);

INSERT INTO test1 VALUES (1, 1, 1);
INSERT INTO test1 VALUES (2, 2, 2);
INSERT INTO test1 VALUES (3, 3, 3);
INSERT INTO test1 VALUES (4, 4, 4);
INSERT INTO test1 VALUES (5, 5, 5);
-------------------------------------------------------------------------------

2) Run next java code:
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;

/**
 * @author Maxim
 */
public class DatabaseDeadlockTest implements Runnable {

    static {
        try {
            Class.forName("com.mysql.jdbc.Driver");
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }
    }

    private String url = "jdbc:mysql://localhost:3306/deadlock";
    private String user = "root";
    private String password = "";

    protected Connection connection;
    private Thread thread;
    private int index;

    public DatabaseDeadlockTest(int i) throws SQLException {
        index = i;
        connection = DriverManager.getConnection(url, user, password);
        thread = new Thread(this, "[Worker " + index + "]");
        thread.start();
    }

    public void run() {
        // wait all threads to start in the same time 
        synchronized (this) {
            try {
                wait(500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        try {
            for (int i = 1; i < 300; i++) {
                try {
                    connection.setAutoCommit(false);
                    Statement stmt = connection.createStatement();

                    // select from first table
                    stmt.execute("SELECT * FROM test WHERE id IN (" + index
                            + ")");

                    // delete from ref table
                    stmt.executeUpdate("DELETE FROM test1 WHERE test_id_ref = "
                            + index);
                    
                    for (int j = 1; j < 30; j++) {
                        // insert to ref table
                        stmt.executeUpdate("INSERT INTO test1 (value, test_id_ref) VALUES ("
                                + (int) (Math.random() * 10) + ", " + index
                                + ")");
                    }

                    stmt.close();
                    connection.commit();
                } catch (SQLException e) {
                    e.printStackTrace();
                    try {
                        ResultSet rs = connection.createStatement().executeQuery("SHOW ENGINE INNODB STATUS");

                        if (rs.next()) {
                            log(rs.getString(1));
                        }
                    } catch (SQLException e1) {
                        e1.printStackTrace();
                    }
                    System.exit(-1);
                }
            }
        } finally {
            try {
                connection.close();
            } catch (SQLException e) {
                e.printStackTrace();
            }
            log("done");
        }
        
    }

    void log(String log) {
        System.out.println(thread.getName() + ": " + log);
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        try {
            DatabaseDeadlockTest ddt1 = new DatabaseDeadlockTest(1);
            DatabaseDeadlockTest ddt2 = new DatabaseDeadlockTest(2);
            DatabaseDeadlockTest ddt3 = new DatabaseDeadlockTest(3);
            DatabaseDeadlockTest ddt4 = new DatabaseDeadlockTest(4);
            DatabaseDeadlockTest ddt5 = new DatabaseDeadlockTest(5);
        } catch (SQLException e) {
            e.printStackTrace();
        }
    }

}

3) Notice that each Transaction/Thread/Connection works only on rows with same reference value, i.e each transaction does:
SET autocommit=0
SELECT * FROM test WHERE id IN (1)
DELETE FROM test1 WHERE test_id_ref = 1
INSERT INTO test1 (value, test_id_ref) VALUES (2, 1)
INSERT INTO test1 (value, test_id_ref) VALUES (9, 1)
COMMIT
with it's own id/test_id_ref (in example = 1). 

I supose that in this case no transaction should lock another transactions for execution - beside DELETE statement - that locks whole table (or index only ?) until all other inserts not committed (from mysql.log):
                      3 Query       SET autocommit=0
                      3 Query       SELECT * FROM test WHERE id IN (1)
                      3 Query       DELETE FROM test1 WHERE test_id_ref = 1
                      3 Query       INSERT INTO test1 (value, test_id_ref) VALUES (5, 1)
                      3 Query       INSERT INTO test1 (value, test_id_ref) VALUES (7, 1)
                      5 Query       SET autocommit=0
                      5 Query       SELECT * FROM test WHERE id IN (3)
                      5 Query       DELETE FROM test1 WHERE test_id_ref = 3
                      3 Query       INSERT INTO test1 (value, test_id_ref) VALUES (7, 1)
                      3 Query       INSERT INTO test1 (value, test_id_ref) VALUES (3, 1)
                      6 Query       SET autocommit=0
                      6 Query       SELECT * FROM test WHERE id IN (4)
                      6 Query       DELETE FROM test1 WHERE test_id_ref = 4
                      3 Query       commit
                      5 Query       INSERT INTO test1 (value, test_id_ref) VALUES (6, 3)
                      .....
Here connection 5 do DELETE and INSERT only when 3 COMMITTED.

Log of Mysql 5.0.15 with deadlock happens in Connection 6 (before SHOW ENGINE INNODB STATUS)

Attachment: mysql.log (application/octet-stream, text), 22.59 KiB.

Java test file

Attachment: DatabaseDeadlockTest.java (text/x-java), 3.36 KiB.

Example deadlock log (SHOW INNODB STATUS)

Attachment: deadlock.log (application/octet-stream, text), 6.83 KiB.

Jan,

please analyze the deadlock. I guess it comes from next-key locking. Maybe we could somehow optimize locking to avoid this deadlock?

Regards,

Heikki

I was able to reproduce this bug in 5.0.16/FC4 using the supplied test case

TRANSACTION 0 1812, ACTIVE 0 sec, process no 9139, OS thread id 57359 inserting
mysql tables in use 1, locked 1
LOCK WAIT 8 lock struct(s), heap size 1024, undo log entries 2
MySQL thread id 5, query id 154 localhost 127.0.0.1 root update
INSERT INTO test1 (value, test_id_ref) VALUES (6, 3)
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 55 n bits 160 index `test_id_ref` of table `deadlock/test1` trx id 0 1812 lock_mode
 X locks gap before rec insert intention waiting
Record lock, heap no 5 PHYSICAL RECORD: n_fields 2; compact format; info bits 32
 0: len 8; hex 8000000000000004; asc         ;; 1: len 8; hex 8000000000000004; asc         ;;

This transaction is waiting a X with insert intention to a gap.

*** (2) TRANSACTION:
TRANSACTION 0 1813, ACTIVE 0 sec, process no 9141, OS thread id 61456 setting auto-inc lock
mysql tables in use 1, locked 1
5 lock struct(s), heap size 320, undo log entries 1
MySQL thread id 6, query id 155 localhost 127.0.0.1 root update
INSERT INTO test1 (value, test_id_ref) VALUES (2, 4)
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 0 page no 55 n bits 160 index `test_id_ref` of table `deadlock/test1` trx id 0 1813 lock_mode
 X
Record lock, heap no 5 PHYSICAL RECORD: n_fields 2; compact format; info bits 32
 0: len 8; hex 8000000000000004; asc         ;; 1: len 8; hex 8000000000000004; asc         ;;

This transactions holds a X-lock to a record (granted for delete)

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
TABLE LOCK table `deadlock/test1` trx id 0 1813 lock mode AUTO-INC waiting
*** WE ROLL BACK TRANSACTION (2)

Transaction is waiting an auto-increment table lock which is granted to the transaction 1.

Fundamental reason behind this deadlock is the next-key locking. Transaction 1 has requested a next-key lock for the index text-id-ref.

Hi!

Ok, this is a classic case of next-key locking versus predicate locking. The index test_id_ref is not unique. When trx (2) deleted all records with value 4, it had to lock also the 'gap' after the last record with value 3. That was to prevent further insertions with value 4 to the 'gap'. 

Predicate locking would remember that the delete ONLY operated on records with value 4, and it would allow an insertion with value 3. But next-key locking does not remember why we locked the gap.

You can remove the deadlock problem (and next-key locking) with the my.cnf option:

innodb_locks_unsafe_for_binlog

but read carefully the warnings about that option. In MySQL-5.1 with 'row-based replication' (better name would be row-based binlogging), that option will be safe to use.

I am setting this bug report to the state 'Not a bug'.

Regards,

Heikki

INSERT INTO test1 (value, test_id_ref) VALUES (6, 3)
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 55 n bits 160 index `test_id_ref` of table
`deadlock/test1` trx id 0 1812 lock_mode
 X locks gap before rec insert intention waiting
Record lock, heap no 5 PHYSICAL RECORD: n_fields 2; compact format; info bits
32
 0: len 8; hex 8000000000000004; asc         ;; 1: len 8; hex 8000000000000004;
asc         ;;

Unfortunatly you wrong. This flag is set and i attached configurations file for DB

MySql configuration file attached

Attachment: my.ini (application/octet-stream, text), 11.80 KiB.

InnoDB startup option locks_unsafe_for_binlog does not affect on insert intention type locks. Thus if you have a lock on a record or a gap insert intention has to wait for it. Note that there is a X-lock on a record (value 4) in the second transaction in the deadlock. 

Regards,
    JanL