Not really. Just use what you know. If you know prototype over jQuery, there are Prototype solutions. If you know Dojo or MooTools, I'm sure there are solutions for those too. If you don't know any, I'd suggest Prototype only because I've used jQuery and the only thing it has over Prototype is the UI stuff (although Script.aculo.us is helping catch Prototype up).
As for a well indexed database, I mean ... a well indexed database. Your data is normalized, it's a quick search, and results don't take any more than a couple seconds to come back. If you have to wait 10 seconds for a result to come back, then perhaps you should rethink using AJAX and instead use something else, or drop-it all together.
Another option is to cache the searches that are run and the number of results that they create. Then use only that table to display a popular search and the approximate number of results it will return. Something like what Magento does by default.