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

Discussion: MCV statistics ordering and compatibility

Hi,

I'd like to share some thoughts on the current design and propose an alternative approach for discussion.

1. Current approach
The current approach is to modify compute_scalar_stats() so that:
- For non-sortable data types, we continue to generate kind 1 (STATISTIC_KIND_MCV),
with MCV entries sorted by frequency (numbers[]).
- For sortable data types, we generate only kind 8 (STATISTIC_KIND_MCV_VALUE_SORTED),
with MCV entries sorted by value (values[]).

2. Potential performance benefits
Several planner functions can benefit from having MCV entries sorted by value, including
var_eq_const(), var_eq_non_const(), mcv_selectivity(), ineq_histogram_selectivity(), booltestsel(),
eqjoinsel(), and get_variable_range().

These functions handle operations such as =, <, <=, >, >=, !=, equality joins, and retrieving the
minimum and maximum values from statistics.

When value-sorted MCV statistics are available, operations that need to compare MCV values
can take advantage of boundary checks or binary search. Depending on the specific operation,
this can reduce the number of comparisons from O(N) or O(N2) to O(1) or O(log N), respectively.
This substantially reduces the number of value comparisons and the associated cost of potentially
expensive comparison functions.

(I haven't yet evaluated the impact on networkjoinsel_inner() and networkjoinsel_semi().)

The function-level and EXPLAIN timing results are available in [4]. These measurements were taken
using a debug build; I'll provide additional results using a release build later.

3. Compatibility concerns with the current approach
Although we can adjust the relevant internal logic to accommodate the new statistics kind, changing
the existing MCV representation may break compatibility for consumers that obtain MCV statistics
through hooks or the pg_stats, pg_stats_ext, and pg_stats_ext_exprs views.

Maintaining compatibility in statistics import/export and pg_dump-related functionality also becomes
difficult, particularly when the statistics kind (1 or 8) needs to be preserved and propagated.

See [5] for more details.

4. An alternative approach: generate both kinds of MCV statistics
After studying the discussions in [1], [2], and [3], I've been considering another approach:

For sortable data types, generate both:
- Kind 1 (STATISTIC_KIND_MCV), with entries sorted by frequency.
- Kind 8 (STATISTIC_KIND_MCV_VALUE_SORTED), with entries sorted by value.

This could address the compatibility concerns described in point 3, while allowing the planner to use
whichever representation is more appropriate for a particular operation.

However, this approach introduces two concerns:

4.1. Additional statistics slot
It would exceed the current limit of five statistics slots (STATISTIC_NUM_SLOTS), potentially requiring
us to increase the limit to six, along with the corresponding catalog changes and related adjustments.

For example, I have observed the following slot usage for an array column with a low statistics target:
stakind1 = 8
stakind2 = 2
stakind3 = 3
stakind4 = 4
stakind5 = 5

This shows that all five slots can already be occupied in some cases. Therefore, simply adding kind 1
alongside kind 8 would require an additional slot in such cases.

The SQL used to reproduce this result is provided at the end.

4.2. Duplicate-looking statistics
For sortable data types, both kinds contain the same MCV values and frequencies, differing only in
their sort order. At first glance, storing both may seem redundant.

5. Why I think storing both may be worthwhile
I don't think these two representations are redundant in terms of their purpose.

A similar analogy would be indexes on (a ASC, b ASC) and (b ASC, a ASC): they contain the same
underlying table data, but their different ordering makes them useful for different access patterns.

In this case, storing both representations is a trade-off between additional storage and better access efficiency.
It could preserve the existing frequency-sorted representation for compatibility while also providing the
value-sorted representation for planner optimizations.

Given how many common planner operations could benefit from value-sorted MCV statistics, I think the potential
benefits may justify this trade-off.

I'd appreciate your thoughts on this alternative approach. In particular, do you think maintaining both representations,
even at the cost of an additional statistics slot, is a reasonable design?

Any comments or suggestions are welcome.

[1] https://www.postgresql.org/message-id/flat/AANLkTikiruxOYh6jE_ETK7u4sEW6VXXqFK3Xn0-zVxoe%40mail.gmail.com
[2] https://www.postgresql.org/message-id/flat/AANLkTin02SOXNzFxju74Hf-uqhAmymR0-hyAodi4G0Of%40mail.gmail.com
[3] https://www.postgresql.org/message-id/flat/20111229163500.GA647%40tornado.leadboat.com#23f5d75556258244556caeb32eb2daef
[4] https://www.postgresql.org/message-id/tencent_0AD51A01E1E1DBC468A12768BEDD2C53A809%40qq.com
[5] https://www.postgresql.org/message-id/tencent_0F362A5AB80984EF5B4B1CEAA7C61AF8C907%40qq.com

sql:
DROP TABLE IF EXISTS test_array_stats;

CREATE TABLE test_array_stats
(
id int,
arr int[]
);
alter table test_array_stats alter column arr set statistics 2;

INSERT INTO test_array_stats
SELECT
i,
CASE
WHEN i % 10 = 0 THEN ARRAY[1, 2, 3]
WHEN i % 10 = 1 THEN ARRAY[1, 2, 4]
WHEN i % 10 = 2 THEN ARRAY[1, 2, 5]
WHEN i % 10 = 3 THEN ARRAY[1, 3, 4]
WHEN i % 10 = 4 THEN ARRAY[2, 3, 5]
WHEN i % 10 = 5 THEN ARRAY[3, 4, 5]
WHEN i % 10 = 6 THEN ARRAY[1, 4, 5]
WHEN i % 10 = 7 THEN ARRAY[2, 4, 5]
WHEN i % 10 = 8 THEN ARRAY[1, 2, 3, 4]
ELSE ARRAY[2, 3, 4, 5]
END
FROM generate_series(1, 100000) AS i;

alter table test_array_stats alter column arr set statistics 2;
ANALYZE test_array_stats;

select * FROM pg_statistic where starelid = 'test_array_stats'::regclass and staattnum = 2 \gx
select * FROM pg_statistic where starelid = 'test_array_stats'::regclass and staattnum = 2 \gx
-[ RECORD 1 ]-------------------------------------------------------------------
starelid | 24895
staattnum | 2
stainherit | f
stanullfrac | 0
stawidth | 33
stadistinct | 8
stakind1 | 8
stakind2 | 2
stakind3 | 3
stakind4 | 4
stakind5 | 5
staop1 | 1070
staop2 | 1072
staop3 | 1072
staop4 | 96
staop5 | 96
stacoll1 | 0
stacoll2 | 0
stacoll3 | 0
stacoll4 | 0
stacoll5 | 0
stanumbers1 | {0.20133333,0.19743334}
stanumbers2 |
stanumbers3 | {0.13585752}
stanumbers4 | {0.50303334,0.70283335,0.7971,0.5963333,0.5988333,0.0101,0.7971,0}
stanumbers5 | {3,4,3.1981332}
stavalues1 | {"{1,2,3}","{3,4,5}"}
stavalues2 | {"{1,2,3,4}","{1,3,4}","{2,4,5}"}
stavalues3 |
stavalues4 | {1,2,3,4,5}
stavalues5 |

xman7=#

n_distinct | 8
most_common_vals | {"{1,2,3}","{3,4,5}"} ==============8
most_common_freqs | {0.20133333,0.19743334} ==============8
histogram_bounds | {"{1,2,3,4}","{1,3,4}","{2,4,5}"} ==============2
correlation | 0.13585752 ==============3
most_common_elems | {1,2,3,4,5} ==============4
most_common_elem_freqs | {0.50303334,0.70283335,0.7971,0.5963333,0.5988333,0.0101,0.7971,0} ==============4
elem_count_histogram | {3,4,3.1981332} ==============5
range_length_histogram | ======6
range_empty_frac | =======6
range_bounds_histogram | =======7

xman7=#

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