MBOX-Line: From tss at iki.fi  Wed Dec 20 05:14:50 2006
To: imap-protocol@u.washington.edu
From: Timo Sirainen <tss@iki.fi>
Date: Fri Jun  8 12:34:38 2018
Subject: [Imap-protocol] Searching
In-Reply-To: <8j2+4TzX9tp2p0Ep9/IgQw.md5@libertango.oryx.com>
References: <1166603479.22214.298.camel@hurina>
	<8j2+4TzX9tp2p0Ep9/IgQw.md5@libertango.oryx.com>
Message-ID: <1166620490.22214.327.camel@hurina>

On Wed, 2006-12-20 at 12:09 +0100, Arnt Gulbrandsen wrote:
> 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.

Normally people search only single words, so this doesn't help much.

> > 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?

I mostly need it for one webmail installation where the webmail code can
be modified if needed, but getting it standardized would be nice. I
imagine other server implementors (and especially admins and users)
would be happy to have fast message body searches. At least I've
preferred grep for a long time since it was just too slow via IMAP (yea,
I should look into optimizing my search code too :).

Perhaps related to this issue is the possibility to allow some kind of
fuzzy matching, where the server may decide to show results for strings
which sort-of match, but not completely.

BTW. I did also implement Cyrus Squat like indexes which allow full
substring searches to be done fast, but they take more disk space and
they're slower to update than "normal" search indexes.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 196 bytes
Desc: This is a digitally signed message part
URL: <http://mailman13.u.washington.edu/pipermail/imap-protocol/attachments/20061220/405e2eb8/attachment.sig>
