Составьте индекс, который бы делал эффективной следующую выборку (индекс должен учитывать все поля):
SELECT * FROM my_table
WHERE country = X AND date > D1 AND date < D2 AND city = Y
Вы хотя бы структуру таблицы привели чтоли.
Общее правило - конкретно указываемые части помещаются спереди, при чем так, чтобы вначале шли части с максимальным сужением области поиска. В конец можно добавить одну диапазонную.