6c/d93a1b1ce4d87afa76a8bea16912c81d865cc8

   1 Return-Path: <amdragon@gmail.com>\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 0C1C2429E25\r
   6         for <notmuch@notmuchmail.org>; Wed,  3 Aug 2011 13:53:02 -0700 (PDT)\r
   7 X-Virus-Scanned: Debian amavisd-new at olra.theworths.org\r
   8 X-Spam-Flag: NO\r
   9 X-Spam-Score: -0.699\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-0.699 tagged_above=-999 required=5\r
  12         tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FROM=0.001,\r
  13         RCVD_IN_DNSWL_LOW=-0.7] 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 VwNaNHfuk7kU for <notmuch@notmuchmail.org>;\r
  17         Wed,  3 Aug 2011 13:53:00 -0700 (PDT)\r
  18 Received: from mail-qw0-f45.google.com (mail-qw0-f45.google.com\r
  19         [209.85.216.45]) (using TLSv1 with cipher RC4-SHA (128/128 bits))\r
  20         (No client certificate requested)\r
  21         by olra.theworths.org (Postfix) with ESMTPS id A83CD431FB6\r
  22         for <notmuch@notmuchmail.org>; Wed,  3 Aug 2011 13:53:00 -0700 (PDT)\r
  23 Received: by qwj8 with SMTP id 8so1069659qwj.18\r
  24         for <notmuch@notmuchmail.org>; Wed, 03 Aug 2011 13:47:32 -0700 (PDT)\r
  25 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma;\r
  26         h=mime-version:sender:in-reply-to:references:date\r
  27         :x-google-sender-auth:message-id:subject:from:to:cc:content-type\r
  28         :content-transfer-encoding;\r
  29         bh=icYt7i0wlGUSUPIDwWuz0F/REmKhA7zdyNf6tOahzt8=;\r
  30         b=dltdYKoB4kF1rxq8j/tqHixhF713zIDR70A4+57B6dHPeG7DOGv3HwfnsMpczNlAqb\r
  31         Mo97IibxW4RB9US5dZ5YXCRqIAvFDF70IlZymyyZ/UqKksuPoHU8aB+0hiWwWp1yjvpV\r
  32         4Vmt3qtZntcL3IaPDgPapjNnvbSYVxA0UQJko=\r
  33 MIME-Version: 1.0\r
  34 Received: by 10.229.127.1 with SMTP id e1mr397546qcs.257.1312404452606; Wed,\r
  35         03 Aug 2011 13:47:32 -0700 (PDT)\r
  36 Sender: amdragon@gmail.com\r
  37 Received: by 10.229.15.136 with HTTP; Wed, 3 Aug 2011 13:47:32 -0700 (PDT)\r
  38 In-Reply-To: <20110705214234.GA15360@mit.edu>\r
  39 References: <20110703171743.GL15901@mit.edu>\r
  40         <1309762318-4530-1-git-send-email-pieter@praet.org>\r
  41         <e8c5fbf4-4dfa-461a-8f5c-6c696291a270@email.android.com>\r
  42         <87sjqldgr7.fsf@praet.org> <87iprg7dm0.fsf@praet.org>\r
  43         <20110705214234.GA15360@mit.edu>\r
  44 Date: Wed, 3 Aug 2011 16:47:32 -0400\r
  45 X-Google-Sender-Auth: lLBeE0pV7g_AdOaqM1DSiQSUG8Q\r
  46 Message-ID:\r
  47  <CAH-f9WsPj=1Eu=g3sOePJgCTBFs6HrLdLq18xMEnJ8aZ00yCEg@mail.gmail.com>\r
  48 Subject: Re: [PROTO] possible solution for "Race condition for '*' command"\r
  49 From: Austin Clements <amdragon@mit.edu>\r
  50 To: Pieter Praet <pieter@praet.org>, Carl Worth <cworth@cworth.org>\r
  51 Content-Type: text/plain; charset=ISO-8859-1\r
  52 Content-Transfer-Encoding: quoted-printable\r
  53 Cc: Olly Betts <olly@survex.com>, Notmuch Mail <notmuch@notmuchmail.org>\r
  54 X-BeenThere: notmuch@notmuchmail.org\r
  55 X-Mailman-Version: 2.1.13\r
  56 Precedence: list\r
  57 List-Id: "Use and development of the notmuch mail system."\r
  58         <notmuch.notmuchmail.org>\r
  59 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  60         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  61 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  62 List-Post: <mailto:notmuch@notmuchmail.org>\r
  63 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  64 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  65         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  66 X-List-Received-Date: Wed, 03 Aug 2011 20:53:02 -0000\r
  67 \r
  68 On Tue, Jul 5, 2011 at 5:42 PM, Austin Clements <amdragon@mit.edu> wrote:\r
  69 > Quoth Pieter Praet on Jul 05 at =A09:04 pm:\r
  70 >> On Mon, 04 Jul 2011 20:48:12 +0200, Pieter Praet <pieter@praet.org> wrot=\r
  71 e:\r
  72 >> > On Mon, 04 Jul 2011 13:56:26 -0400, Austin Clements <amdragon@MIT.EDU>=\r
  73  wrote:\r
  74 >> > > I should probably emit two lists per thread: one of matched IDs and\r
  75 >> > > one of unmatched IDs. Tagging a region can then operate on the\r
  76 >> > > concatenation of these, while * can operate only on the matched\r
  77 >> > > lists. This should be easy to do. I'll send an updated patch when I'=\r
  78 m\r
  79 >> > > back at a computer.\r
  80 >> >\r
  81 >> > The matched MsgIds will be sufficient, as we'll want to operate on\r
  82 >> > either the matched messages or the entire thread (for which the\r
  83 >> > `thread-id' property is already present).\r
  84 >> >\r
  85 >> > Can't think of a use case for non-matched messages right now,\r
  86 >> > but if required, we'll just use `set-exclusive-or'.\r
  87 >>\r
  88 >> Wasn't thinking clearly:\r
  89 >>\r
  90 >> You're right, we *will* be needing both a list of matched as well as one\r
  91 >> of unmatched Message-Id's per result. Otherwise there would still be a\r
  92 >> potential race condition when tagging with +/-.\r
  93 >\r
  94 > Yes, exactly. =A0(I had originally thought this race was a strict\r
  95 > superset of the '*' race; I now realize that's not the case, but\r
  96 > they're related enough that they might as well be addressed together.)\r
  97 >\r
  98 > Below is an updated patch that separates the matched and unmatched\r
  99 > ID's (it's ugly, but no point in cleaning it up since it's a\r
 100 > prototype). =A0Now the tag list on each search line is followed by\r
 101 > something that looks like\r
 102 >\r
 103 > =A0(id:x or id:y) or id:z\r
 104 >\r
 105 > or just\r
 106 >\r
 107 > =A0(id:x or id:y)\r
 108 >\r
 109 > where the parenthesized part of the query is for the matched messages\r
 110 > and the (possibly empty) unparenthesized part is for the non-matched\r
 111 > messages. =A0This is designed to be easy for emacs to parse: grab just\r
 112 > the parenthesized part for the queries used by '*' and the whole thing\r
 113 > for region tagging queries. =A0This should also eliminate corner cases\r
 114 > for pasting together multiple queries with "or".\r
 115 >\r
 116 > *snip*\r
 117 \r
 118 The patch I posted above includes message ID's in search results as a\r
 119 proxy for the match set (which can then be used in a tagging operation\r
 120 to tag exactly the results you saw).  However, from an efficiency\r
 121 standpoint, it makes more sense to capture the match set directly as\r
 122 document ID's.\r
 123 \r
 124 I've had an implementation of this for a while, but finally got around\r
 125 to benchmarking the difference between tagging using message ID's\r
 126 versus using document ID's.  It looks like tagging spends about 2/3rds\r
 127 of its time performing queries, and only about 1/3rd actually tagging,\r
 128 so tagging using document ID's is 3x-4x faster.\r
 129 \r
 130 The downside to using document ID's is that we need API's to expose\r
 131 them.  My prototype exposes these as opaque "object ID"s, which acts a\r
 132 lot like message IDs, but has no intrinsic meaning outside of the\r
 133 library.  This needs two library functions: one to retrieve a\r
 134 message's object ID and another to retrieve a message by object ID.\r
 135 \r
 136 3x-4x isn't enough to make me jump on this added complexity, but it's\r
 137 enough to make me consider it.  Carl, I'd love to hear your thoughts.\r
 138 \r
 139 The benchmark results are below.  All results are for a corpus of 10K\r
 140 messages taken from the Enron email data set and in all cases the\r
 141 database is in the buffer cache.  "P4" is my old Pentium 4 and "C2" is\r
 142 my newer Core 2 Duo.\r
 143 \r
 144                 Message IDs   Document IDs   Diff\r
 145 HDD/ext3,   P4     235.8s         76.3s      3.1x\r
 146 SSD/btrfs,  P4     239.4s         69.0s      3.5x\r
 147 HDD/reiser, C2      72.4s         23.7s      3.1x\r
 148 \r
 149 I also ran with a patch to Xapian from ojwb that optimizes\r
 150 adding/removing terms that don't have position information [1], which\r
 151 reduces the baseline tagging cost.\r
 152 \r
 153 HDD/reiser, C2      71.6s         19.4s      3.7x\r
 154 \r
 155 [1] http://oligarchy.co.uk/xapian/patches/xapian-chert-optimise-adding-term=\r
 156 -without-positions.patch\r