Оптимизация базы данных складывается из целого ряда рецептов, начиная с типа/структуры таблицы и заканчивая оптимизацией самого запроса. Не имея информации, как у тебя там все устроено, можно лишь порекомендовать доки вдоль и поперек по ключевым моментам:
http://mysql.ru/docs/man/Table_types.html
http://mysql.ru/docs/man/Column_types.html
http://mysql.ru/docs/man/MySQL_Optimisation.html
и т.д.