Improving select query
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.