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

Hi, hackers

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

3.TODO(I will take this on.):
- Audit functions for benefits / regressions caused by sorted MCV and apply fixes
- Compatibility support for non-sortable types and sorted-state detection

This patch builds on earlier work; I’d like to start a new thread for it:
Discussion: https://www.postgresql.org/message-id/flat/tencent_A15A9D89A86F2E4B086ABA462578B9B64307(at)qq(dot)com
Commitfest: https://commitfest.postgresql.org/patch/7075/

Feedback is welcome; please point out any problems or deficiencies.

Test SQL:
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=#

-- Test SQL queries
explain select * from t_analyze_mcv where id = -1; -- 1 row, low out-of-MCV-range: compute sumcommon directly, skip comparisons against other MCV values
explain select * from t_analyze_mcv where id = 0; -- 18 rows, match first MCV element: lookup completes immediately
explain select * from t_analyze_mcv where id = 5; -- 18 rows, within MCV range, present in list: found via binary search
explain select * from t_analyze_mcv where id = 10; -- 1 row, within MCV range, not present in list: compute sumcommon directly after binary-search miss
explain select * from t_analyze_mcv where id = 12; -- 20 rows, match last MCV element: lookup completes immediately
explain select * from t_analyze_mcv where id = 13; -- 1 row, high out-of-MCV-range: compute sumcommon directly, skip comparisons against other MCV values

regards,
--
ZizhuanLiu (X-MAN) 
44973863(at)qq(dot)com