Horton
Menu

Thread

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Short-circuit row estimation in NOT IN containing NULL consts

  1. Hash-based MCV matching for large IN-lists

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2025-12-29T20:35:43Z

    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]

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.

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

Example:

CREATE TABLE t (x int);
INSERT INTO t SELECT x % 10000 FROM generate_series(1, 3000000) x;
ALTER TABLE t ALTER COLUMN x SET STATISTICS 10000;
ANALYZE t;

Before patch:
EXPLAIN (SUMMARY) SELECT * FROM t WHERE x IN (1,2,...,2000);
Seq Scan on t  (cost=5.00..58280.00 rows=600000 width=4)
    Filter: (x = ANY ('{1,2,...,2000}'::integer[]))
* Planning Time: 57.137 ms*
(3 rows)

After patch:
EXPLAIN (SUMMARY) SELECT * FROM t WHERE x IN (1,2,...,2000);
Seq Scan on t  (cost=5.00..58280.00 rows=600000 width=4)
    Filter: (x = ANY ('{1,2,...,2000}'::integer[]))
* Planning Time: 0.558 ms*
(3 rows)

Comments, suggestions, and alternative approaches are welcome!

[0]: 
https://www.postgresql.org/message-id/b6316b99-565b-4c89-aa08-6aea51f54526%40gmail.com

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

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

    David Geier <geidav.pg@gmail.com> — 2026-01-05T08:54:17Z

    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

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

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-01-14T10:19:36Z

    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/

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

    David Geier <geidav.pg@gmail.com> — 2026-01-19T14:01:07Z

    On 14.01.2026 11:19, Ilia Evdokimov wrote:
> 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.

Does that mean that we get a different estimation result, depending on
if the IN list is smaller or not? I think we should avoid that because
estimation quality might flip for the user unexpectedly.

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

Is this to make sure we keep getting the same estimation result if the
IN list is smaller and contains duplicates?

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

OK

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

How did you do that? I cannot find the code that checks for that.

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

Beyond that, it seems like you can also combine/reuse a bunch of code
for creating the hash map on the IN vs on the MCV list.

For the MCVs, can't we reuse some code from the eqjoinsel() optimization
we did? The entry and context structs look similar enough to only need one.

Making the code more compact would ease reviewing a lot.

--
David Geier

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

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-01-27T15:43:00Z

    Hi,

On 19.01.2026 17:01, David Geier wrote:
> Does that mean that we get a different estimation result, depending on
> if the IN list is smaller or not? I think we should avoid that because
> estimation quality might flip for the user unexpectedly.

I think you're right.

To address this, I changed the hash-table entry to track an additional 
'count' filed, representing how many times a particular value appears on 
the hashed side. When inserting into the hash table, if the value is 
already present, I increment 'count', otherwise, I create a new entry 
with count = 1


>>> 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.
> How did you do that? I cannot find the code that checks for that.

In scalararraysel(), before attempting the hash-based path, we determine 
whether the operator behaves like equality or inequality based on its 
selectivity function:

if (oprsel == F_EQSEL || oprsel == F_EQJOINSEL)
     isEquality = true;
else if (oprsel == F_NEQSEL || oprsel == F_NEQJOINSEL)
     isInequality = true;

Then the hash-based MCV matching is only attempted under:

if ((isEquality || isInequality) && !is_join_clause)

So effectively this restricts the optimization to operators whose 
selectivity is computed by eqsel()/neqsel() on restriction clauses. Join 
clauses (which would use eqjoinsel/neqjoinsel) are excluded via 
!is_join_clause


> For the MCVs, can't we reuse some code from the eqjoinsel() optimization
> we did? The entry and context structs look similar enough to only need one.

I considered reusing pieces from the eqjoinsel() , but in practice it 
turned out to be difficult to share code cleanly. Also, when looking at 
this file more broadly, we already have multiple places that reimplement 
similar pattern.


> Making the code more compact would ease reviewing a lot.

