Deadlocks, indexing and Primary Key's

Recently a customer has shown up with some deadlocks occurring frequently. They were of the following type (I have shortened the output a bit):

*** (1) TRANSACTION:

TRANSACTION 22723019234, fetching rows
mysql tables in use 1, locked 1
LOCK WAIT 7 lock struct(s), heap size 1216, 14 row lock(s)
update location set expires='2012-08-10 04:50:29' where username='12345678901' AND contact='sip:12345678901@192.168.0.191:5060' AND callid='945a20d4-8945dcb5-15511d3e@192.168.0.191'

*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 2203904 n bits 136 index `GEN_CLUST_INDEX` of table `location` trx id 22723019234 lock_mode X locks rec but not gap waiting


*** (2) TRANSACTION:

TRANSACTION 22723019222, fetching rows, thread declared inside InnoDB 225
mysql tables in use 1, locked 1
192 lock struct(s), heap size 30704, 9483 row lock(s)
delete from location where expires<'2012-08-10 04:49:30' AND expires!='1969-12-31 19:00:00'

*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 0 page no 2203904 n bits 136 index `GEN_CLUST_INDEX` of table `location` trx id 22723019222 lock_mode X

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 2203951 n bits 136 index `GEN_CLUST_INDEX` of table `location` trx id 22723019222 lock_mode X waiting

*** WE ROLL BACK TRANSACTION (1)

They want us to have this fixed. And they did not like the answer that the application has to cope with deadlocks [ 1 ].

But one thing looks suspicious here: The GEN_CLUSTER_INDEX! This basically means there was NO explicit Primary Key on the InnoDB table and InnoDB was creating its own internal Primary Key.

After some discussion we started to examine the whole situation. For this we transformed the UPDATE and the DELETE statement into SELECT's:

UPDATE

EXPLAIN
SELECT *
  FROM location
 WHERE username='12345678901'
   AND contact='sip:12345678901@192.168.0.191:5060'
   AND callid='945a20d4-8945dcb5-15511d3e@192.168.0.191'
;

+----+-------------+----------+------+---------------+----------+---------+-------+------+------------------------------------+
| id | select_type | table    | type | possible_keys | key      | key_len | ref   | rows | Extra                              |
+----+-------------+----------+------+---------------+----------+---------+-------+------+------------------------------------+
|  1 | SIMPLE      | location | ref  | username      | username | 66      | const |    9 | Using index condition; Using where |
+----+-------------+----------+------+---------------+----------+---------+-------+------+------------------------------------+

The first strange thing is, that the MySQL optimizer expects 9 rows (on a long key of 66 bytes) which theoretically should be a Primary Key access! This sound non optimal. And as shorter and faster transactions are as less probable are deadlocks.

START TRANSACTION;
SELECT *
  FROM location
 WHERE username='12345678901'
   AND contact='sip:12345678901@192.168.0.191:5060'
   AND callid='945a20d4-8945dcb5-15511d3e@192.168.0.191'
   FOR UPDATE
;

---TRANSACTION 14033
4 lock struct(s), heap size 1248, 11 row lock(s)
MySQL thread id 5, OS thread handle 0x7f3647b9e700, query id 526 localhost root cleaning up

We can see that the same query uses 4 lock structs and locks in total 11 rows. This is similar to what we have seen in the deadlock.

DELETE

EXPLAIN
SELECT *
  FROM location
 WHERE expires < '2012-08-10 04:49:30'
   AND expires != '1969-12-31 19:00:00'
;

+----+-------------+----------+------+---------------+------+---------+------+-------+-------------+
| id | select_type | table    | type | possible_keys | key  | key_len | ref  | rows  | Extra       |
+----+-------------+----------+------+---------------+------+---------+------+-------+-------------+
|  1 | SIMPLE      | location | ALL  | NULL          | NULL | NULL    | NULL | 10754 | Using where |
+----+-------------+----------+------+---------------+------+---------+------+-------+-------------+

Uiii! The DELETE does not use an index at all but does a full table scan. Which is not so optimal performance wise...

START TRANSACTION;
SELECT *
  FROM location
 WHERE expires < '2012-08-10 04:49:30'
   AND expires != '1969-12-31 19:00:00'
   FOR UPDATE
;

---TRANSACTION 14034
168 lock struct(s), heap size 31160, 11007 row lock(s)
MySQL thread id 6, OS thread handle 0x7f3647b9e700, query id 663 localhost root cleaning up

And we can see a huge amount of locked rows... The table contains 10840 rows in total. Those numbers differ a bit from the deadlock but it is OK because they do not represent the same point in time.

So we started looking at the table structure. The table which was provided by the customer looks as follows:

