ec/ee5ffe4bc0cbff5be97072b84d64a756805b1c

   1 Return-Path: <bgamari@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 B9661431FBC\r
   6         for <notmuch@notmuchmail.org>; Wed, 17 Feb 2010 20:44:31 -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: -0.974\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-0.974 tagged_above=-999 required=5\r
  12         tests=[AWL=-0.789, BAYES_40=-0.185] 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 CzZUaGzf54Jg for <notmuch@notmuchmail.org>;\r
  16         Wed, 17 Feb 2010 20:44:31 -0800 (PST)\r
  17 Received: from qw-out-1920.google.com (qw-out-1920.google.com [74.125.92.144])\r
  18         by olra.theworths.org (Postfix) with ESMTP id 04582431FAE\r
  19         for <notmuch@notmuchmail.org>; Wed, 17 Feb 2010 20:44:30 -0800 (PST)\r
  20 Received: by qw-out-1920.google.com with SMTP id 5so1086404qwc.32\r
  21         for <notmuch@notmuchmail.org>; Wed, 17 Feb 2010 20:44:30 -0800 (PST)\r
  22 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma;\r
  23         h=domainkey-signature:received:received:content-type:cc:subject:from\r
  24         :to:in-reply-to:references:date:message-id:user-agent\r
  25         :content-transfer-encoding;\r
  26         bh=GRD4BAqbUKQunavcWYHGuW2NZ/RRiY7Kzj6AyFERhYA=;\r
  27         b=Owk9FeRENbbcSh01fpB0doWcqX/UeVTOVp3yRvwPuDYKcudsyI5dWmBFu6UTFNdJGK\r
  28         DPxXe1i7MMfY+cu7L7v20rs79ydf1/x+7Ikt3eY/8nAKaWGDO+9A9u903MTR2uR/deU3\r
  29         SK8igk98HJrvvRpfuQa2hq+Rtc1z6xj0mvBO0=\r
  30 DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;\r
  31         h=content-type:cc:subject:from:to:in-reply-to:references:date\r
  32         :message-id:user-agent:content-transfer-encoding;\r
  33         b=F65mEzBKma1TBIgulfNh06tm1OPFLaJBSHTcQJXE3FxsctTXfqIA/fopapb3dS8afg\r
  34         PGfeausr5DJ96aA54wnXMOSeoCkL6w0k9R6ZUjQJ1DEHh9SuiIXFces5ZIH3aw0u3TKR\r
  35         IZr5wlWTs6jAhR0Odv1Zlbu9B4rpOJNqROXkU=\r
  36 Received: by 10.224.59.224 with SMTP id m32mr4983242qah.76.1266468270336;\r
  37         Wed, 17 Feb 2010 20:44:30 -0800 (PST)\r
  38 Received: from localhost (pool-96-236-125-203.spfdma.east.verizon.net\r
  39         [96.236.125.203])\r
  40         by mx.google.com with ESMTPS id 2sm19574976qwi.35.2010.02.17.20.44.28\r
  41         (version=TLSv1/SSLv3 cipher=RC4-MD5);\r
  42         Wed, 17 Feb 2010 20:44:29 -0800 (PST)\r
  43 Content-Type: text/plain; charset=UTF-8\r
  44 From: Ben Gamari <bgamari@gmail.com>\r
  45 To: martin f krafft <madduck@madduck.net>\r
  46 In-reply-to: <20100218034613.GD1991@lapse.rw.madduck.net>\r
  47 References: <20100217012101.GD8249@lapse.rw.madduck.net>\r
  48         <1266418124-sup-6308@ben-laptop>\r
  49         <3wd3a0z7jjv.fsf@mhdcelk-nx01.amd.com>\r
  50         <1266435265-sup-5024@ben-laptop>\r
  51         <20100217235211.GC2628@lapse.rw.madduck.net>\r
  52         <1266453115-sup-7880@ben-laptop>\r
  53         <20100218015847.GB3480@lapse.rw.madduck.net>\r
  54         <1266459453-sup-7234@ben-laptop>\r
  55         <20100218024802.GA795@lapse.rw.madduck.net>\r
  56         <1266463007-sup-8777@ben-laptop>\r
  57         <20100218034613.GD1991@lapse.rw.madduck.net>\r
  58 Date: Wed, 17 Feb 2010 23:44:27 -0500\r
  59 Message-Id: <1266467977-sup-3504@ben-laptop>\r
  60 User-Agent: Sup/git\r
  61 Content-Transfer-Encoding: 8bit\r
  62 Cc: notmuch <notmuch@notmuchmail.org>\r
  63 Subject: Re: [notmuch] nested tag trees (was:  Mail in git)\r
  64 X-BeenThere: notmuch@notmuchmail.org\r
  65 X-Mailman-Version: 2.1.13\r
  66 Precedence: list\r
  67 List-Id: "Use and development of the notmuch mail system."\r
  68         <notmuch.notmuchmail.org>\r
  69 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  70         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  71 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  72 List-Post: <mailto:notmuch@notmuchmail.org>\r
  73 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  74 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  75         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  76 X-List-Received-Date: Thu, 18 Feb 2010 04:44:31 -0000\r
  77 \r
  78 Excerpts from martin f krafft's message of Wed Feb 17 22:46:13 -0500 2010:\r
  79 > You ought to have sent to the list, and I want to send mine there\r
  80 > too, so please give permission.\r
  81 > \r
  82 Oops! Sorry about that. Damn you sup.\r
  83 \r
  84 > also sprach Ben Gamari <bgamari@gmail.com> [2010.02.18.1620 +1300]:\r
  85 > > This is a very good point. From what I've read about the database\r
  86 > > format, I can't think of any way that reverse dependencies could be\r
  87 > > easily found, unfortunately. If there really is no way to do this, then\r
  88 > > we could have a problem. I'm not sure rewriting tens of megabytes\r
  89 > > everytime you receive a mail message is acceptable.\r
  90 > \r
  91 > You would not need to do that, since the messages don't change, and\r
  92 > thus their blobs remain the same.\r
  93 \r
  94 I believe you would. The problem isn't the messages (well, that's a\r
  95 problem too), it's the fact that\r
  96 the tree (e.g. tab) objects which reference the messages are immutable\r
  97 (I believe). This presents us with the difficult\r
  98 circumstance of being unable to modify a tag after it has been created.\r
  99 Therefore, as far as I can tell, we need to rewrite the tag's tree\r
 100 object whenever we add or remove a message. This was the reason I\r
 101 suggested nesting tag trees, although this only partially solves the\r
 102 issue.\r
 103 \r
 104 (Please correct me if I'm wrong about any/all of the above)\r
 105 \r
 106 > \r
 107 > However, for every manipulation of a message, you would need to\r
 108 > iterate *all* tag trees (O(n)) and update the ones referencing the\r
 109 > message (also O(n)).\r
 110 > \r
 111 This is definitely an issue.\r
 112 \r
 113 > This can probably be further optimised, but still: it's not quite as\r
 114 > nice as enumerating all parents of a message in O(1) time (which\r
 115 > would still result in O(m×n)).\r
 116 > \r
 117 Yeah, I'm not sure how well this would scale on truly massive\r
 118 mail stores.\r
 119 \r
 120 Cheers,\r
 121 \r
 122 - Ben\r