1. A method for optimization of a query invoking relational database tables and foreign functions, said method comprising: (a) providing rewrite rules for the foreign functions; (b) receiving an input query to be executed; (c) generating alternative queries from the input query and the rewrite rules by determining if a left-side of at least one of the rewrite rules is equivalent to at least a portion of the query using substitution mapping; (d) generating an optimal plan for each said alternative query; and (e) selecting for execution a lowest cost plan among said optimal plans.