Functional indexes with slow functions are misplanned

When the results of an expression can be obtained from a functional index,
the expression never needs to be evaluated. But the planner doesn't seem
to know that. It thinks the expression is evaluated not only once per row,
but multiple times, presumably at each step as it descends the btree.

So in the example given below the planner will choose to do a very
expensive hash or merge join that read the entire table and calls the slow
function on each row, rather than the much cheaper nested loop where the
function has been pre-evaluated and stored in the index and is simply
tested as part of an inner loop.

Cranking up the cost of the function does no good, because that just keeps
punishing the correct plan at least as much as the others.

I've tested this in 9.2 and HEAD.

This is a pretty silly test case, but it reproduces the real issue I've
seen.

create language plperl;

create table foo1 as select x::text from generate_series(1,1000) foo (x);

create table foo2 as select reverse(x) from foo1;

--use a fast version to set up the demo, as we are impatient

CREATE or replace FUNCTION slow_reverse(text) RETURNS text

LANGUAGE plperl IMMUTABLE STRICT COST 1000000

AS $_X$

return reverse($_[0]);

$_X$;

create index on foo2 (slow_reverse(reverse));

analyze foo2;

--put the slow version in place.

CREATE or replace FUNCTION slow_reverse(text) RETURNS text

LANGUAGE plperl IMMUTABLE STRICT COST 1000000

AS $_X$

my $foo; foreach (1..1e6) {$foo+=sqrt($_)};

return reverse($_[0]);

$_X$;

explain select * from foo1 where exists (select 1 from foo2 where
slow_reverse(reverse)=x);

--- strong-arm it into using the functional index.

set enable_hashjoin TO off;

set enable_mergejoin TO off;

explain select * from foo1 where exists (select 1 from foo2 where
slow_reverse(reverse)=x);

--- see, it actually is fast!

select * from foo1 where exists (select 1 from foo2 where
slow_reverse(reverse)=x);

Cheers,

Jeff