Xeenon

В MariaDB 10.0 есть очень интересная фича engine independent table statistics.

Может помочь.
Но тут сильно зависит от данных (как часто обновляются, какая сardinality) и запроса (сколько в запросе используется таблиц и т.п.).