Re: Hash-based MCV matching for large IN-lists

Hi David!

Thanks for feedback.

On 05.01.2026 11:54, David Geier wrote:
>> 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.

After thinking more about this I realized that this is actually a better
match for how selectivity is currently modeled. After this comments in
master

         * If we were being really tense we would try to confirm that the
         * elements are all distinct, but that would be expensive and it
         * doesn't seem to be worth the cycles; it would amount to
penalizing
         * well-written queries in favor of poorly-written ones.
However, we
         * do protect ourselves a little bit by checking whether the
         * disjointness assumption leads to an impossible (out of range)
         * probability; if so, we fall back to the normal calculation.

when the hash table is built on the IN-list, duplicate IN-list values
are automatically eliminated during insertion, so we no longer risk
summing the same MCV frequency multiple times. This makes the
disjoint-probability estimate more robust and in practice slightly more
accurate.

One thing I initially missed that there are actually three different
places where ScalarArrayOpExpr is handled - the Const array case, the
ArrayExpr case and others - and Const and ArrayExpr require different
implementation of the same idea. In Const case we can directly hash and
probe Datum value, while ArrayExpr case we must work on Node* element,
separating constant and non-constant entries and only hashing the
constants. The current v2 therefore applies the same MCV-hash
optimization in both branches, but using two tailored code paths that
preserve the existing semantics of how non-Const elements are handled by
var_eq_non_const().

If the MCV list is smaller than the IN-list, the behavior is the same as
in v1 of the patch. If the IN-list is smaller, we instead build a hash
table over the distinct constant elements of the IN-list and then:
- Scan the MCV list and sum the frequencies of those MCVs that appear in
the IN-list;
- Count how many distinct IN-list not null constant elements are not
present in the MCV list;
- Estimate the probability of each such non-MCV value using the
remaining frequency mass;
- Handle non-constant IN-list elements separately using
var_eq_non_const(), exactly as in the existing implementation.

>> 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?

Unfortunately there is no safe way to make this optimization generic for
arbitrary restrict functions, because a custom RESTRICT function does
not have to use MCVs at all. IMO, in practice the vast majority of
ScalarArrayOpExpr uses with = or <> rely on the built-in equality
operators whose selectivity is computed by eqsel()/neqsel(), so I
limited this optimization to those cases.

I’ve attached v2 of the patch. It currently uses two fairly large helper
functions for the Const and ArrayExpr cases; this is intentional to keep
the logic explicit and reviewable, even though these will likely need
refactoring or consolidation later.

--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/