Subject: [imapext] GMail's extensions: X-GM-THRID immutability

From: Jan Kundrát <[email-masked]>
Date: Thu, 09 May 2013 18:27:43 +0200

Hi,
this might be a bit OT for this mailing list, but given that GMail is a rather dominant player among the IMAP service providers and due to the usefulness of having data available to other, I'm posting here anyway.

- It isn't clear to me what the immutability guarantees of the returned data of the X-GM-THRID [1] extension are. It would be terrific if it was safe to cache these values in the same manner as any other immutable per-message data, but I suspect this is not possible -- if the threading is "right", delivery of any new message could potentially join independent threads together, thereby changing the thread IDs. How is GMail handling this? How is the threading computed?

- Any plans to support the THREAD=REFS [2] in GMail?

- Any plans for support of the SORT extensions?

- Any plans for CONTEXT=SORT and CONTEXT=SEARCH? :)

The reason why I'm asking is because I'd like to enable threading for Trojita's users who are accessing GMail. Any threading algorithm apart from THREAD=REFS has significant limitations without a server-side sorting simply because old threads with new arrivals are not listed as recent. The only remedy is giving up and hoping that UIDs somehow correlate with the age of a any message, which is rather crude heuristic.

With kind regards,
Jan

[1] https://developers.google.com/google-apps/gmail/imap_extensions#access_to_the_gmail_thread_id_x-gm-thrid
[2] http://tools.ietf.org/html/draft-ietf-morg-inthread-01

-- 
Trojitá, a fast Qt IMAP e-mail client -- http://trojita.flaska.net/

---

From: Brandon Long <[email-masked]>
Date: Thu, 9 May 2013 14:53:44 -0700

On Thu, May 9, 2013 at 9:27 AM, Jan Kundrát <[email-masked]> wrote:

> Hi,
> this might be a bit OT for this mailing list, but given that GMail is a
> rather dominant player among the IMAP service providers and due to the
> usefulness of having data available to other, I'm posting here anyway.
>
> - It isn't clear to me what the immutability guarantees of the returned
> data of the X-GM-THRID [1] extension are. It would be terrific if it was
> safe to cache these values in the same manner as any other immutable
> per-message data, but I suspect this is not possible -- if the threading is
> "right", delivery of any new message could potentially join independent
> threads together, thereby changing the thread IDs. How is GMail handling
> this? How is the threading computed?
>

You should be able to consider X-GM-THRID as immutable, that should have
been called out in the documents.  We never join threads.

Gmail does not thread by references, its closest to threading by subject.
 Our user facing parlance is typically "conversation" instead of thread.  A
conversation is basically up to 100 messages with the same "clean" subject.
 IIRC, we will start a new conversation if there is sufficient time gap
between the two, but we will use references to put a reply on an old
conversation regardless of time... though the 100 message is a "hard" limit.

Having a limit was chosen for performance reasons, we don't want to load a
couple thousand message indexes from disk or have paging in the
conversation view interface.  The conversation view doesn't lend itself to
true threading either, where "new" messages may be in multiple places in
the page.... and most email communication doesn't have that complicated of
a thread structure to begin with.  It also fixes the typical use cases of
"find a message from foo and reply and change the subject" instead of using
an address book and some other corner cases.

> - Any plans to support the THREAD=REFS [2] in GMail?

So, the new search terms might be interesting.  MESSAGEID is basically how
we handle HEADER MESSAGEID already (ie, its not substring, its actually
mapped to the rfc822messageid: term in our index).  INTHREAD is more odd
because our threads can cross folder boundaries (since they're not folders,
they're labels) but nothing overly complicated for us.

THREAD=REFS is just as unlikely as THREAD=REFERENCES for us.  We're not
computing threads on the fly just for IMAP.  We had one early engineer on
the project joke about implementing THREAD=GMAIL, but the THREAD= concept
seems fundamentally flawed to me that both the client and server require
understanding of the threading algorithm.  X-GM-THRID is basically "the
server knows the threads, trust it".

> - Any plans for support of the SORT extensions?

We have only the single SORT order in everything we do, so no.  Again, we
can't load the entire folder into memory just to SORT it on the server, and
we're not going to pre-compute and store each possible order.  You'll note
there is only the one order in all of the Gmail interfaces.  Our marketing
would say, don't sort, search!

> - Any plans for CONTEXT=SORT and CONTEXT=SEARCH? :)

