Trigrams – PostgreSQL

We have some postgres functions at my work where wildcard searches are done, where both the wildcard symbol % is added to the front and back of the search term. By prefixing the symbol to the front of search term this means that a B-Tree index cannot be used in the searching and so a full table/index scan needs to be performed. But what if there was a better way, hello Trigrams 🙂

So a Trigram is just a sequence of three consecutive characters. In PostgreSQL you can create a Trigram GiN index, and all this does is that for each word in the column that the index is built from it splits each word up into trigrams.

Say what? So take the word Dog, this would be split into the following trigrams – (” d” ,” do”, “dog”, “og “) You’ll notice the 1st two trigrams and last one have spaces in them, this is because it prefixes each word with two spaces and suffixes it with one.

So how does the Trigram help? – If you had the following query

SELECT * FROM dbo.animal WHERE TYPE like '%dog%';

The query engine determines the trigrams pattern of the search term that has been entered and will then do a Bitmap Index scan of the GiN Trigram index looking for all rows that contain these trigrams. This could result in some false positives and not all words that have the same trigrams are the same words, to eliminate these you match the rows that were found to have the same trigrams against the pattern.

See sample code below on how to create a trigram index in PostgreSQL

1. Create the Trigram Extension
2. Create a GiN Index that uses the trigram operator class
3. Test a wild card search using (LIKE, ILIKE

1. CREATE EXTENSION pg_trgm;
2. CREATE INDEX idx_tablename_colname_gintrig on tablename USING GIN(colname gin_trgm_ops);
3. SELECT * FROM dbo.tablename WHERE colname LIKE '%somevalue%';

Disclaimer: Never just believe everything you read in a post, test this out for yourself, we all can make mistakes! Happy coding.