Query a name in large database, optimizations?
I understand the feeling that 1mil+ rows is "Very Large", however you should understand that to a lot of database people you aren't getting into a large table until you have 10s-100s of millions of rows.  And even then that is middling large.  

That being said if I understand what you are asking for you are looking for "indexes".  This is a fairly large concept at times and what index(s) you need really depends on what queries you are running.  

I can think of two major categories though that might match what you are looking for.  The first is simple.  You have the name in a column and you want to search the table for everyone with a given name.  For example you are looking for everyone with the name Ken and you have a query like this.

SELECT * FROM TableName WHERE NameColumn = 'Ken'


or you want to get everyone's name that starts with Ken and your query looks like this.

SELECT * FROM TableName WHERE NameColumn LIKE 'Ken%'


In this case a simple index on the NameColumn column of your table will suffice and should give you excellent performance.

If however you want to search for Bob and get everyone who has names such as Bobbie, Robert, Rob etc.  Then I believe you want full text indexing.  This is a bit more complicated and has a number of requirements to set up.  If this is what you need then I suggest either having an in house DBA do the work (someone familiar with full text indexing) or do some research yourself.  For example for SQL Server 2012 the BOL entry is Here.

I'm a SQL Server person so my answers are going to bias that way but in all of the RDBMS' that I know of indexing in one form or another is how you improve basic performance of a well written query on a well designed system.  If you need help with the design of the query or system then you will have to provide a great deal more information starting with which RDBMS you are using and your table structure and the query you are trying to optimize.