MBOX-Line: From mrc at CAC.Washington.EDU  Wed Dec 20 10:40:55 2006
To: imap-protocol@u.washington.edu
From: Mark Crispin <mrc@CAC.Washington.EDU>
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: <alpine.OSX.0.81.0612201018450.10225@pangtzu.panda.com>

On Wed, 20 Dec 2006, Timo Sirainen wrote:
> 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?

Implement SEARCH according to the IMAP specification.  If a library search 
routine does not fufill the IMAP specification, then it is unsuitable for 
use with IMAP SEARCH.

If you are worried about performance, I suggest that you look into one of 
the optimizing algorithms for fast search.  UW and Cyrus use a Boyer-Moore 
fast search which is quite a bit faster than the straightforward linear 
search.

> 1) Just use it for BODY and TEXT searches. Probably won't really break
> anything? I think some servers already do this.

There are clients that depend upon substring searches.  I also do 
substring searches on a regular basis.  Any server that does not do 
substring searches is broken and non-compliant.

I believe that you are a reasonable person, will accept this bad news with 
grace, and will implement a compliant SEARCH in your server in spite of 
the difficulty that it causes you.  There needs to be at least one 
compliant IMAP server that supports Maildir format (Courier is not 
compliant).  Please show that my belief is true.

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

The problem with one-server extensions is that nobody uses them.  Feel 
free to do so anyway, as long as you implement the standard SEARCH 
correctly; but it will languish in obscurity.

-- Mark --

http://panda.com/mrc
Democracy is two wolves and a sheep deciding what to eat for lunch.
Liberty is a well-armed sheep contesting the vote.

