Several native approaches to storing large XML data sets exist. In all of these approaches the internal data representation is designed to support any ad-hoc XQuery query. In this paper we argue that XQuery and its data model are too universal and any one-size-fits-all XML representation leads to significant overheads in terms of representation size and complexity. Based on the consideration that in many applications queries/updates workload is known in advance and does not change often, we propose an application-tailored XML storage. Elimination of the superfluous XQuery data model features and utilization of the various physical data representations improve performance on the specified workload, while ad-hoc queries support can be limited.
XML/XQuery [
Moreover, in any of the approaches there are a lot of
features that are redundant for any particular
applications. For example, suppose we have
relationallike data stored in XML. When we query such data we
don't usually use features like sibling/parent axes or
document order which are supported in all general
approaches. Another example is a set of queries to
content-oriented XML (such as an encyclopedia article
[
We believe that efficient storage and processing of XML data cannot be achieved using any general approach. The only approach to achieve great efficiency for such a universal and flexible model as XML/XQuery is to choose appropriate data structures and processing techniques for a given application (i.e. given XML schema and set of queries and updates). We need to go beyond compiling query execution plans and compile an XML storage tailored for a given workload of queries/updates. This approach allows us to support flexible XQuery model at logical level but eliminate the XQuery data model overhead at physical level. For example, querying/updating relational-like data (even more: nested-table data) can have efficiency comparable with that provided by relational databases. Content-oriented data can be processed with efficiency that is comparable with pure text-oriented systems.
In this paper we summarize the preliminary results of in-progress research on building application-tailored XML storage.
The rest of the paper is organized as follows. Within the next section we consider an example of the application which motivates this work. In Section 3 we give brief overview of the approach proposed. In Section 4 we propose physical data representation and illustrate it on example. Within the Section 5 we survey related work and consider existing approaches. And finally, Section 6 concludes and points out directions of our future work.
To illustrate advantages and various aspects of the
application-tailored XML storage we use simplified
version of the Great Russian Encyclopedia (GRE)
application [
For data processing encyclopedia application uses a number of predefined XQuery queries which are not likely to change often in the production system. Let us consider some of them (Q1-Q5): (Q1): List all articles’ titles.
declare ordering unordered; volume/article/title (Q2): Get article by id. (Q3): Get article by title.
declare ordering unordered; volume/article[@id eq “...”] declare ordering unordered; volume/article[title eq “...”] (Q4): List articles referenced from the article “1”. declare ordering unordered; for $i in volume/article
[@id eq “1”]//link return volume/article
[@id eq $i/@idref]/title (Q5): List articles which have references to the article ‘atom’.
declare ordering unordered; let $j := volume/article
[title eq “atom”]/@id for $i in volume/article where $i//link[@idref eq $j] return $i/title
Considering this simplified example we can point out some interesting observations concerned workload and XML data which we believe are more or less common to every XML processing application: 1. Rendering Markup Content - content part of the XML data usually contains a lot of rendering elements (e.g. HTML in Figures 1-2) which only aim are to be used in front-end applications (like browsers or Word processors) to display proper image on the screen and they are not used directly in queries. Often rendering markup language uses XML syntax and produces additional stress on XML database since it can’t distinguish rendering elements and elements which reflect application-level entities (articles, persons, etc) and extensively used in application defined queries.
2. Relational Like Content - besides rendering elements we can single out attributes and elements with simple content (e.g. id, idref attributes and title element in the example) which are intended to be used in queries just as properties of the application-level entities. For example, id of the article is not interested for us itself; however we are interested in article with some id.
3. Document Ordering Avoidance - quite often document order of the result doesn’t make sense for the application. Therefore in a lot of cases parent-child relationships are the only relationship we actually need between certain entities. In queries Q1 - Q5 we use standard XQuery prolog declaration to turn off results ordering.
4. Known Workload - we can derive a number of quite simple path expressions which play a role of basis for all queries in application. In our example we have volume/article, volume/article/link, volume/article/title and some modifications with predicates.
5. Fixed Workload - finally, just as in the GRE application we suppose that basic queries which are used in production systems are very rare subjected to be changed. We do not have ad-hoc queries but a number of well defined, possibly parameterized expressions.
As the paper progresses we will illustrate how these observations can be used to adjust XML storage for the specified queries.
The approach we employ can be split into two distinct phases: storage compilation for the initial workload and recompilation phase in which storage is reorganized to restore good performance after the workload changed. Below is a brief description of each phase from the logical point of view. A sketch of the physical data representation is observed in next section.
Given a specific query workload (that can include update queries) we compile optimized query plans for the workload and also produce a proper storage plan. In this plan features of XQuery data model that are not required to execute the workload are eliminated.
To build such a storage plan the following main techniques can be used:
1. Combining structural and textual data
representations (and using appropriate techniques to
process each type of representation). As we mentioned
above, majority of elements (such as rendering and
grouping elements) in content-oriented XML are not
addressed by queries/updates at all or addressed in such
a way that they can be parsed and processed efficiently
on-the-fly (using XML streaming processing
techniques). We have designed a method in which
queries are analyzed to find nodes of XML data that
should be stored in a structural way (preserving parent,
child and/or other relationships between nodes like in
[
2. Using various schemes of clustering nodes in
blocks. Sedna structured representation [
3. Eliminating redundant structures (such as redundant pointers, numbering labels, etc.) and flattening structure when possible (i.e. removing grouping elements etc.). Analyzing queries/updates we can identify which structures are redundant to support the queries/updates. Redundant pointers and grouping element can be eliminated and data can be represented using more compact data structures. For example, “relational-like” XML data can be stored in records similar to that used in relational storages. Such records are still not as rigorous as relational records to support possible irregularity in data but it is much more efficient then to use any of the general approaches. We can also flatten the structure of XML in many cases. For example, if the person element contains the address element which in turn contains street, house, city as sub-elements - such the address structure can be flatten.
Note also that the techniques eliminate only necessary XML-specific features of XML/XQuery data model. They don’t lead to losing the data or don't lead to emerging of redundant data. However our approach can be naturally extended with such powerful techniques as data projection on the basis of static query analysis (e.g. identifying constant-based predicate) or materialized views (might lead to data redundancy).
And last but not least, in the result of building
storage structures for a given application we will get
simpler data structures than that used in general
approaches: elements are less interconnected. It allows
improving not only query/update performance but also
opens the door for improving locking granularity and
building a distributed system. For example, we can
implement data parallelism on shared-nothing
architecture. The main critique of the shared-nothing
approach [
When the application is modified we might need to recompile the queries and storage. We can employ a flexible policy of recompiling the database. First, the frequency at which we need to recompile the database depends on the level of optimization that we choose to customize the storage for the given application (it might a parameter of optimization as in programming language compilers: O1-O5). Second, it might be required not as often as it might seem. Indeed it is very unlikely that new queries which address a relational-like XML will start using sibling pointers that were removed at the phase of storage compilation.
But in general case we might really need to recompile the whole database into the new structures.
The solution is as follows. The whole database can
be reconstructed using massive-parallel distributed
processing. It is true for small and middle sized
databases that it can be done quite fast even on
commodity hardware. If the reconstructed database is
distributed (see on the possibility to build a distributed
system above) it can be done really fast. In case of
simple scheme of partitioning the database (when it is
not optimized for things like collocated joins [
There are two main options in reconstructing the
database. Simple solution is to stop the database and
reconstruct it. As it presumably does not take a long
time for small or middle sized database the down time
should not be long. Advanced solution is to use
snapshot isolation (shadow/versioning) transaction
mechanism [
In this section we give a sketch of the physical data representations used in application-tailored XML storage to assure best performance for the given workload.
Let us return to the example described in Section 2 (Figures 1-2). Descriptive schema defines XML nodes decomposition according to pathways in the document. For each group the best storage method is determined in compliance with workload (Figure 3, a-c): •
Node descriptor - each node in group can be
stored as ‘node descriptor’ structure, which
through direct pointers reflects
child/sibling/parent relationships between
nodes. This way gives effective navigation and
goes very well to evaluate structured path
expressions [
Value packed in node descriptor – like in
relational databases for some nodes we employ
structures similar to the relational records [
ancestor (like id and title values shown in Figure 3, b). Actually, in this option we cluster application-level entity (like article or person) with its “relational-like” flat properties (e.g. id, name etc). It gives several advantages. Firstly, presentation is as much compact as possible since we do not have to store irrelevant pointers and numbering scheme labels. Second, it speeds up a whole number of path expressions, particularly with predicates with condition on packed nodes (like //aricle[@id eq “1”]). Finally, it also speeds up serialization process.
expected to be queried (e.g. rendering elements) can be stored in the textual form. Obviously, it saves space (since we do not have to allocate data blocks for each type of nodes) and speeds up serialization process. As mentioned in Section 3 this method is quite flexible and is not restricted by storing the whole XML sub-trees as text. Textual node can have placeholders inside for the descendants stored using first two options.
Database executor uses descriptive schema to determine the way the node is stored and as an entry point to the data blocks in which node is located.
In Figure 4 storage plan for the example defined in Section 2 is shown. According to this plan: • ‘article’ and ‘link’ nodes are stored in a structural way using node descriptors – since we directly query and serialize them in Q1-Q5 • • • queries. Numbering schema labels and some pointers are eliminated because document order and sibling axes are not used in the workload; ‘id’, ‘idref’ attributes values are packed in their parents node descriptors – they have simple content and are used in predicates to filter out application-level entities like article or link; ‘title’ nodes is queried and serialized in path expressions in Q1-Q5. Though they are also flatten in their parents nodes descriptors since they have simple content; ‘author’ nodes along with content markup nodes encircled in Figure 2 are packed in textual representation which parent is article’s node. It is used only to serialize article and has #id, #title and #link placeholders for the id, title and link values respectively.
There are a few works on building customizable XML
storage exists. In the OrientStore [
What we propose should not be mixed up with
component database [
In this paper we propose a method of compiling querydriven XML storage designed to reduce the overhead caused by the universality of XQuery data model. According to our preliminary studies and experiments, proposed method allows us to reduce the size of internal representation from several times to orders of magnitude (consequently optimize buffer memory usage) and to store data in a way that minimize the number of blocks addressed by the queries/updates. The overall effect of such optimization should make XML database significantly effective.
This paper reports the preliminary results of inprogress research. The feature work includes prototyping the system and conducting performance experiments. Also we are going to design an XQuery optimizer to construct storage plan automatically (or semi-automatically using a small number of hits) and a method of reconstructing internal XML representation which does not require database shutdown.