Your point about search being a bottleneck is spot on. IMO, search APIs should return guidance to agents to help them winnow down the results faster. For example, if your query returns 1000 results, then it should tell the agent, "too many results, we recommend you filter on column X because of Y to improve your search. Here are the possible values in column X: ..."
There are a lot of APIs like this that I really wish would expose downloading a parquet file instead of trying to implement server-side filtering and reporting query features.