Subject: CAP: Ordering of the components returned by the search command.

From: Patrice Lapierre <[email-masked]>
Date: 15 Feb 2002 11:13:31 -0500

The latest proposal for CAP-QL states the following for the ordering
of components returned by the search command:

      4.1.2 CAP-QL notes

      (1) There is no ORDERBY.  Sorting will take place in the order the
          columns are supplied in the command.
      ...
   
      (2) The CS MUST sort at least the first column.
          The CS MAY sort additional columns.

      (3) If the cap-cols is only "*" and nothing else, then:

            If EXPAND=FALSE sorting will be by the DTSTART value
            ascending.

            If EXPAND=TRUE sorting will be by the RECURRENCE-ID value
            ascending.

I see some problems/limitations with this approach:

   (1) Often a CUA is not interested in any particular ordering.
       Yet for VEVENTs an ordering is always defined. This causes
       unnecessary processing on the server side.

   (2) When selecting everything (SELECT *) from a VEVENT. The
       CUA might be interested in another ordering than DTSTART
       (or RECURRENCE-ID).

   (3) When selecting everything (SELECT *) from a component
       that doesn't include a DTSTART, no ordering can be specified.

   (4) If the first property in the a select clause occurs more than
       once, the ordering is not defined.

   (5) If the first property in the select clause is not present,
       the ordering is not defined.   

  To address these issues, I propose the addition of an optional
"ORDER BY" clause (as in SQL). When not present no ordering is specified
(this solves (1)).

  The "ORDER BY" clause could be limited to a finite (no *) subset
of the properties included directly or indirectly (i.e., *) 
in the SELECT clause. This would take care of (2) and (3), and
shouldn't introduce additional complexity.

Examples:

1.
   BEGIN:VQUERY
   QUERY:SELECT * FROM VEVENT
   END:VQUERY

  Here no ordering is specified.

2. 
   BEGIN:VQUERY
   QUERY: SELECT * FROM VTODO ORDER BY SUMMARY
   END:VQUERY

 Order the returned VTODO by SUMMARY.

For (4) and (5) additional rules are required:

- Properties that are not present (or not visible due 
  to insufficient access rights), should come first.

- For properties that occurs more than once, the ordering
  should be based on the value of the property instance
  that comes first within each component.

--
Patrice.

---

From: Doug Royer <[email-masked]>
Date: Fri, 15 Feb 2002 19:48:26 -0700

>        unnecessary processing on the server side.

The (old) debate was that the default fetch should be by
DATE or RECURRANCE-ID in UTC. That evolved into what it is now.

>        that doesn't include a DTSTART, no ordering can be specified.

Not true, it is on the 1st item in the SELECT clause.

>        once, the ordering is not defined.

Yes it is, it is by the first item in the SELECT clause.

>        the ordering is not defined.

It has to have at least one item in the SELECT clause
or it is not a valid QUERY:

	QUERY:SELECT FROM VEVENT	; Is not valid.

> "ORDER BY" clause (as in SQL). When not present no ordering is specified

We already beat this down and decided it could be an add on.

---

From: Patrice Lapierre <[email-masked]>
Date: 18 Feb 2002 14:19:19 -0500

...
> DATE or RECURRANCE-ID in UTC. That evolved into what it is now.

The point still holds. Unnecessary processing on the server side
is required when no ordering is required by the CUA.

> > Not true, it is on the 1st item in the SELECT clause.

I clearly stated that the first element is "*".

I don't see anything in the proposal that specifies the
ordering of the elements returned by:

   SELECT * FROM VAGENDA
   
And doing the following:
   SELECT NAME, * FROM VAGENDA
is NOT valid according to the most recent proposal for CAL-QL.

> Yes it is, it is by the first item in the SELECT clause.

I was not clear enough.  What I meant is what if the first item is 
a property that may occur more than once in the returned components
(not in the SELECT clause).  

e.g.,
   
   SELECT ATTENDEE FROM VEVENT

When more than one ATTENDEEs are present in a VEVENT, 
the current proposal does not specify the ordering.

>       QUERY:SELECT FROM VEVENT        ; Is not valid.

Again, you didn't understand my point:

Consider:

   SELECT LOCATION, SUMMARY FROM VEVENT 

If a selected VEVENT does not contain a LOCATION property
(or it is not visible due to access rights), where does it come 
in the ordering?

> We already beat this down and decided it could be an add on.

  Simply adding "ORDER BY" later would not resolve (1) without
breaking backward compatibility.

 Adding the "ORDER BY" clause now, would address all the issues 
mentioned above, and would not add complexity to the implementation
if it is limited to a subset of the SELECT clause.

---

From: Doug Royer <[email-masked]>
Date: Mon, 18 Feb 2002 13:24:31 -0700

> ordering of the elements returned by:

Per the proposal - by DTSTART if EXPAND:FALSE, or RECURRANCE-ID
if EXPAND:TRUE .

> the current proposal does not specify the ordering.

Why does it matter?

> (or it is not visible due to access rights), where does it come

I think I understand. How about - NULL comes first.

> breaking backward compatibility.

A new CS could advertise a new 'ORDER-BY' capability.
How would existing CUAs or CS's break?

> if it is limited to a subset of the SELECT clause.

We are one week from editing the last-call. This debate is going
to take more than a week - just in required wait time to see
if there are any objections + debate time after that.

	Do you want to hold up CAP for this?

