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

Hi, hackers

Optimize MCV statistics for sortable types

Preserve MCV values in ascending order for sort-comparable data types
by introducing a new statistic kind, STATISTIC_KIND_MCV_VALUE_SORTED.
This allows planner code to exploit the ordering of MCV values instead
of repeatedly comparing every MCV entry with a constant.

In compute_scalar_stats(), retain the existing MCV generation logic and
use an additional ScalarMCVItem workspace to produce the value-sorted
MCV list. For sortable types, the sorted MCV list can replace the
legacy STATISTIC_KIND_MCV entry, so no additional statistics slot is
required.

Use the sorted MCV values during selectivity estimation and range
detection. The optimizations are applied conservatively, with strict
conditions on the statistics kind, data type, collation, and operator
ordering compatibility:

* In var_eq_const(), use the minimum and maximum MCV values to quickly
determine whether the constant can match an MCV entry, and use binary
search when the constant falls within the MCV range.
* In mcv_selectivity(), use the sorted MCV values to find the range of
entries satisfying <, <=, >, or >=, avoiding per-entry operator
evaluation.
* In get_stats_slot_range(), use the first and last values of a sorted
MCV list directly when its ordering is compatible with the requested
sort operator, avoiding the O(N) scan otherwise required to determine
the minimum and maximum values.

When the conditions for these optimizations are not satisfied, retain
the existing behavior.

The optimization reduces the number of expensive MCV comparisons while
preserving the existing behavior for non-sortable types and statistics
without a compatible ordering.

Update the pg_stats view to expose STATISTIC_KIND_MCV_VALUE_SORTED through
most_common_vals and most_common_freqs.

Changes from v4:
1. Fixed compute_scalar_stats() to adjust the MCV list members according
to the result returned by analyze_mcv_list().

2. Fixed an issue in mergejoinscansel() -> get_variable_range(), where
the minimum and maximum values could be overwritten incorrectly.
Instead, get_stats_slot_range() now leverages the ordering property
of MCV values to compare and determine the minimum and maximum values.

3. The optimization for eqjoinsel_find_matches() in the following call
paths is not included in this patch due to its complexity and remains
as future work:
eqjoinsel() -> eqjoinsel_inner() -> eqjoinsel_find_matches()
eqjoinsel() -> eqjoinsel_semi() -> eqjoinsel_find_matches()

attached:
01-test_setup_for_var_eq_const(),mcv_selectivity().sql
01-test_result_for_var_eq_const(),mcv_selectivity().xlsx

02-get_variable_range()-setup_and_result.sql

03-eqjoinsel()_setup_text.sql

Today is the Mid-Autumn Festival in China.
Wish everyone a happy Mid-Autumn Festival, with a full moon, happiness,
and wonderful moments with family and friends.

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