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

Original

From: ZizhuanLiu X-MAN <44973863@qq.com>
Date: Sep 15, 2026 10:18
To: pgsql-hackers <pgsql-hackers@lists.postgresql.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@qq.com

I write

From: ZizhuanLiu X-MAN <44973863@qq.com>
Date: Sep 16, 2026 22:49
To: pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Cc: tgl <tgl@sss.pgh.pa.us>, ilya.evdokimov <ilya.evdokimov@tantorlabs.com>
Subject: Re: Optimize MCV stats for sortable types and utilize sorted-order properties

Original

From: ZizhuanLiu X-MAN <44973863@qq.com>
Date: Sep 15, 2026 10:18
To: pgsql-hackers <pgsql-hackers@lists.postgresql.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.

There is another fundamental issue:
If the new-version compute_scalar_stats() no longer generates STATISTIC_KIND_MCV, but third-party code or extensions try to fetch STATISTIC_KIND_MCV. When only STATISTIC_KIND_MCV_VALUE_SORTED exists in the system,
- should get_attstatsslot() re-sort STATISTIC_KIND_MCV_VALUE_SORTED by numbers[] in ascending order before returning it to the caller?
(This re-sort cost should be manageable, since we sort on numbers[], not on values[].)
- Or should we return STATISTIC_KIND_MCV_VALUE_SORTED directly without any processing?

For good backward-compatibility, I lean toward the former option, though it is not a very elegant design.

regards,
--
ZizhuanLiu (X-MAN) 
44973863@qq.com

I write
From: ZizhuanLiu X-MAN <44973863@qq.com>
Date: Sep 17, 2026 10:01
To: ZizhuanLiu X-MAN <44973863@qq.com>, pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Cc: tgl <tgl@sss.pgh.pa.us>, ilya.evdokimov <ilya.evdokimov@tantorlabs.com>
Subject: Re: Optimize MCV stats for sortable types and utilize sorted-order properties
......
There is another fundamental issue:
If the new-version compute_scalar_stats() no longer generates STATISTIC_KIND_MCV, but third-party code or extensions try to fetch STATISTIC_KIND_MCV. When only STATISTIC_KIND_MCV_VALUE_SORTED exists in the system,
- should get_attstatsslot() re-sort STATISTIC_KIND_MCV_VALUE_SORTED by numbers[] in ascending order before returning it to the caller?
(This re-sort cost should be manageable, since we sort on numbers[], not on values[].)
- Or should we return STATISTIC_KIND_MCV_VALUE_SORTED directly without any processing?

For good backward-compatibility, I lean toward the former option, though it is not a very elegant design.

Looking at the call graph in LIST-1:
When a caller requests STATISTIC_KIND_MCV but only STATISTIC_KIND_MCV_VALUE_SORTED is available in the system,
some reordering is required.

Based on how these callers consume the data, we only need to swap the entry with the largest number[i] and its
corresponding values[i] into slot [0], **rather than performing a full sort of the entire array**.

As shown by the logic in LIST-1: existing callers either rely on slot [0] holding the entry with the highest count
(the original behaviour of STATISTIC_KIND_MCV), or iterate over the number[] / values[] arrays.

Simply swapping the maximum-count entry to index [0] is sufficient to preserve backward compatibility. This keeps
the adjustment minimal: it requires N comparisons over the double-typed number[] array and at most one two-element swap,
so the overhead is kept as small as possible.

I will go ahead and implement along these lines. Deep insights and further feedback are very welcome.

=== 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@qq.com

Hi, hackers

Optimize MCV statistics for sortable types by leveraging sorted-order properties

1. Preserve ascending-ordered MCV values (new statistic kind STATISTIC_KIND_MCV_VALUE_SORTED)
for sort-comparable types when populating pg_statistic.
In compute_scalar_stats(), keep existing logic and allocate an extra ScalarMCVItem
workspace to store sorted MCV entries.

2. Use the pre-sorted MCV list during selectivity estimation:
&nbsp; &nbsp;- Check against min/max boundaries; boundary cases complete with only 1-2 comparisons.
&nbsp; &nbsp;- Entries inside the MCV range use binary search, reducing cost from average N/2 to log(N).
&nbsp; &nbsp;- Entries outside the MCV range skip full MCV iteration, limiting comparisons to at most 2.

&nbsp; &nbsp;This optimization is implemented for **var_eq_const()** (equality comparisons) and
&nbsp; &nbsp;**mcv_selectivity()** (inequalities: <, <=, &gt;, &gt;=), fully exploiting sorted MCV properties.
&nbsp; &nbsp;Further functions that can benefit from sorted MCV will be considered later.

3. Completed work:
&nbsp; &nbsp;- Compatibility support for non-sortable types and sorted-state detection.
&nbsp; &nbsp;- pg_stats view updates to expose STATISTIC_KIND_MCV_VALUE_SORTED MCV values
&nbsp; &nbsp; &nbsp;via most_common_vals and most_common_freqs.

4. TODO:
&nbsp; &nbsp;- Avoid storing STATISTIC_KIND_MCV_VALUE_SORTED alongside legacy STATISTIC_KIND_MCV.
&nbsp; &nbsp; &nbsp;When compute_scalar_stats() generates the new sorted MCV for sortable types,
&nbsp; &nbsp; &nbsp;remove or overwrite any existing STATISTIC_KIND_MCV entry.
&nbsp; &nbsp;- Audit functions for performance benefits or regressions introduced by sorted MCV,
&nbsp; &nbsp; &nbsp;and apply necessary fixes.
&nbsp; - Add comparison of performance test results

