MIME-Version: 1.0
References: 
 <CAMbWs49rWYrecgreDhKsfx3VSDW=qo35s+iAmgGu=wpARrM8_g@mail.gmail.com>
In-Reply-To: 
 <CAMbWs49rWYrecgreDhKsfx3VSDW=qo35s+iAmgGu=wpARrM8_g@mail.gmail.com>
From: wenhui qiu <qiuwenhuifx@gmail.com>
Date: Mon, 13 Apr 2026 11:27:39 +0800
Message-ID: 
 <CAGjGUAK7cmV3u6YE3OBQCuhDh6hrhwY=meaEch0VDT3Kn32WDw@mail.gmail.com>
Subject: Re: Propagate stadistinct through GROUP BY/DISTINCT in subqueries and
 CTEs
To: Richard Guo <guofenglinux@gmail.com>
Cc: Pg Hackers <pgsql-hackers@lists.postgresql.org>
Content-Type: multipart/alternative; boundary="00000000000051c7e1064f4f11ca"
Archived-At: 
 <https://www.postgresql.org/message-id/CAGjGUAK7cmV3u6YE3OBQCuhDh6hrhwY%3DmeaEch0VDT3Kn32WDw%40mail.gmail.com>
Precedence: bulk

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

HI Richard

> + /* Convert negative stadistinct to absolute count */
> + if (stats->stadistinct < 0)
> + {
> + RelOptInfo *baserel =3D find_base_rel(subroot, var->varno);
> +
> + if (baserel->tuples > 0)
> + {
> + stats->stadistinct =3D (float4)
> + clamp_row_est(-stats->stadistinct * baserel->tuples);
> + }
> + }

Thanks so much for working on this! While looking at the negative
stadistinct conversion, I was wondering if we might run into a potential
edge case with multi-level nested subqueries. What do you think?

/* Convert negative stadistinct to absolute count */

    if (stats->stadistinct < 0)
    {
-       RelOptInfo *baserel =3D find_base_rel(subroot, var->varno);
+       RelOptInfo *baserel =3D vardata->rel;

-       if (baserel->tuples > 0)
+       if (baserel && baserel->tuples > 0)
        {
            stats->stadistinct =3D (float4)
                clamp_row_est(-stats->stadistinct * baserel->tuples);
        }
    }

Thanks

On Mon, Apr 13, 2026 at 9:19=E2=80=AFAM Richard Guo <guofenglinux@gmail.com=
> wrote:

> I complained in [1] that some TPC-DS queries suffer from very poor
> cardinality estimates on CTE scan filters, to the point that simply
> disabling nestloop makes some queries run hundreds of times faster.
> Here's a simple reproduction:
>
> create table t (a int, b int, c int);
> insert into t select i%2, i, i from generate_series(1,1000) i;
> analyze t;
>
> explain analyze
> with cte as (select a, b, avg(c) as avg from t group by a, b)
> select * from cte t1, cte t2
> where t1.a =3D 1 and t2.a =3D 1 and t1.avg =3D t2.avg;
>
> Column 'a' has only 2 distinct values, so the filter a=3D1 on the
> 1000-row CTE output should estimate ~500 rows (assuming these values
> are equally common).  Instead, the CTE scan estimates 5 rows (1000 *
> 1/200) because examine_simple_variable returns early when the subquery
> has GROUP BY, and selectivity estimation falls back on
> 1/DEFAULT_NUM_DISTINCT.
>
>    ->  CTE Scan on cte t1  (cost=3D0.00..22.50 rows=3D5 width=3D40)
>                    (actual time=3D4.874..5.053 rows=3D500.00 loops=3D1)
>
> As a result, this query ends up with a Nested Loop plan, and the
> Execution Time is 192.907 ms.
>
> For DISTINCT or GROUP BY key columns that are simple Vars, I think we
> can propagate stadistinct from the base table, because the set of
> distinct values is preserved after grouping.  MCV frequencies,
> histograms, and correlation data are not valid since GROUP BY and
> DISTINCT change the frequency distribution, but with stadistinct
> alone, callers like var_eq_const() can use a 1/ndistinct estimate
> rather than 1/DEFAULT_NUM_DISTINCT.
>
> Attached is a patch to do this.  With the patch, the example above
> estimates 500 rows ...
>
>    ->  CTE Scan on cte t1  (cost=3D0.00..22.50 rows=3D500 width=3D40)
>                    (actual time=3D3.785..4.143 rows=3D500.00 loops=3D1)
>
> ... and chooses a Hash Join, with an Execution Time of 8.238 ms (~20x
> faster).
>
> I tested this patch on TPC-DS query 31:
>
> -- on master:
>  Planning Time: 5.207 ms
>  Execution Time: 1536140.258 ms
>
> -- on patched:
>  Planning Time: 5.140 ms
>  Execution Time: 1149.482 ms
>
> Over 1300x faster.
>
> Does this approach make sense?  Any thoughts?
>
> [1]
> https://postgr.es/m/CAMbWs4-QU_nkFqFZLdzWRsEsVE8aLWx4qBBVq7g4rXw+cvYDMg@m=
ail.gmail.com
>
> - Richard
>

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

<div dir=3D"ltr">HI Richard<div><p style=3D"color:rgb(0,0,0)">&gt; +	/* Con=
vert negative stadistinct to absolute count */<br>&gt; +	if (stats-&gt;stad=
istinct &lt; 0)<br>&gt; +	{<br>&gt; +		RelOptInfo *baserel =3D find_base_re=
l(subroot, var-&gt;varno);<br>&gt; +<br>&gt; +		if (baserel-&gt;tuples &gt;=
 0)<br>&gt; +		{<br>&gt; +			stats-&gt;stadistinct =3D (float4)<br>&gt; +		=
		clamp_row_est(-stats-&gt;stadistinct * baserel-&gt;tuples);<br>&gt; +		}<=
br>&gt; +	}<br></p><p style=3D"color:rgb(0,0,0)">Thanks so much for working=
 on this! While looking at the negative stadistinct conversion, I was wonde=
