Mysql – A single, simple update takes 10+ seconds

We are running MySQL 5.1.71-log and have a table with 2.7 million rows. Simple updates to it are regularly taking more than 10 seconds to execute.

The table structure is:

CREATE TABLE `person` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `company_id` int(10) unsigned NOT NULL,
  `status` enum('tmp','active') DEFAULT 'tmp',
  `remote_id` varchar(64) DEFAULT NULL,
  `name_last` varchar(64) DEFAULT NULL,
  `name_first` varchar(64) DEFAULT NULL,
  `sex` char(1) DEFAULT NULL,
  `dob` date DEFAULT NULL,
  `mtime` datetime NOT NULL,
  `ctime` datetime NOT NULL,
  PRIMARY KEY (`id`),
  KEY `ix_ID_SCHEME_LAST_FIRST_DOB` (`company_id`,`name_first`,`name_last`,`dob`),
  KEY `ix_ID_SCHEME_LAST_FIRST_DOB_GENDER` (`company_id`,`name_first`,`name_last`,`dob`,`sex`),
  KEY `ix_ID_SCHEME_MRN` (`company_id`,`remote_id`),
  CONSTRAINT `patient_ibfk_1` FOREIGN KEY (`company_id`) REFERENCES `company` (`id`)
) ENGINE=InnoDB

An update looks like

UPDATE person SET `company_id` = '1', `status` = 'tmp', `remote_id` = '12345', `name_last` = 'DOE', `name_first` = 'JOHN', `sex` = 'M', `dob` = '1980-01-01 00:00:00', `mtime` = '2014-07-11 14:16:07', `ctime` = '2014-07-10 23:00:27' WHERE id = '2693633'

Any ideas about what could be making this slow? Could it be the foreign key?

Edit 1:

show table status like 'patient'\G
*************************** 1. row ***************************
           Name: person
         Engine: InnoDB
        Version: 10
     Row_format: Compact
           Rows: 2581914
 Avg_row_length: 77
    Data_length: 199966720
Max_data_length: 0
   Index_length: 421134336
      Data_free: 5242880
 Auto_increment: 2702933
    Create_time: 2014-07-04 21:38:27
    Update_time: NULL
     Check_time: NULL
      Collation: utf8_general_ci
       Checksum: NULL
 Create_options: 
        Comment: 
1 row in set (0.10 sec)

Edit 2:

CREATE TABLE `company` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `app_id` int(10) unsigned NOT NULL,
  `name` varchar(200) NOT NULL,
  `name_internal` varchar(200) NOT NULL,
  `license` enum('lite','full') NOT NULL DEFAULT 'lite',
  `sales_state` enum('demo','trial','paidtrial','customer','internal') DEFAULT NULL,
  `state_mtime` datetime DEFAULT NULL,
  `status` enum('tmp','active','inactive','locked') NOT NULL DEFAULT 'tmp',
  `status_mtime` datetime DEFAULT NULL,
  `beta` int(11) DEFAULT NULL,
  `mtime` datetime NOT NULL,
  `ctime` datetime NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `company_name_idx` (`name`),
  UNIQUE KEY `company_name_internal_idx` (`name_internal`),
  KEY `app_id` (`app_id`),
  CONSTRAINT `company_ibfk_1` FOREIGN KEY (`app_id`) REFERENCES `app` (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=2586 DEFAULT CHARSET=utf8;

and since this has a foreign key out to table app:

CREATE TABLE `app` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `type` enum('echo') NOT NULL,
  `base_url` varchar(128) NOT NULL,
  `cookie_domain` varchar(128) NOT NULL,
  `internal_url` varchar(128) NOT NULL,
  `name` varchar(128) NOT NULL,
  `login_logo` varchar(128) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `app_base_url_idx` (`base_url`),
  UNIQUE KEY `app_internal_url_idx` (`internal_url`)
) ENGINE=InnoDB AUTO_INCREMENT=2 DEFAULT CHARSET=utf8;

Edit 3:

EXPLAIN SELECT company_id = '1', status = 'tmp', remote_id = '12345', name_last = 'DOE', name_first = 'JOHN', sex = 'M', dob = '1980-01-01 00:00:00', mtime = '2014-07-11 14:16:07', ctime = '2014-07-10 23:00:27' FROM person WHERE id = '2693633'\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: person
         type: const
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: const
         rows: 1
        Extra: 
1 row in set (0.00 sec)

Edit 4:

Also, two more details that might be important:

• Queries like this (with different values) probably get executed 10-15 times per second. Most don't show up in the slow query log.
• We have a bug/feature (not honestly sure which yet) where the exact same update gets executed in quick succession over a short (e.g. 30-second) period. Maybe once per second during that time.