Re: Rather simple optimization for notmuch tag

[Mark Anderson <MarkR.Anderson@amd.com>]

On Wed, 23 Dec 2009 03:45:14 +0000, Olly Betts <olly@survex.com> wrote:
> Carl Worth writes:
> > On Fri, 18 Dec 2009 00:49:00 -0700, Mark Anderson wrote:
> > > I was updating my poll script that tags messages, and a common idiom is
> > > to put
> > >  tag +mytag <search_terms> and not tag:mytag
> > > 
> > > I don't know anything about efficiency, but for the simple single-tag
> > > case, couldn't we imply the "and not tag:mytag" from the +mytag action
> > > list for the tag command?
> > 
> > On one level, it really shouldn't be a performance issue to tag messages
> > that already have a particular tag. (And in fact, the recently proposed
> > patches to fix Xapian defect 250 even address this I think.)
> 
> Applying a filter up-front like this is likely to still help I think as it
> avoids Xapian having to reverse-engineer this information internally.

That's good to hear.

> Actually, you could do this with multiple tags - you just need to build
> a filter for documents which might be affected.
> 
> So if you're adding tags a1 and a2, you want: <query> AND_NOT (a1 AND a2)
> since documents which already have tags a1 and a2 can be ignored.
> 
> If you're removing d1 and d2, then the filter is: <query> AND (d1 OR d2)
> since documents have to be tagged d1 or d2 in order for the removal to
> do anything.
> 
> 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) 

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.

Unfortunately this requires that I know more about how the tags are used
than I ever want notmuch to deal with.  Perhaps a follow-on or parallel
project with less emphasis on minimalism.


This looks pretty good to me.  Easy to implement and not likely to break
things.  I've been wondering about whether there should be a repository
of mail added to the notmuch git so that we can start testing these
kinds of features on a consistent body of mail.
 
I doubt that I'll be the one to write this, since I don't have any time
set aside for real coding, but if it takes long enough, I'll probably
pick this one up eventually.

-Mark