Re: Optimize MCV stats for sortable types and utilize sorted-order properties

Original
>From: Ilia Evdokimov <ilya(dot)evdokimov(at)tantorlabs(dot)com>
>Date: Sep 21, 2026 21:03
>To: ZizhuanLiu X-MAN <44973863(at)qq(dot)com>, pgsql-hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
>Cc: tgl <tgl(at)sss(dot)pgh(dot)pa(dot)us>, tomas <tomas(at)vondra(dot)me>, dean.a.rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com>, guofenglinux <guofenglinux(at)gmail(dot)com>
>Subject: Re: Optimize MCV stats for sortable types and utilize sorted-order properties
>......
>In practice, users rarely bump default_statistics_target to extreme
>values like 10 000. At 100-200, scanning a compact array of Datums fits
>entirely in L1 cache.

1.Regarding the L1 cache aspect, I have not studied it in much depth. After doing some additional research,
I would like to share a few thoughts:

Regardless of whether default_statistics_target is the maximum value of 10,000 or the default value of 100,
across an entire database system, there can be a very large number of columns that may use comparison
operators for selectivity estimation, depending on the SQL workload. var_eq_const() handles =, while
mcv_selectivity() handles <, <=, > and >=.

These comparison operators are very common and can be used very frequently. The proposed approach
could significantly reduce the number of comparisons/scans from an average of N/2 for = and a fixed N
for <, <=, > and >=, to approximately log2(N) by using binary search. If the CONSTVALUE is close to one
of the boundaries of the sorted values, the number of comparisons may potentially be reduced to the
minimum of just one or two.

For example:

var_eq_const():
Original Proposed
default_statistics_target min max avg min max avg
-------------------------------------------------------------------
100 1 100 50 1 7 5.8
10000 1 10000 5000 1 14 12.36
-------------------------------------------------------------------

mcv_selectivity():
Original Proposed
default_statistics_target fixed min max avg
------------------------------------------------------------
100 100 1 7 5.8
10000 10000 1 14 12.36
------------------------------------------------------------

These numbers are only intended to illustrate the reduction in the number of comparisons;
they are not intended to represent measured CPU execution time.

2.Regarding the statement that "a compact array of Datums fits entirely in L1 cache":
L1 cache is a very limited and valuable resource, and part of it is used for instruction caching
rather than being entirely available for data. Therefore, I think it is still useful to consider the
amount of work performed on the cached data.

The goal of this proposal is to reduce the number of scans and comparisons, complete the
required work as quickly as possible, and release the relevant cache resources as soon as
possible so that they can be used by other concurrent work.

3.Since the capacity of L1 cache is limited, even if part or all of the data is cached, there can still
be cases where the mcv values[] array is too large to fit entirely in L1 cache. In addition, for
variable-length data types such as text, the comparison itself can be relatively expensive.
Therefore, reducing the number of comparisons may be even more important in these cases,
as it can significantly reduce the time required for selectivity estimation.

4.In addition, even for commonly used data types such as int, reducing the number of scans/comparisons
also reduces the subsequent function-call overhead and potentially other memory-related overhead
associated with performing the comparisons.

5.From the global perspective of the DBMS and OS, making efficient use of the most limited resources and
releasing them as early as possible is also a useful high-level design principle for improving concurrency.

6.Even if we focus only on these one or two functions themselves, I think the potential benefit is already fairly clear.
These are frequently used and performance-sensitive parts of the selectivity estimation path, and a large number of
columns may potentially go through them. When combined with concurrent workloads across the DBMS and OS,
the cumulative benefit could be significant.

I think this reduction in the number of scans/comparisons is one of the main potential improvements and benefits of this approach.

>Furthermore, introducing a new STATISTIC_KIND fractures the catalog and
>consumes limited slots in pg_statistics for an optimization targeting a
>rare worst-case scenario. Range estimation is already the dedicated

>>From: ZizhuanLiu X-MAN <44973863(at)qq(dot)com>
>>Date: Sep 16, 2026 22:49
>>To: pgsql-hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
>>Cc: tgl <tgl(at)sss(dot)pgh(dot)pa(dot)us>, ilya.evdokimov <ilya(dot)evdokimov(at)tantorlabs(dot)com>
>>Subject: Re: Optimize MCV stats for sortable types and utilize sorted-order properties
>>......
>>STATISTIC_KIND_MCV_VALUE_SORTED and STATISTIC_KIND_MCV
>>will not coexist, so the number of statistics slots will not exceed the STATISTIC_NUM_SLOTS limit."

