Recursive query gets slower when adding an index

Hi,

I have a self-referencing table that defines a hierarchy of projects and sub-projects.

This is the table definition:

CREATE TABLE project
(
project_id integer primary key,
project_name text,
pl_name text,
parent_id integer
);

ALTER TABLE project
ADD CONSTRAINT project_parent_id_fkey FOREIGN KEY (parent_id)
REFERENCES project (project_id)
ON UPDATE NO ACTION
ON DELETE NO ACTION;

The table contains ~11000 rows

The following statement:

with recursive project_tree as (
select project_id,
parent_id,
pl_name as root_pl,
pl_name as sub_pl,
1 as lvl
from project
where parent_id is null
union all
select c.project_id,
c.parent_id,
coalesce(p.root_pl, c.pl_name) as root_pl,
coalesce(c.pl_name, p.sub_pl) as sub_pl,
p.lvl + 1
from project c
join project_tree p on p.project_id = c.parent_id
)
select count(*), max(lvl)
from project_tree
where root_pl <> sub_pl;

usually runs in something like 60-80ms when the parent_id column is *not* indexed.

This is the execution plan without index: http://explain.depesz.com/s/ecCT

When I create an index on parent_id execution time increases to something between 110ms and 130ms

This is the execution plan with index: http://explain.depesz.com/s/xiL

As far as I can tell, the choice for the nested loop is the reason for the (slightly) slower execution.
I increased the statistics for the parent_id column to 10000 (and did an analyze of course) but that didn't change anything.

I have no problem with that performance, so this is more a "I'm curious on why this happens" type of question.
(And I thought you might be interested in this behaviour as well)

My environment:

*Windows 7 Professional 64bit
* PostgreSQL 9.2.1, compiled by Visual C++ build 1600, 64-bit

Regards
Thomas