Problema de índices

[chelsae]

Tengo un problema a la hora de presentar listados ya que según va creciendo la tabla se va ralentizando la respuesta.

La cuestión es que me está ignorando los índices, siempre realiza un recorrido, os pongo la consulta y los índices, a ver que se puede hacer:

SELECT * FROM tabla WHERE alta>$baja and codigo=$cod and activo=1

Hay un indice para alta, codigo y he probado de todo, alta y codigo sólos, alta, codigo y activo, vamos todas las posibilidades que se os ocurran y nada, explain me devuelve que hace el recorrido completo en busca de la selección, aparte que se nota como se engancha.
También he probado a forzar que use el índice y nada, debe ser que no le sirve para nada.

Imagino que el problema está en el mayor entre alta y baja que hace que el índice no le sirva, pero es que no se que hacer ya que no puedo evitar el uso de dicha comparación.