Thread: Bogus nestloop join estimate, ignores WHERE clause
Hi list! I'm getting really surprising planner estimates for a query that's joining another table via a varchar field. All of this was tested on PostgreSQL 8.4.8, 9.0.4 and 9.1rc1. The original query is pretty huge, but I managed to shrink it down to this: SELECT * FROM email_message where email_message.id_code IN (SELECT id_code FROM client WHERE client_id='83509'); * id_code is an indexed varchar(20) NOT NULL column in both tables * client_id is the primary key of client. * There are 149152 rows in email_message and 140975 rows in client * The most common value in both sides of the join is an empty string. 121970 in email_message and 10753 in client (Turning the empty values into NULLs helps a little, but still gives bad estimates) This is the plan I get: EXPLAIN SELECT * FROM email_message where email_message.id_code IN (SELECT id_code FROM client WHERE client_id='83509');Nested Loop (cost=8.28..36.86 rows=139542 width=101) -> HashAggregate (cost=8.28..8.29 rows=1 width=11) -> Index Scan using client_pkey on client (cost=0.00..8.28 rows=1 width=11) Index Cond: (client_id = 83509) -> Index Scan using email_message_id_code_idx on email_message (cost=0.00..28.05 rows=41 width=101) Index Cond: ((email_message.id_code)::text = (client.id_code)::text) (6 rows) This nestloop couldn't possibly generate 139542 rows since the inner plan is expected to return 1 row and the outer plan 41 After a bit of digging, I figured out that it uses the same estimate as a semi-join WITHOUT the client_id restriction. EXPLAIN SELECT * FROM email_message m WHERE EXISTS(SELECT * FROM client c WHERE m.id_code=c.id_code);Nested Loop Semi Join (cost=0.00..7725.31 rows=139542 width=101) -> Seq Scan on email_messagem (cost=0.00..3966.52 rows=149152 width=101) -> Index Scan using client_id_code_idx1 on client c (cost=0.00..0.39 rows=1 width=11) Index Cond: ((c.id_code)::text = (m.id_code)::text) For whatever reason, the 1st query completely ignores the fact that the client_id clause reduces the result count by a large factor. So I turned this into a simple JOIN and I'm still seeing bad estimates: EXPLAIN SELECT * FROM email_message JOIN client USING (id_code) WHERE client_id='83509';Nested Loop (cost=0.00..36.85 rows=9396 width=252) -> Index Scan using client_pkey on client (cost=0.00..8.28rows=1 width=162) Index Cond: (client_id = 83509) -> Index Scan using email_message_id_code_idx on email_message (cost=0.00..28.05 rows=41 width=101) Index Cond: ((email_message.id_code)::text = (client.id_code)::text) This is better, but still overestimates massively. When I change empty values to NULLs, then this JOIN query starts estimating correctly. So this one is probably confused because the empty values would result in a cartesian join. Are there any reasons why nestloop can't use the known (1 * 41) as its estimate? Regards, Marti Raudsepp voicecom.ee
On ons, 2011-08-31 at 15:38 +0300, Marti Raudsepp wrote: > I'm getting really surprising planner estimates for a query that's > joining another table via a varchar field. All of this was tested on > PostgreSQL 8.4.8, 9.0.4 and 9.1rc1. By any chance, did it work better in 8.4.7?
On Wed, Aug 31, 2011 at 16:34, Peter Eisentraut <peter_e@gmx.net> wrote: > On ons, 2011-08-31 at 15:38 +0300, Marti Raudsepp wrote: >> I'm getting really surprising planner estimates for a query that's >> joining another table via a varchar field. All of this was tested on >> PostgreSQL 8.4.8, 9.0.4 and 9.1rc1. > > By any chance, did it work better in 8.4.7? No. Estimates on 8.4.7 are pretty much the same (139820, 139820 and 9455) (I built and installed 8.4.7 with a clean database) Regards, Marti Raudsepp voicecom.ee
Marti Raudsepp <marti@juffo.org> writes: > After a bit of digging, I figured out that it uses the same estimate > as a semi-join WITHOUT the client_id restriction. > ... > For whatever reason, the 1st query completely ignores the fact that > the client_id clause reduces the result count by a large factor. Could we see the pg_stats rows for the two join columns? regards, tom lane
Marti Raudsepp <marti@juffo.org> writes: > On Wed, Aug 31, 2011 at 23:59, Tom Lane <tgl@sss.pgh.pa.us> wrote: >> Could we see the pg_stats rows for the two join columns? > Sure, but I don't want to send this out to the public list since > [ it's private data ] Thanks for the data. I set up a comparable test case and duplicated your problem. It looks like it is a variant of the same brain fade being discussed over in pgsql-performance, http://archives.postgresql.org/pgsql-performance/2011-08/msg00327.php In your case, we are running through the branch of eqjoinsel_semi that does have MCVs to play with, and that code path is effectively not taking any account at all of restrictions applied to the inner relation. We need to have it clamp nd2 (and not nd1) along the same lines as should be happening in the no-MCV-list code path. This is exactly the case I was thinking needed to be covered when I was responding to Mark, and now I've got an example to prove it. In this particular case, the estimate is probably still not going to be that good, because you have so many empty-string keys that that one value dominates the result. The only way for the planner to get a real quality estimate would be for it to know whether or not the specific value of client_id mapped to an empty-string id_code, which would require cross-column stats that we haven't got. Things would get better if you were willing to replace the empty strings with nulls, which the planner would know couldn't match. But I'm not sure if that is the semantics you need. In any case, the eqjoinsel_semi logic is broken; will fix. regards, tom lane