join on indexed fields doesn't utilize indexes

Question

I've got two tables. I've written a query to JOIN them on one column. This column is indexed in both tables, but MySQL is not using the indexes. Can someone a) tell me why and b) tell me how I might get MySQL use an index to join these tables quickly.

First table:

CREATE TABLE `dol_msa_zip_assoc` (
  `pkey` int(5) unsigned NOT NULL AUTO_INCREMENT,
  `zip` varchar(5) NOT NULL DEFAULT '',
  `pmsa_msa` varchar(5) NOT NULL DEFAULT '',
  PRIMARY KEY (`pkey`),
  KEY `zip` (`zip`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8;

It contains 42690 records.

The other table:

CREATE TABLE `v3_msa_zip_assoc` (
  `pkey` int(5) unsigned NOT NULL AUTO_INCREMENT,
  `zip` varchar(9) NOT NULL DEFAULT '',
  `pmsa_msa` varchar(6) NOT NULL DEFAULT '',
  PRIMARY KEY (`pkey`),
  KEY `zip` (`zip`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1;

it contains 42486 records.

My query, intended to find records in the first table not in the second:

SELECT d.*, o.* FROM `dol_msa_zip_assoc` d
LEFT JOIN `v3_msa_zip_assoc` o
ON o.zip = d.zip
WHERE o.zip IS NULL

When I EXPLAIN this query, I see that the indexes on the zip column are not being used:

+----+-------------+-------+------+---------------+------+---------+------+-------+----------------------------------------------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows  | Extra                                                          |
+----+-------------+-------+------+---------------+------+---------+------+-------+----------------------------------------------------------------+
|  1 | SIMPLE      | d     | ALL  | NULL          | NULL | NULL    | NULL | 42915 | NULL                                                           |
|  1 | SIMPLE      | o     | ALL  | NULL          | NULL | NULL    | NULL | 42486 | Using where; Not exists; Using join buffer (Block Nested Loop) |
+----+-------------+-------+------+---------------+------+---------+------+-------+----------------------------------------------------------------+

What might be causing this failure to use the indexes? Is it because one zip column is latin1 and the other utf8? How can I get this query to utilize the indexes so it doesn't take an age to run?

EDIT: reversing the order of the JOIN apparently does make use of the index:

SELECT d . * , o . *
FROM `v3_msa_zip_assoc` o
LEFT JOIN `dol_msa_zip_assoc` d ON d.zip = o.zip
WHERE d.zip IS NULL

Here's the explain:

+----+-------------+-------+------+---------------+------+---------+------+-------+-------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows  | Extra                   |
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------------------+
|  1 | SIMPLE      | o     | ALL  | NULL          | NULL | NULL    | NULL | 42486 | NULL                    |
|  1 | SIMPLE      | d     | ref  | zip           | zip  | 17      | func |     1 | Using where; Not exists |
+----+-------------+-------+------+---------------+------+---------+------+-------+-------------------------+

EDIT 2: I have changed the structure of the old table to use utf8 collations. It is now defined thusly:

CREATE TABLE `v3_msa_zip_assoc` (
  `pkey` int(5) unsigned NOT NULL AUTO_INCREMENT,
  `zip` varchar(9) NOT NULL DEFAULT '',
  `pmsa_msa` varchar(6) NOT NULL DEFAULT '',
  PRIMARY KEY (`pkey`),
  KEY `zip` (`zip`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8;

This appears to have remedied the problem:

mysql> EXPLAIN SELECT d . * , o . *
    -> FROM `dol_msa_zip_assoc` d
    -> LEFT JOIN `v3_msa_zip_assoc` o ON o.zip = d.zip
    -> WHERE o.zip IS NULL;
+----+-------------+-------+------+---------------+------+---------+---------------------+-------+-------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref                 | rows  | Extra                   |
+----+-------------+-------+------+---------------+------+---------+---------------------+-------+-------------------------+
|  1 | SIMPLE      | d     | ALL  | NULL          | NULL | NULL    | NULL                | 42915 | NULL                    |
|  1 | SIMPLE      | o     | ref  | zip           | zip  | 29      | myplan_v4_dev.d.zip |     1 | Using where; Not exists |
+----+-------------+-------+------+---------------+------+---------+---------------------+-------+-------------------------+

Answer 1

It's the characterset that's preventing the use of the index.

One of the zip columns is latin1, the other is utf8.

There's an implicit conversion, equivalent to CONVERT(zip USING charset) on one side,