From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by olra.theworths.org (Postfix) with ESMTP id B9661431FBC for ; Wed, 17 Feb 2010 20:44:31 -0800 (PST) X-Virus-Scanned: Debian amavisd-new at olra.theworths.org X-Spam-Flag: NO X-Spam-Score: -0.974 X-Spam-Level: X-Spam-Status: No, score=-0.974 tagged_above=-999 required=5 tests=[AWL=-0.789, BAYES_40=-0.185] autolearn=ham Received: from olra.theworths.org ([127.0.0.1]) by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id CzZUaGzf54Jg for ; Wed, 17 Feb 2010 20:44:31 -0800 (PST) Received: from qw-out-1920.google.com (qw-out-1920.google.com [74.125.92.144]) by olra.theworths.org (Postfix) with ESMTP id 04582431FAE for ; Wed, 17 Feb 2010 20:44:30 -0800 (PST) Received: by qw-out-1920.google.com with SMTP id 5so1086404qwc.32 for ; Wed, 17 Feb 2010 20:44:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:content-type:cc:subject:from :to:in-reply-to:references:date:message-id:user-agent :content-transfer-encoding; bh=GRD4BAqbUKQunavcWYHGuW2NZ/RRiY7Kzj6AyFERhYA=; b=Owk9FeRENbbcSh01fpB0doWcqX/UeVTOVp3yRvwPuDYKcudsyI5dWmBFu6UTFNdJGK DPxXe1i7MMfY+cu7L7v20rs79ydf1/x+7Ikt3eY/8nAKaWGDO+9A9u903MTR2uR/deU3 SK8igk98HJrvvRpfuQa2hq+Rtc1z6xj0mvBO0= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=content-type:cc:subject:from:to:in-reply-to:references:date :message-id:user-agent:content-transfer-encoding; b=F65mEzBKma1TBIgulfNh06tm1OPFLaJBSHTcQJXE3FxsctTXfqIA/fopapb3dS8afg PGfeausr5DJ96aA54wnXMOSeoCkL6w0k9R6ZUjQJ1DEHh9SuiIXFces5ZIH3aw0u3TKR IZr5wlWTs6jAhR0Odv1Zlbu9B4rpOJNqROXkU= Received: by 10.224.59.224 with SMTP id m32mr4983242qah.76.1266468270336; Wed, 17 Feb 2010 20:44:30 -0800 (PST) Received: from localhost (pool-96-236-125-203.spfdma.east.verizon.net [96.236.125.203]) by mx.google.com with ESMTPS id 2sm19574976qwi.35.2010.02.17.20.44.28 (version=TLSv1/SSLv3 cipher=RC4-MD5); Wed, 17 Feb 2010 20:44:29 -0800 (PST) Content-Type: text/plain; charset=UTF-8 From: Ben Gamari To: martin f krafft In-reply-to: <20100218034613.GD1991@lapse.rw.madduck.net> References: <20100217012101.GD8249@lapse.rw.madduck.net> <1266418124-sup-6308@ben-laptop> <3wd3a0z7jjv.fsf@mhdcelk-nx01.amd.com> <1266435265-sup-5024@ben-laptop> <20100217235211.GC2628@lapse.rw.madduck.net> <1266453115-sup-7880@ben-laptop> <20100218015847.GB3480@lapse.rw.madduck.net> <1266459453-sup-7234@ben-laptop> <20100218024802.GA795@lapse.rw.madduck.net> <1266463007-sup-8777@ben-laptop> <20100218034613.GD1991@lapse.rw.madduck.net> Date: Wed, 17 Feb 2010 23:44:27 -0500 Message-Id: <1266467977-sup-3504@ben-laptop> User-Agent: Sup/git Content-Transfer-Encoding: 8bit Cc: notmuch Subject: Re: nested tag trees (was: Mail in git) X-BeenThere: notmuch@notmuchmail.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: "Use and development of the notmuch mail system." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 18 Feb 2010 04:44:31 -0000 Excerpts from martin f krafft's message of Wed Feb 17 22:46:13 -0500 2010: > You ought to have sent to the list, and I want to send mine there > too, so please give permission. > Oops! Sorry about that. Damn you sup. > also sprach Ben Gamari [2010.02.18.1620 +1300]: > > This is a very good point. From what I've read about the database > > format, I can't think of any way that reverse dependencies could be > > easily found, unfortunately. If there really is no way to do this, then > > we could have a problem. I'm not sure rewriting tens of megabytes > > everytime you receive a mail message is acceptable. > > You would not need to do that, since the messages don't change, and > thus their blobs remain the same. I believe you would. The problem isn't the messages (well, that's a problem too), it's the fact that the tree (e.g. tab) objects which reference the messages are immutable (I believe). This presents us with the difficult circumstance of being unable to modify a tag after it has been created. Therefore, as far as I can tell, we need to rewrite the tag's tree object whenever we add or remove a message. This was the reason I suggested nesting tag trees, although this only partially solves the issue. (Please correct me if I'm wrong about any/all of the above) > > However, for every manipulation of a message, you would need to > iterate *all* tag trees (O(n)) and update the ones referencing the > message (also O(n)). > This is definitely an issue. > This can probably be further optimised, but still: it's not quite as > nice as enumerating all parents of a message in O(1) time (which > would still result in O(m×n)). > Yeah, I'm not sure how well this would scale on truly massive mail stores. Cheers, - Ben