The query optimizer of XTC is accompanied by a visual explain tool that allows for a configuration of the query optimizer. Because our query optimizer is completely rule-based, every rewrite rule that can be applied by the plan generator, can be switched on and off—even during runtime. Furthermore, different search strategies (e.g., Dynamic Programming or Simulated Annealing) can be employed. To immediately see the impact of a larger or smaller search space (by activating or deactivating rewrite rules) and the optimization result gained using a specific search strategy, we provide a powerful visual explain tool (shown in the Illustration below).

This tool allows to track the complete optimization process from the beginning to its very end. You can see all logical query rewrites performed during the XQuery-to-Algebra mapping phase as well as the final Query Execution Plan (QEP) gained by cost-based optimization. After execution, the QEP is additionally annotated with runtime information, e.g., the total number of tuples consumed by each operator as well as the estimated and actual selectivity of predicates.

Let's have a look how query optimization works for XMark query Q8:

let $auction := doc("auction.xml") return
for $p in $auction/site/people/person
let $a :=
for $t in $auction/site/closed_auctions/closed_auction
where $t/buyer/@person = $p/@id
return $t
return <item person="{$p/name/text()}">{count($a)}</item>

On the right-hand side, you can see the corresponding XQGM instance (by clicking on the image, you can get a full-screen view).
All XQGM operators are connected to tuple variables that have an FOR (F) or LET (L) quantification. The solid lines connecting QGM operators describe the data flow. The dotted line associated with the top-most operator's LET-quantified tuple variable describes a context-dependent evaluation of the left subtree. Each path step is evaluated using a logical Structural Join operator using the structural relationshop (e.g., child or descendant) as predicate.All Structural Join operators consume tuple streams provided by the various access operators.

After cost-based query optimization, we get a Query Execution Plan (QEP), which is shown below. Almost all structural relationships are now evaluated using path indexes serving as a kind of materialzed views on specific paths in the document. The remaining path steps are evaluated using physical Structural Joins (we actually implemented the famous StackTree operator). Due to the DeweyID node labeling scheme, our physical Structural Join operator can evaluate all XPath axes, instead of only child and descendant.

Here, the optimizer has chosen to use element index accesses to get all "buyer" and "name" element nodes instead of costly scanning the complete document. By using the content index for getting all content-node values,  expensive accesses to the document are not necessary anymore.