Re: Why not reinvent the wheel?

[Joe English <jenglish@flightlab.com>]

Jonathan Robie wrote:

> Vasileios Papadimos wrote:
>
> >An unordered join would also be associative (right?), and that would turn
> >XML query optimization back into the exponential problem we know and love :-
> )
>
> Your first sentence is something I really want to think about before
> answering. As for your second...well, good query optimization is going to
> be important.


Ordered and unordered joins are both associative, in the sense that:

    [(x1,x2,x3) | x1 <- e1, (x2,x3) <- [(x2,x3) | x2 <- e2, x3 <- e3]]
==
    [(x1,x2,x3) | (x1,x2) <- [(x1,x2) | x1 <- e1, x2 <- e2], x3 <- e3]


Unordered joins however are commutative:

    FOR x1 in e1, x2 in e2 RETURN ...
==
    FOR x2 in e2, x1 in e1 RETURN ...

This is what opens up more possibilities for optimizations;
it holds for unordered joins, but not for ordered ones.

The exponential-time problem Vasileios refers to is in the size
of the query, but since it can give you a polynomially-sized
time reduction in the size of the _input_, it's usually worth
doing.

It seems to me that unordered sequences ought to be the default
in XQuery, not ordered ones.  As long as there is an option to
sort the result by document position, nothing is lost, but there
is much to be gained.


--Joe English

  jenglish@flightlab.com