XQuery Optimizations

This article presents some of the optimizations that speed up the execution and reduce memory consumption of queries.

Introduction

Query execution encompasses multiple steps:

1. Parsing: The query input string is transformed to executable code. The result is a tree representation, called the abstract syntax tree (AST).
2. Compilation: The syntax tree is decorated with additional information (type information, expression properties). Expressions (nodes) in the tree are relocated, simplified, or pre-evaluated. Logical optimizations are performed that do not rely on external information.
3. Optimization: The dynamic context is incorporated: Referenced databases are opened and analyzed; queries are rewritten to use available indexes; accumulative and statistical operations (counts, summations, min/max, distinct values) are pre-evaluated; XPath expressions are simplified, based on the existence of steps.
4. Evaluation: The resulting code is executed.
5. Printing: The query result is serialized and presented in a format that is either human-readable, or can be further processed by an API.

This article presents rewritings of the three middle steps: compilation, optimization, and evaluation.

If you run a query on command-line, you can use -V to output detailed query information, and -x to output the resulting query plan as XML. In the Graphical User Interface, you can enable the Info View panel.

Compilation

Pre-Evaluation

Parts of the query that are static and would be executed multiple times can already be evaluated at compile time:

for $i in 1 to 10
return 2 * 3,

(: rewritten to :)
for $i in 1 to 10
return 6

Variable Inlining

The value of a variable can be inlined: Variable references are replaced with the expressions to which the variables are bound. The resulting expression can often be simplified, and further optimizations can be triggered:

declare variable $INFO := true();

let $nodes := //nodes
where $INFO
return 'Results: ' || count($nodes),

(: rewritten to :)
let $nodes := //nodes
where true()
return 'Results: ' || count($nodes),

(: rewritten to :)
let $nodes := //nodes
return 'Results: ' || count($nodes),

