Subject: [MORG] I-D Action:draft-ietf-morg-multimailbox-search-02.txt

From: [email-masked]
Date: Fri, 5 Feb 2010 09:00:01 -0800 (PST)

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Message Organization Working Group of the IETF.

	Title           : IMAP4 Multimailbox SEARCH Extension
	Author(s)       : B. Leiba, A. Melnikov
	Filename        : draft-ietf-morg-multimailbox-search-02.txt
	Pages           : 10
	Date            : 2010-02-05

The IMAP4 specification allows the searching only of the selected
mailbox.  A user often wants to search multiple mailboxes, and a
client that wishes to support this must issue a series of SELECT and
SEARCH commands, waiting for each to complete before moving on to the
next.  This extension allows a client to search multiple mailboxes
with one command, limiting the round-trips and waiting for various
searches to complete, and not requiring disruption of the currently
selected mailbox.  This also uses MAILBOX and TAG fields in ESEARCH
responses, allowing a client to pipeline the searches if it chooses.

Note

A revised version of this draft document will be submitted to the RFC
editor as a Proposed Standard for the Internet Community.  Discussion
and suggestions for improvement are requested, and should be sent to
[email-masked].

A URL for this Internet-Draft is:
http://www.ietf.org/internet-drafts/draft-ietf-morg-multimailbox-search-02.txt

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

Below is the data which will enable a MIME compliant mail reader
implementation to automatically retrieve the ASCII version of the
Internet-Draft.

---

From: Barry Leiba <[email-masked]>
Date: Fri, 5 Feb 2010 14:16:12 -0500

I have updated the multimailbox-search draft, filling in some of the
gaps.  There's still a list of to-do items, so, folks: please review
this draft and help fill them in.  We need a general review of what's
there, and also a particular look at the "open issues" section to
resolve those issues.

I'll appreciate, as we discuss the open issues, suggestions for text
to resolve them (for those we think need text in the document).

Barry

> responses, allowing a client to pipeline the searches if it chooses.
...

---

From: Barry Leiba <[email-masked]>
Date: Tue, 9 Feb 2010 20:49:36 -0500

> to resolve them (for those we think need text in the document).

Comments, please.  The open issues need to be resolved.

Barry

---

From: Barry Leiba <[email-masked]>
Date: Thu, 18 Feb 2010 20:48:19 -0500

> to resolve them (for those we think need text in the document).

Second reminder: Let's please discuss this on the mailing list, so we
can try to resolve some of the open issues before the Anaheim meeting.

Barry

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Fri, 19 Feb 2010 10:01:37 +0100

> can try to resolve some of the open issues before the Anaheim meeting.

One open issue.

I raised an issue privately. The solution to that is some informative 
text (which I've offered to write). The issue is: An informative section 
or a separate document?

I couldn't care less.

I'll review the document again, too. Haven't in a while.

Arnt

---

From: Timo Sirainen <[email-masked]>
Date: Fri, 19 Feb 2010 13:30:15 +0200

> For each mailbox satisfying the source options, a single ESEARCH
>    response MUST be returned if any messages in that mailbox match the
>    search criteria.  An ESEARCH respoonse SHOULD NOT [[Barry: Why not
>    MUST NOT ?]] be returned for mailboxes that contain no matching
>    messages.  This is true even when result options such as MIN, MAX,

SHOULD NOT seems like the worst possibility. Either it should be MUST or
MUST NOT. MUST might be nice so client knows what mailboxes exactly were
searched, but probably isn't very useful in reality.

> Note that it is now possible for a SEARCH command to return NO
>    untagged responses (no SEARCH nor ESEARCH responses), in the case

The uppercased NO there could be slightly confusing first. First I
thought: "Oh, untagged * NO responses".

> If "subtree" is specified, the server MUST defend against loops in
>    the hierarchy (for example, those caused by recursive file-system
>    links within the message store).  The server SHOULD do this by
>    keeping track of the mailboxes that have been searched, and
>    terminating the hierarchy traversal when a repeat is found.  If it
>    can not do that, it MAY do it by limiting the hierarchy depth.

Well, LIST "" * has exactly the same potential problem..

> If the server supports the ACL [RFC4314] extension, then the logged
>    in user is required to have the 'r' right for each mailbox she wants
>    to search.  Mailboxes matching the source options for which the
>    logged in user has no 'r' right MUST be ignored by a multimailbox
>    search.  In particular, ESEARCH responses MUST NOT be returned for
>    those mailboxes.

Also any mailboxes not explicitly named must have 'l' right.

> Interaction with IMAP Contexts [RFC5267] needs to be defined.

I guess server then just has to monitor all matched mailboxes and send
updates whenever they happen. But should it notice newly created/renamed
mailboxes? Maybe the answer is no, except if NOTIFY is also used:

>    Suggestion: UPDATE option of IMAP Notify [RFC5465] might have to be
>    prohibited when both Context and this extension are used.  [Barry:
>    But why?  Isn't this then the equivalent of doing many SEARCH
>    commands with the UPDATE option?]

I guess the problem is if NOTIFY's extended UPDATE should be allowed.
Sending FETCH replies for messages matching in non-selected mailboxes
wouldn't work. But the solution could be just that the FETCH replies are
sent only to messages in selected mailbox, whichever it happens to be at
the time changes happen.

> There's a suggestion to add an EXCLUDE clause (with a nested search
>    criteria).  For example, one might want to search "personal" but
>    exclude "mailboxes (Trash Spam)".
> 
>    Cyrus suggests you can use metadata to tag mailboxes that you do or
>    don't want to search, and use search criteria to exclude them (good
>    for mailboxes that you NEVER want searched (as Trash and Spam,
>    above)).

