Mysql: Я дурак или виноват хостер?

Вкратце: перенес бд от одного хостера к другому, работать перестало.

Итак, есть бд, в ней три таблицы: "города", "регионы РФ" и таблица соответствия "город-регион". выглядит это так:

[city (города)]

id_city | citynicename | cityname

27419 Dmitrov Дмитров

27613 Domodedovo Домодедово

27626 Zhukovskij Жуковский

27602 Zelenograd Зеленоград

27514 Sheremetevo Шереметьево

27726 Jelektrostal Электросталь

27439 Jelektrougli Электроугли

27418 Jahroma Яхрома

27612 Moscow Москва

[region (регионы)]

id_region | regionname

50 Московская область

77 г. Москва

[region2city (таблица-связка)]

id_region | id_city

50 27419

50 27613

50 27626

50 27602

50 27514

50 27726

50 27439

50 27418

77 27612

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

Zelenograd -> 27602 Зеленоград 50 Московская область

Получившийся SELECT у меня выглядит так:

SELECT city.id_city, city.cityname, region.id_region, region.regionname FROM `city`, `region`, `region2city` WHERE city.id_city = region2city.id_city AND region.id_region = region2city.id_region AND city.citynicename = 'Zelenograd'

Это все работает, но только на тестовой базе (вот эти 9 городов что я привел в примере выше). Когда городов становится около полутора тысяч на новом хостинге (на старом все работало нормально) мускул ругается на:

#1104 - The SELECT would examine more than MAX_JOIN_SIZE rows; check your WHERE and use SET SQL_BIG_SELECTS=1 or SET SQL_MAX_JOIN_SIZE=# if the SELECT is okay

Хостер утверждает что MAX_JOIN_SIZE у него 10млн., никто никогда не жаловался, проблема на моей стороне, и предлагает оптимизировать запрос к бд. Я в свою очередь не понимаю как оптимизировать запрос который и так проще некуда. Рассудите, пожалуйста, это я не прав и запрос плох и его надо переписывать, или хостер чего-то не договаривает и нужно переезжать к другому?