f0/705631d4dea7bb81b72ccb8badb381a4fc2402

   1 Return-Path: <m.walters@qmul.ac.uk>\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 3409D431FB6\r
   6         for <notmuch@notmuchmail.org>; Sat, 28 Jan 2012 02:50:20 -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.098\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-1.098 tagged_above=-999 required=5\r
  12         tests=[DKIM_ADSP_CUSTOM_MED=0.001, FREEMAIL_FROM=0.001,\r
  13         NML_ADSP_CUSTOM_MED=1.2, RCVD_IN_DNSWL_MED=-2.3] autolearn=disabled\r
  14 Received: from olra.theworths.org ([127.0.0.1])\r
  15         by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024)\r
  16         with ESMTP id rQjEfrIfDrz6 for <notmuch@notmuchmail.org>;\r
  17         Sat, 28 Jan 2012 02:50:19 -0800 (PST)\r
  18 Received: from mail2.qmul.ac.uk (mail2.qmul.ac.uk [138.37.6.6])\r
  19         (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits))\r
  20         (No client certificate requested)\r
  21         by olra.theworths.org (Postfix) with ESMTPS id 4163A431FAE\r
  22         for <notmuch@notmuchmail.org>; Sat, 28 Jan 2012 02:50:19 -0800 (PST)\r
  23 Received: from smtp.qmul.ac.uk ([138.37.6.40])\r
  24         by mail2.qmul.ac.uk with esmtp (Exim 4.71)\r
  25         (envelope-from <m.walters@qmul.ac.uk>)\r
  26         id 1Rr5rJ-0004do-Np; Sat, 28 Jan 2012 10:50:14 +0000\r
  27 Received: from 94-192-233-223.zone6.bethere.co.uk ([94.192.233.223]\r
  28         helo=localhost)\r
  29         by smtp.qmul.ac.uk with esmtpsa (TLSv1:AES128-SHA:128) (Exim 4.69)\r
  30         (envelope-from <m.walters@qmul.ac.uk>)\r
  31         id 1Rr5rJ-0001IY-AW; Sat, 28 Jan 2012 10:50:13 +0000\r
  32 From: Mark Walters <markwalters1009@gmail.com>\r
  33 To: Austin Clements <amdragon@MIT.EDU>\r
  34 Subject: Re: [RFC PATCH 2/4] Add NOTMUCH_MESSAGE_FLAG_EXCLUDED flag\r
  35 In-Reply-To: <20120124024521.GY16740@mit.edu>\r
  36 References: <20120124011609.GX16740@mit.edu>\r
  37         <1327367923-18228-2-git-send-email-markwalters1009@gmail.com>\r
  38         <20120124024521.GY16740@mit.edu>\r
  39 User-Agent: Notmuch/0.11+107~g185f859 (http://notmuchmail.org) Emacs/23.2.1\r
  40         (i486-pc-linux-gnu)\r
  41 Date: Sat, 28 Jan 2012 10:51:16 +0000\r
  42 Message-ID: <874nvg6qxn.fsf@qmul.ac.uk>\r
  43 MIME-Version: 1.0\r
  44 Content-Type: text/plain; charset=us-ascii\r
  45 X-Sender-Host-Address: 94.192.233.223\r
  46 X-QM-SPAM-Info: Sender has good ham record.  :)\r
  47 X-QM-Body-MD5: 04068cf5df31b37566bcf27dfc64a333 (of first 20000 bytes)\r
  48 X-SpamAssassin-Score: -1.8\r
  49 X-SpamAssassin-SpamBar: -\r
  50 X-SpamAssassin-Report: The QM spam filters have analysed this message to\r
  51         determine if it is\r
  52         spam. We require at least 5.0 points to mark a message as spam.\r
  53         This message scored -1.8 points.\r
  54         Summary of the scoring: \r
  55         * -2.3 RCVD_IN_DNSWL_MED RBL: Sender listed at http://www.dnswl.org/,\r
  56         *      medium trust\r
  57         *      [138.37.6.40 listed in list.dnswl.org]\r
  58         * 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail\r
  59         provider *      (markwalters1009[at]gmail.com)\r
  60         * -0.0 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay\r
  61         *      domain\r
  62         *  0.5 AWL AWL: From: address is in the auto white-list\r
  63 X-QM-Scan-Virus: ClamAV says the message is clean\r
  64 Cc: notmuch@notmuchmail.org\r
  65 X-BeenThere: notmuch@notmuchmail.org\r
  66 X-Mailman-Version: 2.1.13\r
  67 Precedence: list\r
  68 List-Id: "Use and development of the notmuch mail system."\r
  69         <notmuch.notmuchmail.org>\r
  70 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  71         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  72 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  73 List-Post: <mailto:notmuch@notmuchmail.org>\r
  74 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  75 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  76         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  77 X-List-Received-Date: Sat, 28 Jan 2012 10:50:20 -0000\r
  78 \r
  79 \r
  80 > >     exclude_query = _notmuch_exclude_tags (query, final_query);\r
  81 > >  \r
  82 > > -   final_query = Xapian::Query (Xapian::Query::OP_AND_NOT,\r
  83 > > -                                    final_query, exclude_query);\r
  84 > > +   enquire.set_weighting_scheme (Xapian::BoolWeight());\r
  85 > > +   enquire.set_query (exclude_query);\r
  86 > > +\r
  87 > > +   mset = enquire.get_mset (0, notmuch->xapian_db->get_doccount ());\r
  88 > > +\r
  89 > > +   GArray *excluded_doc_ids = g_array_new (FALSE, FALSE, sizeof (unsigned int));\r
  90 > > +\r
  91 > > +   for (iterator = mset.begin (); iterator != mset.end (); iterator++)\r
  92 > > +   {\r
  93 > > +       unsigned int doc_id = *iterator;\r
  94 > > +       g_array_append_val (excluded_doc_ids, doc_id);\r
  95 > > +   }\r
  96 > > +   messages->base.excluded_doc_ids = talloc (query, _notmuch_doc_id_set);\r
  97 > > +   _notmuch_doc_id_set_init (query, messages->base.excluded_doc_ids,\r
  98 > > +                             excluded_doc_ids);\r
  99 > \r
 100 > This might be inefficient for message-only queries, since it will\r
 101 > fetch *all* excluded docids.  This highlights a basic difference\r
 102 > between message and thread search: thread search can return messages\r
 103 > that don't match the original query and hence needs to know all\r
 104 > potentially excluded messages, while message search can only return\r
 105 > messages that match the original query.\r
 106 \r
 107 I now have some benchmarks (not run enough times to be hugely accurate\r
 108 so ignore minor differences). The full results are below. The summary\r
 109 is:\r
 110 \r
 111 Large-archive = 1 100 000 messages in 290 000 threads (about 10 years of\r
 112 lkml). I mark 1 000 000 deleted\r
 113 Small-archive = 70 000 messages in 35 000 threads. 10 000 marked\r
 114 deleted.\r
 115 \r
 116 Doing the initial exclude work on the big collection takes about 0.8s\r
 117 and on the small collection about 0.01s. So any query to the big\r
 118 collection takes at least 0.8s longer and this all occurs before any\r
 119 results appear.\r
 120 \r
 121 I then implemented the exclude doing it once for each thread query in\r
 122 _notmuch_create_thread. Roughly this made any query 50% slower.\r
 123 \r
 124 In normal front end use even the 0.8s is not totally unusable, but it is\r
 125 totally unacceptable in the backend where a user might do something like\r
 126 \r
 127 for i in ` notmuch search --output=threads  from:xxx ` ; \r
 128 do \r
 129    notmuch search --output=messages $i; \r
 130 done\r
 131 \r
 132 to list all messages in all matching threads.\r
 133 \r
 134 So I think my conclusions are:\r
 135 \r
 136 (1) message only queries must be done without the full exclude.\r
 137 (2) thread queries which only match one message should not do the full\r
 138 exclude\r
 139 (3) it would be nice to switch between the two approaches depending on\r
 140 size but I don't see how to do that without extra(!) queries\r
 141 (4) One possible might be do something that say does thirty threads with\r
 142 the by thread method and then if not finished does the full exclude.\r
 143 (5) thread-by-thread might be best for  Jani's limit-match \r
 144 id:"1327692900-22926-1-git-send-email-jani@nikula.org" \r
 145 \r
 146 Obviously, anything setting an exclude flag like this will be slower\r
 147 (since it is doing more work): the question is are either of these (or a\r
 148 combination like (4) above) acceptable?\r
 149 \r
 150 I now have a mostly working implementation from library to\r
 151 emacs frontend and I do like the overall outcome.\r
 152 \r
 153 The complete benchmarks are below\r
 154 \r
 155 Best wishes\r
 156 \r
 157 Mark\r
 158 \r
 159 LARGE COLLECTION is 1,100,000 messages 290,000 threads 1,000,000 deleted\r
 160 SMALL COLLECTION is 70,000 messages in 35,000 threads 10,000 deleted\r
 161 \r
 162 benchmarks: all times in seconds, x/y/z means a query which matches x\r
 163 threads with y matching messages and z messages in total. Ig or ignore\r
 164 means with the tag-exclude turned off (i.e. with a query matching the\r
 165 excluded tag). list all messages is the time for the for loop listed\r
 166 above giving all message-ids for all messages in any thread matching a\r
 167 query.\r
 168 \r
 169 Finally the three columns are master with exclude code disabled,\r
 170 thread-thread is doing excludes once per thread construction, and\r
 171 in-advance does all the exclude work in advance as in the patches I posted.\r
 172 \r
 173 In most cases the benchmark is the average of a lot of runs so the\r
 174 database should have been as cached as one could hope.\r
 175 \r
 176                         master-(all)    thread-thread   in-advance\r
 177 LARGE COLLECTION                                        \r
 178 show single message     0.016           0.018           0.78\r
 179 search single message   0.015           0.016           0.78\r
 180 search single with tag  0.015           0.015           0.009\r
 181 945/2627/20000\r
 182 query ignore            2.9             n/a             3\r
 183 query                   2.9             4.2             3.8\r
 184 list all messages (ig)  13              n/a             13\r
 185 list all messages       13              14              12mins\r
 186 4754/13000/110000\r
 187 query ignore            15.9            n/a             17\r
 188 query                   15.9            22              17.6\r
 189 only messages           1.25            1.26            1.9\r
 190 177/483/1752            \r
 191 query                   0.3             0.42            1.1\r
 192 \r
 193 search '*'              20mins          28mins          21.5mins                        \r
 194 \r
 195 SMALL COLLECTION\r
 196 1500/2800/5600\r
 197 query                   1.8             2.7             2\r
 198 list all messages       14.5            16.4            30\r
 199 single message          0.008           0.008           0.018\r
 200 \r
 201 search '*'              28              49              32\r