Qexo

Compiling XQuery to Java bytecodes

Per Bothner

`<per@bothner.com>`

June 2004

Qexo and Kawa

Qexo compiles an XQuery module to Java bytecode.
No plan - eager natural evaluation.
Provides full access to Java libraries.
Qexo is based on and part of Kawa, which was originally (1996) written to compile the functional language Scheme.
Open-source GNU software with a liberal license.

Lazy or eager evaluation

Many implementations are demand-driven: a client requests (pulls) successive result items.
An expression is only evaluated when result needed.
Good strategy for certain queries, but large interpretative overhead.
Qexo's eager evaluation maps XQuery program structure more directly into VM state.
Avoids interpretative overhead.
Allows more natural debugging.

Event-driven data

Qexo creates explicit nodes and sequences only when need.
Otherwise, nodes and values are written using SAX-like eventsto an abstract Consumer interface.

for $i in (10, 20) return <p>{$i+1}</p>

becomes

void main (Consumer output) {
  temp_1(10, output);  temp_1(20, output);
}
void temp_1 (Object i, Consumer output) {
  output.beginElement("p");
  output.writeItem(NumOps.add(i, 1));
  output.endElement("p"); }

Node representation

A document (fragment) is stored in a TreeList.
TreeList is a compact representation using 2 arrays.
Space-efficient, improves locality and GC times.
A node is an index into a TreeList array.
Abstraction layer allows for other representations, such as database keys.
Wrapper classes provide a subset of www.w3c.dom functionality.

Compiler overview

Parsing.
QName expansion.
Module import.
Name resolution.
Analysis and optimalization.
Code generation.
Output of bytecode to .class files or for immediate execution.

Expressions

Parsing yields an Expression tree.
Representation is language-independent.
XQuery operations are represented by calls to built-in functions.
Control structures like for are represented a mapping function that applies a compiler-generated function on each item of a sequence.
Analysis and optimization are performed on Expressions.
Hooks for special optimizations and inlining of built-in functions.

Code generation

Generate bytecode by recursively walking Expression.
Default strategy: leave expression result on JVM stack.
Outer expression can ask to leave result elsewhere, perhaps as event calls on a passed-in Consumer.
Can generate custom bytecode for built-in functions.

Compiling for-expressions

FLWOR expressions are hardest to optimize.
Treat return body as anonymous function, called as needed from for clause.
More general solution: compile return body to new Consumer class.
No attempt yet at join optimizations or using indexes.

Compiling functions

XQuery function compiled to Java method.
Each XQuery parameter becomes a Java parameter.
Compiler adds a CallContext parameter.
Method result is void; result passed to caller using SAX-like event calls on CallContext.
Query body treated as a zero-parameter function.

Tail calls

A tail-call is when the last expression in a function is a function call.
Desirable that tail-calls not grow stack.
This is tricky in JVM.
Solution is to split function call into 3 parts:
1. Evaluate arguments and save them and called function in well-known location.
2. Return from method compiled from current function.
3. Call the function using an outer driver loop.

Node constructors

Node constructors are compiled to SAX-like output method calls.
Nodes written to passed-in Consumer object.
When nodes need to be materialized, the target is a TreeList.
Outermost Consumer is initially XML serializer.
Often constructors just cause output directly to serializer.
No global analysis needed.

Extensions

A Java Object without special XQuery meaning is an atomic item.
Convenient namespace-based syntax for calling Java methods.
Interactive command (read-eval-print) console.
A query can be directly compiled to a servlet.

Web applications

Web server can execute XQuery programs on client request.
Trivial deployment. Query is automatically compiled for high performance.
Expression's value is serialized (by default as XHTML); becomes server's response.
Query can set response parameters by prepending special values.
Utility functions/syntax to access query parameters.

Status

A useful and growing subset of the November '03 draft works.
I use Qexo to generate linked web pages for my personal photo album.
Performance decent but hard to measure as startup-time dominates.
Available now from http://www.gnu.org/software/qexo.