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=
Content-Type: text/plain; charset=UTF-8
From: Ben Gamari <bgamari@gmail.com>
To: martin f krafft <madduck@madduck.net>
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 <notmuch@notmuchmail.org>
Subject: Re: [notmuch] nested tag trees (was:  Mail in git)
Precedence: list

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 <bgamari@gmail.com> [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