Claro, como te comenta LordKanabis La solucion esta en los indices, aunque deben de usarse con prudencia si la insercion en la tabla es muy frecuente y tienes demaciados indices ya que se hace lenta la insercion, no creo que en este caso se afecte demaciando con esos indices propuestos
Tambien evita en lo posible el uso de Parentesis en las condiciones where salvo que sean muy necesarios, ya que esto tambien hace lenta las consulta, y ni hablar del Order By ...
Saludos