Attach test SQL and patch files:

drop table if exists t_analyze_mcv;
create table t_analyze_mcv(id int);

insert into t_analyze_mcv select (g+45) % 10 from generate_series(1, 90) g;
insert into t_analyze_mcv select 12 from generate_series(1, 10) g;
insert into t_analyze_mcv select * from t_analyze_mcv;

analyze t_analyze_mcv;

select attname,null_frac,n_distinct,most_common_vals,most_common_freqs,correlation
&nbsp;from pg_catalog.pg_stats where tablename = 't_analyze_mcv'\gx

-[ RECORD 1 ]-----+--------------------------------------------------------
attname &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; | id
null_frac &nbsp; &nbsp; &nbsp; &nbsp; | 0
n_distinct &nbsp; &nbsp; &nbsp; &nbsp;| 11
most_common_vals &nbsp;| {0,1,2,3,4,5,6,7,8,9,12}
most_common_freqs | {0.09,0.09,0.09,0.09,0.09,0.09,0.09,0.09,0.09,0.09,0.1}
correlation &nbsp; &nbsp; &nbsp; | 0.20327759

xman7=# select id,count(*) from t_analyze_mcv group by id ;
&nbsp;id | count
----+-------
&nbsp; 8 | &nbsp; &nbsp;18
&nbsp; 9 | &nbsp; &nbsp;18
&nbsp; 7 | &nbsp; &nbsp;18
&nbsp; 1 | &nbsp; &nbsp;18
&nbsp; 5 | &nbsp; &nbsp;18
&nbsp; 4 | &nbsp; &nbsp;18
&nbsp; 2 | &nbsp; &nbsp;18
&nbsp; 0 | &nbsp; &nbsp;18
&nbsp; 6 | &nbsp; &nbsp;18
&nbsp;12 | &nbsp; &nbsp;20
&nbsp; 3 | &nbsp; &nbsp;18
(11 rows)

xman7=#

--for var_eq_const()
explain select * from t_analyze_mcv where id = -1; &nbsp; --1 &nbsp;rows, &nbsp;low-out-off-mcv-range, directly compute sumcommon with comparing OTHER MCV VALUES
explain select * from t_analyze_mcv where id = 0; &nbsp; &nbsp;--18 rows, &nbsp;compare first one,directly complete
explain select * from t_analyze_mcv where id = 5; &nbsp; &nbsp;--18 rows, &nbsp;in mcv rang,one of list,binary search found
explain select * from t_analyze_mcv where id = 10; &nbsp; --1 &nbsp;rows, &nbsp;in mcv rang,one of list,binary search not found, directly compute sumcommon with comparing OTHER MCV VALUES
explain select * from t_analyze_mcv where id = 12; &nbsp; --20 rows, &nbsp;compare last one,directly complete
explain select * from t_analyze_mcv where id = 13; &nbsp; --1 &nbsp;rows, &nbsp;high-out-off-mcv-range, directly compute sumcommon with comparing OTHER MCV VALUES

--for mcv_selectivity()

--< <=
-- 1 row, low-out-of-mcv-range, 1 compare with [0]. Directly compute sumcommon without comparing other MCV values; mcv_selec = 0.0
explain select * from t_analyze_mcv where id < &nbsp;-1; -- 1 rows
--or
explain select * from t_analyze_mcv where id <= -1; -- 1 rows

-- 1 compare with [0]. Directly compute sumcommon without comparing other MCV values;
explain select * from t_analyze_mcv where id < &nbsp;0; -- 1 rows
--or
explain select * from t_analyze_mcv where id <= 0; -- 18 rows

-- compare with [0] and [nvlaues - 1], and binary search
explain select * from t_analyze_mcv where id < &nbsp;1; -- 18 rows
explain select * from t_analyze_mcv where id <= 1; --36 rows
explain select * from t_analyze_mcv where id < &nbsp;10; --180 rows
explain select * from t_analyze_mcv where id <= 10; --180 rows

-- compare with [0] and [nvlaues - 1], not need binary search
explain select * from t_analyze_mcv where id < &nbsp;12; --180 rows
explain select * from t_analyze_mcv where id <= 12; --200 rows

-- compare with [0] and [nvlaues - 1], not need binary search
explain select * from t_analyze_mcv where id < &nbsp;12; --1 rows
explain select * from t_analyze_mcv where id <= 12; --1 rows

--&gt; &gt;=
--only compare with [0] and and [nvlaues - 1],not need binary search
explain select * from t_analyze_mcv where id &gt; -1; &nbsp;--200 rows
explain select * from t_analyze_mcv where id &gt;= -1; --200 row
explain select * from t_analyze_mcv where id &gt; 0; &nbsp;--182 rows
explain select * from t_analyze_mcv where id &gt;= 0; --200 rows

--only compare with [0] and and [nvlaues - 1],and binary search
explain select * from t_analyze_mcv where id &gt; 5; &nbsp;-- 92 rows
explain select * from t_analyze_mcv where id &gt;= 5; -- 110 rows

--only compare with [nvlaues - 1]
explain select * from t_analyze_mcv where id &gt; 12; &nbsp;-- 1 rows
explain select * from t_analyze_mcv where id &gt;= 12;

regards,
--
ZizhuanLiu&nbsp;(X-MAN)&nbsp;
44973863@qq.com