XQuery Optimizations

This article presents some of the optimizations that make queries faster and reduce their memory consumption.

Introduction

A query is processed in several steps:

1. Parsing: The query string is transformed to a tree of expressions.
2. Compilation: The tree is simplified, and static parts are evaluated in advance.
3. Optimization: Referenced databases are opened, and their indexes and statistics are utilized.
4. Evaluation: The resulting code is executed.
5. Serialization: The result is output.

This article presents optimizations of the three middle steps. On command-line, -V outputs the query information and the optimized query, and -x outputs the query plan. In the Graphical User Interface, the same information is shown in the Info View.

Compilation

Pre-Evaluation

Expressions that do not depend on any input are evaluated once at compile time:

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

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

Type information is utilized as well. If $i is known to be an integer, $i instance of xs:numeric is rewritten to true().

Variable Inlining

Variable references are replaced with the bound expressions, which often enables further rewritings:

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

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

Function Inlining

Function calls are replaced with the function body:

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 $n + 1

A function is inlined if its body does not exceed the size specified by INLINELIMIT (default: 50). The limit can be changed for single functions with the %basex:inline annotation. Functions annotated with %basex:memo are never inlined. During development, you can set the option to 0: the optimized query will then be closer to the original one, and error messages will contain a full stack trace.

Loop Unrolling

Loops with few iterations are unrolled:

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

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

(: rewritten to :)
2, 4

Simple maps, FLWOR expressions, filters, and the functions fn:fold-left and fn:fold-right are unrolled if they have at most 5 iterations. The limit can be changed with the UNROLLLIMIT option. Higher values increase the compile time, but they can enable index access:

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

Paths

Paths are rewritten to cheaper equivalents. For example, // is an abbreviation for /descendant-or-self::node()/, which would visit each node repeatedly. In most cases, it is rewritten to a single descendant step:

doc('addressbook.xml')//city,

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

This is not possible if the last step has a positional predicate: //city[1] returns the first city child of each node, not the first city of the document.

Redundant predicates are removed, and names in predicates are converted to name tests:

a[b]/b[c/d]/c,
db:get('addressbook')/descendant::*[name() = 'city'],

(: rewritten to :)
a/b/c[d],
db:get('addressbook')/descendant::city

FLWOR Rewritings

FLWOR expressions are simplified in many ways: for clauses with a single item become let clauses, let clauses are moved out of loops and inlined, unused variables are removed, where clauses become predicates, and the last for clause is turned into a Simple Map Operator:

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

(: rewritten to :)
(1 to 10)[. > 3] ! (. + 2)

An order by clause is dropped if it cannot change the order, and a clause with a single ascending key is rewritten to fn:sort:

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

(: rewritten to :)
sort($seq)

If only the first items of a sorted sequence are requested (with fn:head, fn:subsequence, fn:items-at or a positional predicate), fn:sort, fn:sort-by and the last order by clause of a FLWOR expression only keep the smallest items in memory instead of sorting the whole input:

