Message-ID: <c5c7cf37-218d-405a-8dde-520aa313830a@gmail.com>
Date: Mon, 5 Jan 2026 09:54:17 +0100
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: Hash-based MCV matching for large IN-lists
To: Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>,
 PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
References: <7db341e0-fbc6-4ec5-922c-11fdafe7be12@tantorlabs.com>
Content-Language: en-US
From: David Geier <geidav.pg@gmail.com>
In-Reply-To: <7db341e0-fbc6-4ec5-922c-11fdafe7be12@tantorlabs.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Archived-At: <https://www.postgresql.org/message-id/c5c7cf37-218d-405a-8dde-520aa313830a%40gmail.com>
Precedence: bulk

Hi Ilia!

On 29.12.2025 21:35, Ilia Evdokimov wrote:
> Hi hackers,
> 
> When estimating selectivity for ScalarArrayOpExpr (IN, ANY, ALL) and MCV
> statistics are available for the column, the planner currently matches
> IN-list elements against the MCV array using nested loop. For large IN-
> list and large MCV arrays this results in O(N*M) behavior, which can
> become unnecessarily expensive during planning.
> 
> Thanks to David for pointing out this case [0]
> 

Cool that you tackled this. I've seen this happening a lot in practice.

> This patch introduces a hash-based matching path, analogous to what is
> already done for MCV matching in join selectivity estimation (057012b
> commit). Instead of linearly scanning the MCV array for each IN-list
> element, we build a hash table and probe it to identify matches.
> 
> The hash table is built over the MCV values, not over the IN-list. The
> IN-list may contain NULLs, non-Const expressions, and duplicate values,
> whereas the MCV list is guaranteed to contain distinct, non-NULL values
> and represents the statistically meaningful domain we are matching
> against. Hashing the MCVs therefore avoids duplicate work and directly
> supports selectivity estimation.

The downside of doing it this way is that we always pay the price of
building a possibly big hash table if the column has a lot of MCVs, even
for small IN lists. Why can't we build the hash table always on the
smaller list, like we do already in the join selectivity estimation?

For NULL we can add a flag to the hash entry, non-Const expressions must
anyways be evaluated and duplicate values will be discarded during insert.

> 
> For each IN-list element, if a matching MCV is found, we add the
> corresponding MCV frequency to the selectivity estimate. If no match is
> found, the remaining selectivity is estimated in the same way as the
> existing non-MCV path (similar to var_eq_const when the constant is not
> present in the MCV list).
> 

The code in master currently calls an operator-specific selectivity
estimation function. For equality this is typically eqsel() but the
function can be specified during CREATE OPERATOR.

Can be safely special-case the behavior of eqsel() for all possible
operators for the ScalarArrayOpExpr case?

> The hash-based path is enabled only when both a sufficiently large IN-
> list and an MCV list are present, and suitable hash functions exist for
> the equality operator. The threshold is currently the same as the one
> used for join MCV hashing, since the underlying algorithmic tradeoffs
> are similar.

Seems reasonable.

I'll test and review in more detail once we clarified the design.

--
David Geier