If you add an appropriate index, you won't be searching the entire table.

I suspect this is one of the interview questions where there's no right or wrong. They want to see if you can explain your design, the good, the bad, if you can see flaws, if you can see alternatives, if you can explain why you designed things in a specific way.

I used to like asking these kind of questions. Lets you see how a candidate thinks, whether they're confident in their work or whether they'll defer immediately to the interviewer, etc.