Khludev

Для примера count(*) также выполняется 14 секунд. И он не создает дополнительных временных таблиц,
select count(*) as aggregate
from `news`
inner join `news_rayon` on `news_rayon`.`news_id` = `news`.`id`
where `news_rayon`.`rayon_id` = 20
and `news`.`type` = 'news'

В EXPLAIN первой отображается таблица news_rayon, видимо она и берется первой.
Я скопировал полностью столбец news.public_date в news_rayon.public_date добавил его в индекс и сортировку order by news.public_date desc заменил на order by news_rayon.public_date desc. Запрос вместо 14 секунд, выполнился за 43мс.
Напомню что на сервере не postgrss, а mariadb