From: Manuel Weitzman <manuelweitzman@gmail.com>
Message-Id: <B7F75B2A-A241-46BA-B6FF-E95874C39D65@gmail.com>
Content-Type: multipart/mixed;
	boundary="Apple-Mail=_6506C5C0-94E0-498D-B65A-9C29911124F1"
Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.100.0.2.22\))
Subject: Re: Planning performance problem (67626.278ms)
Date: Thu, 1 Jul 2021 16:49:44 -0400
In-Reply-To: <E4AB7AC2-596B-4B60-A5D4-D4BD48F9DE55@gmail.com>
Cc: Ranier Vilela <ranier.vf@gmail.com>,
 David Rowley <dgrowleyml@gmail.com>,
 Jeremy Schneider <schnjere@amazon.com>,
 "pgsql-performance@lists.postgresql.org"
 <pgsql-performance@lists.postgresql.org>,
 Andres Freund <andres@anarazel.de>
To: Tom Lane <tgl@sss.pgh.pa.us>
References: <6d58f68e-ed1a-c48e-1440-691554f6e1e7@9livesdata.com>
 <CAFj8pRDDnOVNcU7dx4+oKH0x4-DsmL3XRWppQ8Cf5wwJ=G2fPg@mail.gmail.com>
 <20190408144210.GG10080@telsasoft.com>
 <b145b428-3351-ec86-d522-100a5bf8ded7@amazon.com>
 <20190408232644.r6xixkeulsmomwfj@alap3.anarazel.de>
 <3f5e5673-06aa-bf7c-cdb7-0e053c45ba26@amazon.com>
 <CAApHDvq9o1J45is6w-3Gv1UgtuDQ4eQP4UhFPQSnQmEH_EijvQ@mail.gmail.com>
 <767433.1619015825@sss.pgh.pa.us>
 <EFE95962-F088-45E2-BD13-AA5012829A69@gmail.com>
 <F06D0C00-DE75-4688-98B0-85A46E8F312C@gmail.com>
 <CAEudQApVF7TX-EJXwBz4TUhH6NzNB-wXqhs4wj+qSe6Vw3H5-Q@mail.gmail.com>
 <1588548.1624234651@sss.pgh.pa.us>
 <39C2266C-3143-4A7A-BCAF-E0C8394F9D24@gmail.com>
 <500142.1624995808@sss.pgh.pa.us>
 <F9C9FBE0-C535-49DA-B913-F11AC30F8F4E@gmail.com>
 <508897.1625005916@sss.pgh.pa.us>
 <E4AB7AC2-596B-4B60-A5D4-D4BD48F9DE55@gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/B7F75B2A-A241-46BA-B6FF-E95874C39D65%40gmail.com>
Precedence: bulk


--Apple-Mail=_6506C5C0-94E0-498D-B65A-9C29911124F1
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=us-ascii


> On 30-06-2021, at 16:56, Manuel Weitzman <manuelweitzman@gmail.com> wrote:
> 
> One way in which I see possible to share this kind of information (of
> extremal values) across RestrictInfos is to store the known variable
> ranges in PlannerInfo (or within a member of such struct), which seems
> to be around everywhere it would be needed.

I have written a new patch that's (hopefully) better than the first
one I sent, to store the extremal index values within PlannerInfo.

> it is also possible to reproduce the increasing cost in planning
> buffers for each new join on a distinct table being added:
> 
> [...]
> 

> I can imagine that deconstruct_jointree() and
> generate_join_implied_equalities() would generate multiple
> RestrictInfos, in which many of them a constraint on a.a would be
> involved (each involving a different table).

I also attached an example in which there are RestrictInfos generated
for multiple tables instead of just a single aliased one. The buffers
read for planning also increase with each join added to the query.


Best regards,
Manuel


--Apple-Mail=_6506C5C0-94E0-498D-B65A-9C29911124F1
Content-Disposition: attachment;
	filename=actual_variable_range_cache.patch
Content-Type: application/octet-stream;
	x-unix-mode=0644;
	name="actual_variable_range_cache.patch"
Content-Transfer-Encoding: 7bit

diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 5d515842dc..cb397c6012 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -636,6 +636,7 @@ subquery_planner(PlannerGlobal *glob, Query *parse,
 		root->wt_param_id = -1;
 	root->non_recursive_path = NULL;
 	root->partColsUpdated = false;
+	root->actual_var_ranges = NIL;
 
 	/*
 	 * If there is a WITH list, process each WITH query and either convert it
diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 9ff2b595a8..9672934534 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -936,6 +936,7 @@ pull_up_simple_subquery(PlannerInfo *root, Node *jtnode, RangeTblEntry *rte,
 	subroot->hasRecursion = false;
 	subroot->wt_param_id = -1;
 	subroot->non_recursive_path = NULL;
+	subroot->actual_var_ranges = NIL;
 
 	/* No CTEs to worry about */
 	Assert(subquery->cteList == NIL);
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
index e96bfce4dc..a6e73d0b8f 100644
--- a/src/backend/utils/adt/selfuncs.c
+++ b/src/backend/utils/adt/selfuncs.c
@@ -5585,9 +5585,12 @@ get_actual_variable_range(PlannerInfo *root, VariableStatData *vardata,
 						  Datum *min, Datum *max)
 {
 	bool		have_data = false;
+	bool		have_cache = false;
+	ActualVarRangeInfo *cache = NULL;
 	RelOptInfo *rel = vardata->rel;
 	RangeTblEntry *rte;
 	ListCell   *lc;
+	PlannerInfo *proot;
 
 	/* No hope if no relation or it doesn't have indexes */
 	if (rel == NULL || rel->indexlist == NIL)
@@ -5648,7 +5651,37 @@ get_actual_variable_range(PlannerInfo *root, VariableStatData *vardata,
 		}
 
 		/*
-		 * Found a suitable index to extract data from.  Set up some data that
+		 * Found a suitable index to extract data from.
+		 * Do we have the extremal values on PlannerInfo cache?
+		 *
+		 * If this is a subquery, traverse to the top-level PlannerInfo
+		 * to read/store ActualVarRangeInfos.
+		 */
+		proot = root;
+		while (proot->parent_root != NULL)
+			proot = proot->parent_root;
+
+		foreach(lc, proot->actual_var_ranges)
+		{
+			cache = (ActualVarRangeInfo *) lfirst(lc);
+
+			if (cache->indexoid != index->indexoid)
+				continue;
+			have_cache = true;
+
+			if (min && cache->min)
+				*min = datumCopy(cache->min, cache->typByVal, cache->typLen);
+			if (max && cache->max)
+				*max = datumCopy(cache->max, cache->typByVal, cache->typLen);
+
+			if ((min && !cache->min) || (max && !cache->max))
+				break;
+
+			return have_cache;
+		}
+
+		/*
+		 * Nope, read actual range from index. Set up some data that
 		 * can be used by both invocations of get_actual_variable_endpoint.
 		 */
 		{
@@ -5689,7 +5722,7 @@ get_actual_variable_range(PlannerInfo *root, VariableStatData *vardata,
 								   (Datum) 0);	/* constant */
 
 			/* If min is requested ... */
-			if (min)
+			if (min && (!have_cache || !cache->min))
 			{
 				have_data = get_actual_variable_endpoint(heapRel,
 														 indexRel,
@@ -5708,7 +5741,7 @@ get_actual_variable_range(PlannerInfo *root, VariableStatData *vardata,
 			}
 
 			/* If max is requested, and we didn't find the index is empty */
-			if (max && have_data)
+			if (max && have_data && (!have_cache || !cache->max))
 			{
 				/* scan in the opposite direction; all else is the same */
 				have_data = get_actual_variable_endpoint(heapRel,
@@ -5731,6 +5764,36 @@ get_actual_variable_range(PlannerInfo *root, VariableStatData *vardata,
 			MemoryContextSwitchTo(oldcontext);
 			MemoryContextDelete(tmpcontext);
 
+			/*
+			 * Store variable range in PlannerInfo cache for subsequent calls.
+			 *
+			 * If there's already a ActualVarRangeInfo for this index, just
+			 * fill the missing information.
+			 */
+			if (have_data && !have_cache)
+			{
+				oldcontext = MemoryContextSwitchTo(proot->planner_cxt);
+				cache = (ActualVarRangeInfo *) palloc(sizeof(ActualVarRangeInfo));
+
+				cache->indexoid = index->indexoid;
+				cache->min = PointerGetDatum(NULL);
+				cache->max = PointerGetDatum(NULL);
+				cache->typByVal = typByVal;
+				cache->typLen = typLen;
+
+				proot->actual_var_ranges = lappend(proot->actual_var_ranges,
+												   cache);
+				MemoryContextSwitchTo(oldcontext);
+			}
+
+			if (have_data)
+			{
+				if (min && !cache->min)
+					cache->min = datumCopy(*min, typByVal, typLen);
+				if (max && !cache->max)
+					cache->max = datumCopy(*max, typByVal, typLen);
+			}
+
 			/* And we're done */
 			break;
 		}
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 69150e46eb..d92f169b76 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -362,6 +362,9 @@ struct PlannerInfo
 
 	/* Does this query modify any partition key columns? */
 	bool		partColsUpdated;
+
+	/* List of ActualVarRangeInfos, a cache for get_actual_variable_range */
+	List	   *actual_var_ranges;
 };
 
 
@@ -2333,6 +2336,24 @@ typedef struct MinMaxAggInfo
 	Param	   *param;			/* param for subplan's output */
 } MinMaxAggInfo;
 
+
+/*
+ * Store both extremal values of an index.
+ *
+ * The planner stores ActualVarRangeInfos in PlannerInfo to avoid repeated
+ * executions of get_actual_variable_range that can be very expensive,
+ * particularly if the index is bloated on any of the extremes.
+ */
+typedef struct ActualVarRangeInfo
+{
+	Datum	min;				/* index minimal value */
+	Datum	max;				/* index maximal value */
+	Oid		indexoid;
+	int16	typLen;
+	bool	typByVal;
+} ActualVarRangeInfo;
+
+
 /*
  * At runtime, PARAM_EXEC slots are used to pass values around from one plan
  * node to another.  They can be used to pass values down into subqueries (for

--Apple-Mail=_6506C5C0-94E0-498D-B65A-9C29911124F1
Content-Disposition: attachment;
	filename=planning_buffers.sql
Content-Type: application/octet-stream;
	x-unix-mode=0644;
	name="planning_buffers.sql"
Content-Transfer-Encoding: 7bit

create table p (
	id bigint primary key
) with (autovacuum_enabled=off);

create table p1 (
	p_id bigint primary key references p(id)
) with (autovacuum_enabled=off);

create table p2 (
	p_id bigint primary key references p(id)
) with (autovacuum_enabled=off);

create table p3 (
	p_id bigint primary key references p(id)
) with (autovacuum_enabled=off);

create table p4 (
	p_id bigint primary key references p(id)
) with (autovacuum_enabled=off);

create table p5 (
	p_id bigint primary key references p(id)
) with (autovacuum_enabled=off);


insert into p  select x from generate_series(1, 10000000) x;
insert into p1 select x from generate_series(1, 10000000) x where x % 5 = 1;
insert into p2 select x from generate_series(1, 10000000) x where x % 5 = 2;
insert into p3 select x from generate_series(1, 10000000) x where x % 5 = 3;
insert into p4 select x from generate_series(1, 10000000) x where x % 5 = 4;
insert into p5 select x from generate_series(1, 10000000) x where x % 5 = 0;

analyze p, p1, p2, p3, p4, p5;

begin;
insert into p select x from generate_series(10000001, 20000000) x;
rollback;

-- uncomment one join/projection at a time to see
-- planning buffers increase
explain (analyze, buffers)
select
	p.*
--	, p1.*
--	, p2.*
--	, p3.*
--	, p4.*
--	, p5.*
from p
--left join p1 on (p.id = p1.p_id)
--left join p2 on (p.id = p2.p_id)
--left join p3 on (p.id = p3.p_id)
--left join p4 on (p.id = p4.p_id)
--left join p5 on (p.id = p5.p_id)
where p.id IN (1,100,10000,1000000,10000000, 20000000);

--Apple-Mail=_6506C5C0-94E0-498D-B65A-9C29911124F1--