返回Google圖書搜尋

Filter Joins: Cost-based Optimization for Magic Sets

University of Wisconsin--Madison. Computer Sciences DepartmentPraveen Seshadri

出版	University of Wisconsin-Madison, Computer Sciences Department, 1995
URL	http://books.google.com.hk/books?id=F-1dGwAACAAJ&hl=&source=gbs_api

註釋Abstract: "Complex decision-support queries often involve table expressions and views. The current state-of-the-art optimization technique for such queries is the magic sets rewriting. Unfortunately, this rewriting is typically applied as a heuristic query transformation, rather than as part of a cost-based query optimizer. There are some cases in which the rewriting can improve query execution time, and other cases in which it can degrade performance. Further, there are a large number of variants of magic sets rewriting that may be applied to a single query. The optimal choice of how and when to apply magic sets rewriting has remained an open research problem. In this paper we take a new approach, treating magic sets rewriting as a particular case of a new join algorithm that we call the Filter Join. Adding the Filter Join algorithm to a traditional cost-based query optimizer is difficult, because it can cause an unacceptable increase in the complexity of optimization. We demonstrate how this problem arises, and how it can be addressed by placing reasonable limits on the search space. Using the cost formulas that we derive, an optimizer can examine the Filter Join as a join algorithm option, without adversely affecting the complexity of optimization. This allows magic sets rewriting and similar techniques to be fully integrated with a cost-based query optimizer. The Filter Join allows the DBMS to find better evaluation algorithms for complex queries. It is also applicable to remote relations in distributed databases, and to relations defined by user functions. We treat all such relations uniformly as 'virtual' relations. Any join expression involving virtual relations benefits from the cost-based exploration of a Filter Join. This is especially important for heterogeneous queries involving remote views."