Squat Full Text Search Indexing
===============================

Squat indexes can be used to optimize standard IMAP SEARCH TEXT and BODY
commands. The main advantage of Squat indexes is that they allow substring
matching, while pretty much all other FTS indexes support only matching from
the beginning of words. IMAP searches require substring matching, so Squat
indexes are the only choice to optimize them in a standard way.

 * 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:

 1. Search for messages having "char" (reply example: 1,5,10)
 2. Search for messages having "hara" (reply example: 3,5,10)
 3. Store the intersection of the above searches to "maybe UIDs" (example:
    5,10)
 4. Search for full word "chara" and store it as "definite UIDs" (reply
    example: 5)
 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 [http://cyrusimap.web.cmu.edu/] 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
}
---%<-------------------------------------------------------------------------

(This file was created from the wiki on 2011-11-16 14:09)