Thanks for the suggestion.
I've tried it with seqscan set to off, but there's still a bitmap heap scan going on:
http://explain.depesz.com/s/zIJl
I have random_page_cost set to 1.5 at the moment, as the database is on a solid state disk.
Every user has a parent, but not every parent has a child.
The number of rows returned by the query is 17 at the moment.
It would be even less for a child tree of other users, usually 0 to 3, and the plan remains the same in those cases.
The table itself has only slightly below 5000 rows right now. It's not a lot, but it seems too many to go for a table scan for just 17 rows.
Could it be that the planner cannot estimate the possible match count because of the CTE?
Can you do "explain (analyze, buffers)"? I'm wondering if your entire table is in a very small number of pages, possibly all on just one page, in which case a table scan makes sense. The plan with seqscan off has just a tiny bit higher estimated cost, and it ran 1.5ms slower - that difference could be noise, but I'm thinking that all it's doing is an extra index page read without eliminating any table data page reads (under the assumption that the table is all in a single page).