 |
|
|
Changing the Rules: Transformations for Rule-Based Optimizers |
Rule-based optimizers are extensible because they consist of modifiable sets of rules. For modification to be straightforward, rules must be easily reasoned about (i.e., understood and verified). At the same time, rules must be expressive and efficient (to fire) for rule-based optimizers to be practical. Production-style rules (as in [15]) are expressed with code and are hard to reason about. Pure rewrite rules (as in [1]) lack code, but cannot atomically express complex transformations (e.g., normalizations). Some systems allow rules to be grouped, but sacrifice efficiency by providing limited control over their firing. Therefore, none of these approaches succeeds in making rules expressive, efficient and understandable.
We propose a language (COKO) for expressing an alternative form of input to a rule-based optimizer. A COKO transformation consists of a set of declarative (KOLA) rewrite rules and a (firing) algorithm that specifies their firing. It is straightforward to reason about COKO transformations because all query modification is expressed with declarative rewrite rules. Firing is specified algorithmically with an expressive language that provides direct control over how query representations are traversed, and under what conditions rules are fired. Therefore, COKO achieves a delicate balance of understandability, efficiency and expressivity. |
References, where available, link to the DBLP on the World Wide Web.
[1]Ludger Becker, Ralf Hartmut Güting:
Rule-Based Optimization and Query Processing in an Extensible Geometric Database System.
TODS 17(2): 247-303(1992)[2]...
[3]...
[4]...
[5]Mitch Cherniack, Stanley B. Zdonik:
Rule Languages and Internal Algebras for Rule-Based Optimizers.
SIGMOD Conf. 1996: 401-412[6]Béatrice Finance, Georges Gardarin:
A Rule-Based Query Rewriter in an Extensible DBMS.
ICDE 1991: 248-256[7]Béatrice Finance, Georges Gardarin:
A Rule-Based Query Optimizer with Multiple Search Strategies.
DKE 13(1): 1-29(1994)[8]Goetz Graefe:
The Cascades Framework for Query Optimization.
Data Engineering Bulletin 18(3): 19-29(1995)[9]Goetz Graefe, William J. McKenna:
The Volcano Optimizer Generator: Extensibility and Efficient Search.
ICDE 1993: 209-218[10]...
[11]Won Kim:
On Optimizing an SQL-like Nested Query.
TODS 7(3): 443-469(1982)[12]...
[13]Gail Mitchell, Umeshwar Dayal, Stanley B. Zdonik:
Control of an Extensible Query Optimizer: A Planning-Based Approach.
VLDB 1993: 517-528[14]Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan:
Magic is Relevant.
SIGMOD Conference 1990: 247-258[15]Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan:
Extensible/Rule Based Query Rewrite Optimization in Starburst.
SIGMOD Conference 1992: 39-48[16]...
[17]Edward Sciore, John Sieg Jr.:
A Modular Query Optimizer Generator.
ICDE 1990: 146-153[18]Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan:
Cost-Based Optimization for Magic: Algebra and Implementation.
SIGMOD Conf. 1996: 435-446
Referenced By:
- Mitch Cherniack, Stanley B. Zdonik:
Inferring Function Semantics to Optimize Queries.
VLDB 1998: 239-250
- Leonidas Fegaras:
Query Unnesting in Object-Oriented Databases.
SIGMOD Conference 1998: 49-60
|
@inproceedings{DBLP:conf/sigmod/CherniackZ98,
author = {Mitch Cherniack and
Stanley B. Zdonik},
editor = {Laura M. Haas and
Ashutosh Tiwary},
title = {Changing the Rules: Transformations for Rule-Based Optimizers},
booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-955-5},
pages = {61-72},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
