The first method will appear to render results faster on the client side, but will lag each time the page load and the [unlimited] query runs.
You could use AJAX so that every onkeyup event triggers a new, more-specific query, but, chances are, the first letter will be used in a large percentage of the words. So if the query searches for the letter 'A', there is a good chance that most of the words will be returned anyways.
What if you used AJAX to execute the query, but only after a 1 or 2 second delay after the user finished pressing keys? That would eliminate a lot of unnecessary querying.
Or, just ask the people on the Google Suggest project how they're doing it 🙂