eXrQuy: Order Indifference in XQuery

There are more spots than immediately obvious in XQuery expressions where order is immaterial for evaluation—this affects most notably, but not exclusively, expressions in the scope of unordered { } and the argument of fn:unordered( ). Clearly, performance gains are lurking behind such expression contexts but the prevalent impact of order on the XQuery semantics reaches deep into any compliant XQuery processor, making it non-trivial to set this potential free. Here, we describe how the relational XQuery compiler Pathfinder uniformly exploits such order indifference in a purely algebraic fashion: Pathfinder-emitted plans faithfully implement the required XQuery order semantics but (locally) ignore order wherever this is admitted.