Subject: Partial equality match and sort order

From: Doug Royer <[email-masked]>
Date: Mon, 10 Mar 2003 10:22:52 -0700

I was reading another WG document this weekend and noticed that we
did not include a description of the sort order when two or
more results were a partial match of each other.

I would like to add to cap:

	When determining which object to return first on sorted results
         when two or more results partially match each other, the shorter
         match will be returned first. If the following:

		SELECT SUMMARY FROM VEVENT WHERE ...

	returned two matches:

		SUMMARY:ABC
		SUMMARY:ABCD

         The "VEVENT" component that had the "SUMMARY" property value of "ABC"
         must be returned before the longer "ABCD" result.

I really do not care if the longer or shorter one is returned
first - I just picked one. Any objections?

-- 

  Doug Royer                     |   http://INET-Consulting.com
  -------------------------------|-----------------------------
  [email-masked]                 | Office: (208)612-INET
  http://Royer.com/People/Doug   |    Fax: (866)594-8574
                                 |   Cell: (208)520-4044

                 We Do Standards - You Need Standards

---

From: John Stracke <[email-masked]>
Date: Mon, 10 Mar 2003 13:12:57 -0500

> more results were a partial match of each other.

I'm not sure what this means.  The word "partial" doesn't appear in 
draft 10; are you talking about queries using LIKE? Why would the sort 
order depend on the nature of the query? The draft defines the sort 
order as depending on the order in which the columns are listed; I 
assume that means listed in the cap-cols production, which makes it 
independent of the query.

>         SUMMARY:ABCD

Why wouldn't you just use the ordinary string sort for the locale, as 
specified in 6.1.1.6?

-- 
/==============================================================\
|John Stracke      [email-masked]                       |
|Principal Engineer|http://www.centive.com                     |
|Centive           |My opinions are my own.                    |
|==============================================================|
|Until you stalk and overrun, you can't devour anyone. --Hobbes|
\==============================================================/

---

From: Doug Royer <[email-masked]>
Date: Mon, 10 Mar 2003 12:04:57 -0700

John Stracke wrote:
> draft 10;

Which is my proposal - to add it.

--

---

From: Doug Royer <[email-masked]>
Date: Mon, 10 Mar 2003 12:06:15 -0700

> Why wouldn't you just use the ordinary string sort for the locale, as 

Does locale sort ordering solve it? I thought that partial match
sorts were unspecified?

--

---

From: John Stracke <[email-masked]>
Date: Mon, 10 Mar 2003 14:35:37 -0500

> Does locale sort ordering solve it? I thought that partial match

What are partial matches?

|All I ask is a chance to prove that money can't make me happy.|

---

From: [email-masked]
Date: Tue, 11 Mar 2003 10:46:37 -0500

> first - I just picked one. Any objections?

I big time object.  This just makes the CS have to cache up ALL matching 
objects/values to return before it can return ANY so that it can sort them 
based on some implyed sort order (the order of the SELECT).  This makes 
bounded latency even worse!

The CS should NOT have to cache ALL results before it can send back any 
results at all.  The CS should be able to send back data as soon as it can 
thus allowing the data to flow back to the requestor as its available.  My 
users are looking for better performance, not worse.

Bruce
===========================================================================
Bruce Kahn                                INet: 
[email-masked]
Messaging & Collaboration                 Phone: 978.399.6496
IBM Software Group                         FAX: and nothing but the FAX...
Standard disclaimers apply, even where prohibited by law...

---

From: John Stracke <[email-masked]>
Date: Tue, 11 Mar 2003 11:35:39 -0500

[email-masked] wrote:

> I big time object.  This just makes the CS have to cache up ALL 
> matching objects/values to return before it can return ANY so that it 
> can sort them based on some implyed sort order (the order of the 
> SELECT).  This makes bounded latency even worse! 

True.  We've been over this before, though I don't remember the 
discussion well enough to know why we settled on sorting.

My take is that sorting is like any other CPU-intensive operation: if 
you want the system to scale, you need to push it to the edges.

-- 
/========================================================\
|John Stracke      [email-masked]                 |
|Principal Engineer|http://www.centive.com               |
|Centive           |My opinions are my own.              |
|========================================================|
|Diplomacy: The art of letting someone else have your way|
\========================================================/

---

From: Doug Royer <[email-masked]>
Date: Tue, 11 Mar 2003 10:10:15 -0700

[email-masked] wrote:
> objects/values to return before it can return ANY so that it can sort 
> them based on some implyed sort order (the order of the SELECT).  This 
> makes bounded latency even worse!

What do you do with the other items that must be sorted that is
any different?

