XQuery Optimizations - Revision history

CG: Text replacement - "" to "

2023-12-01T16:33:28Z

Text replacement - "<syntaxhighlight lang="xquery">" to "<pre lang='xquery'>"

Show changes

CG: Text replacement - "" to ""

2023-12-01T16:30:52Z

Text replacement - "</syntaxhighlight>" to "</pre>"

CG: Text replacement - "db:pre(" to "db:get("

2022-07-20T11:34:47Z

Text replacement - "db:pre(" to "db:get("

CG: Text replacement - "db:open" to "db:pre"

2022-07-19T18:55:02Z

Text replacement - "db:open" to "db:pre"

CG: /* FLWOR Rewritings */

2022-07-19T06:55:32Z

FLWOR Rewritings

CG: /* FLWOR Rewritings */

2022-07-19T06:54:25Z

FLWOR Rewritings

CG at 06:51, 19 July 2022

2022-07-19T06:51:04Z

CG: /* Index Rewritings */

2022-07-19T06:14:19Z

Index Rewritings

CG: /* Index Rewritings */

2022-07-16T06:54:21Z

Index Rewritings

CG: /* Index Rewritings */

2022-07-16T06:53:02Z

Index Rewritings

@@ Line 28: / Line 28: @@
 for $i in 1 to 10
 return 6
-</syntaxhighlight>
+</pre>
 ==Variable Inlining==
@@ Line 52: / Line 52: @@
 (: rewritten to :)
 'Results: ' || count(//nodes)
-</syntaxhighlight>
+</pre>
 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.
@@ Line 75: / Line 75: @@
 for $n in 1 to 5
 return $n + 1
-</syntaxhighlight>
+</pre>
 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}}.
@@ Line 94: / Line 94: @@
 (: further rewritten to :)
 , 4
-</syntaxhighlight>
+</pre>
 Folds are unrolled, too:
@@ Line 105: / Line 105: @@
 let $f := function($a, $b) { $a * $b }
 return $f($f($f($f(1, 2), 3), 4), 5)
-</syntaxhighlight>
+</pre>
 The standard unroll limit is <code>5</code>. It can be adjusted with the {{Option|UNROLLLIMIT}} option, e.g. via a pragma:
@@ Line 120: / Line 120: @@
 ...
 db:get('db10')//*[text() = 'abc'],
-</syntaxhighlight>
+</pre>
 The last example indicates that index rewritings might be triggered by unrolling loops with paths on database nodes.
@@ Line 146: / Line 146: @@
 (: rewritten to :)
 doc('addressbook.xml')/descendant::city
-</syntaxhighlight>
+</pre>
 …unless the last step does not contain a positional predicate:
@@ Line 152: / Line 152: @@
 <syntaxhighlight lang="xquery">
 doc('addressbook.xml')//city[1]
-</syntaxhighlight>
+</pre>
 As the positional test refers to the city child step, a rewritten query would yield different steps.
@@ Line 164: / Line 164: @@
 (: rewritten to :)
 a/b/c[d]
-</syntaxhighlight>
+</pre>
 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:
@@ Line 174: / Line 174: @@
 (: rewritten to :)
 db:get('addressbook')/descendant::city
-</syntaxhighlight>
+</pre>
 ==FLWOR Rewritings==
@@ Line 229: / Line 229: @@
 (: the remaining clauses are merged and rewritten to a simple map :)
 (1 to 10)[. > 3] ! (. + 2)
-</syntaxhighlight>
+</pre>
 ==Static Typing==
@@ Line 244: / Line 244: @@
 for $i in 1 to 5
 return 'number'
-</syntaxhighlight>
+</pre>
 ==Pure Logic==
@@ Line 264: / Line 264: @@
 (: rewritten to :)
 ('a', '')[.]
-</syntaxhighlight>
+</pre>
 Boolean algebra (and set theory) comes with a set of laws that can all be applied to XQuery expressions.
@@ Line 326: / Line 326: @@
 (: rewritten to :)
-</syntaxhighlight>
+</pre>
 ;Return distinct values
@@ Line 337: / Line 337: @@
 (: rewritten to :)
 ('Muslim', 'Roman Catholic', 'Albanian Orthodox', ...)
-</syntaxhighlight>
+</pre>
 ==Index Rewritings==
@@ Line 391: / Line 391: @@
 (: rewritten to :)
 db:text('factbook', 'Shenzhen')/parent::name
-</syntaxhighlight>
+</pre>
 Multiple element names and query strings can be supplied in a path:
