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

On 9/21/26 08:40, ZizhuanLiu X-MAN wrote:
> Hi, hackers
>
> (Rebase it. CC’ing all, hoping for your sincere assistance.)
>
> 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:
> - Check against min/max boundaries; boundary cases complete with only 1-2 comparisons.
> - Entries inside the MCV range use binary search, reducing cost from average N/2 to log(N).
> - Entries outside the MCV range skip full MCV iteration, limiting comparisons to at most 2.
>
> This optimization is implemented for **var_eq_const()** (equality comparisons) and
> **mcv_selectivity()** (inequalities: <, <=, >, >=), fully exploiting sorted MCV properties.
> Further functions that can benefit from sorted MCV will be considered later.
>
> 3. Completed work:
> - Compatibility support for non-sortable types and sorted-state detection.
> - pg_stats view updates to expose STATISTIC_KIND_MCV_VALUE_SORTED MCV values
> via most_common_vals and most_common_freqs.
>
> 4. TODO:
> - Avoid storing STATISTIC_KIND_MCV_VALUE_SORTED alongside legacy STATISTIC_KIND_MCV.
> When compute_scalar_stats() generates the new sorted MCV for sortable types,
> remove or overwrite any existing STATISTIC_KIND_MCV entry.
> - Audit functions for performance benefits or regressions introduced by sorted MCV,
> and apply necessary fixes.
> - 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
> from pg_catalog.pg_stats where tablename = 't_analyze_mcv'\gx
> -[ RECORD 1 ]-----+--------------------------------------------------------
> attname | id
> null_frac | 0
> n_distinct | 11
> most_common_vals | {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 | 0.20327759
> xman7=# select id,count(*) from t_analyze_mcv group by id ;
> id | count
> ----+-------
> 8 | 18
> 9 | 18
> 7 | 18
> 1 | 18
> 5 | 18
> 4 | 18
> 2 | 18
> 0 | 18
> 6 | 18
> 12 | 20
> 3 | 18
> (11 rows)
> xman7=#
> --for var_eq_const()
> explain select * from t_analyze_mcv where id = -1; --1 rows, low-out-off-mcv-range, directly compute sumcommon with comparing OTHER MCV VALUES
> explain select * from t_analyze_mcv where id = 0; --18 rows, compare first one,directly complete
> explain select * from t_analyze_mcv where id = 5; --18 rows, in mcv rang,one of list,binary search found
> explain select * from t_analyze_mcv where id = 10; --1 rows, 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; --20 rows, compare last one,directly complete
> explain select * from t_analyze_mcv where id = 13; --1 rows, 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 < -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 < 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 < 1; -- 18 rows
> explain select * from t_analyze_mcv where id <= 1; --36 rows
> explain select * from t_analyze_mcv where id < 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 < 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 < 12; --1 rows
> explain select * from t_analyze_mcv where id <= 12; --1 rows
> --> >=
> --only compare with [0] and and [nvlaues - 1],not need binary search
> explain select * from t_analyze_mcv where id > -1; --200 rows
> explain select * from t_analyze_mcv where id >= -1; --200 row
> explain select * from t_analyze_mcv where id > 0; --182 rows
> explain select * from t_analyze_mcv where id >= 0; --200 rows
> --only compare with [0] and and [nvlaues - 1],and binary search
> explain select * from t_analyze_mcv where id > 5; -- 92 rows
> explain select * from t_analyze_mcv where id >= 5; -- 110 rows
> --only compare with [nvlaues - 1]
> explain select * from t_analyze_mcv where id > 12; -- 1 rows
> explain select * from t_analyze_mcv where id >= 12;
> regards,
> --
> ZizhuanLiu (X-MAN)
> 44973863(at)qq(dot)com

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.

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
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.

--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/