MBOX-Line: From arnt at gulbrandsen.priv.no  Wed Dec 20 03:09:22 2006
To: imap-protocol@u.washington.edu
From: Arnt Gulbrandsen <arnt@gulbrandsen.priv.no>
Date: Fri Jun  8 12:34:38 2018
Subject: [Imap-protocol] Searching
In-Reply-To: <1166603479.22214.298.camel@hurina>
References: <1166603479.22214.298.camel@hurina>
Message-ID: <8j2+4TzX9tp2p0Ep9/IgQw.md5@libertango.oryx.com>

Timo Sirainen writes:
> RFC says: "In all search keys that use strings, a message matches the 
> key if the string is a substring of the field."
>
> Strictly reading this, it means that the SEARCH command can't really 
> be optimized with most of the normal search index 
> algorithms/libraries, because they support only matching from the 
> beginning of words.
>
> So, in case I wanted to use such indexes, what do you think I should do?
>
> 1) Just use it for BODY and TEXT searches. Probably won't really break 
> anything? I think some servers already do this.

As a first try, I would scan for spaces in the search key and doing an 
index-assisted search on whatever follows the first space, then looking 
at the matches more closely. If the command is ?SEARCH SUBJECT "a b"?, 
that implies that only messages whose subject contain a word starting 
with b can match, so use that to narrow down the possibilities. If that 
doesn't help your users enough, you could revisit the problem in a 
later server version.

> 2) Add some X-NONEXACT-BODY search extension. Or use COMPARATOR somehow?

You could define a new collation whose substring operation only chops at 
word boundaries, and then name that collation using COMPARATOR, but I 
doubt that would help you. Which clients would do it?

For me, the most important aspect of this problem is address searches. 
After discussing that with Mark Crispin, I implemented a little bit of 
address parsing: My code treats a ?SEARCH FROM "<tss@"? as a search for 
messages from addresses whose complete localpart is tss. My code will 
not find ?From: "<tss@" <any@thi.ng>?, but it finds mail from you 
really quickly.

Arnt

