It depends on the query. Remember that you can write a custom method that responds to autocompletion, so the efficiency of autocompletion will become the efficiency of that method. If you base the query in LIKE perhaps performance (of the query) is poor, if you use ferret instead it will be surely better. You see, the point is not autocompletion itself, but the action behind it.
-- fxn