А все это началось при переезде с mysql 5.7 на percona server 5.7. До переезда этот запрос был мнгновенным, а теперь стал тормозить.
Простите за сарказм, "но это же MySQL, чего вы ожидали?". Одной из особенностей данной БД является довольно "топорный" оптимизатор запросов (если его можно так назвать), который не всегда корректно может определить, какой именно индекс следует использовать. Конечно, не корректность определения "оптимального" индекса - это проблема не только MySQL, но и других БД... но, как-то уж очень слабо в MySQL (и его производных) пытаются с этим бороться. Так же проблему усугубляет тот факт, что MySQL может использовать только 1 индекс на запрос + некоторые другие факторы.
"Что с этим делать?" - сказать сложно, вряд ли в обозримом будущем, Вам (или разработчикам MySQL или других БД) удастся решить эту проблему целиком и полностью, но конкретно в Вашем случае, из личного опыта, могу предположить, что наиболее оптимальным решением будет
"тыкать пальцем, какой именно индекс использовать" ну и отслеживать/отлаживать/корректировать подобные запросы в будущем.
Так же, хочу обратить Ваше внимание, что проблема тут скорее всего не в "Percona" как таковой, и MySQL и MariaDB и т.д., не редко грешат подобными вещами, при относительно больших объёмах данных.