Description:
For table
CREATE TABLE `sbtest` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `k` int(10) unsigned NOT NULL DEFAULT '0',
  `c` char(120) NOT NULL DEFAULT '',
  `pad` char(60) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`),
  KEY `k` (`k`)
) ENGINE=InnoDB AUTO_INCREMENT=100000001 DEFAULT CHARSET=latin1
with 100000000 records
MySQL 5.5.4 shows different execution plan then MySQL 5.1.48 with InnoDB-plugin.
For 5.1:
explain select avg(id) from sbtest;
+----+-------------+--------+-------+---------------+------+---------+------+-----------+-------------+
| id | select_type | table  | type  | possible_keys | key  | key_len | ref  | rows      | Extra       |
+----+-------------+--------+-------+---------------+------+---------+------+-----------+-------------+
|  1 | SIMPLE      | sbtest | index | NULL          | k    | 4       | NULL | 100000081 | Using index | 
+----+-------------+--------+-------+---------------+------+---------+------+-----------+-------------+
1 row in set (0.00 sec)
For 5.5.4:
explain select avg(id) from sbtest;
+----+-------------+--------+-------+---------------+---------+---------+------+-----------+-------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows      | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+-----------+-------------+
|  1 | SIMPLE      | sbtest | index | NULL          | PRIMARY | 4       | NULL | 100000081 | Using index | 
+----+-------------+--------+-------+---------------+---------+---------+------+-----------+-------------+
1 row in set (0.00 sec)
On cold the second execution plan is 2x slower.
in 5.1:
30 sec
in 5.5.4:
1 min 1 sec
How to repeat:
create table
CREATE TABLE `sbtest` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `k` int(10) unsigned NOT NULL DEFAULT '0',
  `c` char(120) NOT NULL DEFAULT '',
  `pad` char(60) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`),
  KEY `k` (`k`)
) ENGINE=InnoDB AUTO_INCREMENT=100000001 DEFAULT CHARSET=latin1
populate with
sysbench --test=oltp --oltp-table-size=100000000 prepare
check EXPLAIN