In 5.5, in order to be in line with InnoDB, we changed the way we declare char and varchar. It used to be declarations of length were in bytes, now length is declared in number of characters. This means that a varchar(5) declared as UTF will create a field with max length of 15 (3 being the largest number of bytes for a UTF character). The largest number of bytes that can currently be stored in the data file of a varchar is 7 (1st byte is length). So the ZIP varchar(5) becomes a dictionary field. Dictionary fields cannot currently be used in extent elimination, so it requires a full scan.

In the future we hope to implement 16 byte char data files (15 usable bytes for varchar), which means this particular definition would again participate in extent elimination. In addition we are working on a design to allow dictionary columns to participate in extent elimination. However, neither of these efforts has been scheduled.

There are two workarounds:
1) declare the field as a numeric type. In all cases, if a choice to declare a field as numeric is possible, it should be done:
`ZIP` int NOT NULL,
2) if it is impossible to declare the field as numeric, but it can be declared as latin1, it should be done. Better yet, declare it with collate latin1_bin:
`ZIP` varchar(5) character set 'latin1' COLLATE latin1_bin NOT NULL,

When used in a WHERE clause. numeric fields are significantly faster than character fields, even when those character fields can participate in extent elimination.

This depends on 4529, which will be 6.1.1 at best...

In 5.5.2 the situation is improved due to 4527, which restores the performance for latin1 charsets at least. utf8 series require more work.

Tested in 5.5.2 GA, with latin1. extent elimination of character columns in utf8 needs to wait for 6.1.1