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

"=?utf-8?B?Wml6aHVhbkxpdSBYLU1BTg==?=" <44973863@qq.com> writes:

While reviewing CF6397(https://commitfest.postgresql.org/patch/6397/), I noticed that
the function `var_eq_const()` located at `backend/utils/adt/selfuncs.c` consumes statistical
data from the `most_common_vals` and `most_common_freqs` columns in the system
catalog `pg_catalog.pg_stats`. Currently, the function terminates iteration immediately
after finding the first matching entry and adopts the selectivity of this single matched value.

I believe this estimation logic is inaccurate. Instead, we should traverse all entries in
`most_common_vals`, check for matches against each entry, and sum up the selectivities
of all matching items.

That would double the function's runtime on average, without changing
the results at all in most cases (it could only be different if the
given operator has different semantics from the equality operator used
while building the statistics list). I think you need a far stronger
argument for changing the existing tradeoff than "I believe".

regards, tom lane

Hi,

I signed up as a reviewer for CF entry 7075 and I tested this on current
master with ICU enabled on macOS.

Without the patch, this query:

WHERE a = 'b' COLLATE "case_insensitive"

estimated 10 rows but actually returned 19 rows.

After applying the patch, the same query estimated 19 rows and returned 19
rows.

I also checked the normal equality cases and those stayed the same:

WHERE a = 'B' estimated 10 and returned 10

WHERE a = 'b' estimated 9 and returned 9

So the author's example looks real, and the patch fixes that example.

Tom's concern still seems important. Scanning the whole MCV list every time
would cost more in the common case, and it only changes the result when the
comparison operator or collation is different from the equality used to
build the statistics. Before this can move forward, I think we need a
stronger reason for that tradeoff. For example:

1. How often do multiple MCV entries match in practice?
2. Can we only do the full scan when the operator or collation differs
from the stats equality operator?

I am happy to test a revised approach if one is proposed.

Thanks,

Damil Shahzad

On Tue, 4 Aug 2026 at 16:26, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Original
&gt;From:&nbsp;Tom&nbsp;Lane&nbsp;<tgl@sss.pgh.pa.us&gt;
&gt;Date:&nbsp;2026-07-30&nbsp;21:39
&gt;To:&nbsp;ZizhuanLiu&nbsp;X-MAN&nbsp;<44973863@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;<44973863@qq.com&gt;&nbsp;writes:
&gt;&gt;&nbsp;While&nbsp;reviewing&nbsp;CF6397(https://commitfest.postgresql.org/patch/6397/),&amp;nbsp;I&amp;nbsp;noticed&amp;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;
44973863@qq.com

On 8/4/26 14:29, Damil Shahzad wrote:

Tom's concern still seems important. Scanning the whole MCV list every
time would cost more in the common case, and it only changes the
result when the comparison operator or collation is different from the
equality used to build the statistics. Before this can move forward, I
think we need a stronger reason for that tradeoff.

+1

A cheaper way to get some benefit here without touching that tradeoff:
when there are no MCV matches, var_eq_const does a second full pass over
MCV list just to compute `sumcommon` - but that branch is only reached
after the first loop has already scanned every entry. So `sumcommon` can
be accumulated inline in that same scan, and the separate summing loop
dropped. The match case is unaffected; only the no-match path gets
faster, by skipping a redundant second traversal.

I attached patch with these changes. What do you think?

--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com

Hi Ilia,

Thanks for the patch. I tested it on current master.

Your patch by itself keeps the same estimates as unpatched code on my tests.
The case insensitive example still estimates 10 rows instead of 19. So it
looks like a performance cleanup, not a fix for the original issue.

I also tested your patch combined with the multi MCV match change from the
original patch. On that combined version I got the same estimates as the
original patch alone:

case insensitive 'b' -> estimated 19, actual 19

exact 'B' -> estimated 10, actual 10

exact 'b' -> estimated 9, actual 9

no match constant -> estimated 1, actual 0

So I agree with your idea. Merging the frequency sum work into the same loop
is a good cleanup once we keep the multi match accumulation fix. It avoids
the extra second pass on the no match path without changing the estimates I
checked.

I think the next step is to combine both changes in one patch series.

Thanks,

Damil Shahzad

On Wed, 5 Aug 2026 at 12:33, Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>
wrote:

Original

From: Damil Shahzad <shahzaddamil@gmail.com>
Date: 2026-08-04 19:29
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: ZizhuanLiu X-MAN <44973863@qq.com>, pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Fix var_eq_const: sum selectivity of all matching MCV entries instead of stopping at first match

Hi, Damil
Thank you very much for your testing and valuable feedback.

Original

From: Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>
Date: 2026-08-05 15:33
To: Damil Shahzad <shahzaddamil@gmail.com>, Tom Lane <tgl@sss.pgh.pa.us>
Cc: ZizhuanLiu X-MAN <44973863@qq.com>, pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Fix var_eq_const: sum selectivity of all matching MCV entries instead of stopping at first match

A cheaper way to get some benefit here without touching that tradeoff: when there are no MCV matches, var_eq_const does a second full pass over MCV list just to compute `sumcommon` - but that branch is only reached after the first loop has already scanned every entry. So `sumcommon` can be accumulated inline in that same scan, and the separate summing loop dropped. The match case is unaffected; only the no-match path gets faster, by skipping a redundant second traversal.

I attached patch with these changes. What do you think?

Hi, Ilia,
Thanks for your feedback and the patch. Your patch removes
an extra loop used for a straightforward calculation, but the resulting
performance improvement is probably minor.

Hi all,
Upon further careful analysis,I have found that that full MCV scanning is
only justified and beneficial under the following condition:
the column has a deterministic collation, and the expression uses a
non-deterministic collation.

For every other scenario, performing a full MCV scan is either
unnecessary or inappropriate.

The relevant test queries are listed below. The attached XLS spreadsheet
contains the full analysis.

I welcome any discussion or feedback if there are deficiencies in my analysis.

```SQL
CREATE COLLATION case_insensitive (provider = icu, locale = 'und-u-ks-level2', deterministic = false);
CREATE COLLATION num_ignore_punct (provider = icu, deterministic = false, locale = 'und-u-ka-shifted-kn');

CREATE TABLE test_mcv(c1 text, c2 text COLLATE "case_insensitive");
xman7=# \d+ test_mcv
Table "public.test_mcv"
Column | Type | Collation | Nullable | Default | Storage | Compression | Stats target | Description
--------+------+------------------+----------+---------+----------+-------------+--------------+-------------
c1 | text | | | | extended | | |
c2 | text | case_insensitive | | | extended | | |
Access method: heap

xman7=#

INSERT INTO test_mcv values ('a-1','a-1'), ('A-1','A-1');
INSERT INTO test_mcv values ('a-1','a-1'), ('A-1','A-1');
INSERT INTO test_mcv values ('a-2','a-2'), ('A-2','A-2');
INSERT INTO test_mcv values ('a-2','a-2'), ('A-2','A-2');

INSERT INTO test_mcv values ('b-1','b-1'), ('B-1','B-1');
INSERT INTO test_mcv values ('b-1','b-1'), ('B-1','B-1');
INSERT INTO test_mcv values ('b-2','b-2'), ('B-2','B-2');
INSERT INTO test_mcv values ('b-2','b-2'), ('B-2','B-2');

ANALYZE test_mcv;

select attname,n_distinct,most_common_vals,most_common_freqs,correlation from pg_catalog.pg_stats where tablename = 'test_mcv'\gx
-[ RECORD 1 ]-----+--------------------------------------------------
attname | c1
n_distinct | -0.5
most_common_vals | {A-1,A-2,B-1,B-2,a-1,a-2,b-1,b-2}
most_common_freqs | {0.125,0.125,0.125,0.125,0.125,0.125,0.125,0.125}
correlation | 0.4
-[ RECORD 2 ]-----+--------------------------------------------------
attname | c2
n_distinct | -0.25
most_common_vals | {a-1,a-2,b-1,b-2}
most_common_freqs | {0.25,0.25,0.25,0.25}
correlation | 1

xman7=#

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

That would double the function's runtime on average, without changing
the results at all in most cases (it could only be different if the
given operator has different semantics from the equality operator used
while building the statistics list).

So I agree with Tom’s reasoning.

Hi ZizhuanLiu,

Thanks for the update and the spreadsheet. That analysis is helpful.

I agree with the narrowed conclusion full MCV scanning only looks

justified when the column collation is deterministic and the expression

uses a non deterministic collation. In the other cases, keeping the

current first match behavior seems right.

If you post a revised patch that does the full scan only in that case,

I am happy to retest it.

Thanks,

Damil Shahzad

On Wed, 5 Aug 2026 at 15:37, Zizhuan Liu <44973863@qq.com> wrote:

Original

From: Tom Lane <tgl@sss.pgh.pa.us>
Date: 2026-07-30 21:39
To: ZizhuanLiu X-MAN <44973863@qq.com>
Cc: pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Fix var_eq_const: sum selectivity of all matching MCV entries instead of stopping at first match

I think you need a far stronger
argument for changing the existing tradeoff than "I believe".

Although I have made efforts to implement it, there is still
no satisfactory and acceptable solution available at present.

That would double the function's runtime on average, without changing
the results at all in most cases (it could only be different if the
given operator has different semantics from the equality operator used
while building the statistics list).

So I agree with Tom’s reasoning.

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

Original

From: ZizhuanLiu X-MAN <44973863@qq.com>
Date: 2026-08-05 18:44
To: Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>, Damil Shahzad <shahzaddamil@gmail.com>, Tom Lane <tgl@sss.pgh.pa.us>
Cc: pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Fix var_eq_const: sum selectivity of all matching MCV entries instead of stopping at first match

From: Tom Lane <tgl@sss.pgh.pa.us>
Date: 2026-07-30 21:39
To: ZizhuanLiu X-MAN <44973863@qq.com>
Cc: pgsql-hackers <pgsql-hackers@lists.postgresql.org>

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

I think you need a far stronger
argument for changing the existing tradeoff than "I believe".

Although I have made efforts to implement it, there is still
no satisfactory and acceptable solution available at present.

That would double the function's runtime on average, without changing
the results at all in most cases (it could only be different if the
given operator has different semantics from the equality operator used
while building the statistics list).

So I agree with Tom’s reasoning.

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

Hi, Ilia
After further consideration, based on the definition of the AttStatsSlot
data structure and the functional logic of get_attstatsslot(), sslot.nvalues
and sslot.nnumbers are two members that are not guaranteed to be
symmetric or equal. Therefore, for the logic related to sumcommon,
I suggest taking a conservative approach and leaving it untouched for this patch.

Original

From: ZizhuanLiu X-MAN <44973863@qq.com>
Date: 2026-08-05 18:31
To: Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>, Damil Shahzad <shahzaddamil@gmail.com>, Tom Lane <tgl@sss.pgh.pa.us>
Cc: pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Fix var_eq_const: sum selectivity of all matching MCV entries instead of stopping at first match
Hi all,
Upon further careful analysis,I have found that that full MCV scanning is
only justified and beneficial under the following condition:
the column has a deterministic collation, and the expression uses a
non-deterministic collation.

Hi Damil, all,
The patch currently implements only this scenario, and addresses only the test cases listed in the attached spreadsheet:
```SQL
explain analyze select * from test_mcv where c1 = 'a-0' collate ""case_insensitive""; --Some adjustments are needed, yet this idea is feasible.
explain analyze select * from test_mcv where c1 = 'a-1' collate ""case_insensitive""; --Some adjustments are needed, yet this idea is feasible.
explain analyze select * from test_mcv where c1 = 'a-2' collate ""case_insensitive""; --Some adjustments are needed, yet this idea is feasible.

I welcome additional comprehensive test cases and suggestions for improvements.
We will add and refine regression tests once testing and feedback have stabilized.

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

Hi ZizhuanLiu,

Thanks for sending v2. I tested it using your test_mcv setup and the
case_insensitive example I tried before.

On the case you are targeting, deterministic column and non deterministic
expression in the query, it looks good to me. Without the patch, c1 = 'a-1'
COLLATE "case_insensitive" estimated 2 rows but actually returned 4. With
v2 it estimated 4 and returned 4. Same kind of fix on my other table, a =
'b' COLLATE "case_insensitive" went from estimated 10 to estimated 19, and
actual was 19.

The normal equality cases I checked still looked the same as before, things
like c1 = 'a-1', a = 'B', and a = 'b'.

For the other cases in your spreadsheet, v2 seemed to keep the old first
match behavior, which matches what you described. I did still see c2 =
'A-1' COLLATE "default" estimate 1 vs actual 2, but I think that is the out
of scope case you already noted.

Overall I think v2 is a much better direction than v1. I don't have extra
test cases to add beyond what is already in your spreadsheet.

Thanks,

Damil Shahzad

On Thu, 6 Aug 2026 at 12:25, ZizhuanLiu X-MAN <44973863@qq.com> wrote:

Original

From: Damil Shahzad <shahzaddamil@gmail.com>
Date: 2026-08-06 15:59
To: ZizhuanLiu X-MAN <44973863@qq.com>
Cc: Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>, Tom Lane <tgl@sss.pgh.pa.us>, pgsql-hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Fix var_eq_const: sum selectivity of all matching MCV entries instead of stopping at first match

Hi ZizhuanLiu,

Thanks for sending v2. I tested it using your test_mcv setup and the case_insensitive example I tried before.

On the case you are targeting, deterministic column and non deterministic expression in the query, it looks good to me. Without the patch, c1 = 'a-1' COLLATE "case_insensitive" estimated 2 rows but actually returned 4. With v2 it estimated 4 and returned 4. Same kind of fix on my other table, a = 'b' COLLATE "case_insensitive" went from estimated 10 to estimated 19, and actual was 19.

The normal equality cases I checked still looked the same as before, things like c1 = 'a-1', a = 'B', and a = 'b'.

For the other cases in your spreadsheet, v2 seemed to keep the old first match behavior, which matches what you described. I did still see c2 = 'A-1' COLLATE "default" estimate 1 vs actual 2, but I think that is the out of scope case you already noted.

Overall I think v2 is a much better direction than v1. I don't have extra test cases to add beyond what is already in your spreadsheet.

Thanks,

Damil Shahzad

c2 = 'A-1' COLLATE "default" estimate 1 vs actual 2

Yes, C2 uses the case_insensitive collation. The row count recorded for value 'a-1'
in its statistics includes rows for both 'A-1' and 'a-1', as shown below:
-[ RECORD 2 ]-----+--------------------------------------------------
attname | c2
n_distinct | -0.25
most_common_vals | {a-1,a-2,b-1,b-2}
most_common_freqs | {0.25,0.25,0.25,0.25}
correlation | 1

Note: this concerns the literal 'a-1', not 'A-1'. When we inserted data, 'a-1' was loaded
into column c2 first. Since c2 uses the case_insensitive collation, the earlier entry 'a-1'
becomes the representative value covering both 'a-1' and 'A-1'.

When estimating for c2 = 'A-1' COLLATE "default", based on the literals stored in c2’s most_common_vals,
the matching row count ought to be 0. However, the optimizer estimates at least 1 row. At execution time,
each value in c2 is implicitly cast to COLLATE "default" and then compared against 'A-1' COLLATE "default",
yielding an actual row count of 2. This case produces either an accurate estimate or an underestimation.
xman7=# explain analyze select * from test_mcv where c2 = 'A-1' collate "default"; --accurate estimate/underestimation that cannot be corrected
QUERY PLAN
-----------------------------------------------------------------------------------------------------
Seq Scan on test_mcv (cost=0.00..1.20 rows=1 width=8) (actual time=0.140..0.187 rows=2.00 loops=1)
Filter: (c2 = 'A-1'::text)
Rows Removed by Filter: 14
Buffers: shared hit=1
Planning Time: 0.570 ms
Execution Time: 0.264 ms
(6 rows)

Conversely, for c2 = 'a-1' COLLATE "default", the literal entry in c2’s most_common_vals suggests a matching
count of 4 rows. During execution, each c2 value is implicitly cast to COLLATE "default" and compared to
`'a-1' COLLATE "default"", resulting in 2 actual rows. This case yields either an accurate estimate or an overestimation.
xman7=# explain analyze select * from test_mcv where c2 = 'a-1' collate "default"; --accurate estimate/overestimation that cannot be corrected
QUERY PLAN
-----------------------------------------------------------------------------------------------------
Seq Scan on test_mcv (cost=0.00..1.20 rows=4 width=8) (actual time=0.071..0.105 rows=2.00 loops=1)
Filter: (c2 = 'a-1'::text)
Rows Removed by Filter: 14
Buffers: shared hit=1
Planning Time: 0.626 ms
Execution Time: 0.161 ms
(6 rows)

I need to make a correction here: the outcome previously labelled 'underestimation' should
instead be 'accurate estimate / underestimation'.
I have updated the corresponding notes in the attached spreadsheet.

All of the test scenarios below fall into either the accurate estimate / underestimation or accurate estimate / overestimation category.

explain analyze select * from test_mcv where c2 = 'A-1' collate "default"; --accurate estimate/underestimation that cannot be corrected
explain analyze select * from test_mcv where c2 = 'A-2' collate "default"; --accurate estimate/underestimation that cannot be corrected
explain analyze select * from test_mcv where c2 = 'a-1' collate "default"; --accurate estimate/overestimation that cannot be corrected
explain analyze select * from test_mcv where c2 = 'a-2' collate "default"; --accurate estimate/overestimation that cannot be corrected

explain analyze select * from test_mcv where c2 = 'a-1' collate "num_ignore_punct"; --accurate estimate/overestimation that cannot be corrected
explain analyze select * from test_mcv where c2 = 'A-1' collate "num_ignore_punct"; --accurate estimate/underestimation that cannot be corrected
explain analyze select * from test_mcv where c2 = 'a-2' collate "num_ignore_punct"; --accurate estimate/overestimation that cannot be corrected
explain analyze select * from test_mcv where c2 = 'A-2' collate "num_ignore_punct"; --accurate estimate/underestimation that cannot be corrected

regards,

ZizhuanLiu (X-MAN)
44973863@qq.com

Hi ZizhuanLiu,

Thanks for the explanation. That makes sense now.

I see why c2 = 'A-1' COLLATE "default" can estimate 1 while returning 2.
The stats for c2 were built under case_insensitive, so 'a-1' becomes the
stored MCV entry for both spellings, and comparing with COLLATE "default"
does not line up with that.

Agreed that this is outside what v2 is trying to fix.

Regards,

Damil

On Thu, 6 Aug 2026 at 14:00, ZizhuanLiu X-MAN <44973863@qq.com> wrote:

On 8/4/26 14:29, Damil Shahzad wrote:

Tom's concern still seems important. Scanning the whole MCV list every time would cost more in the common case, and it only changes the result when the comparison operator or collation is different from the equality used to build the statistics. Before this can move forward, I think we need a stronger reason for that tradeoff.

+1

A cheaper way to get some benefit here without touching that tradeoff: when there are no MCV matches, var_eq_const does a second full pass over MCV list just to compute `sumcommon` - but that branch is only reached after the first loop has already scanned every entry. So `sumcommon` can be accumulated inline in that same scan, and the separate summing loop dropped. The match case is unaffected; only the no-match path gets faster, by skipping a redundant second traversal.

I attached patch with these changes. What do you think?

--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com

Hi, Ilia, hackers

After reviewing compute_scalar_stats(), one of the functions responsible for
collecting statistics, and verifying the corresponding statistics columns in the
system catalog, I confirmed that the arrays in pg_stats for most_common_vals
and most_common_freqs always have the same number of elements.

Therefore, I agree with your suggestion and have now integrated your code into the patch.

Thanks again for your patch.

1.Attached is compute_scalar_stats(). The allocation and assignment of elements in
these two arrays are both consistently based on the variable num_mcv:
```
compute_scalar_stats()
/* Generate MCV slot entry */
if (num_mcv > 0)
{
MemoryContext old_context;
Datum *mcv_values;
float4 *mcv_freqs;

/* Must copy the target values into anl_context */
old_context = MemoryContextSwitchTo(stats->anl_context);
mcv_values = palloc_array(Datum, num_mcv);
mcv_freqs = palloc_array(float4, num_mcv);
for (i = 0; i < num_mcv; i++)
{
mcv_values[i] = datumCopy(values[track[i].first].value,
stats->attrtype->typbyval,
stats->attrtype->typlen);
mcv_freqs[i] = (double) track[i].count / (double) samplerows;
}
MemoryContextSwitchTo(old_context);

stats->stakind[slot_idx] = STATISTIC_KIND_MCV;
stats->staop[slot_idx] = mystats->eqopr;
stats->stacoll[slot_idx] = stats->attrcollid;
stats->stanumbers[slot_idx] = mcv_freqs;
stats->numnumbers[slot_idx] = num_mcv;
stats->stavalues[slot_idx] = mcv_values;
stats->numvalues[slot_idx] = num_mcv;

/*
* Accept the defaults for stats->statypid and others. They have
* been set before we were called (see vacuum.h)
*/
slot_idx++;
}

2.Verify that the `most_common_vals` and `most_common_freqs` arrays have the same length:
```SQL
analyze; --whole database

with t1 as (
select tablename,attname
,array_length(most_common_vals , 1) as length_most_common_vals
,array_length(most_common_freqs, 1) as length_most_common_freqs
from pg_catalog.pg_stats
)
select sum(1) as total
,sum(case when length_most_common_vals != length_most_common_freqs then 1 else 0 end) not_same
,sum(case when length_most_common_vals != length_most_common_freqs then 0 else 1 end) same
from t1;

database postgres return:
total | not_same | same
-------+----------+------
417 | 0 | 417
(1 row)

database xman2 return:
total | not_same | same
-------+----------+------
568 | 0 | 568
(1 row)

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

HI,  hackers
  So far, I have only found compute_scalar_stats() and compute_distinct_stats() that
generate STATISTIC_KIND_MCV statistics. The way they allocate space for and populate
most_common_vals and most_common_freqs, as well as determine their number of elements,
is the same in both cases. In other words, these two arrays always have the same number of elements.

The relevant code is briefly shown below:
```C
/* Generate MCV slot entry */

                  mcv_values = palloc_array(Datum, num_mcv);
                  mcv_freqs = palloc_array(float4, num_mcv);
                  for (i = 0; i < num_mcv; i++)
                  {
                        mcv_values[i] = datumCopy(values[track[i].first].value,
                                                              stats->attrtype->typbyval,
                                                              stats->attrtype->typlen);
                        mcv_freqs[i] = (double) track[i].count / (double) samplerows;
                  }
                  MemoryContextSwitchTo(old_context);

                  stats->stakind[slot_idx] = STATISTIC_KIND_MCV;
                  stats->staop[slot_idx] = mystats->eqopr;
                  stats->stacoll[slot_idx] = stats->attrcollid;
                  stats->stanumbers[slot_idx] = mcv_freqs;
                  stats->numnumbers[slot_idx] = num_mcv;
                  stats->stavalues[slot_idx] = mcv_values;
                  stats->numvalues[slot_idx] = num_mcv;

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

Hi,
I apologize for the issue in patches v2 and v3. They contained a bug
that caused an error when collid == 0. This has now been fixed.

For example:
xman7=# select * from pg_catalog.pg_attribute where attrelid = 16418;
ERROR: cache lookup failed for collation 0
xman7=#

DROP TABLE IF EXISTS char_stats_1;
CREATE TABLE char_stats_1 (c "char");

INSERT INTO char_stats_1
SELECT v::"char"
FROM unnest(array['I','S','c','i','m','p','r','t','v']) AS v,
generate_series(1, CASE WHEN v IN ('i','v','r','t') THEN 50 ELSE 1 END);

analyze char_stats_1;

select * from char_stats_1 where c = 'C';
return error:
ERROR: cache lookup failed for collation 0

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