Original
>From: Ilia Evdokimov <[email protected]>
>Date: Sep 21, 2026 21:03
>To: ZizhuanLiu X-MAN <[email protected]>, pgsql-hackers
><[email protected]>
>Cc: tgl <[email protected]>, tomas <[email protected]>, dean.a.rasheed
><[email protected]>, guofenglinux <[email protected]>
>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 <[email protected]>
>>Date: Sep 16, 2026 22:49
>>To: pgsql-hackers <[email protected]>
>>Cc: tgl <[email protected]>, ilya.evdokimov <[email protected]>
>>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)
[email protected]