(: the ten largest files, without sorting all of them :)
subsequence(
  sort-by(file:descendants('.'), { 'key': file:size#1, 'order': 'descending' }),
  1, 10
)

Simplifications

Many expressions only need part of their input: a condition needs a boolean, fn:count needs the number of items, fn:distinct-values ignores order and duplicates. This information is passed on to the input, which is simplified accordingly. Some more examples of simplified expressions:

Expression	Rewritten expression
boolean(count(//city) > 0)	exists(//city)
count(reverse($nodes))	count($nodes)
//nodes[a[. = 'x']]	//nodes[a = 'x']
$seq[1], $seq[last()]	head($seq), foot($seq)
$seq[position() != 3]	remove($seq, 3)
map:put({}, $key, $value)	map:entry($key, $value)
map:get({ 1: 'a' }, 'b')	()
if ($a) then true() else false()	boolean($a)
$a and ($a or $b)	boolean($a)
not($a) and not($b)	not($a or $b)

Rules from arithmetic and logic are only applied if they are valid in XQuery. For example, $a * 0 is not rewritten to 0 if $a may be NaN.

Optimization

Further optimizations are presented in the article on index structures.

Database Statistics

Each database stores statistics that can make the evaluation of a query unnecessary. In the following examples, factbook.xml, which is included in our full distributions, has been added to a database:

count(/mondial/country),
distinct-values(//religions),

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

Distinct values are only stored up to the number specified by MAXCATS.

Index Rewritings

Many query patterns are rewritten for index access. All of the following queries are evaluated with a single request to the text index:

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

//name[. = 'Shenzhen'],
//name[text() = 'Shenzhen'],
//name[string() = 'Shen' || 'zhen'],
//*[local-name() = 'name'][data() = 'Shenzhen'],
for $name in //name
where $name/text() = 'Shenzhen'
return $name,

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

If a query contains several candidates for index access, the database statistics are consulted to choose the most selective one. Index access is also possible within more complex queries:

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, ' ', '') } {}

contains text expressions are rewritten for the full-text index in the same manner, and the full-text options are preserved:

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

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

If the database is not known at compile time, you can enforce index rewritings.

Evaluation

Some decisions can only be made at runtime, when the actual data is known: the size and types of a sequence, the values that are compared, or whether an expression is evaluated repeatedly with the same input.

Lazy Evaluation

Expressions are evaluated as late as possible. Most results are processed item by item and never held in memory as a whole, and the evaluation stops as soon as the result is known:

(: stops after the first match :)
exists((1 to 1000000000)[. mod 1000 = 999]),

(: stops after the first value :)
head(distinct-values((1 to 1000000000) ! (. mod 1000)))

file:read-text-lines reads lines on demand, and lazy items only fetch their data when it is actually accessed.

Compact Values

The representation of a sequence is chosen while it is built: integers, doubles, strings and booleans are stored in arrays of primitive values, ranges such as 1 to 1000000000 are never materialized, and database nodes are represented by their positions in the database. As the size of a sequence is known, fn:count, fn:subsequence, fn:reverse, fn:foot and positional predicates need not traverse it:

let $seq := (1 to 10000000) ! (. * 2)
return (count($seq), $seq[last()], subsequence($seq, 5000000, 2))

Node sequences are only sorted if their nodes are not already in document order. Maps are represented according to the types of their keys and values: for example, a map with integer keys and string values is stored more compactly than a map with arbitrary items.

Comparisons

If items are compared with a large sequence, the sequence is indexed on the fly, and each comparison becomes a single lookup:

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

Joins benefit from the same technique: if the same sequence is filtered repeatedly, it is indexed from the second evaluation on:

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

If the compared sequence is a path, its result is cached as long as the root of the path and the variables it references do not change:

let $orders := doc('orders.xml')//order
return doc('customers.xml')//customer[not(@id = $orders/@customer)]

The optimizations require the default collation and items that are all numbers, all strings, or all booleans. Untyped values, such as attribute values, are treated as strings: @id = string($id) is evaluated with a lookup, whereas @id = $id is not if $id is an integer.

Folds

If the result of a fold cannot change anymore, the remaining input is skipped:

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

(: stops 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 same applies to conditions that return the unchanged result, and to boolean results that are combined with and or or. The optimization is available for fn:fold-left, fn:fold-right, array:fold-left and array:fold-right.

Tail Calls

If a function call is the last expression of a function body, the current call frame is no longer needed and can be discarded. 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)

Calls within the try clause of a try/catch expression are no tail calls, as the frame is needed to catch errors.

Node Construction

Added: Enclosed nodes are no longer copied if the result is only serialized.

Node constructors usually copy enclosed nodes. If the result is only serialized, the copies are skipped. In the following query, the database is written to the file without being duplicated in main memory:

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

The optimization applies to fn:serialize, file:write and file:append. In other cases, copying can be disabled with the COPYNODE option.

Changelog

Version 13.0

• Added: Node Construction.

Version 9.4

• Added: This article was introduced with Version 9.4.