One of my favourite little-known PostgreSQL features is trigram indexes. They let you speed up queries that need to match substrings within a text column - queries like this:

select * from articles where title like '%smil%'

There's a great explanation of how these work in PostgreSQL here: https://about.gitlab.com/blog/2016/03/18/fast-search-using-postgresql-trigram-indexes/#trigram-indexes

I would love to have a version of this functionality in SQLite. There's an experimental module for that here, but it's not seen any work in seven years: https://github.com/jonasfj/trilite

Has anyone seen a SQLite-oriented solution for this?

The reason you can't find external solutions is that it's built into SQLite.

https://www.sqlite.org/fts5.html

FTS5 is a recent addition to SQLite and you may not find a lot of examples to learn from. If you prefer to stick with tried and tested solutions you may prefer

https://www.sqlite.org/fts3.html

Except a trigram sequence can speed up LIKE regardless of the position of characters in a column. FTS5 won't (I don't think) support substrings within a longer string, only prefix or exact matches of tokens. For example:

SELECT * FROM tab WHERE col LIKE '%cot%'

Will return 'cot', 'rural cottage', 'cottage cheese', and 'Scott' (among other possibilities). I don't think FTS5 would support that sort of a search, where cot might be embedded within a word as it is in my name.

Yes exactly - FTS5 is amazing but it doesn't solve internal substrings in the same way that trigrams do.

... though now I'm wondering if one could use a custom FTS tokenizer to create a trigram index.

You could definitely tokenize a string into three character overlapping chunks. One problem might be tracking the overlapping of strings. For example, if you had a string 'ABCDEF' and you searched for 'DEFABC', you would find 'ABC' and 'DEF'. You wouldn't find 'EFA' or 'FAB'. So your MATCH clause would probably need to be customized based on what you were searching for. So the FTS index could have all the trigrams, but matching would be a little more complex than a simple LIKE. However, it should be quite fast to find even with the more complicated query formatting, and probably much easier than adding actual trigram indexes to SQLite.

An alternate to these trigram indices is a schema of the form

table word   (id, string);
table suffix (id, string);
table link   (suffix, word);
index link_s on link (suffix);

The basic idea behind this is that any substring S of a word W is the prefix of a suffix of W.

Whenever a word W is added to word, all the suffices of W are added to suffix, and link is extended also, to map from the suffices to W.

Now a substring search for the words matching %foo% becomes a prefix search foo% in suffix, and we get the relevant word id by joining link.

Roughly:

SELECT DISTINCT word
FROM   link
WHERE  suffix IN (SELECT id
	          FROM   suffix
	          WHERE  suffix LIKE 'foo%')

Note, this gives us only the word ids. To get the actual words we have to join word as well. That exercise is left for the reader.

That's really clever, and seems like it should be pretty easy to implement. Thanks!

You are welcome.

I do not believe that the idea is original to me, although I do not remember having it seen anywhere else.

I should note that I expect the suffix table to be quite a bit larger than the word table, and the link table to be much larger. Plus the index on link.

So this looks to be very much trading memory/space for speed.

Whoa. I just got that working on my Mac - I had to copy ./sqlite/ext/fts5/fts5.h into the same directory as that ftstri.c file but once I did that the following:

gcc -I. -g -fPIC -shared ftstri.c -o ftstri.so

Did indeed produce a ftstri.so extension which I successfully loaded into SQLite using Python!

ftstri % python3
Python 3.8.5 (default, Jul 21 2020, 10:48:26) 
[Clang 11.0.3 (clang-1103.0.32.62)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import sqlite3
>>> c = sqlite3.connect(":memory:")
>>> c
<sqlite3.Connection object at 0x107e137b0>
>>> c.enable_load_extension(True)
>>> c.load_extension("ftstri.so")
>>> c
<sqlite3.Connection object at 0x107e137b0>
>>> c.execute("CREATE VIRTUAL TABLE dict USING fts5(word, tokenize=tri);")
<sqlite3.Cursor object at 0x107e9f880>
>>> c.execute('INSERT INTO dict values ("simon")')
<sqlite3.Cursor object at 0x107e9f8f0>
>>> c.execute('INSERT INTO dict values ("cleo")')
<sqlite3.Cursor object at 0x107e9f880>
>>> c.execute('INSERT INTO dict values ("natalie")')
<sqlite3.Cursor object at 0x107e9f8f0>
>>> c.execute('select * from dict(?)', ['simon']).fetchall()
[('simon',)]
>>> c.execute('select * from dict(?)', ['sim']).fetchall()
[('simon',)]
>>> c.execute('select * from dict(?)', ['imo']).fetchall()
[('simon',)]
>>> 
>>> 
>>> 
>>> c.execute("select highlight(dict, 0, '(', ')') from dict(?)", ['sim']).fetchall()
[('(sim)on',)]
>>> c.execute("select highlight(dict, 0, '(', ')') from dict(?)", ['simon']).fetchall()
[('(simon)',)]
>>> c.execute("select highlight(dict, 0, '(', ')') from dict(?)", ['mon']).fetchall()
[('si(mon)',)]
>>> c.execute("select highlight(dict, 0, '(', ')') from dict(?)", ['cl']).fetchall()
[]
>>> c.execute("select highlight(dict, 0, '(', ')') from dict(?)", ['cleo']).fetchall()
[('(cleo)',)]
>>> c.execute("select highlight(dict, 0, '(', ')') from dict(?)", ['cle']).fetchall()
[('(cle)o',)]
>>> c.execute("select highlight(dict, 0, '(', ')') from dict(?)", ['cleop']).fetchall()
[]
>>> c.execute("select highlight(dict, 0, '(', ')') from dict(?)", ['nat']).fetchall()
[('(nat)alie',)]

Do you mind if I create a GitHub repo for this, crediting you as the author of the code and adding some documentation on how to build it? Is the same license as SQLite OK?

By all means. Please do!