Most searching these days is incremental (e.g. one letter is typed and added to the search term at a time).
Search.query() is enhanced to maintain state from the prior
queryResult (but really just row/col indexes), then each subsequence search would not need to search all cells, just the ones from the prior search.
Example: searching for "fo" followed by typing another 'o' to get "foo" would, by definition, mean that any "foo" results are a subset of "fo".
As it stands now, the complexity is always
rows*columns and as more letters are typed, the slower it gets instead of faster.
Clearing a search should be faster and maybe even a separate call. With caching incremental searches, the only cells that need to be cleared are the ones last matched.
Clear() would be called when a incremental search hits a combo breaker.
Bonus speedup: because of the typing behavior, most users might mistakenly type one letter (e.g when looking for foobar, they type "food" vs "foob"). They would then delete one character after the typo. So, "food" becomes "foo". If the search results of "foo" are cached in a history, then it's an instance result set lookup.