Pa da, sa autocomplete-om treba povesti računa u smislu broja i učestalosti tih zahteva za pretragu. Ali mislim da tu više pažnje treba posvetiti optimizacijama na serverskoj strani, u smislu struktuiranja samog indeksa, keširanja, itd. Naravno, i na klijentu bi trebalo odrediti te pragove, u vidu broja unetih karaktera nakon kojih će biti "okinuta" pretraga, pa i nekim keširanjem server-side rezultata, za pojmove koje unosi korisnik. Što se rešenja na klijentskoj strani tiče, preporučujem ti da ideš sa
jQuery UI Autocomplete.