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

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:
   - 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
&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(at)qq(dot)com