---

From: Patrice Lapierre <[email-masked]>
Date: 18 Feb 2002 16:45:49 -0500

...
> Per the proposal - by DTSTART if EXPAND:FALSE, or RECURRANCE-ID

The point was that VAGENDA does NOT have a DTSTART or a RECURRENCE-ID.
  
...
> > the current proposal does not specify the ordering.

It makes the following ambiguous:

      4.1.2 CAP-QL notes

My original post contained the following:

> I think I understand. How about - NULL comes first.

That is exactly what was proposed.

> 	Do you want to hold up CAP for this?

  The "search" command is likely to be the command that is the most
frequently used by all CUAs. As such eliminating a potential 
O(n log n) in time complexity, to sort components when the CUA 
does not require any ordering, is important.

  Another alternative to "ORDER BY", would be to completely leave 
the ordering unspecified in the first version of CAP, and add it 
in the future if needed.

---

From: Doug Royer <[email-masked]>
Date: Mon, 18 Feb 2002 16:22:06 -0700

> The point was that VAGENDA does NOT have a DTSTART or a RECURRENCE-ID.

:-) Sorry!

As this returns the property names, how about sort by
property names?

>     to insufficient access rights), should come first.

Okay -  I am now understanding.

Yes - I agree.

>     that comes first within each component.

Same - I agree.

> does not require any ordering, is important.

The problem is do we want to limit it to EXACTLY ONE argument.
As in this not allowed:

	ORDER-BY DTSTART,SUMMARY

If not, now you have just mandated multiple sorting which
was already shot down. Could you be happy with if multiple
are supplied, the CS MUST sort by the the first, and MAY
sort by the additional arguments?

> the ordering unspecified in the first version of CAP, and add it 

Not acceptable - it was added for small device support.
So how about we add ORDER-BY, but IF not supplied, then
it is ordered as in the proposal - this way small devices
can get/display without having to hold the entire contents
and then sort.

---

From: "Graham Gilmore" <[email-masked]>
Date: Mon, 18 Feb 2002 21:29:49 -0500

> can get/display without having to hold the entire contents

    While it's nice to see some agreement on the smaller points, having the
ordering remain as it is in the proposal in the case that ORDER-BY is not
present basically ignores Patrice's main argument against the proposal,
which I quote here:

<Patrice>

</Patrice>

    If requiring CUAs that want ordering to specify "ORDER-BY:DTSTART" is
too much trouble (maybe we want to save those twenty-or-so bytes that small
devices would otherwise have to send with each search), then perhaps
alternately a special value is needed for ORDER-BY:

    ORDER-BY:NONE

    which would permit the CS to return the results without any ordering at
all, thus solving (one of) the issues Patrice mentioned.

    Graham

---

From: Doug Royer <[email-masked]>
Date: Mon, 18 Feb 2002 20:27:08 -0700

> all, thus solving (one of) the issues Patrice mentioned.

Yes, I am quite sure it would solve Patrice's problem.
However that text did not evolve into CAP as a result
of a 1000 monkeys pounding on a 1000 keyboards. It was
the result of a debate over time. Simply because someone wants
to change it less than one week before our final
edit for the last-call is not a reason to add it.

That text has been in the CAP draft for over a year. It
is not new text. So far only Patrice has objected and over
the last year or so, everyone else wanted it.

The reason that that text is in the draft is because small
vendor CUA wanted to be able to do it that way. The
default is currently that the first column is sorted.
So far there has only been a request to add ORDER-BY. There
has been no real debate. In fact, lately it seem that when ever
anyone wants to debate anything they get all sorts
of non-technical reasons - and they resemble "I want".

Patrice did point out some omissions "non-existant fields"
for example. Those can be fixed easily. However we can not
just remove or alter that text without both a debate and TIME
after it has been proposed. One or two days is not plenty
of time to add it in. Not everyone reads this list
every day.

I don't think it is unreasonable to wait one week before
seeing if any one has other issues with it.

---

From: Doug Royer <[email-masked]>
Date: Mon, 18 Feb 2002 20:37:19 -0700

> all, thus solving (one of) the issues Patrice mentioned.

I sent a reply to Patrice's proposal and this might work (However
I don't see it on the list yet - which is odd).

It was something like:

	We could add ORDER-BY

Issues:

	Currently in CAP only the first select value is
	required to be sorted.

	So, would ORDER-BY just take one argument?
	If more than one, could you agree to:

		A CS MUST sort by the first ORDER-BY value
		and SHOULD sort by any additional arguments.

Then if we were to add your "ORDER-BY NONE";
then we could get the behavior that has been proposed
for over a year by NOT including ORDER-BY, and for those
that want un-sorted, they could add ORDER-BY NONE.

In that way we don't have to re-visit the old debate
as we will not be changing any existing behavior.

---

From: "Graham Gilmore" <[email-masked]>
Date: Tue, 19 Feb 2002 00:13:14 -0500

> and SHOULD sort by any additional arguments.

    You mentioned this in your latest response to Patrice's proposal.  It
makes sense to me, for what that's worth.
    ( s/SHOULD/MAY  ? )

> as we will not be changing any existing behavior.

    That's exactly what I meant to say.  :-)  I guess I wasn't clear enough.
I was proposing a way to keep the existing behaviour that you had outlined,
and Patrice's ORDER-BY property with a simple addition that would also
permit the CS to return unordered results.

    Graham