“The pg_trgm module provides functions and operators for determining the similarity of ASCII alphanumeric text based on trigram matching, as well as index operator classes that support fast searching for similar strings.”
This is the introduction to the official documentation of the extension at [1]. Note, that I used the EXTENSION terminology instead of CONTRIB, as in PostgreSQL 9.1. Now we’ll use the CREATE EXTENSION command to include this module in the database. This new methodology allows us to manage modules installations/uninstallations with only a few commands.
The idea of this post is to show you how KNN GIST and pg_trgm could be used together to obtain interesting results. First, let’s start with some basic elements of pg_trgm.
Installation
Installing the module is easy. If you are installing through the use of source code, you must compile the module and once you get access to the database execute:
CREATE EXTENSION pg_trgm;
That’s it! Installation complete!
What is a Trigram and how use them?
A trigram is a group of three consecutive characters in a string that can be used to detect the similarity of two words (for example) or the ‘distance’ between them.
When we talk about ‘distance’, 0 means in the same place and 1 is very far. When we talk about similarity, 1 is equal and 0 is totally different. In other words, distance is 1 minus the similarity value. These concepts about distance and similarity, are necessary to start without confusion.
What’s is a trigram? A trigram is a group of three consecutive characters from a string, used to know the similarity between two strings by counting the trigrams they share.
A trigram looks like this:
palominodb=# select show_trgm('PalominoDB CO');
show_trgm
-----------------------------------------------------------------------
{" c"," p"," co"," pa",alo,"co ","db ",ino,lom,min,nod,odb,omi,pal}
(1 row)
In the pg_trgm extension we have functions and operators. show_limit and set_limit are functions used to set up and show the similarity threshold for the % operator. This operator takes the form “string1 % string2” and returns a boolean type (“t” if the similarity is greater than the similarity threshold, otherwise it returns “f”).
palominodb=# select show_limit();
show_limit
0.4
palominodb=# select set_limit(0.3), show_limit();
set_limit | show_limit
0.3 | 0.3
In the following example we’ll see the use of each one. Operator % will return true if the similarity of the strings is greater than similarity threshold returned by show_limit function. In this example, both string are equal, in consequence, the operation will return true:
palominodb=# select similarity('Palomino','Palomino') AS Similarity,
'Palomino'<->'Palomino' AS distance,
'Palomino' % 'Palomino' AS SimilarOrNot;
-[ RECORD 1 ]+--
similarity | 1
distance | 0
similarornot | t
Index Support and usage
Now let’s discuss combining GIST or GIN and pg_trgm. pg_trgm includes an operator class to support searches using similarity, like, or ilike operators. GIN and GIST have several differences. If you don’t know which to choose, just remember a few rules: GIN searches quicker than GIST but is slower to update; if you have a write-intensive table use GIST. GIN is better for static data. Please be aware, however, that they don’t support exact matching with the equals operator! You can do an exact match using like/ilike with no wildcards. If you want to use the equals operator(=), you must create a standard BTREE index on the pertinent column.
In the following examples, we’ll show a table only with a GIST index. As you can see, if you want to match the exact value with equal operator, it will scan the whole table:
palominodb=# EXPLAIN ANALYZE SELECT id, texto FROM texto_busqueda WHERE texto = 'Palomino';
QUERY PLAN
-------------------------------------------------------------------------------------------------------------
Seq Scan on texto_busqueda (cost=0.00..90.15 rows=1 width=136) (actual time=16.835..16.846 rows=1 loops=1)
Filter: (texto = 'Palomino'::text)
Total runtime: 17.094 ms
(3 rows)
But, if we use LIKE operator, index scan will be activated:
palominodb=# EXPLAIN ANALYZE SELECT id, texto FROM texto_busqueda WHERE texto like 'Palomino';
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
Index Scan using texto_busqueda_texto_idx on texto_busqueda (cost=0.00..8.27 rows=1 width=136) (actual time=0.374..1.780 rows=1 loops=1)
Index Cond: (texto ~~ 'Palomino'::text)
Total runtime: 1.979 ms
(3 rows)
palominodb=# EXPLAIN ANALYZE SELECT id, texto FROM texto_busqueda WHERE texto like '%Palomino%';
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
Index Scan using texto_busqueda_texto_idx on texto_busqueda (cost=0.00..8.27 rows=1 width=136) (actual time=0.171..1.732 rows=1 loops=1)
Index Cond: (texto ~~ '%Palomino%'::text)
Total runtime: 1.882 ms
(3 rows)
To use an index for match equal strings, we need to create a BTREE index. But in case of BTREE there is a limitation of 8191 bytes per index row. So, if you have very large text columns you will not allowed to create a BTREE index without using functional indexes.
We get this result because, unlike BTREE indexes, the search string is not left-anchored.
The creation of indexes with the pg_trgm operator class is simple:
CREATE INDEX ON texto_busqueda USING GIST(texto gist_trgm_ops);
or
CREATE INDEX ON texto_busqueda USING GIN(texto gin_trgm_ops);
If you want a more comprehensive understanding of GIST or GIN implementation on Postgres, you can download the the source code and read src/backend/access/gist/README and src/backend/access/gin/README.
Another useful technique
Combining % operator to get the strings that have a similarity greater than the established threshold and similarity function -that returns the similarity-, we can get ordered from the most similar to the less one discarding all the strings that aren’t similar enough:
palominodb=# SELECT ctid, similarity(texto, 'Palominodb') AS simil
palominodb-# FROM texto_busqueda
palominodb-# WHERE texto % 'Palominodb'
palominodb-# ORDER BY simil DESC;
ctid | simil
--------+----------
(55,3) | 0.666667
(1 row)
The same query, but with its EXPLAIN plan shows that the generated index is used in the condition:
palominodb=# EXPLAIN ANALYZE SELECT ctid, similarity(texto, 'Palominodb') AS sml
palominodb-# FROM texto_busqueda
palominodb-# WHERE texto % 'Palominodb'
palominodb-# ORDER BY sml DESC;
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
Sort (cost=14.26..14.27 rows=3 width=138) (actual time=3.428..3.437 rows=1 loops=1)
Sort Key: (similarity(texto, 'Palominodb'::text))
Sort Method: quicksort Memory: 17kB
-> Bitmap Heap Scan on texto_busqueda (cost=4.28..14.24 rows=3 width=138) (actual time=3.336..3.383 rows=1 loops=1)
Recheck Cond: (texto % 'Palominodb'::text)
-> Bitmap Index Scan on texto_busqueda_texto_idx (cost=0.00..4.28 rows=3 width=0) (actual time=3.278..3.278 rows=1 loops=1)
Index Cond: (texto % 'Palominodb'::text)
Total runtime: 3.578 ms
(8 rows)
Well, this is the first part. Hope you enjoyed the reading and I’ll wait your comments and feedback!
[1] http://www.postgresql.org/docs/9.1/static/pgtrgm.html
