From: Tom Lane <tgl@sss.pgh.pa.us>
To: Dmitry Shalashov <skaurus@gmail.com>
cc: "pgsql-performance@postgresql.org" <pgsql-performance@postgresql.org>,
        pgsql-hackers@lists.postgresql.org
Subject: Re: Query became very slow after 9.6 -> 10 upgrade
In-reply-to: 
 <CAKPeCUGkCcp37oa3n=-9EDAujx_f190wFdmbfy_K4OF5H62JyQ@mail.gmail.com>
References: 
 <CAKPeCUGAeHgoh5O=SvcQxREVkoX7UdeJUMj1F5=aBNvoTa+O8w@mail.gmail.com>
 <13426.1511363963@sss.pgh.pa.us>
 <CAKPeCUGkCcp37oa3n=-9EDAujx_f190wFdmbfy_K4OF5H62JyQ@mail.gmail.com>
Comments: In-reply-to Dmitry Shalashov <skaurus@gmail.com>
	message dated "Thu, 23 Nov 2017 00:34:47 +0300"
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0"
Content-ID: <9747.1511392012.0@sss.pgh.pa.us>
Date: Wed, 22 Nov 2017 18:07:07 -0500
Message-ID: <9755.1511392027@sss.pgh.pa.us>
Precedence: bulk

------- =_aaaaaaaaaa0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <9747.1511392012.1@sss.pgh.pa.us>
Content-Transfer-Encoding: quoted-printable

Dmitry Shalashov <skaurus@gmail.com> writes:
> Turns out we had not 9.6 but 9.5.

I'd managed to reproduce the weird planner behavior locally in the
regression database:

regression=3D# create table foo (f1 int[], f2 int);
CREATE TABLE
regression=3D# explain select * from tenk1 where unique2 in (select distin=
ct unnest(f1) from foo where f2=3D1);
                                    QUERY PLAN                            =
         =

--------------------------------------------------------------------------=
---------
 Nested Loop  (cost=3D30.85..80.50 rows=3D6 width=3D244)
   ->  HashAggregate  (cost=3D30.57..30.63 rows=3D6 width=3D4)
         Group Key: (unnest(foo.f1))
         ->  HashAggregate  (cost=3D30.42..30.49 rows=3D6 width=3D4)
               Group Key: unnest(foo.f1)
               ->  ProjectSet  (cost=3D0.00..28.92 rows=3D600 width=3D4)
                     ->  Seq Scan on foo  (cost=3D0.00..25.88 rows=3D6 wid=
th=3D32)
                           Filter: (f2 =3D 1)
   ->  Index Scan using tenk1_unique2 on tenk1  (cost=3D0.29..8.30 rows=3D=
1 width=3D244)
         Index Cond: (unique2 =3D (unnest(foo.f1)))
(10 rows)

Digging into it, the reason for the duplicate HashAggregate step was that
query_supports_distinctness() punted on SRFs-in-the-targetlist, basically
on the argument that it wasn't worth extra work to handle that case.
Thinking a bit harder, it seems to me that the correct analysis is:
1. If we are proving distinctness on the grounds of a DISTINCT clause,
then it doesn't matter whether there are any SRFs, because DISTINCT
removes duplicates after tlist SRF expansion.
2. But tlist SRFs break the ability to prove distinctness on the grounds
of GROUP BY, unless all of them are within grouping columns.
It still seems like detecting the second case is harder than it's worth,
but we can trivially handle the first case, with little more than some
code rearrangement.

The other problem is that the output rowcount of the sub-select (ie, of
the HashAggregate) is being estimated as though the SRF weren't there.
This turns out to be because estimate_num_groups() doesn't consider the
possibility of SRFs in the grouping columns.  It never has, but in 9.6 and
before the problem was masked by the fact that grouping_planner scaled up
the result rowcount by tlist_returns_set_rows() *after* performing
grouping.  Now we're effectively doing that in the other order, which is
more correct, but that means estimate_num_groups() has to apply some sort
of adjustment.  I suggest that it just multiply its old estimate by the
maximum of the SRF expansion counts.  That's likely to be an overestimate,
but it's really hard to do better without specific knowledge of the
individual SRF's behavior.

In short, I propose the attached fixes.  I've checked this and it seems
to fix Dmitry's original problem according to the test case he sent
off-list.

			regards, tom lane


------- =_aaaaaaaaaa0
Content-Type: text/x-diff; name="improve-distinct-on-srf-estimates.patch";
	charset="us-ascii"
Content-ID: <9747.1511392012.2@sss.pgh.pa.us>
Content-Description: improve-distinct-on-srf-estimates.patch
Content-Transfer-Encoding: quoted-printable

diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optim=
izer/plan/analyzejoins.c
index 5b0da14..5783f90 100644
*** a/src/backend/optimizer/plan/analyzejoins.c
--- b/src/backend/optimizer/plan/analyzejoins.c
*************** rel_is_distinct_for(PlannerInfo *root, R
*** 744,751 ****
  bool
  query_supports_distinctness(Query *query)
  {
! 	/* we don't cope with SRFs, see comment below */
! 	if (query->hasTargetSRFs)
  		return false;
  =

  	/* check for features we can prove distinctness with */
--- 744,751 ----
  bool
  query_supports_distinctness(Query *query)
  {
! 	/* SRFs break distinctness except with DISTINCT, see below */
! 	if (query->hasTargetSRFs && query->distinctClause =3D=3D NIL)
  		return false;
  =

  	/* check for features we can prove distinctness with */
*************** query_is_distinct_for(Query *query, List
*** 787,806 ****
  	Assert(list_length(colnos) =3D=3D list_length(opids));
  =

  	/*
- 	 * A set-returning function in the query's targetlist can result in
- 	 * returning duplicate rows, if the SRF is evaluated after the
- 	 * de-duplication step; so we play it safe and say "no" if there are an=
y
- 	 * SRFs.  (We could be certain that it's okay if SRFs appear only in th=
e
- 	 * specified columns, since those must be evaluated before de-duplicati=
on;
- 	 * but it doesn't presently seem worth the complication to check that.)
- 	 */
- 	if (query->hasTargetSRFs)
- 		return false;
- =

- 	/*
  	 * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
  	 * columns in the DISTINCT clause appear in colnos and operator semanti=
cs
! 	 * match.
  	 */
  	if (query->distinctClause)
  	{
--- 787,796 ----
  	Assert(list_length(colnos) =3D=3D list_length(opids));
  =

  	/*
  	 * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
  	 * columns in the DISTINCT clause appear in colnos and operator semanti=
cs
! 	 * match.  This is true even if there are SRFs in the DISTINCT columns =
or
! 	 * elsewhere in the tlist.
  	 */
  	if (query->distinctClause)
  	{
*************** query_is_distinct_for(Query *query, List
*** 820,825 ****
--- 810,825 ----
  	}
  =

  	/*
+ 	 * Otherwise, a set-returning function in the query's targetlist can
+ 	 * result in returning duplicate rows, despite any grouping that might
+ 	 * occur before tlist evaluation.  (If all tlist SRFs are within GROUP =
BY
+ 	 * columns, it would be safe because they'd be expanded before grouping=
.
+ 	 * But it doesn't currently seem worth the effort to check for that.)
+ 	 */
+ 	if (query->hasTargetSRFs)
+ 		return false;
+ =

+ 	/*
  	 * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if a=
ll
  	 * the grouped columns appear in colnos and operator semantics match.
  	 */
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/self=
uncs.c
index 4bbb4a8..edff6da 100644
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
*************** estimate_num_groups(PlannerInfo *root, L
*** 3361,3366 ****
--- 3361,3367 ----
  					List **pgset)
  {
  	List	   *varinfos =3D NIL;
+ 	double		srf_multiplier =3D 1.0;
  	double		numdistinct;
  	ListCell   *l;
  	int			i;
*************** estimate_num_groups(PlannerInfo *root, L
*** 3394,3399 ****
--- 3395,3401 ----
  	foreach(l, groupExprs)
  	{
  		Node	   *groupexpr =3D (Node *) lfirst(l);
+ 		double		this_srf_multiplier;
  		VariableStatData vardata;
  		List	   *varshere;
  		ListCell   *l2;
*************** estimate_num_groups(PlannerInfo *root, L
*** 3402,3407 ****
--- 3404,3424 ----
  		if (pgset && !list_member_int(*pgset, i++))
  			continue;
  =

+ 		/*
+ 		 * Set-returning functions in grouping columns are a bit problematic.
+ 		 * The code below will effectively ignore their SRF nature and come up
+ 		 * with a numdistinct estimate as though they were scalar functions.
+ 		 * We compensate by scaling up the end result by the largest SRF
+ 		 * rowcount estimate.  (This will be an overestimate if the SRF
+ 		 * produces multiple copies of any output value, but it seems best to
+ 		 * assume the SRF's outputs are distinct.  In any case, it's probably
+ 		 * pointless to worry too much about this without much better
+ 		 * estimates for SRF output rowcounts than we have today.)
+ 		 */
+ 		this_srf_multiplier =3D expression_returns_set_rows(groupexpr);
+ 		if (srf_multiplier < this_srf_multiplier)
+ 			srf_multiplier =3D this_srf_multiplier;
+ =

  		/* Short-circuit for expressions returning boolean */
  		if (exprType(groupexpr) =3D=3D BOOLOID)
  		{
*************** estimate_num_groups(PlannerInfo *root, L
*** 3467,3475 ****
--- 3484,3498 ----
  	 */
  	if (varinfos =3D=3D NIL)
  	{
+ 		/* Apply SRF multiplier as we would do in the long path */
+ 		numdistinct *=3D srf_multiplier;
+ 		/* Round off */
+ 		numdistinct =3D ceil(numdistinct);
  		/* Guard against out-of-range answers */
  		if (numdistinct > input_rows)
  			numdistinct =3D input_rows;
+ 		if (numdistinct < 1.0)
+ 			numdistinct =3D 1.0;
  		return numdistinct;
  	}
  =

*************** estimate_num_groups(PlannerInfo *root, L
*** 3638,3643 ****
--- 3661,3670 ----
  		varinfos =3D newvarinfos;
  	} while (varinfos !=3D NIL);
  =

+ 	/* Now we can account for the effects of any SRFs */
+ 	numdistinct *=3D srf_multiplier;
+ =

+ 	/* Round off */
  	numdistinct =3D ceil(numdistinct);
  =

  	/* Guard against out-of-range answers */

------- =_aaaaaaaaaa0--