Agreed — I also think making the code more compact would significantly 
ease reviewing. I’ve found a way to unify the Const-array and ArrayExpr 
cases: in the ArrayExpr path, we can first construct the same arrays as 
in the Const-array case (elem_values, elem_nulls), and additionally 
build a boolean array elem_const[] indicating whether each element is a 
Const. Then the hash-based MCV matching function can:

- Ignore NULL and non-Const elements when building and probing the hash 
table.
- Count how many non-Const elements are present.
- After MCV and non-MCV constant handling, account for non-Const 
elements separately using var_eq_non_const() and fold their 
probabilities into the same ANY/ALL accumulation logic.

I've attached v3 patch with it.

To validate the same estimation results, I temporarily kept both 
implementations (hash-based and nested-loop) and compared their 
resulting selectivity values. Whenever they differed, I logged it. I ran 
regression tests and some local workload testing with this check 
enabled, and did not observe any mismatches. I attached patch with this 
logging.

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

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

    Chengpeng Yan <chengpeng_yan@outlook.com> — 2026-01-28T13:08:36Z

    
> On Jan 14, 2026, at 18:19, Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> wrote:
> 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.

Thanks for working on this.

I had previously reviewed the v2 patch and wrote up some comments, but
didn’t get a chance to send them before v3 was posted. I haven’t yet had
time to review v3 in detail, so I’m not sure whether the issues below
have already been addressed there. I’m posting my earlier review notes
first and will follow up with comments on v3 once I’ve had a chance to
look at it.

* Treat NULL array elements as zero selectivity for ALL:

In `scalararray_mcv_hash_match_const()` (and similarly
`scalararray_mcv_hash_match_expr()`), NULL array elements are currently
handled by simply continuing the loop (e.g. `if (elem_nulls[i])
continue;`), effectively ignoring them.

This behavior is only correct for ANY/OR semantics. For ALL/AND (`useOr
= false`), a single NULL array element causes the `ScalarArrayOpExpr` to
never return TRUE for strict operators (as assumed by the surrounding
code and comments). In that case, the correct selectivity estimate
should be 0.0, but the current code path can return a non-zero
selectivity.


* Fix cross-type equality argument order in `mcvs_in_equal`:

`mcvs_in_equal()` always invokes the equality function as `(key0,
key1)`. However, `simplehash` provides `key0` from the hash table and
`key1` as the probe key.

In the branch where the hash table is built over IN-list values and
probed with MCVs (the `sslot.nvalues > num_elems` path), this reverses
the operator’s argument order for cross-type equality operators. This
risks incorrect match decisions and may misinterpret Datums compared to
the operator’s declared signature.


* Include non-MCV IN-list constants in non-disjoint selectivity:

In the `sslot.nvalues > num_elems` path of
`scalararray_mcv_hash_match_const()` and
`scalararray_mcv_hash_match_expr()`, non-MCV constant elements currently
only contribute via `disjoint_sel`.

For cases where disjoint-probability estimation is not used (e.g. ALL,
`<> ANY`, or when `disjoint_sel` is out of range), the code leaves the
selectivity based solely on MCV matches. This effectively treats non-MCV
constants as having probability 1.0, leading to overestimation of
selectivity.


* Avoid double-negating inequality estimates for non-Const elements:

In the `scalararray_mcv_hash_match_expr()` `sslot.nvalues > num_elems`
branch, non-Const elements are handled via

`var_eq_non_const(..., negate = isInequality)`

and then later adjusted again with

`if (isInequality)
s1 = 1.0 - s1 - nullfrac;`

This results in a double negation for inequality cases, effectively
turning the estimate back into an equality selectivity.

--
Best regards,
Chengpeng Yan

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

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-01-29T11:14:43Z

    Hi Chengpeng,

Thanks for your review!


On 28.01.2026 16:08, Chengpeng Yan wrote:
> * Treat NULL array elements as zero selectivity for ALL:

