Thread: Query with straightforward plan changes and becomes 6520 times slower after VACUUM ANALYZE

On Wed, 19 May 2021 at 01:36, Jan Kort <jan.kort@genetics.nl> wrote:
> After VACUUM ANALYZE the plan becomes inefficient again, and does not start with the gfo_zaken_kosten primary key,
theplan starts at the wrong end with an index scan on 1M rows:
 
>
> Merge Join  (cost=1.48..1.59 rows=1 width=159) (actual time=619.374..619.376 rows=1 loops=1)
>   Merge Cond: (gfo_zaken.id = gfo_zaken_kosten.gfo_zaken_id)
>   ->  Nested Loop  (cost=0.43..96503.47 rows=1048587 width=155) (actual time=0.022..619.359 rows=9 loops=1)
>         Join Filter: (gfo_zaken.zaaktypecode_id = gfo_zaken_typecode.id)
>         Rows Removed by Join Filter: 4194316
>         ->  Index Scan using gfo_zakenp on gfo_zaken  (cost=0.43..33587.23 rows=1048587 width=8) (actual
time=0.006..141.167rows=1048587 loops=1)
 
>         ->  Materialize  (cost=0.00..1.06 rows=4 width=155) (actual time=0.000..0.000 rows=4 loops=1048587)
>               ->  Seq Scan on gfo_zaken_typecode  (cost=0.00..1.04 rows=4 width=155) (actual time=0.011..0.012 rows=4
loops=1)
>   ->  Sort  (cost=1.05..1.05 rows=1 width=8) (actual time=0.012..0.012 rows=1 loops=1)
>         Sort Key: gfo_zaken_kosten.gfo_zaken_id
>         Sort Method: quicksort  Memory: 25kB
>         ->  Seq Scan on gfo_zaken_kosten  (cost=0.00..1.04 rows=1 width=8) (actual time=0.008..0.008 rows=1 loops=1)
>               Filter: (id = 13)
>               Rows Removed by Filter: 2
> Planning Time: 69.151 ms
> Execution Time: 619.410 ms

It looks like something is a bit weird with the merge join costing
code. Merge join not a very good choice in this case as out of the 3
values you have in gfo_zaken_kosten, 2 are at the very start of the
sorted merge join input in the gfo_zaken table and the 3rd is right at
the end.  That means the merge join must read all of gfo_zaken to join
the 3 rows in gfo_zaken_kosten.

Here's a minimal case to reproduce:

drop table if exists million,three;
create table million (id int primary key);
create table three (id int primary key, million_id int not null);

insert into million select x from generate_series(1,1000000) x;
insert into three values(1,1),(2,1),(3,1000000);

analyze million,three;
explain analyze select * from million m inner join three t on m.id =
t.million_id;

Gives: Merge Join  (cost=1.49..1.56 rows=3 width=12)

The weird thing is that when I just put the two rows in the "three"
table, that Merge Join is the planner's last choice:

truncate three;
insert into three values(1,1),(3,1000000);
analyze three;

set enable_nestloop=0; set enable_hashjoin=0; set
max_parallel_Workers_per_Gather=0;
explain analyze select * from million m inner join three t on m.id =
t.million_id;

Gives me: Merge Join  (cost=1.46..32909.49 rows=2 width=12)

A total cost of 32909.49 is quite a bit higher than the 1.56 of when
the table had 3 rows. You'd expect the cost could only drop if we
removed a row.

The first choice is a parameterized nested loop:

Nested Loop  (cost=0.42..9.91 rows=2 width=12)

So it appears that the total cost of the merge join of 1.56 is pretty
unrealistic.

I'll debug this and see if I can see what's going on.

