How to design a user table with 1 mio entries

Hi there, I am having a search engine on á user table. It works fine for a few users. But I asume that it is gonna be realy slow for 1 Million entries. That because I have all parameters in on table and I am doing to select stmt on it. The first one gets all users for storing the ranking, the other one gets as many as fit on one site. How could I improve performance? Splitting into different tables? How would this look like. I am pretty knew on db design and guess there is a better way. Can anybody help who has more knowledge about db design than I have? Thanx for any help cheers guys and girls, Andy