Re: Fix var_eq_const: sum selectivity of all matching MCV entries instead of stopping at first match

[ZizhuanLiu X-MAN]

Original
&gt;From:&nbsp;Tom&nbsp;Lane&nbsp;<t...@sss.pgh.pa.us&gt;
&gt;Date:&nbsp;2026-07-30&nbsp;21:39
&gt;To:&nbsp;ZizhuanLiu&nbsp;X-MAN&nbsp;<44973...@qq.com&gt;
&gt;Cc:&nbsp;pgsql-hackers&nbsp;<pgsql-hackers@lists.postgresql.org&gt;
&gt;Subject:&nbsp;Re:&nbsp;Fix&nbsp;var_eq_const:&nbsp;sum&nbsp;selectivity&nbsp;of&nbsp;all&nbsp;matching&nbsp;MCV&nbsp;entries&nbsp;instead&nbsp;of&nbsp;stopping&nbsp;at&nbsp;first&nbsp;match
&gt;"=?utf-8?B?Wml6aHVhbkxpdSBYLU1BTg==?="&nbsp;<44973...@qq.com&gt;&nbsp;writes:
&gt;&gt;&nbsp;While&nbsp;reviewing&nbsp;CF6397(https://commitfest.postgresql.org/patch/6397/),&nbsp;I&nbsp;noticed&nbsp;that
&gt;&gt;&nbsp;the&nbsp;function&nbsp;`var_eq_const()`&nbsp;located&nbsp;at&nbsp;`backend/utils/adt/selfuncs.c`&nbsp;consumes&nbsp;statistical
&gt;&gt;&nbsp;data&nbsp;from&nbsp;the&nbsp;`most_common_vals`&nbsp;and&nbsp;`most_common_freqs`&nbsp;columns&nbsp;in&nbsp;the&nbsp;system
&gt;&gt;&nbsp;catalog&nbsp;`pg_catalog.pg_stats`.&nbsp;Currently,&nbsp;the&nbsp;function&nbsp;terminates&nbsp;iteration&nbsp;immediately
&gt;&gt;&nbsp;after&nbsp;finding&nbsp;the&nbsp;first&nbsp;matching&nbsp;entry&nbsp;and&nbsp;adopts&nbsp;the&nbsp;selectivity&nbsp;of&nbsp;this&nbsp;single&nbsp;matched&nbsp;value.
&gt;
&gt;&gt;&nbsp;I&nbsp;believe&nbsp;this&nbsp;estimation&nbsp;logic&nbsp;is&nbsp;inaccurate.&nbsp;Instead,&nbsp;we&nbsp;should&nbsp;traverse&nbsp;all&nbsp;entries&nbsp;in
&gt;&gt;&nbsp;`most_common_vals`,&nbsp;check&nbsp;for&nbsp;matches&nbsp;against&nbsp;each&nbsp;entry,&nbsp;and&nbsp;sum&nbsp;up&nbsp;the&nbsp;selectivities
&gt;&gt;&nbsp;of&nbsp;all&nbsp;matching&nbsp;items.
&gt;
&gt;That&nbsp;would&nbsp;double&nbsp;the&nbsp;function's&nbsp;runtime&nbsp;on&nbsp;average,&nbsp;without&nbsp;changing
&gt;the&nbsp;results&nbsp;at&nbsp;all&nbsp;in&nbsp;most&nbsp;cases&nbsp;(it&nbsp;could&nbsp;only&nbsp;be&nbsp;different&nbsp;if&nbsp;the
&gt;given&nbsp;operator&nbsp;has&nbsp;different&nbsp;semantics&nbsp;from&nbsp;the&nbsp;equality&nbsp;operator&nbsp;used
&gt;while&nbsp;building&nbsp;the&nbsp;statistics&nbsp;list).&nbsp;I&nbsp;think&nbsp;you&nbsp;need&nbsp;a&nbsp;far&nbsp;stronger
&gt;argument&nbsp;for&nbsp;changing&nbsp;the&nbsp;existing&nbsp;tradeoff&nbsp;than&nbsp;"I&nbsp;believe".
&gt;
&gt;regards,&nbsp;tom&nbsp;lane

Hi,&nbsp;tom,&nbsp;hackers


Thanks for the review and important feedback.

From&nbsp;an&nbsp;algorithm&nbsp;perspective,&nbsp;the&nbsp;average&nbsp;complexity&nbsp;shifts&nbsp;from
N/2&nbsp;to&nbsp;a&nbsp;fixed&nbsp;O(N)&nbsp;full&nbsp;scan,&nbsp;adding&nbsp;performance&nbsp;overhead.&nbsp;I&nbsp;had
not&nbsp;accounted&nbsp;for&nbsp;this&nbsp;downside&nbsp;earlier.


After&nbsp;examining&nbsp;pg_catalog.pg_collation,&nbsp;I&nbsp;found&nbsp;that&nbsp;all&nbsp;preloaded
collations&nbsp;have&nbsp;collisdeterministic&nbsp;=&nbsp;true.

This&nbsp;applies&nbsp;to&nbsp;all&nbsp;provider&nbsp;types:&nbsp;d&nbsp;(default),&nbsp;b&nbsp;(builtin),&nbsp;c&nbsp;(libc),&nbsp;and&nbsp;i&nbsp;(icu).
Below&nbsp;is&nbsp;the&nbsp;statistic&nbsp;from&nbsp;my&nbsp;test&nbsp;environment&nbsp;(ICU&nbsp;enabled):
```sql
select&nbsp;collprovider,collisdeterministic,count(*)&nbsp;from&nbsp;pg_catalog.pg_collation&nbsp;group&nbsp;by&nbsp;1,2;
&nbsp;collprovider&nbsp;&nbsp;|&nbsp;collisdeterministic&nbsp;&nbsp;&nbsp;|&nbsp;count&nbsp;
--------------+---------------------+-------
&nbsp;c&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;t&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3
&nbsp;b&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;t&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;3
&nbsp;i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;t&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;853
&nbsp;d&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;t&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1
&nbsp;i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;f&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;1

The&nbsp;single&nbsp;row&nbsp;with&nbsp;collisdeterministic&nbsp;=&nbsp;false&nbsp;is&nbsp;the&nbsp;custom&nbsp;collation&nbsp;I&nbsp;created:
```sql
CREATE&nbsp;COLLATION&nbsp;case_insensitive&nbsp;(provider&nbsp;=&nbsp;icu,&nbsp;locale&nbsp;=&nbsp;'und-u-ks-level2',&nbsp;deterministic&nbsp;=&nbsp;false);

As&nbsp;required&nbsp;by&nbsp;PostgreSQL&nbsp;collation&nbsp;rules,&nbsp;deterministic&nbsp;=&nbsp;false
must&nbsp;be&nbsp;explicitly&nbsp;specified&nbsp;to&nbsp;create&nbsp;a&nbsp;non-deterministic&nbsp;collation.

Only&nbsp;when&nbsp;collisdeterministic&nbsp;=&nbsp;false&nbsp;can&nbsp;a&nbsp;comparison&nbsp;match
multiple&nbsp;binary-distinct&nbsp;strings.
For&nbsp;example:
'a'&nbsp;COLLATE&nbsp;case_insensitive&nbsp;can&nbsp;match&nbsp;both&nbsp;'A'&nbsp;and&nbsp;'a'&nbsp;stored&nbsp;in&nbsp;MCV
entries&nbsp;collected&nbsp;under&nbsp;a&nbsp;deterministic&nbsp;collation.
Similarly,&nbsp;plain&nbsp;values&nbsp;'A'&nbsp;/&nbsp;'a' can 
match&nbsp;MCV&nbsp;entries which defined
by COLLATE&nbsp;case_insensitive.

By&nbsp;comparing&nbsp;the&nbsp;collation&nbsp;OID&nbsp;of&nbsp;the&nbsp;attribute&nbsp;and&nbsp;the&nbsp;expression,&nbsp;together
 
with&nbsp;each&nbsp;collation’s&nbsp;collisdeterministic&nbsp;property,&nbsp;I&nbsp;have&nbsp;outlined&nbsp;the&nbsp;following&nbsp;decision&nbsp;table:
attribute-collation      | expr-collation     &nbsp; &nbsp; &nbsp; &nbsp; 
&nbsp;|&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;|&nbsp; &nbsp; &nbsp; 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
&nbsp; |       
coll-oid | deterministic? | coll-oid | deterministic? | oid eq? | 
mcv-scan-strategy |
---------+--------------+---------+----------------+--------+--------------------
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x | &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
&nbsp;dem  |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x |&nbsp; &nbsp; &nbsp; 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dem |&nbsp; &nbsp; &nbsp; &nbsp;== |   
first/fast &nbsp; &nbsp; &nbsp; &nbsp;|
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x | &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
&nbsp;dem&nbsp; &nbsp;|&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; y |&nbsp; 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dem |&nbsp; &nbsp; &nbsp; 
&nbsp;<&gt; |&nbsp; &nbsp; first/fast &nbsp; &nbsp; &nbsp; &nbsp;| &nbsp; 
&nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;x |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
&nbsp;non&nbsp; &nbsp; |    &nbsp; &nbsp; &nbsp; x |  &nbsp; &nbsp; &nbsp; 
&nbsp; &nbsp; &nbsp; &nbsp;non |&nbsp; &nbsp; &nbsp; &nbsp; == |   first/fast 
&nbsp; &nbsp; &nbsp; &nbsp;|
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;x |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
&nbsp;non  |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; y |&nbsp; &nbsp; &nbsp; 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; non |&nbsp; &nbsp; &nbsp; &nbsp;<&gt;&nbsp; 
|&nbsp; &nbsp; first/fast &nbsp; &nbsp; &nbsp; &nbsp;|
&nbsp; &nbsp; &nbsp; &nbsp;
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;x |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
&nbsp;non  |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; y |&nbsp; &nbsp; &nbsp; 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;dem |&nbsp; &nbsp; &nbsp; &nbsp;<&gt;  
|&nbsp; &nbsp; all/low &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; |
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;x |&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 
&nbsp;dem&nbsp; &nbsp;|&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; y |&nbsp; 
&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; non |&nbsp; &nbsp; &nbsp; 
&nbsp;<&gt; |&nbsp; &nbsp; all/low &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; |
-------------------------------------------------------------------------------------
Where:
dem&nbsp;=&nbsp;deterministic
non&nbsp;=&nbsp;non-deterministic

The&nbsp;MCV&nbsp;list&nbsp;holds&nbsp;up&nbsp;to&nbsp;100&nbsp;entries&nbsp;by&nbsp;default;&nbsp;this&nbsp;limit&nbsp;can&nbsp;be&nbsp;adjusted&nbsp;via
ALTER&nbsp;TABLE&nbsp;...&nbsp;ALTER&nbsp;COLUMN&nbsp;...&nbsp;SET&nbsp;STATISTICS&nbsp;(range&nbsp;0&nbsp;to&nbsp;10000).

Accurate&nbsp;row&nbsp;estimates&nbsp;are&nbsp;critical&nbsp;for&nbsp;planner&nbsp;decisions&nbsp;such&nbsp;as&nbsp;choosing
the&nbsp;driving&nbsp;table&nbsp;in&nbsp;a&nbsp;Nested&nbsp;Loop&nbsp;Join.&nbsp;Poor&nbsp;estimates&nbsp;can&nbsp;lead&nbsp;to&nbsp;drastically
incorrect&nbsp;cost&nbsp;calculations&nbsp;and&nbsp;bad&nbsp;plans.

This&nbsp;proposed&nbsp;strategy&nbsp;preserves&nbsp;the&nbsp;existing&nbsp;fast&nbsp;first-match&nbsp;logic&nbsp;for&nbsp;the&nbsp;vast&nbsp;majority&nbsp;of&nbsp;workloads,&nbsp;maintaining
current&nbsp;performance&nbsp;characteristics.&nbsp;
Meanwhile&nbsp;it&nbsp;enables&nbsp;accurate&nbsp;selectivity&nbsp;estimation&nbsp;for&nbsp;the
special&nbsp;mixed-collation&nbsp;scenario&nbsp;described&nbsp;above.

This&nbsp;is&nbsp;the&nbsp;approach&nbsp;I&nbsp;have&nbsp;in&nbsp;mind.&nbsp;Please&nbsp;let&nbsp;me&nbsp;know
if&nbsp;there&nbsp;are&nbsp;flaws&nbsp;or&nbsp;missing&nbsp;considerations.

If&nbsp;the&nbsp;overall&nbsp;direction&nbsp;looks&nbsp;reasonable,&nbsp;I&nbsp;will&nbsp;move&nbsp;on&nbsp;to
work&nbsp;out&nbsp;the&nbsp;concrete&nbsp;code&nbsp;adaptations.

regards,
--
ZizhuanLiu&nbsp;(X-MAN)&nbsp;
44973...@qq.com