4 ms·

Structure of FTS5 Index in SQLite

95 points by ellieh 3y ago

AlexErrant 3y ago
I had a... suboptimal experience with SQLite's FTS, so here it is for others: match queries don't work with `OR` conditions. You have to do this work around: WHERE fa.rowid IN (SELECT rowid FROM address_fts WHERE address_fts MATCH 'google') OR ta.rowid IN (SELECT rowid FROM address_fts WHERE address_fts MATCH 'google') Source https://sqlite.org/forum/forumpost?udc=1&name=1a2f2ffdd80cf795 https://sqlite.org/forum/forumpost?udc=1&name=1a2f2ffdd80cf7... I'm building a search feature for my app, that parses a user's search query (a la Github search) and returns relevant results. Generating the above workaround SQL on the fly is just... ulgh.
- Hakkin 3y ago
  I encountered similar issues with FTS5, I found you can clean it up slightly with a CTE WITH matches(id) AS ( SELECT rowid FROM address_fts WHERE address_fts MATCH 'google' ) ... WHERE fa.rowid IN matches OR ta.rowid IN matches You can also have more complex queries, such as if you want to match multiple domains (MATCH 'google OR gmail'). It makes it slightly easier to generate queries since you only have to generate the CTE and then you can just use the CTE name everywhere else.
- shivawu 3y ago
  Yeah this is exactly what I ended up doing, like two days ago. It’s quite a pitfall… (and not optimal in terms of performance)
forinti 3y ago
I've been using FTS with a stemming module from CPAN and it works quite well. Of course the stemming module does not catch all cases, but it works well enough to be useful.
- knighthack 3y ago
  It works well enough for standard English. For other languages though, it's a bit of a different story.
- rogerbinns 3y ago
  Stemmers tend to cover English and a few Europeanish languages only. For example you can see what snowball covers here [1] while NLTK has some more [2]. [1] https://snowballstem.org/ https://snowballstem.org/ [2] https://www.nltk.org/api/nltk.stem.html https://www.nltk.org/api/nltk.stem.html What you may find useful is unidecode that transliterates Unicode to ASCII similar sounds. There are packages available for most programming languages, with the original being on Perl. I highly recommend reading the original article describing how it works. My practical experience is that is fairly good for text searching, producing reasonable results. https://interglacial.com/tpj/22/ https://interglacial.com/tpj/22/
  - forinti 3y ago
    I really only have to worry about one language. I think I've seen this method before, but I'll read up on it. Thanks for the link.
  - dfox 3y ago
    This! Just pass both the content and query through unidecode and some simple filter that removes stop words and cruft in the content, works wonders for autocomplete. Applying that idea to true full-text search is somewhat more involved (you have to somehow produce a stemmer that works on the output of unidecode), but doable and it works.
resoluteteeth 3y ago
I hadn't seen that tokenizer and it's really great that they open sourced it because not supporting CJK languages out of the box is one of the major issues with sqlite fts. I think this also shows why a standard third party distribution of sqlite is needed so that extensions like this can be included with the sqlite binaries provided with bindings for other languages
- rogerbinns 3y ago
  The problem with doing CJK and other languages properly is that you need a lot of data lookup tables. As an example Python has a unicodedata module with several tables available, but not enough to implement word splitting. It is compiled code and 1.2MB in size. The ICU C library does include all the tables and algorithms, which are 30MB compiled data plus 12MB of compiled code. Run through gzip the compiled data becomes 12MB giving a reasonable minimum bound. This gives an idea of the payload that would have to be included if you want up to date Unicode definitions, or to be included in base images. SQLite does have optional integration with ICU, but it doesn't cover segmentation. https://sqlite.org/src/dir/ext/icu https://sqlite.org/src/dir/ext/icu
  - resoluteteeth 3y ago
    > The problem with doing CJK and other languages properly is that you need a lot of data lookup tables Hmm.. My impression is that with other search software, just splitting CJK text into bigrams often works well enough for a lot of things, but I guess because sqlite FTS doesn't allow fuzzy searches where it returns the best ranked results even if they don't include all the input tokens, that might not work. Perhaps a good compromise would be to figure out a way to include an extension by default that requires the additional data lookup tables for CJK support to be loaded at runtime if required? That way the binary sqlite distribution could still be standardized, since loading custom binary extensions isn't really that convenient if you're using a language other than c and trying to build binaries for multiple platforms. Unfortunately, it doesn't seem like the creators of sqlite are that interested in solving this problem since theoretically you can just use extensions to do whatever you need.
rogerbinns 3y ago
It isn't made clear in the repo but what this is doing [1] is a small amount of code to glue SQLite's tokenizer API to the Rust unicode-segmentation crate [2] which in turn is using the TR-29 algorithm with generated tables [3]. [1] https://github.com/signalapp/Signal-FTS5-Extension/blob/main/Cargo.toml https://github.com/signalapp/Signal-FTS5-Extension/blob/main... [2] https://unicode-rs.github.io/unicode-segmentation/unicode_segmentation/index.html https://unicode-rs.github.io/unicode-segmentation/unicode_se... [3] https://github.com/unicode-rs/unicode-segmentation/blob/master/src/tables.rs https://github.com/unicode-rs/unicode-segmentation/blob/mast... International Components for Unicode is the reference library for this and other Unicode algorithms. https://en.wikipedia.org/wiki/International_Components_for_Unicode https://en.wikipedia.org/wiki/International_Components_for_U...
bomewish 3y ago
This is really great and helpful. Confused why roll own tokeniser for fts5 when there’s already a good one?? https://github.com/wangfenjin/simple https://github.com/wangfenjin/simple

