Re: [HACKERS] Perfomance bug in v10

[Tom Lane]

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

[Teodor Sigaev]

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

[Tom Lane]

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

[Claudio Freire]

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

[Teodor Sigaev]

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

[Claudio Freire]

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

[Tom Lane]

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 Sigaev]

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

[Tom Lane]

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 

Re: [HACKERS] Perfomance bug in v10

[David Rowley]

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

[Teodor Sigaev]

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

[David Rowley]

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

[HACKERS] Perfomance bug in v10

[Teodor Sigaev]

Hi!

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
;

It takes 4 seconds on my laptop, uncommenting commented lines causes run 
forever. analyzing table or removing index reduces execution time to 
milliseconds regardless on commented or uncommented lines.


The commit
commit 9c7f5229ad68d7e0e4dd149e3f80257893e404d4
Author: Tom Lane 
Date:   Fri Apr 7 22:20:03 2017 -0400

Optimize joins when the inner relation can be proven unique.

seems a root this problem - before it the query takes milliseconds. In 
attachment there is a output of explain analyze with commented lines, my 
attention was attracted by a huge number of loops:


 ->  Materialize  (cost=0.00..1.40 rows=1 width=8) (actual time=0.000..0.001 
rows=17 loops=1048576)




--
Teodor Sigaev   E-mail: teo...@sigaev.ru
   WWW: http://www.sigaev.ru/
Timing is on.
DROP TABLE
Time: 5,268 ms
SELECT 32
Time: 5,515 ms
CREATE INDEX
Time: 14,971 ms
QUERY PLAN  
   
---
 Nested Loop Left Join  (cost=0.00..8.55 rows=1 width=48) (actual 
time=818.219..4159.317 rows=1 loops=1)
   Join Filter: (t1.b = t2.a)
   Rows Removed by Join Filter: 31
   ->  Seq Scan on t t1  (cost=0.00..1.48 rows=1 width=8) (actual 
time=0.026..0.032 rows=1 loops=1)
 Filter: ((c = 0) AND (a = 5))
 Rows Removed by Filter: 31
   ->  Nested Loop Left Join  (cost=0.00..7.06 rows=1 width=40) (actual 
time=10.588..4159.270 rows=32 loops=1)
 Join Filter: (t2.b = t3.a)
 Rows Removed by Join Filter: 993
 ->  Seq Scan on t t2  (cost=0.00..1.40 rows=1 width=8) (actual 
time=0.008..0.020 rows=32 loops=1)
   Filter: (c = 0)
 ->  Nested Loop Left Join  (cost=0.00..5.65 rows=1 width=32) (actual 
time=0.142..129.970 rows=32 loops=32)
   Join Filter: (t3.b = t4.a)
   Rows Removed by Join Filter: 993
   ->  Seq Scan on t t3  (cost=0.00..1.40 rows=1 width=8) (actual 
time=0.002..0.010 rows=32 loops=32)
 Filter: (c = 0)
   ->  Nested Loop Left Join  (cost=0.00..4.23 rows=1 width=24) 
(actual time=0.007..4.055 rows=32 loops=1024)
 Join Filter: (t4.b = t5.a)
 Rows Removed by Join Filter: 993
 ->  Seq Scan on t t4  (cost=0.00..1.40 rows=1 width=8) 
(actual time=0.002..0.010 rows=32 loops=1024)
   Filter: (c = 0)
 ->  Nested Loop Left Join  (cost=0.00..2.82 rows=1 
width=16) (actual time=0.003..0.121 rows=32 loops=32768)
   Join Filter: (t5.b = t6.a)
   Rows Removed by Join Filter: 528
   ->  Seq Scan on t t5  (cost=0.00..1.40 rows=1 
width=8) (actual time=0.002..0.009 rows=32 loops=32768)
 Filter: (c = 0)
   ->  Materialize  (cost=0.00..1.40 rows=1 width=8) 
(actual time=0.000..0.001 rows=17 loops=1048576)
 ->  Seq Scan on t t6  (cost=0.00..1.40 rows=1 
width=8) (actual time=0.008..0.031 rows=32 loops=1)
   Filter: (c = 0)
 Planning time: 3.316 ms
 Execution time: 4159.596 ms
(31 rows)

Time: 4165,372 ms (00:04,165)

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers