I write
>From: ZizhuanLiu X-MAN <[email protected]>
>Date: Sep 16, 2026 22:49
>To: pgsql-hackers <[email protected]>
>Cc: tgl <[email protected]>, ilya.evdokimov <[email protected]>
>Subject: Re: Optimize MCV stats for sortable types and utilize sorted-order
>properties
>
>Original
>>From: ZizhuanLiu X-MAN <[email protected]>
>>Date: Sep 15, 2026 10:18
>>To: pgsql-hackers <[email protected]>
>>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)
[email protected]
