I disagree, Alta Vista had excellent an excellent search UI with Boolean logic. Google discarded that because it thought it 'knew better' in terms of Page Rank.
A-V could be fine-tuned to find a page with exactly the search terms, Google just gave fuzzy approximations from a very large search set.