How to store and query strings matching prefix or suffix in PostgreSQL?

Question

Say I have 1 million words each in 100 different languages (so 100 million words, each with alphabets ranging from 10 characters to 200 characters, although Chinese has 80k "characters" alone! And I would want to support it on Chinese too). These words are stored in the database for a variety of other reasons, so we should ideally use them from the database if possible.

What would you add to a words table (assuming the words.text property has the string from any of 100 different languages) to allow for prefix/suffix matching queries? Maybe we have different tables for different languages if absolutely necessary.

To do prefix queries in PostgreSQL, (without indexes I think?), you would do something like:

select * from words where text like 'cal%'

For searching all words starting with cal. But is that the most efficient/scalable approach for this size of dataset? I don't have too much experience with these types of queries in my career. If not, what is the recommended, standard, ideal, or otherwise efficient approach (in terms of data size and query performance)? What sorts of indexes would you need to add to make this efficient? If PostgreSQL can't do this efficiently (or SQL for that matter), then at a high level what is the preferred solution? I know that in-memory tries are a good solution, but is that that much better than a PostgreSQL solution (if it is at all possible)?

Already, I am considering, based on this answer, using 26 indexes for the English language to be able to find all words that unscramble some input (so CAUDK finds duck, amongst other things), but not sure if a similar solution could be extended to prefix/suffix searches. Plus, that also doesn't appear that efficient (in terms of data size), to handle larger alphabets, and other types of queries.

Realistically, most languages have less than 200k words, and it would probably start out with less than 20k words. I am talking way more than the English language, but Tibetan ལྷ་སའི་སྐད་, Chinese, Korean, Sanskrit and the Devanagari script, etc.

If this is an extremely complicated task to implement across this diverse a set of languages, please just layout the basic vision of how it is solved, with pointers into the key places to do more research. If it's possible to go super deep to implement complex solutions on an individual-language basis (like Chinese is way different solution-wise than English, for example perhaps), I don't really want to have to implement something complex and unique for each language. Ideally it would simply be something "character based", which would apply cross-language. Because in my brief look into full text search implementation, that doesn't seem like what I need, but not sure.

Answer 1

Prefix search in most cases is as efficient as string search, but stops earlier.
For suffix search you have to store your word reversed (desrever) and then search for reversed suffix (de% instead of %ed).
For anagram/scramble search you have to store your word ordered alphabetically (anagram -> aaagmnr)

Answer 2

Following up on my answer to the other question:

For prefix searches, I recommend an in-memory trie. This is essentially a tree with each unique word corresponding to a unique root-to-leaf path down the tree, with 1 letter per tree node. As a potential memory optimization you can use a radix tree, which is a trie with single-child nodes merged with their parents. Here is a diagram of how a prefix search in a radix tree works, taken from the previous link:

This tree can house words from multiple languages using multiple alphabets. The maximum branching factor of this tree will correspond to the number of characters among all alphabets.

Implementation-wise, my recommendation is that the query-handling process load the entire word list from the database and construct the trie at initialization time. It should be relatively fast to build.

Suffix searches can be performed by using a second trie contained the words reversed.

As for "unscrambling" operations, I do believe my index-per-character solution from the other question is best for languages with small alphabets. But for languages with large alphabets, this will be terribly inefficient, as it demands O(MN) space, where M is the number of words and N is the number of alphabet characters. For such languages, since each word typically has a small number of characters (Chinese has about 1.6 characters per word - source), it is more efficient to simply construct an in-memory hash-map mapping each character to the list of all words (or word indices) containing that character. A given unscramble query can be handled then by looking up each character of the query in this hash-map and taking the intersection of the returned lists. A final filtering step can be used to handle multiplicities; alternatively, the hash-map values can themselves be maps mapping multiplicities to words.

The multiple-database-index approach effectively performs something similar to this more general approach under its hood, but should be more optimized thanks to piggy-backing general database mechanics. You can consider just trying the general approach for a single language-independent implementation.