440-му в аське я уже писал, но, думаю, и остальным может быть интересно:
Посмотрел на SQL файл.
Я бы сущностям таки авто-инкременты раздал, соответственно их и юзал бы для внутренних целей. А снаружи пусть видны фэйковые id varchar16. А то лично у меня на mysql 4.0.20c была такая штука, что не могли быть использованы индексы при джоинах по varchar полям, соответстенно шел фулскан 300,000 * 300,000 * 200,000 * 120,000 записей.
Или можно заменить индексы с varchar16 на неавтинкрементный mediumint, с рандомными значениями. Эффект тоже будет положительный.