Optimize performance of members profile's

Hello,

I have issues with speed and performance of my MySQL Server, i have slow query's like this from member profiles:
Query select userid from user where username regexp

These query's appears when someone is trying to access to a member profile with special characters like dots, underscores, etc...

I know that this can be fixed adding the userid and this will prevent the full table-scan but i think that now is too late, the members profiles are indexed and i'm receiving traffic from searchs.

My question is if is possible add a mysql index on the usertable or something similar to help a bit this query.

Thanks

I'm pretty sure a regular expression, regardless of indexes, will perform a full table scan anyway.