Agreed. For ALL/AND semantics the function now returns selectivity = 0.0 
as soon as a NULL element is encountered.


> * Fix cross-type equality argument order in `mcvs_in_equal`:

Agreed. Added 'op_is_reserved' flag MCVInHashContext, same as in 
MCVHashContext.


> * Include non-MCV IN-list constants in non-disjoint selectivity:

This is not applicable to v3.


> * Avoid double-negating inequality estimates for non-Const elements:

Agreed. var_eq_non_const() is now always with negate = false, not to 
call negation twice.


Attached v4 patch with above fixes.

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

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

    David Geier <geidav.pg@gmail.com> — 2026-02-02T09:29:16Z

    Hi!

> Attached v4 patch with above fixes.

Good progress!

I did another pass over the code, focusing on structure:

- MCVHasContext and MCVInHashContext are identical. MCVHashEntry and
MCVInHashEntry only differ by the count member. I would, as said before,
merge them and simply not use the count member for the join case.

- hash_mcv_in() and mcvs_in_equal() are identical to hash_mcv() and
mcvs_equal(). Let's remove the new functions and use the existing ones
instead, in the spirit of the previous point.

- The threshold constants are also identical. I would merge them into a
single, e.g. MCV_HASH_THRESHOLD, in the spirit of the previous two points.

- MCVHashTable_hash will then be interchangable with
MCVInHashTable_hash. So let's remove MCVInHashTable_hash, in the spirit
of the previous three points.

- Use palloc_array() instead of palloc() when allocating arrays.

- We can avoid allocating the all-true elem_const array by passing NULL
for elem_const to scalararray_mcv_hash_match(), and considering a NULL
pointer to mean "all elements are constant".

- The following comment got copy&pasted from eqsel_internal() twice. It
reads a little strange now because we're not punting here by immediately
returning like in eqsel_internal() but instead fallback to the original
code path. Maybe say instead "... falling back to default code path to
compute default selectivity" or something like that.
	/*
	 * If expression is not variable = something or something =
	 * variable, then punt and return a default estimate.
	 */

- The call to fmgr_info(opfuncoid, &eqproc) is currently under have_mcvs
but can be moved into the next if.

- elem_nulls and elem_const does have to be 0-initialized via palloc0().
All elements are set in the subsequent for-loop. I believe elem_values
also doesn't have to be 0-initialized via palloc0().

- Have you checked there there's test coverage for the special cases
(nvalues_non_mcv > 0, nvalues_nonconst > 0, IN contains NULL,
isEnequality==true, etc.)?  If not let's add tests for these.


I'll do a 2nd iteration, focusing on correctness, once these comments
are addressed and I've got the SQL from you so that I can test the
corner cases manually.

--
David Geier

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

    Tatsuya Kawata <kawatatatsuya0913@gmail.com> — 2026-02-07T07:42:01Z

    Hi,

Thank you for this patch.
I've been studying how PostgreSQL handles selectivity estimation, and this
optimization for large IN-lists looks very useful.

I ran some tests for the special cases David mentioned:

- NULL + ALL: correctly returns selectivity ≈ 0 (rows=1)
- isInequality: <> ALL estimates match NOT IN
- Cross-type: int = ANY(bigint[]) works correctly
- Duplicate values: IN (1,1,1,2,2,3) preserves existing behavior

I noticed a few minor points:

1. The comment in MCVInHashEntry struct contains a typo:
   "number of occurrences od current value" -> "of"

2. The ALL + NULL early-return logic appears in two places (lines 2579-2591
and 2644-2656). I initially considered consolidating this by checking for
NULL elements before building the hash table, but realized this would add
an extra loop in the common case where there are no NULLs.
   Perhaps a brief comment explaining why this check is duplicated (to
avoid the overhead of a separate NULL-scanning loop) would help future
readers understand the design choice?

