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

Started by Alexey Bashtanovabout 9 years ago2 messageshackers
Beta feature

Hackorum builds and tests every patch posted to the lists, not only commitfest submissions. This is Hackorum's own CI rather than the PostgreSQL project's, and it is still under testing - please report anything that looks wrong.

won't retrysuccessCI history

You can run a PostgreSQL built from this patch straight from Docker, with no checkout and no build:

docker run --rm -p 5432:5432 ghcr.io/hackorum-dev/postgres-patch:t37150
psql -h localhost -U postgres

Built from patchset v1 (message #1), July 28, 2026 at 05:45 AM.

Every patchset is also pushed to a branch of our PostgreSQL fork, so you can check out the same tree CI built. Without a PostgreSQL checkout:

git clone --branch t37150_1 https://github.com/hackorum-dev/postgres.git

In a checkout you already have, add the fork once:

git remote add hackorum https://github.com/hackorum-dev/postgres.git

then, for this patchset and every later one:

git fetch hackorum t37150_1 && git checkout t37150_1

Patchset v1 (message #1) is on t37150_1

Jump to latest
#1Alexey Bashtanov
bashtanov@imap.cc

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

Attachments:

t37150_1
join-card-est.patchtext/x-patch; name=join-card-est.patchDownload+13-9
join-card-est.sqlapplication/sql; name=join-card-est.sqlDownload
join-card-est.resulttext/plain; charset=UTF-8; name=join-card-est.resultDownload
#2Tom Lane
tgl@sss.pgh.pa.us
In reply to: Alexey Bashtanov (#1)
Re: estimation for join results cardinality is sometimes more than the product of the downstream nodes'

Alexey Bashtanov <bashtanov@imap.cc> writes:

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?

Because that would be giving an unfair advantage to some paths over
others based on nothing except estimation errors. I do not think we'd
get a net benefit in plan quality.

If we could do this earlier and adjust the join relation's overall
cardinality estimate, it might be something to consider.

regards, tom lane

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers