Because you are filtering on an associated entity, the database server already has indexed these two tables and the relationship between them. For this reason, the fastest way to get this information is with a database retrieve. When you have a large number of records, database retrieves are always faster than list operations.
If you want to do this with a list operation, I would recommend finding the Status object that meets your search criteria and then filter on the association using that object (if you find a number of status objects, you may get better performance by doing individual filters and using a Union actions to get a final list.