Bureaucrats, editor, reviewer, Administrators
13,554
edits
Changes
Jump to navigation
Jump to search
m
An XQuery expression is evaluated in Query execution encompasses multiple steps:
Each of the steps allows for numerous optimizations, some of which Some rewritings are described in this article.
{{Mark|Introduced with Version 9.6:}}
Text replacement - "<syntaxhighlight lang="xquery">" to "<pre lang='xquery'>"
This article is part of the [[XQuery|XQuery Portal]]. Optimizations are presented It presents some of the optimizations that speed up the execution time and reduce memory consumption. The text will be regularly extended with further examplesof queries.
=Introduction=
# At parse time, the '''Parsing''': The query input string – an XQuery main module – is transformed to executable code. The result is a tree representation, called the ''abstract syntax tree'' (AST).# At compile time, the '''Compilation''': The syntax tree is decorated with additional information (type information, expression properties); expressions . Expressions (nodes) in the tree are relocated, simplified, or pre-evaluated:## . Logical optimizations are performed that do not rely on external information.# '''context-independentOptimization'''. They can be applied no matter which data will be processed later on.## Physical optimizations rely on : The dynamic context information, such as database statistics or 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.# At evaluation time, the '''Evaluation''': The resulting expression tree code is processedexecuted.# '''Printing''': The results are returned to the user. Some expression (such as simple loops) can be evaluated query result is serialized and presented in iterative mannera format that is either human-readable, whereas others (such as sort operations) need to or can be fully evaluated before the first result is availablefurther processed by an API.
If you run a query on [[Command-Line_Options#Standalone|command-line]], you can use {{Code|-V}} to output detailed query information. In the [[GUI]], you can enable the Info View panel.
=Logical OptimizationsCompilation=
==Pre-Evaluation==
Parts of the query that are static and would be executed multiple times can already be evaluated at compile time:
<syntaxhighlight pre lang="'xquery"'>
for $i in 1 to 10
return 2 * 3
for $i in 1 to 10
return 6
</syntaxhighlightpre>
==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 pre lang="'xquery"'>
declare variable $INFO := true();
(: rewritten to :)
'Results: ' || count(//nodes)
</syntaxhighlightpre>
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 {{Code|try}}/{{Code|catch}}, {{Code|switch}} or {{Code|typeswitch}} expressions.
Functions can be inlined as well. The parameters are rewitten to {{Code|let}} clauses and the function is body is bound to the {{Code|return}} clause.
<syntaxhighlight pre lang="'xquery"'>
declare function local:inc($i) { $i + 1 };
for $n in 1 to 5
for $n in 1 to 5
return $n + 1
</syntaxhighlightpre>
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 pre lang="'xquery"'>
(1 to 2) ! (. * 2)
(: further rewritten to :)
2, 4
</syntaxhighlightpre>
Folds are unrolled, too:
<syntaxhighlight pre lang="'xquery"'>
let $f := function($a, $b) { $a * $b }
return fold-left(2 to 5, 1, $f)
let $f := function($a, $b) { $a * $b }
return $f($f($f($f(1, 2), 3), 4), 5)
</syntaxhighlightpre>
The standard unroll limit is <code>5</code>. It can be adjusted with the {{Option|UNROLLLIMIT}} option, e.g. via a pragma:
<syntaxhighlight pre lang="'xquery"'>
(# db:unrolllimit 10 #) {
for $i in 1 to 10
return db:openget('db' || $i)//*[text() = 'abc']
}
(: rewritten to :)
db:openget('db1')//*[text() = 'abc'],db:openget('db2')//*[text() = 'abc'],
...
db:openget('db10')//*[text() = 'abc'],</syntaxhighlightpre>
The last example indicates that index rewritings might be triggered by unrolling loops with paths on database nodes.
In most cases, paths with a double slash can be rewritten to descendant steps…
<syntaxhighlight pre lang="'xquery"'>
(: equivalent queries, with identical syntax trees :)
doc('addressbook.xml')//city,
(: rewritten to :)
doc('addressbook.xml')/descendant::city
</syntaxhighlightpre>
…unless the last step does not contain a positional predicate:
<syntaxhighlight pre lang="'xquery"'>
doc('addressbook.xml')//city[1]
</syntaxhighlightpre>
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 pre lang="'xquery"'>
(: equivalent query :)
a[b]/b[c/d]/c
(: rewritten to :)
a/b/c[d]
</syntaxhighlightpre>
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 pre lang="'xquery"'>
declare variable $name external := 'city';
db:openget('addressbook')/descendant::*[name() = $name]
(: rewritten to :)
db:openget('addressbook')/descendant::city</syntaxhighlightpre>
==FLWOR Rewritings==
* {{Code|where}} clauses are rewritten to predicates.
* {{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.
Various of these rewriting are demonstrated in the following example:
<syntaxhighlight pre lang="'xquery"'>for $a in 1 to 510
for $b in 2
where $a > 3
(: for is rewritten to let :)
for $a in 1 to 510
let $b := 2
where $a > 3
(: let is lifted up :)
let $b := 2
for $a in 1 to 510
where $a > 3
let $c := $a + $b
(: the where expression is rewritten to a predicate :)
let $b := 2
for $a in (1 to 510)[. > 3]
let $c := $a + $b
return $c
(: $b is inlined :)
for $a in (1 to 510)[. > 3]
let $c := $a + 2
return $c
(: $c is inlined :)
for $a in (1 to 510)[. > 3]
return $a + 2
(: the remaining clauses are merged and rewritten to a simple map :)
(1 to 510)[. > 3] ! (. + 2)</syntaxhighlightpre>
==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 {{Code|$i}} will always reference items of type {{Code|xs:integer}} can be utilized to simplify the expression:
<syntaxhighlight pre lang="'xquery"'>
for $i in 1 to 5
return typeswitch($i)
for $i in 1 to 5
return 'number'
</syntaxhighlightpre>
==Pure Logic==
If expressions can often be simplified:
<syntaxhighlight pre lang="'xquery"'>
for $a in ('a', '')
return $a[boolean(if(.) then true() else false())]
(: rewritten to :)
('a', '')[.]
</syntaxhighlightpre>
Boolean algebra (and set theory) comes with a set of laws that can all be applied to XQuery expressions.
* <code>true#0 and true#0</code> must raise an error; it cannot be simplified to <code>true#0</code>
=Physical OptimizationsOptimization=
Some physical optimizations are also presented in the article on [[Indexes|index structures]].
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 pre lang="'xquery"'>
count(/mondial/country)
(: rewritten to :)
231
</syntaxhighlightpre>
;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 {{Option|MAXCATS}} for more information):
<syntaxhighlight pre lang="'xquery"'>
distinct-values(//religions)
(: rewritten to :)
('Muslim', 'Roman Catholic', 'Albanian Orthodox', ...)
</syntaxhighlightpre>
==Index Rewritings==
A major feature of BaseX is the ability to rewrite all kinds of query patterns for [[Indexes#Value Indexes|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 <code>factbook.xml</code> database instance (the file included in our full distributions):
<syntaxhighlight pre lang="'xquery"'>declare context item := db:openget('factbook');
declare variable $DB := 'factbook';
//name[text() ! data() ! string() = 'Shenzhen'],
//name[. eq 'Shenzhen'],
//name[not(. ne 'Shenzhen')],
//name[not(. != 'Shenzhen')],
.//name[. = 'Shenzhen'],
//*[local-name() = 'name'][data() = 'Shenzhen'],
db:openget('factbook')//name[. = 'Shenzhen'],db:openget($DB)//name[. = 'Shenzhen'],
for $name in //name[text() = 'Shenzhen']
(: rewritten to :)
db:text('factbook', 'Shenzhen')/parent::name
</syntaxhighlightpre>
Multiple element names and query strings can be supplied in a path:
<syntaxhighlight pre lang="'xquery"'>
//*[(ethnicgroups, religions)/text() = ('Jewish', 'Muslim')]
(: rewritten to :)
db:text('factbook', ('Jewish', 'Muslim'))/(parent::*:ethnicgroups | parent::*:religions)/parent::*
</syntaxhighlightpre>
If multiple candidates for index access are found, the database statistics (if available) are consulted to choose the cheapest candidate:
<syntaxhighlight pre lang="'xquery"'>
/mondial/country
[religions = 'Muslim'] (: yields 77 results :)
(: rewritten to :)
db:text('factbook', 'Greeks')/parent::ethnicgroups/parent::country[religions = 'Muslim']
</syntaxhighlightpre>
If index access is possible within more complex FLWOR expressions, only the paths will be rewritten:
<syntaxhighlight pre lang="'xquery"'>
for $country in //country
where $country/ethnicgroups = 'German'
order by $country/name[1]
return element { replace($country/@name, ' ', '') } {}
</syntaxhighlightpre>
The [https://projects.cwi.nl/xmark/ 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 pre lang="'xquery"'>
let $auction := doc('xmark')
return for $b in $auction/site/people/person[@id = 'person0']
(: rewritten to :)
db:attribute('xmark', 'person0')/self::attribute(id)/parent::person/name/text()
</syntaxhighlightpre>
;XMark Query 8
<syntaxhighlight pre lang="'xquery"'>
let $auction := doc('xmark')
return
where $t/buyer/@person = $p/@id
return $t
return <item person='"{ $p/name/text() }'">{ count($a) }</item>,
(: rewritten to :)
db:openget('xmark')/site/people/person !
<item person='{ name/text() }'>{ count(
db:attribute('xmark', @id)/self::attribute(person)/parent::buyer/parent::closed_auction
)
}</item>
</syntaxhighlightpre>
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=
==Comparisons==
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, <code>count($input1) * count($input2)</code> comparisons would need to be made without the intermediate index structure:
<syntaxhighlight pre lang="'xquery"'>
let $input1 := file:read-text-lines('huge1.txt')
let $input2 := file:read-text-lines('huge2.txt')
return $input1[not(. = $input2)]
</syntaxhighlightpre>
=Changelog=
