Перебор 65 строк таблицы не может быть медленне чем столь сложная выборка из 28959*3820=110623380 записей :)
В explain cервер вам тактично намекнул, что не хватает правильных сборных индекcов. Какие нужно - посмотрите порядок выполнения условий в select запросах.