Запрос простейший, даже если миллиарды записей, выборка должна быть меньше секунды, так как индекс должен все решать. Вопрос к знатокам, почему планировщик не использует этот индекс, а должен же?
Потому что там был такой LEFT JOIN, для которого существенной пользы от индекса нет (планировщик очень редко занимается "исправлением ошибок" в запросах, вроде вывода того, что кто-то использовал LEFT вместо INNER).
С inner же всё получилось.