No.  We'd probably have to create a filter on the fly for CONTEXT=SEARCH,
get updates that the filter has hit, and then load and finish testing
against the new message to see if it actually hit (not all of the IMAP
SEARCH syntax is translatable to our own search syntax, some things require
loading parts of the message).  That just seems like an overall large
effort for supporting "online" low caching clients, and we don't really
support them well in many other ways, mostly because almost all clients are
actually offline caching clients.

>
> The reason why I'm asking is because I'd like to enable threading for
> Trojita's users who are accessing GMail. Any threading algorithm apart from
> THREAD=REFS has significant limitations without a server-side sorting
> simply because old threads with new arrivals are not listed as recent. The
> only remedy is giving up and hoping that UIDs somehow correlate with the
> age of a any message, which is rather crude heuristic.
>

What does "old thread with new arrivals are not listed as recent" mean?
 New messages are clearly new, since they have newer UIDs (well, new to
that folder at least).  We always display messages in our "threads" in
INTERNALDATE order.

Brandon

>
> With kind regards,
> Jan
>
> [1] https://developers.google.com/**google-apps/gmail/imap_**
> extensions#access_to_the_**gmail_thread_id_x-gm-thrid<https://developers.google.com/google-apps/gmail/imap_extensions#access_to_the_gmail_thread_id_x-gm-thrid>
> [2] http://tools.ietf.org/html/**draft-ietf-morg-inthread-01<http://tools.ietf.org/html/draft-ietf-morg-inthread-01>
>
> --
> ______________________________**_________________
> imapext mailing list
> [email-masked]
> https://www.ietf.org/mailman/**listinfo/imapext<https://www.ietf.org/mailman/listinfo/imapext>
>

---

From: Jan Kundrát <[email-masked]>
Date: Fri, 10 May 2013 12:51:02 +0200

> been called out in the documents.  We never join threads.

Thanks, this answers my question perfectly.

> but the THREAD= concept
> understanding of the threading algorithm.

Could you elaborate a bit? Trojita does not have any builtin knowledge of any threading algorithm, yet will happily issue and use THREAD={REFS,REFERENCES,ORDEREDSUBJECT} and display the result to the user. It works pretty well, actually. Best when combined with Dovecot due to its THREAD=REFS support.

Yes, this means that upon an arrival of a new message, it has to ask for the threading info for a whole mailbox again simply because we might not know the Message-Id of the existing threads, and therefore cannot replicate the server's algorithm. This is the "joy" of lazy loading in action :(.

I've tried to address this waste of bandwidth by the INCTHREAD proposal [1], but I didn't have time to push for its inclusion in FLOSS IMAP servers yet.

> What does "old thread with new arrivals are not listed as recent" mean?

THREAD=REFERENCES and THREAD=ORDEREDSUBJECT both sort the list of threads by the INTERNALDATE of the thread root. Trojita will always display the threads in the order in which the THREAD response contained them. This means that an old thread which receives a new response will still be listed midway through the list of all threads, not at the end. Effectively, this means that these algorithms are rather useless for a client which wants to rely on server-side threading.

Situation is much better with THREAD=REFS because the threads are sorted by the most recent message in asubthread, not by the timestamp of the thread root. When a new message arrives, the whole thread is brought to the end of the THREAD response and the client knows that it shall be shown as a recent one.

In Trojita, the ENVELOPE and INTERNALDATE are lazily loaded, fetched only for currently visible messages (with some preload). We don't fetch these for each message in a 100k mailbox for obvious reasons. However, this means that we cannot reliably post-process the THREAD response by sorting the threads according to the latest message in them.

> that folder at least).

That's a good heuristic, thanks for suggesting that. It breaks when I copy/move and old thread from my INBOX into some specific mailbox -- even though the new mailbox probably contains newer messages, the old thread would be displayed at the end, among the recent ones, due to the higher UIDs. Still, I agree that it's better than having truly new messages sunk deep withing the mailbox history. I'll have a look at implementing this for algorithms other than THREAD=REFS.

