May be our definition of “reasonable” is a bit different. A search time of a minute does not fit into my definition if I need the search between 50 and 100 times on a normal working day. That would add up to waiting for 1 - 2 hours just to see the search result when I have search (and presentation) times in my database app with PostgreSQL under one second. So the benchmark should not be what you or I see on our systems but what is achievable with modern database backends. And a search in 600k rows is simply small change for those database backends and nothing a user should be forced to wait a minute.
But at the end of the day, I don’t have any clue. I know from other discussions that search times appear to vary in a very wide range without any recognizable rationale.