You could perhaps fix it by trying to use some index hints in the query to get a bit more consistency, see https://dev.mysql.com/doc/refman/8.0/en/index-hints.html
https://dom.as/2015/07/30/on-order-by-optimization/ - Wisdom from the guy who managed to get MySQL to work at facebook scale.