Thread: estimates for nested loop very wrong?
Hi, When JOINing two tabels (one with 23 entries, one with 2.5e6 entries), psql estimates the cost of the nested loop method way to high, causing it to use Hash Join, even though Hash Join actually takes 30 seconds, agianst 0.020 seconds for Nested Loop. It really puzzles me why the estimate for the Nested Loop is so bad, as it looks like a rather easy thing to estimate... Below: table db has 2.5e6 entries, column "id" has rather evenly distributed values. column id has a (btree) index. table tmp1 has 23 entries, column "v0" has all unique entries. psql version: 7.2.1 Here is the query twice, once with enable_hashjoin ON, second time with enable_hashjoin OFF, to force psql to use Nested Loop ueadb=> explain analyse select id, var, val from db, tmp1 where id=tmp1.v0; NOTICE: QUERY PLAN: Hash Join (cost=1.29..67863.71 rows=61140 width=38) (actual time=4475.26..32442.99 rows=756 loops=1) -> Seq Scan on db (cost=0.00..54498.12 rows=2520012 width=31) (actual time=0.07..29170.62 rows=2520012 loops=1) -> Hash (cost=1.23..1.23rows=23 width=7) (actual time=0.25..0.25 rows=0 loops=1) -> Seq Scan on tmp1 (cost=0.00..1.23 rows=23width=7) (actual time=0.17..0.22 rows=23 loops=1) Total runtime: 32443.78 msec --Setting hashjoin off, forcing psql to use the Nested Loop ueadb=> set enable_hashjoin = off; ueadb=> explain analyse select id, var, val from db, tmp1 where id=tmp1.v0; NOTICE: QUERY PLAN: Nested Loop (cost=0.00..208256.60 rows=61140 width=38) (actual time=0.92..18.49 rows=756 loops=1) -> Seq Scan on tmp1 (cost=0.00..1.23 rows=23 width=7) (actual time=0.24..0.39 rows=23 loops=1) -> Index Scan using db_id_idx on db (cost=0.00..9021.35rows=2658 width=31) (actual time=0.32..0.69 rows=33 loops=23) Total runtime: 19.20 msec I guess I'll be doing my queries with enable_hashjoin OFF, but is there anythign I'm doing wrong? (Apart from maybe uzing psql 7.2.1 -- would 7.3 be smarter here?)
On Thu, 10 Apr 2003 joostje@komputilo.org wrote: > It really puzzles me why the estimate for the Nested Loop is so bad, > as it looks like a rather easy thing to estimate... > > Below: > table db has 2.5e6 entries, column "id" has rather evenly distributed values. > column id has a (btree) index. > table tmp1 has 23 entries, column "v0" has all unique entries. > psql version: 7.2.1 > > Here is the query twice, once with enable_hashjoin ON, second time > with enable_hashjoin OFF, to force psql to use Nested Loop > > ueadb=> explain analyse select id, var, val from db, tmp1 where id=tmp1.v0; > NOTICE: QUERY PLAN: > > Hash Join (cost=1.29..67863.71 rows=61140 width=38) (actual time=4475.26..32442.99 rows=756 loops=1) > -> Seq Scan on db (cost=0.00..54498.12 rows=2520012 width=31) (actual time=0.07..29170.62 rows=2520012 loops=1) > -> Hash (cost=1.23..1.23 rows=23 width=7) (actual time=0.25..0.25 rows=0 loops=1) > -> Seq Scan on tmp1 (cost=0.00..1.23 rows=23 width=7) (actual time=0.17..0.22 rows=23 loops=1) > Total runtime: 32443.78 msec > > > --Setting hashjoin off, forcing psql to use the Nested Loop > ueadb=> set enable_hashjoin = off; > > > ueadb=> explain analyse select id, var, val from db, tmp1 where id=tmp1.v0; > NOTICE: QUERY PLAN: > > Nested Loop (cost=0.00..208256.60 rows=61140 width=38) (actual time=0.92..18.49 rows=756 loops=1) > -> Seq Scan on tmp1 (cost=0.00..1.23 rows=23 width=7) (actual time=0.24..0.39 rows=23 loops=1) > -> Index Scan using db_id_idx on db (cost=0.00..9021.35 rows=2658 width=31) (actual time=0.32..0.69 rows=33 loops=23) It seems to be misestimating the number of rows to return on db. That's probably why the cost is so wrong (it's over estimating by nearly a factor of 100). Have you analyzed db recently? > I guess I'll be doing my queries with enable_hashjoin OFF, but is there anythign I'm > doing wrong? > (Apart from maybe uzing psql 7.2.1 -- would 7.3 be smarter here?) It might.
joostje@komputilo.org writes:
> When JOINing two tabels (one with 23 entries, one with 2.5e6 entries),
> psql estimates the cost of the nested loop method way to high, causing
> it to use Hash Join, even though Hash Join actually takes 30 seconds,
> agianst 0.020 seconds for Nested Loop.
Have you done an ANALYZE or VACUUM ANALYZE recently?
> Nested Loop (cost=0.00..208256.60 rows=61140 width=38) (actual time=0.92..18.49 rows=756 loops=1)
> -> Seq Scan on tmp1 (cost=0.00..1.23 rows=23 width=7) (actual time=0.24..0.39 rows=23 loops=1)
> -> Index Scan using db_id_idx on db (cost=0.00..9021.35 rows=2658 width=31) (actual time=0.32..0.69 rows=33
loops=23)
> Total runtime: 19.20 msec
The planner is evidently estimating that each row of tmp1 will match 2600+
rows of db, whereas in reality there is only one match. Rather than
mess with enable_hashjoin, you need to find out why that estimate is so
badly off. Are the entries in tmp1 specially selected to correspond to
unique rows of db?
regards, tom lane
Je 2003/04/10(4)/10:04, Tom Lane skribis:
> Have you done an ANALYZE or VACUUM ANALYZE recently?
Jes, both, actually, and the `analyse' quite a few times.
> > Nested Loop (cost=0.00..208256.60 rows=61140 width=38) (actual time=0.92..18.49 rows=756 loops=1)
> The planner is evidently estimating that each row of tmp1 will match 2600+
> rows of db, whereas in reality there is only one match. Rather than
> mess with enable_hashjoin, you need to find out why that estimate is so
> badly off. Are the entries in tmp1 specially selected to correspond to
> unique rows of db?
Well, each entry in tmp1 matches with about 7-80 entries in db, but yes
the problem indeed seems to be that the estimate is so far off.
And no, the entries in tmp1 are not specially selected, they correspond
to `normal' values of id in db (values that are about as frequent as
other values).
I have done VACUUM ANALYSE on the table (and drop index; create index db_id_idx on db(id);).
=> analyse db;
=> select n_distinct from pg_stats where tablename='db' and attname='id'; 1996
=> select count(distinct(id)) from db; 42225
Unless I'm mistaken, pg_nstats.n_distinct should be (aproximately) the same as
count(distinct(id)), but it obviously isn't. Also the most_common_freqs
values are about a 100 times higher than in reality, and, even tough about
900 values of id occur more often than 40 times, in the 'most_common_vals'
list are 7 (of the 10) vals that occur less than 40 times, and the real
top two isn't even represented.
(BTW, the table I'm using now is a little smaller, as it turned out that
a few (75%) of the entries in db had only 3 different id values. This
didn't have any effect on the accurateness of the estimates, though).
BTW,
=> select count(id) from db; 586035
Thanks!
joostje
-- what pg_stat thinks about db.id:
=> select n_distinct, most_common_vals, most_common_freqs from pg_stats where tablename='db' and
attname='id';n_distinct| most_common_vals |
most_common_freqs
------------+-----------------------------------------------------+-------------------------------------------------------------------------------------------------------
1907 | {subo,smys,raha,sjbo,sdai,roal,sooi,stsw,rmwi,snuw} |
{0.00733333,0.007,0.00633333,0.00633333,0.006,0.00566667,0.00566667,0.00566667,0.00533333,0.00533333}
--these estimates are far off:
=> select id, count (id)/586035.0 from db where id='subo' or id='smys' or id='raha' or id='sjbo' or id='sdai' or
id='roal'or id='sooi' or id='stsw' or id='rmwi' or id='snuw' group by id; id | ?column?
------+----------------------raha | 0.000156987210661479rmwi | 3.24212717670446e-05roal | 6.3136160809508e-05sdai |
8.70255189536461e-05sjbo| 6.3136160809508e-05smys | 7.5080839881577e-05snuw | 4.26595681145324e-05sooi |
0.000114327642546947stsw| 6.14297780849267e-05subo | 5.11914817374389e-05
--and these would be the real most_common_freqs:
=> select id, count(id), count(id)/586035.0 from db group by id order by - count(id) limit 10; id | count |
?column?
--------+-------+----------------------indmem | 194 | 0.000331038248568771hton | 97 | 0.000165519124284386raha
| 92 | 0.000156987210661479simo | 87 | 0.000148455297038573sugn | 87 | 0.000148455297038573rjgl | 85 |
0.00014504253158941hroy | 84 | 0.000143336148864829jrgv | 84 | 0.000143336148864829tojo | 83 |
0.000141629766140248lucy | 82 | 0.000139923383415666
-- the above all done after a 'vacuum analyse';
joostje@komputilo.org writes:
> Unless I'm mistaken, pg_nstats.n_distinct should be (aproximately) the same as
> count(distinct(id)), but it obviously isn't. Also the most_common_freqs
> values are about a 100 times higher than in reality, and, even tough about
> 900 values of id occur more often than 40 times, in the 'most_common_vals'
> list are 7 (of the 10) vals that occur less than 40 times, and the real
> top two isn't even represented.
Please try increasing the statistics target (see ALTER TABLE) for db.id, then
re-analyze and see if the estimates get better. The default setting is
10 --- try 20, 50, 100 to see what happens.
regards, tom lane
Je 2003/04/10(4)/12:04, Tom Lane skribis: > joostje@komputilo.org writes: > > Unless I'm mistaken, pg_nstats.n_distinct should be (aproximately) the same as > > count(distinct(id)), but it obviously isn't. Also the most_common_freqs > > values are about a 100 times higher than in reality, and, even tough about > > 900 values of id occur more often than 40 times, in the 'most_common_vals' > > list are 7 (of the 10) vals that occur less than 40 times, and the real > > top two isn't even represented. > > Please try increasing the statistics target (see ALTER TABLE) for db.id, then > re-analyze and see if the estimates get better. The default setting is > 10 --- try 20, 50, 100 to see what happens. Well, the n_distinct estimates get better, but the cost estimates still don't quite add up: `actual cost' is 23.24, cost estimate never gets below 49930. stat.targ n_distinct| correlation cost estimate 5 1917 | 0.43189 3621794.92 10 1998 | 0.3909 3618363.33 20 4330 | -0.247617 1981594.38 50 9708 | 0.0762642 975847.15100 14604 | 0.030706 657631.41200 21855 | 0.0446929 204335.70500 39980 | -0.0497829 121000.31 1000 29468 | 0.0366528 49930.08 1000 29453 | 0.0367673 49954.08 Table 1: various estimates as a function of statistical target actualdistinct values: 42226 actual cost: varies from 5.0 to 27.8 So, the planner still prefers the mergejoin and hashjoin plans, causing the select to take tens of seconds (60 for the mergejoin, I beleve), wheras the Nested Loop takes only 0.024 seconds: For example, for the stat.targ=500 run: => explain analyse SELECT id from db, tmp0 WHERE valida AND poseda='uea' AND tab='pers' AND tmp0.v0=id ; NOTICE: QUERY PLAN: Nested Loop (cost=0.00..121000.31 rows=28184 width=39) (actual time=1.05..23.24 rows=415 loops=1) -> Seq Scan on tmp0 (cost=0.00..20.00 rows=1000 width=32) (actual time=0.22..0.40 rows=29 loops=1) -> Index Scan using db_id_idx on db (cost=0.00..120.63rows=28 width=7) (actual time=0.27..0.75 rows=14 loops=29) Total runtime: 23.92 msec In the above example, tmp0 had 29 values, that correspond to 415 rows in table db. Table db has 586157 rows. The shown select statement is the one used to get all cost estimates in table 1. postgresql: 7.2.1 (debian release 3)
joostje@komputilo.org writes:
> Je 2003/04/10(4)/12:04, Tom Lane skribis:
>> Please try increasing the statistics target (see ALTER TABLE) for db.id, then
>> re-analyze and see if the estimates get better. The default setting is
>> 10 --- try 20, 50, 100 to see what happens.
> Well, the n_distinct estimates get better, but the cost estimates still
> don't quite add up: `actual cost' is 23.24, cost estimate never gets
> below 49930.
How much RAM do you have on this machine? If the system is caching
a goodly fraction of the tables, it'd be appropriate to lower
random_page_cost (or increase effective_cache_size).
I do recall a thread awhile back to the effect that the planner
overestimates the cost of nestloop/indexscan plans because it doesn't
account for the fact that successive indexscans aren't independent ---
the top levels of the index btree, at least, are certain to remain
in cache from loop to loop. That seems unlikely to account for as
large an estimation error as you're showing here, though. Is there
anything nonrandom about your data statistics? (For example, could
it be that all the db rows matching a particular tmp0 row are physically
bunched together?)
regards, tom lane
joostje@komputilo.org writes:
> For example, for the stat.targ=500 run:
> => explain analyse SELECT id from db, tmp0 WHERE valida AND poseda='uea' AND tab='pers' AND tmp0.v0=id ;
> NOTICE: QUERY PLAN:
> Nested Loop (cost=0.00..121000.31 rows=28184 width=39) (actual time=1.05..23.24 rows=415 loops=1)
> -> Seq Scan on tmp0 (cost=0.00..20.00 rows=1000 width=32) (actual time=0.22..0.40 rows=29 loops=1)
^^^^^^^^^
> -> Index Scan using db_id_idx on db (cost=0.00..120.63 rows=28 width=7) (actual time=0.27..0.75 rows=14
loops=29)
> Total runtime: 23.92 msec
Actually, I see part of the problem: you haven't vacuumed
tmp0, so it's sitting at the default size estimate of 1000 rows.
That accounts for more than a factor of 30 in the estimation error
in the nestloop plan, while it wouldn't have nearly as much impact
on hash or mergejoin estimates.
There's still a good big error left to account for though :-(
I don't think you mentioned the other WHERE conditions before. Which
table are those restricting, and how selective are they?
regards, tom lane
On Thu, 10 Apr 2003 joostje@komputilo.org wrote: > Je 2003/04/10(4)/12:04, Tom Lane skribis: > > joostje@komputilo.org writes: > > > Unless I'm mistaken, pg_nstats.n_distinct should be (aproximately) the same as > > > count(distinct(id)), but it obviously isn't. Also the most_common_freqs > > > values are about a 100 times higher than in reality, and, even tough about > > > 900 values of id occur more often than 40 times, in the 'most_common_vals' > > > list are 7 (of the 10) vals that occur less than 40 times, and the real > > > top two isn't even represented. > > > > Please try increasing the statistics target (see ALTER TABLE) for db.id, then > > re-analyze and see if the estimates get better. The default setting is > > 10 --- try 20, 50, 100 to see what happens. > > Well, the n_distinct estimates get better, but the cost estimates still > don't quite add up: `actual cost' is 23.24, cost estimate never gets > below 49930. > > stat.targ n_distinct| correlation cost estimate > 5 1917 | 0.43189 3621794.92 > 10 1998 | 0.3909 3618363.33 > 20 4330 | -0.247617 1981594.38 > 50 9708 | 0.0762642 975847.15 > 100 14604 | 0.030706 657631.41 > 200 21855 | 0.0446929 204335.70 > 500 39980 | -0.0497829 121000.31 > 1000 29468 | 0.0366528 49930.08 > 1000 29453 | 0.0367673 49954.08 > Table 1: various estimates as a function of statistical target > actual distinct values: 42226 > actual cost: varies from 5.0 to 27.8 > > So, the planner still prefers the mergejoin and hashjoin plans, causing > the select to take tens of seconds (60 for the mergejoin, I beleve), wheras > the Nested Loop takes only 0.024 seconds: > > For example, for the stat.targ=500 run: > => explain analyse SELECT id from db, tmp0 WHERE valida AND poseda='uea' AND tab='pers' AND tmp0.v0=id ; > NOTICE: QUERY PLAN: > > Nested Loop (cost=0.00..121000.31 rows=28184 width=39) (actual time=1.05..23.24 rows=415 loops=1) > -> Seq Scan on tmp0 (cost=0.00..20.00 rows=1000 width=32) (actual time=0.22..0.40 rows=29 loops=1) > -> Index Scan using db_id_idx on db (cost=0.00..120.63 rows=28 width=7) (actual time=0.27..0.75 rows=14 loops=29) > Total runtime: 23.92 msec > > In the above example, tmp0 had 29 values, that correspond to 415 rows in table db. > Table db has 586157 rows. Just a thought: is tmp0 analyzed? (1000 rows vs 29). :) Wouldn't this divide cost estimate by at least 30? (ok... it's still high...). -- Antti Haapala
Je 2003/04/10(4)/16:04, Tom Lane skribis: > joostje@komputilo.org writes: > > For example, for the stat.targ=500 run: > > => explain analyse SELECT id from db, tmp0 WHERE valida AND poseda='uea' AND tab='pers' AND tmp0.v0=id ; > > NOTICE: QUERY PLAN: > > > Nested Loop (cost=0.00..121000.31 rows=28184 width=39) (actual time=1.05..23.24 rows=415 loops=1) > > -> Seq Scan on tmp0 (cost=0.00..20.00 rows=1000 width=32) (actual time=0.22..0.40 rows=29 loops=1) > ^^^^^^^^^ > > -> Index Scan using db_id_idx on db (cost=0.00..120.63 rows=28 width=7) (actual time=0.27..0.75 rows=14 loops=29) > > Total runtime: 23.92 msec > > Actually, I see part of the problem: you haven't vacuumed > tmp0, so it's sitting at the default size estimate of 1000 rows. > That accounts for more than a factor of 30 in the estimation error > in the nestloop plan, while it wouldn't have nearly as much impact > on hash or mergejoin estimates. > > There's still a good big error left to account for though :-( OK, here it goes: db.id.statistics target set to 10 (default); effective_cache_size=1000 (default); random_page_cost=4 (default); => estimated cost = 3690777.90 analyse tmp0; => estimated cost = 107033.27 set effective_cache_size=100000; => estimated cost = 107033.27 (no change there) set random_page_cost=1; (default was 4) => estimated cost = 27592.06 db.id.statistics target = 500; (improves n_distinct estimate from 2041 to 39909) => estimated cost = 943.44 set enable_nestloop = off; => planner elects Hash Loop, estimated/real cost: 52834.33 12762.86 set enable_hashjoin = off; => planner elects Merge Join, estimated/real cost: 179961.75/54314.09 So, it seems everything is working as it should now! Thanks! > I don't think you mentioned the other WHERE conditions before. Which > table are those restricting, and how selective are they? Ah, sorry, they are worth not mentioning, as db.poseda='uea' and db.tab='pers' and valida for about 97.6% of the rows. I guess I should have done the tests without the two conditions, as they have no influence. Thanks! joostje