MySQL query very slow for one object, very fast for others

Question

I have a table for Items and then a table for Parameters where each Item can have multiple Parameters. Each Parameter object has a foreign key back to its Item. I also have a Parameter Type table that stores the possible types of Parameters.

Here is the table info for my Parameter table:

CREATE TABLE 'parameter' (
  'id' int(11) NOT NULL AUTO_INCREMENT,
  'type_id' int(11) NOT NULL,
  'value' longtext NOT NULL,
  'item_id' int(11) NOT NULL,
  PRIMARY KEY ('id'),
  KEY 'parameter_403d8ff3' ('type_id'),
  KEY 'parameter_0a47aae8' ('item_id'),
  CONSTRAINT 'item_id_refs_id_eeb3b028' FOREIGN KEY ('item_id') REFERENCES 'tracker_item' ('id'),
  CONSTRAINT 'type_id_refs_id_53b2638a' FOREIGN KEY ('type_id') REFERENCES 'parametertype' ('id'),
) ENGINE=InnoDB AUTO_INCREMENT=31445609 DEFAULT CHARSET=utf8;

And here is my Parameter Type table:

CREATE TABLE 'parametertype' (
  'id' int(11) NOT NULL AUTO_INCREMENT,
  'name' varchar(60) NOT NULL,
  PRIMARY KEY ('id'),
  UNIQUE KEY 'name' ('name'),
) ENGINE=InnoDB AUTO_INCREMENT=309 DEFAULT CHARSET=utf8;

I have two Items, IDs 115711 and 116792, for which I want to do this query:

SELECT p.`id`,
       p.`type_id`,
       p.`value`,
       p.`item_id`,
       p.`upload_id`,
       p.`creator_id`,
       p.`date_recorded`,
       p.`date_last_modified`,
       p.`date_added`
FROM parameter p
INNER JOIN parametertype pt ON p.`type_id` = pt.`id`
WHERE p.`item_id` = <ITEM_ID> 
  AND pt.`name` LIKE 'some_name' 
ORDER BY p.`date_recorded` DESC

When I do this for Item 116792, it takes 5.7ms. When I do it for Item 115711, it takes 9 SECONDS. The EXPLAIN of each query is the same except for the "ref" column -- for the fast query, it shows const in that column for the parameter table entry, where as for the slow query, it shows parametertype.id. Also, in the key column. The slow query shows data_parameter_403d8ff3 there (the key for the Parameter Type table) whereas the fast query shows data_parameter_0a47aae8 there (the key for the Item table).

What does this mean and why is one so slow? Is there anything I can do to make it as fast as the other query?

For context, Item 116792 has 560 Parameter entries and Item 115711 has 823 Parameter entries. The Parameter Type table has 237 entries.

The full EXPLAIN query for Item 116792:

    +----+-------------+--------------------+-------+-------------------------------------------------+-------------------------+---------+-------+------+-----------------------------------------------------------+
    | id | select_type | table              | type  | possible_keys                                   | key                     | key_len | ref   | rows | Extra                                                     |
    +----+-------------+--------------------+-------+-------------------------------------------------+-------------------------+---------+-------+------+-----------------------------------------------------------+
    |  1 | SIMPLE      | parametertype      | range | PRIMARY,name                                    | name                    | 182     | NULL  |    1 | Using where; Using index; Using temporary; Using filesort |
    |  1 | SIMPLE      | parameter          | ref   | parameter_403d8ff3,parameter_0a47aae8           | parameter_0a47aae8      | 4       | const |  559 | Using where                                               |
    +----+-------------+--------------------+-------+-------------------------------------------------+-------------------------+---------+-------+------+-----------------------------------------------------------+

The full EXPLAIN query for Item 115711:

    +----+-------------+--------------------+-------+-------------------------------------------------+-------------------------+---------+-------------------------------+------+-----------------------------------------------------------+
    | id | select_type | table              | type  | possible_keys                                   | key                     | key_len | ref                           | rows | Extra                                                     |
    +----+-------------+--------------------+-------+-------------------------------------------------+-------------------------+---------+-------------------------------+------+-----------------------------------------------------------+
    |  1 | SIMPLE      | parametertype      | range | PRIMARY,name                                    | name                    | 182     | NULL                          |    1 | Using where; Using index; Using temporary; Using filesort |
    |  1 | SIMPLE      | parameter          | ref   | parameter_403d8ff3,parameter_0a47aae8           | parameter_403d8ff3      | 4       | parametertype.id              |  676 | Using where                                               |
    +----+-------------+--------------------+-------+-------------------------------------------------+-------------------------+---------+-------------------------------+------+-----------------------------------------------------------+

Answer 1

ALTER TABLE parameter ADD INDEX(item_id, date_recorded)

Please provide EXPLAIN SELECT ... for both the slow and fast queries.