From: Manuel Weitzman <manuelweitzman@gmail.com>
Message-Id: <F06D0C00-DE75-4688-98B0-85A46E8F312C@gmail.com>
Content-Type: multipart/mixed;
	boundary="Apple-Mail=_3FBDACC4-0323-4B92-A579-9140BC1AD60D"
Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.60.0.2.21\))
Subject: Re: Planning performance problem (67626.278ms)
Date: Sat, 19 Jun 2021 20:09:58 -0400
In-Reply-To: <EFE95962-F088-45E2-BD13-AA5012829A69@gmail.com>
Cc: 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>
Archived-At: 
 <https://www.postgresql.org/message-id/F06D0C00-DE75-4688-98B0-85A46E8F312C%40gmail.com>
Precedence: bulk


--Apple-Mail=_3FBDACC4-0323-4B92-A579-9140BC1AD60D
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii

Hello everyone,

> Apparently, the planner isn't reusing the data boundaries across =
alternative
> plans. It would be nicer if the planner remembered each column =
boundaries
> for later reuse (within the same planner execution).

I've written a very naive (and crappy) patch to show how adding
memorization to get_actual_variable_range() could help the planner on
scenarios with a big number of joins.

For the previous example,

> explain (analyze, buffers)
> select * from a
> join b b1 on (b1.a =3D a.a)
> join b b2 on (b2.a =3D a.a)
> where b1.a in (1,100,10000,1000000,1000001);

each time you add a join clause the planner has to read an extra ~5[K]
buffers and gets about 200[ms] slower.

1 join
 Planning:
   Buffers: shared hit=3D9 read=3D27329
 Planning Time: 101.745 ms
 Execution Time: 0.082 ms

2 joins
 Planning:
   Buffers: shared hit=3D42 read=3D81988
 Planning Time: 303.237 ms
 Execution Time: 0.102 ms

3 joins
 Planning:
   Buffers: shared hit=3D94 read=3D136660
 Planning Time: 508.947 ms
 Execution Time: 0.155 ms

4 joins
 Planning:
   Buffers: shared hit=3D188 read=3D191322
 Planning Time: 710.981 ms
 Execution Time: 0.168 ms


After adding memorization the cost in buffers remains constant and the
latency deteriorates only marginally (as expected) with each join.

1 join
 Planning:
   Buffers: shared hit=3D10 read=3D27328
 Planning Time: 97.889 ms
 Execution Time: 0.066 ms

2 joins
 Planning:
   Buffers: shared hit=3D7 read=3D27331
 Planning Time: 100.589 ms
 Execution Time: 0.111 ms

3 joins
 Planning:
   Buffers: shared hit=3D9 read=3D27329
 Planning Time: 105.669 ms
 Execution Time: 0.134 ms

4 joins
 Planning:
   Buffers: shared hit=3D132 read=3D27370
 Planning Time: 155.716 ms
 Execution Time: 0.219 ms


I'd be happy to improve this patch into something better. Though I'd
like suggestions on how to do it:
I have this idea of creating a local "memorization" struct instance =
within
standard_planner(). That would require passing on a pointer down until
it reaches get_actual_variable_range(), which I think would be quite
ugly, if done just to improve the planner for this scenario.
Is there any better mechanism I could reuse from other modules? (utils
or cache, for example).


Regards,
Manuel


--Apple-Mail=_3FBDACC4-0323-4B92-A579-9140BC1AD60D
Content-Disposition: attachment;
	filename=actual_variable_range_memorization.diff
Content-Type: application/octet-stream;
	x-unix-mode=0644;
	name="actual_variable_range_memorization.diff"
Content-Transfer-Encoding: 7bit

