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

Hi hackers,

Based on v5, I made the following changes in v6:
0. compute_scalar_stats(): Use a lightweight algorithm to generate MCVs with values[] sorted.
1. In mcv_selectivity(), use get_ordering_op_properties(operatoroid) to obtain the CompareType for the operator.
2. Simplify the non-hash path in eqjoinsel_find_matches().
The new implementation only handles the !op_is_reversed case, and only when sslot2 uses
MCV_SPECIAL_COMPARE_THRESHOLD. When op_is_reversed is true, the matching logic becomes considerably
more complicated. For sslot2 with MCV_SPECIAL_COMPARE_THRESHOLD, we can use the min/max values and
binary search to find the matching range.

The conditions for enabling the new logic are currently intentionally quite strict and conservative,
as described in the commit message:
> Use the sorted MCV values during selectivity estimation and range
> detection. The optimizations are applied conservatively, with strict
> conditions on the statistics kind, collation, data type, and operator
> ordering compatibility.

I have verified the functional correctness of v6 and debugged the implementation.
I also compared the patched version with an unpatched version. The query plans and
row-count estimates I observed were consistent between the two versions.

In addition, after initdb, I ran the following query on both versions:
sql
select schemaname,tablename,attname,attnum,inherited,null_frac,avg_width,
n_distinct,most_common_vals,most_common_freqs,histogram_bounds,correlation,
most_common_elems,most_common_elem_freqs,elem_count_histogram,
range_length_histogram,range_empty_frac,range_bounds_histogram
from pg_catalog.pg_stats
order by 1,2,3,4,5,6
\gx

The difference I observed was the ordering of the elements in most_common_vals and most_common_freqs.
Before the patch, they were ordered by most_common_freqs in descending order. With the patch, they are
ordered by most_common_vals in ascending order.
There is one issue that I have not figured out yet.
When accessing the underlying catalog table directly, running the query interactively in psql xman7 displays
he values of most_common_vals and most_common_freqs correctly.
However, when I run the same SQL through:
sh
cat xxxx.sql | psql xman7
the values of these two columns are not displayed.

I am not sure yet whether this is related to the patch or to how psql handles the output in this case.
Any suggestions on where I should look would be appreciated.

The SQL is as follows:
select * from (
SELECT n.nspname AS schemaname,
c.relname AS tablename,
a.attname,
a.attnum,
s.stainherit AS inherited,
s.stanullfrac AS null_frac,
s.stadistinct AS n_distinct,
CASE
WHEN s.stakind1 = 1 THEN 1
WHEN s.stakind2 = 1 THEN 1
WHEN s.stakind3 = 1 THEN 1
WHEN s.stakind4 = 1 THEN 1
WHEN s.stakind5 = 1 THEN 1
WHEN s.stakind1 = 8 THEN 8
WHEN s.stakind2 = 8 THEN 8
WHEN s.stakind3 = 8 THEN 8
WHEN s.stakind4 = 8 THEN 8
WHEN s.stakind5 = 8 THEN 8
ELSE 0
END AS KIND_MCV,
CASE
WHEN s.stakind1 = 1 THEN s.stavalues1
WHEN s.stakind2 = 1 THEN s.stavalues2
WHEN s.stakind3 = 1 THEN s.stavalues3
WHEN s.stakind4 = 1 THEN s.stavalues4
WHEN s.stakind5 = 1 THEN s.stavalues5
ELSE NULL::anyarray
END AS most_common_vals,
CASE
WHEN s.stakind1 = 1 THEN s.stanumbers1
WHEN s.stakind2 = 1 THEN s.stanumbers2
WHEN s.stakind3 = 1 THEN s.stanumbers3
WHEN s.stakind4 = 1 THEN s.stanumbers4
WHEN s.stakind5 = 1 THEN s.stanumbers5
ELSE NULL::real[]
END AS most_common_freqs,
CASE
WHEN s.stakind1 = 2 THEN s.stavalues1
WHEN s.stakind2 = 2 THEN s.stavalues2
WHEN s.stakind3 = 2 THEN s.stavalues3
WHEN s.stakind4 = 2 THEN s.stavalues4
WHEN s.stakind5 = 2 THEN s.stavalues5
ELSE NULL::anyarray
END AS histogram_bounds,
CASE
WHEN s.stakind1 = 3 THEN s.stanumbers1[1]
WHEN s.stakind2 = 3 THEN s.stanumbers2[1]
WHEN s.stakind3 = 3 THEN s.stanumbers3[1]
WHEN s.stakind4 = 3 THEN s.stanumbers4[1]
WHEN s.stakind5 = 3 THEN s.stanumbers5[1]
ELSE NULL::real
END AS correlation,
CASE
WHEN s.stakind1 = 4 THEN s.stavalues1
WHEN s.stakind2 = 4 THEN s.stavalues2
WHEN s.stakind3 = 4 THEN s.stavalues3
WHEN s.stakind4 = 4 THEN s.stavalues4
WHEN s.stakind5 = 4 THEN s.stavalues5
ELSE NULL::anyarray
END AS most_common_elems,
CASE
WHEN s.stakind1 = 4 THEN s.stanumbers1
WHEN s.stakind2 = 4 THEN s.stanumbers2
WHEN s.stakind3 = 4 THEN s.stanumbers3
WHEN s.stakind4 = 4 THEN s.stanumbers4
WHEN s.stakind5 = 4 THEN s.stanumbers5
ELSE NULL::real[]
END AS most_common_elem_freqs,
CASE
WHEN s.stakind1 = 5 THEN s.stanumbers1
WHEN s.stakind2 = 5 THEN s.stanumbers2
WHEN s.stakind3 = 5 THEN s.stanumbers3
WHEN s.stakind4 = 5 THEN s.stanumbers4
WHEN s.stakind5 = 5 THEN s.stanumbers5
ELSE NULL::real[]
END AS elem_count_histogram,
CASE
WHEN s.stakind1 = 6 THEN s.stavalues1
WHEN s.stakind2 = 6 THEN s.stavalues2
WHEN s.stakind3 = 6 THEN s.stavalues3
WHEN s.stakind4 = 6 THEN s.stavalues4
WHEN s.stakind5 = 6 THEN s.stavalues5
ELSE NULL::anyarray
END AS range_length_histogram,
CASE
WHEN s.stakind1 = 6 THEN s.stanumbers1[1]
WHEN s.stakind2 = 6 THEN s.stanumbers2[1]
WHEN s.stakind3 = 6 THEN s.stanumbers3[1]
WHEN s.stakind4 = 6 THEN s.stanumbers4[1]
WHEN s.stakind5 = 6 THEN s.stanumbers5[1]
ELSE NULL::real
END AS range_empty_frac,
CASE
WHEN s.stakind1 = 7 THEN s.stavalues1
WHEN s.stakind2 = 7 THEN s.stavalues2
WHEN s.stakind3 = 7 THEN s.stavalues3
WHEN s.stakind4 = 7 THEN s.stavalues4
WHEN s.stakind5 = 7 THEN s.stavalues5
ELSE NULL::anyarray
END AS range_bounds_histogram
FROM pg_statistic s
JOIN pg_class c ON c.oid = s.starelid
JOIN pg_attribute a ON c.oid = a.attrelid AND a.attnum = s.staattnum
LEFT JOIN pg_namespace n ON n.oid = c.relnamespace
WHERE NOT a.attisdropped AND has_column_privilege(c.oid, a.attnum, 'select'::text) AND (c.relrowsecurity = false OR NOT row_security_active(c.oid))
) as t1 order by 1,2,3,4,5,6;

