Elastic search or Trie for search/autocomplete?

Question

My understanding how autocomplete/search for text/item works at high level in any scalable product like Amazon eCommerce/Google at high level was :-

Elastic Search(ES) based approach

1. Documents are stored in DB . Once persisted given to Elastic search, It creates the index and store the index/document(based on tokenizer) in memory or disk based configuration.

2. Once user types say 3 characters, it search all index under ES(Can be configured to index even ngram) , Rank them based on weightage and return to user

But after reading couple of resources on google like Trie based search

Looks some of the scalable product also uses Trie data stucture to do the prefix based search.

My question Is Can trie based approach be good alternative to ES or ES internally uses Trie or am i missing completely here ?

Lover

Answer 1

ES autocompletion can be achieved in two ways:

1. using prefix queries
2. either using (edge-)ngrams
3. or using the completion suggester

The first option is the poor man's completion feature. I'm mentioning it because it can be useful in certain situation but you should avoid it if you have a substantial amount of documents.

The second option uses the conventional ES indexing features, i.e. it will tokenize the text, all (edge-)ngrams will be indexed and then you can search for any prefix/infix/suffix that have been indexed.

The third option uses a different approach and is optimized for speed. Basically, when indexing a field of type completion, ES will create a "finite state transducer" and store it in memory for ultra fast access.

A finite state transducer is close to a trie in terms of implementation. You can check this excellent article which shows how trie compares to finite state transducer

UPDATE (June 25th, 2019):

ES 7.2 introduced a new data type called search_as_you_type that allows this kind of behavior natively. Read more at: https://www.elastic.co/guide/en/elasticsearch/reference/7.2/search-as-you-type.html

Lustreware

Updated answer for ES 7.2 – Lustreware