(I was a bit worried that this might have been down to the fairly new
code that uses the presence of foreign keys to help with join
selectivity estimations. It appears that's not the case.)

David

On Wed, 19 May 2021 at 12:35, David Rowley <dgrowleyml@gmail.com> wrote:
> I'll debug this and see if I can see what's going on.

This is down to the fact that when there are 2 items in the "three"
table we have a histogram in the stats and we can get the upper bound
by just looking at the final histogram bucket.

However, when there are 3 items, or more accurately, there's a
duplicate, we don't build a histogram and just have a
most-common-values list instead.  I've not yet checked the logic for
what we include in the MCV list but it appears in this case we only
store the item that's duplicated, in this case, the value 1.  We
calculate the end bound of the merge join with that value, which is a
bad choice as that makes it appear that the end bound is very close to
or the same as the start bound, making the merge join seem very cheap.

truncate three;
insert into three values(1,1),(2,1),(3,1000000);
analyze three;
select most_common_vals,histogram_bounds from pg_stats where tablename
= 'three' and attname = 'million_id';

-[ RECORD 1 ]----+----
most_common_vals | {1}
histogram_bounds |

truncate three;
insert into three values(1,1),(3,1000000);
analyze three;
select most_common_vals,histogram_bounds from pg_stats where tablename
= 'three' and attname = 'million_id';

-[ RECORD 1 ]----+------------
most_common_vals |
histogram_bounds | {1,1000000}

I'm not really sure the best way to make this better.  It seems like
an unfortunate bad case. I'm not sure if it'd be better to try and be
more inclusive when building MCV lists. But then, what would the logic
be when we don't have enough buckets to store more items.

There is some code in get_variable_range() that's #ifdef'd out to get
the actual range, when possible. There's a comment explaining why we
don't do that.

/*
* XXX It's very tempting to try to use the actual column min and max, if
* we can get them relatively-cheaply with an index probe.  However, since
* this function is called many times during join planning, that could
* have unpleasant effects on planning speed.  Need more investigation
* before enabling this.
*/
#ifdef NOT_USED
if (get_actual_variable_range(root, vardata, sortop, collation, min, max))
return true;
#endif

For this case, it might be ok to have done that since we have
RestrictInfo.scansel_cache. It does not seem as likely that we'll end
up doing get_actual_variable_range too often. However, there are
likely other cases that are not as well cached which we could make too
slow if we did call get_actual_variable_range.

That makes me think the best fix would be to do something better
during ANALYZE and maybe try and include some more upper bound MCVs.
I'm not yet too sure what drawbacks there might be from doing that.

David

On Wed, 19 May 2021 at 14:13, David Rowley <dgrowleyml@gmail.com> wrote:
> That makes me think the best fix would be to do something better
> during ANALYZE and maybe try and include some more upper bound MCVs.
> I'm not yet too sure what drawbacks there might be from doing that.

I had a quick look at the ANALYZE code and see that we only consider
items for the MCV list when they appear more than once in the analyzed
set.  When it comes to the histogram, we only consider making the
histogram if there are at least 2 items that are not covered in the
MCV list. The comment mentions:

/*
* Generate a histogram slot entry if there are at least two distinct
* values not accounted for in the MCV list.  (This ensures the
* histogram won't collapse to empty or a singleton.)
*/

So given we only have 2 distinct values in the "three" table and one
of those is tracked in the MCV list, there are not enough values
remaining to build a histogram.

It seems you've hit about the worst-case here. If you'd had 1 more
value in the gfo_zaken_kosten table then that would have been enough
to build a histogram. Or if the 98 value was not duplicated then we'd
not have built an MCV list and built a histogram with the two values
instead.

If you want a workaround, you could do:

alter table trial.gfo_zaken_kosten alter column gfo_zaken_id set statistics 0;
delete from pg_statistic where
starelid='trial.gfo_zaken_kosten'::regclass and staattnum=2;
analyze trial.gfo_zaken_kosten;

that's a bit dirty though. You'd need to do:

alter table trial.gfo_zaken_kosten alter column gfo_zaken_id set statistics -1;
analyze trial.gfo_zaken_kosten;

if that table was to ever change, else you might get bad plans due to
lack of stats.

David

Hi David,

Ok so the problem is that the MCV list is created, because there are groups of common values, but then this has no
effect,because there are not enough single values to create a histogram?
 

That is not such a rare case as I would have hoped, for example this would then also cause the same behavior:

values(1,1),(2,1),(3,1000000),(4,2),(5,2),(6,3),(7,3);

And it seems to do.

Ranges can then be longer too:

values(1,1),(2,1),(4,1),(3,1000000);

for some reason I can't reverse the ranges:

values(1,1000000),(2,1000000),(3,1);

I don’t understand why that doesn't create a bad plan, there seems to be order involved too.

I admit that this is still somewhat rare, but much less rare than I was hoping for.

A few more things:

Using text as primary key seems to perform good too, even if it keeps the same "merge" plan:

create table million (id text primary key); create table three (id text primary key, million_id text not null);

What the high value is and how close it is to the low value seems to matter:

values(1,1),(2,1),(3,100000);
values(1,1),(2,1),(3,10000);
values(1,1),(2,1),(3,1000);

Gets progressively less bad, again the plan is not changed, but the execution of it becomes more efficient.

It seems like it goes through the records from 1 till say 10000 one by one.

Regards,

Jan

-----Oorspronkelijk bericht-----
Van: David Rowley <dgrowleyml@gmail.com> 
Verzonden: woensdag 19 mei 2021 09:52
Aan: Jan Kort <jan.kort@genetics.nl>
CC: pgsql-bugs@lists.postgresql.org
Onderwerp: Re: Query with straightforward plan changes and becomes 6520 times slower after VACUUM ANALYZE

On Wed, 19 May 2021 at 14:13, David Rowley <dgrowleyml@gmail.com> wrote:
> That makes me think the best fix would be to do something better 
> during ANALYZE and maybe try and include some more upper bound MCVs.
> I'm not yet too sure what drawbacks there might be from doing that.

I had a quick look at the ANALYZE code and see that we only consider items for the MCV list when they appear more than
oncein the analyzed set.  When it comes to the histogram, we only consider making the histogram if there are at least 2
itemsthat are not covered in the MCV list. The comment mentions:
 

/*
* Generate a histogram slot entry if there are at least two distinct
* values not accounted for in the MCV list.  (This ensures the
* histogram won't collapse to empty or a singleton.) */

So given we only have 2 distinct values in the "three" table and one of those is tracked in the MCV list, there are not
enoughvalues remaining to build a histogram.
 

It seems you've hit about the worst-case here. If you'd had 1 more value in the gfo_zaken_kosten table then that would
havebeen enough to build a histogram. Or if the 98 value was not duplicated then we'd not have built an MCV list and
builta histogram with the two values instead.
 

If you want a workaround, you could do:

alter table trial.gfo_zaken_kosten alter column gfo_zaken_id set statistics 0; delete from pg_statistic where
starelid='trial.gfo_zaken_kosten'::regclassand staattnum=2; analyze trial.gfo_zaken_kosten;
 

that's a bit dirty though. You'd need to do:

alter table trial.gfo_zaken_kosten alter column gfo_zaken_id set statistics -1; analyze trial.gfo_zaken_kosten;

if that table was to ever change, else you might get bad plans due to lack of stats.

David

On Wed, 19 May 2021 at 22:55, Jan Kort <jan.kort@genetics.nl> wrote:
> Ok so the problem is that the MCV list is created, because there are groups of common values, but then this has no
effect,because there are not enough single values to create a histogram? 

The problem is mainly that the join costing code for the merge join
looks at the statistics on the column to get the upper bound of the
merge.  Ideally this value would be 1000000 in my "three" table.
However, the MCV list sees the value of 1 as a most common value due
to it appearing twice. When we consider building a histogram with the
remaining values, we see we don't have enough to build one. We need at
least 2 values.  This means when the merge join costing code tries to
get the upper bound of the merge (ideally 1000000), it only has the
MCV list to go on, which just contains the value 1.  The 1000000 value
is not tracked at all. This makes it appear that the merge join will
start and end with the same value, which is very cheap, and it costs
that path accordingly.

> That is not such a rare case as I would have hoped, for example this would then also cause the same behavior:
>
> values(1,1),(2,1),(3,1000000),(4,2),(5,2),(6,3),(7,3);

Yeah, technically you can add enough duplicate values to fill the MCV
list then just not enough to build the histogram.  However, to
maintain the problem case, the MCVs that you do add will need to be
very early in the range.  Your last MCV here is 3, which would make
the estimated merge range of 1 to 3, which is not as cheap as 1 to 1

> And it seems to do.
>
> Ranges can then be longer too:
>
> values(1,1),(2,1),(4,1),(3,1000000);
>
> for some reason I can't reverse the ranges:
>
> values(1,1000000),(2,1000000),(3,1);
>
> I don’t understand why that doesn't create a bad plan, there seems to be order involved too.

That's because the 1000000 value will make it into the MCV list and
extend the estimated range of the merge join.

> Using text as primary key seems to perform good too, even if it keeps the same "merge" plan:

That will be because of the change in sort order between text and int.
e.g 1000000 sorts before 2, for example.  I don't think you should
work around the problem this way.

> What the high value is and how close it is to the low value seems to matter:

Yeah, that's because merge join can end by reading fewer values from
the "million" table.  When the highest value is 1000000 it needs to
read the entire "million" table.

> values(1,1),(2,1),(3,100000);
> values(1,1),(2,1),(3,10000);
> values(1,1),(2,1),(3,1000);
>
> Gets progressively less bad, again the plan is not changed, but the execution of it becomes more efficient.
>
> It seems like it goes through the records from 1 till say 10000 one by one.

This is how Merge Join works. See
https://en.wikipedia.org/wiki/Sort-merge_join . There's a c# example
there that shows how you have to consume a value from the side with
the lowest value until you find an equal value, where you join, or a
higher value, where you must consume the other side until you find
another equal value.  The join ends when you run out of values on one
side.

David