3. Minor style suggestion: adding a brief SQL example in the header comment
(e.g., "WHERE x IN (1,2,3,...)" or "WHERE x = ANY(ARRAY[...])") might help
future readers quickly understand the use case.

Thanks again for working on this optimization. It's been very educational
to follow the discussion and understand how selectivity estimation works in
PostgreSQL.

Regards,
Tatsuya Kawata

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

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-02-18T12:48:36Z

    I've fixed all the comments raised above and updated the v5 patch.


On 2/7/26 10:42, Tatsuya Kawata wrote:
> I initially considered consolidating this by checking for NULL 
> elements before building the hash table, but realized this would add 
> an extra loop in the common case where there are no NULLs.

Thanks for that suggestion. We can check for NULL elements without an 
explicit loop by using memchr(), so there's no need for an additional 
building of hash table. I'll update patch with it.

That said, I think it might be better to continue this small 
optimization with NULL for constant arrays separately in another thread. 
It's cleaner to split this work into smaller, focused changes rather 
than mixing everything into single patch


If anything is still unclear in the code or insufficiently documented, 
or if you have other suggestions, please do not hesitate to point them out.

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

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

    David Geier <geidav.pg@gmail.com> — 2026-02-23T09:21:00Z

    > That said, I think it might be better to continue this small
> optimization with NULL for constant arrays separately in another thread.
> It's cleaner to split this work into smaller, focused changes rather
> than mixing everything into single patch

Given that there's now a new thread about this, let's either remove it
from this patch and make sure we rebase correctly once the other patch
is merged, or use the latest version from this patch (ARR_HASNULL()
instead of memchr()).

> If anything is still unclear in the code or insufficiently documented,
> or if you have other suggestions, please do not hesitate to point them out.

- Currently we bail for unique Vars, via the following line.
var_eq_const() returns 1.0 / vardata->rel->tuples in that case. How
about we improve this case as well and, either, return
number_of_in_elements / vardata->rel->tuples, or fill the hash map and
then return number_of_unique_in_elements / vardata->rel->tuples. In
master this code is currently O(n). We could make it O(1) and keep the
today's semantics (count duplicates), or keep it O(n) but improve it by
not counting duplicates.

  if (vardata->isunique && vardata->rel && vardata->rel->tuples >= 1.0)
      return -1.0;

- How about factoring out the shared code from accum_scalararray_prob()
which is also used in the original estimation implementation? That would
get rid of some code duplication. Not sure how nice the code will get
though.

- The comment starting with the following line seems to have unintended
line breaks in various places (between the enumeration items):

  Build arrays describing ARRAY[] elements:

- No need to use palloc0_array() for elem_values as all elements are
initialized anyways.

- Use lfirst_node() and castNode() instead of C type casts.

- Add a comment to the following line where you bail because an element
is NULL for the NOT IN case.

  if (!useOr && elem_nulls[i])

- You can use foreach_current_index(). Then you don't need to declare
and update your own loop counter.

The rest looks good to me.

--
David Geier

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

    Matheus Alcantara <matheusssilv97@gmail.com> — 2026-02-24T19:32:15Z

    Hi, thanks for working on this!

On Wed Feb 18, 2026 at 9:48 AM -03, Ilia Evdokimov wrote:
> I've fixed all the comments raised above and updated the v5 patch.
>

Here are some comments regarding v5 patch:

On scalararraysel() we have:

+				ReleaseVariableStats(vardata);
+
+				if (s1 >= 0.0)
+					return s1;

I'm wondering if we also should call ReleaseVariableStats() on the early
return?

+					if (!useOr && elem_nulls[i])
+					{
+						pfree(elem_values);
+						pfree(elem_nulls);
+						pfree(elem_const);
+
+						return (Selectivity) 0.0;
+					}

------------------

On scalararray_mcv_hash_match() free_attstatsslot() is called only on
if (have_mcvs && OidIsValid(hashLeft) && OidIsValid(hashRight)),
perhaps it should be moved outside the if condition?

