Function execution costs 'n all that

So I've been working on the scheme I suggested a few days ago of
representing "equivalence classes" of variables explicitly, and avoiding
the current ad-hocery of generating and then removing redundant clauses
in favor of generating only the ones we want in the first place.  Any
clause that looks like an equijoin gets sent to the EquivalenceClass
machinery by distribute_qual_to_rels, and not put into the
restrictlist/joinlist data structure at all.  Then we make passes over
the EquivalenceClass lists at appropriate times to generate the clauses
we want.  This is turning over well enough now to pass the regression
tests, but I noticed that one query in opr_sanity got a whole lot slower
than before.  The query is

SELECT p1.opcname, p1.opcfamily
FROM pg_opclass AS p1
WHERE NOT EXISTS(SELECT 1 FROM pg_amop AS p2                WHERE p2.amopfamily = p1.opcfamily                  AND
binary_coercible(p1.opcintype,p2.amoplefttype));
 

and investigation showed that the plan changed from (8.2 and before)
Seq Scan on pg_opclass p1  (cost=0.00..393.94 rows=51 width=68)  Filter: (NOT (subplan))  SubPlan    ->  Seq Scan on
pg_amopp2  (cost=0.00..7.66 rows=2 width=0)          Filter: ((amopfamily = $0) AND binary_coercible($1,
amoplefttype))

to
Seq Scan on pg_opclass p1  (cost=0.00..393.94 rows=51 width=68)  Filter: (NOT (subplan))  SubPlan    ->  Seq Scan on
pg_amopp2  (cost=0.00..7.66 rows=2 width=0)          Filter: (binary_coercible($1, amoplefttype) AND (amopfamily =
$0))

thus resulting in many more calls of binary_coercible() which is a
pretty expensive function.  This is not too surprising: the clause
p2.amopfamily = p1.opcfamily got diverted through the EquivalenceClass
code for just long enough to end up behind the other one in the table's
restrictlist :-(

In short, this approach results in a whole lot less stability in the
order in which WHERE clauses are evaluated.  That might be a killer
objection to the whole thing, but on the other hand we've never made
any strong promises about WHERE evaluation order.

Instead, I'm thinking it might be time to re-introduce some notion of
function execution cost into the system, and make use of that info to
sort WHERE clauses into a reasonable execution order.  This example
would be fixed with even a very stupid rule-of-thumb about SQL functions
being more expensive than C functions, but if we're going to go to the
trouble it seems like it'd be a good idea to provide a way to label
user-defined functions with execution costs.

Would a simple constant value be workable, or do we need some more
complex model (and if so what)?

Comments?
        regards, tom lane