MIME-Version: 1.0
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>
In-Reply-To: <2194366.1752875645@sss.pgh.pa.us>
From: Matt Long <matt@mattlong.org>
Date: Mon, 8 Sep 2025 12:13:41 -0700
Message-ID: 
 <CAB2=oSHo0cjK-BktYgFL-mDHCov125my4XhvQRJzZo2VBBz=eA@mail.gmail.com>
Subject: Re: Poor row estimates from planner, stat `most_common_elems`
 sometimes missing for a text[] column
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Mark Frost <FROSTMAR@uk.ibm.com>,
	"pgsql-performance@lists.postgresql.org"
 <pgsql-performance@lists.postgresql.org>
Content-Type: multipart/alternative; boundary="000000000000eebac8063e4efc63"
Archived-At: 
 <https://www.postgresql.org/message-id/CAB2%3DoSHo0cjK-BktYgFL-mDHCov125my4XhvQRJzZo2VBBz%3DeA%40mail.gmail.com>
Precedence: bulk

--000000000000eebac8063e4efc63
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Not to let perfect be the enemy of better, but we're facing a variant of
this issue that would not be addressed by the proposed patch. If you're
interested, the real world use case is described in
https://github.com/medplum/medplum/issues/7310. Rows have an array
consisting of one common element present in every row and one unique
element. With a statistics target at the default 100, this pushes the
threshold for vastly overestimated row counts for the unique elements down
to 7,937 rows.

In this case, the effects of the proposed patch are not applied since the
most_common_elems array is not empty. I'm not a statistician, so maybe this
wouldn't be valid, but it seems like using the highest frequency of an
element that did not qualify for the mce list instead of the 0.5% default
frequency could be an elegant, but more invasive solution.

Simple repro of the problem:

CREATE TABLE public.test(
    id integer,
    tags text[]
);

INSERT INTO public.test (id, tags)
        SELECT n, ARRAY['common', TO_CHAR(n,'fm00000000')] FROM ( SELECT
generate_series(1,7_937) AS n );

ANALYZE public.test;

SELECT most_common_elems, most_common_elem_freqs FROM pg_stats WHERE
schemaname =3D 'public' AND tablename =3D 'test' AND attname =3D 'tags';

EXPLAIN (ANALYZE,BUFFERS,VERBOSE)
        SELECT * FROM test WHERE tags && ARRAY['common'];

EXPLAIN (ANALYZE,BUFFERS,VERBOSE)
        SELECT * FROM test WHERE tags && ARRAY['00000001'];

With 7,936 rows:
    most_common_elems has 1,000 entries and looks like
{00000001,00000003,00000009,...,common}
    most_common_elem_freqs has 1,003 entries and looks like
{0.00012600806,0.00012600806,0.00012600806,...,1,0.00012600806,1,0}

With 7,937+ rows:
    most_common_elems is {common}
    most_common_elem_freqs is {1,1,1,0}

On Mon, Sep 8, 2025 at 11:27=E2=80=AFAM Tom Lane <tgl@sss.pgh.pa.us> wrote:

> I wrote:
> > Well, we don't have a most common element in this scenario --- the
> > whole point is that the occurrence counts resulting from the lossy
> > counting algorithm are too low to be trustworthy.  However, what we
> > do have is the cutoff frequency, and it seems to me that we could use
> > that as the estimate of the maximum frequency of the non-MCEs.
>
> Here's a less crude patch for that.  The array_typanalyze.c changes
> are the same as before, but I reconsidered what to do about this
> stumbling block:
>
> > Assuming we like this direction, the main thing that makes this a hack
> > not a polished patch is that I had to strongarm the code into storing
> > a zero-length values array.  What update_attstats would normally do
> > is leave the values column of the MCELEM stats slot NULL, which then
> > causes get_attstatsslot to throw a that-shouldn't-be-null error.
> > An alternative answer is to change get_attstatsslot to allow a null,
> > but I'm not sure that that's any cleaner.  Either way it seems like
> > there's a hazard of breaking some code that isn't expecting the case.
>
> I concluded that letting get_attstatsslot accept nulls is too risky;
> there is probably code that assumes that get_attstatsslot would've
> rejected that.  Instead, this version changes update_attstats' rule
> for when to store an array rather than a null.  Now it will do so
> if the passed-in stavalues pointer isn't null, even if numvalues
> is zero.  I think that this doesn't change the outcome for any
> existing analyze routines because they wouldn't pass a data pointer
> if they have no values; and even if it does, storing an empty array
> not a null seems like it should be pretty harmless.
>
> > An alternative that feels cleaner but a good bit more invasive
> > is to get rid of the convention of storing the min/max/nulls
> > frequencies as extra entries in the MCELEM numbers entry ---
> > which surely is a hack too --- and put them into some new slot
> > type.  I'm not sure if that's enough nicer to be worth the
> > conversion pain.
>
> A year ago I would have seriously considered doing it that way.
> But now that we have code to dump-n-restore stats, that code would
> have to be adjusted to convert the old representation.  It's not
> worth it for this case.
>
> Hence, v1 attached, now with a commit message.
>
>                         regards, tom lane
>
>

--000000000000eebac8063e4efc63
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Not to let perfect be the enemy of better, but we&#39;re f=
acing a variant of this issue that would not be addressed by the proposed p=
atch. If you&#39;re interested, the real world use case is described in <a =
href=3D"https://github.com/medplum/medplum/issues/7310">https://github.com/=
medplum/medplum/issues/7310</a>. Rows have an array consisting of one commo=
n element present in every row and one unique element. With a statistics ta=
rget at the default 100, this pushes the threshold for vastly overestimated=
 row counts for the unique elements down to 7,937 rows.<div><br></div><div>=