95 points by ellieh 3y ago

I had a... suboptimal experience with SQLite's FTS, so here it is for others: match queries don't work with `OR` conditions. You have to do this work around: WHERE fa.rowid IN (SELECT rowid FROM address_fts WHERE address_fts MATCH 'google') OR ta.rowid IN (SELECT rowid FROM address_fts WHERE address_fts MATCH 'google') Source https://sqlite.org/forum/forumpost?udc=1&name=1a2f2ffdd80cf795 https://sqlite.org/forum/forumpost?udc=1&name=1a2f2ffdd80cf7... I'm building a search feature for my app, that parses a user's search query (a la Github search) and returns relevant results. Generating the above workaround SQL on the fly is just... ulgh.

Hakkin 3y ago
I encountered similar issues with FTS5, I found you can clean it up slightly with a CTE WITH matches(id) AS ( SELECT rowid FROM address_fts WHERE address_fts MATCH 'google' ) ... WHERE fa.rowid IN matches OR ta.rowid IN matches You can also have more complex queries, such as if you want to match multiple domains (MATCH 'google OR gmail'). It makes it slightly easier to generate queries since you only have to generate the CTE and then you can just use the CTE name everywhere else.
shivawu 3y ago
Yeah this is exactly what I ended up doing, like two days ago. It’s quite a pitfall… (and not optimal in terms of performance)

forinti 3y ago

I've been using FTS with a stemming module from CPAN and it works quite well. Of course the stemming module does not catch all cases, but it works well enough to be useful.

knighthack 3y ago
It works well enough for standard English. For other languages though, it's a bit of a different story.
rogerbinns 3y ago
Stemmers tend to cover English and a few Europeanish languages only. For example you can see what snowball covers here [1] while NLTK has some more [2]. [1] https://snowballstem.org/ https://snowballstem.org/ [2] https://www.nltk.org/api/nltk.stem.html https://www.nltk.org/api/nltk.stem.html What you may find useful is unidecode that transliterates Unicode to ASCII similar sounds. There are packages available for most programming languages, with the original being on Perl. I highly recommend reading the original article describing how it works. My practical experience is that is fairly good for text searching, producing reasonable results. https://interglacial.com/tpj/22/ https://interglacial.com/tpj/22/
- forinti 3y ago
  I really only have to worry about one language. I think I've seen this method before, but I'll read up on it. Thanks for the link.
- dfox 3y ago
  This! Just pass both the content and query through unidecode and some simple filter that removes stop words and cruft in the content, works wonders for autocomplete. Applying that idea to true full-text search is somewhat more involved (you have to somehow produce a stemmer that works on the output of unidecode), but doable and it works.

resoluteteeth 3y ago

I hadn't seen that tokenizer and it's really great that they open sourced it because not supporting CJK languages out of the box is one of the major issues with sqlite fts. I think this also shows why a standard third party distribution of sqlite is needed so that extensions like this can be included with the sqlite binaries provided with bindings for other languages

rogerbinns 3y ago
The problem with doing CJK and other languages properly is that you need a lot of data lookup tables. As an example Python has a unicodedata module with several tables available, but not enough to implement word splitting. It is compiled code and 1.2MB in size. The ICU C library does include all the tables and algorithms, which are 30MB compiled data plus 12MB of compiled code. Run through gzip the compiled data becomes 12MB giving a reasonable minimum bound. This gives an idea of the payload that would have to be included if you want up to date Unicode definitions, or to be included in base images. SQLite does have optional integration with ICU, but it doesn't cover segmentation. https://sqlite.org/src/dir/ext/icu https://sqlite.org/src/dir/ext/icu
- resoluteteeth 3y ago
  > The problem with doing CJK and other languages properly is that you need a lot of data lookup tables Hmm.. My impression is that with other search software, just splitting CJK text into bigrams often works well enough for a lot of things, but I guess because sqlite FTS doesn't allow fuzzy searches where it returns the best ranked results even if they don't include all the input tokens, that might not work. Perhaps a good compromise would be to figure out a way to include an extension by default that requires the additional data lookup tables for CJK support to be loaded at runtime if required? That way the binary sqlite distribution could still be standardized, since loading custom binary extensions isn't really that convenient if you're using a language other than c and trying to build binaries for multiple platforms. Unfortunately, it doesn't seem like the creators of sqlite are that interested in solving this problem since theoretically you can just use extensions to do whatever you need.

rogerbinns 3y ago

It isn't made clear in the repo but what this is doing [1] is a small amount of code to glue SQLite's tokenizer API to the Rust unicode-segmentation crate [2] which in turn is using the TR-29 algorithm with generated tables [3]. [1] https://github.com/signalapp/Signal-FTS5-Extension/blob/main/Cargo.toml https://github.com/signalapp/Signal-FTS5-Extension/blob/main... [2] https://unicode-rs.github.io/unicode-segmentation/unicode_segmentation/index.html https://unicode-rs.github.io/unicode-segmentation/unicode_se... [3] https://github.com/unicode-rs/unicode-segmentation/blob/master/src/tables.rs https://github.com/unicode-rs/unicode-segmentation/blob/mast... International Components for Unicode is the reference library for this and other Unicode algorithms. https://en.wikipedia.org/wiki/International_Components_for_Unicode https://en.wikipedia.org/wiki/International_Components_for_U...

bomewish 3y ago

This is really great and helpful. Confused why roll own tokeniser for fts5 when there’s already a good one?? https://github.com/wangfenjin/simple https://github.com/wangfenjin/simple