Squat Full Text Search Indexing

NOTE: The Squat code is quite slow for large mailboxes. There are also a few bugs that are unlikely to be fixed. In v2.1+ it's recommended to use fts-lucene instead. There's also a "New Squat" redesign/reimplementation going on, which will likely end up having a new name.

The main difference between Squat indexes and the others is that Squat provides support for substring searches, while pretty much all other FTS indexes support only matching from the beginning of words. By strictly reading the IMAP RFC it requires substring matching, so to optimize regular TEXT and BODY searches you must use Squat with Dovecot v2.0. The other indexes are used only for Dovecot's non-standard X-TEXT-FAST and X-BODY-FAST searches. However, almost all other commonly used IMAP servers no longer care about this requirement, so Dovecot v2.1 also no longer makes this distinction. In Dovecot v2.1 TEXT and BODY searches are done using any indexes available.

The Squat indexes are currently updated only when SEARCH TEXT or SEARCH BODY command is used. It's planned that in future they could be updated immediately when messages are being saved.
The Squat indexes take about 30% of the mailbox size (with partial=4 full=4).
The initial Squat index building for large mailboxes can be very CPU and memory hungry.
The Squat indexes are stored among Dovecot's other index files. They're called dovecot.index.search and dovecot.index.search.uids. It's safe to delete both of these files to trigger a rebuild.

Some statistics with Core2 duo 6600, 2 GB memory (partial=4 full=4):

1,4 GB mbox with 368000 messages: SEARCH BODY asdfgh
- Without Squat: 2 min 35 sec CPU, process RSS size 24 MB
- Initial Squat build: 6 min 36 sec CPU, process RSS size peaks at 800 MB, drops to 96 MB at end.
- Subsequent searches: 0.10 sec CPU, 1.18 sec real with cold cache, process RSS size 2 MB.
  - Most of the time was spent verifying Squat results. Searching for a 1..4 letter word gives results in 0.00 CPU secs and 0.80 real secs with cold cache.

32 MB mbox with 7500 messages: SEARCH BODY asdfgh
- Without Squat: 2.3 sec CPU, 3.6 sec real with cold cache, process RSS size 5 MB
- Initial Squat build: 8.9 sec CPU, 10.0 sec real with cold cache, process RSS size peaks at 61 MB, drops to 20 MB at end.
48 MB maildir with 10000 messages: SEARCH BODY asdfgh
- Without Squat: 2.6 sec CPU, 9.7 sec real with cold cache
- Initial Squat build: 9.7 sec CPU, 15.3 sec real with cold cache

Internal workings

Squat works by building a trie of all 1..4 character combinations of all words in messages. For example given a word "world" it indexes "worl", "orld", "rld", "ld" and "d". Matching message UIDs are stored to each trie node, so Squat supports giving definitive answers to any searches with a length of 1..4 characters. For longer search words the word is looked up in 4 letter pieces and the results are merged. The resulting list is a list of messages where the word *may* exist. This means that those messages are still opened and the word is searched from them the slow way.

Squat also supports indexing more characters from the beginning of words. For example if 5 first characters are indexed, the word "character" would be cut to "chara". If a user then searches for "chara", Dovecot does:

Search for messages having "char" (reply example: 1,5,10)
Search for messages having "hara" (reply example: 3,5,10)
Store the intersection of the above searches to "maybe UIDs" (example: 5,10)
Search for full word "chara" and store it as "definite UIDs" (reply example: 5)
Remove definite UIDs (5) from maybe UIDs (5,10 -> 10)

In the above example Dovecot would know that message UID 5 has the word "chara", but it still has to check if UID 10 has it as a substring (e.g. in word "achara") by reading the message contents. If the user's search words match mostly non-substrings (which is common), using long enough full word indexing can improve the search performance a lot, especially when the word matches a lot of messages.

The Squat name comes from Cyrus IMAP which implements slightly similar Squat indexes ("Search QUery Answer Tool"). Dovecot's implementation and file format however is completely different. The main visible difference is that Dovecot allows updating the index incrementally instead of requiring to re-read the entire mailbox to build it. Cyrus Squat also doesn't support 1..3 characters long searches.

Configuration

fts_squat setting can be used to change Squat options:

partial=n: Length of the substring blocks to index. Default is 4 characters and it's probably not a good idea to change it.
full=n: Index n first characters from the beginning of words. Default is 4, but it could be useful to increase this to e.g. 10 or so. However larger values take more disk space.

mail_plugins = $mail_plugins fts fts_squat

plugin {
  fts = squat
  fts_squat = partial=4 full=10
}

Using both Squat and non-Squat (v2.0-only)

It's possible to use both Squat and non-Squat indices at the same time, so that TEXT/BODY are looked up from Squat indexes and X-TEXT-FAST/X-BODY-FAST are looked up from the non-Squat index. This of course means that indices will have to be built and updated for both, so it might not be that good idea.

protocol imap {
..
  mail_plugins = fts fts_squat fts_solr
}
...
plugin {
  fts = squat solr
}