[Mondrian] proposal for Order function with key specification list

[John V. Sichi]

Regarding the discussion on input/output order stability below, Rushan 
was also asking about other functions such as Generate and Exists (not 
just Order).  The MS docs are silent for these functions, implying that 
MDX query authors should not make any assumptions about the result 
order. This also implies that implementations are free to use 
optimizations which might destroy order (for example, Zelaine has 
prototyped a HashMap-based implementation of Exists).  Everyone's 
favorite (NonEmptyCrossJoin) probably wants to stay unstable, but the 
more SQL pushdown is used (Filter is a better example), the more this is 
likely to come up.

The version of Generate which produces a concatenated string carries a 
strong implication that it is order-preserving, but the version which 
produces a set union is the more interesting case.

Some options are:

a) status quo (no guarantee unless specified in MS docs or in Mondrian docs)

b) declare a rule that when in doubt, order stability is implied for all 
functions where it is meaningful unless explicitly specified otherwise, 
e.g. we might declare NECJ as an exception, or that stability guarantees 
are canceled when relevant native SQL options are enabled

c) more properties?  ugh

For (b), there is the additional possibility of adding the somewhat 
distasteful "Unorder" hint:

http://msdn.microsoft.com/en-us/library/ms145609.aspx

(Incidentally, Rushan is out on vacation, so I'm working with Khanh on 
thinking through some more examples for the hierarchy-breaking question, 
after which he'll respond to your other comments on that topic.)

JVS

Julian Hyde wrote:
>> Rushan wrote:
>> There is also a note on order preservedness (after the MDX 
>> examples) of 
>> set functions. Currently there is no guarantee from Mondrian, 
>> although 
>> the implementations can be order preserving. MDX does not 
>> have a way to 
>> "hint" this property. I would like to know if any other Mondrian 
>> applications depend on this property for set functions(Generate and 
>> Exists to start with).  If that is the case, then perhaps this can be 
>> formalized in documentation.
> 
> I don't know whether order-preservation is an explicit design principle of
> MDX, but it is definitely pervasive. For example, fundamental set operations
> like set-constructor operator "{ ... }", Filter, Crossjoin, Union, Except
> all preserve order. In fact, 'set operator' is a misnomer - they work on
> lists that have an ordering and may contain duplicates.
> 
> So, let's declare that Order function is order-preserving (in
> computer-science jargon, it is a stable sort). Given this, your proposed
> 
>   order(<set-expr>, <expr1>, asc, <expr2>, asc)
> 
> is equivalent to
>  
>   order(order(<set-expr>, <expr2>, asc), <expr1>, asc)
> 
> But the of course the first form can be implemented more efficiently.