Weird plan variation with recursive CTEs - Mailing list pgsql-performance

Here's a strange thing.

Postgres 9.1.0 on a severely underpowered test machine

effective_cache_size = 128M
work_mem = 48M


This query:

WITH
RECURSIVE subordinates AS (
    SELECT id, originator_id FROM partner_deliveries WHERE originator_id
in (225645)
    UNION ALL
    SELECT partner_deliveries.id, subordinates.originator_id
        FROM partner_deliveries, subordinates
        WHERE partner_deliveries.originator_id = subordinates.id
),
distinct_subordinates AS ( SELECT id, originator_id FROM (
    SELECT DISTINCT id, originator_id FROM subordinates
    UNION DISTINCT
    SELECT id, id FROM partner_deliveries WHERE id in (225645)
) itab ORDER BY id )
SELECT
    s.originator_id,
    sum(o.opens) as opens,
    sum(o.clicks) as clicks,
    sum(o.questionnaire) as questionnaire,
    sum(o.completes) as completes,
    sum(o.quotafulls) as quotafulls,
    sum(o.screenouts) as screenouts
FROM overview o
JOIN distinct_subordinates s ON s.id = o.partner_delivery_id
GROUP BY s.originator_id;

Works perfectly: http://explain.depesz.com/s/j9Q

The plan produces an index scan on overview (roughly 1.5M tuples),
which is desired.

Now, I tried to skip one hashagg to "speed it up a bit", and found
something really unexpected:

http://explain.depesz.com/s/X1c

for

WITH
RECURSIVE subordinates AS (
    SELECT id, originator_id FROM partner_deliveries WHERE originator_id
in (225645)
    UNION ALL
    SELECT partner_deliveries.id, subordinates.originator_id
        FROM partner_deliveries, subordinates
        WHERE partner_deliveries.originator_id = subordinates.id
),
distinct_subordinates AS ( SELECT id, originator_id FROM (
    SELECT id, originator_id FROM subordinates
    UNION DISTINCT
    SELECT id, id FROM partner_deliveries WHERE id in (225645)
) itab ORDER BY id )
SELECT
    s.originator_id,
    sum(o.opens) as opens,
    sum(o.clicks) as clicks,
    sum(o.questionnaire) as questionnaire,
    sum(o.completes) as completes,
    sum(o.quotafulls) as quotafulls,
    sum(o.screenouts) as screenouts
FROM overview o
JOIN distinct_subordinates s ON s.id = o.partner_delivery_id
GROUP BY s.originator_id;

If you don't notice, the only difference is I removed the distinct
from the select against the recursive CTE for distinct_subordinates,
expecting the union distinct to take care. It did. But it took a whole
2 seconds longer! (WTF)

Fun thing is, nothing in the CTE's execution really changed. The only
change, is that now a sequential scan of overview was chosen instead
of the index.
Why could this be? The output (number of search values, even the
values themselves and their order) is the same between both plans.