You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@couchdb.apache.org by Jedediah Smith <je...@silencegreys.com> on 2008/11/24 07:57:34 UTC

threaded email view

I'm using CouchDB to store and process emails.

Every email has a "message-id" header field containing a globally unique 
identifier and zero or more "references" and "in-reply-to" fields, each 
of which contains the message-id of a different message.

To construct a threaded view, a tree structure is built using 
"references" and "in-reply-to" as parent links. This implies that a 
message can have more than one parent, in which case it would appear 
multiple times in the view.

I would like to have a CouchDB view that allows me to easily construct 
threads in this way. Specifically, given a particular message, I want to 
get all of its directly or indirectly connected messages. Messages don't 
need to be in any particular order within a thread. It can be assumed 
that a thread contains a small number of messages, say <100

The view might have one or more other key fields (e.g. date) which will 
be used to sort the threads or restrict the range. When a range is 
given, the view returns all messages from each thread that contains at 
least one message in the range.

I want to be able to handle each of these cases with one request, 
without storing intermediate data in documents.


Re: threaded email view

Posted by Jedediah Smith <je...@silencegreys.com>.
The header fields I mentioned are the only ones available in a typical 
email. If nobody can come up with something, I will resort to adding 
extra data at import time but that would be nice to avoid.

It would be nifty if partially iterative queries like this could be done 
in couchdb and still take advantage of map/reduce.

Chris Anderson wrote:
> On Sun, Nov 23, 2008 at 10:57 PM, Jedediah Smith
> <je...@silencegreys.com> wrote:
>> I'm using CouchDB to store and process emails.
>>
>> Every email has a "message-id" header field containing a globally unique
>> identifier and zero or more "references" and "in-reply-to" fields, each of
>> which contains the message-id of a different message.
> 
> You might have the easiest time providing this view if you can have an
> original-message-for-thread-id that is attached to all messages that
> are replies or references to another message.
> 
> That way you can pull out an entire thread by finding all messages
> that reference the thread-originating message in the parent field(s).
> 
> The method you describe (where each message links only to its
> immediate parent) leaves you no common identifier for an entire
> thread. By linking to the first message in a thread, from all
> subsequent replies, you'll have an easy way to pull all replies
> together in one view.
> 
> I hope this helps.
> 
> Chris
> 
> 

Re: threaded email view

Posted by Chris Anderson <jc...@apache.org>.
On Sun, Nov 23, 2008 at 10:57 PM, Jedediah Smith
<je...@silencegreys.com> wrote:
> I'm using CouchDB to store and process emails.
>
> Every email has a "message-id" header field containing a globally unique
> identifier and zero or more "references" and "in-reply-to" fields, each of
> which contains the message-id of a different message.

You might have the easiest time providing this view if you can have an
original-message-for-thread-id that is attached to all messages that
are replies or references to another message.

That way you can pull out an entire thread by finding all messages
that reference the thread-originating message in the parent field(s).

The method you describe (where each message links only to its
immediate parent) leaves you no common identifier for an entire
thread. By linking to the first message in a thread, from all
subsequent replies, you'll have an easy way to pull all replies
together in one view.

I hope this helps.

Chris


-- 
Chris Anderson
http://jchris.mfdz.com

Re: threaded email view

Posted by Thomas Kerpe <th...@googlemail.com>.
Yeah, you are right.
I find it useful to have a common "thread-id" but this is optional.

//Thomas



2008/11/27 Chris Anderson <jc...@apache.org>

> On Thu, Nov 27, 2008 at 6:06 AM, Thomas Kerpe
> <th...@googlemail.com> wrote:
> >
> > function(doc) {
> >  if (doc.type == "email") {
> >    thread = [];
> >    if (doc.header.references){
> >      thread = doc.header.references.split(" ");
> >    }
> >    thread.push(doc.header['message-id']);
> >    thread_id = thread[0];
> >    emit([thread_id, thread,], doc.header.subject);
> >  }
> > }
> >
> > //Thomas
> >
>
> I'd like to dig into this deeper. I'm not sure I understand what the
> second element in the emitted key is useful for. Could you just
> emit(thread, doc.header.subject) and skip the explicit thread_id?
> Group reduce should will interact nicely with that.
>
> I think this problem is similar to that of storing document versions
> (like for a wiki). Each version must link to it's parent, but also to
> the original version. I'm not familiar enough with email but
> doc.header.references sounds like it can do the job.
>
> I suppose the analog in versioned docs would be keeping a list of the
> chain of parents in each new doc (and not just the head of the chain
> and immediate parent.)
>
> --
> Chris Anderson
> http://jchris.mfdz.com
>