Dunno. A 3rd possibility would be to make the IN a search-key, but
perhaps that would make things too complex again. It would anyway allow
e.g.:

SEARCH unseen IN (personal) NOT IN (mailboxes "Spam" subtree "Trash")

> C: tag1 SEARCH IN ((mailboxes "folder1" subtree "folder2")) unseen
>    C: tag2 SEARCH IN ((mailboxes "folder1" subtree-one "folder2"))

Double (( )) doesn't seem correct?

---

From: Dan Karp <[email-masked]>
Date: Sat, 20 Feb 2010 12:36:21 -0800 (PST)

>    Because message numbers are not useful for mailboxes that are not
>    selected, each ESEARCH response MUST return information about UIDs,
>    not message numbers, regardless of whether it is in response to a
>    SEARCH or a UID SEARCH command.  In particular, the responses MUST
>    contain the UID indicator.  This is true even if the source options
>    specify that only the selected mailbox be searched.

Would it be clearer to just require an explicit UID SEARCH when using 
the "IN" multimailbox syntax?  Non-UID SEARCH could just return BAD.

---

From: Timo Sirainen <[email-masked]>
Date: Tue, 23 Feb 2010 20:35:38 +0200

> the "IN" multimailbox syntax?  Non-UID SEARCH could just return BAD.

+1

---

From: Barry Leiba <[email-masked]>
Date: Tue, 23 Feb 2010 13:47:44 -0500

>> the "IN" multimailbox syntax?  Non-UID SEARCH could just return BAD.

I like this too.  Does anyone object to the change?
I'll put it into my source code for the next version.

Barry

---

From: Alexey Melnikov <[email-masked]>
Date: Tue, 23 Feb 2010 18:49:56 +0000

>I'll put it into my source code for the next version.
Works for me.

---

From: Mark Crispin <[email-masked]>
Date: Tue, 23 Feb 2010 10:57:17 -0800 (PST)

I have not paid much attention to this discussion, but this caught my eye.

It would be cleaner to have a new command for multimailbox searching that 
always returns UIDs.

That way, all three searches would have the same set of search criteria.

Also, isn't it reasonable to do this command without a mailbox selected? 
In that case, you can't use SEARCH or UID SEARCH since both require a 
mailbox to be selected as a fundamental part of the command.

Arguments to a command should not change its fundamental semantics.

>>>> the "IN" multimailbox syntax?  Non-UID SEARCH could just return BAD.

-- Mark --

http://panda.com/mrc
Democracy is two wolves and a sheep deciding what to eat for lunch.
Liberty is a well-armed sheep contesting the vote.

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Tue, 23 Feb 2010 21:05:31 +0100

> That way, all three searches would have the same set of search criteria.

Not quite; MSN sets are also valid as search keys.

Arnt

---

From: Barry Leiba <[email-masked]>
Date: Tue, 23 Feb 2010 15:33:28 -0500

> It would be cleaner to have a new command for multimailbox searching that

I have no objection to that: we could make an "ESEARCH" command, to
match the "ESEARCH" response, and that would be OK with me.

I think it's OK to extend UID SEARCH this way, but I agree with Mark
that it's preferable to change the command.  Some servers -- including
mine -- parse the command and check the command against the state
before parsing any options.  If this works with UID SEARCH, it
requires that all UID commands be allowed in authenticated state, and
that another state check be done later.  That's clearly not a terrible
change, but it does alter the server's basic parsing and state-check
logic, and can easily be avoided.

So what do others think of using "ESEARCH" or "MSEARCH" for this?

Barry

---

From: Mark Crispin <[email-masked]>
Date: Tue, 23 Feb 2010 12:48:52 -0800 (PST)

> Not quite; MSN sets are also valid as search keys.

And are you saying that there's a problem with an MSN set being provided 
as a search key for this functionality?  I'll grant that it often seems 
silly, but it is not necessary bogus!

