pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedAbysmal hash join
6+ messages / 3 participants
[nested] [flat]
* Abysmal hash join
@ 2006-09-11 13:48 Florian Weimer <fweimer@bfk.de>
0 siblings, 1 reply; 6+ messages in thread
From: Florian Weimer @ 2006-09-11 13:48 UTC (permalink / raw)
To: pgsql-performance
Hi,
for this simple join of two tables,
SELECT * FROM large_rel n, smaller_rel a
WHERE n.field_1 = a.field_2 AND a.key = '127.0.0.1';
PostgreSQL 8.1.4 chooses an extremely bad query plan:
Hash Join (cost=283.45..8269374.38 rows=14137 width=94)
Hash Cond: ("outer".field_1 = "inner".field_2)
-> Seq Scan on large_rel n (cost=0.00..6760690.04 rows=301651904 width=52)
-> Hash (cost=283.27..283.27 rows=74 width=42)
-> Bitmap Heap Scan on smaller_rel a (cost=2.26..283.27 rows=74 width=42)
Recheck Cond: (key = '127.0.0.1'::inet)
-> Bitmap Index Scan on smaller_rel_1_key (cost=0.00..2.26 rows=74 width=0)
Index Cond: (key = '127.0.0.1'::inet)
Note the sequential scan over the whole large_rel table (and the
corresponding row estimate is roughly correct).
If I turn off hash joins, I get this plan, which actually completes in
finite time:
Nested Loop (cost=2005.35..46955689.59 rows=14137 width=94) (actual time=0.325..0.678 rows=12 loops=1)
-> Bitmap Heap Scan on smaller_rel a (cost=2.26..283.27 rows=74 width=42) (actual time=0.132..0.133 rows=1 loops=1)
Recheck Cond: (key = '127.0.0.1'::inet)
-> Bitmap Index Scan on smaller_rel_1_key (cost=0.00..2.26 rows=74 width=0) (actual time=0.095..0.095 rows=1 loops=1)
Index Cond: (key = '127.0.0.1'::inet)
-> Bitmap Heap Scan on large_rel n (cost=2003.09..632110.78 rows=193739 width=52) (actual time=0.182..0.501 rows=12 loops=1)
Recheck Cond: (n.field_1 = "outer".field_2)
-> Bitmap Index Scan on large_rel_1_field_1 (cost=0.00..2003.09 rows=193739 width=0) (actual time=0.148..0.148 rows=12 loops=1)
Index Cond: (n.field_1 = "outer".field_2)
The row estimate for
SELECT * FROM smaller_rel a WHERE a.key = '127.0.0.1';
is somewhat off:
Bitmap Heap Scan on smaller_rel a (cost=2.26..283.27 rows=74 width=42) (actual time=0.134..0.135 rows=1 loops=1)
Recheck Cond: (key = '127.0.0.1'::inet)
-> Bitmap Index Scan on smaller_rel_1_key (cost=0.00..2.26 rows=74 width=0) (actual time=0.108..0.108 rows=1 loops=1)
Index Cond: (key = '127.0.0.1'::inet)
However, I can't believe that the hash join would be faster even if
there where 74 matching rows in smaller_rel instead of just one. The
estimate decreases when I increase the portion of smaller_rel which is
scanned by ANALYZE (to something like 10% of the table), but this
doesn't look like a solution.
Any suggestions?
(The queries have been pseudonzmized and may contain typos.)
--
Florian Weimer <fweimer@bfk.de>
BFK edv-consulting GmbH http://www.bfk.de/
Durlacher Allee 47 tel: +49-721-96201-1
D-76131 Karlsruhe fax: +49-721-96201-99
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Abysmal hash join
@ 2006-09-11 14:28 Tom Lane <tgl@sss.pgh.pa.us>
parent: Florian Weimer <fweimer@bfk.de>
0 siblings, 1 reply; 6+ messages in thread
From: Tom Lane @ 2006-09-11 14:28 UTC (permalink / raw)
To: Florian Weimer <fweimer@bfk.de>; +Cc: pgsql-performance
Florian Weimer <fweimer@bfk.de> writes:
> -> Bitmap Index Scan on large_rel_1_field_1 (cost=0.00..2003.09 rows=193739 width=0) (actual time=0.148..0.148 rows=12 loops=1)
> Index Cond: (n.field_1 = "outer".field_2)
What you need to look into is why that rowcount estimate is off by four
orders of magnitude.
The estimate on the smaller table is only off by a factor of 75 but
that's still pretty darn awful. Are the statistics up to date? Maybe
larger stats targets would help.
regards, tom lane
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Abysmal hash join
@ 2006-09-11 15:15 Florian Weimer <fweimer@bfk.de>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 6+ messages in thread
From: Florian Weimer @ 2006-09-11 15:15 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-performance
* Tom Lane:
> Florian Weimer <fweimer@bfk.de> writes:
>> -> Bitmap Index Scan on large_rel_1_field_1 (cost=0.00..2003.09 rows=193739 width=0) (actual time=0.148..0.148 rows=12 loops=1)
>> Index Cond: (n.field_1 = "outer".field_2)
>
> What you need to look into is why that rowcount estimate is off by four
> orders of magnitude.
Ah, thanks.
> The estimate on the smaller table is only off by a factor of 75 but
> that's still pretty darn awful. Are the statistics up to date?
Seems so. Running ANALYZE only increased the row estimate, instead of
decreasing it. 8-(
> Maybe larger stats targets would help.
I've set default_statistics_target to 100 and rerun ANALYZE on that
table. The estimate went down to 43108 (and the hash join is still
the preferred plan). ANALZE with default_statistics_target = 200
(which seems pretty large to me) is down to 26050 and the bitmap scan
plan is chosen.
PostgreSQL seems to think that there are only very few distinct values
for that column (with default_statistics_target = 100 and 200):
EXPLAIN SELECT DISTINCT field_1 FROM large_rel;
Unique (cost=82841534.37..84400982.21 rows=7235 width=24)
-> Sort (cost=82841534.37..83621258.29 rows=311889568 width=24)
Sort Key: field_1
-> Seq Scan on large_rel (cost=0.00..6863066.68 rows=311889568 width=24)
Unique (cost=82733282.28..84290654.92 rows=11957 width=24)
-> Sort (cost=82733282.28..83511968.60 rows=311474528 width=24)
Sort Key: field_1
-> Seq Scan on large_rel (cost=0.00..6858916.28 rows=311474528 width=24)
I don't know the exact value, but it's closer to a few millions. The
distribution is quite odd. A large sample of the column (10 million
rows) looks like this:
SELECT cnt, COUNT(*) FROM
(SELECT COUNT(*) AS cnt FROM
(SELECT field_1 FROM large_rel LIMIT 10000000) x GROUP BY field_1) y
GROUP BY cnt ORDER BY cnt;
cnt | count
--------+--------
1 | 258724
2 | 85685
3 | 46215
4 | 29333
5 | 20512
6 | 15276
7 | 11444
8 | 9021
[...]
59379 | 1
59850 | 1
111514 | 1
111783 | 1
111854 | 1
112259 | 1
112377 | 1
116379 | 1
116473 | 1
116681 | 1
Maybe I'm just screwed with such a distribution, but it's still rather
unfortunate.
--
Florian Weimer <fweimer@bfk.de>
BFK edv-consulting GmbH http://www.bfk.de/
Durlacher Allee 47 tel: +49-721-96201-1
D-76131 Karlsruhe fax: +49-721-96201-99
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Abysmal hash join
@ 2006-09-11 15:39 Tom Lane <tgl@sss.pgh.pa.us>
parent: Florian Weimer <fweimer@bfk.de>
0 siblings, 1 reply; 6+ messages in thread
From: Tom Lane @ 2006-09-11 15:39 UTC (permalink / raw)
To: Florian Weimer <fweimer@bfk.de>; +Cc: pgsql-performance
Florian Weimer <fweimer@bfk.de> writes:
>> Maybe larger stats targets would help.
> I've set default_statistics_target to 100 and rerun ANALYZE on that
> table. The estimate went down to 43108 (and the hash join is still
> the preferred plan). ANALZE with default_statistics_target = 200
> (which seems pretty large to me) is down to 26050 and the bitmap scan
> plan is chosen.
> PostgreSQL seems to think that there are only very few distinct values
> for that column (with default_statistics_target = 100 and 200):
Yeah, n_distinct estimation from a sample is inherently hard :-(. Given
that you have such a long tail on the distribution, it might be worth
your while to crank the stats target for that column all the way to the
maximum (1000). Also you need to experiment with extending the stats
for the smaller table.
I believe what's happening here is that the smaller table joins only to
less-frequent entries in the big table (correct?). The hash join would
be appropriate if there were many rows joining to the very-frequent
entries, and the problem for the planner is to determine that that's not
so. Given enough stats on the two joining columns, it should be able to
determine that.
Of course, large stats targets will slow down planning to some extent,
so you should also keep an eye on how long it takes to plan the query.
regards, tom lane
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Abysmal hash join
@ 2006-09-11 16:28 Florian Weimer <fweimer@bfk.de>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 6+ messages in thread
From: Florian Weimer @ 2006-09-11 16:28 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-performance
* Tom Lane:
> Yeah, n_distinct estimation from a sample is inherently hard :-(. Given
> that you have such a long tail on the distribution, it might be worth
> your while to crank the stats target for that column all the way to the
> maximum (1000).
I've done that. Fortunately, ANALYZE time didn't increase by that
much, compared to the default (by just a factor of 10). The bitmap
scan estimate is still way off (around 8000), but let's hope that it
won't matter in practice.
> Also you need to experiment with extending the stats for the smaller
> table.
Yeah, the situation is quite similar, but on a much smaller scale.
> I believe what's happening here is that the smaller table joins only to
> less-frequent entries in the big table (correct?).
Almost. We won't select the rows based on these values, at least not
in queries of that type. The reason is simply that the result set is
too large to be useful.
> Of course, large stats targets will slow down planning to some extent,
> so you should also keep an eye on how long it takes to plan the query.
These queries are mostly ad-hoc, so a delay of a couple of seconds
doesn't matter. Only if you need to wait five minutes, it's a
different story.
It seems that the situation is under control now. Thanks.
--
Florian Weimer <fweimer@bfk.de>
BFK edv-consulting GmbH http://www.bfk.de/
Durlacher Allee 47 tel: +49-721-96201-1
D-76131 Karlsruhe fax: +49-721-96201-99
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: Abysmal hash join
@ 2006-09-12 00:56 Gregory Stark <gsstark@mit.edu>
parent: Florian Weimer <fweimer@bfk.de>
0 siblings, 0 replies; 6+ messages in thread
From: Gregory Stark @ 2006-09-12 00:56 UTC (permalink / raw)
To: Florian Weimer <fweimer@bfk.de>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; pgsql-performance
Florian Weimer <fweimer@bfk.de> writes:
> I've done that. Fortunately, ANALYZE time didn't increase by that
> much, compared to the default (by just a factor of 10).
With really high stats times you also have to keep an eye on planning time.
The extra data in the stats table can cause planning to take longer.
--
greg
^ permalink raw reply [nested|flat] 6+ messages in thread
end of thread, other threads:[~2006-09-12 00:56 UTC | newest]
Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2006-09-11 13:48 Abysmal hash join Florian Weimer <fweimer@bfk.de>
2006-09-11 14:28 ` Tom Lane <tgl@sss.pgh.pa.us>
2006-09-11 15:15 ` Florian Weimer <fweimer@bfk.de>
2006-09-11 15:39 ` Tom Lane <tgl@sss.pgh.pa.us>
2006-09-11 16:28 ` Florian Weimer <fweimer@bfk.de>
2006-09-12 00:56 ` Gregory Stark <gsstark@mit.edu>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox