Original
>From: ZizhuanLiu X-MAN <[email protected]>
>Date: Sep 15, 2026 10:18
>To: pgsql-hackers <[email protected]>
>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)
[email protected]
