[notmuch] Rather simple optimization for notmuch tag

[Olly Betts]

Mark Anderson writes:
> On Wed, 23 Dec 2009 03:45:14 +0000, Olly Betts wrote:
> > Handling a combination of removals and additions is trickier, but probably
> > possible, although the more tags you are dealing with, the less profitable
> > the filtering is likely to be (as the filter is likely to cull fewer
> > documents yet be more expensive to evaluate).
> 
> But the transform is pretty simple, I think that any combination of
> additions and removals could be transformed according to the following
> formula.
> 
> notmuch tag +a1 +a2 +a3 -d1 -d2 -d3 <search-terms>
> 
> would transform to something like:
> 
> <search-terms> and ( not(a1) or not(a2) or not(a3) or d1 or d2 or d3)

Note that Xapian doesn't really have a "not" operator (because of how it
works - by storing the documents indexing each term - rather than because
nobody's implemented it), so it isn't quite as simple as the above.

There is a posting list for "all documents" (which is very efficient if
the document ids form a contiguous range; if they don't, it's as efficient
as a term which matches all those documents for the chert backend, but not
so great for the default flint backend in 1.0.x), and you can combine this
with the "AND_NOT" operator to give the equivalent of a "NOT" operator.

So I think the example above is probably best expressed as:

( <search-terms> AND ( ( ALL AND_NOT (a1 AND a2 AND a3) ) OR d1 OR d2 OR d3 )

But my point wasn't that I doubted it could be handled, but that it becomes
less worthwhile as the number of tags increases (and at some point will
become slower).

> There are certainly may be much more optimal ways to do it depending on
> the specific corpus of the database, considering if the tags a1 and a2
> and a3 are usually added as one tag, or if the addition is done
> individually, because if I know that a3 implies a1 and a2, the first 3
> terms could be combined to not(a1 and a2 and a3), or I could just
> exclude a3 tagged messages for nearly the same effect, with expected
> performance improvements.

I think you always can combine them like that.  The documents that don't
need looking at are precisely those which already have all three tags
(i.e. a1 AND a2 AND a3), so those that do are "NOT" that expression.

Cheers,
    Olly