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

Hi hackers,

I have revisited the four int4/text cases from my earlier performance
report [1], first retesting v15 and then comparing it with v16. The
earlier results were obtained with debug builds. In the current release
tests, I could not reproduce the magnitude of the speedups reported
there: joins still benefit under the tested conditions, but the two
scalar cases do not show an overall planning-time improvement.

I have also implemented the paired-MCV design proposed in [2]. Below
are the release results and the main implementation changes.

The comparison uses three versions based on master 8b529705d153:
master, master with the v15 changes from the earlier mail, and master
with the v16 changes. All were built with -O2, --disable-cassert, and
--disable-debug. Function timing code and its NOTICE output were removed
to measure overall EXPLAIN Planning Time without that instrumentation.

Each version used a fresh instance with the same test data: 20,000 rows,
100 distinct values, and 100 MCVs for each tested column. The text case
uses 12-character strings with the "C" collation. Tests ran serially,
with version order rotated across 20 rounds. Each case/round/version
used one connection and 104 EXPLAINs; the first two were discarded as
warm-up runs and the remaining 102 were averaged. Raw outputs were
retained. The int4 values are multiples of ten, so =51 is an interior
MCV miss and <51 has its boundary between MCV values.

The following are arithmetic means across all 20 rounds, without
removing outliers. Times are in milliseconds. Reduction is calculated
as (master - patch) / master, so a negative value means a regression.

Case &nbsp; &nbsp; &nbsp; &nbsp;master &nbsp; &nbsp; &nbsp; v15 &nbsp; &nbsp; &nbsp; &nbsp;v16 &nbsp; &nbsp; &nbsp;v15 reduction &nbsp;v16 reduction
--------- &nbsp;--------- &nbsp;--------- &nbsp;--------- &nbsp; ------------- &nbsp;-------------
int4 =51 &nbsp; 0.041766 &nbsp; 0.062891 &nbsp; 0.043947 &nbsp; &nbsp; &nbsp; -50.58% &nbsp; &nbsp; &nbsp; &nbsp; -5.22%
int4 <51 &nbsp; 0.040116 &nbsp; 0.045483 &nbsp; 0.042681 &nbsp; &nbsp; &nbsp; -13.38% &nbsp; &nbsp; &nbsp; &nbsp; -6.39%
int4 IN &nbsp; &nbsp;0.132870 &nbsp; 0.120811 &nbsp; 0.113871 &nbsp; &nbsp; &nbsp; &nbsp;+9.08% &nbsp; &nbsp; &nbsp; &nbsp;+14.30%
text IN &nbsp; &nbsp;0.162116 &nbsp; 0.140652 &nbsp; 0.136496 &nbsp; &nbsp; &nbsp; +13.24% &nbsp; &nbsp; &nbsp; &nbsp;+15.80%

The v15 int4 =51 mean is particularly affected by large timing spikes.
For context, pooled medians of all post-warm-up samples are:

Case &nbsp; &nbsp; &nbsp; &nbsp;master &nbsp; &nbsp; &nbsp; v15 &nbsp; &nbsp; &nbsp; &nbsp;v16
--------- &nbsp;--------- &nbsp;--------- &nbsp;---------
int4 =51 &nbsp; 0.039000 &nbsp; 0.040000 &nbsp; 0.040000
int4 <51 &nbsp; 0.038000 &nbsp; 0.040000 &nbsp; 0.039000
int4 IN &nbsp; &nbsp;0.124000 &nbsp; 0.115000 &nbsp; 0.113000
text IN &nbsp; &nbsp;0.161000 &nbsp; 0.130000 &nbsp; 0.132000

Thus the large mean regression in the v15 equality case should not be
interpreted as its typical overhead. Both summaries still show no
scalar-query benefit and lower planning times for the two join cases.

In [1], the debug-build tests reported Planning Time reductions of
47.22%, 53.51%, 52.17%, and 67.39% for these four cases. The current
release measurements show much smaller join gains and do not support
carrying those earlier percentages over to release builds. This is not
a comparison with identical build settings, and the master baseline has
also changed; I have not established which factors explain the gap.

All three versions used an MCV hash threshold of 202. With 100 MCVs on
each input, this deliberately exercises non-hash matching. The default
release threshold is 200, so the join results characterize that non-hash
comparison and do not establish a benefit over master's default hash
path. A default-threshold comparison is also needed.

A separate diagnostic equality join also exposed a v15 estimation
difference: 3,960,000 rows versus 4,000,000 for master, v16, and the
actual result. The old v15 implementation was retained unchanged for
the historical comparison; these timing results should not be taken as
evidence that all versions produce identical estimates.

As for v16, the main changes from v15 are:

* Retain kind 1 in descending frequency order and add kind 8 in ascending
&nbsp; value order, containing the same value-frequency pairs and collation.
&nbsp; Kind 1 records the equality operator; kind 8 records the actual '<'
&nbsp; ordering operator.

* Generate kind 8 after selecting the final kind-1 members. Sort their
&nbsp; positions in the already sorted sample and reuse that order for
&nbsp; histogram construction, avoiding another round of value comparisons.

* Use ordered MCVs for compatible endpoint/binary-search lookups in
&nbsp; var_eq_const() and mcv_selectivity(), ordered non-hash matching in
&nbsp; eqjoinsel(), and endpoint retrieval in get_variable_range() and
&nbsp; get_stats_slot_range(). Check operator semantics, types, collation,
&nbsp; and access to the actual comparator. Use kind 1 when frequency order
&nbsp; is required. Network selectivity code continues to use kind 1.

* Increase STATISTIC_NUM_SLOTS from five to six, since array statistics
&nbsp; can already occupy five slots. Keep the existing MCV view columns
&nbsp; associated with kind 1, and append separate value-sorted columns to
&nbsp; pg_stats and pg_stats_ext_exprs. Update statistics import, pg_dump,
&nbsp; and postgres_fdw accordingly. Import accepts no MCVs, kind 1 alone,
&nbsp; or a consistent pair of kinds 1 and 8, and rejects kind 8 alone.

The paired design preserves the meaning and ordering of the existing
MCV columns, but changes the catalog layout and view result shapes.
It also duplicates the MCV value/frequency payload and adds work during
ANALYZE and statistics access. The new tests do not yet establish that
the performance benefit generally justifies these costs.

These results reinforce Ilia's earlier concern [3] about cheap
comparisons on small MCV lists. Reducing comparison counts does not
necessarily reduce elapsed time once setup and statistics-access costs
are included. The next evaluation should distinguish regressions when
both versions use the existing path from gains when the patch uses an
ordered path, and examine list length, frequency skew, comparison cost,
and constant position.

My main concern is whether the measured gains justify the scope and
long-term maintenance cost. For sortable columns with MCVs, we would
store the same value-frequency pairs in two statistics slots instead
of one, and increase the catalog-wide slot limit from five to six.
The current patch already touches 27 files, with 3,445 insertions and
243 deletions, including comments, regression SQL, and expected output.

This is before any substantial optimization of network_selfuncs.c,
which currently has only changes to keep using kind 1 with the adjusted
interfaces. Further regression cases and validation are also still
needed, so the scope may grow further.

Given that scale, I am not yet convinced that the release-build gains
observed so far are compelling enough to justify the catalog changes,
additional storage, and implementation complexity. I would appreciate
feedback on whether there is a sufficiently strong case for pursuing
this design, or whether a narrower approach would be more worthwhile.

[1] https://www.postgresql.org/message-id/tencent_0AD51A01E1E1DBC468A12768BEDD2C53A809%40qq.com
[2] https://www.postgresql.org/message-id/tencent_70A009DE6F5DCB02EADB467EF8CA36345A07%40qq.com
[3] https://www.postgresql.org/message-id/87fde6ac-3647-4fce-be92-af27f6c132fa%40tantorlabs.com

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