@@ Line 400: / Line 400: @@
 (: rewritten to :)
 db:text('factbook', ('Jewish', 'Muslim'))/(parent::*:ethnicgroups | parent::*:religions)/parent::*
-</syntaxhighlight>
+</pre>
 If multiple candidates for index access are found, the database statistics (if available) are consulted to choose the cheapest candidate:
@@ Line 411: / Line 411: @@
 (: rewritten to :)
 db:text('factbook', 'Greeks')/parent::ethnicgroups/parent::country[religions = 'Muslim']
-</syntaxhighlight>
+</pre>
 If index access is possible within more complex FLWOR expressions, only the paths will be rewritten:
@@ Line 425: / Line 425: @@
 order by $country/name[1]
 return element { replace($country/@name, ' ', '') } {}
-</syntaxhighlight>
+</pre>
 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:
@@ Line 438: / Line 438: @@
 (: rewritten to :)
 db:attribute('xmark', 'person0')/self::attribute(id)/parent::person/name/text()
-</syntaxhighlight>
+</pre>
 ;XMark Query 8
@@ Line 458: / Line 458: @@
+   )
 }</item>
-</syntaxhighlight>
+</pre>
 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]].
@@ Line 474: / Line 474: @@
 let $input2 := file:read-text-lines('huge2.txt')
 return $input1[not(. = $input2)]
-</syntaxhighlight>
+</pre>
 =Changelog=

@@ Line 112: / Line 112: @@
 (# db:unrolllimit 10 #) {
    for $i in 1 to 10
-   return db:pre('db' || $i)//*[text() = 'abc']
+   return db:get('db' || $i)//*[text() = 'abc']
+}
 (: rewritten to :)
-db:pre('db1')//*[text() = 'abc'],
+db:get('db1')//*[text() = 'abc'],
-db:pre('db2')//*[text() = 'abc'],
+db:get('db2')//*[text() = 'abc'],
 ...
-db:pre('db10')//*[text() = 'abc'],
+db:get('db10')//*[text() = 'abc'],
 </syntaxhighlight>
@@ Line 170: / Line 170: @@
 <syntaxhighlight lang="xquery">
 declare variable $name external := 'city';
-db:pre('addressbook')/descendant::*[name() = $name]
+db:get('addressbook')/descendant::*[name() = $name]
 (: rewritten to :)
-db:pre('addressbook')/descendant::city
+db:get('addressbook')/descendant::city
 </syntaxhighlight>
@@ Line 346: / Line 346: @@
 <syntaxhighlight lang="xquery">
-declare context item := db:pre('factbook');
+declare context item := db:get('factbook');
 declare variable $DB := 'factbook';
@@ Line 364: / Line 364: @@
 //*[local-name() = 'name'][data() = 'Shenzhen'],
-db:pre('factbook')//name[. = 'Shenzhen'],
+db:get('factbook')//name[. = 'Shenzhen'],
-db:pre($DB)//name[. = 'Shenzhen'],
+db:get($DB)//name[. = 'Shenzhen'],
 for $name in //name[text() = 'Shenzhen']
@@ Line 453: / Line 453: @@
 (: rewritten to :)
