From: Tom Lane <tgl@sss.pgh.pa.us>
To: Matt Long <matt@mattlong.org>, Mark Frost <FROSTMAR@uk.ibm.com>
cc: "pgsql-performance@lists.postgresql.org"
 <pgsql-performance@lists.postgresql.org>
Subject: Re: Poor row estimates from planner,
 stat `most_common_elems` sometimes missing for a text[] column
In-reply-to: <987464.1757374621@sss.pgh.pa.us>
References: 
 <PH3PPF1C905D6E6F24A5C1A1A1D8345B593E16FA@PH3PPF1C905D6E6.namprd15.prod.outlook.com>
 <3e539c8b-c95a-4ba9-8462-04045b2da2b0@dalibo.com>
 <PH3PPF1C905D6E61EEB89CF46C1F572D402E16EA@PH3PPF1C905D6E6.namprd15.prod.outlook.com>
 <1751511.1749259794@sss.pgh.pa.us> <2194366.1752875645@sss.pgh.pa.us>
 <CAB2=oSHo0cjK-BktYgFL-mDHCov125my4XhvQRJzZo2VBBz=eA@mail.gmail.com>
 <987464.1757374621@sss.pgh.pa.us>
Comments: In-reply-to Tom Lane <tgl@sss.pgh.pa.us>
	message dated "Mon, 08 Sep 2025 19:37:01 -0400"
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <1209258.1757445586.1@sss.pgh.pa.us>
Content-Transfer-Encoding: quoted-printable
Date: Tue, 09 Sep 2025 15:19:46 -0400
Message-ID: <1209259.1757445586@sss.pgh.pa.us>
Archived-At: 
 <https://www.postgresql.org/message-id/1209259.1757445586%40sss.pgh.pa.us>
Precedence: bulk

I wrote:
> * The selectivity functions believe that the upper bound on the
> frequency of non-MCEs is minfreq / 2, not the stored minfreq.
> This seems like complete brain fade: there could easily be
> elements with frequency just less than minfreq, and probably are
> if the data distribution follows Zipf's law.  I did not dig into
> the git history, but I wonder if the divide-by-two business
> predates the introduction of the lossy-counting algorithm, and
> if so whether it was less insane with the original collection
> algorithm.  In any case, this patch removes the divisions by 2,
> and makes some nearby cosmetic improvements.

In the light of morning, I started to have second thoughts about
this aspect of the patch.  I checked the git history this time,
and found that the oldest instance of "minfreq / 2" dates to
4e57668da which originated from this discussion:

https://www.postgresql.org/message-id/flat/488DAEB8.3000402%40students.mim=
uw.edu.pl

It's already coded like that in Jan's initial patch, and there
was no discussion in the thread, so not a lot to be gleaned:

+            /*
+             * The element is not in MCELEM. Punt, but  assure that the
+             * selectivity cannot be more than minfreq / 2.
+             */
+            return (Selectivity) Min(DEFAULT_TS_SEL, minfreq / 2);

But looking at this, I think the problem is really that the comment
fails to describe his thought process.  We know that the frequency
of this not-in-the-MCE-list value cannot be more than minfreq, but
we have no idea how much less it is.  I think the idea of the
division might have been to assume that an "average" non-MCE value
would have a frequency about half that of the lowest MCE.  It does
seem reasonable to use some number lower than the cutoff, although
I dunno if 0.5 is exactly the right factor.

So now I'm wondering if we should leave the divisions alone and
instead fix the comments to explain why they are there.  Bolstering
this is that on the two test cases you guys submitted, the patch
with the divisions gets a spot-on estimate (1 row) while removing
the divisions yields an estimate of 2 rows.  I don't put a lot of
weight on that, since these are toy examples.  But I wonder if you
guys could test the patch on some of your real-world cases and
see if it looks like we should keep the divisions.

			regards, tom lane