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/
On Wed, 27 Oct 2021 at 15:58, Simon Riggs <simon.riggs@enterprisedb.com> wrote:
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.
If you think this should be derived without parameters, then we would
want a function that starts at 1 for 1 input row and gets much larger
for larger input. The thinking here is that Graph OLTP is often a
shortest path between two nodes, whereas Graph Analytics and so the
worktable will get much bigger.
So I'm, thinking we use
rel->tuples = min(1, cte_rows * cte_rows/2);
--
Simon Riggs http://www.EnterpriseDB.com/
The factor 10 should not be hardcoded in the planner, but should be
settable, just as cursor_tuple_fraction is.
I feel considerably out of my depth here, but I like the idea of a working
table size multiplier GUC, given the challenges of predicting the number of
iterations (and any adjustments to cardinality per iteration). An
exponential cost function may lead to increasingly pathological outcomes,
especially when estimates for cte_rows are off.
In the EXPLAINs, it looked like the estimates for knows_pkey were off by an
order of magnitude or so. It's possible the planner would have chosen the
Nested Loop plan if knows_pkey had estimated to rows=87 (as the WindowAgg
would have estimated to roughly the same size as the second plan anyways,
even with rel->tuples = 10 * cte_rows).
I also wonder if there's a better default than cte_rows * 10, but
implementing a new GUC sounds like a reasonable solution to this as well.
--
Kenaniah
On Sat, Jan 22, 2022 at 1:58 PM Simon Riggs <simon.riggs@enterprisedb.com>
wrote:
Show quoted text
On Wed, 27 Oct 2021 at 15:58, Simon Riggs <simon.riggs@enterprisedb.com>
wrote: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.If you think this should be derived without parameters, then we would
want a function that starts at 1 for 1 input row and gets much larger
for larger input. The thinking here is that Graph OLTP is often a
shortest path between two nodes, whereas Graph Analytics and so the
worktable will get much bigger.So I'm, thinking we use
rel->tuples = min(1, cte_rows * cte_rows/2);
--
Simon Riggs http://www.EnterpriseDB.com/
On 31.12.21 15:10, Simon Riggs wrote:
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.If you think this should be derived without parameters, then we would
want a function that starts at 1 for 1 input row and gets much larger
for larger input. The thinking here is that Graph OLTP is often a
shortest path between two nodes, whereas Graph Analytics and so the
worktable will get much bigger.
On the one hand, this smells like a planner hint. But on the other
hand, it doesn't look like we will come up with proper graph-aware
selectivity estimation system any time soon, so just having all graph
OLTP queries suck until then because the planner hint is hardcoded
doesn't seem like a better solution. So I think this setting can be ok.
I think the way you have characterized it makes sense, too: for graph
OLAP, you want a larger value, for graph OLTP, you want a smaller value.
On Tue, 25 Jan 2022 at 14:44, Peter Eisentraut <
peter.eisentraut@enterprisedb.com> wrote:
On 31.12.21 15:10, Simon Riggs wrote:
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.If you think this should be derived without parameters, then we would
want a function that starts at 1 for 1 input row and gets much larger
for larger input. The thinking here is that Graph OLTP is often a
shortest path between two nodes, whereas Graph Analytics and so the
worktable will get much bigger.On the one hand, this smells like a planner hint. But on the other
hand, it doesn't look like we will come up with proper graph-aware
selectivity estimation system any time soon, so just having all graph
OLTP queries suck until then because the planner hint is hardcoded
doesn't seem like a better solution. So I think this setting can be ok.
I think the way you have characterized it makes sense, too: for graph
OLAP, you want a larger value, for graph OLTP, you want a smaller value.
Do you think there is a case to replace the 10x multiplier with
"recursive_worktable_estimate" for total_rows calculation in the
cost_recursive_union function too?
On Tue, Jan 25, 2022 at 4:44 AM Peter Eisentraut
<peter.eisentraut@enterprisedb.com> wrote:
On the one hand, this smells like a planner hint. But on the other
hand, it doesn't look like we will come up with proper graph-aware
selectivity estimation system any time soon, so just having all graph
OLTP queries suck until then because the planner hint is hardcoded
doesn't seem like a better solution. So I think this setting can be ok.
I agree. It's a bit lame, but seems pretty harmless, and I can't see
us realistically doing a lot better with any reasonable amount of
work.
--
Robert Haas
EDB: http://www.enterprisedb.com
On Fri, 28 Jan 2022 at 14:07, Robert Haas <robertmhaas@gmail.com> wrote:
On Tue, Jan 25, 2022 at 4:44 AM Peter Eisentraut
<peter.eisentraut@enterprisedb.com> wrote:On the one hand, this smells like a planner hint. But on the other
hand, it doesn't look like we will come up with proper graph-aware
selectivity estimation system any time soon, so just having all graph
OLTP queries suck until then because the planner hint is hardcoded
doesn't seem like a better solution. So I think this setting can be ok.I agree. It's a bit lame, but seems pretty harmless, and I can't see
us realistically doing a lot better with any reasonable amount of
work.
Shall I set this as Ready For Committer?
--
Simon Riggs http://www.EnterpriseDB.com/
Hi,
On 2022-03-10 17:42:14 +0000, Simon Riggs wrote:
Shall I set this as Ready For Committer?
Currently this CF entry fails on cfbot: https://cirrus-ci.com/task/4531771134967808?logs=test_world#L1158
[16:27:35.772] # Failed test 'no parameters missing from postgresql.conf.sample'
[16:27:35.772] # at t/003_check_guc.pl line 82.
[16:27:35.772] # got: '1'
[16:27:35.772] # expected: '0'
[16:27:35.772] # Looks like you failed 1 test of 3.
[16:27:35.772] [16:27:35] t/003_check_guc.pl ..............
Marked as waiting on author.
- Andres
On Tue, 22 Mar 2022 at 00:04, Andres Freund <andres@anarazel.de> wrote:
On 2022-03-10 17:42:14 +0000, Simon Riggs wrote:
Shall I set this as Ready For Committer?
Currently this CF entry fails on cfbot: https://cirrus-ci.com/task/4531771134967808?logs=test_world#L1158
[16:27:35.772] # Failed test 'no parameters missing from postgresql.conf.sample'
[16:27:35.772] # at t/003_check_guc.pl line 82.
[16:27:35.772] # got: '1'
[16:27:35.772] # expected: '0'
[16:27:35.772] # Looks like you failed 1 test of 3.
[16:27:35.772] [16:27:35] t/003_check_guc.pl ..............Marked as waiting on author.
Thanks.
I've corrected that by adding a line to postgresql.conf.sample, as
well as adding docs.
--
Simon Riggs http://www.EnterpriseDB.com/
Attachments:
recursive_worktable_estimate.v2.patchapplication/octet-stream; name=recursive_worktable_estimate.v2.patchDownload+41-3
Robert Haas <robertmhaas@gmail.com> writes:
On Tue, Jan 25, 2022 at 4:44 AM Peter Eisentraut
<peter.eisentraut@enterprisedb.com> wrote:On the one hand, this smells like a planner hint. But on the other
hand, it doesn't look like we will come up with proper graph-aware
selectivity estimation system any time soon, so just having all graph
OLTP queries suck until then because the planner hint is hardcoded
doesn't seem like a better solution. So I think this setting can be ok.
I agree. It's a bit lame, but seems pretty harmless, and I can't see
us realistically doing a lot better with any reasonable amount of
work.
Yeah, agreed on all counts. The thing that makes it lame is that
there's no reason to expect that the same multiplier is good for
every recursive query done in an installation, or even in a session.
One could imagine dealing with that by adding custom syntax to WITH,
as we have already done once:
WITH RECURSIVE cte1 AS SCALE 1.0 (SELECT ...
But I *really* hesitate to go there, mainly because once we do
something like that we can't ever undo it. I think Simon's
proposal is a reasonable low-effort compromise.
Some nitpicks:
* The new calculation needs clamp_row_est(), since the float
GUC could be fractional or even zero.
* Do we want to prevent the GUC value from being zero? It's not
very sensible, plus I think we might want to reserve that value
to mean "use the built-in calculation", in case we ever do put
in some smarter logic here. But I'm not sure what a reasonable
non-zero lower bound would be.
* The proposed docs claim that a smaller setting works by biasing
the planner towards fast-start plans, but I don't think I believe
that explanation. I'd venture that we want text more along the
lines of "This may help the planner choose the most appropriate
method for joining the work table to the query's other tables".
regards, tom lane
On Wed, 23 Mar 2022 at 17:36, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Robert Haas <robertmhaas@gmail.com> writes:
On Tue, Jan 25, 2022 at 4:44 AM Peter Eisentraut
<peter.eisentraut@enterprisedb.com> wrote:On the one hand, this smells like a planner hint. But on the other
hand, it doesn't look like we will come up with proper graph-aware
selectivity estimation system any time soon, so just having all graph
OLTP queries suck until then because the planner hint is hardcoded
doesn't seem like a better solution. So I think this setting can be ok.I agree. It's a bit lame, but seems pretty harmless, and I can't see
us realistically doing a lot better with any reasonable amount of
work.Yeah, agreed on all counts. The thing that makes it lame is that
there's no reason to expect that the same multiplier is good for
every recursive query done in an installation, or even in a session.One could imagine dealing with that by adding custom syntax to WITH,
as we have already done once:WITH RECURSIVE cte1 AS SCALE 1.0 (SELECT ...
But I *really* hesitate to go there, mainly because once we do
something like that we can't ever undo it. I think Simon's
proposal is a reasonable low-effort compromise.Some nitpicks:
* The new calculation needs clamp_row_est(), since the float
GUC could be fractional or even zero.
True, will do.
* Do we want to prevent the GUC value from being zero? It's not
very sensible, plus I think we might want to reserve that value
to mean "use the built-in calculation", in case we ever do put
in some smarter logic here. But I'm not sure what a reasonable
non-zero lower bound would be.
Agreed, makes sense.
* The proposed docs claim that a smaller setting works by biasing
the planner towards fast-start plans, but I don't think I believe
that explanation. I'd venture that we want text more along the
lines of "This may help the planner choose the most appropriate
method for joining the work table to the query's other tables".
OK, will improve.
[New patch version pending]
--
Simon Riggs http://www.EnterpriseDB.com/
On Wed, 23 Mar 2022 at 18:20, Simon Riggs <simon.riggs@enterprisedb.com> wrote:
[New patch version pending]
--
Simon Riggs http://www.EnterpriseDB.com/
Attachments:
recursive_worktable_estimate.v3.patchapplication/octet-stream; name=recursive_worktable_estimate.v3.patchDownload+47-3
Simon Riggs <simon.riggs@enterprisedb.com> writes:
[New patch version pending]
Do you have any objection if I rename the GUC to
recursive_worktable_factor? That seems a bit clearer as to what
it does, and it leaves more room for other knobs in the same area
if we decide we need any.
regards, tom lane
On Wed, 23 Mar 2022 at 20:25, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Simon Riggs <simon.riggs@enterprisedb.com> writes:
[New patch version pending]
Do you have any objection if I rename the GUC to
recursive_worktable_factor? That seems a bit clearer as to what
it does, and it leaves more room for other knobs in the same area
if we decide we need any.
None, I think your proposal is a better name.
--
Simon Riggs http://www.EnterpriseDB.com/
Simon Riggs <simon.riggs@enterprisedb.com> writes:
On Wed, 23 Mar 2022 at 20:25, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Do you have any objection if I rename the GUC to
recursive_worktable_factor? That seems a bit clearer as to what
it does, and it leaves more room for other knobs in the same area
if we decide we need any.
None, I think your proposal is a better name.
Pushed that way.
regards, tom lane
On Thu, 24 Mar 2022 at 15:48, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Simon Riggs <simon.riggs@enterprisedb.com> writes:
On Wed, 23 Mar 2022 at 20:25, Tom Lane <tgl@sss.pgh.pa.us> wrote:
Do you have any objection if I rename the GUC to
recursive_worktable_factor? That seems a bit clearer as to what
it does, and it leaves more room for other knobs in the same area
if we decide we need any.None, I think your proposal is a better name.
Pushed that way.
Ok, thanks.
--
Simon Riggs http://www.EnterpriseDB.com/