ring if we might run into a potential edge case with multi-level nested sub=
queries. What do you think?<br></p><p style=3D"color:rgb(0,0,0)">/* Convert=
 negative stadistinct to absolute count  */<br></p><p style=3D"color:rgb(0,=
0,0)">=C2=A0 =C2=A0 if (stats-&gt;stadistinct &lt; 0)<br>=C2=A0 =C2=A0 {<br=
>- =C2=A0 =C2=A0 =C2=A0 RelOptInfo *baserel =3D find_base_rel(subroot, var-=
&gt;varno);<br>+ =C2=A0 =C2=A0 =C2=A0 RelOptInfo *baserel =3D vardata-&gt;r=
el;<br><br>- =C2=A0 =C2=A0 =C2=A0 if (baserel-&gt;tuples &gt; 0)<br>+ =C2=
=A0 =C2=A0 =C2=A0 if (baserel &amp;&amp; baserel-&gt;tuples &gt; 0)<br>=C2=
=A0 =C2=A0 =C2=A0 =C2=A0 {<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 sta=
ts-&gt;stadistinct =3D (float4)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 clamp_row_est(-stats-&gt;stadistinct * baserel-&gt;tuples=
);<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 }<br>=C2=A0 =C2=A0 }<span style=3D"font-f=
amily:-webkit-standard;font-size:medium"><br></span></p><p style=3D"color:r=
gb(0,0,0)">Thanks=C2=A0</p></div></div><br><div class=3D"gmail_quote gmail_=
quote_container"><div dir=3D"ltr" class=3D"gmail_attr">On Mon, Apr 13, 2026=
 at 9:19=E2=80=AFAM Richard Guo &lt;<a href=3D"mailto:guofenglinux@gmail.co=
m">guofenglinux@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmai=
l_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,20=
4,204);padding-left:1ex">I complained in [1] that some TPC-DS queries suffe=
r from very poor<br>
cardinality estimates on CTE scan filters, to the point that simply<br>
disabling nestloop makes some queries run hundreds of times faster.<br>
Here&#39;s a simple reproduction:<br>
<br>
create table t (a int, b int, c int);<br>
insert into t select i%2, i, i from generate_series(1,1000) i;<br>
analyze t;<br>
<br>
explain analyze<br>
with cte as (select a, b, avg(c) as avg from t group by a, b)<br>
select * from cte t1, cte t2<br>
where t1.a =3D 1 and t2.a =3D 1 and t1.avg =3D t2.avg;<br>
<br>
Column &#39;a&#39; has only 2 distinct values, so the filter a=3D1 on the<b=
r>
1000-row CTE output should estimate ~500 rows (assuming these values<br>
are equally common).=C2=A0 Instead, the CTE scan estimates 5 rows (1000 *<b=
r>
1/200) because examine_simple_variable returns early when the subquery<br>
has GROUP BY, and selectivity estimation falls back on<br>
1/DEFAULT_NUM_DISTINCT.<br>
<br>
=C2=A0 =C2=A0-&gt;=C2=A0 CTE Scan on cte t1=C2=A0 (cost=3D0.00..22.50 rows=
=3D5 width=3D40)<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(actua=
l time=3D4.874..5.053 rows=3D500.00 loops=3D1)<br>
<br>
As a result, this query ends up with a Nested Loop plan, and the<br>
Execution Time is 192.907 ms.<br>
<br>
For DISTINCT or GROUP BY key columns that are simple Vars, I think we<br>
can propagate stadistinct from the base table, because the set of<br>
distinct values is preserved after grouping.=C2=A0 MCV frequencies,<br>
histograms, and correlation data are not valid since GROUP BY and<br>
DISTINCT change the frequency distribution, but with stadistinct<br>
alone, callers like var_eq_const() can use a 1/ndistinct estimate<br>
rather than 1/DEFAULT_NUM_DISTINCT.<br>
<br>
Attached is a patch to do this.=C2=A0 With the patch, the example above<br>
estimates 500 rows ...<br>
<br>
=C2=A0 =C2=A0-&gt;=C2=A0 CTE Scan on cte t1=C2=A0 (cost=3D0.00..22.50 rows=
=3D500 width=3D40)<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(actua=
l time=3D3.785..4.143 rows=3D500.00 loops=3D1)<br>
<br>
... and chooses a Hash Join, with an Execution Time of 8.238 ms (~20x<br>
faster).<br>
<br>
I tested this patch on TPC-DS query 31:<br>
<br>
-- on master:<br>
=C2=A0Planning Time: 5.207 ms<br>
=C2=A0Execution Time: 1536140.258 ms<br>
<br>
-- on patched:<br>
=C2=A0Planning Time: 5.140 ms<br>
=C2=A0Execution Time: 1149.482 ms<br>
<br>
Over 1300x faster.<br>
<br>
Does this approach make sense?=C2=A0 Any thoughts?<br>
<br>
[1] <a href=3D"https://postgr.es/m/CAMbWs4-QU_nkFqFZLdzWRsEsVE8aLWx4qBBVq7g=
4rXw+cvYDMg@mail.gmail.com" rel=3D"noreferrer" target=3D"_blank">https://po=
stgr.es/m/CAMbWs4-QU_nkFqFZLdzWRsEsVE8aLWx4qBBVq7g4rXw+cvYDMg@mail.gmail.co=
m</a><br>
<br>
- Richard<br>
</blockquote></div>

--00000000000051c7e1064f4f11ca--