Unlike FETCH/STORE/COPY, MSN range validation does not apply to SEARCH set 
arguments.  So it is perfectly reasonable to do things like 1:100 for "the 
first hundred messages in the mailbox", 101:200 for "the second hundred 
messages in the mailbox", etc.

-- Mark --

http://panda.com/mrc

---

From: Mark Crispin <[email-masked]>
Date: Tue, 23 Feb 2010 12:49:37 -0800 (PST)

On Tue, 23 Feb 2010, Barry Leiba wrote:
> Some servers -- including

I was thinking about this as well.

-- Mark --

http://panda.com/mrc

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Wed, 24 Feb 2010 10:31:45 +0100

Mark Crispin writes:
> And are you saying that there's a problem with an MSN set being 
> provided as a search key for this functionality?  I'll grant that it 
> often seems silly, but it is not necessary bogus!
>
> Unlike FETCH/STORE/COPY, MSN range validation does not apply to SEARCH 
> set arguments.  So it is perfectly reasonable to do things like 1:100 
> for "the first hundred messages in the mailbox", 101:200 for "the 
> second hundred messages in the mailbox", etc.

I'm saying it's just neat to have.

I know at least two clients that use it to get incremental search 
results. I know that because they cause enough load to be noticed.

I can often/usually execute a search quickly, by doing b-tree lookups 
and whatnot. 'search from <a@b>' is a O(log(n)). But if the client 
sends those MSNs ('search 1:100 from <a@b>', then 'search 101:200 from 
<a@b>', then ...), the the b-tree lookup is repeated O(n) times and the 
total cost of the search is O(n*log(n)).

There's some value in incremental search results. Depends on the client. 
But in the case of multimailbox search, I see little or no real value 
in being able to search incrementally _in_that_way_. Base IMAP already 
supports multimailbox incremental search by sending a sequence of 
select and plain search commands.

Arnt

---

From: Alexey Melnikov <[email-masked]>
Date: Wed, 24 Feb 2010 11:36:20 +0000

>So what do others think of using "ESEARCH" or "MSEARCH" for this?
Changing the command name (I slightly prefer ESEARCH) is fine with me.

I would like to keep the untagged ESEARCH response name/structure.

---

From: Mark Crispin <[email-masked]>
Date: Wed, 24 Feb 2010 06:10:23 -0800 (PST)

> total cost of the search is O(n*log(n)).

That sounds like a predictable consequence of your implementation choice;
and suggests that you should consider some alternative choices to remove
that cost.

One obvious possibility is to cache the b-tree lookup results for reuse.

> select and plain search commands.

Client authors would disagree.

I thought that the entire point of the exercise was to do the function
without the additional RTTs.  RTTs are deadly, and it is desirable to
reduce them.

Now it sounds like the sole purpose is to accomodate a single server.

-- Mark --

http://panda.com/mrc

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Wed, 24 Feb 2010 15:17:17 +0100

> Client authors would disagree.

Disagree with what?

That there's value in incremental search results?

That I see little or no value in THAT WAY to do incremental multimailbox 
search?

That base IMAP allows sending a sequence of select and search commands?

Arnt

---

From: Mark Crispin <[email-masked]>
Date: Wed, 24 Feb 2010 06:25:29 -0800 (PST)

> That there's value in incremental search results?

Considering that I just gave an example of a strategy to do incremental
search, it would make no sense for me to disagree with its value.

> That I see little or no value in THAT WAY to do incremental multimailbox

It should be obvious, from context, that client authors may want to do
incremental multimailbox search in that way.

> That base IMAP allows sending a sequence of select and search commands?

I see no point for a multimailbox search other than to remove RTTs.

-- Mark --

http://panda.com/mrc

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Wed, 24 Feb 2010 15:34:59 +0100

> incremental multimailbox search in that way.

Really?

I reviewed the draft when I did multimailbox search for a client a whole 
ago, and ended up with something like this to get incremental search 
results:

  find list of mailboxes to be searched
  if server supports multimailbox search
    send status (messages) for each mailbox
    process the status responses as they come back
    find the highest message count in any relevant mailbox
    loop from 1 to that count by steps of e.g. 256
      send 'search in (...) x+1:x+256 (other criteria)'
    process the search responses that come back
  else
    for each mailbox
      send examine
      send search
    process the search responses that come back
  retrieve some/all of the matching messages

My conclusion was that the whole thing was too much hassle, so it would 
be better to just send a single SEARCH IN. If I overlooked some better 
way, I'd be thrilled to hear what it is.

Arnt

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Wed, 24 Feb 2010 15:52:18 +0100

Actually, let me rephrase. That was too much of a digression.

> way, I'd be thrilled to hear what it is.

If I overlooked a better way, then I think the document might do well to 
describe it.

If there is some other use-case for using MSNs in multimailbox search 
commands, then I'd like to hear about that, too.

Arnt

---

From: Mark Crispin <[email-masked]>
Date: Wed, 24 Feb 2010 07:02:30 -0800 (PST)

> If I overlooked a better way, then I think the document might do well to

In your quest for the complex you overlooked the simple.

What you overlooked is that many incremental search tasks have no
intention of sweeping the entire space.  All they seek to do is collect
some results.

Hence the loop is to fetch 1:100, 101:200, etc. until "enough" results
have been obtained, and/or a time interval has expired, and/or the user
says stop, etc.  No need to do STATUS commands & etc.

The fact that you can't conceive of a use for something doesn't mean that
nobody else can.

-- Mark --

http://panda.com/mrc

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Wed, 24 Feb 2010 16:10:06 +0100

> says stop, etc. No need to do STATUS commands & etc.

Either you know that there are results so the search will terminate, or 
you run the STATUSes to know when to stop looking, or you loop all the 
way to UINT_MAX. Right?

> The fact that you can't conceive of a use for something doesn't mean that

Right. The question is whether this is plausible/simple/useful enough to 
warrant support. IMAP extensions have a habit of making arcane 
taskspossible; I'd rather make the important tasks simple.

Arnt

---

From: Mark Crispin <[email-masked]>
Date: Wed, 24 Feb 2010 09:06:53 -0800 (PST)

> you run the STATUSes to know when to stop looking, or you loop all the

No, because the point of that search is to collect some results, not all
results.  You seem to be hung up on what needs to be done to assemble a
complete set of results from pieces.

> taskspossible; I'd rather make the important tasks simple.

No, the question is whether the needs of your server justify adding yet
another special rule to IMAP.  In this case, the burden of proof is on
the proposal for deletion from a standard rule.

Have you considered that implementations might have to go to extra work
NOT to do something that they do in other circumstances?

-- Mark --

http://panda.com/mrc

---

From: Arnt Gulbrandsen <[email-masked]>
Date: Thu, 25 Feb 2010 09:42:04 +0100

> complete set of results from pieces.

Not quite; you assume there are some results to collect, I don't assume 
that. And I have a... semi-rational disposition against the kind of very 
long loop that would result, due to once having to pay €1769 in traffic 
charges for a similar loop.

> the proposal for deletion from a standard rule.

A misunderstanding, perhaps. I'm not arguing to eliminate the existing 
MSN rule. I'm arguing that the present justification is too weak to 
extend the rule to OTHER mailboxes. (Find a good use-case and my 
protests with disappear.)

I think MSNs should be used to refer to messages in the selected 
mailbox, not extended to unselected mailboxes.

> NOT to do something that they do in other circumstances?

Yes. So? We all do that. GENURLAUTH and URLFETCH have similar 
implications in my case, for example: No MSNs, all UIDs.

Arnt

---

From: Barry Leiba <[email-masked]>
Date: Thu, 25 Feb 2010 15:39:32 -0500

Just addressing one point in particular:

> I think MSNs should be used to refer to messages in the selected mailbox,
> not extended to unselected mailboxes.

It would be the opposite of "extending", here; we would have to
*prohibit* a search criterion that's otherwise allowed.  I see no
reason to make such a prohibition.

It's possible that we should, nevertheless, say something about this
in the document, because it might create some confusion.  I'd like to
add a paragraph that explains the use of MSNs as search criteria in
unselected mailboxes.  In particular, I'd like to point out the usage
of only selecting the Nth set of M messages... and I'd like to add
some normative text saying that the server MUST NOT (or SHOULD NOT?
opinions requested) consider it an error for ESEARCH to pass an MSN
set that goes beyond the bounds of valid MSNs for any particular
mailbox.

In other words if there are 53 messages in mailbox Bloog, whether or not

   T0 SELECT Bloog
   T1 SEARCH SINCE 1-Dec-2009 101:200

...returns "T1 BAD - 101:200 out of range"

   T1 ESEARCH IN (mailboxes "Bloog") SINCE 1-Dec-2009 101:200

...MUST NOT (or SHOULD NOT?) return tagged NO or BAD.

Barry

---

From: Mark Crispin <[email-masked]>
Date: Thu, 25 Feb 2010 13:10:50 -0800 (PST)

On Thu, 25 Feb 2010, Barry Leiba wrote:
> I'd like to add

It is not an error in SEARCH or UID SEARCH either.  RFC 3501 could perhaps
be a bit more clear on that point.  The question never really came up
before.

In SEARCH, the MSN search criterion is a searching specifier.  Unlike
FETCH, STORE, COPY, etc., the SEARCH command is not operating on those
MSNs; in fact, it could even be a NOT of those MSNs.

-- Mark --

http://panda.com/mrc