Обсуждение: [PATCH] ANALYZE: hash-accelerate MCV tracking for equality-only types

Hi Chengpeng,

`compute_distinct_stats()` is used for data types that have an equality
operator but no ordering (so we can't use the sort-based path).  It
keeps a `track[]` array of candidate MCVs and, for each sampled row,
searches that array for a match.  With high `statistics_target`, that
becomes O(n) per sample and can dominate ANALYZE time.

Nice catch - this is indeed not first time we run into an O(N^2) bottleneck in MCV array and address it with hash-based lookup. Thanks for working on this!

I have a couple of follow-up questions after a quick look at the patch:

1. The hash table is created but I do not see a corresponding destroy call.
2. In the original code, when a value was not found using the nested-loop search, the singleton (count = 1) region was shifted to make room for the new entry. After the patch, I no longer see this shifting logic. I might be missing something, but it looks like the non-hash path now follows the same replacement behavior as the hash-based one.

I’ll need a bit more time for a deeper review and some local benchmarks, but overall the approach looks interesting.

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

On 22.01.2026 12:40, Chengpeng Yan wrote:

The v2 patch is attached.

I took a deeper look at the v2 patch. The hash-based lookup itself looks correct, and when testing ANALYZE runtime with large default_statistics_target values, the patch indeed provides a noticeable speedup.

I have one small suggestion regarding the handling of firstcount1 and c1_cursor in the 'match' path.

When we find a match in track[], we increment count and perform bubble-up swaps to keep the array ordered by frequency. If the value previously has count = 1, it is effectively leaving the singleton (count = 1) region and becoming part of the count>1. Conceptually, this means that the boundary between these two regions (firstcount1) should move left by one.

Given that, it seems sufficient to update the boundary and then ensure that c1_cursor still point inside the singleton region:

if (was_count1 && j < firstcount1)
    firstcount1--;
if (c1_cursor < firstcount1)
    c1_cursor = firstcount1;

This avoids reasoning about specific shifted subranges (firstcount1..match_index). FIFO behavior is still preserved because c1_cursor is only advanced when an eviction actually happens.

Let me know if I'm overlooking any corner cases.

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

> On Feb 2, 2026, at 21:09, Tatsuya Kawata <kawatatatsuya0913@gmail.com> wrote:
> 
> Hi,
> 
> Thank you for the detailed explanation! Your explanation helped me understand the design much better.
> I hope my understanding is now on the right track.
> 
> I tested v3 both approaches:
> 
> 1. Ilia's proposal with corrected increment and <= condition:
>    if (was_count1 && j <= firstcount1)
>        firstcount1++;
> 
> 2. The original patch with while loop:
>    while (use_hash && firstcount1 < track_cnt &&
>           track[firstcount1].count > 1)
>        firstcount1++;
> 
> I verified the following cases and both approaches produced correct 
> track array values after the loop completed:
> 
> Case 1: c1_cursor == match_index
>   c1_cursor points to a singleton, that singleton is matched again,
>   bubble-up occurs, then a new value arrives triggering eviction.
> 
> Case 2: c1_cursor < match_index
>   c1_cursor is in the earlier part of the singleton region,
>   and a singleton further back is matched.
> 
> Case 3: c1_cursor > match_index
>   c1_cursor has advanced past match_index due to previous evictions,
>   and an earlier singleton is matched.
> 
> Both approaches seem to work correctly. The code reduction from 1 is minimal, so either approach should be fine.
> I believe the while loop exists to handle potential edge cases, 
> though in typical scenarios firstcount1 would only increment once per match (since one singleton is promoted at a
time).
> 
> Overall, the patch looks good to me.

Hi Tatsuya,

Thank you for the detailed testing and for validating those
c1_cursor/match_index cases. I agree with your conclusion that both
variants behave correctly, and that the code reduction from the
single-step approach is small.

On firstcount1: in the typical case it should advance by one when a
singleton is promoted. I kept the loop-style adjustment mainly as an
invariant repair step in hash mode — after bubble-up, it simply advances
firstcount1 until it again points to the first singleton (or track_cnt).
That makes the update less dependent on subtle index relationships and
is a bit more robust against potential corner cases (or future tweaks to
the reordering), while still being cheap since firstcount1 only moves
forward and is bounded by track_cnt/track_max.

That said, if other community members would prefer the simpler one-step
update for readability, I’m happy to switch.

--
Best regards,
Chengpeng Yan

On Tue, Feb 3, 2026 at 11:33 AM Chengpeng Yan <chengpeng_yan@outlook.com> wrote:
> That said, if other community members would prefer the simpler one-step
> update for readability, I’m happy to switch.

To evaluate that, it would be easier if the patch were split into two
commits, one with the simple step approach, and one that changes to
the other approach.

Also, we have some places that switch from e.g. an array to a hash
table once a collection gets above a certain threshold. In this case,
however, having less than 100 stat target is unheard of, in my
experience. It's only a tiny amount of code, but it doesn't seem worth
special-casing. Others may have a different opinion, and I'm not sure
we don't already have this behavior elsewhere.

--
John Naylor
Amazon Web Services

> On Feb 3, 2026, at 13:39, John Naylor <johncnaylorls@gmail.com> wrote:
>
> To evaluate that, it would be easier if the patch were split into two
> commits, one with the simple step approach, and one that changes to
> the other approach.
>
> Also, we have some places that switch from e.g. an array to a hash
> table once a collection gets above a certain threshold. In this case,
> however, having less than 100 stat target is unheard of, in my
> experience. It's only a tiny amount of code, but it doesn't seem worth
> special-casing. Others may have a different opinion, and I'm not sure
> we don't already have this behavior elsewhere.

Thanks for the suggestion — I’ve applied it in v4 by splitting the
changes into two commits.

I think it would be beneficial to split it into two logically independent parts. Right now the patch introduces two different changes at once:

1. Replacing the original shift-based singleton handling with the cursor based eviction mechanism.
2. Adding the hash-based lookup.

Splitting the patch would make review easier because I can first focus purely on the algorithmic transformation (shift -> cursor) and verify semantic equivalence.

Regarding the hash threshold: my initial approach followed existing
postgres precedent for hash-based MCV matching. For example, commit
057012b205a (“Speed up eqjoinsel() with lots of MCV entries”) introduces
EQJOINSEL_MCV_HASH_THRESHOLD in selfuncs.c, only enabling hashing once
the MCV set is large enough to amortize the setup cost. The exact
threshold differs, but the pattern is similar.

Also, while 100 is the default statistics target, there are internal
cases that use smaller values — e.g. vacuumdb staged analyze temporarily
sets default_statistics_target to 1 and 10 in vacuuming.c — which was
part of the motivation for keeping the thresholded behavior.

That said, I’m happy to adjust or remove the threshold if the consensus
is to simplify this further.

I would probably not rely too heavily on EQJOINSEL_MCV_HASH_THRESHOLD as a direct reference point here. That threshold is somewhat heuristic as well, and the cost trade-offs in eqjoinsel() are not identical to what we have in compute_distinct_stats(). In particular, here the break-even point will strongly depend on the data type and value width. For example, with wider datums (e.g. bytea), the comparison cost increases, and the threshold at which hashing amortizes its setup cost may shift noticeably. We don't need to compute the exact optimal threshold - just get a reasonable order.

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

Have you benchmarked this change except in first message in this thread?

While reviewing the patch more closely, I noticed 
that compute_distinct_stats() is only used for types where we have =, != 
but not <. In practice, most common scalar types go through 
compute_scalar_stats() instead.

That makes me wonder how often this optimization would actually trigger 
in real workloads. Since compute_scalar_stats() is the more common path, 
there's chance that the hash-table based improvement in 
compute_distinct_stats() may not provide a noticeable overall benefit.

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