--

---

From: Andrea Campi <[email-masked]>
Date: Tue, 11 Mar 2003 18:19:39 +0100

Hi Bruce,

> users are looking for better performance, not worse.

just so that I'm sure I understand your POV: are you objecting to
Doug's proposal or are you objecting to sorting in general? Sorting
is still in the draft and I don't recall anybody objecting to it in
recent times at least (read, last year).

My opinion is that sorting is irrelevant and badly specified anyway [1];
I agree with John that sorting should be done at the client.

Bye,
	Andrea

[1] the draft says the results are sorted depending on the order in which
columns appear in the query. This means the rather common SELECT * ... has
no specified order.

-- 
Andrea Campi                              mailto:[email-masked]
I.NET S.p.A. - BT Ignite                  http://www.inet.it
Technical Dept. - R&D			  phone: +39 02 32863 ext 1
v. Darwin, 85 - I-20019			  fax: +39 02 32863 ext 7705
Settimo Milanese (MI), Italy

---

From: [email-masked]
Date: Tue, 11 Mar 2003 15:08:34 -0500

> recent times at least (read, last year).

Sorting is in the latest draft as you noted.  However it was was added to 
Draft 08 (so sometime between March 2002 and June 2002).  It was (is!?) an 
issue before and I honestly do not recall reaching a concensus on it nor 
do I have cycles to research it. 

It was originally added to Draft 08 as just:

6.1.1.6 Ordering of Results

   Sorting will take place in the order the columns are supplied in the
   QUERY command.

and is now covered in 2 sections in Draft 10:

6.1.1.6.  Ordering of Results
    Sorting will take place in the order the columns are supplied in the 
QUERY command. The CS MUST sort at least the first column. The CS MAY sort 
additional columns. 

and

6.1.1.7.  Date sorting order

    If EXPAND=FALSE sorting will be by the "DTSTART" property value 
ascending as if it were in UTC. 
     If EXPAND=TRUE sorting will be by the "RECURRENCE-ID" property value 
ascending as if it were in UTC. 

I have an aversion to having the sorting requirement as stated as it 
precludes ANY ablity to send results back to the requestor as they are 
found.

I think that having the CS "sort all results alphabetically (or reverse) 
based on SUMMARY and then DESCRIPTION [and then by LOCATION...]" is not 
necessarily all that useful.  Sorting based on the order of the SELECT 
clause is something that the UI really wants, NOT that CAP itself needs 
IMHO.  Sorting is more of a rendering concern than a protocol concern 
really.

> I agree with John that sorting should be done at the client.

Make that 3 votes for sorting in the client rather than in the CS.  (If my 
MUA can insertion sort mail that arrives out of order in my Inbox, why 
cant my CUA?)

Bruce

---

From: [email-masked]
Date: Tue, 11 Mar 2003 13:16:59 -0800

could the sort be specified in the query
(as in ORDER BY ... ASCENDING/DESCENDING)?
sorting would then only be done if and as desired.
or was that already discussed and rejected?

---

From: [email-masked]
Date: Wed, 12 Mar 2003 11:20:41 -0500

I wrote on 03/11/2003 03:08:34 PM:
>                                                However it was was 
> added to Draft 08 (so sometime between March 2002 and June 2002). 

Last night that kinda felt odd so I did another check this AM and found 
that it was actually added into Draft 03 which was Dec 2000.  I have to 
blame user error in trusting MSIE to search the archives on Dougs site for 
this (after all searching for "sort" should find any hits).  Time to use 
Opera again... 

In briefly going back to the archives I see that we had no real meaty 
discussion on adding sorting so some of the more heated discussions must 
have been at an IETF meeting.  The effort appears to have been triggered 
by Mark Pattersons discussion of ordering of results but in the context of 
the CAP requirements doc, not acutally in CAP discussions.

In any case since there are previously expressed concerns by both John 
Strack (ie: locale) and Andrea (ie: The '*') case as well as my own 
dealing with the impact to bounded latency I think some cycles need to be 
put into a better solution or we should remove the implicit sorting 
entirely.  I for one though have far fewer cycles to spare these days on 
CAP so I cannot offer any text now.  I can suggest we take the KISS 
approach and simplify the design for CAP 1.0 and remove the sorting 
entirely.  After all it was Doug who originally (1999) wanted to take this 
approach if I recall correctly...

Bruce

---

From: Doug Royer <[email-masked]>
Date: Wed, 12 Mar 2003 10:06:10 -0700

[email-masked] wrote:
> that it was actually added into Draft 03 which was Dec 2000.  ...
> 
> have been at an IETF meeting.