In this case, the effects of the proposed patch are not applied since the m=
ost_common_elems array=C2=A0is not empty. I&#39;m not a statistician, so ma=
ybe this wouldn&#39;t be valid, but it seems like using the highest frequen=
cy of an element that did not qualify for the mce list instead of the 0.5% =
default frequency could be an elegant, but more invasive solution.=C2=A0</d=
iv><div><br></div><div>Simple repro of the problem:<br><br>CREATE TABLE pub=
lic.test(<br>=C2=A0 =C2=A0 id integer,<br>=C2=A0 =C2=A0 tags text[]<br>);<b=
r><div><br></div><div>INSERT INTO public.test (id, tags)<br>=C2=A0 =C2=A0 =
=C2=A0 =C2=A0 SELECT n, ARRAY[&#39;common&#39;, TO_CHAR(n,&#39;fm00000000&#=
39;)] FROM ( SELECT generate_series(1,7_937) AS n );<br></div><div><br></di=
v><div>ANALYZE public.test;<br><br>SELECT most_common_elems, most_common_el=
em_freqs FROM pg_stats WHERE schemaname =3D &#39;public&#39; AND tablename =
=3D &#39;test&#39; AND attname =3D &#39;tags&#39;;<br><br>EXPLAIN (ANALYZE,=
BUFFERS,VERBOSE)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 SELECT * FROM test WHERE ta=
gs &amp;&amp; ARRAY[&#39;common&#39;];<br><br>EXPLAIN (ANALYZE,BUFFERS,VERB=
OSE)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 SELECT * FROM test WHERE tags &amp;&amp=
; ARRAY[&#39;00000001&#39;];<br></div><div><br></div><div>With 7,936 rows:<=
/div><div>=C2=A0 =C2=A0 most_common_elems has 1,000 entries and looks like =
{00000001,00000003,00000009,...,common}</div><div>=C2=A0 =C2=A0 most_common=
_elem_freqs has 1,003 entries and looks like {0.00012600806,0.00012600806,0=
.00012600806,...,1,0.00012600806,1,0}</div><div><br></div><div>With 7,937+ =
rows:</div><div>=C2=A0 =C2=A0 most_common_elems is {common}</div><div>=C2=
=A0 =C2=A0 most_common_elem_freqs is {1,1,1,0}</div></div></div><br><div cl=
ass=3D"gmail_quote gmail_quote_container"><div dir=3D"ltr" class=3D"gmail_a=
ttr">On Mon, Sep 8, 2025 at 11:27=E2=80=AFAM Tom Lane &lt;<a href=3D"mailto=
:tgl@sss.pgh.pa.us">tgl@sss.pgh.pa.us</a>&gt; wrote:<br></div><blockquote c=
lass=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px soli=
d rgb(204,204,204);padding-left:1ex">I wrote:<br>
&gt; Well, we don&#39;t have a most common element in this scenario --- the=
<br>
&gt; whole point is that the occurrence counts resulting from the lossy<br>
&gt; counting algorithm are too low to be trustworthy.=C2=A0 However, what =
we<br>
&gt; do have is the cutoff frequency, and it seems to me that we could use<=
br>
&gt; that as the estimate of the maximum frequency of the non-MCEs.<br>
<br>
Here&#39;s a less crude patch for that.=C2=A0 The array_typanalyze.c change=
s<br>
are the same as before, but I reconsidered what to do about this<br>
stumbling block:<br>
<br>
&gt; Assuming we like this direction, the main thing that makes this a hack=
<br>
&gt; not a polished patch is that I had to strongarm the code into storing<=
br>
&gt; a zero-length values array.=C2=A0 What update_attstats would normally =
do<br>
&gt; is leave the values column of the MCELEM stats slot NULL, which then<b=
r>
&gt; causes get_attstatsslot to throw a that-shouldn&#39;t-be-null error.<b=
r>
&gt; An alternative answer is to change get_attstatsslot to allow a null,<b=
r>
&gt; but I&#39;m not sure that that&#39;s any cleaner.=C2=A0 Either way it =
seems like<br>
&gt; there&#39;s a hazard of breaking some code that isn&#39;t expecting th=
e case.<br>
<br>
I concluded that letting get_attstatsslot accept nulls is too risky;<br>
there is probably code that assumes that get_attstatsslot would&#39;ve<br>
rejected that.=C2=A0 Instead, this version changes update_attstats&#39; rul=
e<br>
for when to store an array rather than a null.=C2=A0 Now it will do so<br>
if the passed-in stavalues pointer isn&#39;t null, even if numvalues<br>
is zero.=C2=A0 I think that this doesn&#39;t change the outcome for any<br>
existing analyze routines because they wouldn&#39;t pass a data pointer<br>
if they have no values; and even if it does, storing an empty array<br>
not a null seems like it should be pretty harmless.<br>
<br>
&gt; An alternative that feels cleaner but a good bit more invasive<br>
&gt; is to get rid of the convention of storing the min/max/nulls<br>
&gt; frequencies as extra entries in the MCELEM numbers entry ---<br>
&gt; which surely is a hack too --- and put them into some new slot<br>
&gt; type.=C2=A0 I&#39;m not sure if that&#39;s enough nicer to be worth th=
e<br>
&gt; conversion pain.<br>
<br>
A year ago I would have seriously considered doing it that way.<br>
But now that we have code to dump-n-restore stats, that code would<br>
have to be adjusted to convert the old representation.=C2=A0 It&#39;s not<b=
r>
worth it for this case.<br>
<br>
Hence, v1 attached, now with a commit message.<br>
<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 regards, tom lane<br>
<br>
</blockquote></div>

--000000000000eebac8063e4efc63--