Note: In this question I'm using the term "autocomplete" (or "iterative search") to refer to returning search-as-you-type results, e.g. like Google Search gives you. Also my question is not specific to web applications vs. fat client apps.

How are SQL SELECT queries normally constructed to provide decent performance for this type of query, especially over arbitrarily large data sets? In the case where the search will only query based on the first n characters (easiest case) am I still issuing a new SELECT result FROM sometable WHERE entry LIKE... on each keypress. Even with various forms of caching this seems like it might result in poor performance.

In cases where you want your search string to return results with prefix matches, substring matches, etc. it's an even more difficult problem. Looking at a case of searching a list of contacts, you might return results that match FirstName + LastName, LastName + FirstName, or any other substring.