Date: Thu, 18 Nov 2010 02:38:29 -0500
From: Austin Clements <amdragon@MIT.EDU>
To: notmuch@notmuchmail.org
Subject: Re: [PATCH 3/4] Optimize thread search using matched docid sets.
Message-ID: <20101118073828.GD2439@mit.edu>
References: <20101117192826.GU2439@mit.edu>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20101117192826.GU2439@mit.edu>
User-Agent: Mutt/1.5.20 (2009-06-14)
Precedence: list

Currently this code uses a bitmap indexed by docid as a simple, fast
set structure.  This is quite memory-efficient if the docid space is
dense, even if the largest docid is quite large.  Is there a danger
that the docid space will be large and sparse?  Is it worth replacing
this with a smarter bit set structure?

Quoth myself on Nov 17 at  2:28 pm:
> This reduces thread search's 1+2t Xapian queries (where t is the
> number of matched threads) to 1+t queries and constructs exactly one
> notmuch_message_t for each message instead of 2 to 3.
> notmuch_query_search_threads eagerly fetches the docids of all
> messages matching the user query instead of lazily constructing
> message objects and fetching thread ID's from term lists.
> _notmuch_thread_create takes a seed docid and the set of all matched
> docids and uses a single Xapian query to expand this docid to its
> containing thread, using the matched docid set to determine which
> messages in the thread match the user query instead of using a second
> Xapian query.
> 
> As a side effect, this fixes author order so authors are always sorted
> by first occurrence in each thread.  This breaks two emacs tests that
> hard-code the old, buggy author order.
> 
> This reduces the amount of time required to load my inbox from 4.523
> seconds to 3.025 seconds (1.5X faster).