Re: Optimize MCV stats for sortable types and utilize sorted-order properties - Mailing list pgsql-hackers

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

   **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;