+	if (have_mcvs && OidIsValid(hashLeft) && OidIsValid(hashRight))
+	{
+       ...

+		MCVHashTable_destroy(hashTable);
+		free_attstatsslot(&sslot);
+	}
+
+	return selec;


------------------

typo: "all elements are const"

+ *              array is NULL if all elemnets is const.

------------------

It's worth adding on scalararray_mcv_hash_match() an early return when
num_elems == 0? I imagine that this can happens, e.g "WHERE a =
ANY(array[]::int[]);". In this case the function should still execute
completely?

--
Matheus Alcantara
EDB: https://www.enterprisedb.com

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

    Zsolt Parragi <zsolt.parragi@percona.com> — 2026-02-25T21:39:05Z

    Hello

+ hashContext.hash_fcinfo = hash_fcinfo;
+ hashContext.op_is_reversed = !hash_mcv;
+ hashContext.insert_mode = true;

Are you sure about op_is_reversed, isn't it backwards, shouldn't it be
= hash_mcv instead?

See the following testcase:

CREATE TABLE test_cross_type_bug (val float4);

INSERT INTO test_cross_type_bug
    SELECT v
      FROM generate_series(1, 200) AS v,
           generate_series(1, 50);

ALTER TABLE test_cross_type_bug ALTER COLUMN val SET STATISTICS 200;
ANALYZE test_cross_type_bug;

SELECT string_agg(v::text, ', ') AS in_list
  FROM generate_series(1, 200) AS gs(v) \gset

EXPLAIN SELECT * FROM test_cross_type_bug
 WHERE val = ANY(ARRAY[:in_list]::float4[]);

EXPLAIN SELECT * FROM test_cross_type_bug
 WHERE val = ANY(ARRAY[:in_list]::float8[]);

DROP TABLE test_cross_type_bug;

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

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-02-25T22:45:44Z

    I've addressed the review comments mentioned above.

David made a very good observation: for unique columns, where each 
iteration effectively returns the same per-element selectivity, there is 
no need to iterate at all. In such cases we can reduce the computation 
to a closed-form expression, i.e. O(1) instead of running the loop O(N).

I applied this idea to unique columns and cases falling back to 
DEFAULT_EQ_SEL. In both cases the loop can be replaced with a 
closed-from formula implemented in calculate_combined_selectivity(). The 
formula mirros the existing independent/disjoint probability model: ANY 
(sel = 1 - (1 - s) ^ length or length * s ), ALL (sel = s ^ length or 1 
- length*(1 - s)). It would be good to carefully review that this is 
fully equivalent to the current accumulation logic.

I also exprimented with applying the same idea to elements that are not 
found in MCV, are not Const, and effectively found in MCV with more than 
one count. Those cases can still be accumulated using 
accum_scalararray_prob(), but potentially grouped to reduce repeated work.

Overall, the optimization work can be logically split into three parts:

 1. Degenerate NULL case O(N) -> O(1) [0]
 2. Identical non-NULL per-element selectivity O(N) -> O(1) (can be
    split into a separate thread if prederred)
 3. MCV matching via hashing O(M*N) -> O(M+N) (current thread)

Feedback on how to best structure or split this work would be appreciated.

About op_is_reserved. It seems we should assign op_is_reserved = true, 
because we don't reverse types like eqjoinsel_semi(). If IN-list smaller 
than MCV-list we reverse it by fmgr_info(hash_mcv ? hashLeft : 
hashRight, &hash_proc). Thanks for this remark.

Thoughts?

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

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

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-02-26T08:57:26Z

    On 2/26/26 01:45, Ilia Evdokimov wrote:

