Adapting plan-based re-optimization of multiway join queries for streaming data

Abstract

Exploiting a cost model to decide an optimal query execution plan has been widely accepted by the database community. When the plans for running queries are found to be sub-optimal, re-optimization techniques can be applied to generate new plans on the fly. Because plan-based re-optimization techniques can guarantee effectiveness and improve execution efficiency, they achieve success in traditional database systems. However in data-stream management, exploiting re-optimization to improve performance is more challenging, not only because the characteristics of streaming data change rapidly, but also because the re-optimization overheads cannot be easily ignored.

To alleviate these problems, we propose to bridge the gap between exploiting plan-based re-optimization techniques and reacting to the data-stream environments. We describe a new framework to re-optimize multiway join queries over data streams. The aim is to minimize the redundant re-optimization calls but still guarantee sub-optimal plans are detected.

In our scheme, the re-optimizer contains a three-phase re-optimization checking and two-path plan generating component. The three-phase checking component is performed periodically to decide whether re-optimization is needed. Because query optimizers heavily rely on information of cardinality and arrival rate to decide best plans, we evaluate them at checking duration. In the first phase, we quantify arrival rate changes to avoid redundant re-optimization. In the second phase, most recent cardinality values are considered to identify sub-optimality. Finally, in the third phase, we explicitly exploit useful cardinality information to detect local optimality. According to the decision made by the checking component, the plan generating component takes different actions for optimal and sub-optimal plans.

We explored the re-optimization performance over streaming data with different value distributions, arrival rates and window sizes, and we showed that re-optimization could offer significant performance improvement. The experimental results also showed that, traditional re-optimization techniques were able to provide significant performance improvement, if properly adapted to the real-time and constantly-varying environments.