It's completely irrelevant how many rows the thing returns. It could well read half the DB to return no rows.

Don't just look at indexes (and indexing foreign key probably won't help unless there are updates or deletes that need to check the relationship). Analyse and tune the query/procedure.