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

I write:
>Original
>From: ZizhuanLiu X-MAN <44973863(at)qq(dot)com>
>Date: 2026-10-17 20:06
>To: pgsql-hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
>Cc: Ilia Evdokimov <ilya(dot)evdokimov(at)tantorlabs(dot)com>, tgl <tgl(at)sss(dot)pgh(dot)pa(dot)us>, tomas <tomas(at)vondra(dot)me>, dean.a.rasheed <dean(dot)a(dot)rasheed(at)gmail(dot)com>, guofenglinux <guofenglinux(at)gmail(dot)com>
>Subject: Re: Optimize MCV stats for sortable types and utilize sorted-order properties
>......
>The results are as follows:
> - var_eq_const(): The patch version is, on average, 43.88% faster than master.
> - mcv_selectivity(): The patch version is, on average, 39.02% faster than master.
>......

Hi,

Using the same testing methodology, I also tested eqjoinsel(), mergejoinscansel(), and EXPLAIN planning time.

The results are summarized below.
- Execution plans: Master and the patch produce identical plans for the tested SQL cases.
See the 02-stats_data_explain sheet in the attached XLS file.
- Performance: The patch shows substantial improvements in both eqjoinsel() and mergejoinscansel(),
as well as in planning time. See the 03-Raw_test_data_analyze and 03-test_data_analyze_2 sheets.

Some measurements for master were anomalous. To make the comparison fairer, 03-test_data_analyze_2 excludes
those anomalous master measurements and recalculates the results using the remaining measurements and the
same methodology for both master and the patch. The results from both data sets are shown below.

Metric 03-Raw_test_data_analyze 03-test_data_analyze_2
eqjoinsel() 96.46% 95.08%
mergejoinscansel() 80.23% 74.17%
EXPLAIN planning time 91.90% 89.05%

These results mark an important milestone in my testing. Based on the current test cases,
the SQL scenarios, relevant functions, and observed performance improvements are summarized below.

1. Scalar equality
- sql
SELECT FROM t WHERE col1 = const;
- Function: var_eq_const()
- Average performance improvement: 43.88%

2. Scalar inequality comparisons
- sql
SELECT FROM t WHERE col1 < const;
SELECT FROM t WHERE col1 <= const;
SELECT FROM t WHERE col1 > const;
SELECT FROM t WHERE col1 >= const;
- Function: mcv_selectivity()
- Average performance improvement: 39.02%

3. Join-related queries
- sql
SELECT FROM t1 WHERE col1 IN (SELECT col2 FROM t2);
SELECT FROM t1, t2 WHERE t1.col1 = t2.col2;
- eqjoinsel(): average performance improvement of 95.08%
- mergejoinscansel(): average performance improvement of 74.17%
- EXPLAIN planning time: average improvement of 89.05%

These results are encouraging, although the current SQL scenarios may not cover all relevant workloads.
The patch could also affect other planning scenarios, and I would particularly appreciate feedback on
cases that might regress or show substantially different performance.

I would be grateful for any feedback on the test coverage, the interpretation of these results, or additional
scenarios that would be useful to test. If anyone has observed regressions or has suggestions for improving
the implementation, I would welcome the opportunity to investigate them.

Thank you for your time and feedback.

The following scripts were used to run the tests:
DROP TABLE IF EXISTS t_eqjoinsel_mergejoinscansel_1;
CREATE TABLE t_eqjoinsel_mergejoinscansel_1(name text COLLATE case_insensitive);
ALTER TABLE t_eqjoinsel_mergejoinscansel_1 ALTER COLUMN name SET STATISTICS 10000;

DROP TABLE IF EXISTS t_eqjoinsel_mergejoinscansel_2;
CREATE TABLE t_eqjoinsel_mergejoinscansel_2(name text COLLATE case_insensitive);
ALTER TABLE t_eqjoinsel_mergejoinscansel_2 ALTER COLUMN name SET STATISTICS 10000;

select attrelid,attname,attstattarget from pg_catalog.pg_attribute where attrelid in ('t_eqjoinsel_mergejoinscansel_1'::regclass, 't_eqjoinsel_mergejoinscansel_2'::regclass) and attnum = 1;

INSERT INTO t_eqjoinsel_mergejoinscansel_1 SELECT repeat( 'PostgreSQL', 100) || to_char(101 - g, '099') FROM generate_series(1, 100) g;
INSERT INTO t_eqjoinsel_mergejoinscansel_1 SELECT repeat( 'PostgreSQL', 100) || to_char(101 - g, '099') FROM generate_series(1, 100) g;

insert into t_eqjoinsel_mergejoinscansel_2 select * from t_eqjoinsel_mergejoinscansel_1;

DO $$
BEGIN
FOR i IN 1..100 LOOP
INSERT INTO t_eqjoinsel_mergejoinscansel_2 SELECT repeat( 'PostgreSQL', 100) || to_char(g, '099') FROM generate_series(i, 100) g;
END LOOP;
END $$;

