Difference between revisions of "XQuery Optimizations"

From BaseX Documentation
Jump to navigation Jump to search
(12 intermediate revisions by the same user not shown)
Line 81: Line 81:
  
 
Subsequent rewritings might result in query plans that differ a lot from the original query. As this might complicate debugging, you can disable function inling during development by setting {{Option|INLINELIMIT}} to {{Code|0}}.
 
Subsequent rewritings might result in query plans that differ a lot from the original query. As this might complicate debugging, you can disable function inling during development by setting {{Option|INLINELIMIT}} to {{Code|0}}.
 +
 +
==Loop Unrolling==
 +
 +
Loops with few iterations are ''unrolled'' by the XQuery compiler to enable further optimizations:
 +
 +
<syntaxhighlight lang="xquery">
 +
(1 to 2) ! (. * 2)
 +
 +
(: rewritten to :)
 +
1 ! (. * 2), 2 ! (. * 2)
 +
 +
(: further rewritten to :)
 +
1 * 2, 2 * 2
 +
 +
(: further rewritten to :)
 +
2, 4
 +
</syntaxhighlight>
 +
 +
Folds are unrolled, too:
 +
 +
<syntaxhighlight lang="xquery">
 +
let $f := function($a, $b) { $a * $b }
 +
return fold-left(2 to 5, 1, $f)
 +
 +
(: rewritten to :)
 +
let $f := function($a, $b) { $a * $b }
 +
return $f($f($f($f(1, 2), 3), 4), 5)
 +
</syntaxhighlight>
 +
 +
The standard unroll limit is <code>5</code>. It can be adjusted with the {{Option|UNROLLLIMIT}} option, e.g. via a pragma:
 +
 +
<syntaxhighlight lang="xquery">
 +
(# db:unrolllimit 10 #) {
 +
  for $i in 1 to 10
 +
  return db:open('db' || $i)//*[text() = 'abc']
 +
}
 +
 +
(: rewritten to :)
 +
db:open('db1')//*[text() = 'abc'],
 +
db:open('db2')//*[text() = 'abc'],
 +
...
 +
db:open('db10')//*[text() = 'abc'],
 +
</syntaxhighlight>
 +
 +
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
 +