-db:pre('xmark')/site/people/person !
+db:get('xmark')/site/people/person !
    <item person='{ name/text() }'>{ count(
      db:attribute('xmark', @id)/self::attribute(person)/parent::buyer/parent::closed_auction

@@ Line 112: / Line 112: @@
 (# db:unrolllimit 10 #) {
    for $i in 1 to 10
-   return db:open('db' || $i)//*[text() = 'abc']
+   return db:pre('db' || $i)//*[text() = 'abc']
+}
 (: rewritten to :)
-db:open('db1')//*[text() = 'abc'],
+db:pre('db1')//*[text() = 'abc'],
-db:open('db2')//*[text() = 'abc'],
+db:pre('db2')//*[text() = 'abc'],
 ...
-db:open('db10')//*[text() = 'abc'],
+db:pre('db10')//*[text() = 'abc'],
 </syntaxhighlight>
@@ Line 170: / Line 170: @@
 <syntaxhighlight lang="xquery">
 declare variable $name external := 'city';
-db:open('addressbook')/descendant::*[name() = $name]
+db:pre('addressbook')/descendant::*[name() = $name]
 (: rewritten to :)
-db:open('addressbook')/descendant::city
+db:pre('addressbook')/descendant::city
 </syntaxhighlight>
@@ Line 346: / Line 346: @@
 <syntaxhighlight lang="xquery">
-declare context item := db:open('factbook');
+declare context item := db:pre('factbook');
 declare variable $DB := 'factbook';
@@ Line 364: / Line 364: @@
 //*[local-name() = 'name'][data() = 'Shenzhen'],
-db:open('factbook')//name[. = 'Shenzhen'],
+db:pre('factbook')//name[. = 'Shenzhen'],
-db:open($DB)//name[. = 'Shenzhen'],
+db:pre($DB)//name[. = 'Shenzhen'],
 for $name in //name[text() = 'Shenzhen']
@@ Line 453: / Line 453: @@
 (: rewritten to :)
-db:open('xmark')/site/people/person !
+db:pre('xmark')/site/people/person !
    <item person='{ name/text() }'>{ count(
      db:attribute('xmark', @id)/self::attribute(person)/parent::buyer/parent::closed_auction

@@ Line 187: / Line 187: @@
 * {{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.
+* 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:

@@ Line 192: / Line 192: @@
 <syntaxhighlight lang="xquery">
-for $a in 1 to 5
+for $a in 1 to 10
 for $b in 2
 where $a > 3
@@ Line 199: / Line 199: @@
 (: for is rewritten to let :)
-for $a in 1 to 5
+for $a in 1 to 10
 let $b := 2
 where $a > 3
@@ Line 207: / Line 207: @@
 (: let is lifted up :)
 let $b := 2
-for $a in 1 to 5
+for $a in 1 to 10
 where $a > 3
 let $c := $a + $b
@@ Line 214: / Line 214: @@
 (: the where expression is rewritten to a predicate :)
 let $b := 2
-for $a in 1 to 5[. > 3]
+for $a in (1 to 10)[. > 3]
 let $c := $a + $b
 return $c
 (: $b is inlined :)
-for $a in 1 to 5[. > 3]
+for $a in (1 to 10)[. > 3]
 let $c := $a + 2
 return $c
 (: $c is inlined :)
-for $a in 1 to 5[. > 3]
+for $a in (1 to 10)[. > 3]
 return $a + 2
 (: the remaining clauses are merged and rewritten to a simple map :)
-(1 to 5)[. > 3] ! (. + 2)
+(1 to 10)[. > 3] ! (. + 2)
 </syntaxhighlight>

@@ Line 1: / Line 1: @@
-This article is part of the [[XQuery|XQuery Portal]]. Optimizations are presented that speed up the execution time and reduce memory consumption.
+This article is part of the [[XQuery|XQuery Portal]]. It presents some of the optimizations that speed up the execution and reduce memory consumption of queries.
 =Introduction=
-An XQuery expression is evaluated in multiple steps:
+Query execution encompasses multiple steps:
-# At parse time, the query string – an XQuery main module – is transformed to a tree representation, the ''abstract syntax tree'' (AST).
+# '''Parsing''': The query input string is transformed to executable code. The result is a tree representation, called the ''abstract syntax tree'' (AST).
-# At compile time, the syntax tree is decorated with additional information (type information, expression properties); expressions are relocated, simplified, or pre-evaluated:
+# '''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.
-## Logical optimizations are ''context-independent''. They can be applied no matter which data will be processed later on.
+# '''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.
-## Physical optimizations rely on context information, such as database statistics or available indexes.
+# '''Evaluation''': The resulting code is executed.
-# At evaluation time, the resulting expression tree is processed.
+# '''Printing''': The query result is serialized and presented in a format that is either human-readable, or can be further processed by an API.
-Each of the steps allows for numerous optimizations, some of which are described in this article.
+Some rewritings are described in this article.
 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 Optimizations=
+=Compilation=
 ==Pre-Evaluation==
@@ Line 312: / Line 309: @@
 * <code>true#0 and true#0</code> must raise an error; it cannot be simplified to <code>true#0</code>
-=Physical Optimizations=
+=Optimization=
 Some physical optimizations are also presented in the article on [[Indexes|index structures]].
@@ Line 465: / Line 462: @@
 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=
 ==Comparisons==

@@ Line 361: / Line 361: @@
 //name[text() ! data() ! string() = 'Shenzhen'],
 .//name[. = 'Shenzhen'],
 //*[local-name() = 'name'][data() = 'Shenzhen'],

@@ Line 344: / Line 344: @@
 ==Index Rewritings==
-A major feature of BaseX is the ability to rewrite all kinds of query patterns for [Indexes#Value Indexes|index access]].
+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):