1.When analyzing a table, for data types without a < operator, compute_distinct_stats() continues to
generate the existing MCV statistics, where the values[] cannot necessarily be sorted by value, but the
numbers[] are sorted in descending order of frequency.

For data types with a < operator, the original compute_scalar_stats() generates MCV statistics with
numbers[] sorted in descending order of frequency, while the new version generates MCV statistics
with values[] sorted in ascending order of value. The change to this function is relatively small:
it mainly adds a palloc_array(ScalarMCVItem, num_mcv) allocation, without introducing other
significant computation. These two forms will not coexist for sortable columns.

(TODO: this part is not completed yet. I will continue working on it later: the new version will replace
the old statistics for this type of column.) Therefore, there should be no conflict, and the number of
statistics slots will not exceed the STATISTIC_NUM_SLOTS limit.

2.pg_stats had been adjusted to treat STATISTIC_KIND_MCV and STATISTIC_KIND_MCV_VALUE_SORTED
in the same way when returning most_common_vals and most_common_freqs.

This is currently the only compatibility concern I have identified: an SQL caller may access most_common_freqs[0]
and assume that it represents the maximum frequency, which is related to the next point.

3.For consumers that currently directly use numbers[0] as the maximum MCV selectivity, we can encapsulate this
behavior in a compatibility helper such as max_mcv_numbers(&sslot, statskind).

4.This is the compatibility and discoverability approach I have considered so far for retaining compatibility while
allowing MCV values to be stored in value order. I think this addresses the concern you raised, but I would be very
interested to hear if there are other compatibility issues that I have overlooked.

>rare worst-case scenario. Range estimation is already the dedicated
>responsibility of histogram_BOUNDS, so having MCV duplicate sorted range
>checks adds considerable code complexity to selfuncs.c with very
>questionable gains.
>To sum it up, keeping the status quo is the better choice.

1.Based on my investigation, comparison operators cover a fairly broad class of commonly used selectivity estimation paths.
ar_eq_const() handles =, while mcv_selectivity() handles <, <=, > and >=:

* var_eq_const --- eqsel for var = const case
* scalarineqsel - Selectivity of "<", "<=", ">", ">=" for scalars.
* scalarltsel - Selectivity of "<" for scalars.
* scalarlesel - Selectivity of "<=" for scalars.
* scalargtsel - Selectivity of ">" for scalars.
* scalargesel - Selectivity of ">=" for scalars.

In particular, mcv_selectivity() performs selectivity estimation for an individual range comparison.

I have not yet carefully investigated cases where these operators are combined with AND, or BETWEEN conditions.
I do not yet know whether these cases can also benefit from the value ordering of the new MCV array. This is one of
the areas I plan to investigate next, and I suspect there may be opportunities to make use of the sorted values[] there as well.

2.Regarding the existing STATISTIC_KIND_HISTOGRAM comment:
* stanumbers is not used and should be NULL. IMPORTANT POINT: if an MCV
* slot is also provided, then the histogram describes the data distribution
* *after removing the values listed in MCV* (thus, it's a "compressed
* histogram" in the technical parlance). This allows a more accurate
* representation of the distribution of a column with some very-common
* values. In a column with only a few distinct values, it's possible that
* the MCV list describes the entire data population; in this case the
* histogram reduces to empty and should be omitted.

My understanding is that MCV and STATISTIC_KIND_HISTOGRAM are therefore not duplicating the same information.
In fact, STATISTIC_KIND_HISTOGRAM may not exist at all in some cases.

Therefore, I think an MCV list sorted by values[] is not redundant storage, but can provide independent value for
efficiently locating and processing the MCV portion of the distribution.

3.Looking at the V2 patch, because it takes binary search into account, makes use of the comparison results against
the two boundary elements of the array, and also needs to handle the = cases within <= and >=, the current code logic,
readability, and maintainability may not yet be optimal.

If there is an opportunity, I think this part could be further simplified or refactored into an independent helper function to
encapsulate the relevant checks.
>--
>Best regards,
>Ilia Evdokimov,
>Tantor Labs LLC,
>https://tantorlabs.com/

These are my current thoughts and observations.
I may certainly have overlooked some aspects,so I would welcome any corrections or suggestions.

regards,
--
ZizhuanLiu (X-MAN) 
44973863(at)qq(dot)com