The declarativeness of relational query languages is very attractive for developing applications. However, many applications also need to invoke external functions or to access data that is not stored in the database. It is not hard to express references to such foreign functions in the query language. However, the issue of cost-based optimization of relational queries in the presence of such foreign functions has not previously been addressed satisfactorily. In this paper, we describe a comprehensive approach to this problem. Our key observation is that the optimization must take into account semantic information about foreign functions. Therefore, we provide a simple declarative rule language to express such semantics. We present algorithms necessary for applying the rules and for generating the space of equivalent queries. The equivalent queries provide the optimizer with an enriched execution space. We show how we can modify the traditional join reordering algorithm based on dynamic programming to obtain an optimal plan from the execution space. We provide necessary extensions to the cost model that are needed in the presence of foreign functions.
展开▼