So you are saying that just because you were busy (or for what ever
reason) and did not wish to participate in that discussion that it
does not count (as meaty)? Sorry - it was discussed and you elected
not to particapte for what ever reason. It is time to close CAP
and ship it.

> The effort appears to have been triggered 
> by Mark Pattersons discussion of ordering of results but in the context 
> of the CAP requirements doc, not acutally in CAP discussions.

I am confused - you site Mark Pattersons discussion of ordering (which
IS on the list) and yet declare there was not a CAP discussion? Explain
what a discussion is if that is not it?

--

---

From: Doug Royer <[email-masked]>
Date: Wed, 12 Mar 2003 10:35:54 -0700

[email-masked] wrote:
> blame user error in trusting MSIE to search the archives on Dougs site 
> for this (after all searching for "sort" should find any hits).  Time to 
> use Opera again...  

It was in CAP-00, draft-ietf-calsch-cap-00.txt dated August 5, 1999 :

   orderby         = <any valid SQL string that goes into a ORDERBY
                    clause>

As some did not want SQL, this was changed into explicit sorting
as the debate went forward. It has been in CAP for years.

--

---

From: Patrice Lapierre <[email-masked]>
Date: 12 Mar 2003 16:51:50 -0500

On Tue, 2003-03-11 at 15:08, [email-masked] wrote:
> 
> Make that 3 votes for sorting in the client rather than in the CS.
> (If my MUA can insertion sort mail that arrives out of order in my
> Inbox, why cant my CUA?)
> 

Make that 4 votes. 

Interested parties can look at the archive:

http://www.imc.org/ietf-calendar/mail-archive/msg03435.html

--
Patrice.

---

From: sfg <[email-masked]>
Date: 13 Mar 2003 10:20:41 +1100