diff --git i/src/backend/optimizer/plan/planner.c w/src/backend/optimizer/plan/planner.c
index 5d515842dc..65d74be557 100644
--- i/src/backend/optimizer/plan/planner.c
+++ w/src/backend/optimizer/plan/planner.c
@@ -316,6 +316,10 @@ standard_planner(Query *parse, const char *query_string, int cursorOptions,
 	glob->transientPlan = false;
 	glob->dependsOnRole = false;
 
+
+	/* clear crappy variable range cache */
+	clear_variable_range_cache();
+
 	/*
 	 * Assess whether it's feasible to use parallel mode for this query. We
 	 * can't do this in a standalone backend, or if the command will try to
diff --git i/src/backend/utils/adt/selfuncs.c w/src/backend/utils/adt/selfuncs.c
index e96bfce4dc..0e0cc68307 100644
--- i/src/backend/utils/adt/selfuncs.c
+++ w/src/backend/utils/adt/selfuncs.c
@@ -5567,6 +5567,99 @@ get_stats_slot_range(AttStatsSlot *sslot, Oid opfuncoid, FmgrInfo *opproc,
 }
 
 
+/*
+ * a lot of crappy code to emulate variable range caching
+ * just intended for testing purposes
+ */
+typedef struct ActualVariableRangeCache ActualVariableRangeCache;
+struct ActualVariableRangeCache {
+	Oid		indexoid;
+	int64	min_value;
+	int64	max_value;
+	bool	has_min;
+	bool	has_max;
+};
+
+static unsigned long range_caches_size = 0;
+static ActualVariableRangeCache range_caches[1000] = {{0, 0, 0, false, false}};
+
+void
+clear_variable_range_cache(void)
+{
+	for (unsigned long i = 0; i < range_caches_size; i++) {
+		range_caches[i].indexoid = 0;
+		range_caches[i].has_min = false;
+		range_caches[i].has_max = false;
+	}
+	range_caches_size = 0;
+}
+
+static bool
+get_cached_actual_variable_min(Oid indexoid, Datum *min)
+{
+	for (unsigned long i = 0; i < range_caches_size; i++) {
+		if (range_caches[i].indexoid == indexoid) {
+			if (!range_caches[i].has_min)
+				return false;
+
+			*min = range_caches[i].min_value;
+			return true;
+		}
+	}
+	return false;
+}
+
+
+static bool
+get_cached_actual_variable_max(Oid indexoid, Datum *max)
+{
+	for (unsigned long i = 0; i < range_caches_size; i++) {
+		if (range_caches[i].indexoid == indexoid) {
+			if (!range_caches[i].has_max)
+				return false;
+
+			*max = range_caches[i].max_value;
+			return true;
+		}
+	}
+	return false;
+}
+
+
+static void
+add_actual_variable_min_to_cache(Oid indexoid, Datum *min)
+{
+	for (unsigned long i = 0; i < range_caches_size; i++) {
+		if (range_caches[i].indexoid == indexoid) {
+			range_caches[i].min_value = *min;
+			range_caches[i].has_min = true;
+			return;
+		}
+	}
+	range_caches[range_caches_size].indexoid = indexoid;
+	range_caches[range_caches_size].min_value = *min;
+	range_caches[range_caches_size].has_min = true;
+	range_caches_size++;
+}
+
+
+static void
+add_actual_variable_max_to_cache(Oid indexoid, Datum *max)
+{
+	for (unsigned long i = 0; i < range_caches_size; i++) {
+		if (range_caches[i].indexoid == indexoid) {
+			range_caches[i].max_value = *max;
+			range_caches[i].has_max = true;
+			return;
+		}
+	}
+	range_caches[range_caches_size].indexoid = indexoid;
+	range_caches[range_caches_size].max_value = *max;
+	range_caches[range_caches_size].has_max = true;
+	range_caches_size++;
+}
+
+
 /*
  * get_actual_variable_range
  *		Attempt to identify the current *actual* minimum and/or maximum
@@ -5691,15 +5784,23 @@ get_actual_variable_range(PlannerInfo *root, VariableStatData *vardata,
 			/* If min is requested ... */
 			if (min)
 			{
-				have_data = get_actual_variable_endpoint(heapRel,
-														 indexRel,
-														 indexscandir,
-														 scankeys,
-														 typLen,
-														 typByVal,
-														 slot,
-														 oldcontext,
-														 min);
+				/* try to reuse min from previous planner nodes */
+				have_data = get_cached_actual_variable_min(index->indexoid, min);
+				/* or fetch from index if first time here */
+				if (!have_data)
+					have_data = get_actual_variable_endpoint(heapRel,
+															 indexRel,
+															 indexscandir,
+															 scankeys,
+															 typLen,
+															 typByVal,
+															 slot,
+															 oldcontext,
+															 min);
+				/* update the min memorization */
+				if (have_data)
+					add_actual_variable_min_to_cache(index->indexoid,
+													 min);
 			}
 			else
 			{
@@ -5710,16 +5811,25 @@ 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)
 			{
+				/* try to reuse max from previous planner nodes */
+				have_data = get_cached_actual_variable_max(index->indexoid, max);
+
+				/* or fetch from index if first time here */
 				/* scan in the opposite direction; all else is the same */
-				have_data = get_actual_variable_endpoint(heapRel,
-														 indexRel,
-														 -indexscandir,
-														 scankeys,
-														 typLen,
-														 typByVal,
-														 slot,
-														 oldcontext,
-														 max);
+				if (!have_data)
+					have_data = get_actual_variable_endpoint(heapRel,
+															 indexRel,
+															 -indexscandir,
+															 scankeys,
+															 typLen,
+															 typByVal,
+															 slot,
+															 oldcontext,
+															 max);
+				/* update the max memorization */
+				if (have_data)
+					add_actual_variable_max_to_cache(index->indexoid,
+													 max);
 			}
 
 			/* Clean everything up */
diff --git i/src/include/utils/selfuncs.h w/src/include/utils/selfuncs.h
index 7ac4a06391..a46c272ac7 100644
--- i/src/include/utils/selfuncs.h
+++ w/src/include/utils/selfuncs.h
@@ -220,4 +220,7 @@ extern Selectivity scalararraysel_containment(PlannerInfo *root,
 											  Oid elemtype, bool isEquality, bool useOr,
 											  int varRelid);
 
+extern void
+clear_variable_range_cache(void);
+
 #endif							/* SELFUNCS_H */

--Apple-Mail=_3FBDACC4-0323-4B92-A579-9140BC1AD60D--