Parameter for planner estimate of recursive queries

I've been investigating the poor performance of a WITH RECURSIVE
query, which I've recreated with test data.

The first thing was to re-write the query, which helped improve
performance by about 30%, but the plan was still very bad. With a
small patch I've been able to improve performance by about x100.

The poor performance is traced to the planner cost estimates for
recursive queries. Specifically, the cost of the recursive arm of the
query is evaluated based upon both of these hardcoded assumptions:

1. The recursion will last for 10 loops
2. The average size of the worktable will be 10x the size of the
initial query (non-recursive term).

Taken together these assumptions lead to a very poor estimate of the
worktable activity (in this case), which leads to the plan changing as
a result.

The factor 10 is a reasonably safe assumption and helps avoid worst
case behavior in bigger graph queries. However, the factor 10 is way
too large for many types of graph query, such as where the path
through the data is tight, and/or the query is written to prune bushy
graphs, e.g. shortest path queries. The factor 10 should not be
hardcoded in the planner, but should be settable, just as
cursor_tuple_fraction is.

I've written a short patch to make the estimate of the avg size of the
worktable configurable:

recursive_worktable_estimate = N (default 10)

Using this parameter with the test query results in a consistently
repeatable ~100x gain in performance, using
recursive_worktable_estimate = 1 for a shortest path query:

Unpatched: 1775ms
Patched: 17.2ms

This is because the estimated size of the worktable is closer to the
truth and so leads naturally to a more sensible plan. EXPLAINs
attached - please look at the estimated rows for the WorkTable Scan.

There are various options for setting the two estimates: just one, or
other, or both values separately, or both together. Note that I
haven't touched the estimate that recursion will last for 10 loops. I
figured that people would object to two knobs.

Thoughts?

There are 2 other ways to speed up the query. One is to set
enable_seqscan = off, which helps about 20%, but may have other
consequences. Two is to set work_mem = 512MB, so that the poor plan
(hash) works as fast as possible, but that is far from optimal either.
Getting the right plan is x20 faster than either of those
alternatives.

--
Simon Riggs http://www.EnterpriseDB.com/