* [[Higher-Order Functions#fn:fold-left|fn:fold-left]], [[Higher-Order Functions#fn:fold-right|fn:fold-right]], {{Function|Higher-Order Functions|fn:fold-left1}}
 +
 +
Care should be taken if a higher value is selected, as memory consumption and compile time will increase.
  
 
==Paths==
 
==Paths==
Line 91: Line 145:
 
(: equivalent queries, with identical syntax trees :)
 
(: equivalent queries, with identical syntax trees :)
 
doc('addressbook.xml')//city,
 
doc('addressbook.xml')//city,
doc('addressbook.xml')/descendant-or-node()/child::city
+
doc('addressbook.xml')/descendant-or-self::node()/child::city
  
 
(: rewritten to :)
 
(: rewritten to :)
Line 136: Line 190:
 
* {{Code|where}} clauses are rewritten to predicates.
 
* {{Code|where}} clauses are rewritten to predicates.
 
* {{Code|if}} expressions in the return clause are rewritten to {{Code|where}} clauses.
 
* {{Code|if}} expressions in the return clause are rewritten to {{Code|where}} clauses.
 
+
* The last {{Code|for}} clause is merged into the {{Code|return}} clause and rewritten to a [[XQuery_3.0|Simple_Map_Operator|simple map]] expression.
Since {{Version|9.4}}, the last {{Code|for}} clause is merged into the {{Code|return}} clause and rewritten to a [[XQuery_3.0|Simple_Map_Operator|simple map]] expression.
 
  
 
Various of these rewriting are demonstrated in the following example:
 
Various of these rewriting are demonstrated in the following example:
Line 244: Line 297:
 
| Distributivity
 
| Distributivity
 
|- valign="top"
 
|- valign="top"
| <code>$a and not($a)</code>
+
| <code>$a or not($a)</code>
 
| <code>true()</code>
 
| <code>true()</code>
 
| Tertium non datur
 
| Tertium non datur
Line 394: Line 447:
 
   for $p in $auction/site/people/person
 
   for $p in $auction/site/people/person
 
   let $a :=
 
   let $a :=
     for $t in $auction/site/closedauctions/closedauction
+
     for $t in $auction/site/closed_auctions/closed_auction
 
     where $t/buyer/@person = $p/@id
 
     where $t/buyer/@person = $p/@id
 
     return $t
 
     return $t
   return <item person='{ $p/name/text() }'>{ count($a) }</item>,
+
   return <item person="{ $p/name/text() }">{ count($a) }</item>,
  
 
(: rewritten to :)
 
(: rewritten to :)
Line 407: Line 460:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
If the accessed database is not known at compile time, or if you want to give a predicate preference to another one, you can use {{Option|ENFORCEINDEX}}.
+
If the accessed database is not known at compile time, or if you want to give a predicate preference to another one, you can [[Indexes#Enforce Rewritings|enforce index rewritings]].
  
 
=Evaluation-Time Optimizations=
 
=Evaluation-Time Optimizations=
Line 424: Line 477:
  
 
=Changelog=
 
=Changelog=
 +
 +
;Version 9.6
 +
* Added: {{Option|UNROLLLIMIT}}
  
 
Introduced with Version 9.4.
 
Introduced with Version 9.4.

Revision as of 09:39, 25 April 2022

This article is part of the XQuery Portal. Optimizations are presented that speed up the execution time and reduce memory consumption.

The text will be regularly extended with further examples.

Introduction

An XQuery expression is evaluated in multiple steps:

  1. At parse time, the query string – an XQuery main module – is transformed to a tree representation, the abstract syntax tree (AST).
  2. At compile time, the syntax tree is decorated with additional information (type information, expression properties); expressions are relocated, simplified, or pre-evaluated:
    1. Logical optimizations are context-independent. They can be applied no matter which data will be processed later on.
    2. Physical optimizations rely on context information, such as database statistics or available indexes.
  3. At evaluation time, the resulting expression tree is processed.
  4. The results are returned to the user. Some expression (such as simple loops) can be evaluated in iterative manner, whereas others (such as sort operations) need to be fully evaluated before the first result is available.

Each of the steps allows for numerous optimizations, some of which are described in this article.

If you run a query on command-line, you can use -V to output detailed query information. In the GUI, you can enable the Info View panel.

Logical Optimizations

Pre-Evaluation

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

<syntaxhighlight lang="xquery"> for $i in 1 to 10 return 2 * 3

(: rewritten to :) for $i in 1 to 10 return 6 </syntaxhighlight>

Variable Inlining

The value of a variable can be inlined: The variables references are replaced by the expression that is bound to the variable. The resulting expression can often be simplified, and further optimizations can be triggered:

<syntaxhighlight lang="xquery"> 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) </syntaxhighlight>

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 rewitten to let clauses and the function is body is bound to the return clause.

<syntaxhighlight lang="xquery"> 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 </syntaxhighlight>

Subsequent rewritings might result in query plans that differ a lot from the original query. As this might complicate debugging, you can disable function inling during development by setting INLINELIMIT to 0.

Loop Unrolling

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

<syntaxhighlight lang="xquery"> (1 to 2) ! (. * 2)

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

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

(: further rewritten to :) 2, 4 </syntaxhighlight>

Folds are unrolled, too:

<syntaxhighlight lang="xquery"> let $f := function($a, $b) { $a * $b } return fold-left(2 to 5, 1, $f)

(: rewritten to :) let $f := function($a, $b) { $a * $b } return $f($f($f($f(1, 2), 3), 4), 5) </syntaxhighlight>

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

<syntaxhighlight lang="xquery"> (# db:unrolllimit 10 #) {

 for $i in 1 to 10
 return db:open('db' || $i)//*[text() = 'abc']

}

(: rewritten to :) db:open('db1')//*[text() = 'abc'], db:open('db2')//*[text() = 'abc'], ... db:open('db10')//*[text() = 'abc'], </syntaxhighlight>

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

The following expressions can be unrolled:

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

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-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…

<syntaxhighlight lang="xquery"> (: 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 </syntaxhighlight>

…unless the last step does not contain a positional predicate:

<syntaxhighlight lang="xquery"> doc('addressbook.xml')//city[1] </syntaxhighlight>

As the positional test refers to the city child step, a rewritten query would yield different steps.

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

<syntaxhighlight lang="xquery"> (: equivalent query :) a[b]/b[c/d]/c

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

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

<syntaxhighlight lang="xquery"> declare variable $name external := 'city'; db:open('addressbook')/descendant::*[name() = $name]

(: rewritten to :) db:open('addressbook')/descendant::city </syntaxhighlight>

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|simple map expression.

Various of these rewriting are demonstrated in the following example:

<syntaxhighlight lang="xquery"> for $a in 1 to 5 for $b in 2 where $a > 3 let $c := $a + $b return $c

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

(: let is lifted up :) let $b := 2 for $a in 1 to 5 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 5[. > 3] let $c := $a + $b return $c

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

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

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

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:

<syntaxhighlight lang="xquery"> 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' </syntaxhighlight>

Pure Logic

If expressions can often be simplified:

<syntaxhighlight lang="xquery"> 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', )[.] </syntaxhighlight>

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

It is not sufficient to apply the rules to arbitrary input. Examples:

  • If the operands are no 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

Physical Optimizations

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:

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:

<syntaxhighlight lang="xquery"> count(/mondial/country)

(: rewritten to :) 231 </syntaxhighlight>

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):

<syntaxhighlight lang="xquery"> distinct-values(//religions)

(: rewritten to :) ('Muslim', 'Roman Catholic', 'Albanian Orthodox', ...) </syntaxhighlight>

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.xml database instance (the file included in our full distributions):

<syntaxhighlight lang="xquery"> declare context item := db:open('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[. = 'Shenzhen'], //*[local-name() = 'name'][data() = 'Shenzhen'],

db:open('factbook')//name[. = 'Shenzhen'], db:open($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,

(: rewritten to :) db:text('factbook', 'Shenzhen')/parent::name </syntaxhighlight>

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

<syntaxhighlight lang="xquery"> //*[(ethnicgroups, religions)/text() = ('Jewish', 'Muslim')]

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

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

<syntaxhighlight lang="xquery"> /mondial/country

 [religions    = 'Muslim']  (: yields 77 results :)
 [ethnicgroups = 'Greeks']  (: yields 2 results :) 

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

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

<syntaxhighlight lang="xquery"> 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, ' ', ) } {} </syntaxhighlight>

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

<syntaxhighlight lang="xquery"> 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() </syntaxhighlight>

XMark Query 8

<syntaxhighlight lang="xquery"> 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:open('xmark')/site/people/person !

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

}</item> </syntaxhighlight>

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-Time Optimizations

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 optimizations needs to be chosen at runtime.

If sequences of items are compared against each other, a dynamic hash index will be generated, 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:

<syntaxhighlight lang="xquery"> let $input1 := file:read-text-lines('huge1.txt') let $input2 := file:read-text-lines('huge2.txt') return $input1[not(. = $input2)] </syntaxhighlight>

Changelog

Version 9.6

Introduced with Version 9.4.