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/[email protected] 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) [email protected]
v1-0001-Optimize-MCV-stats-for-sortable-types-and-utilize.patch
Description: Binary data
