Post #4323751
2026-08-02 00:15 UTC
Replies (1)
-
@david_chisnall@infosec.exchange 2026-08-02 08:07
@joepie91@fedi.slightly.tech It’s been almost two decades since I looked at this. Back then, Apple’s SearchKit and Apache Lucene used a fairly similar strategy: they split things into tokens that were smaller than words (because people often search for stems or variants of words) and then created bloom filters to match these to documents (files, database tables, whatever: they were stored externally by the API consumer). When you searched, you got a two-stage lookup, where the first would ask you for a set of documents that might contain it and then it would do a slower search over those. You could return those in the UI immediately if you didn’t mind that some things would be removed later. The size of the bloom filters were configurable, so you could trade false positives (which impacted search time and I/O requirements) for memory (or disk, depending on how you stored the indexes) usage. This approach still works well. That said, if you don’t configure a FTS engine for Dovecot, it falls back to an approach that is basically ‘grep the files in your Maildir’. And that works way better than it should. Even with consumer SSDs, that can scan 1 GiB of data every couple of seconds. If you have some indexing to know which bits of the files are non-text MIME types, you can skip all of the attachments and the test parts of most people’s email folders are not huge. I’ve seen people deploy ElasticSearch when their entire text would fit in RAM on a vaguely modern Smartphone, which could happily search the whole thing with a naïve algorithm in a few ms.