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 A5C48431FBC for ; Wed, 17 Feb 2010 20:34:53 -0800 (PST) X-Virus-Scanned: Debian amavisd-new at olra.theworths.org X-Spam-Flag: NO X-Spam-Score: -2.101 X-Spam-Level: X-Spam-Status: No, score=-2.101 tagged_above=-999 required=5 tests=[AWL=0.498, BAYES_00=-2.599] 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 H4ovxZ6vXOQE for ; Wed, 17 Feb 2010 20:34:52 -0800 (PST) Received: from clegg.madduck.net (clegg.madduck.net [193.242.105.96]) by olra.theworths.org (Postfix) with ESMTP id 74C19431FAE for ; Wed, 17 Feb 2010 20:34:52 -0800 (PST) Received: from lapse.rw.madduck.net (unknown [IPv6:2404:130:0:1000:20a:e4ff:fe30:4316]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "lapse.rw.madduck.net", Issuer "CAcert Class 3 Root" (verified OK)) by clegg.madduck.net (postfix) with ESMTPS id 798611D409C for ; Thu, 18 Feb 2010 05:34:48 +0100 (CET) Received: by lapse.rw.madduck.net (Postfix, from userid 1000) id 6F57324C; Thu, 18 Feb 2010 17:34:49 +1300 (NZDT) Date: Thu, 18 Feb 2010 17:34:49 +1300 From: martin f krafft To: notmuch discussion list Message-ID: <20100218043449.GB4127@lapse.rw.madduck.net> Mail-Followup-To: notmuch discussion list 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> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-ripemd160; protocol="application/pgp-signature"; boundary="uZ3hkaAS1mZxFaxD" Content-Disposition: inline In-Reply-To: <1266463007-sup-8777@ben-laptop> X-Motto: Keep the good times rollin' X-OS: Debian GNU/Linux squeeze/sid kernel 2.6.32-1-686 i686 X-Spamtrap: madduck.bogus@madduck.net X-Subliminal-Message: debian/rules! User-Agent: Mutt/1.5.20 (2009-06-14) X-Virus-Scanned: clamav-milter 0.95.3 at clegg X-Virus-Status: Clean 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:34:53 -0000 --uZ3hkaAS1mZxFaxD Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable [Taking a private message back to the list with permission] 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. 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)). The entire process will still be O(n) per message, and O(m=D7n) for all: messages=3D[list of messages] add_tags=3D[list of tags to add] remove_tags=3D[list of tags to remove] tagtrees=3D[all tag trees] trees_to_update=3D[] for t in remove_tags: if intersection(t.tree.children, messages): T =3D new_tree(t.name) write_tree(T, t.tree.children - messages) write_tree(t.tree, []) t.tree =3D T for t in add_tags: t.tree =3D new_tree(t.name) rewrite_tree(t.tree, messages) 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=D7n)). --=20 martin | http://madduck.net/ | http://two.sentenc.es/ =20 "... (ethik und =E4sthetik sind eins.)" -- wittgenstein =20 spamtraps: madduck.bogus@madduck.net --uZ3hkaAS1mZxFaxD Content-Type: application/pgp-signature; name="digital_signature_gpg.asc" Content-Description: Digital signature (see http://martin-krafft.net/gpg/) Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.10 (GNU/Linux) iEYEAREDAAYFAkt8w2kACgkQIgvIgzMMSnVLbgCgwlpf6fA/o7KJsneecT3ACwNU 0VIAoLOGCyP8AdClLybXpA2es+soXZSZ =KEWJ -----END PGP SIGNATURE----- --uZ3hkaAS1mZxFaxD--