The
Query Compiler
Compilation
of Queries: - Compilation means turning a query into a
physical query plan, which can be implemented by query engine.
The query- compiler package is
a set of tools for the inspection of the process of query compilation. It shows
how a SQL query is parsed, desugared, translated in relational algebra and
optimized. The user interface is web-based, implemented using strategy-net and xml-tools. Of course the components of the query-compiler are also
available as command-line utile.
The query-compiler is based
on the sql-front and relational-algebra packages. sql-front is used to
parse a SQL query to an abstract syntax for SQL. The relational-algebra
packages implement the optimization of relational algebra and the rendering of
relational algebra expressions in MathML?.
Steps of query compilation:
— Parsing
— Semantic
checking
— Selection
of the preferred logical query plan
— Generating
the best physical plan
The
Parser:
— It
is the first step in query processing.
— Parsing
turns query into parse tree.
— It generates a parse tree.
— It generates a parse tree.
ü
Subject
of Compilation
- Nodes in the parse
tree corresponds to the SQL constructs.
- It is similar to the compiler of a programming language.
Preprocessor:
•
Responsible for semantic checking
–
Check relation uses
–
Check and resolve attribute uses
–
Check types
•
If the parse tree satisfies all the above
tests, it is valid
•
Otherwise, processing stops.
View
Expansion:
- A very critical part of query compilation.
- A very critical part of query compilation.
- Expands the view references in the query tree to the actual view.
- Provides opportunities for the query optimization.
Semantic
Checking:
- Checks
the semantics of a SQL query.
— Examines
a parse tree
Checks:
Checks:
ü
Attributes
ü
Relation
names
ü
Types
- · Resolves attribute references.
Conversion
to a logical query plan:
- Converts
a semantically parsed tree to a algebraic expression.
- Conversion
is straightforward but subqueries need to be optimized.
—Two argument selection approach can be used.
—Two argument selection approach can be used.
Cost
based optimizing:
- Best physical query plan represents the least costly plan.
- Factors that decide the cost of a query plan:
- Best physical query plan represents the least costly plan.
- Factors that decide the cost of a query plan:
ü
Order
and grouping operations like joins, unions and intersections.
ü
Nested
loop and the hash loop joins used.
ü
Scanning
and sorting operations.
ü
Storing
intermediate results.
ü
The
query cost is defined by the time to answer a query.
ü
Different
factors are contributed to query cost like disk access time, CPU time or
network communication time.
Logical and physical query plans: -
· Both are trees representing query evaluation
· Leaves represent data
· Internal nodes are operators over the data
· Logical plan is higher-level and
algebraic
· Physical plan is lower-level and operational
· Logical plan operators correspond to query language
constructs
- · Physical plan operators correspond to implemented access methods
Logical
plan operators: -
- · Extended relational algebra
- · Leaves of logical plans are table names
- · Basic operators: Select, Project, Cross-Product, Union, Difference
- · Abbreviations: Natural-Join, Theta-Join, Intersect
No comments:
Post a Comment