> About op_is_reserved. It seems we should assign op_is_reserved = true, 
> because we don't reverse types like eqjoinsel_semi(). If IN-list 
> smaller than MCV-list we reverse it by fmgr_info(hash_mcv ? hashLeft : 
> hashRight, &hash_proc). Thanks for this remark.
>
I guess I rushed to conclusions. This assignment op_is_reversed = true 
was incorrect. During lookups, simplehash passes: key0 as the value 
stored in the hash table, key1 as the probe value. Since MCV entries 
correspond to the variable's statistics, the correct argument order 
depends on which side we build the hash table on. If we hash MCV values 
(hash_mcv = true), then key0 = MCV value, key1 = IN-list value, so we 
must call operator(key0, key1). If we hash IN-list elements (hash_mcv = 
fasle), then key0 = IN-list value, key1 = MCV value and we must call 
operator(key1, key0). Therefore the correct assignment is 
hashContext.op_is_reversed = hash_mcv.

If you have another suggestions to v6 patches, send them, and I'll fix 
them with hashContext.op_is_reversed = hash_mcv.

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

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

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-03-02T09:35:15Z

    I've addressed the previously mentioned issues in v7 patches.

I also retested the hash-based MCV path using bytea as the data type.

```
CREATE TABLE t (val bytea);
INSERT INTO t SELECT int4send(i) FROM generate_series(1, 10000) AS i, 
generate_series(1, 50);

ALTER TABLE t ALTER COLUMN val SET STATISTICS 10000;
ANALYZE t;
SELECT string_agg(format('int4send(%s)', v), ',') FROM 
generate_series(1, 10000) AS gs(v) \gset
EXPLAIN (SUMMARY) SELECT * FROM t WHERE val = 
ANY(ARRAY[:string_agg]::bytea[]);
```

Planning Time Speedup

default_statistics_target | Before (ms) | After (ms) | Speedup (x)
--------------------------------------------------------------------
100                       | 0.984       | 0.697      | 1.41
500                       | 1.260       | 0.984      | 1.28
1000                      | 4.183       | 1.825      | 2.29
2500                      | 64.715      | 1.298      | 49.86
5000                      | 251.619     | 4.751      | 52.96
7500                      | 562.775     | 2.895      | 194.40
10000                     | 998.330     | 3.561      | 280.36

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

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

    Zsolt Parragi <zsolt.parragi@percona.com> — 2026-03-02T21:37:01Z

    Hello!

+ if (vardata.isunique && vardata.rel && vardata.rel->tuples >= 1.0)
+ {
+ s2 = 1.0 / vardata.rel->tuples;
+ if (HeapTupleIsValid(vardata.statsTuple))
+ {
+ Form_pg_statistic stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
+ if (isInequality)
+ s2 = 1.0 - s2 - stats->stanullfrac;
+ }
+ }


Isn't there's a corner case where this if order returns an incorrect
estimate/regression?
See the following test:

CREATE TABLE test AS SELECT generate_series(1, 1000) AS id;
CREATE UNIQUE INDEX ON test(id);
-- no ANALYZE

EXPLAIN SELECT * FROM test WHERE id <> ALL(ARRAY[1, 2, 3]);
-- Actual:   rows=1
-- Expected: rows=997

ANALYZE test;
EXPLAIN SELECT * FROM test WHERE id <> ALL(ARRAY[1, 2, 3]);
-- Correct: rows=997

DROP TABLE test;

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

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-03-10T14:55:57Z

    In the thread discussing ALL semantics and NULL [0], the question was 
raised about adding a new regression test that checks selectivity 
estimation. If the change gets committed, it would make sense to add 
tests for this case as well.

Regarding the idea of optimizing the loop when all per-element 
selectivities are the same: I ran some quick tests to see how much the 
change in the v7-0002 patch affects planning time. Even without that 
patch, iterating over an array with 50k elements takes about 30 ms.

```
CREATE TABLE t (val bytea PRIMARY KEY);
INSERT INTO t SELECT int4send(i) FROM generate_series(1,50000) AS i;
ANALYZE t;
SELECT n_distinct FROM pg_stats WHERE tablename = 't';
  n_distinct
------------
          -1
(1 row)

SELECT string_agg(format('int4send(%s)', i), ',') FROM 
generate_series(1,50000) AS i \gset
EXPLAIN (SUMMARY) SELECT * FROM t WHERE val = ANY 
(ARRAY[:string_agg]::bytea[]);
..........
  Planning Time: 32.816 ms
(3 rows)
```

