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

I write
>From: ZizhuanLiu X-MAN <44973863(at)qq(dot)com>
>Date: Sep 16, 2026 22:49
>To: pgsql-hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
>Cc: tgl <tgl(at)sss(dot)pgh(dot)pa(dot)us>, ilya.evdokimov <ilya(dot)evdokimov(at)tantorlabs(dot)com>
>Subject: Re: Optimize MCV stats for sortable types and utilize sorted-order properties
>
>Original
>>From: ZizhuanLiu X-MAN <44973863(at)qq(dot)com>
>>Date: Sep 15, 2026 10:18
>>To: pgsql-hackers <pgsql-hackers(at)lists(dot)postgresql(dot)org>
>>Subject: Optimize MCV stats for sortable types and utilize sorted-order properties
>>......
>>Optimize MCV stats for sortable types and utilize sorted-order properties.
>>
>>1.Preserve ascending-ordered MCV values for sort-comparable types when filling
>>pg_statistic. In compute_scalar_stats(), retain existing logic and allocate
>>extra ScalarMCVItem workspace to hold sorted MCV entries.
>>
>>2.When applying statistics, use the pre-sorted MCV list:
>>-compare against min/max boundaries. Boundary hits finish in 1-2 comparisons.
>>-Values inside MCV range use binary-search (average N/2 -> log(n)).
>>-Values outside MCV range skip full MCV iteration (N -> at most 2 comparisons).
>
>
>Hi, hackers,
>
>After investigating the files and functions related to STATISTIC_KIND_MCV, I classified their
>roles (producer or consumer) and how MCV statistics are produced or consumed, as shown
>in the list below (LIST-1). Taking third-party extensions and end users into consideration as well,
>the consumers can be broadly classified as follows:
>0. Final update of the statistics data: attribute_statistics_update_internal()
>1. Producers: compute_distinct_stats(), compute_scalar_stats(), and import_pg_statistic()
>2. Consumers, which can be classified according to how they consume MCV statistics:
> 2.1. Iterate through the MCV list, compare values using "=", and either select the selectivity
> of a matching value or accumulate selectivities.
> 2.2. Ignore the values and only use the number of elements in the list/array, or unconditionally
> accumulate the selectivities.
> 2.3. Only use the first element (the one with the highest selectivity).
>
>After careful consideration, my initial proposal is as follows:
>1. Add a new statistics kind:
> #define STATISTIC_KIND_MCV_VALUE_SORTED 8
>
>Unlike STATISTIC_KIND_MCV, which is ordered by frequency, STATISTIC_KIND_MCV_VALUE_SORTED
>stores MCVs ordered by their values. STATISTIC_KIND_MCV_VALUE_SORTED and STATISTIC_KIND_MCV
>will not coexist, so the number of statistics slots will not exceed the STATISTIC_NUM_SLOTS limit.
>
>2. Only change the producer compute_scalar_stats() to generate the new MCV kind, STATISTIC_KIND_MCV_VALUE_SORTED.
> This should introduce almost no additional performance overhead (see the path/code snippet in my previous email).
>If STATISTIC_KIND_MCV already exists, it will be updated or replaced by STATISTIC_KIND_MCV_VALUE_SORTED.
>
>3. Adjust the consumers described above as follows:
> 2.1. Iterate through the MCV list, compare values using "=", and select the matching selectivity or accumulate selectivities.
> This is the more complicated case, which I discuss in detail below.
> 2.2. Ignore the values and only use the number of elements in the list/array, or unconditionally accumulate selectivities.
> --> No change is required.
> 2.3. Only use the first element (the one with the highest selectivity).
> --> Behavior needs to be adjusted: iterate through numbers[] and find the maximum selectivity.
> The performance impact should be controllable.
>
>Here I would like to discuss case 2.1 in more detail: iterating through the MCV list, comparing values using "=",
>and selecting a matching selectivity or accumulating selectivities.
>A. If a data type only has "=", the MCV statistics are generated by compute_distinct_stats().
> Therefore, only STATISTIC_KIND_MCV exists, and it can continue to be fetched and used in the existing way.
>
>B. If a data type has both "=" and "<", prefer STATISTIC_KIND_MCV_VALUE_SORTED when fetching the MCV statistics.
> If it is not available, fall back to STATISTIC_KIND_MCV.
> 2.1.1. If STATISTIC_KIND_MCV is available, use it exactly as before.
> 2.1.2. If STATISTIC_KIND_MCV_VALUE_SORTED is available and the collations are equal, we can consider using
> the value ordering to optimize the lookup. For example:
> - First check whether the constant is within the range of the MCV values.
> - If it is within the range, use binary search to locate the matching value.
> - If it is outside the range, there is no need to compare it with every MCV value; we can directly use sumcommon.
> Otherwise, if the collations are not equalbe, have the same as with STATISTIC_KIND_MCV.
>
>Case B will exist for a long time during upgrades/migration, because different tables may
>have either STATISTIC_KIND_MCV_VALUE_SORTED or STATISTIC_KIND_MCV, unless this is a completely new database.
>
>Based on my review of the relevant code and the function list in LIST-1,
>my current assessment is that this approach is feasible and that the associated risks appear manageable.
>
>As discussed here and in my previous email, the potential benefit can be significant.
>In particular, var_eq_const() and mcv_selectivity() can greatly reduce the number of relatively expensive value comparisons.
>eqjoinsel() and get_variable_range() may also benefit significantly, although I have not analyzed them in detail yet.
>
>My biggest concern, however, is third-party/extension consumers of STATISTIC_KIND_MCV.
>Their behavior is not something we can fully control or adjust at the PostgreSQL core level.
>Since the ordering of the MCV values would change, an extension may be relying on the first
>element being the MCV with the highest frequency, for example. Such assumptions could therefore be affected significantly.
>I have not yet found a good solution for this potential compatibility issue.

There is another fundamental issue:
If the new-version compute_scalar_stats() no longer generates STATISTIC_KIND_MCV, but third-party code or extensions try to fetch STATISTIC_KIND_MCV. When only STATISTIC_KIND_MCV_VALUE_SORTED exists in the system,
- should get_attstatsslot() re-sort STATISTIC_KIND_MCV_VALUE_SORTED by numbers[] in ascending order before returning it to the caller?
(This re-sort cost should be manageable, since we sort on numbers[], not on values[].)
- Or should we return STATISTIC_KIND_MCV_VALUE_SORTED directly without any processing?

For good backward-compatibility, I lean toward the former option, though it is not a very elegant design.

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