Traditional optimizers fail to pick good execution plans, when faced with increasingly complex queries and large data sets. This failure is even more acute in the context of XQuery, due to the structured nature of the XML language. To overcome the vulnerabilities of traditional optimizers, we have previously proposed ROX, a Run-time Optimizer for XQueries, which interleaves optimization and execution of full tables. ROX has proved to be robust, even in the presence of strong correlations, but it has one limitation: it uses full materialization of intermediate results making it unsuitable for pipelined systems. Therefore, this paper proposes ROX-sampled, a variant of ROX, which executes small data samples, thus generating smaller intermediates. We conduct extensive experiments which proved that ROX-sampled is comparable to ROX in performance, and that it is still robust against correlations. The main bene t of ROX-sampled is that it allows the large number of pipelined databases to import the ROX idea into their optimization paradigm.
The main role of a database optimizer is to explore the search space of execution
plans and pick a good one in a small amount of time. For this, the traditional
optimization paradigm relies on cardinality estimation techniques and cost models
which should accurately estimate the size and the cost of operators. But these
estimations are not always accurate. This is caused by, among others, missing
or not up-to-date statistics [
With XQuery, the above problems are more acute. Due to the expressiveness and structured nature of XML, it is hard to build good cost models and concise synopses which accurately re ect both the structure and values in documents.
To overcome the shortcomings of traditional optimizers, we have previously
proposed ROX, a Run-time Optimizer for XQueries [
It is the alternation of optimization and execution steps followed by the full materialization of results that gives ROX its robustness. But this also makes ROX unsuitable for the pipelined execution style adopted by most database systems. This paper proposes ROX-sampled, a new variant of ROX, that removes this limitation. In a pipelined system, an operator is executed in an iterative fashion, \piping" its output directly into the next operator. This means that only small chunks of data is processed and saved in memory at each iteration. In ROX-sampled, optimization and execution phases process only data samples resulting in less materialized data, making ROX suitable to pipelined systems.
Our proposed ROX-sampled approach raises some questions. Does the use of only small samples during the optimization and execution steps jeopardize its robustness? Will the small generated intermediates be representative enough to detect data correlations? As will become clear later in this paper, ROX-sampled needs, in some situations, to perform redundant operations. Will this reduce the e ciency of ROX-sampled? The paper addresses these questions and presents experiments that investigate the performance and e ciency of ROX-sampled.
The contribution of this paper is the generalization of ROX to other pipelined execution styles, allowing the large number of pipelined databases to import the ROX idea into their optimization paradigm. The paper starts with preliminaries (Section 2) followed by a brief description of the original ROX, referred to hereafter as ROX-full (Section 3). Then ROX-sampled is explained, including the requirements that a pipelined system should support to e ciently run ROX (Section 4). Finally the conducted experiments are presented (Section 5). 2
We now describe the foundations on which ROX builds: the join graph, the used physical algorithms and indexes, and the sampling techniques. 2.1
ROX takes as input a join graph, which represents the to-be-ordered path steps
and relational joins in XQuery, without any implications on their execution order.
An input XQuery is rst completely compiled into a DAG-shaped plan [
author // / // / text() = text() = text() = text()
=
root root root root
conf1.xml conf2.xml conf3.xml conf4.xml
=
//
/
for $a1 in doc("conf1.xml")//author,
$a2 in doc("conf2.xml")//author,
$a3 in doc("conf3.xml")//author,
$a4 in doc("conf4.xml")//author,
where $a1/text() = $a2/text() and
$a1/text() = $a3/text() and
$a1/text() = $a4/text()
return $a1
=
Fig. 1. Join graph of the 4-way join XQuery returning authors that have published in
4 di erent conferences.
is then statically optimized in such a way that XPath steps, joins, selections, and
projections are grouped together forming a join graph [
ROX is implemented on top of MonetDB/XQuery where XML documents are
shredded into relational tables using a pre/post numbering scheme [
ROX uses sampling techniques to estimate the cardinality of vertices and edges in the join graph. To limit the time spent on sampling, only physical operators satisfying the zero-investment property should be sampled. These operators do not require any investment (e.g. sorting) prior to starting execution, and therefore their cost is linearly dependent on the size of the outer operand. All operators used in the ROX algorithm satisfy the zero-investment property.
To estimate the cardinality of a vertex in the join graph, the appropriate
index is sampled. To estimate the size of an edge, the corresponding operator is
sampled using an index based join sampling technique [
De nitions - Given an edge e = (v; v0), we de ne the following: { The weight of e is an estimation of the size of the operator associated to e. { edges (v; v0) is the set of all edges contained in the paths of executed edges branching from v, excluding the path starting with the edge (v; v0). We give an example of the second de nition using the join graph in Fig. 1. We refer to the edges (author(1); text()(1)), (text()(1); text()(2)), (text()(2); text()(3)), and (text()(1); text()(4)) with respectively e1, e2, e3, e4. The superscript (i) denotes the document conf i:xml. If we suppose that the above 4 edges have already been executed, then edges (text()(1); author(1)) is equal to fe2, e3, e4g. 3
This section brie y describes ROX-full, a complete presentation is given in [
Phase 2: This phase is the core of the ROX algorithm where optimization and execution steps are iterated. During optimization, a search for a superior path in the join graph is initiated. The search begins from the edge e with the smallest weight. Although e is the most selective edge, ROX does not proceed with executing it immediately. Instead chain sampling is used to search for a potential sequence of operators that is more selective than e. This can be compared to hill-climbing: ROX invests a small amount of time exploring the surrounding of e to avoid the execution of a local minimum. Note that if the vertices of edge e do not have branching unexecuted edges, no chain sampling will take place and the edge will be directly executed.
Chain sampling consists of exploring in a breadth rst manner the paths of unexecuted edges branching from e, sampling iteratively one edge in each path. By consecutively sampling edges in one path, using the output of one sampling operation as input to the next, it is possible to detect correlations between the joined vertices. The input to the sampling operation of the rst edge in each path is picked from the vertex v of e that has the smallest cardinality. At the end of each sampling iteration, a stopping condition searches for a path that is highly selective compared to the others. If such a path exists, chain sampling is stopped and the path is returned for execution. Otherwise and when all the edges in the paths branching from e are sampled, another condition checks for the most selective path and returns it for execution.
The execution phase evaluates the edges in the chosen path, using full tables as input, and materializes the result. Consequently the data in the vertices of the join graph are updated, and the weights of edges are recomputed using the newly materialized data. Optimization and execution steps are alternated until all edges in the join graph are executed.
ROX-full, the rst XQuery optimizer that interleaves optimization and execution, proved to be a robust optimizer that improves the state-of-art in XQuery optimization. It does not depend on statistics nor a cost model, and chooses good execution plans even in the presence of strong data correlations while keeping its run-time overhead limited. ROX can handle a large class of the XQuery language by optimizing the join graph as part of a bigger execution plan. Although proposed in the XQuery context and implemented on top of MonetDB/XQuery, the ROX idea can be generalized to other systems and query languages, especially SPARQL in which a large number of self-joins are expressed. 4
We now introduce ROX-sampled, a variant of ROX, which makes the ROX idea also suitable for pipelined systems. ROX-full is not suitable for pipelined systems because its execution steps process operators with full tables, hence generating large intermediates. Therefore, the execution phases in ROX-sampled does not manipulate full tables. In fact, ROX-sampled follows the same steps as ROXfull, with main di erence that only data samples are used throughout the whole algorithm. Therefore unlike ROX-full, where the optimization phase works with
phase using sample data
phase using sample data
phase using full data ROX-sampled
phase using full-sample data
plan execution using full data
a data sample while the execution phase processes full tables, both the optimization and execution phases of ROX-sampled manipulate data samples (Fig. 2). This means that the execution phases of ROX-sampled consist of sampling edges instead of executing them with full tables. Note that we use the term executing e to refer to the process of sampling e during an execution phase. Although both optimization and execution phases of ROX-sampled consist of sampling operations, each phase might use a di erent cuto limit in their sampling; execution steps might specify a larger cuto to allow for more results to be generated.
In ROX-full, two types of relations are associated to a vertex v: the full table F T (v) which contains the XML nodes corresponding to v and which is used as input and output to execution operations, and a sample table S(v) chosen randomly from F T (v) and used in the sampling operations. In ROXsampled, three relations are associated to a vertex v: the full table F T (v) which contains the XML nodes corresponding to v, a full-sample table F S(v) whose content is initially a random sample of tuples picked from F T (v) and afterwards is input and output to execution operations, and a sample table S(v) chosen randomly from F S(v) and used in the sampling operations. Full-samples in ROXsampled have the same role full tables have in ROX-full; however, they are of a much smaller size. The content of full tables in ROX-sampled is never changed, while, after each execution step, the content of full-sample tables is updated to the result of the processed steps and joins. Each decision made by an optimization phase is executed with the full-sample tables, and saved as part of a nal execution plan. When ROX-sampled terminates, the saved plan is executed using the full tables. By limiting the amount of data accessed from base tables, processed and materialized at every execution phase, it becomes possible to apply ROX to pipelined systems. An issue arises when executing or sampling an edge e with two executed vertices e = (v1; v2). A vertex v is an executed vertex if at least one of its edges is executed. The problem is that a join between two sample sets from v1 and v2 does not result in a random sample of the output of the join between v1 and v2. (a) Join graph before the execution of edge e = (v1; v2).
(b) The join graph illustrating the execution of the edge e = (v1; v2). More precisely, S(R1) ./ S(R2) 6= S(R1 ./ R2). We stress that our goal is both to estimate the size of a join or step and to create a representative sample of the operator's output, which results in reliable cardinalities and outputs when used in further evaluations. Next, a solution to the problem is presented for the case of executing e. The same solution will be used for the sampling case.
Again, the problem is that F S(v1) ./ F S(v2) does not result in a good sample of the join between v1 and v2. The solution we propose is not to use the fullsample of one of the vertices, but instead use the full table, i.e. F S(v1) ./ F T (v2). This operation will match the tuples in F S(v1) with all XML nodes in the document corresponding to v2. However, F S(v2) contains the result of all joins and steps that were already executed between v2 and other vertices. Therefore, to correctly re ect those previous executions, the output of the join between F S(v1) and F T (v2) should be used as input to re-evaluate all the executed edges branching from v2. The solution is illustrated in the join graph of Fig. 3(a) where solid and dashed lines represent respectively executed and non executed edges. First edge e is executed using as input F S(v1) and F T (v2), then the result is input to the join with F T (q1), and so on until all edges in edges (v2; v1) are reexecuted. The execution order is depicted in Fig. 3(b) as labels on edges while the arrows indicate the execution direction (i.e. the vertex from which the fullsample data is used as input for the execution). The decision to execute F S(v1) ./ F T (v2) instead of F S(v2) ./ F T (v1) aims at reducing the number of redundant evaluations, and stems from the fact that jedges (v2; v1)j < jedges (v1; v2)j.
For the sampling case of e, the same procedure is applied, but instead of using F S(v1) as input it uses S(v1). The goal of sampling e during an optimization phase is to also estimate its cardinality. Therefore, the proposed solution keeps track of the join hit ratio of all the sampled operators, to derive an estimation of the size of e. We omit the details due to lack of space. 4.2
Now that we have explained ROX-sampled and the MonetDB operators and data structures it uses, we brie y discuss the requirements to run ROX-sampled in other systems. We will focus on two points: picking the initial samples for each vertex, and the sampling of joins.
To pick the initial samples of XML nodes, ROX-sampled uses index lookups.
Another method is to have the samples pre-built and saved in the database. This
is comparable to collecting statistics, but instead of storing the data
characteristics about each attribute, a representative sample of the attribute's values is
saved. A good survey about sampling techniques is [
The sampling of edges is performed using an index-based join between a
sample and a full table. This requires the existence of an index on one of the
joined attributes. Techniques that e ciently sample a join without the use of an
index have been proposed in [
A prototype of ROX is implemented on top of the \Jun2008" release of
MonetDB/XQuery1. Path nder, the XQuery processor of MonetDB [
The experiments use the DBLP XML dataset2, and the 4-way join XQuery template shown in Fig. 1. The DBLP document is split up into 4500 single XML documents, one for each journal and conference. By replacing the 4 documents in the XQuery by 4 journal and/or conferences chosen from the same or di erent research areas, ROX-sampled will be tested against queries with different degrees of correlation. It is in general more likely that authors publish in various journals and/or conferences of one research area, than that an author publishes in multiple research areas. We cluster the document combinations, according to their anticipated correlation, into 3 groups: group 2:2, group 3:1, group 4:0. A group x:y contains all combinations of 4 documents such that x number of documents are chosen from the same research area and y number of documents are picked from a di erent area. Since it is not possible to use all 4500 documents in our experiments, we select 23 \representative" documents from 5 research areas (Database, Data mining, Information retrieval, Bioinformatics, Arti cial Intelligence), which results in 831 document combinations. The size of the documents extracted from the original DBLP document ranges from 300 B to 4.8 MB. ROX + MonetDB/XQuery evaluate these queries in less than 50 milliseconds. To achieve more reliable performance measurements, we scale the complete dataset to 45 GB by replicating each article 100 times. 1 http://monetdb.cwi.nl/XQuery/ 2 http://dblp.uni-trier.de/xml/
all equi_joins
Operators similarly ordered (a) Plan comparison.
ryque llapan1.6
Execution order of operators: Our rst experiment runs ROX-full and ROXsampled on the 831 document combinations using 3 di erent sample sizes = f100; 500; 1000g, and compares the chosen execution order of operators. Fig. 4(a) shows the percentage of queries optimized to the same plan by the two ROX. With a sample size equal to 100, only 20% of the plans are similar. This number increases to 48% when a sample size of 1000 is used. We also report the percentage of plans in which equi-joins are ordered similarly. This is of interest since the correlations between the 4 queried documents is detected through the estimated size of the equi-joins. Therefore when the two variants order the equijoins similarly, it means that they detect and handle the correlations in the same manner. The percentage of plans with the same order of equi-joins grows from 55% to 73% when the sample size increases from 100 to 1000. We conclude that an increase in the sample size reduces the di erences between the ROX variants. With a sample size equal to 1000, ROX-sampled is comparable to ROX-full in detecting correlations, and di ers mainly in ordering the step operators. Execution time of plans: The second experiment compares the execution time of the plans generated by the two ROX variants. Fig. 4(b) shows the average normalized execution time relative to the fastest time. For each variant, we time the chosen plan (pure plan), and the full-run which includes the sampling overhead. The execution time of the pure plan of ROX-sampled decreases when a bigger sample size is used. With a sample size of 100, the execution time of ROX-sampled is on average 9% longer than ROX-full, and it decreases to 6% when a sample size of 1000 is used. The execution time of the full run plans increases when a larger sample is used. We note that ROX-sampled has a higher sampling overhead than ROX-full. This is expected since, the time spent in the execution steps of ROX-sampled and to re-execute and resample some edges contributes to the optimization overhead.
Fig. 5 shows the normalized execution times of the four plans. The symbols (+) and (-) denote respectively full run plans and pure plans. We also consider the plan that a classical compile time optimizer would generate. The optimizer is able to accurately estimate the cardinality of operations carried on a single document, but lacks the ability to estimate the correlations existing among several documents. This results in an order of joins that re ects a smallest-input- rst heuristic where the two smallest inputs are joined rst, which is then joined with the third largest input, and so on. The pure plan of ROX-full is the fastest almost all the time, except for very few queries. This is caused by the use of non representative samples during chain sampling which leads to bad execution decisions. A way to solve this is by detecting the error during execution and restarting the optimization phase. ROX-sampled is close to ROX-full, but for very few queries, it can be 3 times slower. The sampling overhead (full run) is on average around 30%. This plot shows that both ROX variants are robust and insensitive to the di erent correlations, while the classical optimizer shows strong variations.
Impact of the cuto limit: In our last experiment, we vary the cuto limit used during the execution steps of ROX-sampled. As explained in Section 4, the optimization and execution steps of ROX-sampled might use a di erent cuto limit for their sampling operations. In our previous experiments, sampling during execution steps was performed with an unlimited cuto limit: all tuples in the sample input were consumed by the sampling operation. In this experiment, the cuto limit is set to the double of the sample size. The cuto limit used during the optimization steps in the current and previous experiments is equal to the sample size. Fig. 6 shows the average normalized execution time of ROX-full, ROX-sampled, and ROX-sampled using a cuto . We notice that the use of a small cuto results in a small increase in the execution times of ROX-sampled, while the use of a cuto limit of 2000 does not. Therefore, it is possible to use an appropriate cuto limit in ROX-sampled without a ecting its performance. ROX-sampled has also been evaluated against XMark documents3, and proved to be successful in picking a good execution order for the operators in the join graph. One XQuery, containing 15 XPath steps and 2 equality joins, is interesting 3 http://www.xml-benchmark.org/
500
Sample size
1000
to mention with greater detail (the query can be found in [
Adaptive query processing has been researched during the last few years.
Parametric query optimization [
Eddies [
In this paper, we described ROX-sampled which generalizes the ROX idea to pipelined systems. ROX-sampled is a proactive optimizer which does not depend on statistics nor a cost model, and is robust in face of correlations. We also discussed the requirement to run ROX-sampled on other systems. Extensive experiments were conducted and showed that the performance of ROX-sampled is close to that of ROX-full, especially with larger sample sizes.
As future work, we plan to make ROX dynamic with respect to the time it spends on optimization, i.e. able to balance between the sampling overhead and the estimated execution time of the query. Currently, the execution decisions in ROX are based on operators' cardinality. A future extension to ROX would also take into account the execution time of operators. Finally, we want to study e cient ways of integrating operators like Sorting, Distinct and Grouping into the join graph and the optimization and evaluation environment of ROX.