Alternativas para agilizar consulta...

Que tal Sres. tengo una tabla de aprox 5 millones de reg. y en dicha tabla
existe un campo 'codnivel' Char(20). Ejem: 020103050705.. Los 2
primeros(02), los 2 siguientes (01) y asi sucesivamente tienen un
significado. Ahora el campo tiene su indice y debo extraer informacion de
cualquier lugar de la cadena. Ejem:

Caso 1:
SELECT <campos>
FROM mytabla
WHERE LEFT(codnivel,2) IN ('01','02','03'..) --Esta consulta es lentisimo
<Ahora si lo cambio por (codnivel LIKE '01%' Or codnivel LIKE '02') y
asi..>
se agilizar 3 veces puesto que si hace uso del indice. Pero aun asi siento
que es lento. He probado con los operadores y funciones conocidas pero no
logro agilizarlo masalguna sugerencia ???

Caso 2 (el mas usado)
SELECT <campos>
FROM mytabla
WHERE SUBSTRING(codnivel,5,2) IN ('03','04','07'...) --Esto es mas lento
todavia
<Aqui no tengo idea de como cambiarlo para que haga uso del indice>

Si hago uso del LEFT, SUBSTRING, IN ú otras funciones, la consulta es
lenta
porque me parece que no hace uso del indice. Pero si utilizo el campo solo
sin nada que lo envuelva entonces es una bala la consulta. ¿Algunas
alternativas de como extraer la informacion de forma rapida ?..gracias.