Subject: MCV optimization: design, evolution, trade-offs, and current results (v16)
Hi This proposal reduces planner CPU work by storing MCV entries in value order, so selectivity estimation can avoid repeated predicate calls. It uses the existing per-column/per-expression MCV data. The current v16 design preserves frequency order as well; its storage and catalog costs still need to be justified by performance evidence. The design evolved as follows: - Master: Representation: Kind 1, decreasing frequency order; five slots; Reason and trade-off: Supports frequency-based consumers; value lookups usually scan the list. - Earlier patches, including v6–v15: Representation: Kind 8 replaces kind 1 for sortable types; five slots; Reason and trade-off: Adds value ordering without a second stored copy, but changes existing MCV consumers and view semantics. - v16: Representation: Keep kind 1 and add kind 8; six slots; Reason and trade-off: Preserves the existing frequency-ordered representation, at the cost of duplicated MCV data and a catalog change. The replacement design also required propagating the representation kind through import/export interfaces. An attempt to retrieve it by joining the public statistics views to pg_statistic caused permission failures. Exposing the kind alone would still leave consumers that assume frequency order incompatible. These issues motivated the paired design. In v16, ANALYZE selects the ordinary kind-1 members first, then generates kind 8 from exactly those value-frequency pairs. Sorting their positions in the already sorted sample supplies value order and is reused for histogram construction. Kind 1 records =, kind 8 records the actual < ordering operator, and both record the same collation. This avoids reconstructing the ordering from equality metadata. Consumers use the two representations as follows: - var_eq_const(): Use of value order: Endpoint checks and binary search for compatible equality; frequency order remains available for first-match scans. - mcv_selectivity(): Use of value order: Find a qualifying prefix/suffix for <, <=, >, >=, instead of evaluating the predicate for every MCV. - eqjoinsel() and matching helpers: Use of value order: Merge matching for two ordered lists, or binary- search probes with one ordered input, on eligible non-hash paths. Semi/anti-join top-k selection is by frequency, retaining value order afterward. - mergejoinscansel(): Use of value order: Estimate merge-join scan start/end fractions using input ranges and inequality selectivity. Benefits indirectly from ordered MCV endpoints through the range helpers, and eligible mcv_selectivity() fast paths via scalarineqsel(). - get_variable_range() / get_stats_slot_range(): Use of value order: Use endpoints when the stored ordering and requested ordering/collation agree. The histogram excludes MCVs, so histogram bounds alone cannot replace these MCV operations. The complexity improvement concerns value comparisons: frequency summation, array loading, and top-k preparation can still require linear work or sorting. Ordered comparisons require compatible operators, types, collation, and permission to invoke the actual comparator. Other cases retain predicate evaluation, using kind 1 where first-match frequency order matters. get_attstatsslot_mcv() supports explicit representation selection and metadata-only probes. Network selectivity code continues to use kind 1. Existing MCV columns in pg_stats and pg_stats_ext_exprs continue to expose kind 1; separate most_common_vals_value_sorted / most_common_freqs_value_sorted columns expose kind 8. Import, pg_dump, and postgres_fdw are updated. Ordinary-column and expression imports share validation: allow neither kind, kind 1 alone, or a consistent pair; reject kind 8 alone. Validate ordering, operators/collation, and matching pairs, including partial updates. The additional slot is needed because array statistics can already occupy five slots. This changes catalog layout, increases fixed metadata, and duplicates the logical MCV value/frequency payload where kind 8 exists. It does not imply that the whole pg_statistic relation doubles. The patch touches 27 files, with 3,445 insertions and 243 deletions, including comments, SQL, and expected output. Earlier performance reports used debug builds. The release reruns did not reproduce those speedup magnitudes. Overall Planning Time reductions below use arithmetic means; pooled-median reductions appear in parentheses. Positive means faster than master. Case v15 vs master v16 vs master -------- ----------------- ----------------- int4 =51 −50.58% (−2.56%) −5.22% (−2.56%) int4 <51 −13.38% (−5.26%) −6.39% (−2.63%) int4 IN +9.08% (+7.26%) +14.30% (+8.87%) text IN +13.24% (+19.25%) +15.80% (+18.01%) These runs used master 8b529705d153, -O2, assertions/debug disabled, and timing/NOTICE code removed. Fresh instances had 20,000 rows and 100 MCVs; text used 12-character strings with C collation. Twenty serial rounds rotated version order; each connection discarded two warmups and measured 102 EXPLAINs. Outliers particularly affect v15's equality mean. Build settings and baseline differ from the earlier report, so the cause of the gap is unresolved. All versions used hash threshold 202, keeping 100+100 MCVs on non-hash paths. Default release uses 200; benefits over that default hash path remain unproven. The scalar cases show no overall benefit, and v16 is not uniformly better than v15 across summaries. The historical v15 snapshot also has a join-estimate defect: a diagnostic query gives 3.96M rows instead of 4M; v16 agrees with master and the actual result. For imported frequency ties, value-based top-k tie-breaking can choose different members from a kind-1 prefix; this is documented. Remaining review points include that policy, additional coverage/test portability, default-hash and fallback-path costs, and crossover thresholds. Network code has only adaptation changes. The local snapshot also retains diagnostic timers and the 202 override, which must be separated from a production patch. Thread: https://www.postgresql.org/message-id/flat/tencent_0489DF3C961BD4D48D32F04F6D6EB4301308%40qq.com Release results: https://www.postgresql.org/message-id/tencent_5E363FDABF09F7EF03CB7A6AEEC60D78A307%40qq.com Earlier debug results: https://www.postgresql.org/message-id/tencent_0AD51A01E1E1DBC468A12768BEDD2C53A809%40qq.com Regards, ZizhuanLiu (X-MAN) regards, -- ZizhuanLiu (X-MAN) [email protected]
