Enabling Incremental Query Re-Optimization.

Area of Science:

• Computer Science
• Database Systems
• Query Optimization

Background:

• Declarative query processing is expanding to diverse platforms like the Web, data streams, and cloud computing.
• Runtime performance changes necessitate adaptive query execution re-planning.
• Existing adaptive techniques require advancements in cost estimation and plan search algorithms.

Purpose of the Study:

• To develop a cost-based optimizer capable of incrementally recomputing optimal query plans.
• To investigate novel algorithms for adaptive query optimization in dynamic environments.
• To demonstrate the benefits of incremental optimization, particularly for stream processing workloads.

Main Methods:

• Formulating query plan enumeration as recursive datalog queries.
• Developing novel optimization approaches for effective pruning in static and incremental scenarios.
• Applying lessons from declarative implementations to traditional optimizer implementations.

Main Results:

• An implementation demonstrating incremental query plan re-optimization based on new cost information.
• Effective pruning strategies for both static and incremental query plan enumeration.
• Validation of the approach's benefits, especially for stream processing workloads.

Conclusions:

• Incremental query optimization is crucial for adapting to unanticipated performance changes in modern data systems.
• The proposed datalog-based approach provides a foundation for novel adaptive optimization algorithms.
• The principles of declarative adaptive optimization are transferable to traditional query optimizers.