Илья

Такой вариант работает?

SELECT `id`, `country_id`, `title` FROM `country_regions` WHERE `country_id` IN ('3', '1') LIMIT 1

Полнотекстовый поиск наверное лучше (не точно).
---
Индекы помогут несомненно, но я думаю они уже заданы, без них было бы дольше 4 секунд. Какие вообще индексы заданы в таблицах?

Ну по сути, не меняя архитектуру оптимизировать можно только играясь с индексами. Следовательно посмотрите какие запросы у вас используются (какие поля при фильтре используются) и делайте для них оптимальные индексы.

Например, если у вас есть фильтр по жанру, году и альбому, то у вас должен быть запрос:
... WHERE жанр = "" AND год = "" AND альбом = ""
и соответствующий индекс:
CRAETE INDEX ... ON tabl(жанр, год, альбом)
И обратите внимание, что порядок важен, поэтому все запросы у вас должны иметь строго указаный в индексе порядок!
... WHERE год = "" AND жанр = "" AND альбом = ""
Такой запрос будет использовать только часть индекса.

Ну и прочие тонкости почитайте про индексы, на самом деле интересная задачка)