estimation for join results cardinality is sometimes more than the product of the downstream nodes'

From: Alexey Bashtanov <bashtanov(at)imap(dot)cc>
To: pgsql-hackers(at)postgresql(dot)org
Subject: estimation for join results cardinality is sometimes more than the product of the downstream nodes'
Date: 2017-07-25 13:12:41
Message-ID: 59534fb9-50b0-1447-6b70-e128529ec8ba@imap.cc
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Hello,

Postgres can produce a plan with a nested loop node having rows estimate
much more than the product of underlying nodes' estimates, relying only
on outer relation size:

alexey=# explain
SELECT oid, relname
FROM (
SELECT m.oid, m.relname
FROM pg_class m
UNION ALL
SELECT m.oid, m.relname
FROM pg_class m
) m
WHERE oid IN (VALUES (162456317), (162456310));
QUERY PLAN
----------------------------------------------------------------------------------------------------
Nested Loop (cost=0.31..33.24 rows=*341* width=68)
-> Unique (cost=0.04..0.04 rows=*2* width=4)
-> Sort (cost=0.04..0.04 rows=2 width=4)
Sort Key: (("*VALUES*".column1)::oid)
-> Values Scan on "*VALUES*" (cost=0.00..0.03 rows=2
width=4)
-> Append (cost=0.27..16.58 rows=*2* width=68)
-> Index Scan using pg_class_oid_index on pg_class m
(cost=0.27..8.29 rows=1 width=68)
Index Cond: (oid = ("*VALUES*".column1)::oid)
-> Index Scan using pg_class_oid_index on pg_class m_1
(cost=0.27..8.29 rows=1 width=68)
Index Cond: (oid = ("*VALUES*".column1)::oid)
(10 rows)

Why?
Is there a reason that join cardinality estimates are not limited by the
product of the joined parts cardinalities like in the
join-card-est.patch attached?
An example of a query working faster as a result of this change is in
join-card-est.sql, result is in join-card-est.result

Best Regards,
Alexey

Attachment Content-Type Size
join-card-est.patch text/x-patch 1.3 KB
join-card-est.sql application/sql 773 bytes
join-card-est.result text/plain 4.3 KB

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2017-07-25 14:13:47 Re: cache lookup failed error for partition key with custom opclass
Previous Message Amit Kapila 2017-07-25 12:58:27 Re: pl/perl extension fails on Windows