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

Original
>From: ZizhuanLiu X-MAN <44973863(at)qq(dot)com>
>Date: Sep 15, 2026 10:18
>To: pgsql-hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
>Subject: Optimize MCV stats for sortable types and utilize sorted-order properties
>......
>Optimize MCV stats for sortable types and utilize sorted-order properties.
>
>1.Preserve ascending-ordered MCV values for sort-comparable types when filling
>pg_statistic. In compute_scalar_stats(), retain existing logic and allocate
>extra ScalarMCVItem workspace to hold sorted MCV entries.
>
>2.When applying statistics, use the pre-sorted MCV list:
>-compare against min/max boundaries. Boundary hits finish in 1-2 comparisons.
>-Values inside MCV range use binary-search (average N/2 -> log(n)).
>-Values outside MCV range skip full MCV iteration (N -> at most 2 comparisons).

Hi, hackers,

After investigating the files and functions related to STATISTIC_KIND_MCV, I classified their
roles (producer or consumer) and how MCV statistics are produced or consumed, as shown
in the list below (LIST-1). Taking third-party extensions and end users into consideration as well,
the consumers can be broadly classified as follows:
0. Final update of the statistics data: attribute_statistics_update_internal()
1. Producers: compute_distinct_stats(), compute_scalar_stats(), and import_pg_statistic()
2. Consumers, which can be classified according to how they consume MCV statistics:
2.1. Iterate through the MCV list, compare values using "=", and either select the selectivity
of a matching value or accumulate selectivities.
2.2. Ignore the values and only use the number of elements in the list/array, or unconditionally
accumulate the selectivities.
2.3. Only use the first element (the one with the highest selectivity).

After careful consideration, my initial proposal is as follows:
1. Add a new statistics kind:
#define STATISTIC_KIND_MCV_VALUE_SORTED 8

Unlike STATISTIC_KIND_MCV, which is ordered by frequency, STATISTIC_KIND_MCV_VALUE_SORTED
stores MCVs ordered by their values. 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.

2. Only change the producer compute_scalar_stats() to generate the new MCV kind, STATISTIC_KIND_MCV_VALUE_SORTED.
This should introduce almost no additional performance overhead (see the path/code snippet in my previous email).
If STATISTIC_KIND_MCV already exists, it will be updated or replaced by STATISTIC_KIND_MCV_VALUE_SORTED.

3. Adjust the consumers described above as follows:
2.1. Iterate through the MCV list, compare values using "=", and select the matching selectivity or accumulate selectivities.
This is the more complicated case, which I discuss in detail below.
2.2. Ignore the values and only use the number of elements in the list/array, or unconditionally accumulate selectivities.
--> No change is required.
2.3. Only use the first element (the one with the highest selectivity).
--> Behavior needs to be adjusted: iterate through numbers[] and find the maximum selectivity.
The performance impact should be controllable.

Here I would like to discuss case 2.1 in more detail: iterating through the MCV list, comparing values using "=",
and selecting a matching selectivity or accumulating selectivities.
A. If a data type only has "=", the MCV statistics are generated by compute_distinct_stats().
Therefore, only STATISTIC_KIND_MCV exists, and it can continue to be fetched and used in the existing way.

B. If a data type has both "=" and "<", prefer STATISTIC_KIND_MCV_VALUE_SORTED when fetching the MCV statistics.
If it is not available, fall back to STATISTIC_KIND_MCV.
2.1.1. If STATISTIC_KIND_MCV is available, use it exactly as before.
2.1.2. If STATISTIC_KIND_MCV_VALUE_SORTED is available and the collations are equal, we can consider using
the value ordering to optimize the lookup. For example:
- First check whether the constant is within the range of the MCV values.
- If it is within the range, use binary search to locate the matching value.
- If it is outside the range, there is no need to compare it with every MCV value; we can directly use sumcommon.
Otherwise, if the collations are not equalbe, have the same as with STATISTIC_KIND_MCV.

Case B will exist for a long time during upgrades/migration, because different tables may
have either STATISTIC_KIND_MCV_VALUE_SORTED or STATISTIC_KIND_MCV, unless this is a completely new database.

Based on my review of the relevant code and the function list in LIST-1,
my current assessment is that this approach is feasible and that the associated risks appear manageable.

As discussed here and in my previous email, the potential benefit can be significant.
In particular, var_eq_const() and mcv_selectivity() can greatly reduce the number of relatively expensive value comparisons.
eqjoinsel() and get_variable_range() may also benefit significantly, although I have not analyzed them in detail yet.

My biggest concern, however, is third-party/extension consumers of STATISTIC_KIND_MCV.
Their behavior is not something we can fully control or adjust at the PostgreSQL core level.
Since the ordering of the MCV values would change, an extension may be relying on the first
element being the MCV with the highest frequency, for example. Such assumptions could therefore be affected significantly.
I have not yet found a good solution for this potential compatibility issue.

These are my current thoughts and analysis. I would greatly appreciate any comments or suggestions.

Thanks again!

=== LIST-1 ===

src/backend/commands/analyze.c
static void compute_distinct_stats() — producer ; generates MCV statistics for data types that only have the "=" operator.
static void compute_scalar_stats() — producer ; generates MCV statistics for data types that have both "=" and "<" operators.

src/backend/executor/nodeHash.c
static void ExecHashBuildSkewHash() — consumer ; reads the MCV list and iterates through it, accumulating sslot.numbers[i].

src/backend/statistics/attribute_stats.c
static bool attribute_statistics_update_internal() — producer ; generates MCV statistics from the input parameters using statatt_build_stavalues() and updates the MCV statistics with statatt_set_slot().

src/backend/statistics/extended_stats_funcs.c
static Datum import_pg_statistic() — producer ; generates MCV statistics from JSONB input.

src/backend/utils/adt/network_selfuncs.c
static Selectivity networkjoinsel_inner() — consumer ; reads the MCV list and either accumulates mcv_numbers[i] or compares values for equality using "=".
static Selectivity networkjoinsel_semi() — consumer ; reads the MCV list and either accumulates mcv_numbers[i] or compares values for equality using "=".

src/backend/utils/adt/selfuncs.c
double var_eq_const() — consumer ; reads the MCV list, compares values using "=", obtains the selectivity of a matching value, and accumulates sslot.numbers when there is no match.
double var_eq_non_const() — consumer ; reads the MCV statistics and currently uses sslot.numbers[0], i.e., the largest selectivity.
double mcv_selectivity() — consumer ; reads the MCV list, checks each value against the comparison condition, and accumulates the corresponding selectivities.
double ineq_histogram_selectivity() — consumer ; reads the MCV statistics but only uses mcvslot.nnumbers.
Selectivity booltestsel() — consumer ; reads the first MCV element. If the first element is true, it uses sslot.numbers[0]; otherwise, it uses 1.0 - sslot.numbers[0] - freq_null.
Datum eqjoinsel() — consumer ; apart from the hash algorithm, iterates through the MCV list and compares values using "=".
void estimate_hash_bucket_stats() — consumer ; uses the first/largest-selectivity element by taking mcv_freq = sslot.numbers[0].
static bool get_variable_range() — consumer ; iterates through the MCV list and compares values using "=".

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