Relational databases provide the ability to store user-defined functions and predicates which can be invoked in SQL queries. When evaluation of a user-defined predicate is relatively expensive, the traditional method of evaluating predicates as early as possible is no longer a sound heuristic. There are two previous approaches for optimizing such queries. However, none of these approaches is able to guarantee the optimal plan over the desired execution space. We present efficient techniques that are able to guarantee the choice of an optimal plan over the desired execution space. The na{\"i}ve optimization algorithm is very general and therefore is most widely useful. The optimization algorithm with rank ordering improves upon the na{\"i}ve optimization algorithm by exploiting the nature of the cost formulas for join methods and is polynomial in the number of user-defined predicates. We also propose pruning rules that significantly reduce the cost of searching execution space for both the na{\"i}ve algorithm as well as the optimization algorithm with rank-ordering, without compromising the optimality. We also propose a conservative local heuristic that is even simpler but produces nearly optimal plans. We have implemented the algorithms by extending a System-R style optimizer. We present complexity analysis and experimental comparison of the algorithms.

}, author = {Surajit Chaudhuri and Kyuseok Shim}, institution = {Microsoft Research}, month = {February}, number = {MSR-TR-97-03}, pages = {39}, publisher = {Morgan Kaufmann Publishers}, title = {Optimization of Queries with User-defined Predicates}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=69557}, year = {1997}, }