Changes

This article is part of the [[Advanced User's GuideXQuery|XQuery Portal]] and introduces . It contains information on the available index structures, which are utilized by the query optimizer to rewrite expressions and speed up query evaluation.

Nearly all examples in this article are based on The query compiler tries to optimize and speed up queries by applying the [http://files.basex.org/xml/factbook.xml factbook.xml] documentindex whenever it is possible, and seems promising. To see how a query is rewritten, please and if an index is used, you can turn on the [[GUI#Visualizations|Info View]] in the GUI or use the [[Command-Line Options#BaseX_Standalone|-V flag]] on the command line: * A message like <code>apply text index for "Japan"</code> indicates that the text index is applied to speed up the search of the shown string. The following message…* <code>no index results</code> indicates that a string in a path expression will never yield results. Hence, the path does not need to be evaluated at all.* If you cannot find any index optimization hints in the info output, it often helps if you rewrite and simplify your query. Additional examples for index rewritings are presented in our article on [[XQuery Optimizations]].

Structural indexes will always be present are automatically created and cannot be dropped by the user:

The name index contains all element and attribute references to the names of a database, all elements and the fixed-size index ids are stored attributes in the main database table. If a database is updated, new names are automatically added. Furthermore, the index is enriched with It contains some basic statistical information, such as the distinct (categorical) or minimum and maximum values number of its elements and attributes. The maximum number occurrence of categories to store per a name can be changed via [[Options#MAXCATS|MAXCATS]]. The statistics are discarded after database updates and can be recreated with the [[Commands#OPTIMIZE|OPTIMIZE]] command.

The name index is e.g. applied to pre-evaluate discard location steps that will never yield results:

<pre classlang="brush:'xquery"'>

The contents of the name indexes can be directly accessed with the XQuery functions [[{{Function|Index Module#index:element-names|index:element-names]] }} and [[{{Function|Index Module#|index:attribute-names|index:attribute}}. If a database is updated, new names will be added incrementally, but the statistical information will get out-names]]dated.

The path index (which is also called ''path summary'' or ''data guide'') stores all distinct paths of the documents in the database. It contains the same additional statistical information , such as the number of occurrence of a path, its distinct string values, and the minimum/maximum of numeric values. The maximum number of distinct values to store per name indexcan be changed via {{Option|MAXCATS}}. The statistics Distinct values are discarded after database updates also stored for elements and attributes of numeric type. Various queries will be evaluated much faster if an up-to-date path index is available (as can be recreated with observed when opening the [[CommandsGUI#OPTIMIZEVisualizations|OPTIMIZEInfo View]] command.):

The path index is applied to rewrite descendant * Descendant steps will be rewritten to multiple child steps. Child steps can be are evaluated faster, as less fewer nodes have to be accessedtraversed:

<pre classlang="brush:'xquery"'>

* The paths statistics are e.g. used to pre-evaluate the {{Code|fn:count}} functionwill be pre-evaluated by looking up the number in the index:

<pre classlang="brush:'xquery"'> (: will be rewritten and pre-evaluated by the path index :)count( doc('factbook')//country )

* The contents distinct values of the path index elements or attributes can be directly accessed with looked up in the XQuery function [[Index Module#index:facets|indexas well:facets]].

<pre lang==Resource Index=='xquery'>distinct-values(db:get('factbook')//religions)</pre>

The resource contents of the path index contains references to can be directly accessed with the XQuery function {{CodeFunction|Index|preindex:facets}} values of all XML document nodes. It speeds up the access to specific documents in a database, and it will be automatically updated when updates are performed.

The following query If a database is updated, the statistics in the path index will be sped up by the resource index:invalidated.

<pre class="brush:xquery"> =Document Index== The document index contains references to all document nodes in a database. Once documents with specific paths are requested, the index will be extended to also contain document paths.db:open('DatabaseWithLotsOfDocuments')</pre>The index generally speeds up access to single documents and database paths. It will always be kept up-to-date.

Value indexes can be optionally created and dropped by the user. The Four types of values indexes are available: a text and attribute index, and an optional token and full-text index. By default, the text, and attribute index will automatically be created by default. In the GUI, index structures can be managed in the dialog windows for creating new databases or displaying the database properties. On command-line, the commands {{Command|CREATE INDEX}} and {{Command|DROP INDEX}} are used to create and drop index structures. With {{Command|INFO INDEX}}, you get some insight into the contents of an index structure, and {{Command|SET}} allows you to change the index defaults for new databases: * <code>OPEN factbook; CREATE INDEX fulltext</code>: Open database; create full-text index* <code>OPEN factbook; INFO INDEX TOKEN</code>: Open database; show info on token index* <code>SET ATTRINDEX true; SET ATTRINCLUDE id name; CREATE DB factbook.xml</code>: Enable attribute index; only index 'id' and 'name' attributes; create database With XQuery, index structures can be created and dropped via {{Function|Database|db:optimize}}: <pre lang='xquery'>(: Optimize specified database, create full-text index for texts of the specified elements :)db:optimize( 'factbook', false(), map { 'ftindex': true(), 'ftinclude': 'p div' })</pre>

This index speeds up string-based equality tests on references text nodesof documents. It will be utilized to accelerate string comparisons in path expressions. The [[Options#UPDINDEX|UPDINDEX]] option can following queries will all be activated to keep this rewritten for index up-to-date.access:

The following queries will all be rewritten for index access: <pre classlang="brush:'xquery"'> (: 1st example 1 :)

(: 2nd example 2 :)

(: 3rd st example 3 :)for $c in db:openget('factbook')//country

Matching Before the actual index rewriting takes places, some preliminary optimizations are applied:* In example 2, the context item expression {{Code|.}} will be replaced with a {{Code|text()}} step.* In example 3, the {{Code|where}} clause will be rewritten to a predicate and attached to the first path expression. The indexed text nodes can be accessed directly requested from the index with the XQuery function [[{{Function|Database Module#db:text|db:text]]}}. The index contents indexed string values can be accessed looked up via [[{{Function|Index Module#|index:textstext}}. The {{Option|UPDINDEX}} option can be enabled to keep this indexup-to-date:texts]]. <pre lang='xquery'>db:optimize( 'mydb', true(), map { 'updindex':true(), 'textindex': true(), 'textinclude':'id' })</pre>

<pre classlang="brush:'xquery"'> (: 1st example 1 :)db:openget('Library')//Medium[Year >= '2011' and Year <= '2016'],(: 2nd example 2 :)

return db:openget('news')//entry[date-time > $min and date-time < $max]

Text nodes can be directly accessed from the index via the XQuery function [[With {{Function|Database Module#|db:text-range|db:}}, you can access all text-range]]nodes whose values are between a minimum and maximum value.

Please note that the current index structures do not support queries for numbers and dates.

Similar to the text index, this index speeds up string-based equality and range tests comparisons on attribute values. Additionally, the XQuery function {{Code|fn:id}} takes advantage of the index whenever possible. The [[Options#UPDINDEX|UPDINDEX]] option can following queries will all be activated to keep this rewritten for index up-to-date.access:

The following queries will all be rewritten for index access: <pre classlang="brush:'xquery"'>

Matching text ''Attribute nodes '' with a matching value (containing at least one from a set of given tokens) can be directly requested retrieved from the index with the XQuery functions [[Database Module#db:attributefunction {{Function|db:attribute]] and [[Database Module#db:attribute-range|db:attribute-range]]token}}. The index contents (''token strings'') can be accessed with [[{{Function|Index Module#index:attributes|index:attributes]]tokens}}.

The [[Full-Text]] index speeds contains the normalized tokens of text nodes of a document. It is utilized to speed up queries using with the {{Code|contains text}} expression, and it is capable of processing wildcard and fuzzy search operations. Internally, two index structures Three evaluation strategies are providedavailable: the default standard sequential database scan, a full-text index sorts all keys alphabetically by their character length-based evaluation and a hybrid one, combining both strategies (see [https://files.basex. It is particularly fast if fuzzy searches are performedorg/publications/Gruen%20et%20al. The second index is a compressed trie structure%20%5B2009%5D, which needs slightly more memory, but is specialized on wildcard searches%20XQuery%20Full%20Text%20Implementation%20in%20BaseX. Both index structures will be merged pdf XQuery Full Text implementation in a future version of BaseX]). The following queries are examples for expressions that will be optimized for index access (provided that the relevant index exists in a particular database):

<pre classlang="brush:'xquery"'>

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

//religions[. //text() contains text { 'Catholic', 'Roman' }

</pre>  The index provides support for the following full-text features (the values can be changed in the GUI or via the {{Command|SET}} command): * '''Stemming''': tokens are stemmed before being indexed (option: {{Option|STEMMING}})* '''Case Sensitive''': tokens are indexed in case-sensitive mode (option: {{Option|CASESENS}})* '''Diacritics''': diacritics are indexed as well (option: {{Option|DIACRITICS}})* '''Stopword List''': a stop word list can be defined to reduce the number of indexed tokens (option: {{Option|STOPWORDS}})* '''Language''': see [[Full-Text#Languages|Languages]] for more details (option: {{Option|LANGUAGE}}) The options that have been used for creating the full-text index will also be applied to the optimized full-text queries. However, the defaults can be overwritten if you supply options in your query. For example, if words were stemmed in the index, and if the query can be rewritten for index access, the query terms will be stemmed as well, unless stemming is not explicitly disabled. This is demonstrated in the following [[Commands#Command_Scripts|Command Script]]:

Matching <pre lang="xml"><commands> <!-- Create database with stemmed full-text nodes can be directly requested from the index via the XQuery function [[Full-Text Module#ft-> <set option='stemming'>true</set> <set option='ftindex'>true</set> <create-db name='test-db'> <text>house</text> </create-db> <!-- Index access:search|ft:searchQuery term will be stemmed --> <xquery> /text[. contains text { 'houses' }]]. The </xquery> <!-- Disable stemming (query will not be evaluated by the index contents can be accessed with ) --> <xquery> /text[[Full-Text Module#ft:tokens|ft:tokens. contains text { 'houses' } using no stemming]].</xquery></commands></pre>

If Value indexing can be restricted to specific elements and attributes. The nodes to be indexed can be restricted via the {{Option|TEXTINCLUDE}}, {{Option|ATTRINCLUDE}}, {{Option|TOKENINCLUDE}} and {{Option|FTINCLUDE}} options. The options take a list of name patterns, which are separated by commas. The following name patterns are supported: * <code>*</code>: all names* <code>name</code>: elements or attributes called <code>name</code>, which are in the empty default namespace* <code>*:name</code>: elements or attributes called <code>name</code>, no matter which namespace* <code>Q{uri}*</code>: all elements or attributes in the <code>uri</code> namespace* <code>Q{uri}name</code>: elements or attributes called <code>name</code> in the <code>uri</code> namespace The options can either be specified via the {{Command|SET}} command or via XQuery. With the following operations, an attribute index is created for all {{Code|id}} and {{Code|name}} attributes: ; Commands<pre lang="xml">SET ATTRINCLUDE id,nameCREATE DB factbook http://files.basex.org/xml/factbook.xml'# Restore defaultSET ATTRINCLUDE</pre> ; XQuery<pre lang='xquery'>db:create('factbook', 'http://files.basex.org/xml/factbook.xml', '', map { 'attrinclude': 'id,name' })</pre> With {{Command|CREATE INDEX}} and {{Function|Database|db:optimize}}, new selective indexing options will be applied to an existing database. ==Enforce Rewritings== In various cases, existing index structures will not be utilized by the query optimizer. This is usually the case if the name of the database is not a static string (e.g. because it is bound to a variable or passed on as an argument of a function call). Furthermore, several candidates for index rewritings may exist, and the query optimizer may decide for a rewriting that turns out to be suboptimal. With the {{Option|ENFORCEINDEX}} option, certain index rewritings can be enforced. While the option can be globally enabled, it is usually better to supply it as [[OptionsXQuery Extensions#DEBUGPragmas|DEBUGPragma]]. Two examples: * In the query below, 10 databases will be addressed. If it is known in advance that these databases contain an up-to-date text index, the index rewriting can be enforced as follows: <pre lang='xquery'>(# db:enforceindex #) { for $n in 1 to 10 let $db := 'persons' || $n return db:get($db)//person[name/text() = 'John'] }</pre> * The following query contains two predicates that may both be rewritten for index access. If the automatically chosen rewriting is set known not to be optimal, another index rewriting can enforced by surrounding the specific expression with the pragma: <pre lang='xquery'>db:get('factbook')//country [(# db:enforceindex #) { @population > '10000000' and @population < '10999999' }] [religions/text() = 'Protestant']</pre> The option can also be assigned to truepredicates with dynamic values. In the following example, the comparison of the first comparison will be rewritten for index access. Without the pragma expression, the second comparison is preferred and chosen for the rewriting because the statically known string allows for an exact cost estimation: <pre lang='xquery'>for $name in ('Germany', 'Italy')for $country in db:get('factbook')//countrywhere (# db:enforceindex #) { $country/name = $name }where $country/religions/text() = 'Protestant'return $country</pre> Please note that: * The option should only be enabled if the addressed databases exist, have all required index structures and are up-to-date (otherwise, you will be given an error message).* If you address the full-text index, and if you use non-default indexing options, you will have to specify them in your query (via {{Code|using stemming}}, {{Code|using language 'de'}}, etc).* If you have more than one enforce pragma in a single path expression, only the first will be considered.* In general, there are always expressions that cannot be rewritten for index access. If you enforce rewritings, you will have no guarantee that an index will be used. =Custom Index Structures= With XQuery, it is comparatively easy to create your own, custom index structures. The following query demonstrates how you can create a new {{Code|factbook-index}} database, which contains all texts of the original database in lower case: <pre lang='xquery'>let $db := 'factbook' let $index := <index>{ for $nodes in db:get($db)//text() group by $text := lower-case($nodes) return <text string='{ $text }'>{ for $node in $nodes return <id>{ db:node-id($node ) }</id> }</text>}</index> return db:create($db || '-index', $index, $db || '-index.xml')</pre> In the following query, a text string is created from commandsearched, and the text nodes of the original database are retrieved: <pre lang='xquery'>let $db := 'factbook'let $text := 'italian'for $id in db:get($db || '-index')//*[@string = $text]/idreturn db:get-lineid($db, $id)/..</pre> With some extra effort, and if {{Option|UPDINDEX}} is enabled for both your original and your index database (see below), your index database will support updates as well (try it, it’s fun!). =Performance= If main memory runs out while creating a value index, the number of current index operations structures will be output partially written to standard disk and eventually merged. If the memory heuristics fail for some reason (i.e. because multiple index operations run at the same time, or because the applied JVM does not support explicit garbage collections), a fixed index split sizes may be chosen via the {{Option|SPLITSIZE}} option. If {{Option|DEBUG}} is enabled, the command-line output; this might help you to choose proper find a good split size. The following example shows how the output can look like for creating a database for an XMark document with 111 MB 1 GB, and with 128 MB of available main memoryassigned to the JVM:

> basex -d -c"set ftindexSET FTINDEX ON; create db 111mb 111mbSET TOKENINDEX ON; CREATE DB xmark 1gb.xml"

.... 8132.44 ........................... 76559.99 ms (17824 29001 KB)

.. 979920 ..|...|...|.....|. 9.81 M operations, 291318576.78 92 ms (44 MB13523 KB). Recommended SPLITSIZE: 20.

.. 381870 .......|....... 3.82 M operations, 7151.77 ms (6435 KB). Recommended SPLITSIZE: 20.Indexing Tokens..........|..|.....|.. 3.82 M operations, 6309636.61 73 ms (21257 10809 KB). Recommended SPLITSIZE: 10.

..|.|.| 3 splits, 12089347 .|...|...|..|.|..| 116.33 M operations, 16420138740.47 94 ms (36 106 MB). Recommended SPLITSIZE: 12.

The info string {{Codeoutput can be interpreted as follows: * The vertical bar <code>|3 splits}} </code> indicates that three a partial full-text index structures were structure was written to disk, and .* The mean value of the recommendations can be assigned to the string {{CodeOption|12089347 operationsSPLITSIZE}} tells option. Please note that the index construction consisted recommendation is only a vague proposal, so try different values if you get main-of appr-memory errors or indexing gets too slow. Greater values will require more main memory. * In the example, the full-text index was split 12 mio times. 116 million tokens were indexed, processing time was 2.5 minutes, and final main memory consumption (after writing the index operationsto disk) was 76 MB. If we set [[Options#FTINDEXSPLITSIZE|FTINDEXSPLITSIZE]] to A good value for the fixed value split size option could be {{Code|400000015}} (12 mio divided by three), or a smaller value, we should be able to build the index and circumvent the memory heuristics.

Generally, update operations are very fast in BaseX. By default, the index structures will be invalidated by updates; as a result, queries that benefit from index structures may slow down after updates. There are discarded after an different alternatives to cope with this: * After the execution of one or more update operationoperations, the {{Command|OPTIMIZE}} command or the {{Function|Database|db:optimize}} function can be called to rebuild the index structures.* The {{Option|UPDINDEX}} option can be activated before creating or optimizing the database. As a result, queries the text, attribute and token indexes will be executed more slowlyincrementally updated after each database update. There Please note that incremental updates arenot available for the full-text index and database statistics. This also explains why the UPTODATE flag, which is e.g. displayed via {{Command|INFO DB}} or {{Function|Database|db:info}}, will be set to {{Code|false}} until the database will be optimized again (various optimizations won’t be triggered. For example, count(//item) can be extremely fast if all metadata is up-to-date.* The {{Option|AUTOOPTIMIZE}} option can be enabled before creating or optimizing the database. All outdated index structures and statistics will then be recreated after each database update. This option should only be done for small and medium-sized databases.different alternatives to cope * Both options can be used side by side: {{Option|UPDINDEX}} will take care that the value index structures will be updated as part of the actual update operation. {{Option|AUTOOPTIMIZE}} will update the remaining data structures (full-text index, database statistics). =Changelog= ;Version 9.1* Updated: [[#Enforce Rewritings|Enforce Rewritings]], support for comparisons with this:dynamic values.

After the execution of update operations, the [[Commands#OPTIMIZE|OPTIMIZE]];Version 9.0command or the * Added: [[Database Module#db:optimizeEnforce Rewritings|db:optimizeEnforce Rewritings]] function can becalled to rebuild the index structures. This way, multiple update operations will be performed faster,as the database meta data is only updated and regeneratedwhen requested by the database users.

With the ;Version 8.4* Updated: [[Options#UPDINDEXName Index|UPDINDEXName Index]] option, text and attributesindex structures will incrementally be updated. This option must beturned on before the database is created or optimized.Please note that incremental updates are not available forthe full-text index and database statistics.[[#Path Index|Path Index]]

If ;Version 8.4* Added: [[Options#AUTOOPTIMIZEToken Index|AUTOOPTIMIZEToken Index]] is activated, all outdatedindex structures and statistics will be recreated after a database update.This option should only be activated for medium-sized databases.Similar to UPDINDEX, it must be turned on before the database is createdor optimized.