Excerpts from martin f krafft's message of Wed Feb 17 18:52:11 -0500 2010:
> also sprach Ben Gamari <bgamari@gmail.com> [2010.02.18.0834 +1300]:
> > Excerpts from Mark Anderson's message of Wed Feb 17 14:23:48 -0500
> > 2010:
> > > But if we have notmuch as a cache of the tags, then don't we
> > > already know the tree objects that need updating?  Yes, we would
> > > probably need some consistency checks for when things don't work
> > > as planned, but in the common case we ought to always know.
> > > 
> > Cached or not, rewriting would still be an incredibly (e.g.
> > prohibitively or close to it) expensive operation for a large
> > mailstore.
> 
> Why? Well, would involve creating n objects and unlinking n objects
> for n tags, but it would be constant in the number of messages, no?

Yes, it would be linear in number of tags. I suppose if messages
weren't stored in the top-level tree nodes, then it would still be
linear, although with a slope equal to the reciprocal of the fan-out.
This has the potential to be very reasonable performance-wise.

- Ben