leowoerteler/basex

BaseX Main Repository.

basex's Issues

PlugIn Architecture for Extension Functions

Build-in functions are currently hardwired into BaseX, a uniform plugin architecture would be cleaner and nicer to external users.

Split Prefix and Local Name in QNm

Could save a lot of byte-array copying and make comparisons easier.

Inline Function Calls

User-defined functions should be inlined where possible, eliminating the call overhead and enabling more optimizations.

Example:

declare function local:foo($x as xs:integer) as xs:integer {
  if($x lt 100) then $x
  else 100
};

2 * local:foo(21)

After inlining this would be

2 * (
  let $x as xs:integer := 21
  return
    if($x lt 100) then $x
    else 100
)

which BaseX can evaluate at compile-time:

Compiling:

• binding static variable $x as xs:integer
• pre-evaluating 21 lt 100
• pre-evaluating if(true()) then $x else 100
• removing variable $x as xs:integer
• simplifying flwor expression
• pre-evaluating 2 * 21

Result: 42

Preliminaries:

• argument and result casts have to be explicit (working on it)
• function body has to be copyable
• one has to be careful while inlining recursive functions, otherwise the compiler might loop

Precompile Modules

• related objective: cleaner separation of compiler steps
• copy module (or called functions/variables/...?) before it is evaluated
• implement compile() and optimize() in all expressions
• recompile modules with changed timestamps
• challenge: import of multiple library modules with identical namespaces

Stack Frames for XQuery Function Calls

• no more variable copying
• possible to show XQuery stack trace on errors(?)
• better FLWOR implementation possible

Implement XQuery Sequences as Finger Trees

Currently BaseX implements XQuery sequences as lightweight array lists, which is fast for simple use cases, but breaks down completely when sequences are used as immutable lists because of the copying overhead.

Example:

The standard XQuery function fn:map($f, $xs) applies the function $f so all elements of the sequence $xs, concatenating the results. Implementing it in XQuery is straight-forward:

declare function local:map(
  $f as function(item()) as item()*,
  $xs as item()* 
) as item()* {
  if(empty($xs)) then ()
  else (
    $f(fn:head($xs)),
    local:map($f, fn:tail($xs))
  )
};

Unfortunately the function performs very poorly, as the result sequence has to be copied in every recursive call, which leads to an O(n²) runtime (with n being the length of the list).

Finger Trees

Finger trees are an immutable, purely functional data structure with properties nicely fitting this use case:

• cons, reverse, tail: amortized O(1)
• append and split: O(log n)

Even if should not be replaced by finger trees, an option to turn them on would be nice for idiomatic functional XQuery code.

Compile-Time Optimizations

Some of the proposed optimizations may also take place at run-time:

• Join Optimizations of nested loops: hash join/sort merge join rewritings (XMark 11 & 12; see also: http://xmlprime.blogspot.de/2010/05/join-optimizations-in-xmlprime.html)
• Structural Rewritings (ideas): XQuery Optimization Based on Rewriting

Run-Time Optimizations

Keywords

• Just-In-Time Compilation: rewriting repeatedly executed code
• Alternative Evaluation Plans: chosen (or generated?) at runtime. Examples: sequential evaluation vs. index access, positional vs. existential predicate tests
• Byte Code Generation: complete or partial byte code generation

Publications

This is a largely unreviewed list of papers revolving around XQuery and query optimizations. Some of them include compile-time optimizations:

• ROX: The Robustness of a Run-time XQuery Optimizer
• XQuery Rewrite Optimization in IBM DB2 pureXML
• Rewriting-based Optimization for XQuery
  Transformational Queries
• Trace-Based Just-in-time Compilation for Haskell
• Using XQuery for Problem Solving (may be the inspiration for additional optimizations)
• Ten Reasons why Saxon XQuery is Fast
• HXQ: A Compiler from XQuery to Haskell

Byte Code Generation

• Compiling XQuery to Java byte-codes
• The Effects of Bytecode Generation in XSLT and XQuery
• xquery-b
• Qexo