> > (If my MUA can insertion sort mail that arrives out of order in my

I vote against this. 

I've read the archives, I'm mainly a lurker with desires to build an
Open Source CAP Server (http://www.sf.net/projects/jical)

I would have thought ordering was a natural requirement of a server vs a
client. Surely your data store can make these things easier via indexes
etc. The comparison to an Inbox doesn't stack up. From reading the spec
- CAP Servers are more like a specialised RDBMS. Imagine if your RDBMS
did not support ORDER BY? An alternative would be to add the ORDERBY to
capabilities so that the client can query and see if the server can/will
handle ORDERBY.

Stuart Guthrie
vcard:   http://www.eurekait.com/sfg.vcf
OSS:     http://www.sf.net/projects/jical

---

From: Doug Royer <[email-masked]>
Date: Wed, 12 Mar 2003 17:27:17 -0700

>>>(If my MUA can insertion sort mail that arrives out of order in my

As do I.

Would the others agree to a SORT capability? Where the default is "NONE"?
Something like:

	SORT:none         -> Any random order.
	SORT:SORT-1       -> As currently in CAP.

This would cause less changes and debate than removing SORT completely
and if we agreed then it is less change to CAP and allow us to
ship CAP sooner?

Comments?

Thanks

--

---

From: John Stracke <[email-masked]>
Date: Thu, 13 Mar 2003 08:14:32 -0500

>>>(If my MUA can insertion sort mail that arrives out of order in my
(Remember, we don't vote.)

>client.
Not really, no.  Anything that can be done with equal ease on the server 
or on the client should be done on the client, because everything is 
more expensive on the server, where it has to be done many more times.

>Surely your data store can make these things easier via indexes
>etc.
>
Indices can make sorting more efficient; but it gets really expensive to 
maintain indices on every column, which is basically what would have to 
be done to meet this requirement.

> The comparison to an Inbox doesn't stack up. From reading the spec
>did not support ORDER BY?
>
That wouldn't be much of a problem, actually; I'd just sort in the 
client-side code.  I use SQL pretty regularly these days, and I know of 
only two advantages for having ORDER BY in the language: (a) it's 
convenient for people writing queries by hand; (b) indices.  (A) is not 
something we should be worrying about; (b) is expensive.

(The big difference between indices for CAP and indices for a SQL 
database is that the schema of SQL databases tends to get customized to 
match the application; you can apply the indices that you think you're 
going to need.  A CS can't do that, because it has to work with any CUA.)

>An alternative would be to add the ORDERBY to
Not a good idea.  The more optional features we have in the protocol, 
the harder it is for a client author to make sure their client can 
interoperate with every server.

I mean, come on, guys.  We're talking about *sorting* here.  It's 
potentially CPU-intensive if you've got a huge dataset, but it's hardly 
a big deal to implement.  Any sensible language will have a generic 
sorting feature in its standard library; even C has qsort().  If you're 
on a constrained device, you can put a limit on how many items you're 
going to sort, which will probably be pretty close to the number of 
items you can reasonably display; if you can't sort, you put up an error 
message or something.  The tradeoffs to be made here depend on the UI, 
which means the decision should be made in the CUA.  If the protocol 
specifies that the server has to sort, then it has no idea what the 
tradeoffs are.

-- 
/============================================================\
|John Stracke      [email-masked]                     |
|Principal Engineer|http://www.centive.com                   |
|Centive           |My opinions are my own.                  |
|============================================================|
|"Chris is the most self-effacing guy I know." "Well, I'm not|
|*that* good at it."                                         |
\============================================================/

---

From: [email-masked]
Date: Thu, 13 Mar 2003 14:14:41 -0500

Doug responded on 03/12/2003 12:06:10 PM:
> does not count (as meaty)? 

Not quite. 

Ive been one of the most consistanly active folks in the WG since it was a 
BOF.  There have been times when I was less than immediately responsive to 
postings (work pays the bills so it takes priority to the WG) but Ive 
always tried to keep up on the threads.  I cannot think of anyone else 
whose had my record of consistant engagedment in this WG so dont try to 
make it sound like I was not engaged.  Unless it was around the end game 
time of Notes R6 (~May - Sep 02) I've been involved in the discussion. 

>                                   Sorry - it was discussed and you 
elected
> not to particapte for what ever reason. It is time to close CAP

I did a FT search of the archives for the word "sort" and there was NOT a 
big discussion of sorting as you would suggest.  We did have some 
discussions on it and there was NOT the concensus you claim there is.  In 
fact so far I hear only a concensus that it should NOT be in CAP.

CAP has been drawn out over several years but I do not think we should 
just push it out the door because its taken so long.  I have listed 
several issues in the past that have NOT been addressed and we still have 
some (ie: Stored VQUERYs, sorting, a LOGOUT command, signatures, multipart 
MIME, etc) that need to be addressed before we can attempt a Last Call. 
There are also the blank areas related to BEEP that have not yet been 
filled in for anyone to review.  So I do not think CAP is ready for a Last 
Call yet.

Once we "ship" CAP 1.0 we have to live with the warts it has if we (or 
some future effort) tries to fix up and extend CAP to include features too 
tough to get into CAP 1.0.  I think we need to make sure the bigger warts 
are gone before we try to foist it off on folks and then sell products 
based on it.  Otherwise CAP becomes a wasted protocol since its too buggy 
or kludgy to implement.

> what a discussion is if that is not it?

Cant help your confusion any more than say go reread the archives.  A FT 
search of the archives all the way back to the BOF days reveals 374 
documents that contain the word 'sort'.  This includes:

11 messages under this subject (excluding any traffic after my last msg)
8 messages under the CHARSET discussion recently
270+ messages sent during iCalendar/iTIP/iMIP (and cruft) development 
discussions.  I kinda got lost after 280ish messages so Ill call it 270+
80+ messages unrelated to actual sorting.  Stuff like "intend to answer 
the sort of questions" or "I sort of was thinking...". or "going to work 
sort of " or  "taxes out it's just sort " from Johns .sig.

This rough check of 'sort' is ~369 messages.  Deduct that from the 374 
found and that leaves ~5 messages.  That must have been a very meaty and 
engaging discussion and concensus building.  Maybe it was done under the 
term "ORDERBY" and noone ever used the phrase "sort" (I guess its 
possible...).

FYI: The Mark P. thread was ~29-Nov-2000 under the Subject "CAP 
requirements draft resubmitted".  It only had ~8 msgs in that thread.  I 
would not call that "meaty" either.  Perhaps you do, I don't know.

In any case so far I hear 4 votes against the sorting and 1 for it.  The 
300+ rest are abstentions.  To me that sounds like rough concensus to 
remove it.

Bruce

---

From: Dan Winship <[email-masked]>
Date: 13 Mar 2003 14:45:27 -0500

> 	SORT:SORT-1       -> As currently in CAP.

But then every client that cared about sorting would need to be able to
do sorting itself in case it was talking to a SORT:none server. And if
it has to have the code to do it sometimes, then why not do it all the
time?

-- Dan

---

From: Doug Royer <[email-masked]>
Date: Thu, 13 Mar 2003 15:46:07 -0700

> it has to have the code to do it sometimes, then why not do it all the

Your correct in that the client will have to do that in order to support
CS that do not, however if SORT:SORT-1 is set, then the client will know
that the CS has sorted the results in locale sort order.

--