I have also attached a test SQL file covering the main functions involved in this change,
including var_eq_const(), mcv_selectivity(), get_stats_slot_range(), and eqjoinsel_find_matches(),
so that others can easily reproduce and test the relevant cases.

For convenience, I also list below the modified files and functions. This should make it easier to get
an overview of the changes and review the relevant code.

### Modified files and functions
src/include/catalog/pg_statistic.h
#define STATISTIC_KIND_MCV_VALUE_SORTED 8
- Adds a new statistics kind for MCV values sorted by value.

src/backend/commands/analyze.c
- compute_scalar_stats() Generates STATISTIC_KIND_MCV_VALUE_SORTED

src/backend/catalog/system_views.sql
- Adds support for displaying STATISTIC_KIND_MCV_VALUE_SORTED statistics.

src/include/utils/lsyscache.h
src/backend/utils/cache/lsyscache.c
- Adds the get_attstatsslot_mcv() helper, similar to get_attstatsslot(), for retrieving both
STATISTIC_KIND_MCV_VALUE_SORTED and STATISTIC_KIND_MCV statistics.

src/include/statistics/stat_utils.h
src/backend/statistics/stat_utils.c
-Adds the following helper functions:
- get_max_mcv_frequency() Gets the maximum frequency among the MCV entries.
- get_min_mcv_frequency() Gets the minimum frequency among the MCV entries.

src/backend/executor/nodeHash.c
- Uses get_attstatsslot_mcv() to retrieve MCV statistics.

src/backend/utils/adt/like_support.c
- prefix_selectivity() Uses var_eq_const() for eq_sel.
- patternsel_common()
- Uses var_eq_const().
- Uses mcv_selectivity(..., oprid) for MCV selectivity.

src/backend/utils/adt/network_selfuncs.c
- networksel() Uses mcv_selectivity(..., operator).
- networkjoinsel_inner() Uses get_attstatsslot_mcv().

src/include/utils/selfuncs.h
src/backend/utils/adt/selfuncs.c
***This is the main file affected by the patch. The major changes include:***
var_eq_const() ***
var_eq_non_const()
- Uses get_attstatsslot_mcv() and get_max_mcv_frequency().
scalarineqsel()
- Uses mcv_selectivity().
mcv_selectivity()***
generic_restriction_selectivity()
- Uses mcv_selectivity().
ineq_histogram_selectivity()
- Uses get_attstatsslot_mcv().
booltestsel()
- Uses get_attstatsslot_mcv().
neqjoinsel()
- Uses eqjoinsel().
eqjoinsel() ***
eqjoinsel_inner()
- Uses eqjoinsel_find_matches().
eqjoinsel_semi()
- Uses eqjoinsel_find_matches().
eqjoinsel_find_matches() ***
estimate_hash_bucket_stats()
- Uses get_attstatsslot_mcv() and get_max_mcv_frequency().
get_variable_range()
- Uses get_stats_slot_range() and get_attstatsslot_mcv().
get_stats_slot_range() ***
mergejoinscansel()
- Uses get_variable_range(), which in turn uses mcv_selectivity().

The functions marked above are also the main entry points where the new sorted-MCV
information is consumed during selectivity estimation and range detection.

As a next step, I plan to run some additional performance tests using EXPLAIN to better understand
the impact of the changes on query planning and selectivity estimation.

I would greatly appreciate any comments or suggestions from the community. In particular, feedback
on the implementation, the conservative conditions for applying the optimization, and any potential
performance concerns would be very helpful.

Thanks for your time and review.

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