> We always display messages in our "threads" in INTERNALDATE order.

I agree that this is (or at least *should*) be the only useful sort order. I tend to agree with your marketing department in thinking that sorting by e.g. the sender in order to find messages from a particular person is, well, dumb.

Do you handle the INTERNALDATE in conformance with the SHOULDs in RFC3501 (i.e. they don't have to correlate with the order of UIDs, but truly reflect the arrival of the message *to your server*, not to a *mailbox*)? Do you also sort the "threads" themselves according to the INTERNALDATE of the newest message in each thread? If so, could you make *this* feature available over IMAP? I don't care for being able to sort by sender or subject, but I do care for being able to reliably show truly recent messages at the bottom (or top) of the view.

With kind regards,
Jan

[1] http://tools.ietf.org/html/draft-kundrat-incthread-01

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Fri, 10 May 2013 18:02:01 +0200

Refs can be computed at delivery time. You have to sort the lines at read time, that is all.

Arnt

---

From: Brandon Long <[email-masked]>
Date: Fri, 10 May 2013 13:41:49 -0700

On Fri, May 10, 2013 at 3:51 AM, Jan Kundrát <[email-masked]> wrote:

> Could you elaborate a bit? Trojita does not have any builtin knowledge of
> any threading algorithm, yet will happily issue and use
> THREAD={REFS,REFERENCES,**ORDEREDSUBJECT} and display the result to the
> user. It works pretty well, actually. Best when combined with Dovecot due
> to its THREAD=REFS support.
>

Why else would the threading model need to be so specified and have
multiple choices?  My assumption was because it allowed the client to know
where a message it appended to the server (or maybe copied to another
folder) would end up in the threading.  Or even that it could just download
the new messages in the folder and update the local thread information and
know it was in-sync with the server.

> Yes, this means that upon an arrival of a new message, it has to ask for
> the threading info for a whole mailbox again simply because we might not
> know the Message-Id of the existing threads, and therefore cannot replicate
> the server's algorithm. This is the "joy" of lazy loading in action :(.
>

I would think with THREAD=REFS, you can download the headers and lookup the
possible matches using a SEARCH HEADER MESSAGE-ID construct to find the
other messages.

I've tried to address this waste of bandwidth by the INCTHREAD proposal
> [1], but I didn't have time to push for its inclusion in FLOSS IMAP servers
> yet.
>
> THREAD=REFERENCES and THREAD=ORDEREDSUBJECT both sort the list of threads
> by the INTERNALDATE of the thread root. Trojita will always display the
> threads in the order in which the THREAD response contained them. This
> means that an old thread which receives a new response will still be listed
> midway through the list of all threads, not at the end. Effectively, this
> means that these algorithms are rather useless for a client which wants to
> rely on server-side threading.
>
> Situation is much better with THREAD=REFS because the threads are sorted
> by the most recent message in asubthread, not by the timestamp of the
> thread root. When a new message arrives, the whole thread is brought to the
> end of the THREAD response and the client knows that it shall be shown as a
> recent one.
>
> In Trojita, the ENVELOPE and INTERNALDATE are lazily loaded, fetched only
> for currently visible messages (with some preload). We don't fetch these
> for each message in a 100k mailbox for obvious reasons. However, this means
> that we cannot reliably post-process the THREAD response by sorting the
> threads according to the latest message in them.

Ah, yes, we sort threads in our interface by the INTERNALDATE of the latest
message in the thread.

> That's a good heuristic, thanks for suggesting that. It breaks when I
> copy/move and old thread from my INBOX into some specific mailbox -- even
> though the new mailbox probably contains newer messages, the old thread
> would be displayed at the end, among the recent ones, due to the higher
> UIDs. Still, I agree that it's better than having truly new messages sunk
> deep withing the mailbox history. I'll have a look at implementing this for
> algorithms other than THREAD=REFS.
>
> I agree that this is (or at least *should*) be the only useful sort order.
> I tend to agree with your marketing department in thinking that sorting by
> e.g. the sender in order to find messages from a particular person is,
> well, dumb.
>
> Do you handle the INTERNALDATE in conformance with the SHOULDs in RFC3501
> (i.e. they don't have to correlate with the order of UIDs, but truly
> reflect the arrival of the message *to your server*, not to a *mailbox*)?
> Do you also sort the "threads" themselves according to the INTERNALDATE of
> the newest message in each thread? If so, could you make *this* feature
> available over IMAP? I don't care for being able to sort by sender or
> subject, but I do care for being able to reliably show truly recent
> messages at the bottom (or top) of the view.
>

We just mapped INTERNALDATE to our "received time" for the message, so
checking if that corresponds to the SHOULDs... yes, those should all be
true.  We have "implementation defined" exceptions when messages are
migrated where we sometimes have to try and infer the original received
time which may fall back to the Date: header in the worst case, but for all
regular delivery, its the time of delivery.

Yes, threads are sorted by the INTERNALDATE of the newest message in the
thread.  Our internal message-id (X-GM-MSGID) is based on the date
received, and the original thread-id (which is exposed as X-GM-THRID) is
the same as the message-id of the first message on the thread.  We also
have a concept of "latest thread-id" which is the message-id of the latest
message on the thread, but we chose not to expose that since then the
X-GM-THRID would not be immutable, since its updated whenever the thread
gets a new message.  And we may be moving away from that anyways and just
using the original threadid with some other mechanism for forcing proper
sort order on the thread, so it doesn't seem likely to get exposed via IMAP
at this point.

Brandon

---

From: Cyrus Daboo <[email-masked]>
Date: Fri, 10 May 2013 20:57:25 -0400

Hi Brandon,

--On May 10, 2013 1:41:49 PM -0700 Brandon Long <[email-masked]> wrote:

> multiple choices?  My assumption was because it allowed the client to
> know where a message it appended to the server (or maybe copied to
> another folder) would end up in the threading.  Or even that it could
> just download the new messages in the folder and update the local thread
> information and know it was in-sync with the server.

Also disconnected clients - they may need to thread messages without 
support from the server and ideally would want to use the same threading 
algorithm as the server when displaying messages whilst offline. Indeed, 
when I implemented THREAD in Mulberry I copied the REFERENCES algorithm for 
use client-side.

-- 
Cyrus Daboo

---

From: Jan Kundrát <[email-masked]>
Date: Wed, 15 May 2013 17:52:46 +0200

> know it was in-sync with the server.

I agree that it is good to have the threading algorithm well-specified. However, for me, the only bonus of the server-side threading is that it allows for threading of messages which have not been downloaded yet. The idea is that transferring a list of threading is cheaper than fetching the required headers for all messages.

> possible matches using a SEARCH HEADER MESSAGE-ID construct to find the

True, but this leads to the O(n) latency (the pathologic case are deep ancient threads with the "References" header all containing just a single message). That's a lot of round trips.

> Ah, yes, we sort threads in our interface by the INTERNALDATE of the latest
[...]
> And we may be moving away from that anyways and just

From what you said, it looks like your server supports sorting by INTERNALDATE. I understand that mapping this into some message attribute would not be terribly useful, no matter whether per-thread or per-message -- if it's a message attribute, one could just as well fetch the INTERNALDATE and be done with it.

However, suppose there was a hypothetical SORT=INTERNALDATE capability which would work exactly like the existing SORT extension, but only allowing/requiring to sort via INTERNALDATE. The result would be returned as the plain old SORT response (or, better, via ESEARCH for easier pipelining). Would you be willing to add this to GMail?

I'll be happy to prepare a draft for this extension and to implement it in Trojita. Are the other implementors, both server- and client-side, interested?

With kind regards,
Jan

---

From: Dan Karp <[email-masked]>
Date: Wed, 15 May 2013 09:08:19 -0700 (PDT)

> However, suppose there was a hypothetical SORT=INTERNALDATE capability which
> would work exactly like the existing SORT extension, but only
> allowing/requiring to sort via INTERNALDATE. The result would be returned as
> the plain old SORT response (or, better, via ESEARCH for easier pipelining).

(Just a note: Any server that advertises a capability starting with "SORT"
must also implement the entire SORT extension.  So you'd need to call it
something else.)

   A server that supports the base-level SORT extension indicates this
   with a capability name which starts with "SORT".  Future, upwards-
   compatible extensions to the SORT extension will all start with
   "SORT", indicating support for this base level.

- Dan