CREATE TABLE `location` (
  `username` varchar(64) NOT NULL DEFAULT '',
  `domain` varchar(128) NOT NULL DEFAULT '',
  `contact` varchar(255) NOT NULL DEFAULT '',
  `received` varchar(255) DEFAULT NULL,
  `path` varchar(255) DEFAULT NULL,
  `expires` datetime NOT NULL DEFAULT '2020-01-01 00:00:00',
  `q` float(10,2) NOT NULL DEFAULT '1.00',
  `callid` varchar(255) NOT NULL DEFAULT 'Default-Call-ID',
  `cseq` int(11) NOT NULL DEFAULT '42',
  `last_modified` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
  `replicate` int(10) unsigned NOT NULL DEFAULT '0',
  `state` tinyint(1) unsigned NOT NULL DEFAULT '0',
  `flags` int(11) NOT NULL DEFAULT '0',
  `cflags` int(11) NOT NULL DEFAULT '0',
  `user_agent` varchar(100) NOT NULL DEFAULT '',
  `socket` varchar(128) DEFAULT NULL,
  `methods` int(11) DEFAULT NULL,
  `id` int(10) NOT NULL DEFAULT '0',
  KEY `username` (`username`,`domain`,`contact`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1
;

First I want to fix the problem of the full table scan:

ALTER TABLE location ADD INDEX (expires);

Then the DELETE looks much better:

+----+-------------+----------+-------+---------------+---------+---------+------+------+-----------------------+
| id | select_type | table    | type  | possible_keys | key     | key_len | ref  | rows | Extra                 |
+----+-------------+----------+-------+---------------+---------+---------+------+------+-----------------------+
|  1 | SIMPLE      | location | range | expires       | expires | 5       | NULL |    2 | Using index condition |
+----+-------------+----------+-------+---------------+---------+---------+------+------+-----------------------+

---TRANSACTION 14074
2 lock struct(s), heap size 1248, 1 row lock(s)
MySQL thread id 6, OS thread handle 0x7f3647b9e700, query id 671 localhost root cleaning up

But I do not know how realistic my actual data are. This can change with an other data-set!

Now I want to see if there is any difference with the KEY declared as a Primary Key:

ALTER TABLE location DROP INDEX username, ADD PRIMARY KEY (username, domain, contact);

Long indexes are bad for InnoDB. See blog post which will hopefully appear soon!

+----+-------------+----------+------+---------------+---------+---------+-------+------+-------------+
| id | select_type | table    | type | possible_keys | key     | key_len | ref   | rows | Extra       |
+----+-------------+----------+------+---------------+---------+---------+-------+------+-------------+
|  1 | SIMPLE      | location | ref  | PRIMARY       | PRIMARY | 66      | const |    9 | Using where |
+----+-------------+----------+------+---------------+---------+---------+-------+------+-------------+

---TRANSACTION 14145
3 lock struct(s), heap size 1248, 10 row lock(s)
MySQL thread id 6, OS thread handle 0x7f3647b9e700, query id 684 localhost root cleaning up

Execution plan looks the same. OK. 1 row less is locked. This means 10% less probability of deadlocks?

The effect was not as big as expected. So rolling back last change (making at least a unique key out of it).

As already mentioned, short Primary Keys are good for InnoDB. And as we will show in a blog post soon VARCHAR are bad performance wise. So we try to use the non used? field id:

ALTER TABLE location DROP PRIMARY KEY, ADD UNIQUE KEY (username, domain, contact);

ALTER TABLE location MODIFY COLUMN id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY;

EXPLAIN
SELECT *
  FROM location
 WHERE id = 2984
;

+----+-------------+----------+-------+---------------+---------+---------+-------+------+-------+
| id | select_type | table    | type  | possible_keys | key     | key_len | ref   | rows | Extra |
+----+-------------+----------+-------+---------------+---------+---------+-------+------+-------+
|  1 | SIMPLE      | location | const | PRIMARY       | PRIMARY | 4       | const |    1 | NULL  |
+----+-------------+----------+-------+---------------+---------+---------+-------+------+-------+

START TRANSACTION;
SELECT *
  FROM location
 WHERE id = 2984
   FOR UPDATE
;

---TRANSACTION 14336
2 lock struct(s), heap size 376, 1 row lock(s)
MySQL thread id 6, OS thread handle 0x7f3647b9e700, query id 701 localhost root cleaning up

And see there: The Query Execution Plan looks much better and locks are much smaller.

As a result

• Use proper indexing (expires).
• Follow the rules: Creating Primary Keys on relational database tables. See also article: Disadvantages of explicitly NOT using InnoDB Primary Keys?.
• Follow the rules: Create short synthetic Primary Keys and avoid long natural Primary Keys (especially with InnoDB): Clustered and Secondary Indexes and Optimizing InnoDB Queries.
• Make your application aware of deadlocks (and other kinds of aborted transactions) and reissue transaction if it fails with a deadlock. [ 1 ]

I hope we can add here the results on the impact of deadlock occurrence soon.