MySQL UPDATE primary key query is sometimes extremely slow

Question

The special UPDATE query on our website sometimes runs very slowly and checks a lot more lines than necessary. It filters the primary key, so I would expect MySQL to always just need to examine a single row.

Here are some examples from the MySQL slow query log:

# Time: 090702 12:59:06
# User@Host: XXX[XXX] @ XXX [XXX]
# Query_time: 21  Lock_time: 0  Rows_sent: 0  Rows_examined: 500500
SET timestamp=1246532346;
UPDATE `folders` SET `folder_id` = '1705641', `updated_at` = now() WHERE `folders`.`id` = '1682995';
# Time: 090702 14:13:44
# User@Host: XXX[XXX] @ XXX [XXX]
# Query_time: 17  Lock_time: 0  Rows_sent: 0  Rows_examined: 16816745
SET timestamp=1246536824;
UPDATE `folders` SET `folder_id` = '417997', `updated_at` = now() WHERE `folders`.`id` = '1705956';
# Time: 090702 14:15:42
# User@Host: XXX[XXX] @ XXX [XXX]
# Query_time: 13  Lock_time: 0  Rows_sent: 0  Rows_examined: 16816719
SET timestamp=1246536942;
UPDATE `folders` SET `folder_id` = '1706267', `updated_at` = now() WHERE `folders`.`id` = '1705956';
# Time: 090702 16:07:43
# User@Host: XXX[XXX] @ XXX [XXX]
# Query_time: 499  Lock_time: 0  Rows_sent: 0  Rows_examined: 88668449
SET timestamp=1246543663;
UPDATE `folders` SET `folder_id` = '1707407', `updated_at` = now() WHERE `folders`.`id` = '1706992';

A query is executed more often than this, so it does not always reveal this behavior. Also, if I run the same queries manually, they run just fine and immediately return.

I also checked the table, and as far as I can see, this should be fine:

mysql> describe folders;
+------------------+-----------------------+------+-----+---------------------+----------------+
| Field            | Type                  | Null | Key | Default             | Extra          |
+------------------+-----------------------+------+-----+---------------------+----------------+
| id               | mediumint(8) unsigned | NO   | PRI | NULL                | auto_increment | 
| user_id          | mediumint(8) unsigned | NO   | MUL | NULL                |                | 
| folder_id        | mediumint(8) unsigned | YES  | MUL | NULL                |                | 
| created_at       | timestamp             | NO   |     | CURRENT_TIMESTAMP   |                | 
| updated_at       | timestamp             | NO   |     | 0000-00-00 00:00:00 |                | 
| modified_at      | timestamp             | NO   |     | 0000-00-00 00:00:00 |                | 
| name             | varchar(255)          | NO   |     | NULL                |                | 
| guest_permission | tinyint(3) unsigned   | NO   |     | 1                   |                | 
+------------------+-----------------------+------+-----+---------------------+----------------+
8 rows in set (0.00 sec)

mysql> show index from folders;
+---------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| Table   | Non_unique | Key_name  | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
+---------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
| folders |          0 | PRIMARY   |            1 | id          | A         |      760318 |     NULL | NULL   |      | BTREE      |         | 
| folders |          1 | user_id   |            1 | user_id     | A         |       69119 |     NULL | NULL   |      | BTREE      |         | 
| folders |          1 | folder_id |            1 | folder_id   | A         |      380159 |     NULL | NULL   | YES  | BTREE      |         | 
+---------+------------+-----------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+
3 rows in set (0.00 sec)

, MySQL , , , . , MySQL .

- , , , ?

EDIT: MySQL 5.0.51a 6 -, PHP 5.2.6 PDO MySQL. Debian Lenny. -.

EDIT: EXPLAIN :

mysql> explain SELECT * FROM `folders` WHERE `folders`.`id` = '1682995';
+----+-------------+---------+-------+---------------+---------+---------+-------+------+-------+
| id | select_type | table   | type  | possible_keys | key     | key_len | ref   | rows | Extra |
+----+-------------+---------+-------+---------------+---------+---------+-------+------+-------+
|  1 | SIMPLE      | folders | const | PRIMARY       | PRIMARY | 3       | const |    1 |       | 
+----+-------------+---------+-------+---------------+---------+---------+-------+------+-------+
1 row in set (0.00 sec)

mysql> explain SELECT * FROM `folders` WHERE `folders`.`id` = 1682995;
+----+-------------+---------+-------+---------------+---------+---------+-------+------+-------+
| id | select_type | table   | type  | possible_keys | key     | key_len | ref   | rows | Extra |
+----+-------------+---------+-------+---------------+---------+---------+-------+------+-------+
|  1 | SIMPLE      | folders | const | PRIMARY       | PRIMARY | 3       | const |    1 |       | 
+----+-------------+---------+-------+---------------+---------+---------+-------+------+-------+
1 row in set (0.00 sec)

Answer 1

. , folders , , , , ...

tree, , , . UPDATE , . DELETE :

DELETE FROM `tree`
  WHERE `folder_id` IN (
    SELECT `folder_id` FROM `children`
  )
  AND ...

children - , . - MySQL , RIGHT JOIN, :

DELETE `tree`.* FROM `tree`
  RIGHT JOIN children USING (folder_id)
  WHERE ...

, MySQL , MySQL.

Answer 2

, , , id int, (). , .

, , SELECT WHERE EXPLAIN. :

EXPLAIN SELECT * FROM `folders` WHERE `folders`.`id` = '1682995';
EXPLAIN SELECT * FROM `folders` WHERE `folders`.`id` = 1682995;

, .

EXPLAIN.