certo che è fattibile, l'ho visto su un sito dove facevano una demo di AJAX ...

Mentre si scriveva la parola da cercare con AJAX si faceva una query in background per proporre le combinazioni trovate che cominciano con quanto si sta digitando.