Optimizability of FLWR expressions

Dear WG,

I'm afraid your very procedural description of FLWR expressions,
together with the short circuiting behavior of the "and" operator, makes
optimizing FLWR expressions in ways that are now standard for SQL select
expressions extremely difficult.

Example 1:

for $x in //elem,
$y in expr1($x)
where $x/@attr = expr2
return expr3($x,$y)

To reduce the number of evaluations of both expr1 and expr2, I would
like to be able to rewrite this to

for $x in //elem,
where $x/@attr = expr2
return for $y in expr1($x)
       return expr3($x,$y)

But if expr1 returns the empty sequence, I am not allowed to evaluate
"expr2" in the where clause (which could raise an error).  So I cannot
do this rewrite.

Example 2 (very similar, but with an index):

for $x in //elem,
$y in expr1($x)
where $x/@attr = expr2
return expr3($x,$y)

Assume I have an index on the values of the "attr" attribute of "elem"
elements.  I want to create a query plan like

Evaluate expr2
Look up result in said index
For each element found in the index:
    Evaluate (for $y in expr1 return expr3)

Again, if expr1 returns the empty sequence, I am not allowed to evaluate
"expr2" in the where clause (which could raise an error).  Also, if
there are no "elem" elements in this particular document I am not
allowed to evaluate expr2.  So I cannot use this query plan.

Example 3 (on "and"):

for $x in //elem
where expr1($x)
and $x/@attr = expr2
return expr3($x)

Desired query plan:

Evaluate expr2
Look up result in said index
For each element found in the index:
    Evaluate (if expr1 then expr3 else ())

This time I am not allowed to evaluate expr2 if expr1 evaluates to
false.

If you really want to create a well optimizable language, I strongly
suggest giving implementers a lot more freedom in the order of
evaluation of expressions.  In the same spirit, I would also like to add
my support to comment
http://lists.w3.org/Archives/Public/www-xml-query-comments/2002Jan/0291.
html
on lazy evaluation, where similar considerations apply.  Please note
that in all these cases, the only difference can be between raising or
not raising an error.  A different evaluation order cannot result in a
different non-error value.

Regards,
Bas de Bakker
X-Hive Corporation

Received on Friday, 18 January 2002 05:04:48 UTC