Improving select query I was at an interview for a new job today and got asked a question regarding a SELECT query:

SELECT lastname FROM users WHERE name='John';


This SELECT query is to run over a million rows.

I was asked: How would you make that faster/more efficient?

I didn't have the answer, and some googling also didn't reveal anything to me.

I know the possibility of this question being closed is quite high, but I'd really like to know how you would make that query run faster. Any ideas?
The table may have a million or a billion or a trillion rows. The answer is the same:

Add an appropriate index on the columns used in the WHERE (and other clauses).

In this case, a simple index on (name) would be enough. Assuming that the number of rows that match the condition name = 'John' is small, say 0.1%, then the optimizer will use the index to find the matching rows and then read only those rows from the table (this is done with some additional lookups), to find the lastname values.

With a very large table, this may not be fast enough. If the percent of matching rows is 0.1% with a billion rows, that means a million rows with name = 'John' and a million lookups on the table. We can then have instead a "covering" index - on (name, lastname) - so we don't have to do the additional lookups on the table. Only the index will be used and the million values will be found with a simple index seek (and partial scan).

Response to your comment


  This is, as far as I can see, as simple as altering the table structure and just setting the name column to be an index. Correct?


Basically yes, with either ALTER TABLE ... ADD INDEX ... or CREATE INDEX ... The table structure doesn't really change, the index is an additional (physical) structure.