solución óptima: ¿1 query grande o varias peques?

[Eux]

Buenas,

Tengo una bbddd de unos 40.000 usuarios, y estoy implementando la utilidad de verificar si el nombre de usuario ya existe mientras el usuario esta rellenando en el formulario la casilla "username" para los nuevos usuarios.

Mi dilema es: (sabiendo que el username debe ser igual o más que dos caracateres

1º solución:
yo tenía previsto hacerlo recuperando toda la columna username (los 40.000) y a partir de allí me olvido de la bbdd e iría comparando a partir de la segunda letra si ese usuario existe o no, con lo que la carga fuerte de bbdd sólo sería al principio.

2º solución:
La otra solución sería hacer una query a partir de la segunda letra para cada letra que introduce el usuario para ver si esa cadena existe en la bbdd en la columna username. Aquí no haces carga fuerte pero hacer muuchas pequeñas.

¿QUÉ SOLUCIÓN CREÉIS QUE ES MÁS ÓPTIMA?

Gracias a tod@s.