Given that, I don't see much benefit in adding additional logic here 
just to avoid the loop. It would likely introduce extra code complexity 
without a manful gain. If there is interest in optimization this case 
further, I can revisit it and add the additional patch.

The patch v8 can still be reviewed as-is, and if the selectivity 
regression test gets committed [0], I will add corresponding tests for 
this change as well.

[0]: 
https://www.postgresql.org/message-id/390a46f3-dbc4-4dc1-b49d-5cc61dd36026%40tantorlabs.com

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

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

    Zsolt Parragi <zsolt.parragi@percona.com> — 2026-03-11T08:01:37Z

    + if (elem_nulls[i])
+ {
+ nonmcv_cnt--;
+ continue;
+ }

> The patch v8 can still be reviewed as-is, and if the selectivity
> regression test gets committed [0], I will add corresponding tests for
> this change as well.

Without [0], the const path will return incorrect results for <> ALL
and NULLs. Compared to that, the other path still has special handling
in it:

+ /*
+ * For ALL semantics, if the array contains NULL, assume
+ * operator is strict. The ScalarArrayOpExpr cannot
+ * evaluate to TRUE, so return zero.
+ */



+ nonconst_sel = var_eq_non_const(&vardata, operator,
+ clause->inputcollid,
+ other_op, var_on_left,
+ isInequality);

+ if (isInequality)
+ individual_s = 1.0 - individual_s - nullfrac;

Isn't this the double negation issue again, which was once
mentioned/fixed earlier?

+ int count; /* number of occurrences of current value in */

That's a truncated comment

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

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-03-20T15:58:43Z

    On 3/11/26 11:01, Zsolt Parragi wrote:

> + /*
> + * For ALL semantics, if the array contains NULL, assume
> + * operator is strict. The ScalarArrayOpExpr cannot
> + * evaluate to TRUE, so return zero.
> + */
>
>
>
> + nonconst_sel = var_eq_non_const(&vardata, operator,
> + clause->inputcollid,
> + other_op, var_on_left,
> + isInequality);
>
> + if (isInequality)
> + individual_s = 1.0 - individual_s - nullfrac;
>
> Isn't this the double negation issue again, which was once
> mentioned/fixed earlier?

Right. I fixed it by using 'invert' for non-constant case. If there is a 
more elegant way to structure this, suggestions are very welcome.


> + int count; /* number of occurrences of current value in */
>
> That's a truncated comment

Fixed.


After the commit c95cd29 I have rebased this patch. During the rebase, I 
also add the NUL-handling path. In particular, I added an Assert(useOr) 
in the relevant branch to document and enforce the expected execution flow.

Additionally after the 374a639 I prepared a set of regression-style 
tests to verify that the selectivity estimates remain unchanged before 
and after applying the patch. However, these tests rely on stable row 
estimates from EXPLAIN, which are not guaranteed to be consistent across 
platforms. For that reason, they are not suitable for inclusion in the 
upstream test suite. I will keep these tests locally to validate 
correctness before and after the patch.


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

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

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-04-08T16:48:49Z

    I rebased the previous patch after it was marked as "Need rebase"

I also initialized the 'elem_cost' array to all 'true' values to 
simplify the code and avoid confusion, and rewrote 
accum_scalararray_prob() to improve readability.

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

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

    Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> — 2026-06-23T13:27:28Z

    Rebased patch after 06e94ec (Fix missed checks for hashability of 
container-type equality): the new `scalararray_mcv_hash_match()` now 
calls `get_op_hash_functions_ext()` instead of 
`get_op_hash_functions()`, passing `nominal_element_type` as the input 
type so that container-type operators are correctly rejected when their 
element type is not hashable.

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