From: Tom Lane <tgl@sss.pgh.pa.us>
To: pgsql-committers@lists.postgresql.org
Subject: pgsql: Speed up eqjoinsel() with lots of MCV entries.
Date: Wed, 19 Nov 2025 18:22:23 +0000
Message-ID: <E1vLmow-000Kte-2i@gemulon.postgresql.org> (raw)
Speed up eqjoinsel() with lots of MCV entries.
If both sides of the operator have most-common-value statistics,
eqjoinsel wants to check which MCVs have matches on the other side.
Formerly it did this with a dumb compare-all-the-entries loop,
which had O(N^2) behavior for long MCV lists. When that code was
written, twenty-plus years ago, that seemed tolerable; but nowadays
people frequently use much larger statistics targets, so that the
O(N^2) behavior can hurt quite a bit.
To add insult to injury, when asked for semijoin semantics, the
entire comparison loop was done over, even though we frequently
know that it will yield exactly the same results.
To improve matters, switch to using a hash table to perform the
matching. Testing suggests that depending on the data type, we may
need up to about 100 MCVs on each side to amortize the extra costs
of setting up the hash table and performing hash-value computations;
so continue to use the old looping method when there are fewer MCVs
than that.
Also, refactor so that we don't repeat the matching work unless
we really need to, which occurs only in the uncommon case where
eqjoinsel_semi decides to truncate the set of inner MCVs it
considers. The refactoring also got rid of the need to use the
presented operator's commutator. Real-world operators that are
using eqjoinsel should pretty much always have commutators, but
at the very least this saves a few syscache lookups.
Author: Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>
Co-authored-by: David Geier <geidav.pg@gmail.com>
Reviewed-by: Tom Lane <tgl@sss.pgh.pa.us>
Discussion: https://postgr.es/m/20ea8bf5-3569-4e46-92ef-ebb2666debf6@tantorlabs.com
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/057012b205a082ec930cd7bb7f6663516be011e2
Modified Files
--------------
src/backend/utils/adt/selfuncs.c | 554 ++++++++++++++++++++++++++++++---------
src/tools/pgindent/typedefs.list | 3 +
2 files changed, 436 insertions(+), 121 deletions(-)
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-committers@postgresql.org
Cc: tgl@sss.pgh.pa.us, pgsql-committers@lists.postgresql.org
Subject: Re: pgsql: Speed up eqjoinsel() with lots of MCV entries.
In-Reply-To: <E1vLmow-000Kte-2i@gemulon.postgresql.org>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
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