eXist (version 2.2 and above) includes a super fast modularized range index based on Apache Lucene. This article describes eXist-db's range index.
There is also an older version of the range index, which is kept for compatibility reasons. Usage of this range index is discouraged.
Range indexes are extremely important in eXist-db. Without a proper index, evaluating a general comparison in an XPath filter expression
//foo[baz = "xyz"]) requires eXist to do a full scan over the context node set, checking the value of every node against the
argument. This is not only slow, it also limits concurrency due to necessary locking and consumes memory for loading each of the nodes. With a
well-defined index, queries will usually complete in a few milliseconds instead of seconds. The index allows the optimizer to rewrite the
expression and process the index lookup in advance, assuming that the number of
<baz> elements with content
xyz is much
smaller than the total number of elements.
To use the new range index, wrap the range index definitions into a range element:
Store this definition and do a re-index. Index files are created in the
webapp/WEB-INF/data/range directory (or wherever
you configured your data directory to be).
The indexes will be used automatically for general or value comparisons, as well as string functions like
fn:matches is currently not supported due to limitations in Lucene's regular expression handling. If you require fn:matches a
lot, consider using the old range index.
Above configuration applies to documents using MODS, a standard for bibliographical metadata. The following XPath expressions use the created indexes:
case="no" to create a case insensitive index on a string.
With a case insensitive index on
mods:namePart a match will also be found if you query for "dennis ritchie" instead of
A collation changes how strings are compared. For example, you can change the strength property of the collation to ignore diacritics, accents or case. So to compare strings ignoring accents or case, you can define your index as follows:
Please refer to the ICU documentation (which is used by eXist) for more information on collations, strength, etc.
If you know you will often use a certain combination of filters, you can combine the corresponding indexes into one to further reduce
query times. For example, the
<mods:name> element has an attribute type which qualifies the name as being "personal", "corporate" or
another predefined value.
Assume you want to speed up a query like this:
To do this you could create a combined index on
<mods:name> as follows:
This index will be used whenever the context of the filter expression is a
<mods:name>. It filters on either or both:
<mods:namePart>. Advantage: only one index lookup is required to evaluate such an expression, resulting in a
huge performance boost, in particular if the combination of filters does only match a few names out of a large set!
Note that all 3 attributes of the field element are required. The
name you give to the field can be arbitrary, but it should
be unique within the index configuration document. The
match attribute specifies the nodes to include in the field. It should be
a simple path relative to the context element.
You can skip the match attribute if you want to index the content of the context node itself. In this case, an additional attribute:
nested="yes|no" can be added to tell the indexer to skip the content of nested nodes to only index direct text children of the
The index is also used if you only query one of the defined fields, for instance:
It is important that the filter expression matches the index definition though, so the following will not be sped up by the index:
This is because the context of the filter expression here is
You can create as many combined indexes as you like, even if some of them refer to elements which are nested inside other elements having
a different index. For example, to index a complete MODS record, we could create one nested index on the root element:
and include all attributes or simple descendant elements we may want to query at the same time.
<mods:name>, even though a child of
<mods:mods>, is a complex element, so we want it to have a separate index as shown above. We therefore define both indexes:
This allows more complex queries to be optimized, for instance:
In this case, the
<mods:dateIssued> lookup will be done first, which presumably returns more hits than the name lookup. So, for
maximum performance it may still be faster to split the expression into two parts and do the name check first.
For combined indexes, you can specify conditions to restrict the values being indexed to those contained in elements that have an attribute meeting certain criteria:
This will only index the value of the
tei:term element if it has an attribute named
type with the value
main. Multiple conditions can be specified in an index definition, in which case all conditions need to match in order for the
value to be indexed.
In order to take advantage of query optimization for conditionally indexed fields, queries should be formulated like this:
//tei:term[@type = "main"][. = "xyz"]
This gets rewritten to a call to:
range:field(("mainTerm"), "eq", "xyz")
By default, condition matching is string-based and case-sensitive.
The following optional attributes can be specified on a
Specifies the operator for the comparison.
matchessupports Java regular expressions.
Turns case sensitivity on or off for string comparisons.
Turns numeric comparison on or off for equality and ordinal comparisons (
eq, ne, lt, gt, le, ge). When enabled, 01.0 will equal 1 and 2 will be less than 110 for example. The rewriter will respect the type of the value (string, numeric) when matching a condition to a predicate.
Internally the query optimizer will rewrite range lookup expressions into optimized function calls into the
http://exist-db.org/xquery/range). This happens transparently and you'll never see the function calls. However, for
debugging and testing it is sometimes useful to use the corresponding functions directly. There are two sets of functions: one for simple range
index lookups, and one for indexes on fields.
For example, assume the following index configuration:
And the following query:
This translates into:
If the index is defined on an element with fields, the entire sub-expression, the context path and all its filters, is rewritten into a single function call. For example:
This is replaced with:
Because the index root is defined on
<SPEECH>, the function will always return
If multiple filters are used and each of them has a corresponding field definition, they are combined into one call:
Note that while the field names are specified in a sequence, we add one parameter for every value to look up. This way it is possible to specify more than one value for each parameter by passing in a sequence.
Because different operators might be used inside the filters, the query engine will actually rewrite the expression to the following:
This is not easy to read, but efficient. Users will normally not see this function call. However, it sometimes helps to know what the optimizer is supposed to do and try it out explicitly.
eXist also has an older version of the range index on board (see old range index). Compared to this newer version it has three main issues:
Index entries were organized by collection, resulting in an unfortunate dependency between collection size and update speed. In simple words: updating or removing documents became slower as the collection grew. For a long time, the general recommendation was to split large document sets into multiple, smaller sub-collections if update speed was an issue.
Queries on very frequent search strings were quite inefficient: for example, a query//term[@type ="main"][. = "xyz"]
could be quite slow despite an index being defined if
@type="main"occurred very often. Unfortunately this is a common use of attributes and to make it quick, you had to reformulate the query, e.g. by moving the non-selective step to the back://term[. = "xyz"][@type = "main"]
Range indexes were baked into the core of eXist-db, making maintenance and bug fixing difficult.
The rewritten range index addresses both issues. First, indexes are now organized by document/node, so collection size does no longer matter when updating an index entry. Concerning storage, the index is entirely based on Apache Lucene instead of the B+-tree which was previously used. Most range indexes tend to be strings, so why not leave the indexing to a technology like Lucene, which is known to scale well and does a highly efficient job on string processing? Since version 4, Lucene has added support for storing numeric data types and binary data into the index, so it seemed to be a perfect match for our requirements. Lucene is integrated into eXist on a rather low level with direct access to the indexes.
To address the second issue, it is now possible to combine several fields to index into one index definition:
This can now be evaluated with a single index lookup.
Finally, the new range index is implemented as a pluggable module: a separate component which is not required for the core of eXist-db to work properly. For eXist, the index is a black box: it does not need to know what the index does. If the index is there, it will automatically plug itself into the indexing pipeline as well as the query engine. If it is not, eXist will fall back to default (brute force) query processing.
The old range index is still supported to allow existing applications to run unchanged.