Search users very slow

Also check your DB and tables to be sure all of them are running the same engine (recommendation is innoDB).

If (as @mapress888 said) you discover you got a lot of spam users, this post would be useful to you: