Re: Optimize MCV stats for sortable types and utilize sorted-order properties - Mailing list pgsql-hackers

>I write
>From: ZizhuanLiu X-MAN <44973863@qq.com>
>Date: Sep 17, 2026 10:01
>To: ZizhuanLiu X-MAN <44973863@qq.com>, pgsql-hackers <pgsql-hackers@lists.postgresql.org>
>Cc: tgl <tgl@sss.pgh.pa.us>, ilya.evdokimov <ilya.evdokimov@tantorlabs.com>
>Subject: Re: Optimize MCV stats for sortable types and utilize sorted-order properties
>......
>There is another fundamental issue:
>    If the new-version compute_scalar_stats() no longer generates STATISTIC_KIND_MCV, but third-party code or
extensionstry 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
returningit 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.


Looking at the call graph in LIST-1:
  When a caller requests STATISTIC_KIND_MCV but only STATISTIC_KIND_MCV_VALUE_SORTED is available in the system,
some reordering is required.

Based on how these callers consume the data, we only need to swap the entry with the largest number[i] and its
corresponding values[i] into slot [0], **rather than performing a full sort of the entire array**.

As shown by the logic in LIST-1: existing callers either rely on slot [0] holding the entry with the highest count
 (the original behaviour of STATISTIC_KIND_MCV), or iterate over the number[] / values[] arrays.

Simply swapping the maximum-count entry to index [0] is sufficient to preserve backward compatibility. This keeps
the adjustment minimal: it requires N comparisons over the double-typed number[] array and at most one two-element
swap,
so the overhead is kept as small as possible.

I will go ahead and implement along these lines. Deep insights and further feedback are very welcome.


>=== LIST-1 ===
                                                                                         
>
                                                                                         
>src/backend/commands/analyze.c
                                                                                         
>  static void compute_distinct_stats() —   producer  ; generates MCV statistics for data types that only have the "="
operator.                                                                                
>  static void compute_scalar_stats() —   producer  ; generates MCV statistics for data types that have both "=" and
"<"operators.                                                                              
>
                                                                                         
>src/backend/executor/nodeHash.c
                                                                                         
>  static void ExecHashBuildSkewHash() —   consumer  ; reads the MCV list and iterates through it, accumulating
sslot.numbers[i].                                                                               
>
                                                                                         
>src/backend/statistics/attribute_stats.c
                                                                                         
>  static bool attribute_statistics_update_internal() —   producer  ; generates MCV statistics from the input
parametersusing statatt_build_stavalues() and updates the MCV statistics with statatt_set_slot(). 
>
                                                                                         
>src/backend/statistics/extended_stats_funcs.c
                                                                                         
>  static Datum import_pg_statistic() —   producer  ; generates MCV statistics from JSONB input.
                                                                                        
>
                                                                                         
>src/backend/utils/adt/network_selfuncs.c
                                                                                         
>  static Selectivity networkjoinsel_inner() —   consumer  ; reads the MCV list and either accumulates mcv_numbers[i]
orcompares values for equality using "=".                                                 
>  static Selectivity networkjoinsel_semi() —   consumer  ; reads the MCV list and either accumulates mcv_numbers[i] or
comparesvalues for equality using "=".                                                  
>
                                                                                         
>src/backend/utils/adt/selfuncs.c
                                                                                         
>  double var_eq_const() —   consumer  ; reads the MCV list, compares values using "=", obtains the selectivity of a
matchingvalue, and accumulates sslot.numbers when there is no match.                       
>  double var_eq_non_const() —   consumer  ; reads the MCV statistics and currently uses sslot.numbers[0], i.e., the
largestselectivity.                                                                        
>  double mcv_selectivity() —   consumer  ; reads the MCV list, checks each value against the comparison condition, and
accumulatesthe corresponding selectivities.                                             
>  double ineq_histogram_selectivity() —   consumer  ; reads the MCV statistics but only uses mcvslot.nnumbers.
                                                                                        
>  Selectivity booltestsel() —   consumer  ; reads the first MCV element. If the first element is true, it uses
sslot.numbers[0];otherwise, it uses 1.0 - sslot.numbers[0] - freq_null.                         
>  Datum eqjoinsel() —   consumer  ; apart from the hash algorithm, iterates through the MCV list and compares values
using"=".                                                                                 
>  void estimate_hash_bucket_stats() —   consumer  ; uses the first/largest-selectivity element by taking  mcv_freq =
sslot.numbers[0].                                                                         
>  static bool get_variable_range() —   consumer  ; iterates through the MCV list and compares values using "=".

regards,
--
ZizhuanLiu (X-MAN) 
44973863@qq.com