Re: [HACKERS] Perfomance bug in v10
Teodor Sigaev writes: >> BTW, was the larger query plan that you showed (with a Materialize node) >> generated by 9.6, or v10 HEAD? Because I would be surprised if 9.6 did > v10, > commit acbd8375e954774181b673a31b814e9d46f436a5 > Author: Magnus Hagander > Date: Fri Jun 2 11:18:24 2017 +0200 Thanks. Meanwhile, I poked into this larger example (which Teodor had sent me the data for off-list). I concur with the conclusion that the speed change is because the HEAD code inserts a Materialize node on the inside of an inner loop even though it thinks the outside will produce only one row. In reality the outside produces five rows so there's a small win from the Materialize, and because this is all in a SubPlan that gets executed 24121 times, that adds up. However, I still don't think that this is evidence in favor of forcing a Materialize on the inside of a nestloop even when we think the outside will produce just one row; and it's certainly not evidence that we should do that accidentally in a small number of cases due to a logic error. This query itself has got four other places where there's a nestloop with an outer rel that's predicted to return just one row, and in those four places the prediction is correct. If we were to establish a policy like that, we'd be adding useless overhead to those other places. (Out of idle curiosity, I hacked the planner to force materialization for all non-parameterized nestloop inners, and confirmed that that adds back a couple hundred msec to this query. It might have been worse, except that two of the four other places are in SubPlans that never get executed in this specific example.) So I think it's just chance that this bug was a net benefit on this query, and it's not a reason not to go ahead with the patch. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Perfomance bug in v10
BTW, was the larger query plan that you showed (with a Materialize node) generated by 9.6, or v10 HEAD? Because I would be surprised if 9.6 did v10, commit acbd8375e954774181b673a31b814e9d46f436a5 Author: Magnus Hagander Date: Fri Jun 2 11:18:24 2017 +0200 -- Teodor Sigaev E-mail: teo...@sigaev.ru WWW: http://www.sigaev.ru/ -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Perfomance bug in v10
Teodor Sigaev writes: >> There were old threads about considering a risk factor when estimating >> plans, and I'm thinking this issue is the planner failing to do >> exactly that. > I'm afraid it's tool late for v10 Yeah, we're surely not opening that can of worms for v10. Right now we have to be content with avoiding regressions from 9.6. BTW, was the larger query plan that you showed (with a Materialize node) generated by 9.6, or v10 HEAD? Because I would be surprised if 9.6 did it. But this bug could well cause HEAD to insert Materialize nodes in surprising places, because it would have the effect of making a nestloop with a single row expected from the outer rel look cheaper with a Materialize on the inner rel than without. (Actually I guess 9.6 would have done that too, but only for semi/anti join cases, limiting the visibility of the bug.) regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Perfomance bug in v10
On Fri, Jun 2, 2017 at 11:46 AM, Teodor Sigaev wrote: >> There were old threads about considering a risk factor when estimating >> plans, and I'm thinking this issue is the planner failing to do >> exactly that. >> > I'm afraid it's tool late for v10 Clearly -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Perfomance bug in v10
There were old threads about considering a risk factor when estimating plans, and I'm thinking this issue is the planner failing to do exactly that. I'm afraid it's tool late for v10 -- Teodor Sigaev E-mail: teo...@sigaev.ru WWW: http://www.sigaev.ru/ -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Perfomance bug in v10
On Fri, Jun 2, 2017 at 10:27 AM, Tom Lane wrote: > Teodor Sigaev writes: >>> Teodor, could you check if this patch fixes your real-world problem? > >> It works fine with original query, thank you. But some other query slowdowns >> for >> ~10% (9 secs vs 10 secs). Look at following part of plans of huge query: >> ... >> As you said, it removes Materialize node, although it's useful here. > > Meh. If it's expecting only one outer row, it shouldn't be using a > Materialize on the inner side, period. That's not sane per the cost > model. You haven't shown us enough to guess why the rowcount estimates > are so far off reality in this query, but I don't think it's the fault > of this patch if the result is slightly slower given that much error. > > Most likely, the answer for your real-world problem is "you need to > ANALYZE before running the query". > > regards, tom lane I don't know. Perhaps the risky part is assuming rows=1 for non-unique inner scans. In fact a wrongly estimated rows=1 outer scan would be just as risky. There were old threads about considering a risk factor when estimating plans, and I'm thinking this issue is the planner failing to do exactly that. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Perfomance bug in v10
Teodor Sigaev writes: >> Teodor, could you check if this patch fixes your real-world problem? > It works fine with original query, thank you. But some other query slowdowns > for > ~10% (9 secs vs 10 secs). Look at following part of plans of huge query: > ... > As you said, it removes Materialize node, although it's useful here. Meh. If it's expecting only one outer row, it shouldn't be using a Materialize on the inner side, period. That's not sane per the cost model. You haven't shown us enough to guess why the rowcount estimates are so far off reality in this query, but I don't think it's the fault of this patch if the result is slightly slower given that much error. Most likely, the answer for your real-world problem is "you need to ANALYZE before running the query". regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Perfomance bug in v10
Teodor, could you check if this patch fixes your real-world problem? It works fine with original query, thank you. But some other query slowdowns for ~10% (9 secs vs 10 secs). Look at following part of plans of huge query: without patch: -> Nested Loop (cost=34.82..50.91 rows=1 width=20) (actual time=0.017..0.061 rows=5 loops=24121) -> ... -> Materialize (cost=0.56..15.69 rows=1 width=5) (actual time=0.003..0.004 rows=2 loops=109061) -> Index Scan using ... (cost=0.56..15.68 rows=1 width=5) (actual time=0.013..0.014 rows=2 loops=24121) with patch: -> Nested Loop (cost=34.82..50.91 rows=1 width=20) (actual time=0.018..0.063 rows=5 loops=24121) -> ... -> Index Scan using ... (cost=0.56..15.68 rows=1 width=5) (actual time=0.012..0.013 rows=2 loops=109061) (dots hidden the same parts) As you said, it removes Materialize node, although it's useful here. If you wish, I can do a test suite, its size will be around 10MB and send it by private email. -- Teodor Sigaev E-mail: teo...@sigaev.ru WWW: http://www.sigaev.ru/ -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Perfomance bug in v10
David Rowley writes: > On 1 June 2017 at 04:16, Teodor Sigaev wrote: >> I found an example where v10 chooses extremely non-optimal plan: >> ... > This is all caused by get_variable_numdistinct() deciding that all > values are distinct because ntuples < DEFAULT_NUM_DISTINCT. Uh, no. I traced through this and found that with your hack in place, final_cost_nestloop was costing the desired nestloop paths at less than they were costed in HEAD. That makes no sense: surely, accounting for the fact that the executor might stop early should never result in a higher cost estimate than ignoring that possibility does. After some navel-gazing I realized that there is an ancient oversight in final_cost_nestloop's cost estimate for semi/anti-join cases. To wit, in its attempt to ensure that it always charges inner_run_cost at least once, it may end up charging that twice. Specifically, what we get in this case is outer_path_rows = 1, outer_matched_rows = 0 (implying one unmatched outer row) which will cause the existing logic to add both inner_run_cost and inner_rescan_run_cost to the cost estimate, as if we needed to run the inner plan twice not once. Correcting that, as in the attached draft patch, fixes Teodor's example. Now, this patch also causes some changes in the regression test outputs that are a bit like your patch's side-effects, but on close inspection I am not at all convinced that these changes are wrong. As an example, looking at the first change without "costs off": regression=# explain (verbose) select * from j1 inner join (select distinct id from j3) j3 on j1.id = j3.id; QUERY PLAN --- Nested Loop (cost=1.03..2.12 rows=1 width=8) Output: j1.id, j3.id Inner Unique: true Join Filter: (j1.id = j3.id) -> Unique (cost=1.03..1.04 rows=1 width=4) Output: j3.id -> Sort (cost=1.03..1.03 rows=2 width=4) Output: j3.id Sort Key: j3.id -> Seq Scan on public.j3 (cost=0.00..1.02 rows=2 width=4) Output: j3.id -> Seq Scan on public.j1 (cost=0.00..1.03 rows=3 width=4) Output: j1.id (13 rows) Note that both sides of this join are known unique, so that we'd produce an inner-unique-true join from either direction of joining. I don't think it's so insane to put the larger rel on the inside, because with a size-1 rel on the inside, there is nothing to be gained from stop-early behavior. Moreover, this way we don't need a Materialize node (since we're not predicting the inner to be scanned more than once anyway). So the fact that this way is estimated to be cheaper than the other way is not that surprising after all. Yeah, it's a bit brittle in the face of the outer rel producing more rows than we expect, but that's true of every nestloop join plan we ever make. Fixing that is not a task for v10. Teodor, could you check if this patch fixes your real-world problem? regards, tom lane diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index cdb18d9..324c8c1 100644 *** a/src/backend/optimizer/path/costsize.c --- b/src/backend/optimizer/path/costsize.c *** final_cost_nestloop(PlannerInfo *root, N *** 2287,2306 * difficult to estimate whether that will happen (and it could * not happen if there are any unmatched outer rows!), so be * conservative and always charge the whole first-scan cost once. */ run_cost += inner_run_cost; /* Add inner run cost for additional outer tuples having matches */ ! if (outer_matched_rows > 1) ! run_cost += (outer_matched_rows - 1) * inner_rescan_run_cost * inner_scan_frac; ! ! /* Add inner run cost for unmatched outer tuples */ ! run_cost += (outer_path_rows - outer_matched_rows) * ! inner_rescan_run_cost; ! /* And count the unmatched join tuples as being processed */ ! ntuples += (outer_path_rows - outer_matched_rows) * ! inner_path_rows; } } else --- 2287,2317 * difficult to estimate whether that will happen (and it could * not happen if there are any unmatched outer rows!), so be * conservative and always charge the whole first-scan cost once. + * We consider this charge to correspond to the first unmatched + * outer row, unless there isn't one in our estimate, in which + * case blame it on the first matched row. */ + double outer_unmatched_rows; + + outer_unmatched_rows = outer_path_rows - outer_matched_rows; + + /* While at it, count unmatched join tuples as being processed */ + ntuples += outer_unmatched_rows * inner_path_rows; + + /* Now add the forced full scan, and decrement appropriate count */ run_cost += inner_run_cost; + if (outer_unmatched_rows >= 1) + outer_unmatched_rows -= 1; + else
Re: [HACKERS] Perfomance bug in v10
On 2 June 2017 at 03:46, Teodor Sigaev wrote: > I miss here why could the presence of index influence on that? removing > index causes a good plan although it isn't used in both plans . Unique indexes are used as proofs when deciding if a join to the relation is "inner_unique". A nested loop unique join is costed more cheaply than a non-unique one since we can skip to the next outer tuple once we've matched the current outer tuple to an inner tuple. In theory that's half as many comparisons for a non-parameterised nested loop. -- David Rowley http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Perfomance bug in v10
Thank you for the answer! This is all caused by get_variable_numdistinct() deciding that all values are distinct because ntuples < DEFAULT_NUM_DISTINCT. I see that if the example is increased to use 300 tuples instead of 32, then that's enough for the planner to estimate 2 rows instead of clamping to 1, and the bad plan does not look so good anymore since the planner predicts that those nested loops need to be executed more than once. I miss here why could the presence of index influence on that? removing index causes a good plan although it isn't used in both plans . I really think the planner is too inclined to take risks by nesting Nested loops like this, but I'm not all that sure the best solution to fix this, and certainly not for beta1. So, I'm a bit unsure exactly how best to deal with this. It seems like we'd better make some effort, as perhaps this could be a case that might occur when temp tables are used and not ANALYZED, but the only way I can think to deal with it is not to favour unique inner nested loops in the costing model. The unfortunate thing about not doing this is that the planner will no longer swap the join order of a 2-way join to put the unique rel on the inner side. This is evident by the regression test failures caused by patching with the attached, which changes the cost model for nested loops back to what it was before unique joins. The patch, seems, works for this particular case, but loosing swap isn't good thing, I suppose. My other line of thought is just not to bother doing anything about this. There's plenty more queries you could handcraft to trick the planner into generating a plan that'll blow up like this. Is this a realistic enough one to bother accounting for? Did it come from a real world case? else, how did you stumble upon it? Unfortunately, it's taken from real application. -- Teodor Sigaev E-mail: teo...@sigaev.ru WWW: http://www.sigaev.ru/ -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Perfomance bug in v10
On 1 June 2017 at 04:16, Teodor Sigaev wrote: > I found an example where v10 chooses extremely non-optimal plan: > select > i::int as a, > i::int + 1 as b, > 0 as c > into t > from > generate_series(1,32) as i; > > create unique index i on t (c, a); > > explain analyze > SELECT > t1.a, t1.b, > t2.a, t2.b, > t3.a, t3.b, > t4.a, t4.b, > t5.a, t5.b, > t6.a, t6.b > /* > , > t7.a, t7.b, > t8.a, t8.b, > t9.a, t9.b, > t10.a, t10.b > */ > FROM t T1 > LEFT OUTER JOIN t T2 > ON T1.b = T2.a AND T2.c = 0 > LEFT OUTER JOIN t T3 > ON T2.b = T3.a AND T3.c = 0 > LEFT OUTER JOIN t T4 > ON T3.b = T4.a AND T4.c = 0 > LEFT OUTER JOIN t T5 > ON T4.b = T5.a AND T5.c = 0 > LEFT OUTER JOIN t T6 > ON T5.b = T6.a AND T6.c = 0 > LEFT OUTER JOIN t T7 > ON T6.b = T7.a AND T7.c = 0 > LEFT OUTER JOIN t T8 > ON T7.b = T8.a AND T8.c = 0 > LEFT OUTER JOIN t T9 > ON T8.b = T9.a AND T9.c = 0 > LEFT OUTER JOIN t T10 > ON T9.b = T10.a AND T10.c = 0 > WHERE T1.c = 0 AND T1.a = 5 > ; That's pretty unfortunate. It only chooses this plan due to lack of any useful stats on the table. The planner thinks that a seqscan on t6 with Filter (c = 0) will return 1 row, which is not correct. In the good plan t1 is the outer rel of the inner most loop. Here the filter is c = 0 and a = 5, which *does* actually return only 1 row, which means that all of the other nested loops only execute once, as predicted. This is all caused by get_variable_numdistinct() deciding that all values are distinct because ntuples < DEFAULT_NUM_DISTINCT. I see that if the example is increased to use 300 tuples instead of 32, then that's enough for the planner to estimate 2 rows instead of clamping to 1, and the bad plan does not look so good anymore since the planner predicts that those nested loops need to be executed more than once. I really think the planner is too inclined to take risks by nesting Nested loops like this, but I'm not all that sure the best solution to fix this, and certainly not for beta1. So, I'm a bit unsure exactly how best to deal with this. It seems like we'd better make some effort, as perhaps this could be a case that might occur when temp tables are used and not ANALYZED, but the only way I can think to deal with it is not to favour unique inner nested loops in the costing model. The unfortunate thing about not doing this is that the planner will no longer swap the join order of a 2-way join to put the unique rel on the inner side. This is evident by the regression test failures caused by patching with the attached, which changes the cost model for nested loops back to what it was before unique joins. My other line of thought is just not to bother doing anything about this. There's plenty more queries you could handcraft to trick the planner into generating a plan that'll blow up like this. Is this a realistic enough one to bother accounting for? Did it come from a real world case? else, how did you stumble upon it? -- David Rowley http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services dont_reduce_cost_of_inner_unique_nested_loops.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers