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/
recursive_worktable_estimate.v1.patch
Description: Binary data
graph_query_explains.out
Description: Binary data
