--On Saturday, July 12, 2003 3:09 PM +0300 Timo Sirainen <[EMAIL PROTECTED]> wrote:
| Yes, addition is tricky. You could probably optimize it if you kept the | base subjects and message IDs stored permanently in a hash/btree, but | keeping them up to date requires more work and may not be worth it.
If you have clients generating rfc2822 references headers then the addition is not such a bad problem because the references header contains the full (or at least a truncated part) of the thread tree. This allows you to infer the location of messages missing from the mailstore so that when a message with a 'missing' message-id appears you can easily link it in. Not that the current THREAD extension does not expose these 'holes' in the thread tree to clients - instead it collapses a branch across a hole (i.e. it links a child to its grandparent when the parent is missing). I know personally I would like to see 'holes' exposed in my client as that does better represent the actual flow of messages in a thread. In any case, the server can cache the holes in its own cache and optimise message arrival in that case.
The main problem with arrival is when you don't have references (only in-reply-to) or when references has grown large and has been truncated. I believe that these cases should be in the minority so optimising for the majority case is reasonable.
| You should be able to optimize some expunges more easily. Message without | children can just be removed. Message with parent and children requires | rebuilding that one thread, assuming base subject hasn't changed. | Exception to these would be if expunged message had it's message-id | duplicated elsewhere, if that was the case you'd probably have to rebuild | the whole tree again. | | Is the above worth the trouble? I don't know, I doubt I'll try it for a | while.
Expunge is an interesting problem and is similar to message arrival in that the removal of a single message can also dramatically change the thread tree if you reapply the thread algorithm. From a client perspective, when showing a thread view to the user, the client theoretically has to reissue the thread command anytime the mailbox adds or removes messages to stay up to date with the thread tree. In practice a client has to do that for new messages, but can trade accuracy of the thread tree for performance by inferring a simple change to the thread tree when expunge occurs. I take that approach in Mulberry - I internally relink the thread tree for expunged messages rather than reissue a thread command to the server. That does mean the client view of the thread tree may differ from the server view but that is usually a minority case.
-- Cyrus Daboo
