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

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) 
44973863(at)qq(dot)com