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

Subject: ANALYZE correctness and performance testing

Hi hackers,

The patch is now reaching a relatively complete stage, and all CFBot tests are passing.
I am now starting to evaluate its correctness and performance more systematically.

As the first step, I focused on the ANALYZE side, particularly on the correctness of
generating value-sorted MCV statistics and the performance overhead of collecting them.

For the test, I created a table with 100,020 rows and set the statistics target to 10,000.
Most values occur 10 times, while three values have slightly higher frequencies.

The resulting MCV statistics show the expected difference between v14 and the current master.
With v14, where STATISTIC_KIND_MCV_VALUE_SORTED is used, the MCV values are sorted by value:
mcv_type | no | value | frequency
-----------------------------------+----+------------------+-------------
8-STATISTIC_KIND_MCV_VALUE_SORTED | 1 | "PostgreSQL 001" | 0.10002
8-STATISTIC_KIND_MCV_VALUE_SORTED | 2 | "PostgreSQL 002" | 0.099980004
8-STATISTIC_KIND_MCV_VALUE_SORTED | 3 | "PostgreSQL 003" | 0.099980004
8-STATISTIC_KIND_MCV_VALUE_SORTED | 4 | "PostgreSQL 004" | 0.099980004
8-STATISTIC_KIND_MCV_VALUE_SORTED | 5 | "PostgreSQL 005" | 0.10003999
8-STATISTIC_KIND_MCV_VALUE_SORTED | 6 | "PostgreSQL 006" | 0.099980004
8-STATISTIC_KIND_MCV_VALUE_SORTED | 7 | "PostgreSQL 007" | 0.099980004
8-STATISTIC_KIND_MCV_VALUE_SORTED | 8 | "PostgreSQL 008" | 0.099980004
8-STATISTIC_KIND_MCV_VALUE_SORTED | 9 | "PostgreSQL 009" | 0.099980004
8-STATISTIC_KIND_MCV_VALUE_SORTED | 10 | "PostgreSQL 010" | 0.10007998
(10 rows)

In contrast, on master, the MCVs are sorted by frequency:
mcv_type | no | value | frequency
----------------------+----+------------------+-------------
1-STATISTIC_KIND_MCV | 1 | "PostgreSQL 010" | 0.10007998
1-STATISTIC_KIND_MCV | 2 | "PostgreSQL 005" | 0.10003999
1-STATISTIC_KIND_MCV | 3 | "PostgreSQL 001" | 0.10002
1-STATISTIC_KIND_MCV | 4 | "PostgreSQL 002" | 0.099980004
1-STATISTIC_KIND_MCV | 5 | "PostgreSQL 003" | 0.099980004
1-STATISTIC_KIND_MCV | 6 | "PostgreSQL 004" | 0.099980004
1-STATISTIC_KIND_MCV | 7 | "PostgreSQL 006" | 0.099980004
1-STATISTIC_KIND_MCV | 8 | "PostgreSQL 007" | 0.099980004
1-STATISTIC_KIND_MCV | 9 | "PostgreSQL 008" | 0.099980004
1-STATISTIC_KIND_MCV | 10 | "PostgreSQL 009" | 0.099980004
(10 rows)

This is also consistent with the intended design: the new statistic kind keeps the
MCV values sorted by value while preserving the corresponding frequencies.

For the ANALYZE performance, I ran 100 consecutive ANALYZE operations in each case.
The total time was:
1st 2nd 3rd 4th avg
================================================================
v14: 22510.146 23805.940 24146.746 24869.801 23833.158
master: 22407.108 23095.573 24068.918 23933.353 23376.238
This corresponds to approximately:
v14: 238.33 ms / ANALYZE
master: 233.76 ms / ANALYZE

So, for this particular test case, the additional cost is about 1.95% per ANALYZE.

I would appreciate any feedback on whether this is a reasonable way to evaluate the
ANALYZE-side overhead, and whether there are other representative workloads or
cases that would be useful to test.

In particular, comments from people familiar with analyze.c, MCV generation, or statistics
collection would be very helpful. I'm also interested in whether the current implementation
introduces any unnecessary work that could be optimized further.
As the next step, I plan to measure the performance impact on the different consumers of
these statistics, including the relevant equality/range comparison and join selectivity estimation paths.

Thanks in advance for any review and suggestions.

The test SQL and the corresponding results are as follows:
---------------------
DROP TABLE IF EXISTS t_sort_mcv_100;
CREATE TABLE t_sort_mcv_100(name text);
ALTER TABLE t_sort_mcv_100 ALTER COLUMN name SET STATISTICS 10000;

select attname,attstattarget from pg_catalog.pg_attribute where attrelid = 't_sort_mcv_100'::regclass and attnum = 1;

DO $$
DECLARE i int := 0;
BEGIN
LOOP
EXIT WHEN i >= 10000;
i := i + 1;
INSERT INTO t_sort_mcv_100 SELECT repeat( 'PostgreSQL', 1) || to_char(g, '099') FROM generate_series(1, 10) g;
END LOOP;
END $$;

INSERT INTO t_sort_mcv_100 SELECT repeat( 'PostgreSQL', 1) || ' 010' FROM generate_series(1, 10) g;
INSERT INTO t_sort_mcv_100 SELECT repeat( 'PostgreSQL', 1) || ' 005' FROM generate_series(1, 6) g;
INSERT INTO t_sort_mcv_100 SELECT repeat( 'PostgreSQL', 1) || ' 001' FROM generate_series(1, 4) g;

select count(*) from t_sort_mcv_100;

---------------------
\timing on

DO $$
DECLARE i int := 0;
BEGIN
LOOP
EXIT WHEN i >= 100;
i := i + 1;
ANALYZE t_sort_mcv_100;
END LOOP;
END $$;

---------------------
WITH s AS (SELECT stakind1,stanumbers1, stavalues1::text AS values_text
FROM pg_catalog.pg_statistic
WHERE starelid = 't_sort_mcv_100'::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)
)
SELECT 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
,v.n as no, v.value, f.frequency
FROM v JOIN f USING(n) JOiN s ON 1=1
ORDER BY v.n;

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