Re: threaded email view

Posted by Thomas Kerpe <th...@googlemail.com>.
I have created a temporary couchdb with testmessges, replicate this if you
need testmessages.

http://67.202.48.84:5984/testmail/
//Thomas

2008/11/27 Chris Anderson <jc...@apache.org>

> On Thu, Nov 27, 2008 at 6:06 AM, Thomas Kerpe
> <th...@googlemail.com> wrote:
> >
> > function(doc) {
> >  if (doc.type == "email") {
> >    thread = [];
> >    if (doc.header.references){
> >      thread = doc.header.references.split(" ");
> >    }
> >    thread.push(doc.header['message-id']);
> >    thread_id = thread[0];
> >    emit([thread_id, thread,], doc.header.subject);
> >  }
> > }
> >
> > //Thomas
> >
>
> I'd like to dig into this deeper. I'm not sure I understand what the
> second element in the emitted key is useful for. Could you just
> emit(thread, doc.header.subject) and skip the explicit thread_id?
> Group reduce should will interact nicely with that.
>
> I think this problem is similar to that of storing document versions
> (like for a wiki). Each version must link to it's parent, but also to
> the original version. I'm not familiar enough with email but
> doc.header.references sounds like it can do the job.
>
> I suppose the analog in versioned docs would be keeping a list of the
> chain of parents in each new doc (and not just the head of the chain
> and immediate parent.)
>
> --
> Chris Anderson
> http://jchris.mfdz.com
>

Re: threaded email view

Posted by Chris Anderson <jc...@apache.org>.
On Thu, Nov 27, 2008 at 6:06 AM, Thomas Kerpe
<th...@googlemail.com> wrote:
>
> function(doc) {
>  if (doc.type == "email") {
>    thread = [];
>    if (doc.header.references){
>      thread = doc.header.references.split(" ");
>    }
>    thread.push(doc.header['message-id']);
>    thread_id = thread[0];
>    emit([thread_id, thread,], doc.header.subject);
>  }
> }
>
> //Thomas
>

I'd like to dig into this deeper. I'm not sure I understand what the
second element in the emitted key is useful for. Could you just
emit(thread, doc.header.subject) and skip the explicit thread_id?
Group reduce should will interact nicely with that.

I think this problem is similar to that of storing document versions
(like for a wiki). Each version must link to it's parent, but also to
the original version. I'm not familiar enough with email but
doc.header.references sounds like it can do the job.

I suppose the analog in versioned docs would be keeping a list of the
chain of parents in each new doc (and not just the head of the chain
and immediate parent.)

-- 
Chris Anderson
http://jchris.mfdz.com

Re: threaded email view

Posted by Jan Lehnardt <ja...@apache.org>.
In case somebody hasn't read this one:

http://www.jwz.org/doc/threading.html :)

Cheers
Jan
--
On 28 Nov 2008, at 02:53, Thomas Kerpe wrote:

> This is an old Problem. Most Clients set this References Header. One  
> way
> would be (and some E-Mail-Programs do this) to group by subject,  
> this is of
> course easy, you have to remove the Re: and Aw: etc and emit that as  
> key.
> E-Mail threading problem is not new and there is no 100% relyable  
> way to do
> this. Most programs set the References header, also most the In- 
> Reply-To
> Header. I have tested this and the results are good. However you can  
> never
> be shure. This approach is called strict_threads in the mutt  
> documentation,
> while the subject only approach is called pseudo threads.
>
> When using just the In-Reply-To header it will not be so easy  
> because you
> only get the direct "parent". Without iterating over the map results  
> again
> you don't get these (you can not do this in one iteration with map/ 
> reduce I
> think).
>
> The Problem gets even more worse as the RFC says the Message-ID  
> SHOULD be
> used, this is not mandatory but it is common sense to use this. Some
> E-Mail-Servers add an Message-ID if it has not one.
> In one case the RFC says no References header should be used: when a  
> message
> has more than one single parent.
>
> //Thomas
>
> 2008/11/28 Jedediah Smith <je...@silencegreys.com>
>
>>
>> This works if emails always list all of their ancestors in the  
>> references
>> field. If that is indeed the case then I wasn't aware of it and it  
>> certainly
>> makes my task simpler.
>>
>> I am however still interested in the case where nodes of a data  
>> structure
>> only link to their immediate parent, just or the sake of discussion.
>>
>>
>> Thomas Kerpe wrote:
>>
>>> Hoops, sorry for that html and broken Text-part:
>>>
>>> function(doc) {
>>> if (doc.type == "email") {
>>>  thread = [];
>>>  if (doc.header.references){
>>>    thread = doc.header.references.split(" ");
>>>  }
>>>  thread.push(doc.header['message-id']);
>>>  thread_id = thread[0];
>>>  emit([thread_id, thread,], doc.header.subject);
>>> }
>>> }
>>>
>>> //Thomas
>>>
>>