with t1 as (select substring(name FOR 10) || '...' || substring(name FROM 1002 FOR 3) as name from t_eqjoinsel_mergejoinscansel_1)
select * from (select name ,count(*) as my_count from t1 group by name) order by 2,1 ;

with t1 as (select substring(name FOR 10) || '...' || substring(name FROM 1002 FOR 3) as name from t_eqjoinsel_mergejoinscansel_2)
select * from (select name ,count(*) as my_count from t1 group by name) order by 2,1 ;

----------------

analyze t_eqjoinsel_mergejoinscansel_1, t_eqjoinsel_mergejoinscansel_1;

----------------
WITH s AS (SELECT stakind1,stanumbers1, stavalues1::text AS values_text
FROM pg_catalog.pg_statistic
WHERE starelid = 't_eqjoinsel_mergejoinscansel_1'::regclass AND staattnum = 1
),
v AS ( SELECT ordinality AS n, value
FROM s, LATERAL unnest( string_to_array(trim(both '{}' FROM values_text), ',' ) )
WITH ORDINALITY AS u(value, ordinality)
),
f AS ( SELECT ordinality AS n, frequency
FROM s, LATERAL unnest(stanumbers1)
WITH ORDINALITY AS u(frequency, ordinality)
)
,
s2 AS (SELECT stakind1,stanumbers1, stavalues1::text AS values_text
FROM pg_catalog.pg_statistic
WHERE starelid = 't_eqjoinsel_mergejoinscansel_2'::regclass AND staattnum = 1
),
v2 AS ( SELECT ordinality AS n, value
FROM s2, LATERAL unnest( string_to_array(trim(both '{}' FROM values_text), ',' ) )
WITH ORDINALITY AS u(value, ordinality)
),
f2 AS ( SELECT ordinality AS n, frequency
FROM s2, LATERAL unnest(stanumbers1)
WITH ORDINALITY AS u(frequency, ordinality)
)
select * from (
SELECT 't_eqjoinsel_mergejoinscansel_1' as relname, CASE
when s.stakind1 = 1 then '1-STATISTIC_KIND_MCV'
when s.stakind1 = 8 then '8-STATISTIC_KIND_MCV_VALUE_SORTED'
else NULL END AS MCV_TYPE
,length(v.value) as length
,v.n as no, substring(v.value FOR 10) || '...' || substring(v.value FROM 1003 FOR 3) value, f.frequency
FROM v JOIN f USING(n) JOiN s ON 1=1
and substring(v.value FROM 1003 FOR 3)
in ('000', '001',
'010', '020', '030', '040', '050', '060', '070', '080', '090', '100')
ORDER BY v.n
)
union all
(
SELECT 't_eqjoinsel_mergejoinscansel_2' as relname, CASE
when s.stakind1 = 1 then '1-STATISTIC_KIND_MCV'
when s.stakind1 = 8 then '8-STATISTIC_KIND_MCV_VALUE_SORTED'
else NULL END AS MCV_TYPE
,length(v.value) as length
,v.n as no, substring(v.value FOR 10) || '...' || substring(v.value FROM 1003 FOR 3) value, f.frequency
FROM v2 as v JOIN f2 as f USING(n) JOiN s2 as s ON 1=1
and substring(v.value FROM 1003 FOR 3)
in ('000', '001',
'010', '020', '030', '040', '050', '060', '070', '080', '090', '100')
ORDER BY v.n
);

--generate 07-eqjoinsel_mergejoinscansel.sql
>07-eqjoinsel_mergejoinscansel.sql
for cf in 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2; do echo "explain (SUMMARY, COSTS off) select * from t_eqjoinsel_mergejoinscansel_1 where name in (select name from t_eqjoinsel_mergejoinscansel_2);">>07-eqjoinsel_mergejoinscansel.sql; done

08-test_eqjoinsel_mergejoinscansel.sh
cat 07-eqjoinsel_mergejoinscansel.sql|psql xman7|grep "Planning Time"

-- run 08-test_eqjoinsel_mergejoinscansel.sh

>07-eqjoinsel_mergejoinscansel.out
sh 08-test_eqjoinsel_mergejoinscansel.sh >07-eqjoinsel_mergejoinscansel.out 2>&1

--get test result data
--1st eqjoinsel
cat 07-eqjoinsel_mergejoinscansel.out|grep "eqjoinsel()"|grep -n "eqjoinsel()"|awk 'NR%2==1' | awk '{print $NF'}
--2st eqjoinsel
cat 07-eqjoinsel_mergejoinscansel.out|grep "eqjoinsel()"|grep -n "eqjoinsel()"|awk 'NR%2==0' | awk '{print $NF'}
cat 07-eqjoinsel_mergejoinscansel.out|grep "mergejoinscansel()"|awk '{print $NF}'
cat 07-eqjoinsel_mergejoinscansel.out|grep "e:"|awk -F 'e:' '{print $2}'|awk '{print $1}'|sed 's/NOTICE://g'

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