Loading...
Please wait, while we are loading the content...
Similar Documents
Robust heuristics for scalable optimization of complex sql queries.
| Content Provider | CiteSeerX |
|---|---|
| Author | Chandra, Gopal Jayant, Das Haritsa, R. |
| Abstract | Modern database systems typically use a dynamic-programming-based search strategy to identify optimal ex-ecution plans for SQL queries. However, due to its ex-haustive nature, resulting in exponential time and space overheads, this approach does not easily scale to complex queries with a large number of base relations, such as those found in current decision-support and enterprise manage-ment applications. To address this problem, a variety of heuristics to prune the search space to a manageable size have been proposed in the literature. However, as we will empirically demonstrate in this paper, even the best heuris-tics currently available can often result in either extremely poor choices of execution plans, or an inability to suf£-ciently control the overheads. Accordingly, we revisit the search-space issue in dy-namic programming here, and present a new pruning strat-egy. The strategy is based on (a) selectively applying prun-ing to only local segments of the join graph that are ex-pected to be dif£cult to optimize, and not to the entire join graph; and (b) adopting a skyline-based pruning heuristic on a feature vector that incorporates sub-plan costs, cardi-nalities and selectivities. Through a detailed study, running to millions of complex queries on rich relational schemas implemented on an industrial-strength database system, the new strategy is shown to always ef£ciently produce high-quality plans, oftentimes the optimal itself – that is, it is robust unlike its predecessors. Further, this improvement is achieved with comparable or reduced optimization over-heads. Finally, the strategy is easily amenable to implemen-tation in current database systems. 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Complex Sql Query Scalable Optimization Robust Heuristic Complex Query Modern Database System Search-space Issue Large Number Search Space Join Graph Optimal Ex-ecution Plan Sql Query Ex-haustive Nature Dynamic-programming-based Search Strategy Space Overhead Current Database System Dif Cult Manageable Size Base Relation Skyline-based Pruning Heuristic Rich Relational Schema New Strategy Manage-ment Application Sub-plan Cost Detailed Study Exponential Time Execution Plan Poor Choice Current Decision-support High-quality Plan Industrial-strength Database System Reduced Optimization Over-heads Dy-namic Programming Entire Join Graph Feature Vector Local Segment |
| Content Type | Text |
