From: Mark Walters <markwalters1009@gmail.com>
To: Austin Clements <amdragon@MIT.EDU>
Subject: Re: [RFC PATCH 2/4] Add NOTMUCH_MESSAGE_FLAG_EXCLUDED flag
In-Reply-To: <20120128183340.GD17991@mit.edu>
References: <20120124011609.GX16740@mit.edu>
	<1327367923-18228-2-git-send-email-markwalters1009@gmail.com>
	<20120124024521.GY16740@mit.edu> <874nvg6qxn.fsf@qmul.ac.uk>
	<20120128183340.GD17991@mit.edu>
User-Agent: Notmuch/0.11+132~g30df010 (http://notmuchmail.org) Emacs/23.2.1
	(i486-pc-linux-gnu)
Date: Sat, 28 Jan 2012 23:57:08 +0000
Message-ID: <8739azqt2j.fsf@qmul.ac.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Cc: notmuch@notmuchmail.org
Precedence: list

On Sat, 28 Jan 2012 13:33:40 -0500, Austin Clements <amdragon@MIT.EDU> wrote:
> Quoth Mark Walters on Jan 28 at 10:51 am:
> > 
> > > >  	exclude_query = _notmuch_exclude_tags (query, final_query);
> > > >  
> > > > -	final_query = Xapian::Query (Xapian::Query::OP_AND_NOT,
> > > > -					 final_query, exclude_query);
> > > > +	enquire.set_weighting_scheme (Xapian::BoolWeight());
> > > > +	enquire.set_query (exclude_query);
> > > > +
> > > > +	mset = enquire.get_mset (0, notmuch->xapian_db->get_doccount ());
> > > > +
> > > > +	GArray *excluded_doc_ids = g_array_new (FALSE, FALSE, sizeof (unsigned int));
> > > > +
> > > > +	for (iterator = mset.begin (); iterator != mset.end (); iterator++)
> > > > +	{
> > > > +	    unsigned int doc_id = *iterator;
> > > > +	    g_array_append_val (excluded_doc_ids, doc_id);
> > > > +	}
> > > > +	messages->base.excluded_doc_ids = talloc (query, _notmuch_doc_id_set);
> > > > +	_notmuch_doc_id_set_init (query, messages->base.excluded_doc_ids,
> > > > +				  excluded_doc_ids);
> > > 
> > > This might be inefficient for message-only queries, since it will
> > > fetch *all* excluded docids.  This highlights a basic difference
> > > between message and thread search: thread search can return messages
> > > that don't match the original query and hence needs to know all
> > > potentially excluded messages, while message search can only return
> > > messages that match the original query.
> > 
> > I now have some benchmarks (not run enough times to be hugely accurate
> > so ignore minor differences). The full results are below. The summary
> > is:
> > 
> > Large-archive = 1 100 000 messages in 290 000 threads (about 10 years of
> > lkml). I mark 1 000 000 deleted
> > Small-archive = 70 000 messages in 35 000 threads. 10 000 marked
> > deleted.
> > 
> > Doing the initial exclude work on the big collection takes about 0.8s
> > and on the small collection about 0.01s. So any query to the big
> > collection takes at least 0.8s longer and this all occurs before any
> > results appear.
> 
> Interesting.  Do you know where that time is spent?
> 
> Also, it might be reasonable to assume that no more than, say, 10% of
> a person's mail store is excluded, but maybe that depends on how
> people use this feature.
> 
> > I then implemented the exclude doing it once for each thread query in
> > _notmuch_create_thread. Roughly this made any query 50% slower.
> 
> That's not terrible.
> 
> > In normal front end use even the 0.8s is not totally unusable, but it is
> > totally unacceptable in the backend where a user might do something like
> > 
> > for i in ` notmuch search --output=threads  from:xxx ` ; 
> > do 
> >    notmuch search --output=messages $i; 
> > done
> > 
> > to list all messages in all matching threads.
> > 
> > So I think my conclusions are:
> > 
> > (1) message only queries must be done without the full exclude.
> > (2) thread queries which only match one message should not do the full
> > exclude
> > (3) it would be nice to switch between the two approaches depending on
> > size but I don't see how to do that without extra(!) queries
> > (4) One possible might be do something that say does thirty threads with
> > the by thread method and then if not finished does the full exclude.
> > (5) thread-by-thread might be best for  Jani's limit-match 
> > id:"1327692900-22926-1-git-send-email-jani@nikula.org" 
> > 
> > Obviously, anything setting an exclude flag like this will be slower
> > (since it is doing more work): the question is are either of these (or a
> > combination like (4) above) acceptable?
> 
> Or only mark matched messages as excluded.
> 
> Here's another idea (actually, a rehash of an old idea).  For message
> search do two queries, the original query and "<original> AND
> <exclude>", and use this to keep everything in order and mark excluded
> messages.  For thread search, use message search results so it's easy
> to both sort by unexcluded messages and include fully-excluded
> threads, but compute the excluded flag (either just for unmatched
> messages or for all messages) by examining each message's tags
> directly (which thread_add_message already iterates over, so this is
> easy and won't add any overhead).  If the excluded query is fast,
> which I think it will be, I think this should get the best of all
> worlds and be fairly straightforward to implement (no asymmetries
> between the queries used for message and thread search).  It would be
> easy and worth it to run the excluded query by hand on your test
> corpus; I suspect it will be much faster than 0.8s because the query
> already uses "Tmail", which is huge and doesn't seem to slow things
> down.

I have tried your suggestion (still marking all messages) and it does
seem the way to go: the difference in speed is small from master is
small: between 0 and 10% for most of the tests. 

The code seems to work and I will post it in reply to this thread. 

The library code is reasonable (although whether messages matching an
exclude tag that has been specified in the query should be marked as
excluded is unclear).

The cli stuff needs thought (about what it should do rather than
how to do it).

I won't post the emacs stuff yet but I when I merge my various bits
together I should get different colour headerlines for excluded messages
and that they are initially shown collapsed.

Best wishes

Mark