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) [email protected]
