Balancing server/client load for autocompletion search

To preface, I'm working with Google App Engine which does开发者_JAVA百科 not allow JOINS or Full Text Search.

Problem: I'm trying to build an autocompletion search bar (like Google Instant Search). For the purpose of explaining, assume that each entry in the database is a big string with no spaces. If I type in "cr", I get an autocompletion assist with all the strings that begin with "cr". I figured out a way to achieve this search in Google App Engine but it seems like a horrible idea to POST a query to the server everytime a key is pressed in the input search bar.

I'm thinking that a combination of client side and server side caching could help do this efficiently? Anybody have any ideas? Or just tips on best practices? Thanks.

---

Maybe you could do something like "request a max of 50 options" every time a key is pressed or every 1 second, whichever is less frequent. I think a series of post requests would be a good solution.

On the server, you should expect multiple related queries, so even though you're only sending 50 at a time to the client, you could cache 1000 results and benefit if the next query takes you to a subset of those results.

---

There's really no way around doing frequent queries to the server - either every keypress, or after a slight pause. You could refine this a bit by having the server send not only the suggestions for the current string, but also for what it thinks are the most likely next characters, enabling the client to avoid the need for a query in some cases. Your main focus should probably be on making sure the server end of this is fast and efficient, though.