LantameОчень странные результаты выходят.
При удалении/уменьшении размера индекса и SELECT и INSERT выполняются дольше.
Добавление ID в индекс стабилизирует время INSERT'a.
Выходит где-то 0.5мс на запрос в пустой таблице.
В полной (~10M) SELECT за столько же, INSERT деградирует до 0.8мс примерно.
Отличия MyISAM от InnoDB в пределах погрешности.

Том Кайт как то сказал что самый быстрый
запрос -- это то который НЕ НАДО делать.
Т.е. самый лучшая оптимизация -- оптимизация процесса и
логики -- которая бы позволила (бы) сократить или
даже избежать какихто действий/запросов.

как вариант:

1. есть ли у вас какой-нибудь другий глобальный идентификатор
известный до вставки?
(таймпстамп и апацче лог ид? ГУИД ?)
Если есть то можно избежать
селекта после вставки вообше. а все связки делать по
заранее извесному идентификатору.

2. протестировали ли вы ЛАСТ_ИНСЕРТ_ИД идею --
опять же в избежании ре-селекта?

3. Какие другие селекты будут по этой таблице?
если индекс нужен ТОЛЬКО для единственого селекта то
и индекс не нужен.

4. Какой разнер реальной боевой базы?
может имеет смысл все в память загрузить?
типа табле тайп МЕМОРИ...
или мемкаше -- как уже предлагали.

ScareCrowавтор1. есть ли у вас какой-нибудь другий глобальный идентификатор
известный до вставки?
http://dev.mysql.com/doc/refman/5.5/en/information-functions.html#function_last-insert-id
http://dev.mysql.com/doc/refman/5.5/en/mysql-insert-id.html

это хорошая идея, само собой... вы уже предлагали это выше и
ТС пока не среагировал.

Использование (если есть!) заранее извесного глобального идентификатора
может убрать даже ЛАСТ_ИНСЕРТ_ИД запрос.

LantameИдентификаторы нужны для декомпозиции на отдельные таблицы.
Вы неправильно поняли, SELECT и INSERT выполняются в разные моменты времени. Т.е. сначала надо что-то сохранить в базу данных, в таблицы A, B, C, а потом эта сохраненная информация, в виде ID, выступает как критерий для выборки другой информации.

Table Useful:
ID,
A_ID,
B_ID,
C_ID,
Some_useful_info.

SELECT Some_useful_info FROM Useful Where A_ID = (SELECT ...) AND B_ID = (SELECT ...) ...;

В каком смысле выложить базу? Команды создания, или собственно файлы?

Идентификаторов нет, они служат только для ориентации в БД.

Размер базы - неизвестен. Но вполне возможно, что войдет в память. Надо будет протестировать.

Селекты могут быть, а могут и не быть. По сути, данная база служит для сохранения отладочной информации: будет ошибка - извлечем, не будет - пусть валяется.

тогда не делайте индекса --- мешает на вставке.

А как понадобится -- возьмете копию и создадите индекс за секунды / минуту.