Re: threaded email view

Posted by Thomas Kerpe <th...@googlemail.com>.
This is an old Problem. Most Clients set this References Header. One way
would be (and some E-Mail-Programs do this) to group by subject, this is of
course easy, you have to remove the Re: and Aw: etc and emit that as key.
E-Mail threading problem is not new and there is no 100% relyable way to do
this. Most programs set the References header, also most the In-Reply-To
Header. I have tested this and the results are good. However you can never
be shure. This approach is called strict_threads in the mutt documentation,
while the subject only approach is called pseudo threads.

When using just the In-Reply-To header it will not be so easy because you
only get the direct "parent". Without iterating over the map results again
you don't get these (you can not do this in one iteration with map/reduce I
think).

The Problem gets even more worse as the RFC says the Message-ID SHOULD be
used, this is not mandatory but it is common sense to use this. Some
E-Mail-Servers add an Message-ID if it has not one.
In one case the RFC says no References header should be used: when a message
has more than one single parent.

//Thomas

2008/11/28 Jedediah Smith <je...@silencegreys.com>

>
> This works if emails always list all of their ancestors in the references
> field. If that is indeed the case then I wasn't aware of it and it certainly
> makes my task simpler.
>
> I am however still interested in the case where nodes of a data structure
> only link to their immediate parent, just or the sake of discussion.
>
>
> Thomas Kerpe wrote:
>
>> Hoops, sorry for that html and broken Text-part:
>>
>> function(doc) {
>>  if (doc.type == "email") {
>>    thread = [];
>>    if (doc.header.references){
>>      thread = doc.header.references.split(" ");
>>    }
>>    thread.push(doc.header['message-id']);
>>    thread_id = thread[0];
>>    emit([thread_id, thread,], doc.header.subject);
>>  }
>> }
>>
>> //Thomas
>>
>

Re: threaded email view

Posted by Jedediah Smith <je...@silencegreys.com>.
There is also the question of how to sort by thread and also sort the 
threads by date. I'm having trouble with that. The only thing I can 
think of is to add the date of the thread root message to all thread 
members.

Chris Anderson wrote:
> On Fri, Nov 28, 2008 at 2:58 AM, Chris Anderson <jc...@apache.org> wrote:
>> I don't think there is an easy way to traverse a linked list of
>> couchdb documents. Tell me if you think of a way.
>>
> 
> Unless of course you include the root doc id in all list member docs.
> Then you can get a whole thread in a single view query.
> 

Re: threaded email view

Posted by Chris Anderson <jc...@apache.org>.
On Fri, Nov 28, 2008 at 2:58 AM, Chris Anderson <jc...@apache.org> wrote:
> I don't think there is an easy way to traverse a linked list of
> couchdb documents. Tell me if you think of a way.
>

Unless of course you include the root doc id in all list member docs.
Then you can get a whole thread in a single view query.

Re: threaded email view

Posted by Chris Anderson <jc...@apache.org>.
On Thu, Nov 27, 2008 at 5:32 PM, Jedediah Smith
<je...@silencegreys.com> wrote:
>
> I am however still interested in the case where nodes of a data structure
> only link to their immediate parent, just or the sake of discussion.
>

I don't think there is an easy way to traverse a linked list of
couchdb documents. Tell me if you think of a way.

-- 
Chris Anderson
http://jchris.mfdz.com

Re: threaded email view

Posted by Jedediah Smith <je...@silencegreys.com>.
This works if emails always list all of their ancestors in the 
references field. If that is indeed the case then I wasn't aware of it 
and it certainly makes my task simpler.

I am however still interested in the case where nodes of a data 
structure only link to their immediate parent, just or the sake of 
discussion.