(: rewritten to :)
'Results: ' || count(//nodes)

As the example shows, variable declarations might be located in the query prolog and in FLWOR expressions. They may also occur (and be inlined) in try/catch, switch or typeswitch expressions.

Function Inlining

Functions can be inlined as well. The parameters are rewritten to let clauses, and the function body is used as the expression in the return clause.

declare function local:inc($i) { $i + 1 };
for $n in 1 to 5
return local:inc($n),

(: rewritten to :)
for $n in 1 to 5
return (
  let $_ := $n
  return $_ + 1
),

(: rewritten to :)
for $n in 1 to 5
return $n + 1

A function body is inlined if its number of expressions does not exceed the limit specified by INLINELIMIT, which is 50 by default. The limit can be overridden for single functions with the %basex:inline annotation. Functions annotated with %basex:memo are never inlined.

Subsequent rewritings might result in query plans that differ a lot from the original query. As this might complicate debugging, you can disable function inlining during development by setting the option to 0. Error messages will then contain a full stack trace.

Loop Unrolling

Loops with few iterations are unrolled by the XQuery compiler to enable further optimizations:

(1 to 2) ! (. * 2),

(: rewritten to :)
1 ! (. * 2), 2 ! (. * 2),

(: further rewritten to :)
1 * 2, 2 * 2,

(: further rewritten to :)
2, 4

Folds are unrolled, too:

let $f := fn($a, $b) { $a * $b }
return fold-left(2 to 5, 1, $f),

(: rewritten to :)
let $f := fn($a, $b) { $a * $b }
return $f($f($f($f(1, 2), 3), 4), 5)

The standard unroll limit is 5. It can be adjusted with the UNROLLLIMIT option, for example via a pragma:

(# db:unrolllimit 10 #) {
  for $i in 1 to 10
  return db:get('db' || $i)//*[text() = 'abc']
}

(: rewritten to :)
db:get('db1')//*[text() = 'abc'],
db:get('db2')//*[text() = 'abc'],
...
db:get('db10')//*[text() = 'abc']

The last example indicates that index rewritings might be triggered by unrolling loops with paths on database nodes.

The following expressions can be unrolled:

• Simple map expressions
• Simple FLWOR expressions
• Filter expressions
• fn:fold-left, fn:fold-right

Care should be taken if a higher value is selected, as memory consumption and compile time will increase.

Loop Unswitching

Added: Loop-invariant conditions are moved out of loops.

If the body of a simple map or a FLWOR expression is a conditional expression whose condition does not depend on the loop, the condition is evaluated only once, and the loop is duplicated in both branches. Nondeterministic and focus-dependent conditions are not moved:

for $i in 1 to 100 return if ($c) then $i + 1 else $i * 2,

(: rewritten to :)
if ($c) then (for $i in 1 to 100 return $i + 1) else (for $i in 1 to 100 return $i * 2)

Paths

Due to the compact syntax of XPath, it can make a big difference if a slash is added or omitted in a path expression. A classical example is the double slash //, which is a shortcut for /descendant-or-self::node()/. If the query is evaluated without optimizations, all nodes of a document are gathered, and for each of them, the next step is evaluated. This leads to a potentially huge number of duplicate node tree traversals, most of which are redundant, as all duplicate nodes will be removed at the end anyway.

In most cases, paths with a double slash can be rewritten to descendant steps…

(: equivalent queries, with identical syntax trees :)
doc('addressbook.xml')//city,
doc('addressbook.xml')/descendant-or-self::node()/child::city,

(: rewritten to :)
doc('addressbook.xml')/descendant::city

…unless the last step contains a positional predicate:

doc('addressbook.xml')//city[1]

As the positional test refers to the city child step, it selects the first city child of each descendant node. A rewritten query would return the first city descendant of the document, and hence a different result.

Paths may contain predicates that will be evaluated again by a later axis step. Such predicates are either shifted down or discarded:

(: equivalent query :)
a[b]/b[c/d]/c,

(: rewritten to :)
a/b/c[d]

Names of nodes can be specified via name tests or predicates. If names are supplied via external variables, for example, the predicates can often be dissolved:

declare variable $name external := 'city';
db:get('addressbook')/descendant::*[name() = $name],

(: rewritten to :)
db:get('addressbook')/descendant::city

FLWOR Rewritings

FLWOR expressions are central to XQuery and the most complex constructs the language offers. Numerous optimizations have been realized to improve the execution time:

• Nested FLWOR expressions are flattened.
• for clauses with single items are rewritten to let clauses.
• let clauses that are iterated multiple times are lifted up.
• Expressions of let clauses are inlined.
• Unused variables are removed.
• where clauses are rewritten to predicates.
• if expressions in the return clause are rewritten to where clauses.
• The last for clause is merged into the return clause and rewritten to a Simple Map Operator.

Several of these rewritings are demonstrated in the following example:

for $a in 1 to 10
for $b in 2
where $a > 3
let $c := $a + $b
return $c,

(: for is rewritten to let :)
for $a in 1 to 10
let $b := 2
where $a > 3
let $c := $a + $b
return $c,

(: let is lifted up :)
let $b := 2
for $a in 1 to 10
where $a > 3
let $c := $a + $b
return $c,

(: the where expression is rewritten to a predicate :)
let $b := 2
for $a in (1 to 10)[. > 3]
let $c := $a + $b
return $c,

(: $b is inlined :)
for $a in (1 to 10)[. > 3]
let $c := $a + 2
return $c,

(: $c is inlined :)
for $a in (1 to 10)[. > 3]
return $a + 2,

(: the remaining clauses are merged and rewritten to a simple map :)
(1 to 10)[. > 3] ! (. + 2)

Sorting

An order by clause is discarded if it cannot influence the result. If a single ascending order key is supplied, the clause is rewritten to a call of fn:sort, which is evaluated without materializing the tuple stream of the FLWOR expression:

for $i in $seq
order by 1
return $i

(: rewritten to :)
$seq

for $i in $seq
order by $i
return $i

(: rewritten to :)
sort($seq)

A sort is also dropped if its input cannot be unsorted, i.e., if it yields at most one item, or if it consists of repetitions of a single item. Nested sorts are merged:

sort(sort($seq))

(: rewritten to :)
sort($seq)

Static Typing

If the type of a value is known at compile time, type checks can be removed. In the example below, the static information that $i will always reference items of type xs:integer can be utilized to simplify the expression:

for $i in 1 to 5
return typeswitch($i)
  case xs:numeric return 'number'
  default return 'string',

(: rewritten to :)
for $i in 1 to 5
return 'number'

Simplification

An expression often does not need to deliver its exact result. A predicate is only interested in a boolean value, fn:count only in the number of items, and fn:distinct-values is not affected by duplicates or by the order of its input. Such requirements are propagated top-down through the syntax tree, and each expression can simplify itself accordingly. The following simplification contexts exist:

Context	Requested by
Effective boolean value	if, and, or, fn:boolean, fn:not, predicates, where clauses
Atomization	fn:data, fn:distinct-values, group by, order by, lookups, type checks
String arguments	casts, general comparisons, functions with string arguments
Numeric arguments	arithmetic expressions, range expressions, functions with numeric arguments
Predicate checks	predicates
Distinct values	fn:distinct-values, general comparisons
Counts and existence checks	fn:count, fn:empty, fn:exists

A boolean context allows a comparison to be replaced with a cheaper existence check:

boolean(count(//city) > 0),

(: rewritten to :)
exists(//city)

In a string context, a nested fn:string call is superfluous:

string(string($node))

(: rewritten to :)
string($node)

As only the number of items is requested in a counting context, expressions that merely rearrange their input can be discarded:

count(reverse($nodes))

(: rewritten to :)
count($nodes)

Similarly, order and duplicates are irrelevant if only distinct values are requested. The contexts are propagated recursively, so a single simplification frequently enables the next one.

Positional Predicates

Positional predicates in filter expressions are rewritten to function calls, which can be evaluated without inspecting all items of the input:

Expression	Rewritten expression
$seq[1]	head($seq)
$seq[3]	items-at($seq, 3)
$seq[position() = 2 to 4]	util:range($seq, 2, 4)
$seq[last()]	foot($seq)
$seq[position() = 1 to last() - 1]	trunk($seq)
$seq[position() != 3]	remove($seq, 3)

Non-positional predicates are simplified as well. A path that is only tested for existence is reduced to a comparison, as the predicate does not need to return nodes:

//nodes[a[. = 'x']]

(: rewritten to :)
//nodes[a = 'x']

Maps and Arrays

Calls of map and array functions are pre-evaluated if their result is statically known, and rewritten to cheaper equivalents otherwise:

Expression	Rewritten expression
map:contains({}, $key)	false()
map:get({ 'a': 1 }, 'b')	()
map:put({}, $key, $value)	map:entry($key, $value)
map:merge((map:entry($key, $value), $map))	map:put($map, $key, $value)
array:build($seq)	array { $seq }
array:flatten($seq)	$seq
array:append([], $member)	util:array-member($member)

The rewriting of array:flatten requires an argument type that contains no nested arrays. Similarly, map:size and array:size are pre-evaluated if the size of the argument is statically known.

Key types are utilized as well: if the type of a requested key is incompatible with the key type of a map, the lookup can be answered without inspecting the map at all:

map:get({ 1: 'a' }, 'string'),
map:contains({ 1: 'a' }, 'string')

(: rewritten to :)
(), false()

Pure Logic

If expressions can often be simplified:

for $a in ('a', '')
return $a[boolean(if (.) then true() else false())],

(: rewritten to :)
for $a in ('a', '')
return $a[boolean(.)],

(: rewritten to :)
for $a in ('a', '')
return $a[.],

(: rewritten to :)
('a', '')[.]

Boolean algebra (and set theory) comes with a set of laws that can all be applied to XQuery expressions.

Expression	Rewritten expression	Rule
$a + 0, $a * 1	$a	Identity
$a * 0	0	Annihilator
$a and $a	$a	Idempotence
$a and ($a or $b)	$a	Absorption
($a and $b) or ($a and $c)	$a and ($b or $c)	Distributivity
$a or not($a)	true()	Tertium non datur
not($a) and not($b)	not($a or $b)	De Morgan

The rules must not be applied blindly, as XQuery semantics can get in the way. Examples:

• If the operands are not boolean values, a conversion is enforced: $string and $string is rewritten to boolean($string).
• xs:double('NaN') * 0 yields NaN instead of 0
• true#0 and true#0 must raise an error; it cannot be simplified to true#0

Optimization

Some physical optimizations are also presented in the article on index structures.

Database Statistics

In each database, metadata is stored that can be utilized by the query optimizer to speed up or even skip query evaluation. The following examples refer to a database that contains factbook.xml, the file included in our full distributions; its root element is named mondial:

Count element nodes

The number of elements that are found for a specific path need not be evaluated sequentially. Instead, the count can directly be retrieved from the database statistics:

count(/mondial/country),

(: rewritten to :)
231

Return distinct values

The distinct values for specific names and paths can also be fetched from the database metadata, provided that the number does not exceed the maximum number of distinct values (see MAXCATS for more information):

distinct-values(//religions)

(: rewritten to :)
('Muslim', 'Roman Catholic', 'Albanian Orthodox', ...)

Index Rewritings

A major feature of BaseX is the ability to rewrite all kinds of query patterns for index access.

The following queries are all equivalent. They will be rewritten to exactly the same query that will eventually access the text index of a factbook database instance. The context item and the $DB variable of the prolog are referenced by some of the queries:

declare context item := db:get('factbook');
declare variable $DB := 'factbook';

//name[. = 'Shenzhen'],
//name[data() = 'Shenzhen'],
//name[./text() = 'Shenzhen'],
//name[text()[. = 'Shenzhen']],
//name[string() = 'Shenzhen'],
//name[string() = 'Shen' || 'zhen'],
//name[./data(text()/string()) = 'Shenzhen'],
//name[text() ! data() ! string() = 'Shenzhen'],

//name[. eq 'Shenzhen'],
//name[not(. ne 'Shenzhen')],
//name[not(. != 'Shenzhen')],
.//name[. = 'Shenzhen'],
//*[local-name() = 'name'][data() = 'Shenzhen'],

db:get('factbook')//name[. = 'Shenzhen'],
db:get($DB)//name[. = 'Shenzhen'],

for $name in //name[text() = 'Shenzhen']
return $name,

for $name in //name
return $name[text() = 'Shenzhen'],

for $name in //name
return if ($name/text() = 'Shenzhen') then $name else (),

for $name in //name
where $name/text() = 'Shenzhen'
return $name,

for $name in //name
where $name/text()[. = 'Shenzhen']
return $name,

for $node in //*
where data($node) = 'Shenzhen'
where name($node) = 'name'
return $node

(: all rewritten to :)
db:text('factbook', 'Shenzhen')/parent::name

Multiple element names and query strings can be supplied in a path:

//*[(ethnicgroups, religions)/text() = ('Jewish', 'Muslim')],

(: rewritten to :)
db:text('factbook', ('Jewish', 'Muslim'))/
  (parent::*:ethnicgroups | parent::*:religions)/
  parent::*

If multiple candidates for index access are found, the database statistics (if available) are consulted to choose the cheapest candidate:

/mondial/country
  [religions    = 'Muslim']  (: yields 77 results :)
  [ethnicgroups = 'Greeks'],  (: yields 2 results :)

(: rewritten to :)
db:text('factbook', 'Greeks')/parent::ethnicgroups/parent::country[religions = 'Muslim']

If index access is possible within more complex FLWOR expressions, only the paths will be rewritten:

for $country in //country
where $country/ethnicgroups = 'German'
order by $country/name[1]
return element { replace($country/@name, ' ', '') } {},

(: rewritten to :)
for $country in db:text('factbook', 'German')/parent::ethnicgroups/parent::country
order by $country/name[1]
return element { replace($country/@name, ' ', '') } {}

The XMark XML Benchmark comes with sample auction data and a bunch of queries, some of which are suitable for index rewritings:

XMark Query 1

let $auction := doc('xmark')
return for $b in $auction/site/people/person[@id = 'person0']
return $b/name/text(),

(: rewritten to :)
db:attribute('xmark', 'person0')/self::attribute(id)/parent::person/name/text()

XMark Query 8

let $auction := doc('xmark')
return
  for $p in $auction/site/people/person
  let $a :=
    for $t in $auction/site/closed_auctions/closed_auction
    where $t/buyer/@person = $p/@id
    return $t
  return <item person="{ $p/name/text() }">{ count($a) }</item>

(: rewritten to :)
db:get('xmark')/site/people/person !
  <item person='{ name/text() }'>{ count(
    db:attribute('xmark', @id)/self::attribute(person)/parent::buyer/parent::closed_auction
  )
}</item>

contains text expressions are rewritten for full-text index access in the same manner. The rewritten queries address the index via ft:search, and the full-text options of the original expression are preserved:

//country[name/text() contains text 'and'],

(: rewritten to :)
ft:search('factbook', 'and')/parent::name/parent::country

More complex expressions are rewritten as well. The following query is resolved by a single index request, too, and the query plan will show that the full-text options have been attached to it:

//religions[.//text() contains text { 'Catholic', 'Roman' }
  using case insensitive distance at most 2 words]

If the accessed database is not known at compile time, or if you want to give a predicate preference to another one, you can enforce index rewritings.

Evaluation

Comparisons

In many cases, the amount of data to be processed is only known after the query has been compiled. Moreover, the data that is looped through expressions may change. In those cases, the best optimization needs to be chosen at runtime.

If items are compared against a sequence with an = comparison, a dynamic hash index will be generated for the sequence, and the total number of comparisons can be significantly reduced. In the following example, count($input1) * count($input2) comparisons would need to be made without the intermediate index structure:

let $input1 := file:read-text-lines('huge1.txt')
let $input2 := file:read-text-lines('huge2.txt')
return $input1[not(. = $input2)]

The index is built incrementally and reused as long as the sequence remains the same. The optimization applies if the default collation is used, and if the items are all numeric, all strings or untyped, or all booleans. Otherwise, the items are compared sequentially. In the query plan, the comparison is represented as CmpHashG.

If a filter with an equality comparison is repeatedly applied to the same sequence, as in joins, an index is created for the filtered sequence:

let $customers := csv:doc('customers.csv')//record
for $order in json:doc('orders.json')//_
return $customers[id = $order/customer]

The first evaluation is sequential. From the second evaluation on, the id values of the sequence are indexed, and the values of $order/customer are looked up in the index. The optimization applies if the filter has a single = comparison with the default collation, if one operand depends on the context and the other does not, if the compared items fulfill the same type conditions as above, and if the filtered sequence is bound to a variable and contains more than one item. In the query plan, the expression is represented as HashFilter.

Folds

If the result of a fold can no longer change, the remaining input is skipped. The compiler derives an exit condition from the body of the function item, which is checked before each invocation. The following patterns are detected:

• if(COND) then $result else ACTION, or if(COND) then ACTION else $result, if COND does not reference the current item or position
• if($result = ITEM) then ITEM else ACTION, or if($result != ITEM) then ACTION else ITEM, for numeric and string items
• $result or ACTION, $result and ACTION, if the initial value is a boolean
• $result otherwise ACTION
• any action that yields an empty sequence if $result is empty

(: exits as soon as the result is empty :)
fold-left(1 to 1000000000, 1 to 10, fn($result, $value) {
  $result[. > $value]
}),

(: exits as soon as the first multiple of 7 has been found :)
fold-left(1 to 1000000000, (), fn($result, $value) {
  $result otherwise $value[. mod 7 = 0]
})

The optimization applies to fn:fold-left, fn:fold-right, array:fold-left and array:fold-right. If it is enabled, enable early exit is output in the query info.

Tail Calls

If the last expression of a function body is another function call, the current call frame is not required anymore. Such tail calls are marked at compile time, and the frames are eliminated at runtime. As a result, recursive functions can be evaluated with constant stack space:

declare function local:sum($seq, $result) {
  if (empty($seq)) then $result
  else local:sum(tail($seq), $result + head($seq))
};
local:sum(1 to 1000000, 0)

Frames are eliminated as soon as the query stack exceeds an internal limit.

A function call in the try clause of a try/catch expression is not a tail call: The frame is required to catch errors that are raised by the called function.

Lazy Evaluation

Memory consumption is reduced by evaluating expressions as late as possible:

• Most expressions return iterators, so intermediate results need not be cached in main memory.
• Some functions return lazy items, which only contain a reference to the actual data. The data is retrieved when it is processed for the first time, and it can be passed on to other functions in a streaming fashion.

Node Construction

Node constructors copy enclosed nodes, as the copies get new node identities. If the result of an element or document constructor is only serialized, identities are irrelevant, and enclosed nodes are included without being copied. The original nodes remain unchanged. In the following query, the database is not duplicated in main memory, but written to the file in a streaming fashion:

file:write('wrapped-db-nodes.xml', <xml>{ db:get('huge') }</xml>)

The optimization applies to the arguments of fn:serialize, file:write and file:append. Constructors are detected in sequences, in the branches of conditional expressions, in the return clause of FLWOR expressions, and in the contents of other constructors. It is skipped if the copy-namespaces declaration deviates from the default. Affected constructors are marked with a skipCopy attribute in the query plan. In all other cases, node copying can be disabled with the COPYNODE option.

Changelog

Version 13.0

• Added: Loop Unswitching, Node Construction.

Version 9.4

• Added: This article was introduced with Version 9.4.