Чтобы MySQL лучше оптимизировал запросы, можно выполнить myisamchk --analyze для таблицы после того, как она загружена соответствующими данными. Таким образом для каждой части индекса будет обновлено значение, указывающее среднее число строк, имеющих одинаковые значения (для уникальных индексов это всегда 1, разумеется). MySQL будет использовать это число, чтобы решить, какой индекс следует выбрать для связывания двух таблиц при помощи "неконстантного выражения". Результат работы analyze можно увидеть в столбце Cardinality после выполнения команды SHOW INDEX FROM имя_таблицы.

Чтобы отсортировать индекс и данные в соответствии с индексом, используйте myisamchk --sort-index --sort-records=1 (если нужно отсортировать по индексу 1). Если имеется уникальный индекс, по которому вы хотите считывать все записи в порядке, соответствующем данному индексу, это - хороший способ ускорить считывание записей. Обратите внимание, однако, что эта сортировка написана не оптимально и для большой таблицы будет выполняться долго!