ea/a35404ec370f126d8481dc4a394a1e56f7297e

   1 Return-Path: <amdragon@mit.edu>\r
   2 X-Original-To: notmuch@notmuchmail.org\r
   3 Delivered-To: notmuch@notmuchmail.org\r
   4 Received: from localhost (localhost [127.0.0.1])\r
   5         by olra.theworths.org (Postfix) with ESMTP id 7860340DDC5\r
   6         for <notmuch@notmuchmail.org>; Tue, 16 Nov 2010 08:18:58 -0800 (PST)\r
   7 X-Virus-Scanned: Debian amavisd-new at olra.theworths.org\r
   8 X-Spam-Flag: NO\r
   9 X-Spam-Score: -1.9\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5\r
  12         tests=[BAYES_00=-1.9] autolearn=ham\r
  13 Received: from olra.theworths.org ([127.0.0.1])\r
  14         by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024)\r
  15         with ESMTP id EqVsVJooTRPv for <notmuch@notmuchmail.org>;\r
  16         Tue, 16 Nov 2010 08:18:47 -0800 (PST)\r
  17 Received: from dmz-mailsec-scanner-6.mit.edu (DMZ-MAILSEC-SCANNER-6.MIT.EDU\r
  18         [18.7.68.35])\r
  19         by olra.theworths.org (Postfix) with ESMTP id 0880640DBC8\r
  20         for <notmuch@notmuchmail.org>; Tue, 16 Nov 2010 08:18:46 -0800 (PST)\r
  21 X-AuditID: 12074423-b7bd0ae000000a00-32-4ce2aee5aecb\r
  22 Received: from mailhub-auth-1.mit.edu ( [18.9.21.35])\r
  23         by dmz-mailsec-scanner-6.mit.edu (Symantec Brightmail Gateway) with\r
  24         SMTP id 9F.36.02560.5EEA2EC4; Tue, 16 Nov 2010 11:18:45 -0500 (EST)\r
  25 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103])\r
  26         by mailhub-auth-1.mit.edu (8.13.8/8.9.2) with ESMTP id oAGGIiaG009342\r
  27         for <notmuch@notmuchmail.org>; Tue, 16 Nov 2010 11:18:45 -0500\r
  28 Received: from awakening.csail.mit.edu (awakening.csail.mit.edu [18.26.4.91])\r
  29         (authenticated bits=0)\r
  30         (User authenticated as amdragon@ATHENA.MIT.EDU)\r
  31         by outgoing.mit.edu (8.13.6/8.12.4) with ESMTP id oAGGIhtZ005831\r
  32         (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT)\r
  33         for <notmuch@notmuchmail.org>; Tue, 16 Nov 2010 11:18:44 -0500 (EST)\r
  34 Received: from amthrax by awakening.csail.mit.edu with local (Exim 4.72)\r
  35         (envelope-from <amdragon@mit.edu>) id 1PIOF1-0005Qy-AV\r
  36         for notmuch@notmuchmail.org; Tue, 16 Nov 2010 11:18:43 -0500\r
  37 Date: Tue, 16 Nov 2010 11:18:43 -0500\r
  38 From: Austin Clements <amdragon@MIT.EDU>\r
  39 To: notmuch@notmuchmail.org\r
  40 Subject: Improved search speed by 2.5X\r
  41 Message-ID: <20101116161842.GA2439@mit.edu>\r
  42 MIME-Version: 1.0\r
  43 Content-Type: text/plain; charset=us-ascii\r
  44 Content-Disposition: inline\r
  45 User-Agent: Mutt/1.5.20 (2009-06-14)\r
  46 X-Brightmail-Tracker: AAAAARagEl4=\r
  47 X-Mailman-Approved-At: Tue, 16 Nov 2010 08:34:39 -0800\r
  48 X-BeenThere: notmuch@notmuchmail.org\r
  49 X-Mailman-Version: 2.1.13\r
  50 Precedence: list\r
  51 List-Id: "Use and development of the notmuch mail system."\r
  52         <notmuch.notmuchmail.org>\r
  53 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  54         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  55 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  56 List-Post: <mailto:notmuch@notmuchmail.org>\r
  57 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  58 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  59         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  60 X-List-Received-Date: Tue, 16 Nov 2010 16:18:58 -0000\r
  61 \r
  62 'Lo.  I've been toying with switching to notmuch for a while, but the\r
  63 speed of search has been holding me back.  Perhaps I should upgrade\r
  64 the archaic machine I'm trying to run notmuch on, but I figured\r
  65 optimizing search would be a good way for me to cut my teeth on\r
  66 notmuch's code.  I've implemented two general optimizations that,\r
  67 together, make thread search 2.5X faster, reducing my test "tag:inbox"\r
  68 query from 4.523 seconds to 1.779 seconds.\r
  69 \r
  70 Before cleaning up and posting the patches, I wanted to make sure my\r
  71 general approach is both correct and pedagogically sound.\r
  72 \r
  73 I reduced thread search's 1 + 2t Xapian queries (where t is the number\r
  74 of unique matched threads) to 1 + t queries and now construct exactly\r
  75 one notmuch_message_t for each message instead of 2 to 3.  The query\r
  76 performed by notmuch_query_search_threads to get all messages matching\r
  77 the user's query now fetches only the docid set instead of\r
  78 constructing message objects and decompressing the thread ID of every\r
  79 message from its term list.  Threads are then constructed from these\r
  80 docids using "thread:" queries much as before; however, now which\r
  81 subset of these messages matched the user query is determined by\r
  82 checking their docids against the docid set constructed earlier,\r
  83 rather than requiring yet another Xapian query per thread to find\r
  84 matched messages.\r
  85 \r
  86 Before this optimization, my test "tag:inbox" query took 4.523\r
  87 seconds.  With the optimization, it takes 3.072 seconds (1.5X faster).\r
  88 It has the downside that it requires more RAM, though even with, say,\r
  89 a 1 million message database, it's at most ~4.2 megs.  In principle it\r
  90 also introduces latency before the first search result, but fetching\r
  91 docid sets is what Xapian was born to do and I haven't noticed any\r
  92 latency.\r
  93 \r
  94 The second optimization is based on the observation that Xapian\r
  95 decompresses a document's term list every time you iterate over it.\r
  96 As a result, notmuch can decompress the beginning of a single term\r
  97 list at least five times.  I combined all of the message metadata\r
  98 fetching (message ID, thread ID, reply-to, filename list, and tag\r
  99 list) into a single pass over the term list that fetches everything.\r
 100 \r
 101 This optimization reduces my "tag:inbox" query to 3.521 seconds (1.3X\r
 102 faster).  This one is a bit more of a balancing act, since it may\r
 103 fetch metadata that is never needed; however, doing the single pass\r
 104 takes only a little longer than running any of the individual metadata\r
 105 requests.\r
 106 \r
 107 These two optimizations complement each other.  With both, my query\r
 108 takes 1.779 seconds (2.5X faster).  Because the first constructs only\r
 109 one message object per message, it aggregates all metadata operations\r
 110 on that one object instead of spreading them across multiple objects,\r
 111 increasing the effectiveness of single-pass metadata retrieval.\r
 112 \r
 113 Does this all seem reasonable?  My code passes the test suite [1], so\r
 114 I believe it to be fairly sound.\r
 115 \r
 116 \r
 117 [1] Except for 2 emacs tests that depend on author order.  What order\r
 118 are matched authors *supposed* to be in?\r
 119 \r
 120 -- \r
 121 Austin Clements                                      MIT/'06/PhD/CSAIL\r
 122 amdragon@mit.edu                           http://web.mit.edu/amdragon\r
 123        Somewhere in the dream we call reality you will find me,\r
 124               searching for the reality we call dreams.\r