=Paper=
{{Paper
|id=None
|storemode=property
|title=Query Processing and Optimization using Compiler Tools
|pdfUrl=https://ceur-ws.org/Vol-581/gvd2010_2_3.pdf
|volume=Vol-581
|dblpUrl=https://dblp.org/rec/conf/gvd/Sauer0H10
}}
==Query Processing and Optimization using Compiler Tools==
https://ceur-ws.org/Vol-581/gvd2010_2_3.pdf
Query Processing and Optimization using Compiler Tools
Caetano Sauer Karsten Schmidt Theo Härder
University of Kaiserslautern University of Kaiserslautern University of Kaiserslautern
Germany Germany Germany
csauer@cs.uni-kl.de kschmidt@cs.uni-kl.de haerder@cs.uni-kl.de
ABSTRACT in some specific way, which includes pattern matching, rule
We propose a rule-based approach for (X)Query compila- evaluation, and translation. To avoid writing huge amounts
tion that operates on a single query representation—called of sophisticated code by hand, effective language processing
abstract syntax tree (AST)—throughout the whole trans- tools called compiler generators (or compiler-compilers) are
lation and transformation process. For this purpose, we used. In this way, programmers are enabled to create power-
exploit some new features of the ANTLR compiler gener- ful and complex compilers using just a formal description of
ator such as tree pattern matching. This approach avoids the language: grammars. The goal of this paper is to intro-
error-prone transformations into different internal query rep- duce this compiler approach in all stages of query processing,
resentations and allows to specify grammar rules instead of thereby achieving complexity reduction, improved maintain-
writing code tailor-made for the specific DBMS. This ap- ability, and a formal specification through grammars, which
proach may further help to develop new query optimizer in turn provides safety.
rules, to prove correctness of rules, and to evaluate rule sets
in a declarative manner.
2. QUERY PROCESSING PIPELINE
1. INTRODUCTION The work in [4] describes all stages of XQuery[1] processing
in XTC, a native XML database system [3]. XTC follows
A query processor is part of a DBMS responsible for trans-
classical conventions of query processor design and will be
lating declarative statements written in a given query lan-
used in this work—without loss of generality and indepen-
guage into a sequence of physical operations to be executed
dent of the data model—as a base reference and an example.
by the lower levels of the system. This complex task in-
All nine stages illustrated in Figure 1 correspond to opera-
cludes parsing, modifying, and optimizing the initial repre-
tions over a distinct representation of a query, and the over-
sentation of the query. Typically, this task is divided into
all sequence of stages is here referred to as the pipeline of
smaller and more specific steps thereby introducing differ-
query processing. Three subtasks can be identified, namely
ent query representations facilitating the translation step at
translation, optimization, and execution, each embracing
hand. Reaching the final executable code for a given query,
one or more stages. For this reason, three different inter-
the query representation usually undergoes a metamorpho-
nal query representations are used: AST (abstract syntax
sis from a string, via a syntax tree, to multiple equivalent
tree), XQGM (XML query graph model, i.e., logical plan),
logical and physical plans.
and QEP (query execution plan, i.e., physical plan). Note
that the input XQuery string is considered as an external
Despite the different representations, which also introduce
representation.
new formalisms, data structures, and significant amounts of
source code, the overall task nevertheless is (from a more
The subtask translation parses XQuery statements and
abstract perspective) the translation of a declarative state-
produces ASTs, which contain the syntax elements of the
ment into executable code—and this problem is tackled by
query. Throughout the subsequent steps of normalization,
classical tools known to all computer scientists, namely com-
static typing, and simplification, this syntax is checked and
pilers.
reduced to a canonical AST, which is finally translated into
a logical plan described in XQGM, i.e., an XML extension
Technically speaking, all stages of query processing are per-
of the classical query graph model (QGM)[2]. The logical
forming essentially the same processing steps, that is, repre-
plan serves as input to the optimizer, which reorganizes
senting the query as a tree of operations and manipulating it
or replaces the algebraic operations. Besides reducing the
number of operations and the intermediate result size, it also
identifies join options and generates alternatives for logically
equivalent XQGMs. The logical plan identified as optimal
(i.e., cheapest) one is then converted into a physical plan,
i.e., algebraic operations are replaced by physical operations
on data storage objects. This physical plan, referred to as
QEP, is processed by the query engine and delivers a se-
GvD Workshop’10, 25.-28.05.2010, Bad Helmstedt, Germany
Copyright is held by the author/owner(s). quence of XML nodes. Eventually, these nodes are materi-
alized to a given result format, such as string or XML nodes.
XQuery unit of a language, such as a variable name or keywords like
for, where, and return. Every token is associated to an
Parser optional string, which carries the exact sequence of char-
acters that were matched in the input query. To illustrate
Abstract Syntax Tree (AST) the structure and the creation of the first AST, we use the
sample query in Figure 2a. For this query, the parsing stage
Normalization Translator builds the AST shown in Figure 2b. Tokens are described
Static Typing by their type (always starting with an upper case charac-
ter), e.g. FunctionCall, and the applicable text, which
Simplification serves here as a payload and is described between brackets.
QGM Translation In the function call token, for example, the text payload
is [“count“]. The relationship between tokens is expressed
XML Query Graph Model (XQGM) by the tree hierarchy. The argument of the function count,
for instance, is a variable reference represented as a child of
FunctionCall.
Algebraic Rewriting
Optimizer
Plan Generation 3.2 Creating AST Structures from Grammars
The core engine of a query processor based on ASTs and
Query Execution Plan (QEP) grammars is a compiler generator. The input string is tok-
enized and processed by a compiler. This compiler produc-
Execution ing the AST was generated for a specific language described
Executor
Materialization by a given grammar. Such a grammar consists of a set of
rules used to describe the elements of the language. An
Result XQuery parser, for example, would make use of four rules
to match the input of Figure 2a. At the topmost level, the
Figure 1: Query processing pipeline used in XTC query contains a FLOWR expression consisting of an assign-
ment of a variable to a path expression and a function call
with a variable reference as the return expression. These
Although working at different levels of abstraction and ma- rules are described by Figure 2c, using the syntax of the
nipulating different representations of a query, all stages of ANTLR compiler generator1 .
the pipeline perform essentially similar tasks, such as scan-
ning trees (note, plans are realized as trees), identifying pat- In addition to parsing the input, the generated compiler
terns, and performing rewrites. In the following section, must also execute actions embedded in the rules. One ex-
we present a query processing approach that performs these ample is the maintenance of variable references in a sym-
general tasks based on a high-level descriptive language on bol table when a variable assignment is parsed. This ac-
a single internal representation, which is used in all stages tion appears between curly braces, like the pseudo-function
of the pipeline. insertV ariableRef erence() in the rule flowrExpr of Fig-
ure 2c. Later on, when a variable is referenced, the compiler
looks up its value in the symbol table and replaces the ref-
3. ASTS AND GRAMMARS erence by its value.
Most of the complexity behind the implementation or main-
tenance of a query processor results from the use of different
A special kind of actions are the so-called rewrite rules,
levels of abstraction, which are expressed by the three dif-
which appear after the -> symbol in the grammar. They
ferent internal representations in Figure 1. Implementing
specify how the input matched is translated to an AST,
extensions of the query language, adding new functionali-
as occurring in the rule functionCall. Here, the tokens
ties, or even maintaining the code due to API modifications
matched are mapped to a tree where the root node is the
become cumbersome tasks for the programmer, particularly
FunctionCall token and the arguments of the function are
in research prototypes, where changes frequently happen.
the children. The syntax used for rewrite rules is, for ex-
ample, ^(a b c), where a is the root node and b and c are
3.1 Representing Queries and Plans as ASTs its children. Note, the difference between the token and the
A first step towards complexity reduction can certainly be rule having apparently the same name. The token is a real
achieved by replacing the three internal data structures (AST, object living in memory and starting with an upper-case let-
XQGM and QEP) with only the AST. The reason for choos- ter. Rules, on the other hand, serve as logical units of the
ing a plain syntax tree for a unified query representation compiler execution, like methods in a Java class, and are
comes from the fact that such trees are the basic unit of work written using a lower-case letter in the first position. Figure
in language compilers. This chapter demonstrates tech- 2b shows the resulting AST when parsing the sample query.
niques to execute all stages of the pipeline with ASTs while
maintaining the semantics of the query language. Note that 3.3 AST Manipulation
the logical abstraction of the query pipeline model is re- After the generated parser has processed the input query,
tained, while only the implementation technique is unified. the first AST instance is constructed using the rules given
above. Several ASTs are generated and parsed in different
An AST is a labeled, ordered tree structure, where each node
1
is a token. By definition, a token is the minimal syntactic http://www.antlr.org/
(a) (a)
1 for $b in doc("dblp.xml")//article
2 return count($b) A
(b)
B E
FlowrExpr
ForClause ReturnClause C D
PathExpr
VariableName[”b”] (omitted)
FunctionCall[“count“] (b)
VariableReference[”b”]
A DOWN B DOWN C D UP E UP
(c) Figure 3: (a) A sample AST and (b) the serialized
list of tokens
1 expr:
2 flowrExpr | functionCall | varRef ;
processing, however, is to apply rewrite rules under distinct
3 flowrExpr:
conditions, which are independent of the AST structure. As
4 "for" $ qname "in" expr
an example, the compiler may rewrite a node access to an
5 { insertVariableReference(); }
index scan when generating a QEP, given the condition that
6 "return" expr
an index for that access exists. Such conditions can be in-
7 -> ^(FlowrExpr
corporated into the grammar using semantic predicates, as
8 ^(ForClause VariableName[qname] expr)
will be shown later.
9 ^(ReturnClause expr)
10 );
Sometimes, it is cumbersome to write full grammars in or-
11 functionCall:
der to perform simple AST manipulation tasks, because only
12 qname "(" expr ("," expr)* ")"
a particular subset of the rules is relevant. Since a parser
13 -> ^(FunctionCall[qname] expr+);
always recognizes all valid expressions of a language, all nec-
14 qname:
essary rules must be specified when generating it. To over-
15 ("a".."z")+ ;
come this problem, ANTLR implements the concept of a
Tree Pattern Matcher. These are special kinds of parsers
Figure 2: (a) A sample XQuery expression, (b) the that recognize any token sequence and trigger embedded ac-
AST generated for it, and (c) the grammar rules to tions when a certain pattern contained in the grammar rules
transform the query into an AST is found. Making use of this feature, a grammar, having only
the patterns that require rewrite, is sufficient to generate a
tree scanner that performs the desired manipulation.
stages throughout the pipeline. ANTLR provides powerful 3.4 Applying ASTs in the Pipeline
extensions to the grammar rules, enabling AST-based query Table 1 sketches four examples for the application of gram-
processing and optimization. For instance, the insertion of mar rules on ASTs. Each rule and the related ASTs are
actions in arbitrary places of a rule (syntax: {}) and the reduced to the bare minimum required for showing the AST
specification of rewrite rules (syntax: ->). In the follow- rewrite effects.
ing, additional extensions will be described, and Section 3.4
shows how to apply these techniques in a grammar-based
query processor. 1. Normalization for a FLOWR expression is applied
to replace multiple for clauses by nesting single fors.
Parsing an AST is obviously an essential functionality for Here, the rule’s forClause and returnClause were
further manipulations. Therefore, the AST is serialized into omitted for simplicity.
a sequence of tokens. The serialization method implemented 2. Index Matching for a Path Step generates alterna-
by ANTLR adds two special tokens to signalize descending tive plans, when suitable indexes are available. The ex-
and ascending movements—DOWN and UP—and scans ample addresses child nodes of the context item named
the tree in pre-order. Figure 3a illustrates a sample tree ’author’. After the transformation, this logical data ac-
and 3b its serialized token sequence. Note that the serial- cess is represented by a physical operator, either a doc-
ization is equivalent to the tree syntax in grammar rules, ument index scan (ElementDocumentScan) or an
but using the UP/DOWN tokens instead of parenthesis: element index scan (ElementIndexScan)—physical
^(A ^(B C D) E) operators available in our XDBMS. This rule is using
a semantic predicate—isIndexAvailable().
Because tree parsing allows to manipulate an AST by re-
organizing or replacing entire subtrees, we also use it for 3. Join Reordering rules help to generate alternative
the application of rewriting rules. A crucial task in query plans having different join orders. Thus, cost-based
plan evaluation may aim for the cheapest join order impact of enabling or disabling certain rules and, thereby,
when applying cost estimations to all the alternatives. disabling dependent rules automatically. Furthermore, clas-
In the example, the nested for clauses of expression 1 sical problems will reappear such as cycle detection and pre-
and 2 are swapped because their context is indepen- vention, search space pruning, and various search strategies
dent (the semantic predicate (condition) isForClau- (e.g., bottom-up, top-down, etc.).
seIndependent() has to be checked first).
Eventually an AST-represented plan needs to be translated
4. Predicate Pushdown moves the whereClause of a into a QEP that is often tailored to a specific (X)DBMS.
FLOWR expression into a nested FLOWR expression. Here again, rule-based translation allows to easily translate
However, again a check isWhereIndependent() is AST expressions into DMBS-dependent operators or code
required to verify that the where predicate can be ea- (see Table 1: example 2). In a perfect solution, it is suf-
gerly used as a filter. Normally a nested FLOWR ex- ficient to specify the set of available DBMS operators to
pression is correlated to the outer one and, thus, a non- automatically select the set of rules that produce a tailored
blocking whereClause (e.g., blocking clauses contain QEP. Thus, a generic query optimization may be used for
a grouping or ordering expression) is usually specified different DBMSs without losing expressiveness while reduc-
for the correlated input visible for the nested one. ing the efforts of optimizer development to a single instance.
4. OPPORTUNITIES AND CHALLENGES Because XQuery is a Turing-complete language, its not pos-
Integrating the AST-only query manipulation approach into sible to cover all language aspects within the AST grammar
the XTC system became possible due to the extension of tree rules. For this reason, we want to explore the limitations
pattern matching in ANTLR. However, the existing query and opportunities for a smooth integration.
compilation process, sketched in Section 2, is not only com-
plex but also well-studied, optimized, and supported by a Once the essential parts of the query processing pipeline
huge amount of test cases. To replace the entire compila- are specified based on the AST concept, we can start with
tion process, a step-by-step approach seems to be feasible. other aspects of optimization. For instance, the nice way
As a consequence, the new AST-only version may start with of specifying query rewrite rules may help to easily identify
a rudimentary set of rules that can be manually handled. In opportunities for (intra) query parallelization.
this way, the correctness of the rule’s impact can be proved
and a suboptimal QEP can be built and executed. In the 5. SUMMARY & OUTLOOK
next steps, existing optimization rules (i.e., Java code work- Based on the current state of XTC query processing—the
ing on the QGM) can be transformed into declarative rules classical approach sketched in Section 2—, we presented our
for the AST. Eventually, we hope to obtain at least the same first experience using only language tools. This lightweight
set of powerful rewrite rules and integrate them into our new description style of query translation and transformation
query processing approach. A major challenge is to express seems to provide equal expressiveness as hand-written pro-
the flexibility of rules written in Java with the concepts and gram code. However, up to now, neither all limitations are
features of a language tool while retaining the same seman- identified nor all opportunities disclosed.
tics.
We hope to reduce the complexity of writing query compil-
The AST representation entails certain limitations to the se- ers and query optimizers while not affecting the quality of
mantic rewriting power, when only tree syntax is exploited optimization. Furthermore, we focus on proving rule cor-
within the rules. For instance, nested bindings and depen- rectness, finding optimal rule sets, and identifying DBMS-
dencies cannot always be decoupled, although decoupled independent approaches.
processing may be semantically correct. For instance, for
the join reorder example of Section 3.4 which depends on The next steps will deal with XQuery language aspects and
the evaluation of the forClauseIndependent() condition, physical operator mapping capabilities in XTC, before we
a semantically reordering may also be possible in case of an want to compare the performance (i.e., overhead) of tailored
existing dependency by simply exchanging axis relationships program code with our new AST rule-based approach.
(e.g., from child axis to parent axis). However, XQuery se-
mantics for empty sequences has to be observed2 . Although
all necessary conditions are represented within the AST, it
6. REFERENCES
[1] D. Chamberlin et al., XQuery 1.1: An XML Query
seems to be extremely challenging to describe generic rules Language. W3C Working Draft, (2008).
covering all the (hidden) corner cases. [2] L. M. Haas, J. C. Freytag, G. M. Lohman, and H. Pirahesh,
Extensible query processing in starburst, SIGMOD Rec. 18
Another aspect of rule-based optimization is to control the (1989), no. 2, 377–388.
set of applicable and meaningful rules. Because not all rules [3] Michael P. Haustein and Theo Härder, An Efficient
Infrastructure for Native Transactional XML Processing,
do always improve a given query but only increase the op- DATAK 61 (2007), no. 3, 500–523.
timization budget, the selection and usage of rules may be- [4] Christian Mathis, Storing, Indexing, and Querying XML
come an important aspect. Moreover, we hope to exploit Documents in Native Database Management Systems, Ph.D.
the easy way of expressing (new) rules to figure out which thesis, University of Kaiserslautern, München, 7 2009.
rules maybe applied independently and which not. However,
not only the “fastest” rule chain is interesting but also the
2
When child nodes do not contribute to the evaluation, an
empty sequence is required.
Rule AST before AST after
duplicatedForClause:
^(Flowr
forClause
forClause
returnClause Flowr
)
-> ^(Flowr
^(For
Flowr For Return
forClause{1}
)
^(Return
^(Flowr For For Return expr 1 Flowr
^(For
forClause{2}
) expr 1 expr 2 expr 3 For Return
^(Return
returnClause
)
) expr 2 expr 3
)
)
;
elementAccess:
^(Step
contextItem
Axis ElementDocumentScan
nodeTest (’child’,’author’)
)
-> { isIndexAvailable }? PathStep
^(ElementIndexScan[ correlated
Axis, Input
nodeTest correlated
] Input Axis NodeTest
contextItem
) ElementIndexScan
-> ^(ElementDocumentScan[ NameTest (’child’,’author’)
’child’
Axis, ’author’
nodeTest correlated
] Input
contextItem
)
;
joinReorder:
^(Flowr
forClause // 1 Flowr Flowr
^(ReturnClause
^(Flowr
forClause // 2
For Return For Return
)
)
)
-> { isForClauseIndependent }? expr 1 Flowr expr 2 Flowr
^(Flowr
forClause{2}
^(ReturnClause For Return For Return
^(Flowr Swap
forClause{1}
)
) expr 2 expr 3 expr 1 expr 3
);
predicatePushDown:
^(Flowr
forClause
whereClause
^(ReturnClause Flowr Flowr
^(Flowr
forClause
returnClause
For Where Return For Return
)
)
)
-> { isWhereIndependent }? expr 1 expr 2 Flowr expr 1 Flowr
^(Flowr
forClause
^(ReturnClause For Return For Where Return
^(Flowr
forClause
whereClause
returnClause expr 3 expr 4 expr 3 expr 2 expr 4
)
)
);
Table 1: Examples of AST manipulation for XQuery processing