Search Speed Issues

I have seen this mentioned in passing in a few locations including the Google Dev Group and in old threads on this board, but wanted to ask specifically if anyone else has had issues with speed on advanced searches in large databases?

Also, of particular concerns is the speed of large searches. I was attempting to find a way to return a large number of items and allow users to filter the results with a simple AJAX script; however, there is significant slowness in performing the initial search.

I was wondering if anyone else has ran up against the issue of slow searches or had some ideas for mitigation?

(PS, I have also attempted to resolve this by using a combination of the sort plugin and HTML links to advanced search queries instead rather than the AJAX, but run up against similar speed issues as a result of the slow advanced search)