Thomas Kerpe wrote:
> Hoops, sorry for that html and broken Text-part:
> 
> function(doc) {
>   if (doc.type == "email") {
>     thread = [];
>     if (doc.header.references){
>       thread = doc.header.references.split(" ");
>     }
>     thread.push(doc.header['message-id']);
>     thread_id = thread[0];
>     emit([thread_id, thread,], doc.header.subject);
>   }
> }
> 
> //Thomas

Re: threaded email view

Posted by Thomas Kerpe <th...@googlemail.com>.
Hoops, sorry for that html and broken Text-part:

function(doc) {
   if (doc.type == "email") {
     thread = [];
     if (doc.header.references){
       thread = doc.header.references.split(" ");
     }
     thread.push(doc.header['message-id']);
     thread_id = thread[0];
     emit([thread_id, thread,], doc.header.subject);
   }
}

//Thomas

Am 27.11.2008 13:16 Uhr, Thomas Kerpe schrieb:
> Jedediah,
>
> This should be really easy. When you have for shure unique Message-IDs 
> you can let identify your threads and single messages with them. Your 
> map will emit
>
> function(doc) {
> if (doc.header.references){
> thread = doc.header.references.split(" ");
> thread.push(doc.header['message-id']);
> thread_id = thread[0];
> } else {
> thread = [doc.header['message-id']];
> thread_id = doc.header['message-id'];
> }
> emit([thread_id, thread, ], null);
> }
>
> In this way you can build your indexes. Maybe add a date or the sender 
> adddress to your key. In this way you can get whole threads by knowing 
> only one message ID.
>
>
> HTH,
> //Thomas
>
> 2008/11/24 Jedediah Smith <jedediah@silencegreys.com 
> <ma...@silencegreys.com>>
>
>     I'm using CouchDB to store and process emails.
>
>     Every email has a "message-id" header field containing a globally
>     unique identifier and zero or more "references" and "in-reply-to"
>     fields, each of which contains the message-id of a different message.
>
>     To construct a threaded view, a tree structure is built using
>     "references" and "in-reply-to" as parent links. This implies that
>     a message can have more than one parent, in which case it would
>     appear multiple times in the view.
>
>     I would like to have a CouchDB view that allows me to easily
>     construct threads in this way. Specifically, given a particular
>     message, I want to get all of its directly or indirectly connected
>     messages. Messages don't need to be in any particular order within
>     a thread. It can be assumed that a thread contains a small number
>     of messages, say <100
>
>     The view might have one or more other key fields (e.g. date) which
>     will be used to sort the threads or restrict the range. When a
>     range is given, the view returns all messages from each thread
>     that contains at least one message in the range.
>
>     I want to be able to handle each of these cases with one request,
>     without storing intermediate data in documents.
>
>


Re: threaded email view

Posted by Thomas Kerpe <th...@googlemail.com>.
Jedediah,
This should be really easy. When you have for shure unique Message-IDs you
can let identify your threads and single messages with them. Your map will
emit

function(doc) { if (doc.header.references){ thread =
doc.header.references.split(" "); thread.push(doc.header['message-id']);
thread_id = thread[0]; } else { thread = [doc.header['message-id']];
thread_id = doc.header['message-id']; } emit([thread_id, thread, ], null); }

In this way you can build your indexes. Maybe add a date or the sender
adddress to your key. In this way you can get whole threads by knowing only
one message ID.


HTH,
//Thomas

2008/11/24 Jedediah Smith <je...@silencegreys.com>

> I'm using CouchDB to store and process emails.
>
> Every email has a "message-id" header field containing a globally unique
> identifier and zero or more "references" and "in-reply-to" fields, each of
> which contains the message-id of a different message.
>
> To construct a threaded view, a tree structure is built using "references"
> and "in-reply-to" as parent links. This implies that a message can have more
> than one parent, in which case it would appear multiple times in the view.
>
> I would like to have a CouchDB view that allows me to easily construct
> threads in this way. Specifically, given a particular message, I want to get
> all of its directly or indirectly connected messages. Messages don't need to
> be in any particular order within a thread. It can be assumed that a thread
> contains a small number of messages, say <100
>
> The view might have one or more other key fields (e.g. date) which will be
> used to sort the threads or restrict the range. When a range is given, the
> view returns all messages from each thread that contains at least one
> message in the range.
>
> I want to be able to handle each of these cases with one request, without
> storing intermediate data in documents.
>
>