∗ This work has been supported by the Rheinland-Pfalz cluster of excellence “Dependable adaptive systems and mathematical modelling” (see http://www.dasmod.de). documents. In recent years, the database community suggested many Path Processing Operators (PPOs) for efficiently evaluating structural relationships-such as parent/child or ancestor/descendant as defined by twig query patterns: Definition 1 (Twig query pattern) A twig query pattern (TQP) is a tree QT = (V, E, λ, r) with a set of vertices V , a set of edges E ⊆ V × V , a mapping λ : E → {child , descendant }, and the root of the tree r. Every TQP contains at least one output node, i. e., one or more vertices are part of the query result.
In the last few years, XML became a de-facto standard for the exchange of structured and semi-structured data. The database research community took this development into account by proposing native XML database management systems for efficient and transactional management of XML documents. One of the most important factors for success of such systems is a powerful query optimizer. Many researchers proposed sophisticated Structural Join and Holistic Twig Join algorithms as well as several index structures supporting the evaluation of twig query patterns. Even though almost all XML query evaluation approaches proposed so far use some of these methods, we believe that they provide no sufficient input for real-world cost-based query optimization scenarios, because they only cover a small part of the overall query evaluation process. To provide adequate input for a cost-based XML query optimizer, we propose the XML Query Graph Model as a new internal representation enabling a smooth transition between XQuery language level and physical algebra operators. Furthermore, we introduce a set of rewrite rules for improving the execution of twig queries, e. g., by fusing two adjacent binary join operators to a complex n-way join operator. By presenting further rewrite rules, we make the most of existing joins and indexes—even before query transformation. Using these concepts, we are ready to sketch its integration into our upcoming costbased XML query optimizer.
The algorithms for PPOs can be further partitioned into
two classes: Structural Joins (SJs) [
PPOs were optimized by various kinds of index
structures enabling fast access to element, attribute, and text
nodes. They even allow to obtain answers for complete
TQPs. Basically, the XML indexing algorithms
proposed so far can be partitioned into four classes: path
indexes, element indexes, content indexes, and hybrid
indexes. Path indexes [
Besides the various indexing approaches, there exist
three different classes of XML algebras that allow for an
algebraic optimization of XML queries: tree-based
algebras such as TAX [
Whereas the database community has been doing research on query optimization of relational queries for 30 years, the field of XML query optimization is still in its infancy. We have learned from the experience on relational query optimization, that cost-based approaches outperform heuristic-based approaches in most cases. We believe that cost-based query optimization is also the method of choice for XML query languages like XQuery. To reach this goal, we have to define an overall process for query evaluation that considers all stages of the query evaluation lifecycle beginning with the translation of the query and ending with the provision of the final query result. 1.1
Figure 1 shows the three stages of the overall query
evaluation process: analysis, optimization, and code
generation [
In general, there are two strategies for evaluating XQuery/XPath expressions: node-at-a-time and set-ata-time processing.
Node-at-a-time evaluation is inherent to the XQuery Core Language and follows a nested-loops-style evaluation approach which is similar to sub-selects in SQL. Even though it is not very efficient in most cases, it can be beneficial in low-selectivity scenarios. Figure 2(a) shows how a simple XPath expression a//b/c is evaluated using this strategy: For every a node, the evaluation context for the evaluation of //b is provided (dashed line). By iterating over all qualified b nodes the evaluation context for /c is furnished. Finally, every qualified c node is output.
On the other hand, set-at-a-time query evaluation is similar to relational merge joins. It is employed by almost all SJ and HTJ algorithms and is in most cases very efficient. Unfortunately, its employment is not always possible, because SJ and HTJ operators provide only limited support for XPath axes (in most cases only child and descendant axes are supported). Figure 2(b) shows how the XPath expression a//b/c is evaluated using this approach: First, the structural predicate // is evaluated between all a and b nodes. Afterwards, the result of the first join operator serves together with all c nodes as input for the second one which evaluates the structural predicate /.
(a) Node-at-a-time
(b) Set-at-a-time
Today, there is—to the best of our knowledge—no
query processing proposal that completely covers the
query evaluation process described in Section 1.1. At
an abstract level, all proposals can be partitioned into
two classes: advances in algebraic optimization of
XML query languages and sophisticated algorithms for
twig query processing. Algebraic optimization leads
to sophisticated ideas on normalizing and simplifying
XQuery expressions [
Using indexes for query evaluation as much as possible is not only a good heuristics for the relational world. We believe that an XML query evaluation engine should also follow this approach. Nevertheless, there exists—to the best of our knowledge—no approach which reduces the usage of PPOs for twig query evaluation to a minimum, provided there exist indexes that can deliver the results for components of—or even complete—TQPs.
The effective solution of these problems is preconditional for providing appropriate input for query optimization in general and for cost-based optimization scenarios in particular. 1.4
The contribution of this paper can be outlined as follows: We introduce the XML Query Graph Model (XQGM) as a new internal representation which is tailor-made for XML query languages such as XQuery. By introducing a new logical n-way join operator which permits the evaluation of structural and positional predicates, the XQGM is flexible enough to mediate between node-at-a-time and set-at-a-time processing approaches as well as for finding TQPs as early as possible. Using the XQGM, we provide adequate input for the optimization stage.
To allow for a simpler detection of TQPs and their subsequent mapping to QEPs, we propose a set of rewrite rules which allow to fuse as much as possible adjacent binary SJ operators to a single complex n-way join operator.
To make the most of available indexes, we define additional rules which permit to decompose n-way join operators during query transformation, if the query optimizer recognizes matching index structures. Using these rules, we can exploit existing indexes as far as possible and employ join operators only where it is absolutely necessary.
Finally, using the concepts proposed before, we sketch the architecture of our upcoming query optimizer. 1.5
Pirahesh et al. [
Carey et al. [
The classic work of McHugh and Widom [
Chen et al. [
Hidders et al. [
Re et al. [
Michiels et al. [
Mathis [
Brantner et al. [
The XML Query Graph Model (XQGM) is inspired by
Starburst’s Query Graph Model [
We define a tuple as a mapping from a set of attributes
to a set of values. Every attribute has an assigned type
which corresponds to an XQuery node type or atomic
type, e. g., element or double. A value can be formed
by any atomic value in the value space of atomic types.
All tuples, produced by a TO as output, form a so-called
tuple sequence which is an ordered sequence of tuples. In
contrast to the relational model, we additionally approve
that an attribute value can be a sequence of tuples, too.
We say a tuple is nested, if at least one tuple contains a
tuple sequence as an attribute value. A TO is a generic
object that consumes tuple sequences, transforms them
according to its inherent evaluation strategy, and finally
delivers a tuple sequence as output. The following list
shows the operators we use in the context of the XQGM:
• SELECT: Selects tuples by means of value-based
and positional predicates. Additionally, it supports
the evaluation of aggregate functions.
• JOIN: Evaluates n-way structural joins. It is
introduced after applying query unnesting as described
by Mathis [
All TOs inherit from a Generic Tuple Operator (GTO)
that provides basic functionality needed to create query
graphs. They are permitted to add additional features
such as new predicate types, e. g., for evaluating
structural relationships. Figure 4 shows how the constituents
of the GTO relate to each other [
All TOs except the access operators consist of a Head and a Body (Figure 5). The Head forms a projection specification encompassing every attribute (Head Attr.) that is sent to a consuming operator1.
An attribute calculation (Attr. Calculation) may call the ddo function. It has the same semantics as the fn:distinct-doc-order function introduced by the formal semantics of XQuery during query normalization. It sorts the outgoing tuple sequence in document order and performs duplicate elimination.
The Body provides the procedural description of how output tuples can be derived from input tuples using an inner graph whose nodes are quantified tuple variables (Tuple Var.). The edges of this inner graph can be partitioned into three classes: Definition edges connect TOs with the head of the TO that provides input tuples for the current TO. Predicate edges describe predicate expressions defined for the connected tuple variables. Output edges connect tuple variables, which have to be made 1In our graphical query representation, we hide the head of a TO, if it contains only one head attribute. accessible to other TOs, with the head of the TO.
A correlated edge connects tuple variables with the body of other TOs, for which the current evaluation context has to be provided, e. g., for evaluating existential predicates. Correlated predicate edges are drawn as dotted lines in the graphical representation. In contrast, all other edges are illustrated as solid lines.
Throughout the rest of this paper, we use the
following example—Q5 of the XMark benchmark queries
[
As mentioned in Section 2, we provide two different access operators: Node Access (NA) and Document Access (DA). A DA operator provides the root node of a document as a context node that serves as a starting point for query evaluation. An NA operator supplies a sequence of all nodes fulfilling the selection predicate, e. g., a node name. For example, the left NA operator in Figure 5 provides all price element nodes found in the document.
The join operator is responsible for the evaluation of
structural joins and is introduced during the unnesting
process as described by Mathis [
The select operator is accountable for the evaluation of value-based and positional predicates which can be assigned to F - or L-quantified tuple variables. Additionally, a select operator can evaluate functions, e. g., fn:count.
Let us have a look at our running example which is shown in Figure 6: The left subtree provides a sequence of closed auction tuples that satisfy the structural relationships evaluated by the semi-join operators. For each tuple, the lower select operator provides the evaluation context for the right subtree which establishes a sequence of tuples fulfilling the structural predicate price/text() w. r. t. to the evaluation context. Each text() tuple is sent to the top-most select operator if it fulfills the predicate fn:data >= 40. The top-most select operator applies the fn:count aggregate function to the tuple sequence and outputs the number of tuples in it. 3
Compared to query rewrite in relational database systems, our approach considers the characteristics of cost-effective PPOs (evaluation of TQPs as a whole) and indexes (evaluation of components of—or even complete—TQPs). For example, join operators can be fused to a complex join operator that can be efficiently evaluated using an HTJ or a CAS index access. Being semantics-preserving transformations, the rules for query rewrite are described according to the following textual representation: IF (Condition) THEN (Action). Condition describes the preconditions for applying the rule. In contrast, Action is a sequence of operations which have to be performed on the GTO and its subtypes. Each operation is described by a function call whose semantics is self-explanatory. The overall rewrite philosophy that drives the rewrite process can be condensed into the following statement:
Whenever possible, a query should be converted to a single join operator.
We believe that this strategy is helpful for the evaluation
of TQPs, because they can often be evaluated more
efficiently using HTJ operators rather than SJ operators [
Rewrite rule 1 allows to fuse two adjacent join operators to a single—but probably more complex—join operator. It is only applicable for two adjacent join operators that evaluate structural predicates with child or descendant axes and which are connected over an F quantified definition edge.
The correctness of this rule is obvious: Fusing two adjacent join operators along the definition edge—by copying the body of the upper operator into the lower operator’s one—does not change the semantics of the structural relationships, because we still perform a left-toright evaluation of the predicates.
Rewrite rule 1 IF ((t is Join with F-quantified tuple variable v) ∧ (v references b) ∧ (b is Join) ∧ (b and t only contain structural predicates evaluating child or descendant axes)) THEN ({CopyBody(b,t), CopyHead(b,t), CopyPredicateEdge(b,t), UpdatePredicateEdge(v), UpdateDefinitionEdge(v), Delete(b), UpdateHeadAttributes(t), UpdateAttributeCalculation(t)}); Example 1 Figure 7 shows the query graph presented in Figure 6 after applying rewrite rule 1 which results in a complex 4-way join operator. 3.2
Rewrite rule 2 permits to fuse a join operator and an adjacent select operator. The correctness of the rule is obvious: Consider a join operator that receives its inputs from a select operator. The structural predicate is evaluated on a tuple sequence that has already been filtered by the select operator. After rewrite, the join operator evaluates the predicates added during the fusion, in addition to its own ones. Those additional predicates filter the tuple sequence in the same way, as it is done before rewrite. Rewrite rule 2 IF ((t is Join with F-quantified tuple variable v) ∧ (v references b) ∧ (b is Select) ∧ (b contains no L-quantified tuple variable)) THEN ({CopyBody(b,t), CopyHead(b,t), CopyPredicateEdge(b,t), UpdatePredicateEdge(v), UpdateDefinitionEdge(v), Delete(b)});
The correctness of this rewrite is preserved by the fact that the early evaluation of the selection predicate by the NA operator does not change the query semantics compared to filtering the output of an NA operator by the select operator.
Rewrite rule 3 IF ((t is Select with F-quantified tuple variable v) ∧ (v references b) ∧ (b is Node Access)) THEN ({CopyBody(t,b), CopyHead(t,b), CopyPredicateEdge(t,b), UpdatePredicateEdge(v), CopyOutputEdge(t,b), Delete(t)}); 3.4
In the relational world, commutativity is an important
property of binary join operators which approves to
exchange the left and the right join partner. Rewrite rule 4
defines how we can partially make use of this property to
provide an import operation for query transformation to
extend the search space for join reordering. This rule is
beneficial, e. g., for a hash-based structural join operator
as described by Mathis et al. [
Rewrite rule 4 IF ((t0 is binary Join) ∧ (t0 contains tuple variables v1 and v2) ∧ (v1 and v2 are connected to a structural predicate p) ∧ (p does not evaluate the attribute axis) ∧ (v1 references TO t1) ∧ (v2 references TO v2)) THEN ({ExchangeRef(v1:t1, v2:t1), ExchangeRef(v2:t2, v1:t2), ReversePredicate(p), UpdateOutputEdge(v1), UpdateOutputEdge(v2)}); 3.3
Rewrite rule 3 permits to merge a select and an adjacent NA operator by moving the predicates from the select operator to the body of the NA operator. This rewrite is beneficial, because an NA operator can be directly mapped to a physical element or CAS index access operator. An associativity rule empowers a relational plan generator to traverse the search space of semantically equivalent queries by changing the join order. However, in the world of XML query languages, a single associativity rule is not sufficient, due to the dualism of content and structure. Instead, we will need a rule for reordering content-based joins and a set of associativity rules for structural joins that take combinations of several axes as well as early duplicate elimination and sorting into account.
Every TO that forms the root node of a tree-structured query graph has to perform duplicate elimination and sorting, independent of its operator type. On the other hand, TOs that have incoming and outgoing edges potentially need to perform duplicate elimination. Fortunately, not every join operator needs additional duplicate elimination operations. For example, a full-join TO will not create any duplicates, independent of the structural predicate it evaluates. On the other hand, a semijoin TO can create duplicates on its output. We can partition binary semi-join operators into two different equivalence classes depending on the emergence of duplicates: (1) semi-join operators where only tuples of one incoming tuple sequence can contain duplicates after join evaluation (join operators that evaluate parent/child or previous-/following-sibling axes), and (2) semi-join operators where both incoming tuple sequences can contain duplicates after join evaluation (join operators that evaluate ancestor/descendant or previous/following axes).
Example 2 Let a denote the left join partner, b denote the right join partner of a binary structural semi-join j that evaluates the child axis. If j only produces a tuples satisfying the structural predicate, then duplicate elimination has to be performed, because every node can have multiple child nodes. In contrast, if j only delivers b tuples to consuming operators, then duplicate elimination is not needed, because every node has at most one parent node. If j would evaluate a descendant axis, then duplicate elimination could be necessary in both cases, because every node can have multiple descendants and multiple ancestors.
As mentioned before, to provide a complete set of associativity rules, all combinations of axes have to be considered. Additionally, different output nodes need to be taken into account. A node is called an output node if its tuple sequence contributes to the query result or is processed in a subsequent TO. Due to space constraints, we cannot discuss all associativity rules provided in our framework, except for one rule2.
Figure 8 shows the associativity rule for one output node and two adjacent semi-join operators that evaluate the descendant axis3. To support a more fine-granular treatment of sorting and duplicate elimination, we replace a call to the ddo function, which only eliminates duplicates, by D.
We assume that the output of each join operator is implicitly sorted by the node that is used by a subsequent TO or that contributes to the final result. On the left hand side of Figure 8, a structural full-join is performed between tuples of TO A and B which needs no additional sorting or duplicate elimination. The following semijoin operator requires duplicate elimination and sorting for two reasons: (1) it has only incoming edges, (2) each tuple of the incoming tuple sequence can have multiple descendant c nodes. On the right side, a structural join is performed first between TO B and TO C. Because this structural relationship is evaluated using a semi-join, we need additional duplicate elimination, because every b node can have multiple c descendants. The following semi-join operator requires duplicate elimination for the same reason, but it needs no additional sorting because of our implicit sorting assumption. The main idea that justifies our rewrite philosophy of Section 3 is used for physical HTJ operators that can efficiently evaluate n-way joins. If the plan generator recognizes the availability of path or CAS indexes that can evaluate a branch of—or even a complete—TQP, this index should be used instead of evaluating the twig using a join operator4. To enable a decomposition of complex (n-way) join operators, we have to consider two cases, depending on how many twig paths can be answered using indexes. If there are several indexes available for a given path, then the one is chosen that can answer the largest fraction of the path. To make use of this index for query evaluation, we apply rewrite rule 5 to split the complex join operator into two parts: one part that is evaluated using the index and the other part that will be evaluated using an HTJ or an SJ operator.
Rewrite rule 5 IF ((t is n-way Join) ∧ (t contains one path that can be answered using an available index) ∧ (t contains tuple variables v0, v1, and v2) ∧ (v0 is the twig’s root node) ∧ (all paths from v0 over v1 can be answered by no index) ∧ (at least one index can answer a path from v0 over v2)) THEN({CreateJoinOp(tb), MovePath(v0, v2, t, tb), UpdateHead(tb), InsertDefEdge(v0, tb}); If we can answer more than one twig path using available indexes, then the path of those indexes overlaps at the twig query’s root node. To get rid of this overlap, we use rewrite rule 6 to split the operator into two new join operators and connect them using the old join operator now evaluating a structural self-join to perform an intersection on the outgoing tuples of the newly created join operators.
Rewrite rule 6 IF (t is n-way Join) ∧ (t describes TQP that can make use of at least two indexes) ∧ (t contains tuple variables v0, v1, and v2) ∧ (v0 forms the twig pattern’s root node) ∧ (v1 and v2 are child nodes of v0) ∧ (v1 and v2 are root nodes of subtrees) ∧ 4Using HTJ or SJ operators for twig query evaluation always serves as a fallback strategy, if no index matches the twig. (for each path from v0 over v1 resp. v2 at least one index matches) THEN({CreateJoinOp(tl), CreateJoinOp(tr), MoveSubtree(t, tl, v1), MoveSubtree(t, tr, v2), InsertTupleVar(t, v3), InsertTupleVar(t, v4), InsertPredicate(t, self, v3, v4), UpdateHead(t), UpdateHead(tl), UpdateHead(tr), InsertDefEdge(v3, tl), InsertDefEdge(t4, tr)}); By applying rewrite rules 5 and 6 recursively on the query graph, we obtain a resulting query graph that uses as much as possible existing path indexes or CAS indexes for query evaluation.
Example 3 To show the application of rewrite rules 5, we assume that there exist two different indexes which we can use for query evaluation: I1(//closed auctions/closed auction) and I2(//price[String]). The right subtree of the query graph shown in Figure 7 can be directly mapped to an index access operator for index I2. On the other hand, index I1 cannot be used for query evaluation, yet. By applying rewrite rule 5, we get the query graph shown in Figure 9. As a consequence, index I1 can now be used for query evaluation.
Considering the transformations illustrated in Figures 6 to 9, we can see how the rewritings push the QG towards a better starting point for query transformation by finding TQPs and exploiting existing indexes as early as possible. After query unnesting shown in Figure 6, the sequence of three semi-join operators was transformed into a single 4-way join operator (see Figure 7). Figure 8 sketched how associativity rules can be defined that help to enhance the search space for a cost-based query optimizer. Finally, Figure 9 exemplified how the knowledge on existing indexes helps to rewrite the QG w. r. t. a simpler mapping to index access operators during query transformation. 4
After having introduced the XQGM as our internal representation for XQuery expressions and defined various rules for query rewrite, we are now ready to discuss the infrastructure for cost-based XML query optimization which takes a rewritten QG as input and transforms it into a—hopefully—near-optimal QEP. 4.1
Figure 10 shows the overall architecture of an XML query optimizer which will be integrated into our prototype of a native XML database management system called the XML Transaction Coordinator (XTC)5. The optimizer consists of five major components: The Generic Pattern Matcher (GPM) provides means for extensible rule-based pattern matching on arbitrary graphstructured trees. Using the GPM, a developer just describes the pattern to be matched in a declarative manner. As a consequence, the developer has only to implement the transformation code manually.
The Rewriter applies the rewrite rules described in Section 3 to the QG and uses the GPM for pattern matching.
The Plan Generator is responsible for the transformation of QGs to QEPs. Depending on the plan generation strategy employed, a heuristics-based or a costbased optimization approach is chosen. If no cost model is present, a heuristics-based approach has to be followed by using a static set of transformation rules. On the other hand, using a cost model and statistical information, a cost-based query optimization can be applied. No matter which plan generation approach is used, we also use the GPM for pattern matching to allow for a generation of alternative plans.
One of the main ingredients of a cost-based query
optimizer is the Cost Model. It uses the statistical
information provided by the Statistics component for cost
estimation. In contrast to classic cost-based query
optimization, the cost model is not solely used during query
transformation. If we step back and have a look at the overall
query evaluation process, the following question arises
even during the analysis stage: Is it beneficial to perform
a query unnesting or not?—in other words, shall we
follow a set-at-a-time rather than a node-at-a-time
processing approach. This is only one example where costing
information is needed even before query transformation.
We have learned from classic relational cost-based
optimization, that the search space—consisting of all
se5Project website: http://www.xtc-project.de
mantically equivalent QEPs—for a plan generator gets
tremendously large. If we consider cost-based
optimization of XML queries, the situation gets even worse due
to many different alternative evaluation methods for SJs
and HTJs as well as different index-based access
methods. To enable a query optimizer to keep as much as
possible promising QEPs in main-memory, we use a kind of
mesh data structure as proposed by Graefe and DeWitt
[
The XQGM access operators are providing input for
consuming operators. In general, we can distinguish
between two access methods: document scan and index
access. A document access operator—e. g., the left-most
access operator in Figure 6—is always mapped onto a
document scan, because it only accesses the document’s
root node. For all other access operators, an element
index scan—if present—is the access method of choice.
As outlined in Section 1, there exists a huge variety of
different SJ and HTJ algorithms. Using the rewrite rules
of Section 3, we can reduce the number of binary
structural join operators to a minimum. If there are still
binary structural joins, we use the decision tree shown in
Figure 12 to choose the evaluation method. If positional
predicates are missing, the join operator has three options
depending on the structural relationship it has to
evaluate: The StackTree algorithm by Al-Khalifa et al. [
Complex n-way join operators are created during query
rewrite by fusing two adjacent binary structural joins.
If there is no path or CAS index that can be used for
the evaluation of a complex n-way join, we use the
TwigStack algorithm proposed by Bruno et al. [
In Section 3.6 we showed how to prepare QGs to make the most of available indexes. During query transformation, we can benefit from join decomposition. Whenever a join operator—no matter whether binary or n-nary— and its subtree(s) can be evaluated using an available CAS or path index, we immediately map it to an index access operator. 4.4
During query transformation, we use a profile-based
approach for managing statistical information as proposed
by Mannino et al. [
On the other hand, IPs are associated with QG inner nodes and do not provide accurate statistical information. Instead, they use the statistical information provided by their child nodes (BPs or BIs) as input for cost estimation. This is not done automatically by the database management system. Instead, a database administrator has to run a statistics collection tool similar to DB2’s runstats manually to update the intermediate profiles. Using cost formulas which strongly depend on the assigned physical operator, they allow for an estimation of I/O and CPU costs. In this paper, we smoothed the way for cost-based XML query optimization. First, we introduced the XML Query Graph Model that serves as our internal representation for XML queries and permits an easier transition between QPs and QEPs. Second, we introduced a set of rewrite rules which allow to fuse as much as possible adjacent binary structural join operators to a single n-way join operator. Using these rules, a query optimizer can evaluate TQPs using HTJ or appropriate CAS or path indexes more easily. To make the most out of all existing indexes—especially those that can only answer parts of a TQP—we introduced further rules for join decomposition. Using these rules in combination with our knowledge on existing indexes allows for a separation of paths in TQPs, that can be answered using indexes, from those, that have to be evaluated using PPOs. Third, we sketched the architecture of our query optimizer that will be integrated in our prototype of a native XML database management system. Using the concepts described in this paper, we are already able to provide a heuristics-based query optimizer.
In the future, we will focus on the definition of an appropriate cost model. Choosing the right formulas for cost estimation is far from trivial. Compared to relational join algorithms—e. g., nested-loops join or merge join— SJ and HTJ algorithms are very complex in terms of how they process data. We expect that this leads to complex cost formulas whose quality can only be verified by extensive empirical experiments. Currently, we do not know which plan generation strategy, e. g., dynamic programming or simulated annealing, works best. For that reason, our plan generator will be flexible enough to switch between different strategies to allow for a comparison w. r. t. execution time, quality of the chosen plan and resource consumption.
We thank the anonymous reviewers for their valuable comments on this paper.