Date: Thu, 18 Feb 2010 17:34:49 +1300
From: martin f krafft <madduck@madduck.net>
To: notmuch discussion list <notmuch@notmuchmail.org>
Message-ID: <20100218043449.GB4127@lapse.rw.madduck.net>
Mail-Followup-To: notmuch discussion list <notmuch@notmuchmail.org>
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>
User-Agent: Mutt/1.5.20 (2009-06-14)
Subject: Re: [notmuch] nested tag trees (was:  Mail in git)
Precedence: list


--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 <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.

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--