[PATCH] ANALYZE: hash-accelerate MCV tracking for equality-only types

Hi Chengpeng,

On 21.01.2026 17:13, Chengpeng Yan wrote:

`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/

Hi

On Jan 22, 2026, at 04:44, Ilia Evdokimov <ilya.evdokimov@tantorlabs.com> wrote:

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!

Thanks for the review. This change was actually inspired by your earlier
patch on a similar issue, so thanks a lot for that as well.

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.

The hash table is allocated in the per-column temporary memory context
(the “Analyze Column” context that is active while compute_stats()
runs). That context is MemoryContextReset() after each column and
eventually deleted at the end of ANALYZE, so the table is reclaimed
automatically.

This matches the existing convention noted at the end of
compute_distinct_stats() (“We don’t need to bother cleaning up any of
our temporary palloc’s”).

That said, I can add an explicit DistinctHash_destroy() before returning
for clarity, although it shouldn’t be required for correctness or leak
prevention.

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.

In the original code, inserting a new distinct value into the singleton
(count = 1) region effectively evicted the oldest singleton (FIFO) by
inserting at the head of that region and shifting the tail, which is
O(n) per new distinct value.

The patch replaces this with a FIFO eviction cursor (effectively a
circular / round-robin cursor) over the count = 1 region, avoiding
repeated shifts. When hashing is enabled, this also avoids having to
update many hash→index mappings due to element shifts.

I kept the non-hash path using the same mechanism so that the hash and
fallback paths follow the same replacement behavior, with the intention
of preserving the original FIFO semantics while avoiding the O(n) cost.

I’ve also posted a v2 update. It adjusts the eviction cursor when a
count = 1 value is promoted (via the existing bubble-up logic), so that
the cursor-based eviction is now exactly equivalent to the original
shift-based FIFO behavior.

I’ve also updated the relevant comments to clarify this behavior. The v2
patch is attached.

--
Best regards,
Chengpeng Yan

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/

Hi,

As a newcomer who is still learning the codebase, I attempted to review the
v2 patch.
The behavior looks correct to me.

I considered some edge cases and they all seem to be handled properly:

- Edge case 1: c1_cursor is behind match_index
This can occur when firstcount1 advances past c1_cursor due to bubble-up.
It appears to be handled by the condition at L2318.

- Edge case 2: All singletons are promoted, leaving no singletons to evict
The condition `else if (firstcount1 < track_cnt)` at L2348 ensures that
when firstcount1 == track_cnt (empty singleton region), the new value
is simply skipped. This looks correct.

- Edge case 3: c1_cursor exceeds track array bounds
While Ilia's proposal would simplify this, it's currently handled by
L2321.

Regarding Ilia's simplification proposal:

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

The simplification looks appealing. However, I may be misunderstanding
something -
should the logic perhaps be:

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

My reasoning:
- Without `<=`, the case where j == firstcount1 would leave firstcount1
pointing
to a value with count=2 (no longer a singleton).
- I believe `firstcount1--` should be `firstcount1++`, since when a
singleton
is promoted to multiply-seen, the singleton region shrinks from the left,
meaning the boundary moves right (increases).

Please correct me if I'm missing something.

Regards,
Tatsuya Kawata

On Feb 1, 2026, at 17:09, Tatsuya Kawata <kawatatatsuya0913@gmail.com> wrote:

Regarding Ilia's simplification proposal:

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

The simplification looks appealing. However, I may be misunderstanding something -
should the logic perhaps be:

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

My reasoning:
- Without `<=`, the case where j == firstcount1 would leave firstcount1 pointing
to a value with count=2 (no longer a singleton).
- I believe `firstcount1--` should be `firstcount1++`, since when a singleton
is promoted to multiply-seen, the singleton region shrinks from the left,
meaning the boundary moves right (increases).

Please correct me if I'm missing something.

Regards,
Tatsuya Kawata

Hi,

Thanks for the careful review and the suggestions.

For v3 I did not change the algorithm/behavior; I only adjusted the
comment in the match path to make the bubble-up / cursor interaction
more explicit.

On the firstcount1 / c1_cursor handling: c1_cursor is an index-based
“clock hand” over the count==1 region used to get FIFO eviction without
physically shifting the singleton subarray. The extra cursor adjustment
in the match path is there to preserve the same FIFO victim sequence as
the original shift-based code.

The key case is when a singleton is matched again (was_count1) and then
bubbles up into the count>1 prefix. That bubble-up effectively shifts
track[firstcount1..match_index-1] right by one. If c1_cursor points
anywhere in that shifted range (or at match_index itself), it must
advance by one as well; otherwise the cursor would start referring to a
different element than before the shift and we’d evict a newer singleton
next, breaking FIFO equivalence.

Concrete example: singleton region is [A,B,C,D] and c1_cursor points to
B (next to evict). If D is seen again, it becomes count=2 and bubbles
up, shifting [A,B,C] one slot to the right. B’s index changes, so
c1_cursor must move with it; otherwise the next eviction would
incorrectly target A (or whatever now sits at the old index), not B as
in the shift-based implementation. This is also why the condition uses
<= match_index: the cursor may point at the promoted singleton slot as
well.

Regarding the boundary direction: since firstcount1 is “index of first
singleton”, promotions shrink the singleton region and move the boundary
to the right. In hash mode that’s handled by advancing firstcount1 while
track[firstcount1].count > 1, and then clamping c1_cursor back into the
singleton region if needed.

If anything above still sounds off, happy to walk through a specific
trace.

--
Best regards,
Chengpeng Yan

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.

Regards,
Tatsuya Kawata

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.

0001 contains the main optimization and uses the simpler one-step update
for firstcount1 in the hash path.

0002 is a small follow-up that switches that logic to the more
invariant-preserving form discussed earlier.

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.

--
Best regards,
Chengpeng Yan

On 07.02.2026 16:39, Chengpeng Yan wrote:

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/