Add LSN <-> time conversion functionality

From 8590125d66ce366b35251e5aff14db1a858edda9 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 16:40:27 -0500
Subject: [PATCH v2 2/5] Add LSNTimeline for converting LSN <-> time

Add a new structure, LSNTimeline, consisting of LSNTimes -- each an LSN,
time pair. Each LSNTime can represent multiple logical LSN, time pairs,
referred to as members. LSN <-> time conversions can be done using
linear interpolation with two LSNTimes on the LSNTimeline.

This commit does not add a global instance of LSNTimeline. It adds the
structures and functions needed to maintain and access such a timeline.
---
 src/backend/utils/activity/pgstat_wal.c | 199 ++++++++++++++++++++++++
 src/include/pgstat.h                    |  34 ++++
 src/tools/pgindent/typedefs.list        |   2 +
 3 files changed, 235 insertions(+)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index 1a3c0e1a669..e8d9660f82e 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -17,8 +17,11 @@
 
 #include "postgres.h"
 
+#include "access/xlog.h"
 #include "utils/pgstat_internal.h"
 #include "executor/instrument.h"
+#include "utils/builtins.h"
+#include "utils/timestamp.h"
 
 
 PgStat_PendingWalStats PendingWalStats = {0};
@@ -32,6 +35,12 @@ PgStat_PendingWalStats PendingWalStats = {0};
 static WalUsage prevWalUsage;
 
 
+static void lsntime_absorb(LSNTime *a, const LSNTime *b);
+void lsntime_insert(LSNTimeline *timeline, TimestampTz time, XLogRecPtr lsn);
+
+XLogRecPtr estimate_lsn_at_time(const LSNTimeline *timeline, TimestampTz time);
+TimestampTz estimate_time_at_lsn(const LSNTimeline *timeline, XLogRecPtr lsn);
+
 /*
  * Calculate how much WAL usage counters have increased and update
  * shared WAL and IO statistics.
@@ -184,3 +193,193 @@ pgstat_wal_snapshot_cb(void)
 		   sizeof(pgStatLocal.snapshot.wal));
 	LWLockRelease(&stats_shmem->lock);
 }
+
+/*
+ * Set *a to be the earlier of *a or *b.
+ */
+static void
+lsntime_absorb(LSNTime *a, const LSNTime *b)
+{
+	LSNTime		result;
+	uint64		new_members = a->members + b->members;
+
+	if (a->time < b->time)
+		result = *a;
+	else if (b->time < a->time)
+		result = *b;
+	else if (a->lsn < b->lsn)
+		result = *a;
+	else if (b->lsn < a->lsn)
+		result = *b;
+	else
+		result = *a;
+
+	*a = result;
+	a->members = new_members;
+}
+
+/*
+ * Insert a new LSNTime into the LSNTimeline in the first element with spare
+ * capacity.
+ */
+void
+lsntime_insert(LSNTimeline *timeline, TimestampTz time,
+			   XLogRecPtr lsn)
+{
+	LSNTime		temp;
+	LSNTime		carry = {.lsn = lsn,.time = time,.members = 1};
+
+	for (int i = 0; i < timeline->length; i++)
+	{
+		bool		full;
+		LSNTime    *cur = &timeline->data[i];
+
+		/*
+		 * An array element's capacity to represent members is 2 ^ its
+		 * position in the array.
+		 */
+		full = cur->members >= (1 << i);
+
+		/*
+		 * If the current element is not yet at capacity, then insert the
+		 * passed-in LSNTime into this element by taking the smaller of the it
+		 * and the current LSNTime element. This is required to ensure that
+		 * time moves forward on the timeline.
+		 */
+		if (!full)
+		{
+			Assert(cur->members == carry.members);
+			Assert(cur->members + carry.members <= 1 << i);
+			lsntime_absorb(cur, &carry);
+			return;
+		}
+
+		/*
+		 * If the current element is full, ensure that the inserting LSNTime
+		 * is larger than the current element. This must be true for time to
+		 * move forward on the timeline.
+		 */
+		Assert(carry.lsn >= cur->lsn || carry.time >= cur->time);
+
+		/*
+		 * If the element is at capacity, swap the element with the carry and
+		 * continue on to find an element with space to represent the new
+		 * member.
+		 */
+		temp = *cur;
+		*cur = carry;
+		carry = temp;
+	}
+
+	/*
+	 * Time to use another element in the array -- and increase the length in
+	 * the process
+	 */
+	timeline->data[timeline->length] = carry;
+	timeline->length++;
+}
+
+
+/*
+ * Translate time to a LSN using the provided timeline. The timeline will not
+ * be modified.
+ */
+XLogRecPtr
+estimate_lsn_at_time(const LSNTimeline *timeline, TimestampTz time)
+{
+	TimestampTz time_elapsed;
+	XLogRecPtr	lsns_elapsed;
+	double		result;
+
+	LSNTime		start = {.time = PgStartTime,.lsn = PgStartLSN};
+	LSNTime		end = {.time = GetCurrentTimestamp(),.lsn = GetXLogInsertRecPtr()};
+
+	/*
+	 * If the target time is after the current time, our best estimate of the
+	 * LSN is the current insert LSN.
+	 */
+	if (time >= end.time)
+		return end.lsn;
+
+	for (int i = 0; i < timeline->length; i++)
+	{
+		/* Pass times more recent than our target time */
+		if (timeline->data[i].time > time)
+			continue;
+
+		/* Found the first element before our target time */
+		start = timeline->data[i];
+
+		/*
+		 * If there is only one element in the array, use the current time as
+		 * the end of the range. Otherwise it is the element preceding our
+		 * start.
+		 */
+		if (i > 0)
+			end = timeline->data[i - 1];
+		break;
+	}
+
+	time_elapsed = end.time - start.time;
+	Assert(time_elapsed != 0);
+
+	lsns_elapsed = end.lsn - start.lsn;
+	Assert(lsns_elapsed != 0);
+
+	result = (double) (time - start.time) / time_elapsed * lsns_elapsed + start.lsn;
+	if (result < 0)
+		return InvalidXLogRecPtr;
+	return result;
+}
+
+/*
+ * Translate lsn to a time using the provided timeline. The timeline will not
+ * be modified.
+ */
+TimestampTz
+estimate_time_at_lsn(const LSNTimeline *timeline, XLogRecPtr lsn)
+{
+	TimestampTz time_elapsed;
+	XLogRecPtr	lsns_elapsed;
+	TimestampTz result;
+
+	LSNTime		start = {.time = PgStartTime,.lsn = PgStartLSN};
+	LSNTime		end = {.time = GetCurrentTimestamp(),.lsn = GetXLogInsertRecPtr()};
+
+	/*
+	 * If the target LSN is after the current insert LSN, the current time is
+	 * our best estimate.
+	 */
+	if (lsn >= end.lsn)
+		return end.time;
+
+	for (int i = 0; i < timeline->length; i++)
+	{
+		/* Pass LSNs more recent than our target LSN */
+		if (timeline->data[i].lsn > lsn)
+			continue;
+
+		/* Found the first element before our target LSN */
+		start = timeline->data[i];
+
+		/*
+		 * If there is only one element in the array, use the current LSN and
+		 * time as the end of the range. Otherwise, use the preceding element
+		 * (the first element occuring before our target LSN in the timeline).
+		 */
+		if (i > 0)
+			end = timeline->data[i - 1];
+		break;
+	}
+
+	time_elapsed = end.time - start.time;
+	Assert(time_elapsed != 0);
+
+	lsns_elapsed = end.lsn - start.lsn;
+	Assert(lsns_elapsed != 0);
+
+	result = (lsn - start.lsn) / lsns_elapsed * time_elapsed + start.time;
+	if (result < 0)
+		return 0;
+	return result;
+}
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index 2136239710e..4f25773d681 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -11,6 +11,7 @@
 #ifndef PGSTAT_H
 #define PGSTAT_H
 
+#include "access/xlogdefs.h"
 #include "datatype/timestamp.h"
 #include "portability/instr_time.h"
 #include "postmaster/pgarch.h"	/* for MAX_XFN_CHARS */
@@ -428,6 +429,39 @@ typedef struct PgStat_StatTabEntry
 	PgStat_Counter autoanalyze_count;
 } PgStat_StatTabEntry;
 
+/*
+ * The elements of an LSNTimeline. Each LSNTime represents one or more time,
+ * LSN pairs. The LSN is typically the insert LSN recorded at the time. Members
+ * is the number of logical members -- each a time, LSN pair -- represented in
+ * the LSNTime.
+ */
+typedef struct LSNTime
+{
+	TimestampTz time;
+	XLogRecPtr	lsn;
+	uint64		members;
+} LSNTime;
+
+/*
+ * A timeline consists of LSNTimes from most to least recent. Each element of
+ * the array in the timeline may represent 2^array index logical members --
+ * meaning that each element's capacity is twice that of the preceding element.
+ * This gives more recent times greater precision than less recent ones. An
+ * array of size 64 should provide sufficient capacity without accounting for
+ * what to do when all elements of the array are at capacity.
+ *
+ * When LSNTimes are inserted into the timeline, they are absorbed into the
+ * first array element with spare capacity -- with the new combined element
+ * having the lesser of the two values. The timeline's length is the highest
+ * array index representing one or more logical members. Use the timeline for
+ * LSN <-> time conversion using linear interpolation.
+ */
+typedef struct LSNTimeline
+{
+	int			length;
+	LSNTime		data[64];
+} LSNTimeline;
+
 typedef struct PgStat_WalStats
 {
 	PgStat_Counter wal_records;
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 90b37b919c2..32057181277 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1525,6 +1525,8 @@ LogicalTapeSet
 LsnReadQueue
 LsnReadQueueNextFun
 LsnReadQueueNextStatus
+LSNTime
+LSNTimeline
 LtreeGistOptions
 LtreeSignature
 MAGIC
-- 
2.37.2

From d07f54554b74dd3984c16b3d81b723ed735e80af Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 16:41:47 -0500
Subject: [PATCH v2 3/5] Add LSNTimeline to PgStat_WalStats

Add a globally maintained instance of the new LSNTimeline to
PgStat_WalStats and add utility functions for maintaining and accessing
it. This commit does not insert new values to the timeline or use the
helpers to access it.
---
 src/backend/utils/activity/pgstat_wal.c | 48 +++++++++++++++++++++----
 src/include/pgstat.h                    |  6 ++++
 2 files changed, 48 insertions(+), 6 deletions(-)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index e8d9660f82e..274ed7a24cd 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -36,10 +36,10 @@ static WalUsage prevWalUsage;
 
 
 static void lsntime_absorb(LSNTime *a, const LSNTime *b);
-void lsntime_insert(LSNTimeline *timeline, TimestampTz time, XLogRecPtr lsn);
+static void lsntime_insert(LSNTimeline *timeline, TimestampTz time, XLogRecPtr lsn);
 
-XLogRecPtr estimate_lsn_at_time(const LSNTimeline *timeline, TimestampTz time);
-TimestampTz estimate_time_at_lsn(const LSNTimeline *timeline, XLogRecPtr lsn);
+static XLogRecPtr estimate_lsn_at_time(const LSNTimeline *timeline, TimestampTz time);
+static TimestampTz estimate_time_at_lsn(const LSNTimeline *timeline, XLogRecPtr lsn);
 
 /*
  * Calculate how much WAL usage counters have increased and update
@@ -222,7 +222,7 @@ lsntime_absorb(LSNTime *a, const LSNTime *b)
  * Insert a new LSNTime into the LSNTimeline in the first element with spare
  * capacity.
  */
-void
+static void
 lsntime_insert(LSNTimeline *timeline, TimestampTz time,
 			   XLogRecPtr lsn)
 {
@@ -284,7 +284,7 @@ lsntime_insert(LSNTimeline *timeline, TimestampTz time,
  * Translate time to a LSN using the provided timeline. The timeline will not
  * be modified.
  */
-XLogRecPtr
+static XLogRecPtr
 estimate_lsn_at_time(const LSNTimeline *timeline, TimestampTz time)
 {
 	TimestampTz time_elapsed;
@@ -336,7 +336,7 @@ estimate_lsn_at_time(const LSNTimeline *timeline, TimestampTz time)
  * Translate lsn to a time using the provided timeline. The timeline will not
  * be modified.
  */
-TimestampTz
+static TimestampTz
 estimate_time_at_lsn(const LSNTimeline *timeline, XLogRecPtr lsn)
 {
 	TimestampTz time_elapsed;
@@ -383,3 +383,39 @@ estimate_time_at_lsn(const LSNTimeline *timeline, XLogRecPtr lsn)
 		return 0;
 	return result;
 }
+
+XLogRecPtr
+pgstat_wal_estimate_lsn_at_time(TimestampTz time)
+{
+	XLogRecPtr	result;
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+
+	LWLockAcquire(&stats_shmem->lock, LW_SHARED);
+	result = estimate_lsn_at_time(&stats_shmem->stats.timeline, time);
+	LWLockRelease(&stats_shmem->lock);
+
+	return result;
+}
+
+TimestampTz
+pgstat_wal_estimate_time_at_lsn(XLogRecPtr lsn)
+{
+	TimestampTz result;
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+
+	LWLockAcquire(&stats_shmem->lock, LW_SHARED);
+	result = estimate_time_at_lsn(&stats_shmem->stats.timeline, lsn);
+	LWLockRelease(&stats_shmem->lock);
+
+	return result;
+}
+
+void
+pgstat_wal_update_lsntimeline(TimestampTz time, XLogRecPtr lsn)
+{
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+
+	LWLockAcquire(&stats_shmem->lock, LW_EXCLUSIVE);
+	lsntime_insert(&stats_shmem->stats.timeline, time, lsn);
+	LWLockRelease(&stats_shmem->lock);
+}
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index 4f25773d681..a9bf8301a34 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -472,6 +472,7 @@ typedef struct PgStat_WalStats
 	PgStat_Counter wal_sync;
 	PgStat_Counter wal_write_time;
 	PgStat_Counter wal_sync_time;
+	LSNTimeline timeline;
 	TimestampTz stat_reset_timestamp;
 } PgStat_WalStats;
 
@@ -754,6 +755,11 @@ extern void pgstat_execute_transactional_drops(int ndrops, struct xl_xact_stats_
 extern void pgstat_report_wal(bool force);
 extern PgStat_WalStats *pgstat_fetch_stat_wal(void);
 
+/* Helpers for maintaining the LSNTimeline */
+extern XLogRecPtr pgstat_wal_estimate_lsn_at_time(TimestampTz time);
+extern TimestampTz pgstat_wal_estimate_time_at_lsn(XLogRecPtr lsn);
+extern void pgstat_wal_update_lsntimeline(TimestampTz time, XLogRecPtr lsn);
+
 
 /*
  * Variables in pgstat.c
-- 
2.37.2

From 768829e8e64d7296a86ce55467c5e2adf1e2b3f7 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 15:46:16 -0500
Subject: [PATCH v2 5/5] Add time <-> LSN translation functions to pageinspect

Previous commits added a global LSNTimeline, maintained by background
writer, that allows approximate translations between time and LSNs. This
can be useful for approximating the time of last modification of a page
or estimating the LSN consumption rate to moderate maintenance processes
and balance system resource utilization. This commit adds user-facing
access to the conversion capabilities of the timeline.

ci-os-only:
---
 .../pageinspect/pageinspect--1.10--1.11.sql   | 10 +++++
 contrib/pageinspect/rawpage.c                 | 26 +++++++++++
 doc/src/sgml/pageinspect.sgml                 | 45 +++++++++++++++++++
 3 files changed, 81 insertions(+)

diff --git a/contrib/pageinspect/pageinspect--1.10--1.11.sql b/contrib/pageinspect/pageinspect--1.10--1.11.sql
index 8fa5e105bc4..72b16d5f84d 100644
--- a/contrib/pageinspect/pageinspect--1.10--1.11.sql
+++ b/contrib/pageinspect/pageinspect--1.10--1.11.sql
@@ -26,3 +26,13 @@ ALTER FUNCTION hash_bitmap_info(regclass, int8) PARALLEL RESTRICTED;
 -- Likewise for gist_page_items.
 ALTER FUNCTION brin_page_items(bytea, regclass) PARALLEL RESTRICTED;
 ALTER FUNCTION gist_page_items(bytea, regclass) PARALLEL RESTRICTED;
+
+CREATE FUNCTION estimate_lsn_at_time(IN input_time timestamp with time zone,
+    OUT lsn pg_lsn)
+AS 'MODULE_PATHNAME', 'estimate_lsn_at_time'
+LANGUAGE C STRICT PARALLEL SAFE;
+
+CREATE FUNCTION estimate_time_at_lsn(IN lsn pg_lsn,
+    OUT result timestamp with time zone)
+AS 'MODULE_PATHNAME', 'estimate_time_at_lsn'
+LANGUAGE C STRICT PARALLEL SAFE;
diff --git a/contrib/pageinspect/rawpage.c b/contrib/pageinspect/rawpage.c
index 2800ebd62f5..514d8092838 100644
--- a/contrib/pageinspect/rawpage.c
+++ b/contrib/pageinspect/rawpage.c
@@ -22,6 +22,7 @@
 #include "funcapi.h"
 #include "miscadmin.h"
 #include "pageinspect.h"
+#include "pgstat.h"
 #include "storage/bufmgr.h"
 #include "storage/checksum.h"
 #include "utils/builtins.h"
@@ -335,6 +336,9 @@ page_header(PG_FUNCTION_ARGS)
 PG_FUNCTION_INFO_V1(page_checksum_1_9);
 PG_FUNCTION_INFO_V1(page_checksum);
 
+PG_FUNCTION_INFO_V1(estimate_lsn_at_time);
+PG_FUNCTION_INFO_V1(estimate_time_at_lsn);
+
 static Datum
 page_checksum_internal(PG_FUNCTION_ARGS, enum pageinspect_version ext_version)
 {
@@ -374,3 +378,25 @@ page_checksum(PG_FUNCTION_ARGS)
 {
 	return page_checksum_internal(fcinfo, PAGEINSPECT_V1_8);
 }
+
+Datum
+estimate_time_at_lsn(PG_FUNCTION_ARGS)
+{
+	XLogRecPtr	lsn = PG_GETARG_LSN(0);
+	TimestampTz result;
+
+	result = pgstat_wal_estimate_time_at_lsn(lsn);
+
+	PG_RETURN_TIMESTAMPTZ(result);
+}
+
+Datum
+estimate_lsn_at_time(PG_FUNCTION_ARGS)
+{
+	TimestampTz time = PG_GETARG_TIMESTAMPTZ(0);
+	XLogRecPtr	result;
+
+	result = pgstat_wal_estimate_lsn_at_time(time);
+
+	PG_RETURN_LSN(result);
+}
diff --git a/doc/src/sgml/pageinspect.sgml b/doc/src/sgml/pageinspect.sgml
index 27e0598f74c..cfd60bfd9aa 100644
--- a/doc/src/sgml/pageinspect.sgml
+++ b/doc/src/sgml/pageinspect.sgml
@@ -153,6 +153,51 @@ test=# SELECT fsm_page_contents(get_raw_page('pg_class', 'fsm', 0));
      </para>
     </listitem>
    </varlistentry>
+
+   <varlistentry>
+    <term>
+     <function>estimate_lsn_at_time(lsn timestamptz) returns pg_lsn</function>
+     <indexterm>
+      <primary>estimate_lsn_at_time</primary>
+     </indexterm>
+    </term>
+
+    <listitem>
+     <para>
+      <function>estimate_lsn_at_time</function> estimates the LSN at the provided time.
+     </para>
+
+    </listitem>
+   </varlistentry>
+
+   <varlistentry>
+    <term>
+     <function>estimate_time_at_lsn(lsn pg_lsn) returns timestamp with timezone</function>
+     <indexterm>
+      <primary>estimate_time_at_lsn</primary>
+     </indexterm>
+    </term>
+
+    <listitem>
+     <para>
+      <function>estimate_time_at_lsn</function> estimates the time at provided LSN.
+     </para>
+
+     <para>
+      One useful application is approximating the last modification time of a
+      given page in a relation. For example, when combined with pageinspect
+      functions returning a page LSN:
+<screen>
+test=# SELECT estimate_time_at_lsn((SELECT lsn from page_header(get_raw_page('pg_class', 0))));
+     estimate_time_at_lsn
+-------------------------------
+ 2023-12-22 08:01:02.393598-05
+</screen>
+     </para>
+
+    </listitem>
+   </varlistentry>
+
   </variablelist>
  </sect2>
 
-- 
2.37.2

From fab7205db15a23e15c157e52704690d895e8cd87 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Tue, 5 Dec 2023 07:29:39 -0500
Subject: [PATCH v2 1/5] Record LSN at postmaster startup

The insert_lsn at postmaster startup can be used along with PgStartTime
as seed values for a timeline mapping LSNs to time. Future commits will
add such a structure for LSN <-> time conversions. A start LSN allows
for such conversions before even inserting a value into the timeline.
The current time and current insert LSN can be used along with
PgStartTime and PgStartLSN.

This is WIP, as I'm not sure if I did this in the right place.
---
 src/backend/access/transam/xlog.c   | 2 ++
 src/backend/postmaster/postmaster.c | 1 +
 src/include/utils/builtins.h        | 3 +++
 3 files changed, 6 insertions(+)

diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index 478377c4a23..b0f34f3b7a1 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -146,6 +146,8 @@ bool		XLOG_DEBUG = false;
 
 int			wal_segment_size = DEFAULT_XLOG_SEG_SIZE;
 
+XLogRecPtr	PgStartLSN = InvalidXLogRecPtr;
+
 /*
  * Number of WAL insertion locks to use. A higher value allows more insertions
  * to happen concurrently, but adds some CPU overhead to flushing the WAL,
diff --git a/src/backend/postmaster/postmaster.c b/src/backend/postmaster/postmaster.c
index feb471dd1df..951114342a5 100644
--- a/src/backend/postmaster/postmaster.c
+++ b/src/backend/postmaster/postmaster.c
@@ -1448,6 +1448,7 @@ PostmasterMain(int argc, char *argv[])
 	 * Remember postmaster startup time
 	 */
 	PgStartTime = GetCurrentTimestamp();
+	PgStartLSN = GetXLogInsertRecPtr();
 
 	/*
 	 * Report postmaster status in the postmaster.pid file, to allow pg_ctl to
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 359c570f23e..16a7a058bc7 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -17,6 +17,7 @@
 #include "fmgr.h"
 #include "nodes/nodes.h"
 #include "utils/fmgrprotos.h"
+#include "access/xlogdefs.h"
 
 /* Sign + the most decimal digits an 8-byte number could have */
 #define MAXINT8LEN 20
@@ -85,6 +86,8 @@ extern void generate_operator_clause(fmStringInfo buf,
 									 Oid opoid,
 									 const char *rightop, Oid rightoptype);
 
+extern PGDLLIMPORT XLogRecPtr PgStartLSN;
+
 /* varchar.c */
 extern int	bpchartruelen(char *s, int len);
 
-- 
2.37.2

From 3da2b81d052f39580cd8336853668db6233d2243 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 16:32:40 -0500
Subject: [PATCH v2 4/5] Bgwriter maintains global LSNTimeline

Insert new LSN, time pairs to the global LSNTimeline stored in
PgStat_WalStats in the background writer's main loop. This ensures that
new values are added to the timeline in a regular manner.
---
 src/backend/postmaster/bgwriter.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/src/backend/postmaster/bgwriter.c b/src/backend/postmaster/bgwriter.c
index d7d6cc0cd7b..ec6828aa2a5 100644
--- a/src/backend/postmaster/bgwriter.c
+++ b/src/backend/postmaster/bgwriter.c
@@ -277,6 +277,7 @@ BackgroundWriterMain(void)
 		{
 			TimestampTz timeout = 0;
 			TimestampTz now = GetCurrentTimestamp();
+			XLogRecPtr	current_lsn = GetLastImportantRecPtr();
 
 			timeout = TimestampTzPlusMilliseconds(last_snapshot_ts,
 												  LOG_SNAPSHOT_INTERVAL_MS);
@@ -289,10 +290,11 @@ BackgroundWriterMain(void)
 			 * the end of the record.
 			 */
 			if (now >= timeout &&
-				last_snapshot_lsn <= GetLastImportantRecPtr())
+				last_snapshot_lsn <= current_lsn)
 			{
 				last_snapshot_lsn = LogStandbySnapshot();
 				last_snapshot_ts = now;
+				pgstat_wal_update_lsntimeline(now, current_lsn);
 			}
 		}
 
-- 
2.37.2

From cf9e6f507bc9781bf79e8c39766c8e84209d2ada Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 21 Feb 2024 20:06:29 -0500
Subject: [PATCH v3 5/5] Add time <-> LSN translation functions

Previous commits added a global LSNTimeline, maintained by background
writer, that allows approximate translations between time and LSNs.

Add SQL-callable functions to convert from LSN to time and back and a
SQL-callable function returning the entire LSNTimeline.

This could be useful in combination with SQL-callable functions
accessing a page LSN to approximate the time of last modification of a
page or estimating the LSN consumption rate to moderate maintenance
processes and balance system resource utilization.
---
 src/backend/utils/activity/pgstat_wal.c | 58 +++++++++++++++++++++++++
 src/include/catalog/pg_proc.dat         | 22 ++++++++++
 2 files changed, 80 insertions(+)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index df4c91ee3cf..27f2b23cd88 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -18,6 +18,7 @@
 #include "postgres.h"
 
 #include "access/xlog.h"
+#include "funcapi.h"
 #include "utils/pgstat_internal.h"
 #include "executor/instrument.h"
 #include "utils/builtins.h"
@@ -418,3 +419,60 @@ pgstat_wal_update_lsntimeline(TimestampTz time, XLogRecPtr lsn)
 	lsntime_insert(&stats_shmem->stats.timeline, time, lsn);
 	LWLockRelease(&stats_shmem->lock);
 }
+
+PG_FUNCTION_INFO_V1(pg_estimate_lsn_at_time);
+PG_FUNCTION_INFO_V1(pg_estimate_time_at_lsn);
+PG_FUNCTION_INFO_V1(pg_lsntimeline);
+
+Datum
+pg_estimate_time_at_lsn(PG_FUNCTION_ARGS)
+{
+	XLogRecPtr	lsn = PG_GETARG_LSN(0);
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+	TimestampTz result;
+
+	LWLockAcquire(&stats_shmem->lock, LW_SHARED);
+	result = estimate_time_at_lsn(&stats_shmem->stats.timeline, lsn);
+	LWLockRelease(&stats_shmem->lock);
+
+	PG_RETURN_TIMESTAMPTZ(result);
+}
+
+Datum
+pg_estimate_lsn_at_time(PG_FUNCTION_ARGS)
+{
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+	TimestampTz time = PG_GETARG_TIMESTAMPTZ(0);
+	XLogRecPtr	result;
+
+	LWLockAcquire(&stats_shmem->lock, LW_SHARED);
+	result = estimate_lsn_at_time(&stats_shmem->stats.timeline, time);
+	LWLockRelease(&stats_shmem->lock);
+
+	PG_RETURN_LSN(result);
+}
+
+Datum
+pg_lsntimeline(PG_FUNCTION_ARGS)
+{
+	ReturnSetInfo *rsinfo;
+	LSNTimeline *timeline;
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+
+	InitMaterializedSRF(fcinfo, 0);
+	rsinfo = (ReturnSetInfo *) fcinfo->resultinfo;
+	LWLockAcquire(&stats_shmem->lock, LW_SHARED);
+	timeline = &stats_shmem->stats.timeline;
+	for (int i = LSNTIMELINE_VOLUME - timeline->length; i < LSNTIMELINE_VOLUME; i++)
+	{
+		Datum		values[2] = {0};
+		bool		nulls[2] = {0};
+
+		values[0] = timeline->data[i].time;
+		values[1] = timeline->data[i].lsn;
+		tuplestore_putvalues(rsinfo->setResult, rsinfo->setDesc,
+							 values, nulls);
+	}
+	LWLockRelease(&stats_shmem->lock);
+	return (Datum) 0;
+}
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 9c120fc2b7f..e69cf9c2437 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -6326,6 +6326,28 @@
   prorettype => 'timestamptz', proargtypes => 'xid',
   prosrc => 'pg_xact_commit_timestamp' },
 
+{ oid => '9997',
+  descr => 'get approximate LSN at a particular point in time',
+  proname => 'pg_estimate_lsn_at_time', provolatile => 'v',
+  prorettype => 'pg_lsn', proargtypes => 'timestamptz',
+  prosrc => 'pg_estimate_lsn_at_time' },
+
+{ oid => '9996',
+  descr => 'get approximate time at a particular LSN',
+  proname => 'pg_estimate_time_at_lsn', provolatile => 'v',
+  prorettype => 'timestamptz', proargtypes => 'pg_lsn',
+  prosrc => 'pg_estimate_time_at_lsn' },
+
+{ oid => '9994',
+  descr => 'print the LSN timeline',
+  proname => 'pg_lsntimeline', prorows => '64',
+  proretset => 't', provolatile => 'v', proparallel => 's',
+  prorettype => 'record', proargtypes => '',
+  proallargtypes => '{timestamptz,pg_lsn}',
+  proargmodes => '{o,o}',
+  proargnames => '{time, lsn}',
+  prosrc => 'pg_lsntimeline' },
+
 { oid => '6168',
   descr => 'get commit timestamp and replication origin of a transaction',
   proname => 'pg_xact_commit_timestamp_origin', provolatile => 'v',
-- 
2.37.2

From 6fd317a319de144a7a999fc6230268521e72a36f Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 21 Feb 2024 20:28:27 -0500
Subject: [PATCH v3 3/5] Add LSNTimeline to PgStat_WalStats

Add a globally maintained instance of the new LSNTimeline to
PgStat_WalStats and a utility function to insert new values.
---
 src/backend/utils/activity/pgstat_wal.c | 10 ++++++++++
 src/include/pgstat.h                    |  4 ++++
 2 files changed, 14 insertions(+)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index 96e84319f6f..df4c91ee3cf 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -408,3 +408,13 @@ stop:
 	result = (double) (lsn - start.lsn) / lsns_elapsed * time_elapsed + start.time;
 	return Max(result, 0);
 }
+
+void
+pgstat_wal_update_lsntimeline(TimestampTz time, XLogRecPtr lsn)
+{
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+
+	LWLockAcquire(&stats_shmem->lock, LW_EXCLUSIVE);
+	lsntime_insert(&stats_shmem->stats.timeline, time, lsn);
+	LWLockRelease(&stats_shmem->lock);
+}
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index 1926ddb00ed..8a63f56fdd3 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -482,6 +482,7 @@ typedef struct PgStat_WalStats
 	PgStat_Counter wal_sync;
 	PgStat_Counter wal_write_time;
 	PgStat_Counter wal_sync_time;
+	LSNTimeline timeline;
 	TimestampTz stat_reset_timestamp;
 } PgStat_WalStats;
 
@@ -764,6 +765,9 @@ extern void pgstat_execute_transactional_drops(int ndrops, struct xl_xact_stats_
 extern void pgstat_report_wal(bool force);
 extern PgStat_WalStats *pgstat_fetch_stat_wal(void);
 
+/* Helpers for maintaining the LSNTimeline */
+extern void pgstat_wal_update_lsntimeline(TimestampTz time, XLogRecPtr lsn);
+
 
 /*
  * Variables in pgstat.c
-- 
2.37.2

From 1348109617ce772835336ea8e8a9781407f6060d Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Tue, 5 Dec 2023 07:29:39 -0500
Subject: [PATCH v3 1/5] Record LSN at postmaster startup

The insert_lsn at postmaster startup can be used along with PgStartTime
as seed values for a timeline mapping LSNs to time. Future commits will
add such a structure for LSN <-> time conversions. A start LSN allows
for such conversions before even inserting a value into the timeline.
The current time and current insert LSN can be used along with
PgStartTime and PgStartLSN.

This is WIP, as I'm not sure if I did this in the right place.
---
 src/backend/access/transam/xlog.c   | 2 ++
 src/backend/postmaster/postmaster.c | 1 +
 src/include/utils/builtins.h        | 3 +++
 3 files changed, 6 insertions(+)

diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index c1162d55bff..3fea9f4c31f 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -146,6 +146,8 @@ bool		XLOG_DEBUG = false;
 
 int			wal_segment_size = DEFAULT_XLOG_SEG_SIZE;
 
+XLogRecPtr	PgStartLSN = InvalidXLogRecPtr;
+
 /*
  * Number of WAL insertion locks to use. A higher value allows more insertions
  * to happen concurrently, but adds some CPU overhead to flushing the WAL,
diff --git a/src/backend/postmaster/postmaster.c b/src/backend/postmaster/postmaster.c
index df945a5ac4d..9e5cad60549 100644
--- a/src/backend/postmaster/postmaster.c
+++ b/src/backend/postmaster/postmaster.c
@@ -1440,6 +1440,7 @@ PostmasterMain(int argc, char *argv[])
 	 * Remember postmaster startup time
 	 */
 	PgStartTime = GetCurrentTimestamp();
+	PgStartLSN = GetXLogInsertRecPtr();
 
 	/*
 	 * Report postmaster status in the postmaster.pid file, to allow pg_ctl to
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 359c570f23e..16a7a058bc7 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -17,6 +17,7 @@
 #include "fmgr.h"
 #include "nodes/nodes.h"
 #include "utils/fmgrprotos.h"
+#include "access/xlogdefs.h"
 
 /* Sign + the most decimal digits an 8-byte number could have */
 #define MAXINT8LEN 20
@@ -85,6 +86,8 @@ extern void generate_operator_clause(fmStringInfo buf,
 									 Oid opoid,
 									 const char *rightop, Oid rightoptype);
 
+extern PGDLLIMPORT XLogRecPtr PgStartLSN;
+
 /* varchar.c */
 extern int	bpchartruelen(char *s, int len);
 
-- 
2.37.2

From 6204555c6d59035cba9f850c676d0b1f530c6f43 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 16:32:40 -0500
Subject: [PATCH v3 4/5] Bgwriter maintains global LSNTimeline

Insert new LSN, time pairs to the global LSNTimeline stored in
PgStat_WalStats in the background writer's main loop. This ensures that
new values are added to the timeline in a regular manner.
---
 src/backend/postmaster/bgwriter.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/src/backend/postmaster/bgwriter.c b/src/backend/postmaster/bgwriter.c
index 6364b16261f..4b4d5db60bb 100644
--- a/src/backend/postmaster/bgwriter.c
+++ b/src/backend/postmaster/bgwriter.c
@@ -272,6 +272,7 @@ BackgroundWriterMain(void)
 		{
 			TimestampTz timeout = 0;
 			TimestampTz now = GetCurrentTimestamp();
+			XLogRecPtr	current_lsn = GetLastImportantRecPtr();
 
 			timeout = TimestampTzPlusMilliseconds(last_snapshot_ts,
 												  LOG_SNAPSHOT_INTERVAL_MS);
@@ -284,10 +285,11 @@ BackgroundWriterMain(void)
 			 * the end of the record.
 			 */
 			if (now >= timeout &&
-				last_snapshot_lsn <= GetLastImportantRecPtr())
+				last_snapshot_lsn <= current_lsn)
 			{
 				last_snapshot_lsn = LogStandbySnapshot();
 				last_snapshot_ts = now;
+				pgstat_wal_update_lsntimeline(now, current_lsn);
 			}
 		}
 
-- 
2.37.2

From 800b0610f430f965e9216a374afe638bbec7bb6f Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 16:40:27 -0500
Subject: [PATCH v3 2/5] Add LSNTimeline for converting LSN <-> time

Add a new structure, LSNTimeline, consisting of LSNTimes -- each an LSN,
time pair. Each LSNTime can represent multiple logical LSN, time pairs,
referred to as members. LSN <-> time conversions can be done using
linear interpolation with two LSNTimes on the LSNTimeline.

This commit does not add a global instance of LSNTimeline. It adds the
structures and functions needed to maintain and access such a timeline.
---
 src/backend/utils/activity/pgstat_wal.c | 224 ++++++++++++++++++++++++
 src/include/pgstat.h                    |  44 +++++
 src/tools/pgindent/typedefs.list        |   2 +
 3 files changed, 270 insertions(+)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index 1a3c0e1a669..96e84319f6f 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -17,8 +17,12 @@
 
 #include "postgres.h"
 
+#include "access/xlog.h"
 #include "utils/pgstat_internal.h"
 #include "executor/instrument.h"
+#include "utils/builtins.h"
+#include "utils/timestamp.h"
+#include "utils/pg_lsn.h"
 
 
 PgStat_PendingWalStats PendingWalStats = {0};
@@ -32,6 +36,12 @@ PgStat_PendingWalStats PendingWalStats = {0};
 static WalUsage prevWalUsage;
 
 
+static void lsntime_merge(LSNTime *target, LSNTime *src);
+static void lsntime_insert(LSNTimeline *timeline, TimestampTz time, XLogRecPtr lsn);
+
+XLogRecPtr	estimate_lsn_at_time(const LSNTimeline *timeline, TimestampTz time);
+TimestampTz estimate_time_at_lsn(const LSNTimeline *timeline, XLogRecPtr lsn);
+
 /*
  * Calculate how much WAL usage counters have increased and update
  * shared WAL and IO statistics.
@@ -184,3 +194,217 @@ pgstat_wal_snapshot_cb(void)
 		   sizeof(pgStatLocal.snapshot.wal));
 	LWLockRelease(&stats_shmem->lock);
 }
+
+/*
+ * Set *target to be the earlier of *target or *src.
+ */
+static void
+lsntime_merge(LSNTime *target, LSNTime *src)
+{
+	LSNTime		result;
+	uint64		new_members = target->members + src->members;
+
+	if (target->time < src->time)
+		result = *target;
+	else if (src->time < target->time)
+		result = *src;
+	else if (target->lsn < src->lsn)
+		result = *target;
+	else if (src->lsn < target->lsn)
+		result = *src;
+	else
+		result = *target;
+
+	*target = result;
+	target->members = new_members;
+	src->members = 1;
+}
+
+static int
+lsntime_merge_target(LSNTimeline *timeline)
+{
+	/* Don't merge if free space available */
+	Assert(timeline->length == LSNTIMELINE_VOLUME);
+
+	for (int i = timeline->length; i-- > 0;)
+	{
+		/*
+		 * An array element can represent up to twice the number of members
+		 * represented by the preceding array element.
+		 */
+		if (timeline->data[i].members < (2 * timeline->data[i - 1].members))
+			return i;
+	}
+
+	/* Should not be reachable or we are out of space */
+	Assert(false);
+}
+
+/*
+ * Insert a new LSNTime into the LSNTimeline in the first available element,
+ * or, if there are no empty elements, insert it into the element at index 0,
+ * merge the logical members of two old buckets and move the intervening
+ * elements down by one.
+ */
+void
+lsntime_insert(LSNTimeline *timeline, TimestampTz time,
+			   XLogRecPtr lsn)
+{
+	int			merge_target;
+	LSNTime		entrant = {.lsn = lsn,.time = time,.members = 1};
+
+	if (timeline->length < LSNTIMELINE_VOLUME)
+	{
+		/*
+		 * The new entry should exceed the most recent entry to ensure time
+		 * moves forward on the timeline.
+		 */
+		Assert(timeline->length == 0 ||
+			   (lsn >= timeline->data[LSNTIMELINE_VOLUME - timeline->length].lsn &&
+				time >= timeline->data[LSNTIMELINE_VOLUME - timeline->length].time));
+
+		/*
+		 * If there are unfilled elements in the timeline, then insert the
+		 * passed-in LSNTime into the tail of the array.
+		 */
+		timeline->length++;
+		timeline->data[LSNTIMELINE_VOLUME - timeline->length] = entrant;
+		return;
+	}
+
+	/*
+	 * If all elements in the timeline represent at least one member, merge
+	 * the oldest element whose membership is < 2x its predecessor with its
+	 * preceding member. Then shift all elements preceding these two elements
+	 * down by one and insert the passed-in LSNTime at array index 0.
+	 */
+	merge_target = lsntime_merge_target(timeline);
+	Assert(merge_target >= 0 && merge_target < timeline->length);
+	lsntime_merge(&timeline->data[merge_target], &timeline->data[merge_target - 1]);
+	memmove(&timeline->data[1], &timeline->data[0], sizeof(LSNTime) * merge_target - 1);
+	timeline->data[0] = entrant;
+}
+
+/*
+ * Translate time to a LSN using the provided timeline. The timeline will not
+ * be modified.
+ */
+XLogRecPtr
+estimate_lsn_at_time(const LSNTimeline *timeline, TimestampTz time)
+{
+	XLogRecPtr	result;
+	int64		time_elapsed,
+				lsns_elapsed;
+	LSNTime		start = {.time = PgStartTime,.lsn = PgStartLSN};
+	LSNTime		end = {.time = GetCurrentTimestamp(),.lsn = GetXLogInsertRecPtr()};
+
+	/*
+	 * If the provided time is before DB startup, the best we can do is return
+	 * the start LSN.
+	 */
+	if (time < start.time)
+		return start.lsn;
+
+	/*
+	 * If the provided time is after now, the current LSN is our best
+	 * estimate.
+	 */
+	if (time >= end.time)
+		return end.lsn;
+
+	/*
+	 * Loop through the timeline. Stop at the first LSNTime earlier than our
+	 * target time. This LSNTime will be our interpolation start point. If
+	 * there's an LSNTime later than that, then that will be our interpolation
+	 * end point.
+	 */
+	for (int i = LSNTIMELINE_VOLUME - timeline->length; i < LSNTIMELINE_VOLUME; i++)
+	{
+		if (timeline->data[i].time > time)
+			continue;
+
+		start = timeline->data[i];
+		if (i > 0)
+			end = timeline->data[i - 1];
+		goto stop;
+	}
+
+	/*
+	 * If we exhausted the timeline, then use its earliest LSNTime as our
+	 * interpolation end point.
+	 */
+	if (timeline->length > 0)
+		end = timeline->data[timeline->length - 1];
+
+stop:
+	Assert(end.time > start.time);
+	Assert(end.lsn > start.lsn);
+	time_elapsed = end.time - start.time;
+	Assert(time_elapsed != 0);
+	lsns_elapsed = end.lsn - start.lsn;
+	Assert(lsns_elapsed != 0);
+	result = (double) (time - start.time) / time_elapsed * lsns_elapsed + start.lsn;
+	return Max(result, 0);
+}
+
+/*
+ * Translate lsn to a time using the provided timeline. The timeline will not
+ * be modified.
+ */
+TimestampTz
+estimate_time_at_lsn(const LSNTimeline *timeline, XLogRecPtr lsn)
+{
+	int64		time_elapsed,
+				lsns_elapsed;
+	TimestampTz result;
+	LSNTime		start = {.time = PgStartTime,.lsn = PgStartLSN};
+	LSNTime		end = {.time = GetCurrentTimestamp(),.lsn = GetXLogInsertRecPtr()};
+
+	/*
+	 * If the LSN is before DB startup, the best we can do is return that
+	 * time.
+	 */
+	if (lsn <= start.lsn)
+		return start.time;
+
+	/*
+	 * If the target LSN is after the current insert LSN, the current time is
+	 * our best estimate.
+	 */
+	if (lsn >= end.lsn)
+		return end.time;
+
+	/*
+	 * Loop through the timeline. Stop at the first LSNTime earlier than our
+	 * target LSN. This LSNTime will be our interpolation start point. If
+	 * there's an LSNTime later than that, then that will be our interpolation
+	 * end point.
+	 */
+	for (int i = LSNTIMELINE_VOLUME - timeline->length; i < LSNTIMELINE_VOLUME; i++)
+	{
+		if (timeline->data[i].lsn > lsn)
+			continue;
+
+		start = timeline->data[i];
+		if (i > 0)
+			end = timeline->data[i - 1];
+		goto stop;
+	}
+
+	/*
+	 * If we exhausted the timeline, then use its earliest LSNTime as our
+	 * interpolation end point.
+	 */
+	if (timeline->length > 0)
+		end = timeline->data[timeline->length - 1];
+
+stop:
+	Assert(end.time > start.time);
+	Assert(end.lsn > start.lsn);
+	time_elapsed = end.time - start.time;
+	Assert(time_elapsed != 0);
+	lsns_elapsed = end.lsn - start.lsn;
+	Assert(lsns_elapsed != 0);
+	result = (double) (lsn - start.lsn) / lsns_elapsed * time_elapsed + start.time;
+	return Max(result, 0);
+}
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index 2136239710e..1926ddb00ed 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -11,6 +11,7 @@
 #ifndef PGSTAT_H
 #define PGSTAT_H
 
+#include "access/xlogdefs.h"
 #include "datatype/timestamp.h"
 #include "portability/instr_time.h"
 #include "postmaster/pgarch.h"	/* for MAX_XFN_CHARS */
@@ -428,6 +429,49 @@ typedef struct PgStat_StatTabEntry
 	PgStat_Counter autoanalyze_count;
 } PgStat_StatTabEntry;
 
+/*
+ * The elements of an LSNTimeline. Each LSNTime represents one or more time,
+ * LSN pairs. The LSN is typically the insert LSN recorded at the time. Members
+ * is the number of logical members -- each a time, LSN pair -- represented in
+ * the LSNTime.
+ */
+typedef struct LSNTime
+{
+	TimestampTz time;
+	XLogRecPtr	lsn;
+	uint64		members;
+} LSNTime;
+
+#define LSNTIMELINE_VOLUME 64
+/*
+ * A timeline consists of LSNTimes from most to least recent. The array is
+ * filled from end to start before the contents of any elements are merged.
+ * Once the LSNTimeline length == volume (the array is full), old elements are
+ * merged to make space for new elements at index 0. When merging logical
+ * members, each element of the array in the timeline may represent twice as
+ * many logical members as the preceding element.
+ *
+ * This gives more recent times greater precision than less recent ones. An
+ * array of size 64 and an unsigned 64-bit number for the number of members
+ * should provide sufficient capacity without accounting for what to do when
+ * all elements of the array are at capacity.
+ *
+ * After every element has at least one logical member, when a new LSNTime is
+ * inserted, the oldest array element whose logical membership is < 2x its
+ * predecessor is the merge target. Its preceding element is merged into it.
+ * Then all of the intervening elements are moved down by one and the new
+ * LSNTime is inserted at index 0.
+ *
+ * Merging two elements is combining their members and assigning the lesser
+ * LSNTime. Use the timeline for LSN <-> time conversion using linear
+ * interpolation.
+ */
+typedef struct LSNTimeline
+{
+	int			length;
+	LSNTime		data[LSNTIMELINE_VOLUME];
+} LSNTimeline;
+
 typedef struct PgStat_WalStats
 {
 	PgStat_Counter wal_records;
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index d808aad8b05..aef83230836 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1525,6 +1525,8 @@ LogicalTapeSet
 LsnReadQueue
 LsnReadQueueNextFun
 LsnReadQueueNextStatus
+LSNTime
+LSNTimeline
 LtreeGistOptions
 LtreeSignature
 MAGIC
-- 
2.37.2

commit 908f3bb511450f05980ba01d42c909cc9ef8007a
Author: Daniel Gustafsson <dgustafsson@postgresql.org>
Date:   Thu Mar 14 14:32:15 2024 +0100

    Code review hackery

diff --git a/src/backend/postmaster/bgwriter.c b/src/backend/postmaster/bgwriter.c
index 7d9ad9046f..115204f708 100644
--- a/src/backend/postmaster/bgwriter.c
+++ b/src/backend/postmaster/bgwriter.c
@@ -267,7 +267,7 @@ BackgroundWriterMain(void)
 		{
 			TimestampTz timeout = 0;
 			TimestampTz now = GetCurrentTimestamp();
-			XLogRecPtr	current_lsn = GetLastImportantRecPtr();
+			XLogRecPtr	current_lsn;
 
 			timeout = TimestampTzPlusMilliseconds(last_snapshot_ts,
 												  LOG_SNAPSHOT_INTERVAL_MS);
@@ -279,12 +279,15 @@ BackgroundWriterMain(void)
 			 * start of a record, whereas last_snapshot_lsn points just past
 			 * the end of the record.
 			 */
-			if (now >= timeout &&
-				last_snapshot_lsn <= current_lsn)
+			if (now >= timeout)
 			{
-				last_snapshot_lsn = LogStandbySnapshot();
-				last_snapshot_ts = now;
-				pgstat_wal_update_lsntimeline(now, current_lsn);
+				current_lsn = GetLastImportantRecPtr();
+				if (last_snapshot_lsn <= current_lsn)
+				{
+					last_snapshot_lsn = LogStandbySnapshot();
+					last_snapshot_ts = now;
+					pgstat_wal_update_lsntimeline(now, current_lsn);
+				}
 			}
 		}
 
diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index 0a7b545fd2..90afec580b 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -238,7 +238,7 @@ lsntime_merge_target(LSNTimeline *timeline)
 	}
 
 	/* Should not be reachable or we are out of space */
-	Assert(false);
+	return -1;
 }
 
 /*
@@ -280,7 +280,12 @@ lsntime_insert(LSNTimeline *timeline, TimestampTz time,
 	 * down by one and insert the passed-in LSNTime at array index 0.
 	 */
 	merge_target = lsntime_merge_target(timeline);
-	Assert(merge_target >= 0 && merge_target < timeline->length);
+	if (merge_target < 0)
+	{
+		elog(WARNING, "unable to insert LSN in LSN timeline, merge failed");
+		return;
+	}
+	Assert(merge_target < timeline->length);
 	lsntime_merge(&timeline->data[merge_target], &timeline->data[merge_target - 1]);
 	memmove(&timeline->data[1], &timeline->data[0], sizeof(LSNTime) * merge_target - 1);
 	timeline->data[0] = entrant;

From 1b86460bb25aef99a39034e5bf6be581cdccfb88 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Tue, 5 Dec 2023 07:29:39 -0500
Subject: [PATCH v4 1/6] Record LSN at postmaster startup

The insert_lsn at postmaster startup can be used along with PgStartTime
as seed values for a timeline mapping LSNs to time. Future commits will
add such a structure for LSN <-> time conversions. A start LSN allows
for such conversions before even inserting a value into the timeline.
The current time and current insert LSN can be used along with
PgStartTime and PgStartLSN.

This is WIP, as I'm not sure if I did this in the right place.
---
 src/backend/access/transam/xlog.c   | 2 ++
 src/backend/postmaster/postmaster.c | 2 ++
 src/include/utils/builtins.h        | 3 +++
 3 files changed, 7 insertions(+)

diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index 330e058c5f2..6fff1f52084 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -142,6 +142,8 @@ bool		XLOG_DEBUG = false;
 
 int			wal_segment_size = DEFAULT_XLOG_SEG_SIZE;
 
+XLogRecPtr	PgStartLSN = InvalidXLogRecPtr;
+
 /*
  * Number of WAL insertion locks to use. A higher value allows more insertions
  * to happen concurrently, but adds some CPU overhead to flushing the WAL,
diff --git a/src/backend/postmaster/postmaster.c b/src/backend/postmaster/postmaster.c
index bf0241aed0c..f1b60fe6cee 100644
--- a/src/backend/postmaster/postmaster.c
+++ b/src/backend/postmaster/postmaster.c
@@ -117,6 +117,7 @@
 #include "storage/proc.h"
 #include "tcop/backend_startup.h"
 #include "tcop/tcopprot.h"
+#include "utils/builtins.h"
 #include "utils/datetime.h"
 #include "utils/memutils.h"
 #include "utils/pidfile.h"
@@ -1345,6 +1346,7 @@ PostmasterMain(int argc, char *argv[])
 	 * Remember postmaster startup time
 	 */
 	PgStartTime = GetCurrentTimestamp();
+	PgStartLSN = GetXLogInsertRecPtr();
 
 	/*
 	 * Report postmaster status in the postmaster.pid file, to allow pg_ctl to
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 359c570f23e..16a7a058bc7 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -17,6 +17,7 @@
 #include "fmgr.h"
 #include "nodes/nodes.h"
 #include "utils/fmgrprotos.h"
+#include "access/xlogdefs.h"
 
 /* Sign + the most decimal digits an 8-byte number could have */
 #define MAXINT8LEN 20
@@ -85,6 +86,8 @@ extern void generate_operator_clause(fmStringInfo buf,
 									 Oid opoid,
 									 const char *rightop, Oid rightoptype);
 
+extern PGDLLIMPORT XLogRecPtr PgStartLSN;
+
 /* varchar.c */
 extern int	bpchartruelen(char *s, int len);
 
-- 
2.34.1

From 661d8f2db88a510efbbd7c19f0af13ee75416967 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 16:32:40 -0500
Subject: [PATCH v4 4/6] Bgwriter maintains global LSNTimeStream

Insert new LSN, time pairs to the global LSNTimeStream stored in
PgStat_WalStats in the background writer's main loop. This ensures that
new values are added to the stream in a regular manner.
---
 src/backend/postmaster/bgwriter.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)

diff --git a/src/backend/postmaster/bgwriter.c b/src/backend/postmaster/bgwriter.c
index 0f75548759a..02b039cfacf 100644
--- a/src/backend/postmaster/bgwriter.c
+++ b/src/backend/postmaster/bgwriter.c
@@ -273,6 +273,7 @@ BackgroundWriterMain(char *startup_data, size_t startup_data_len)
 		{
 			TimestampTz timeout = 0;
 			TimestampTz now = GetCurrentTimestamp();
+			XLogRecPtr	current_lsn;
 
 			timeout = TimestampTzPlusMilliseconds(last_snapshot_ts,
 												  LOG_SNAPSHOT_INTERVAL_MS);
@@ -284,11 +285,15 @@ BackgroundWriterMain(char *startup_data, size_t startup_data_len)
 			 * start of a record, whereas last_snapshot_lsn points just past
 			 * the end of the record.
 			 */
-			if (now >= timeout &&
-				last_snapshot_lsn <= GetLastImportantRecPtr())
+			if (now >= timeout)
 			{
-				last_snapshot_lsn = LogStandbySnapshot();
-				last_snapshot_ts = now;
+				current_lsn = GetLastImportantRecPtr();
+				if (last_snapshot_lsn <= current_lsn)
+				{
+					last_snapshot_lsn = LogStandbySnapshot();
+					last_snapshot_ts = now;
+					pgstat_wal_update_lsntime_stream(now, current_lsn);
+				}
 			}
 		}
 
-- 
2.34.1

From 23db440712a45f7c58eb57933df61a9b2e40c6a0 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 21 Feb 2024 20:06:29 -0500
Subject: [PATCH v4 5/6] Add time <-> LSN translation functions

Previous commits added a global LSNTimeStream, maintained by background
writer, that allows approximate translations between time and LSNs.

Add SQL-callable functions to convert from LSN to time and back and a
SQL-callable function returning the entire LSNTimeStream.

This could be useful in combination with SQL-callable functions
accessing a page LSN to approximate the time of last modification of a
page or estimating the LSN consumption rate to moderate maintenance
processes and balance system resource utilization.
---
 doc/src/sgml/monitoring.sgml            | 66 +++++++++++++++++++++++++
 src/backend/utils/activity/pgstat_wal.c | 56 +++++++++++++++++++++
 src/include/catalog/pg_proc.dat         | 22 +++++++++
 3 files changed, 144 insertions(+)

diff --git a/doc/src/sgml/monitoring.sgml b/doc/src/sgml/monitoring.sgml
index b2ad9b446f3..1f7cd2f2f3b 100644
--- a/doc/src/sgml/monitoring.sgml
+++ b/doc/src/sgml/monitoring.sgml
@@ -3187,6 +3187,72 @@ description | Waiting for a newly initialized WAL file to reach durable storage
    </tgroup>
   </table>
 
+  <para>
+  In addition to these WAL stats, a stream of LSN <-> time pairs is accessible
+  via the functions shown in <xref linkend="functions-lsn-time-stream"/>.
+  </para>
+
+  <table id="functions-lsn-time-stream">
+   <title>LSN Time Stream Information Functions</title>
+   <tgroup cols="1">
+    <thead>
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       Function
+      </para>
+      <para>
+       Description
+      </para></entry>
+     </row>
+    </thead>
+
+    <tbody>
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_estimate_lsn_at_time</primary>
+       </indexterm>
+       <function>pg_estimate_lsn_at_time</function> ( <type>timestamp with time zone</type> )
+       <returnvalue>pg_lsn</returnvalue>
+      </para>
+      <para>
+       Returns the estimated lsn at the provided time.
+      </para></entry>
+     </row>
+
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_estimate_lsn_at_time</primary>
+       </indexterm>
+       <function>pg_estimate_lsn_at_time</function> ( <type>pg_lsn</type> )
+       <returnvalue>timestamp with time zone</returnvalue>
+      </para>
+      <para>
+        Returns the estimated time at the provided lsn.
+      </para></entry>
+     </row>
+
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_lsntime_stream</primary>
+       </indexterm>
+       <function>pg_lsntime_stream</function> ()
+       <returnvalue>record</returnvalue>
+       ( <parameter>time</parameter> <type>timestamp with time zone</type>,
+       <parameter>lsn</parameter> <type>pg_lsnwith time zone</type>)
+      </para>
+      <para>
+       Returns all of the LSN <-> time pairs in the current LSN time stream.
+      </para></entry>
+     </row>
+    </tbody>
+   </tgroup>
+  </table>
+
+
+
 </sect2>
 
  <sect2 id="monitoring-pg-stat-database-view">
diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index eddd2ec03cb..5d5ab62d4ba 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -19,7 +19,9 @@
 
 #include "access/xlog.h"
 #include "executor/instrument.h"
+#include "funcapi.h"
 #include "utils/builtins.h"
+#include "utils/pg_lsn.h"
 #include "utils/pgstat_internal.h"
 #include "utils/timestamp.h"
 
@@ -427,3 +429,57 @@ pgstat_wal_update_lsntime_stream(TimestampTz time, XLogRecPtr lsn)
 	lsntime_insert(&stats_shmem->stats.stream, time, lsn);
 	LWLockRelease(&stats_shmem->lock);
 }
+
+PG_FUNCTION_INFO_V1(pg_estimate_lsn_at_time);
+PG_FUNCTION_INFO_V1(pg_estimate_time_at_lsn);
+PG_FUNCTION_INFO_V1(pg_lsntime_stream);
+
+Datum
+pg_estimate_time_at_lsn(PG_FUNCTION_ARGS)
+{
+	XLogRecPtr	lsn = PG_GETARG_LSN(0);
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+	TimestampTz result;
+
+	LWLockAcquire(&stats_shmem->lock, LW_SHARED);
+	result = estimate_time_at_lsn(&stats_shmem->stats.stream, lsn);
+	LWLockRelease(&stats_shmem->lock);
+
+	PG_RETURN_TIMESTAMPTZ(result);
+}
+
+Datum
+pg_estimate_lsn_at_time(PG_FUNCTION_ARGS)
+{
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+	TimestampTz time = PG_GETARG_TIMESTAMPTZ(0);
+	XLogRecPtr	result;
+
+	LWLockAcquire(&stats_shmem->lock, LW_SHARED);
+	result = estimate_lsn_at_time(&stats_shmem->stats.stream, time);
+	LWLockRelease(&stats_shmem->lock);
+
+	PG_RETURN_LSN(result);
+}
+
+Datum
+pg_lsntime_stream(PG_FUNCTION_ARGS)
+{
+	ReturnSetInfo *rsinfo;
+	PgStat_WalStats *stats = pgstat_fetch_stat_wal();
+	LSNTimeStream *stream = &stats->stream;
+
+	InitMaterializedSRF(fcinfo, 0);
+	rsinfo = (ReturnSetInfo *) fcinfo->resultinfo;
+	for (int i = LSNTIMESTREAM_VOLUME - stream->length; i < LSNTIMESTREAM_VOLUME; i++)
+	{
+		Datum		values[2] = {0};
+		bool		nulls[2] = {0};
+
+		values[0] = stream->data[i].time;
+		values[1] = stream->data[i].lsn;
+		tuplestore_putvalues(rsinfo->setResult, rsinfo->setDesc,
+							 values, nulls);
+	}
+	return (Datum) 0;
+}
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 6a5476d3c4c..8ab14b49b2a 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -6342,6 +6342,28 @@
   prorettype => 'timestamptz', proargtypes => 'xid',
   prosrc => 'pg_xact_commit_timestamp' },
 
+{ oid => '9997',
+  descr => 'get approximate LSN at a particular point in time',
+  proname => 'pg_estimate_lsn_at_time', provolatile => 'v',
+  prorettype => 'pg_lsn', proargtypes => 'timestamptz',
+  prosrc => 'pg_estimate_lsn_at_time' },
+
+{ oid => '9996',
+  descr => 'get approximate time at a particular LSN',
+  proname => 'pg_estimate_time_at_lsn', provolatile => 'v',
+  prorettype => 'timestamptz', proargtypes => 'pg_lsn',
+  prosrc => 'pg_estimate_time_at_lsn' },
+
+{ oid => '9994',
+  descr => 'print the LSN Time Stream',
+  proname => 'pg_lsntime_stream', prorows => '64',
+  proretset => 't', provolatile => 'v', proparallel => 's',
+  prorettype => 'record', proargtypes => '',
+  proallargtypes => '{timestamptz,pg_lsn}',
+  proargmodes => '{o,o}',
+  proargnames => '{time, lsn}',
+  prosrc => 'pg_lsntime_stream' },
+
 { oid => '6168',
   descr => 'get commit timestamp and replication origin of a transaction',
   proname => 'pg_xact_commit_timestamp_origin', provolatile => 'v',
-- 
2.34.1

From 9b8091be4a9e327e39bc4b9a5f4e5a438897c0e1 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 21 Feb 2024 20:28:27 -0500
Subject: [PATCH v4 3/6] Add LSNTimeStream to PgStat_WalStats

Add a globally maintained instance of an LSNTimeStream to
PgStat_WalStats and a utility function to insert new values.
---
 src/backend/utils/activity/pgstat_wal.c | 10 ++++++++++
 src/include/pgstat.h                    |  4 ++++
 2 files changed, 14 insertions(+)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index d76ace5cbfc..eddd2ec03cb 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -417,3 +417,13 @@ stop:
 	result = (double) (lsn - start.lsn) / lsns_elapsed * time_elapsed + start.time;
 	return Max(result, 0);
 }
+
+void
+pgstat_wal_update_lsntime_stream(TimestampTz time, XLogRecPtr lsn)
+{
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+
+	LWLockAcquire(&stats_shmem->lock, LW_EXCLUSIVE);
+	lsntime_insert(&stats_shmem->stats.stream, time, lsn);
+	LWLockRelease(&stats_shmem->lock);
+}
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index af348be839c..773e3cd5003 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -470,6 +470,7 @@ typedef struct PgStat_WalStats
 	PgStat_Counter wal_sync;
 	PgStat_Counter wal_write_time;
 	PgStat_Counter wal_sync_time;
+	LSNTimeStream stream;
 	TimestampTz stat_reset_timestamp;
 } PgStat_WalStats;
 
@@ -752,6 +753,9 @@ extern void pgstat_execute_transactional_drops(int ndrops, struct xl_xact_stats_
 extern void pgstat_report_wal(bool force);
 extern PgStat_WalStats *pgstat_fetch_stat_wal(void);
 
+/* Helpers for maintaining the LSNTimeStream */
+extern void pgstat_wal_update_lsntime_stream(TimestampTz time, XLogRecPtr lsn);
+
 
 /*
  * Variables in pgstat.c
-- 
2.34.1

From 0b2ab6bb6507cec869f6f55a78016d8c446a7b2f Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 16:40:27 -0500
Subject: [PATCH v4 2/6] Add LSNTimeStream for converting LSN <-> time

Add a new structure, LSNTimeStream, consisting of LSNTimes -- each an
LSN, time pair. The LSNTimeStream is fixed size, so when a new LSNTime
is inserted to a full LSNTimeStream, an LSNTime is dropped and the new
LSNTime is inserted. We drop the LSNTime whose absence would cause the
least error when interpolating between its adjoining points.

LSN <-> time conversions can be done using linear interpolation with two
LSNTimes on the LSNTimeStream.

This commit does not add a global instance of LSNTimeStream. It adds the
structures and functions needed to maintain and access such a stream.
---
 src/backend/utils/activity/pgstat_wal.c | 233 ++++++++++++++++++++++++
 src/include/pgstat.h                    |  32 ++++
 src/tools/pgindent/typedefs.list        |   2 +
 3 files changed, 267 insertions(+)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index 0e374f133a9..d76ace5cbfc 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -17,8 +17,11 @@
 
 #include "postgres.h"
 
+#include "access/xlog.h"
 #include "executor/instrument.h"
+#include "utils/builtins.h"
 #include "utils/pgstat_internal.h"
+#include "utils/timestamp.h"
 
 
 PgStat_PendingWalStats PendingWalStats = {0};
@@ -32,6 +35,11 @@ PgStat_PendingWalStats PendingWalStats = {0};
 static WalUsage prevWalUsage;
 
 
+static void lsntime_insert(LSNTimeStream *stream, TimestampTz time, XLogRecPtr lsn);
+
+XLogRecPtr	estimate_lsn_at_time(const LSNTimeStream *stream, TimestampTz time);
+TimestampTz estimate_time_at_lsn(const LSNTimeStream *stream, XLogRecPtr lsn);
+
 /*
  * Calculate how much WAL usage counters have increased and update
  * shared WAL and IO statistics.
@@ -184,3 +192,228 @@ pgstat_wal_snapshot_cb(void)
 		   sizeof(pgStatLocal.snapshot.wal));
 	LWLockRelease(&stats_shmem->lock);
 }
+
+/*
+ * Given three LSNTimes, calculate the area of the triangle they form were they
+ * plotted with time on the X axis and LSN on the Y axis.
+ */
+static int
+lsn_ts_calculate_error_area(LSNTime *left, LSNTime *mid, LSNTime *right)
+{
+	int			rectangle_all = (right->time - left->time) * (right->lsn - left->lsn);
+	int			triangle1 = rectangle_all / 2;
+	int			triangle2 = (mid->lsn - left->lsn) * (mid->time - left->time) / 2;
+	int			triangle3 = (right->lsn - mid->lsn) * (right->time - mid->time) / 2;
+	int			rectangle_part = (right->lsn - mid->lsn) * (mid->time - left->time);
+
+	return rectangle_all - triangle1 - triangle2 - triangle3 - rectangle_part;
+}
+
+/*
+ * Determine which LSNTime to drop from a full LSNTimeStream. Once the LSNTime
+ * is dropped, points between it and either of its adjacent LSNTimes will be
+ * interpolated between those two LSNTimes instead. To keep the LSNTimeStream
+ * as accurate as possible, drop the LSNTime whose absence would have the least
+ * impact on future interpolations.
+ *
+ * We determine the error that would be introduced by dropping a point on the
+ * stream by calculating the area of the triangle formed by the LSNTime and its
+ * adjacent LSNTimes. We do this for each LSNTime in the stream (except for the
+ * first and last LSNTimes) and choose the LSNTime with the smallest error
+ * (area). We avoid extrapolation by never dropping the first or last points.
+ */
+static int
+lsntime_to_drop(LSNTimeStream *stream)
+{
+	int			min_area = INT_MAX;
+	int			target_point = stream->length - 1;
+
+	/* Don't drop points if free space available */
+	Assert(stream->length == LSNTIMESTREAM_VOLUME);
+
+	for (int i = stream->length - 1; i-- > 0;)
+	{
+		LSNTime    *left = &stream->data[i - 1];
+		LSNTime    *mid = &stream->data[i];
+		LSNTime    *right = &stream->data[i + 1];
+		int			area = lsn_ts_calculate_error_area(left, mid, right);
+
+		if (abs(area) < abs(min_area))
+		{
+			min_area = area;
+			target_point = i;
+		}
+	}
+
+	return target_point;
+}
+
+/*
+ * Insert a new LSNTime into the LSNTimeStream in the first available element,
+ * or, if there are no empty elements, drop an LSNTime from the stream, move
+ * all LSNTimes down and insert the new LSNTime into the element at index 0.
+ */
+void
+lsntime_insert(LSNTimeStream *stream, TimestampTz time,
+			   XLogRecPtr lsn)
+{
+	int			drop;
+	LSNTime		entrant = {.lsn = lsn,.time = time};
+
+	if (stream->length < LSNTIMESTREAM_VOLUME)
+	{
+		/*
+		 * The new entry should exceed the most recent entry to ensure time
+		 * moves forward on the stream.
+		 */
+		Assert(stream->length == 0 ||
+			   (lsn >= stream->data[LSNTIMESTREAM_VOLUME - stream->length].lsn &&
+				time >= stream->data[LSNTIMESTREAM_VOLUME - stream->length].time));
+
+		/*
+		 * If there are unfilled elements in the stream, insert the passed-in
+		 * LSNTime into the tail of the array.
+		 */
+		stream->length++;
+		stream->data[LSNTIMESTREAM_VOLUME - stream->length] = entrant;
+		return;
+	}
+
+	drop = lsntime_to_drop(stream);
+	if (drop < 0 || drop >= stream->length)
+	{
+		elog(WARNING, "Unable to insert LSNTime to LSNTimeStream. Drop failed.");
+		return;
+	}
+
+	/*
+	 * Drop the LSNTime at index drop by copying the array from drop - 1 to
+	 * drop
+	 */
+	memmove(&stream->data[1], &stream->data[0], sizeof(LSNTime) * drop);
+	stream->data[0] = entrant;
+}
+
+/*
+ * Translate time to a LSN using the provided stream. The stream will not
+ * be modified.
+ */
+XLogRecPtr
+estimate_lsn_at_time(const LSNTimeStream *stream, TimestampTz time)
+{
+	XLogRecPtr	result;
+	int64		time_elapsed,
+				lsns_elapsed;
+	LSNTime		start = {.time = PgStartTime,.lsn = PgStartLSN};
+	LSNTime		end = {.time = GetCurrentTimestamp(),.lsn = GetXLogInsertRecPtr()};
+
+	/*
+	 * If the provided time is before DB startup, the best we can do is return
+	 * the start LSN.
+	 */
+	if (time < start.time)
+		return start.lsn;
+
+	/*
+	 * If the provided time is after now, the current LSN is our best
+	 * estimate.
+	 */
+	if (time >= end.time)
+		return end.lsn;
+
+	/*
+	 * Loop through the stream. Stop at the first LSNTime earlier than our
+	 * target time. This LSNTime will be our interpolation start point. If
+	 * there's an LSNTime later than that, then that will be our interpolation
+	 * end point.
+	 */
+	for (int i = LSNTIMESTREAM_VOLUME - stream->length; i < LSNTIMESTREAM_VOLUME; i++)
+	{
+		if (stream->data[i].time > time)
+			continue;
+
+		start = stream->data[i];
+		if (i > 0)
+			end = stream->data[i - 1];
+		goto stop;
+	}
+
+	/*
+	 * If we exhausted the stream, then use its earliest LSNTime as our
+	 * interpolation end point.
+	 */
+	if (stream->length > 0)
+		end = stream->data[stream->length - 1];
+
+stop:
+	Assert(end.time > start.time);
+	Assert(end.lsn > start.lsn);
+	time_elapsed = end.time - start.time;
+	Assert(time_elapsed != 0);
+	lsns_elapsed = end.lsn - start.lsn;
+	Assert(lsns_elapsed != 0);
+	result = (double) (time - start.time) / time_elapsed * lsns_elapsed + start.lsn;
+	return Max(result, 0);
+}
+
+/*
+ * Translate lsn to a time using the provided stream. The stream will not
+ * be modified.
+ */
+TimestampTz
+estimate_time_at_lsn(const LSNTimeStream *stream, XLogRecPtr lsn)
+{
+	int64		time_elapsed,
+				lsns_elapsed;
+	TimestampTz result;
+	LSNTime		start = {.time = PgStartTime,.lsn = PgStartLSN};
+	LSNTime		end = {.time = GetCurrentTimestamp(),.lsn = GetXLogInsertRecPtr()};
+
+	/*
+	 * If the LSN is before DB startup, the best we can do is return that
+	 * time.
+	 */
+	if (lsn <= start.lsn)
+		return start.time;
+
+	/*
+	 * If the target LSN is after the current insert LSN, the current time is
+	 * our best estimate.
+	 */
+	if (lsn >= end.lsn)
+		return end.time;
+
+	/*
+	 * Loop through the stream. Stop at the first LSNTime earlier than our
+	 * target LSN. This LSNTime will be our interpolation start point. If
+	 * there's an LSNTime later than that, then that will be our interpolation
+	 * end point.
+	 */
+	for (int i = LSNTIMESTREAM_VOLUME - stream->length; i < LSNTIMESTREAM_VOLUME; i++)
+	{
+		if (stream->data[i].lsn > lsn)
+			continue;
+
+		start = stream->data[i];
+		if (i > 0)
+			end = stream->data[i - 1];
+		goto stop;
+	}
+
+	/*
+	 * If we exhausted the stream, then use its earliest LSNTime as our
+	 * interpolation end point.
+	 */
+	if (stream->length > 0)
+		end = stream->data[stream->length - 1];
+
+stop:
+	Assert(end.time > start.time);
+	Assert(end.lsn > start.lsn);
+	time_elapsed = end.time - start.time;
+	Assert(time_elapsed != 0);
+	lsns_elapsed = end.lsn - start.lsn;
+	Assert(lsns_elapsed != 0);
+	result = (double) (lsn - start.lsn) / lsns_elapsed * time_elapsed + start.time;
+	return Max(result, 0);
+}
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index 2136239710e..af348be839c 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -11,6 +11,7 @@
 #ifndef PGSTAT_H
 #define PGSTAT_H
 
+#include "access/xlogdefs.h"
 #include "datatype/timestamp.h"
 #include "portability/instr_time.h"
 #include "postmaster/pgarch.h"	/* for MAX_XFN_CHARS */
@@ -428,6 +429,37 @@ typedef struct PgStat_StatTabEntry
 	PgStat_Counter autoanalyze_count;
 } PgStat_StatTabEntry;
 
+/*
+ * The elements of an LSNTimeStream. Each LSNTime represents one or more time,
+ * LSN pairs. The LSN is typically the insert LSN recorded at the time.
+ */
+typedef struct LSNTime
+{
+	TimestampTz time;
+	XLogRecPtr	lsn;
+} LSNTime;
+
+#define LSNTIMESTREAM_VOLUME 64
+
+/*
+ * An LSN time stream is an array consisting of LSNTimes from most to least
+ * recent. The array is filled from end to start before the contents of any
+ * elements are merged. Once the LSNTimeStream length == volume (the array is
+ * full), an LSNTime is dropped, the new LSNTime is added at index 0, and the
+ * intervening LSNTimes are moved down by one.
+ *
+ * When dropping an LSNTime, we attempt to pick the member which would
+ * introduce the least error into the stream. See lsntime_to_drop() for more
+ * details.
+ *
+ * Use the stream for LSN <-> time conversion using linear interpolation.
+ */
+typedef struct LSNTimeStream
+{
+	int			length;
+	LSNTime		data[LSNTIMESTREAM_VOLUME];
+} LSNTimeStream;
+
 typedef struct PgStat_WalStats
 {
 	PgStat_Counter wal_records;
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 61ad417cde6..4c065e24ba7 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1584,6 +1584,8 @@ LogicalTapeSet
 LsnReadQueue
 LsnReadQueueNextFun
 LsnReadQueueNextStatus
+LSNTime
+LSNTimeStream
 LtreeGistOptions
 LtreeSignature
 MAGIC
-- 
2.34.1

From f492af31c1b9917aa27ba3ad76560e59f3fd5c9b Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 16:40:27 -0500
Subject: [PATCH v5 2/6] Add LSNTimeStream for converting LSN <-> time

Add a new structure, LSNTimeStream, consisting of LSNTimes -- each an
LSN, time pair. The LSNTimeStream is fixed size, so when a new LSNTime
is inserted to a full LSNTimeStream, an LSNTime is dropped and the new
LSNTime is inserted. We drop the LSNTime whose absence would cause the
least error when interpolating between its adjoining points.

LSN <-> time conversions can be done using linear interpolation with two
LSNTimes on the LSNTimeStream.

This commit does not add a global instance of LSNTimeStream. It adds the
structures and functions needed to maintain and access such a stream.
---
 src/backend/utils/activity/pgstat_wal.c | 233 ++++++++++++++++++++++++
 src/include/pgstat.h                    |  32 ++++
 src/tools/pgindent/typedefs.list        |   2 +
 3 files changed, 267 insertions(+)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index 0e374f133a9..cef9429994c 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -17,8 +17,11 @@
 
 #include "postgres.h"
 
+#include "access/xlog.h"
 #include "executor/instrument.h"
+#include "utils/builtins.h"
 #include "utils/pgstat_internal.h"
+#include "utils/timestamp.h"
 
 
 PgStat_PendingWalStats PendingWalStats = {0};
@@ -32,6 +35,11 @@ PgStat_PendingWalStats PendingWalStats = {0};
 static WalUsage prevWalUsage;
 
 
+static void lsntime_insert(LSNTimeStream *stream, TimestampTz time, XLogRecPtr lsn);
+
+XLogRecPtr	estimate_lsn_at_time(const LSNTimeStream *stream, TimestampTz time);
+TimestampTz estimate_time_at_lsn(const LSNTimeStream *stream, XLogRecPtr lsn);
+
 /*
  * Calculate how much WAL usage counters have increased and update
  * shared WAL and IO statistics.
@@ -184,3 +192,228 @@ pgstat_wal_snapshot_cb(void)
 		   sizeof(pgStatLocal.snapshot.wal));
 	LWLockRelease(&stats_shmem->lock);
 }
+
+/*
+ * Given three LSNTimes, calculate the area of the triangle they form were they
+ * plotted with time on the X axis and LSN on the Y axis.
+ */
+static int
+lsn_ts_calculate_error_area(LSNTime *left, LSNTime *mid, LSNTime *right)
+{
+	int			rectangle_all = (right->time - left->time) * (right->lsn - left->lsn);
+	int			triangle1 = rectangle_all / 2;
+	int			triangle2 = (mid->lsn - left->lsn) * (mid->time - left->time) / 2;
+	int			triangle3 = (right->lsn - mid->lsn) * (right->time - mid->time) / 2;
+	int			rectangle_part = (right->lsn - mid->lsn) * (mid->time - left->time);
+
+	return rectangle_all - triangle1 - triangle2 - triangle3 - rectangle_part;
+}
+
+/*
+ * Determine which LSNTime to drop from a full LSNTimeStream. Once the LSNTime
+ * is dropped, points between it and either of its adjacent LSNTimes will be
+ * interpolated between those two LSNTimes instead. To keep the LSNTimeStream
+ * as accurate as possible, drop the LSNTime whose absence would have the least
+ * impact on future interpolations.
+ *
+ * We determine the error that would be introduced by dropping a point on the
+ * stream by calculating the area of the triangle formed by the LSNTime and its
+ * adjacent LSNTimes. We do this for each LSNTime in the stream (except for the
+ * first and last LSNTimes) and choose the LSNTime with the smallest error
+ * (area). We avoid extrapolation by never dropping the first or last points.
+ */
+static int
+lsntime_to_drop(LSNTimeStream *stream)
+{
+	int			min_area = INT_MAX;
+	int			target_point = stream->length - 1;
+
+	/* Don't drop points if free space available */
+	Assert(stream->length == LSNTIMESTREAM_VOLUME);
+
+	for (int i = stream->length - 1; i-- > 0;)
+	{
+		LSNTime    *left = &stream->data[i - 1];
+		LSNTime    *mid = &stream->data[i];
+		LSNTime    *right = &stream->data[i + 1];
+		int			area = lsn_ts_calculate_error_area(left, mid, right);
+
+		if (abs(area) < abs(min_area))
+		{
+			min_area = area;
+			target_point = i;
+		}
+	}
+
+	return target_point;
+}
+
+/*
+ * Insert a new LSNTime into the LSNTimeStream in the first available element,
+ * or, if there are no empty elements, drop an LSNTime from the stream, move
+ * all LSNTimes down and insert the new LSNTime into the element at index 0.
+ */
+void
+lsntime_insert(LSNTimeStream *stream, TimestampTz time,
+			   XLogRecPtr lsn)
+{
+	int			drop;
+	LSNTime		entrant = {.lsn = lsn,.time = time};
+
+	if (stream->length < LSNTIMESTREAM_VOLUME)
+	{
+		/*
+		 * The new entry should exceed the most recent entry to ensure time
+		 * moves forward on the stream.
+		 */
+		Assert(stream->length == 0 ||
+			   (lsn >= stream->data[LSNTIMESTREAM_VOLUME - stream->length].lsn &&
+				time >= stream->data[LSNTIMESTREAM_VOLUME - stream->length].time));
+
+		/*
+		 * If there are unfilled elements in the stream, insert the passed-in
+		 * LSNTime into the tail of the array.
+		 */
+		stream->length++;
+		stream->data[LSNTIMESTREAM_VOLUME - stream->length] = entrant;
+		return;
+	}
+
+	drop = lsntime_to_drop(stream);
+	if (drop < 0 || drop >= stream->length)
+	{
+		elog(WARNING, "Unable to insert LSNTime to LSNTimeStream. Drop failed.");
+		return;
+	}
+
+	/*
+	 * Drop the LSNTime at index drop by copying the array from drop - 1 to
+	 * drop
+	 */
+	memmove(&stream->data[1], &stream->data[0], sizeof(LSNTime) * drop);
+	stream->data[0] = entrant;
+}
+
+/*
+ * Translate time to a LSN using the provided stream. The stream will not
+ * be modified.
+ */
+XLogRecPtr
+estimate_lsn_at_time(const LSNTimeStream *stream, TimestampTz time)
+{
+	XLogRecPtr	result;
+	int64		time_elapsed,
+				lsns_elapsed;
+	LSNTime		start = {.time = PgStartTime,.lsn = PgStartLSN};
+	LSNTime		end = {.time = GetCurrentTimestamp(),.lsn = GetXLogInsertRecPtr()};
+
+	/*
+	 * If the provided time is before DB startup, the best we can do is return
+	 * the start LSN.
+	 */
+	if (time < start.time)
+		return start.lsn;
+
+	/*
+	 * If the provided time is after now, the current LSN is our best
+	 * estimate.
+	 */
+	if (time >= end.time)
+		return end.lsn;
+
+	/*
+	 * Loop through the stream. Stop at the first LSNTime earlier than our
+	 * target time. This LSNTime will be our interpolation start point. If
+	 * there's an LSNTime later than that, then that will be our interpolation
+	 * end point.
+	 */
+	for (int i = LSNTIMESTREAM_VOLUME - stream->length; i < LSNTIMESTREAM_VOLUME; i++)
+	{
+		if (stream->data[i].time > time)
+			continue;
+
+		start = stream->data[i];
+		if (i > LSNTIMESTREAM_VOLUME)
+			end = stream->data[i - 1];
+		goto stop;
+	}
+
+	/*
+	 * If we exhausted the stream, then use its earliest LSNTime as our
+	 * interpolation end point.
+	 */
+	if (stream->length > 0)
+		end = stream->data[LSNTIMESTREAM_VOLUME - 1];
+
+stop:
+	Assert(end.time > start.time);
+	Assert(end.lsn > start.lsn);
+	time_elapsed = end.time - start.time;
+	Assert(time_elapsed != 0);
+	lsns_elapsed = end.lsn - start.lsn;
+	Assert(lsns_elapsed != 0);
+	result = (double) (time - start.time) / time_elapsed * lsns_elapsed + start.lsn;
+	return Max(result, 0);
+}
+
+/*
+ * Translate lsn to a time using the provided stream. The stream will not
+ * be modified.
+ */
+TimestampTz
+estimate_time_at_lsn(const LSNTimeStream *stream, XLogRecPtr lsn)
+{
+	int64		time_elapsed,
+				lsns_elapsed;
+	TimestampTz result;
+	LSNTime		start = {.time = PgStartTime,.lsn = PgStartLSN};
+	LSNTime		end = {.time = GetCurrentTimestamp(),.lsn = GetXLogInsertRecPtr()};
+
+	/*
+	 * If the LSN is before DB startup, the best we can do is return that
+	 * time.
+	 */
+	if (lsn <= start.lsn)
+		return start.time;
+
+	/*
+	 * If the target LSN is after the current insert LSN, the current time is
+	 * our best estimate.
+	 */
+	if (lsn >= end.lsn)
+		return end.time;
+
+	/*
+	 * Loop through the stream. Stop at the first LSNTime earlier than our
+	 * target LSN. This LSNTime will be our interpolation start point. If
+	 * there's an LSNTime later than that, then that will be our interpolation
+	 * end point.
+	 */
+	for (int i = LSNTIMESTREAM_VOLUME - stream->length; i < LSNTIMESTREAM_VOLUME; i++)
+	{
+		if (stream->data[i].lsn > lsn)
+			continue;
+
+		start = stream->data[i];
+		if (i > LSNTIMESTREAM_VOLUME - stream->length)
+			end = stream->data[i - 1];
+		goto stop;
+	}
+
+	/*
+	 * If we exhausted the stream, then use its earliest LSNTime as our
+	 * interpolation end point.
+	 */
+	if (stream->length > 0)
+		end = stream->data[LSNTIMESTREAM_VOLUME - 1];
+
+stop:
+	Assert(end.time > start.time);
+	Assert(end.lsn > start.lsn);
+	time_elapsed = end.time - start.time;
+	Assert(time_elapsed != 0);
+	lsns_elapsed = end.lsn - start.lsn;
+	Assert(lsns_elapsed != 0);
+	result = (double) (lsn - start.lsn) / lsns_elapsed * time_elapsed + start.time;
+	return Max(result, 0);
+}
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index 2136239710e..af348be839c 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -11,6 +11,7 @@
 #ifndef PGSTAT_H
 #define PGSTAT_H
 
+#include "access/xlogdefs.h"
 #include "datatype/timestamp.h"
 #include "portability/instr_time.h"
 #include "postmaster/pgarch.h"	/* for MAX_XFN_CHARS */
@@ -428,6 +429,37 @@ typedef struct PgStat_StatTabEntry
 	PgStat_Counter autoanalyze_count;
 } PgStat_StatTabEntry;
 
+/*
+ * The elements of an LSNTimeStream. Each LSNTime represents one or more time,
+ * LSN pairs. The LSN is typically the insert LSN recorded at the time.
+ */
+typedef struct LSNTime
+{
+	TimestampTz time;
+	XLogRecPtr	lsn;
+} LSNTime;
+
+#define LSNTIMESTREAM_VOLUME 64
+
+/*
+ * An LSN time stream is an array consisting of LSNTimes from most to least
+ * recent. The array is filled from end to start before the contents of any
+ * elements are merged. Once the LSNTimeStream length == volume (the array is
+ * full), an LSNTime is dropped, the new LSNTime is added at index 0, and the
+ * intervening LSNTimes are moved down by one.
+ *
+ * When dropping an LSNTime, we attempt to pick the member which would
+ * introduce the least error into the stream. See lsntime_to_drop() for more
+ * details.
+ *
+ * Use the stream for LSN <-> time conversion using linear interpolation.
+ */
+typedef struct LSNTimeStream
+{
+	int			length;
+	LSNTime		data[LSNTIMESTREAM_VOLUME];
+} LSNTimeStream;
+
 typedef struct PgStat_WalStats
 {
 	PgStat_Counter wal_records;
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 82b3b411fb5..a5851d44b16 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1584,6 +1584,8 @@ LogicalTapeSet
 LsnReadQueue
 LsnReadQueueNextFun
 LsnReadQueueNextStatus
+LSNTime
+LSNTimeStream
 LtreeGistOptions
 LtreeSignature
 MAGIC
-- 
2.34.1

From af14cc7652649e1e651ab73c2041b5bf434a57c3 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 16:32:40 -0500
Subject: [PATCH v5 4/6] Bgwriter maintains global LSNTimeStream

Insert new LSN, time pairs to the global LSNTimeStream stored in
PgStat_WalStats in the background writer's main loop. This ensures that
new values are added to the stream in a regular manner.
---
 src/backend/postmaster/bgwriter.c | 13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)

diff --git a/src/backend/postmaster/bgwriter.c b/src/backend/postmaster/bgwriter.c
index 0f75548759a..02b039cfacf 100644
--- a/src/backend/postmaster/bgwriter.c
+++ b/src/backend/postmaster/bgwriter.c
@@ -273,6 +273,7 @@ BackgroundWriterMain(char *startup_data, size_t startup_data_len)
 		{
 			TimestampTz timeout = 0;
 			TimestampTz now = GetCurrentTimestamp();
+			XLogRecPtr	current_lsn;
 
 			timeout = TimestampTzPlusMilliseconds(last_snapshot_ts,
 												  LOG_SNAPSHOT_INTERVAL_MS);
@@ -284,11 +285,15 @@ BackgroundWriterMain(char *startup_data, size_t startup_data_len)
 			 * start of a record, whereas last_snapshot_lsn points just past
 			 * the end of the record.
 			 */
-			if (now >= timeout &&
-				last_snapshot_lsn <= GetLastImportantRecPtr())
+			if (now >= timeout)
 			{
-				last_snapshot_lsn = LogStandbySnapshot();
-				last_snapshot_ts = now;
+				current_lsn = GetLastImportantRecPtr();
+				if (last_snapshot_lsn <= current_lsn)
+				{
+					last_snapshot_lsn = LogStandbySnapshot();
+					last_snapshot_ts = now;
+					pgstat_wal_update_lsntime_stream(now, current_lsn);
+				}
 			}
 		}
 
-- 
2.34.1

From 693cd6d15b0e60c16f8e7977e1631676f4ca7c5d Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Tue, 5 Dec 2023 07:29:39 -0500
Subject: [PATCH v5 1/6] Record LSN at postmaster startup

The insert_lsn at postmaster startup can be used along with PgStartTime
as seed values for a timeline mapping LSNs to time. Future commits will
add such a structure for LSN <-> time conversions. A start LSN allows
for such conversions before even inserting a value into the timeline.
The current time and current insert LSN can be used along with
PgStartTime and PgStartLSN.

This is WIP, as I'm not sure if I did this in the right place.
---
 src/backend/access/transam/xlog.c   | 2 ++
 src/backend/postmaster/postmaster.c | 2 ++
 src/include/utils/builtins.h        | 3 +++
 3 files changed, 7 insertions(+)

diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index d36272ab4ff..5be3361582e 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -142,6 +142,8 @@ bool		XLOG_DEBUG = false;
 
 int			wal_segment_size = DEFAULT_XLOG_SEG_SIZE;
 
+XLogRecPtr	PgStartLSN = InvalidXLogRecPtr;
+
 /*
  * Number of WAL insertion locks to use. A higher value allows more insertions
  * to happen concurrently, but adds some CPU overhead to flushing the WAL,
diff --git a/src/backend/postmaster/postmaster.c b/src/backend/postmaster/postmaster.c
index bf0241aed0c..f1b60fe6cee 100644
--- a/src/backend/postmaster/postmaster.c
+++ b/src/backend/postmaster/postmaster.c
@@ -117,6 +117,7 @@
 #include "storage/proc.h"
 #include "tcop/backend_startup.h"
 #include "tcop/tcopprot.h"
+#include "utils/builtins.h"
 #include "utils/datetime.h"
 #include "utils/memutils.h"
 #include "utils/pidfile.h"
@@ -1345,6 +1346,7 @@ PostmasterMain(int argc, char *argv[])
 	 * Remember postmaster startup time
 	 */
 	PgStartTime = GetCurrentTimestamp();
+	PgStartLSN = GetXLogInsertRecPtr();
 
 	/*
 	 * Report postmaster status in the postmaster.pid file, to allow pg_ctl to
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 359c570f23e..16a7a058bc7 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -17,6 +17,7 @@
 #include "fmgr.h"
 #include "nodes/nodes.h"
 #include "utils/fmgrprotos.h"
+#include "access/xlogdefs.h"
 
 /* Sign + the most decimal digits an 8-byte number could have */
 #define MAXINT8LEN 20
@@ -85,6 +86,8 @@ extern void generate_operator_clause(fmStringInfo buf,
 									 Oid opoid,
 									 const char *rightop, Oid rightoptype);
 
+extern PGDLLIMPORT XLogRecPtr PgStartLSN;
+
 /* varchar.c */
 extern int	bpchartruelen(char *s, int len);
 
-- 
2.34.1

From f384a26ef0264b688b7be1d1e0a18b17313a3ffc Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 21 Feb 2024 20:06:29 -0500
Subject: [PATCH v5 5/6] Add time <-> LSN translation functions

Previous commits added a global LSNTimeStream, maintained by background
writer, that allows approximate translations between time and LSNs.

Add SQL-callable functions to convert from LSN to time and back and a
SQL-callable function returning the entire LSNTimeStream.

This could be useful in combination with SQL-callable functions
accessing a page LSN to approximate the time of last modification of a
page or estimating the LSN consumption rate to moderate maintenance
processes and balance system resource utilization.
---
 doc/src/sgml/monitoring.sgml            | 66 +++++++++++++++++++++++++
 src/backend/utils/activity/pgstat_wal.c | 56 +++++++++++++++++++++
 src/include/catalog/pg_proc.dat         | 22 +++++++++
 3 files changed, 144 insertions(+)

diff --git a/doc/src/sgml/monitoring.sgml b/doc/src/sgml/monitoring.sgml
index 991f6299075..979c193a721 100644
--- a/doc/src/sgml/monitoring.sgml
+++ b/doc/src/sgml/monitoring.sgml
@@ -3195,6 +3195,72 @@ description | Waiting for a newly initialized WAL file to reach durable storage
    </tgroup>
   </table>
 
+  <para>
+  In addition to these WAL stats, a stream of LSN-time pairs is accessible
+  via the functions shown in <xref linkend="functions-lsn-time-stream"/>.
+  </para>
+
+  <table id="functions-lsn-time-stream">
+   <title>LSN Time Stream Information Functions</title>
+   <tgroup cols="1">
+    <thead>
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       Function
+      </para>
+      <para>
+       Description
+      </para></entry>
+     </row>
+    </thead>
+
+    <tbody>
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_estimate_lsn_at_time</primary>
+       </indexterm>
+       <function>pg_estimate_lsn_at_time</function> ( <type>timestamp with time zone</type> )
+       <returnvalue>pg_lsn</returnvalue>
+      </para>
+      <para>
+       Returns the estimated lsn at the provided time.
+      </para></entry>
+     </row>
+
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_estimate_lsn_at_time</primary>
+       </indexterm>
+       <function>pg_estimate_lsn_at_time</function> ( <type>pg_lsn</type> )
+       <returnvalue>timestamp with time zone</returnvalue>
+      </para>
+      <para>
+        Returns the estimated time at the provided lsn.
+      </para></entry>
+     </row>
+
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_lsntime_stream</primary>
+       </indexterm>
+       <function>pg_lsntime_stream</function> ()
+       <returnvalue>record</returnvalue>
+       ( <parameter>time</parameter> <type>timestamp with time zone</type>,
+       <parameter>lsn</parameter> <type>pg_lsnwith time zone</type>)
+      </para>
+      <para>
+       Returns all of the LSN-time pairs in the current LSN time stream.
+      </para></entry>
+     </row>
+    </tbody>
+   </tgroup>
+  </table>
+
+
+
 </sect2>
 
  <sect2 id="monitoring-pg-stat-database-view">
diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index 68bc5b4e9af..2e05eb1a4f3 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -19,7 +19,9 @@
 
 #include "access/xlog.h"
 #include "executor/instrument.h"
+#include "funcapi.h"
 #include "utils/builtins.h"
+#include "utils/pg_lsn.h"
 #include "utils/pgstat_internal.h"
 #include "utils/timestamp.h"
 
@@ -427,3 +429,57 @@ pgstat_wal_update_lsntime_stream(TimestampTz time, XLogRecPtr lsn)
 	lsntime_insert(&stats_shmem->stats.stream, time, lsn);
 	LWLockRelease(&stats_shmem->lock);
 }
+
+PG_FUNCTION_INFO_V1(pg_estimate_lsn_at_time);
+PG_FUNCTION_INFO_V1(pg_estimate_time_at_lsn);
+PG_FUNCTION_INFO_V1(pg_lsntime_stream);
+
+Datum
+pg_estimate_time_at_lsn(PG_FUNCTION_ARGS)
+{
+	XLogRecPtr	lsn = PG_GETARG_LSN(0);
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+	TimestampTz result;
+
+	LWLockAcquire(&stats_shmem->lock, LW_SHARED);
+	result = estimate_time_at_lsn(&stats_shmem->stats.stream, lsn);
+	LWLockRelease(&stats_shmem->lock);
+
+	PG_RETURN_TIMESTAMPTZ(result);
+}
+
+Datum
+pg_estimate_lsn_at_time(PG_FUNCTION_ARGS)
+{
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+	TimestampTz time = PG_GETARG_TIMESTAMPTZ(0);
+	XLogRecPtr	result;
+
+	LWLockAcquire(&stats_shmem->lock, LW_SHARED);
+	result = estimate_lsn_at_time(&stats_shmem->stats.stream, time);
+	LWLockRelease(&stats_shmem->lock);
+
+	PG_RETURN_LSN(result);
+}
+
+Datum
+pg_lsntime_stream(PG_FUNCTION_ARGS)
+{
+	ReturnSetInfo *rsinfo;
+	PgStat_WalStats *stats = pgstat_fetch_stat_wal();
+	LSNTimeStream *stream = &stats->stream;
+
+	InitMaterializedSRF(fcinfo, 0);
+	rsinfo = (ReturnSetInfo *) fcinfo->resultinfo;
+	for (int i = LSNTIMESTREAM_VOLUME - stream->length; i < LSNTIMESTREAM_VOLUME; i++)
+	{
+		Datum		values[2] = {0};
+		bool		nulls[2] = {0};
+
+		values[0] = stream->data[i].time;
+		values[1] = stream->data[i].lsn;
+		tuplestore_putvalues(rsinfo->setResult, rsinfo->setDesc,
+							 values, nulls);
+	}
+	return (Datum) 0;
+}
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 6a5476d3c4c..8ab14b49b2a 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -6342,6 +6342,28 @@
   prorettype => 'timestamptz', proargtypes => 'xid',
   prosrc => 'pg_xact_commit_timestamp' },
 
+{ oid => '9997',
+  descr => 'get approximate LSN at a particular point in time',
+  proname => 'pg_estimate_lsn_at_time', provolatile => 'v',
+  prorettype => 'pg_lsn', proargtypes => 'timestamptz',
+  prosrc => 'pg_estimate_lsn_at_time' },
+
+{ oid => '9996',
+  descr => 'get approximate time at a particular LSN',
+  proname => 'pg_estimate_time_at_lsn', provolatile => 'v',
+  prorettype => 'timestamptz', proargtypes => 'pg_lsn',
+  prosrc => 'pg_estimate_time_at_lsn' },
+
+{ oid => '9994',
+  descr => 'print the LSN Time Stream',
+  proname => 'pg_lsntime_stream', prorows => '64',
+  proretset => 't', provolatile => 'v', proparallel => 's',
+  prorettype => 'record', proargtypes => '',
+  proallargtypes => '{timestamptz,pg_lsn}',
+  proargmodes => '{o,o}',
+  proargnames => '{time, lsn}',
+  prosrc => 'pg_lsntime_stream' },
+
 { oid => '6168',
   descr => 'get commit timestamp and replication origin of a transaction',
   proname => 'pg_xact_commit_timestamp_origin', provolatile => 'v',
-- 
2.34.1

From f78ea2aee794358a8ba1dabece1debd52d48a10c Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 21 Feb 2024 20:28:27 -0500
Subject: [PATCH v5 3/6] Add LSNTimeStream to PgStat_WalStats

Add a globally maintained instance of an LSNTimeStream to
PgStat_WalStats and a utility function to insert new values.
---
 src/backend/utils/activity/pgstat_wal.c | 10 ++++++++++
 src/include/pgstat.h                    |  4 ++++
 2 files changed, 14 insertions(+)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index cef9429994c..68bc5b4e9af 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -417,3 +417,13 @@ stop:
 	result = (double) (lsn - start.lsn) / lsns_elapsed * time_elapsed + start.time;
 	return Max(result, 0);
 }
+
+void
+pgstat_wal_update_lsntime_stream(TimestampTz time, XLogRecPtr lsn)
+{
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+
+	LWLockAcquire(&stats_shmem->lock, LW_EXCLUSIVE);
+	lsntime_insert(&stats_shmem->stats.stream, time, lsn);
+	LWLockRelease(&stats_shmem->lock);
+}
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index af348be839c..773e3cd5003 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -470,6 +470,7 @@ typedef struct PgStat_WalStats
 	PgStat_Counter wal_sync;
 	PgStat_Counter wal_write_time;
 	PgStat_Counter wal_sync_time;
+	LSNTimeStream stream;
 	TimestampTz stat_reset_timestamp;
 } PgStat_WalStats;
 
@@ -752,6 +753,9 @@ extern void pgstat_execute_transactional_drops(int ndrops, struct xl_xact_stats_
 extern void pgstat_report_wal(bool force);
 extern PgStat_WalStats *pgstat_fetch_stat_wal(void);
 
+/* Helpers for maintaining the LSNTimeStream */
+extern void pgstat_wal_update_lsntime_stream(TimestampTz time, XLogRecPtr lsn);
+
 
 /*
  * Variables in pgstat.c
-- 
2.34.1

From 49f767bc859356df8b4a6ea03d490b6b1aa1d48d Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 21 Feb 2024 20:06:29 -0500
Subject: [PATCH v6 5/6] Add time <-> LSN translation functions

Previous commits added a global LSNTimeStream, maintained by background
writer, that allows approximate translations between time and LSNs.

Add SQL-callable functions to convert from LSN to time and back and a
SQL-callable function returning the entire LSNTimeStream.

This could be useful in combination with SQL-callable functions
accessing a page LSN to approximate the time of last modification of a
page or estimating the LSN consumption rate to moderate maintenance
processes and balance system resource utilization.
---
 doc/src/sgml/monitoring.sgml            | 66 +++++++++++++++++++++++++
 src/backend/utils/activity/pgstat_wal.c | 52 +++++++++++++++++++
 src/include/catalog/pg_proc.dat         | 22 +++++++++
 src/test/regress/expected/stats.out     | 13 +++++
 src/test/regress/sql/stats.sql          |  5 ++
 5 files changed, 158 insertions(+)

diff --git a/doc/src/sgml/monitoring.sgml b/doc/src/sgml/monitoring.sgml
index 55417a6fa9d..f86e77955d6 100644
--- a/doc/src/sgml/monitoring.sgml
+++ b/doc/src/sgml/monitoring.sgml
@@ -3195,6 +3195,72 @@ description | Waiting for a newly initialized WAL file to reach durable storage
    </tgroup>
   </table>
 
+  <para>
+  In addition to these WAL stats, a stream of LSN-time pairs is accessible
+  via the functions shown in <xref linkend="functions-lsn-time-stream"/>.
+  </para>
+
+  <table id="functions-lsn-time-stream">
+   <title>LSN Time Stream Information Functions</title>
+   <tgroup cols="1">
+    <thead>
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       Function
+      </para>
+      <para>
+       Description
+      </para></entry>
+     </row>
+    </thead>
+
+    <tbody>
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_estimate_lsn_at_time</primary>
+       </indexterm>
+       <function>pg_estimate_lsn_at_time</function> ( <type>timestamp with time zone</type> )
+       <returnvalue>pg_lsn</returnvalue>
+      </para>
+      <para>
+       Returns the estimated lsn at the provided time.
+      </para></entry>
+     </row>
+
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_estimate_lsn_at_time</primary>
+       </indexterm>
+       <function>pg_estimate_lsn_at_time</function> ( <type>pg_lsn</type> )
+       <returnvalue>timestamp with time zone</returnvalue>
+      </para>
+      <para>
+        Returns the estimated time at the provided lsn.
+      </para></entry>
+     </row>
+
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_lsntime_stream</primary>
+       </indexterm>
+       <function>pg_lsntime_stream</function> ()
+       <returnvalue>record</returnvalue>
+       ( <parameter>time</parameter> <type>timestamp with time zone</type>,
+       <parameter>lsn</parameter> <type>pg_lsnwith time zone</type>)
+      </para>
+      <para>
+       Returns all of the LSN-time pairs in the current LSN time stream.
+      </para></entry>
+     </row>
+    </tbody>
+   </tgroup>
+  </table>
+
+
+
 </sect2>
 
  <sect2 id="monitoring-pg-stat-database-view">
diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index c1c3da22b2f..7552a964b80 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -19,8 +19,10 @@
 
 #include "access/xlog.h"
 #include "executor/instrument.h"
+#include "funcapi.h"
 #include "math.h"
 #include "utils/builtins.h"
+#include "utils/pg_lsn.h"
 #include "utils/pgstat_internal.h"
 #include "utils/timestamp.h"
 
@@ -525,3 +527,53 @@ pgstat_wal_update_lsntime_stream(TimestampTz time, XLogRecPtr lsn)
 	lsntime_insert(&stats_shmem->stats.stream, time, lsn);
 	LWLockRelease(&stats_shmem->lock);
 }
+
+Datum
+pg_estimate_time_at_lsn(PG_FUNCTION_ARGS)
+{
+	XLogRecPtr	lsn = PG_GETARG_LSN(0);
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+	TimestampTz result;
+
+	LWLockAcquire(&stats_shmem->lock, LW_SHARED);
+	result = estimate_time_at_lsn(&stats_shmem->stats.stream, lsn);
+	LWLockRelease(&stats_shmem->lock);
+
+	PG_RETURN_TIMESTAMPTZ(result);
+}
+
+Datum
+pg_estimate_lsn_at_time(PG_FUNCTION_ARGS)
+{
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+	TimestampTz time = PG_GETARG_TIMESTAMPTZ(0);
+	XLogRecPtr	result;
+
+	LWLockAcquire(&stats_shmem->lock, LW_SHARED);
+	result = estimate_lsn_at_time(&stats_shmem->stats.stream, time);
+	LWLockRelease(&stats_shmem->lock);
+
+	PG_RETURN_LSN(result);
+}
+
+Datum
+pg_lsntime_stream(PG_FUNCTION_ARGS)
+{
+	ReturnSetInfo *rsinfo;
+	PgStat_WalStats *stats = pgstat_fetch_stat_wal();
+	LSNTimeStream *stream = &stats->stream;
+
+	InitMaterializedSRF(fcinfo, 0);
+	rsinfo = (ReturnSetInfo *) fcinfo->resultinfo;
+	for (int i = 0; i < stream->length; i++)
+	{
+		Datum		values[2] = {0};
+		bool		nulls[2] = {0};
+
+		values[0] = stream->data[i].time;
+		values[1] = stream->data[i].lsn;
+		tuplestore_putvalues(rsinfo->setResult, rsinfo->setDesc,
+							 values, nulls);
+	}
+	return (Datum) 0;
+}
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 54b50ee5d61..b5d8d0d3673 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -6375,6 +6375,28 @@
   prorettype => 'timestamptz', proargtypes => 'xid',
   prosrc => 'pg_xact_commit_timestamp' },
 
+{ oid => '9997',
+  descr => 'get approximate LSN at a particular point in time',
+  proname => 'pg_estimate_lsn_at_time', provolatile => 'v',
+  prorettype => 'pg_lsn', proargtypes => 'timestamptz',
+  prosrc => 'pg_estimate_lsn_at_time' },
+
+{ oid => '9996',
+  descr => 'get approximate time at a particular LSN',
+  proname => 'pg_estimate_time_at_lsn', provolatile => 'v',
+  prorettype => 'timestamptz', proargtypes => 'pg_lsn',
+  prosrc => 'pg_estimate_time_at_lsn' },
+
+{ oid => '9994',
+  descr => 'print the LSN Time Stream',
+  proname => 'pg_lsntime_stream', prorows => '64',
+  proretset => 't', provolatile => 'v', proparallel => 's',
+  prorettype => 'record', proargtypes => '',
+  proallargtypes => '{timestamptz,pg_lsn}',
+  proargmodes => '{o,o}',
+  proargnames => '{time, lsn}',
+  prosrc => 'pg_lsntime_stream' },
+
 { oid => '6168',
   descr => 'get commit timestamp and replication origin of a transaction',
   proname => 'pg_xact_commit_timestamp_origin', provolatile => 'v',
diff --git a/src/test/regress/expected/stats.out b/src/test/regress/expected/stats.out
index 6e08898b183..b02b74e5872 100644
--- a/src/test/regress/expected/stats.out
+++ b/src/test/regress/expected/stats.out
@@ -813,6 +813,19 @@ SELECT (n_tup_ins + n_tup_upd) > 0 AS has_data FROM pg_stat_all_tables
 -----
 -- Test that various stats views are being properly populated
 -----
+SELECT pg_estimate_time_at_lsn(pg_current_wal_insert_lsn()) >
+                              now() - make_interval(years=> 100);
+ ?column? 
+----------
+ t
+(1 row)
+
+SELECT pg_estimate_lsn_at_time(now()) - '0/0' > 0;
+ ?column? 
+----------
+ t
+(1 row)
+
 -- Test that sessions is incremented when a new session is started in pg_stat_database
 SELECT sessions AS db_stat_sessions FROM pg_stat_database WHERE datname = (SELECT current_database()) \gset
 \c
diff --git a/src/test/regress/sql/stats.sql b/src/test/regress/sql/stats.sql
index d8ac0d06f48..8562bdb45e8 100644
--- a/src/test/regress/sql/stats.sql
+++ b/src/test/regress/sql/stats.sql
@@ -411,6 +411,11 @@ SELECT (n_tup_ins + n_tup_upd) > 0 AS has_data FROM pg_stat_all_tables
 -- Test that various stats views are being properly populated
 -----
 
+SELECT pg_estimate_time_at_lsn(pg_current_wal_insert_lsn()) >
+                              now() - make_interval(years=> 100);
+
+SELECT pg_estimate_lsn_at_time(now()) - '0/0' > 0;
+
 -- Test that sessions is incremented when a new session is started in pg_stat_database
 SELECT sessions AS db_stat_sessions FROM pg_stat_database WHERE datname = (SELECT current_database()) \gset
 \c
-- 
2.34.1

From 3df61a9f26f33a88409920587707d269f35eccdf Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Tue, 5 Dec 2023 07:29:39 -0500
Subject: [PATCH v6 1/6] Record LSN at postmaster startup

The insert_lsn at postmaster startup can be used along with PgStartTime
as seed values for a timeline mapping LSNs to time. Future commits will
add such a structure for LSN <-> time conversions. A start LSN allows
for such conversions before even inserting a value into the timeline.
The current time and current insert LSN can be used along with
PgStartTime and PgStartLSN.

This is WIP, as I'm not sure if I did this in the right place.
---
 src/backend/access/transam/xlog.c   | 2 ++
 src/backend/postmaster/postmaster.c | 2 ++
 src/include/utils/builtins.h        | 3 +++
 3 files changed, 7 insertions(+)

diff --git a/src/backend/access/transam/xlog.c b/src/backend/access/transam/xlog.c
index 4a8a2f6098f..fed41b3f992 100644
--- a/src/backend/access/transam/xlog.c
+++ b/src/backend/access/transam/xlog.c
@@ -140,6 +140,8 @@ bool		XLOG_DEBUG = false;
 
 int			wal_segment_size = DEFAULT_XLOG_SEG_SIZE;
 
+XLogRecPtr	PgStartLSN = InvalidXLogRecPtr;
+
 /*
  * Number of WAL insertion locks to use. A higher value allows more insertions
  * to happen concurrently, but adds some CPU overhead to flushing the WAL,
diff --git a/src/backend/postmaster/postmaster.c b/src/backend/postmaster/postmaster.c
index 02442a4b85a..c637a4229fe 100644
--- a/src/backend/postmaster/postmaster.c
+++ b/src/backend/postmaster/postmaster.c
@@ -117,6 +117,7 @@
 #include "storage/proc.h"
 #include "tcop/backend_startup.h"
 #include "tcop/tcopprot.h"
+#include "utils/builtins.h"
 #include "utils/datetime.h"
 #include "utils/memutils.h"
 #include "utils/pidfile.h"
@@ -1333,6 +1334,7 @@ PostmasterMain(int argc, char *argv[])
 	 * Remember postmaster startup time
 	 */
 	PgStartTime = GetCurrentTimestamp();
+	PgStartLSN = GetXLogInsertRecPtr();
 
 	/*
 	 * Report postmaster status in the postmaster.pid file, to allow pg_ctl to
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 359c570f23e..16a7a058bc7 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -17,6 +17,7 @@
 #include "fmgr.h"
 #include "nodes/nodes.h"
 #include "utils/fmgrprotos.h"
+#include "access/xlogdefs.h"
 
 /* Sign + the most decimal digits an 8-byte number could have */
 #define MAXINT8LEN 20
@@ -85,6 +86,8 @@ extern void generate_operator_clause(fmStringInfo buf,
 									 Oid opoid,
 									 const char *rightop, Oid rightoptype);
 
+extern PGDLLIMPORT XLogRecPtr PgStartLSN;
+
 /* varchar.c */
 extern int	bpchartruelen(char *s, int len);
 
-- 
2.34.1

From 1f55402be2f1e4bd015432a11640cfe72e44957c Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 21 Feb 2024 20:28:27 -0500
Subject: [PATCH v6 3/6] Add LSNTimeStream to PgStat_WalStats

Add a globally maintained instance of an LSNTimeStream to
PgStat_WalStats and a utility function to insert new values.
---
 src/backend/utils/activity/pgstat_wal.c | 10 ++++++++++
 src/include/pgstat.h                    |  4 ++++
 2 files changed, 14 insertions(+)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index affab8437c8..c1c3da22b2f 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -515,3 +515,13 @@ stop:
 	result = (double) (lsn - start.lsn) / lsns_elapsed * time_elapsed + start.time;
 	return Max(result, 0);
 }
+
+void
+pgstat_wal_update_lsntime_stream(TimestampTz time, XLogRecPtr lsn)
+{
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+
+	LWLockAcquire(&stats_shmem->lock, LW_EXCLUSIVE);
+	lsntime_insert(&stats_shmem->stats.stream, time, lsn);
+	LWLockRelease(&stats_shmem->lock);
+}
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index 825cdc8f73a..667f2b93cad 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -470,6 +470,7 @@ typedef struct PgStat_WalStats
 	PgStat_Counter wal_sync;
 	PgStat_Counter wal_write_time;
 	PgStat_Counter wal_sync_time;
+	LSNTimeStream stream;
 	TimestampTz stat_reset_timestamp;
 } PgStat_WalStats;
 
@@ -752,6 +753,9 @@ extern void pgstat_execute_transactional_drops(int ndrops, struct xl_xact_stats_
 extern void pgstat_report_wal(bool force);
 extern PgStat_WalStats *pgstat_fetch_stat_wal(void);
 
+/* Helpers for maintaining the LSNTimeStream */
+extern void pgstat_wal_update_lsntime_stream(TimestampTz time, XLogRecPtr lsn);
+
 
 /*
  * Variables in pgstat.c
-- 
2.34.1

From d6dc1128f75d883332945ab27f98a8c70b83b607 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 16:40:27 -0500
Subject: [PATCH v6 2/6] Add LSNTimeStream for converting LSN <-> time

Add a new structure, LSNTimeStream, consisting of LSNTimes -- each an
LSN, time pair. The LSNTimeStream is fixed size, so when a new LSNTime
is inserted to a full LSNTimeStream, an LSNTime is dropped and the new
LSNTime is inserted. We drop the LSNTime whose absence would cause the
least error when interpolating between its adjoining points.

LSN <-> time conversions can be done using linear interpolation with two
LSNTimes on the LSNTimeStream.

This commit does not add a global instance of LSNTimeStream. It adds the
structures and functions needed to maintain and access such a stream.
---
 src/backend/utils/activity/pgstat_wal.c | 323 ++++++++++++++++++++++++
 src/include/pgstat.h                    |  32 +++
 src/tools/pgindent/typedefs.list        |   2 +
 3 files changed, 357 insertions(+)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index e2a3f6b865c..affab8437c8 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -17,8 +17,12 @@
 
 #include "postgres.h"
 
+#include "access/xlog.h"
 #include "executor/instrument.h"
+#include "math.h"
+#include "utils/builtins.h"
 #include "utils/pgstat_internal.h"
+#include "utils/timestamp.h"
 
 
 PgStat_PendingWalStats PendingWalStats = {0};
@@ -32,6 +36,11 @@ PgStat_PendingWalStats PendingWalStats = {0};
 static WalUsage prevWalUsage;
 
 
+static void lsntime_insert(LSNTimeStream *stream, TimestampTz time, XLogRecPtr lsn);
+
+XLogRecPtr	estimate_lsn_at_time(const LSNTimeStream *stream, TimestampTz time);
+TimestampTz estimate_time_at_lsn(const LSNTimeStream *stream, XLogRecPtr lsn);
+
 /*
  * Calculate how much WAL usage counters have increased and update
  * shared WAL and IO statistics.
@@ -192,3 +201,317 @@ pgstat_wal_snapshot_cb(void)
 		   sizeof(pgStatLocal.snapshot.wal));
 	LWLockRelease(&stats_shmem->lock);
 }
+
+/*
+ * Given three LSNTimes, calculate the area of the triangle they form were they
+ * plotted with time on the X axis and LSN on the Y axis. An illustration:
+ *
+ *   LSN
+ *    |
+ *    |                                                         * right
+ *    |
+ *    |
+ *    |
+ *    |                                                * mid    * C
+ *    |
+ *    |
+ *    |
+ *    |  * left                                        * B      * A
+ *    |
+ *    +------------------------------------------------------------------
+ *
+ * The area of the triangle with vertices (left, mid, right) is the error
+ * incurred over the interval [left, right] were we to interpolate with just
+ * [left, right] rather than [left, mid) and [mid, right).
+ */
+static float
+lsn_ts_calculate_error_area(LSNTime *left, LSNTime *mid, LSNTime *right)
+{
+	float		left_time = left->time,
+				left_lsn = left->lsn;
+	float		mid_time = mid->time,
+				mid_lsn = mid->lsn;
+	float		right_time = right->time,
+				right_lsn = right->lsn;
+
+	/* Area of the rectangle with opposing corners left and right */
+	float		rectangle_all = (right_time - left_time) * (right_lsn - left_lsn);
+
+	/* Area of the right triangle with vertices left, right, and A */
+	float		triangle1 = rectangle_all / 2;
+
+	/* Area of the right triangle with vertices left, mid, and B */
+	float		triangle2 = (mid_lsn - left_lsn) * (mid_time - left_time) / 2;
+
+	/* Area of the right triangle with vertices mid, right, and C */
+	float		triangle3 = (right_lsn - mid_lsn) * (right_time - mid_time) / 2;
+
+	/* Area of the rectangle with vertices mid, A, B, and C */
+	float		rectangle_part = (right_lsn - mid_lsn) * (mid_time - left_time);
+
+	/* Area of the triangle with vertices left, mid, and right */
+	return triangle1 - triangle2 - triangle3 - rectangle_part;
+}
+
+/*
+ * Determine which LSNTime to drop from a full LSNTimeStream. Once the LSNTime
+ * is dropped, points between it and either of its adjacent LSNTimes will be
+ * interpolated between those two LSNTimes instead. To keep the LSNTimeStream
+ * as accurate as possible, drop the LSNTime whose absence would have the least
+ * impact on future interpolations.
+ *
+ * We determine the error that would be introduced by dropping a point on the
+ * stream by calculating the area of the triangle formed by the LSNTime and its
+ * adjacent LSNTimes. We do this for each LSNTime in the stream (except for the
+ * first and last LSNTimes) and choose the LSNTime with the smallest error
+ * (area). We avoid extrapolation by never dropping the first or last points.
+ */
+static unsigned int
+lsntime_to_drop(LSNTimeStream *stream)
+{
+	double		min_area;
+	unsigned int target_point;
+
+	/* Don't drop points if free space available */
+	Assert(stream->length == LSNTIMESTREAM_VOLUME);
+
+	min_area = lsn_ts_calculate_error_area(&stream->data[0],
+										   &stream->data[1],
+										   &stream->data[2]);
+
+	target_point = 1;
+
+	for (int i = 1; i < stream->length - 1; i++)
+	{
+		LSNTime    *left = &stream->data[i - 1];
+		LSNTime    *mid = &stream->data[i];
+		LSNTime    *right = &stream->data[i + 1];
+		float		area = lsn_ts_calculate_error_area(left, mid, right);
+
+		if (fabs(area) < fabs(min_area))
+		{
+			min_area = area;
+			target_point = i;
+		}
+	}
+
+	return target_point;
+}
+
+/*
+ * Insert a new LSNTime into the LSNTimeStream in the first available element,
+ * or, if there are no empty elements, drop an LSNTime from the stream, move
+ * all the subsequent LSNTimes down and insert the new LSNTime into the tail.
+ */
+void
+lsntime_insert(LSNTimeStream *stream, TimestampTz time,
+			   XLogRecPtr lsn)
+{
+	unsigned int drop;
+	LSNTime		entrant = {.lsn = lsn,.time = time};
+
+	if (stream->length < LSNTIMESTREAM_VOLUME)
+	{
+		/*
+		 * The new entry should exceed the most recent entry to ensure time
+		 * moves forward on the stream.
+		 */
+		Assert(stream->length == 0 ||
+			   (lsn >= stream->data[stream->length - 1].lsn &&
+				time >= stream->data[stream->length - 1].time));
+
+		/*
+		 * If there are unfilled elements in the stream, insert the passed-in
+		 * LSNTime into the current tail of the array.
+		 */
+		stream->data[stream->length++] = entrant;
+		return;
+	}
+
+	drop = lsntime_to_drop(stream);
+
+	/*
+	 * Drop the LSNTime at index drop by copying the array from drop - 1 to
+	 * drop
+	 */
+	memmove(&stream->data[drop],
+			&stream->data[drop + 1],
+			sizeof(LSNTime) * (stream->length - 1 - drop));
+
+	stream->data[stream->length - 1] = entrant;
+}
+
+/*
+ * Translate time to a LSN using the provided stream. The stream will not
+ * be modified.
+ */
+XLogRecPtr
+estimate_lsn_at_time(const LSNTimeStream *stream, TimestampTz time)
+{
+	XLogRecPtr	result;
+	int64		time_elapsed,
+				lsns_elapsed;
+	LSNTime		start = {.time = PgStartTime,.lsn = PgStartLSN};
+	LSNTime		end = {.time = GetCurrentTimestamp(),.lsn = GetXLogInsertRecPtr()};
+
+	/*
+	 * If the database has been restarted, PgStartLSN may be after our oldest
+	 * value. In that case, use the oldest value in the time stream as the
+	 * start.
+	 */
+	if (stream->length > 0 && start.time > stream->data[0].time)
+		start = stream->data[0];
+
+	/*
+	 * If the LSN is before our oldest known LSN, the best we can do is return
+	 * our oldest known time.
+	 */
+	if (time < start.time)
+		return start.lsn;
+
+	/*
+	 * If the provided time is after now, the current LSN is our best
+	 * estimate.
+	 */
+	if (time >= end.time)
+		return end.lsn;
+
+	/*
+	 * Loop through the stream. Stop at the first LSNTime later than our
+	 * target time. This LSNTime will be our interpolation end point. If
+	 * there's an LSNTime earlier than that, that will be our interpolation
+	 * start point.
+	 */
+	for (int i = 0; i < stream->length; i++)
+	{
+		if (stream->data[i].time < time)
+			continue;
+
+		end = stream->data[i];
+		if (i > 0)
+			start = stream->data[i - 1];
+		goto stop;
+	}
+
+	/*
+	 * If we exhausted the stream, then use its latest LSNTime as our
+	 * interpolation start point.
+	 */
+	if (stream->length > 0)
+		start = stream->data[stream->length - 1];
+
+stop:
+
+	/*
+	 * In rare cases, the start and end LSN could be the same. If, for
+	 * example, no new records have been inserted since the last one recorded
+	 * in the LSNTimeStream and we are looking for the LSN corresponding to
+	 * the current time.
+	 */
+	if (end.lsn == start.lsn)
+		return end.lsn;
+
+	Assert(end.lsn > start.lsn);
+
+	/*
+	 * It should be extremely rare (if not impossible) for the start time and
+	 * end time to be the same. In this case, just return an LSN halfway
+	 * between the two.
+	 */
+	if (end.time == start.time)
+		return start.lsn + ((end.lsn - start.lsn) / 2);
+
+	Assert(end.time > start.time);
+
+	time_elapsed = end.time - start.time;
+	lsns_elapsed = end.lsn - start.lsn;
+
+	result = (double) (time - start.time) / time_elapsed * lsns_elapsed + start.lsn;
+	return Max(result, 0);
+}
+
+/*
+ * Translate lsn to a time using the provided stream. The stream will not
+ * be modified.
+ */
+TimestampTz
+estimate_time_at_lsn(const LSNTimeStream *stream, XLogRecPtr lsn)
+{
+	int64		time_elapsed,
+				lsns_elapsed;
+	TimestampTz result;
+	LSNTime		start = {.time = PgStartTime,.lsn = PgStartLSN};
+	LSNTime		end = {.time = GetCurrentTimestamp(),.lsn = GetXLogInsertRecPtr()};
+
+	/*
+	 * If the database has been restarted, PgStartLSN may be after our oldest
+	 * value. In that case, use the oldest value in the time stream as the
+	 * start.
+	 */
+	if (stream->length > 0 && start.time > stream->data[0].time)
+		start = stream->data[0];
+
+	/*
+	 * If the LSN is before our oldest known LSN, the best we can do is return
+	 * our oldest known time.
+	 */
+	if (lsn < start.lsn)
+		return start.time;
+
+	/*
+	 * If the target LSN is after the current insert LSN, the current time is
+	 * our best estimate.
+	 */
+	if (lsn >= end.lsn)
+		return end.time;
+
+	/*
+	 * Loop through the stream. Stop at the first LSNTime later than our
+	 * target time. This LSNTime will be our interpolation end point. If
+	 * there's an LSNTime earlier than that, that will be our interpolation
+	 * start point.
+	 */
+	for (int i = 0; i < stream->length; i++)
+	{
+		if (stream->data[i].lsn < lsn)
+			continue;
+
+		end = stream->data[i];
+		if (i > 0)
+			start = stream->data[i - 1];
+		goto stop;
+	}
+
+	/*
+	 * If we exhausted the stream, then use its earliest LSNTime as our
+	 * interpolation end point.
+	 */
+	if (stream->length > 0)
+		start = stream->data[stream->length - 1];
+
+stop:
+
+	/* It should be nearly impossible to have the same start and end time. */
+	if (end.time == start.time)
+		return end.time;
+
+	Assert(end.time > start.time);
+
+	/*
+	 * In rare cases, the start and end LSN could be the same. If, for
+	 * example, no new records have been inserted since the last one recorded
+	 * in the LSNTimeStream and we are looking for the LSN corresponding to
+	 * the current time. In this case, just return a time halfway between
+	 * start and end.
+	 */
+	if (end.lsn == start.lsn)
+		return start.time + ((end.time - start.time) / 2);
+
+	Assert(end.lsn > start.lsn);
+
+	time_elapsed = end.time - start.time;
+	lsns_elapsed = end.lsn - start.lsn;
+
+	result = (double) (lsn - start.lsn) / lsns_elapsed * time_elapsed + start.time;
+	return Max(result, 0);
+}
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index 6b99bb8aadf..825cdc8f73a 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -11,6 +11,7 @@
 #ifndef PGSTAT_H
 #define PGSTAT_H
 
+#include "access/xlogdefs.h"
 #include "datatype/timestamp.h"
 #include "portability/instr_time.h"
 #include "postmaster/pgarch.h"	/* for MAX_XFN_CHARS */
@@ -428,6 +429,37 @@ typedef struct PgStat_StatTabEntry
 	PgStat_Counter autoanalyze_count;
 } PgStat_StatTabEntry;
 
+/*
+ * The elements of an LSNTimeStream. Each LSNTime represents one or more time,
+ * LSN pairs. The LSN is typically the insert LSN recorded at the time.
+ */
+typedef struct LSNTime
+{
+	TimestampTz time;
+	XLogRecPtr	lsn;
+} LSNTime;
+
+#define LSNTIMESTREAM_VOLUME 64
+
+/*
+ * An LSN time stream is an array consisting of LSNTimes from least to most
+ * recent. The array is filled before any element is dropped. Once the
+ * LSNTimeStream length == volume (the array is full), an LSNTime is dropped,
+ * the subsequent LSNTimes are moved down by 1, and the new LSNTime is inserted
+ * at the tail.
+ *
+ * When dropping an LSNTime, we attempt to pick the member which would
+ * introduce the least error into the stream. See lsntime_to_drop() for more
+ * details.
+ *
+ * Use the stream for LSN <-> time conversion using linear interpolation.
+ */
+typedef struct LSNTimeStream
+{
+	int			length;
+	LSNTime		data[LSNTIMESTREAM_VOLUME];
+} LSNTimeStream;
+
 typedef struct PgStat_WalStats
 {
 	PgStat_Counter wal_records;
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 8de9978ad8d..d924855069c 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1587,6 +1587,8 @@ LogicalTapeSet
 LsnReadQueue
 LsnReadQueueNextFun
 LsnReadQueueNextStatus
+LSNTime
+LSNTimeStream
 LtreeGistOptions
 LtreeSignature
 MAGIC
-- 
2.34.1

From 0ab41bd5030caf33c82692c7a3a6618a3771166f Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 27 Dec 2023 16:32:40 -0500
Subject: [PATCH v6 4/6] Bgwriter maintains global LSNTimeStream

Insert new LSN, time pairs to the global LSNTimeStream stored in
PgStat_WalStats in the background writer's main loop. This ensures that
new values are added to the stream in a regular manner.
---
 src/backend/postmaster/bgwriter.c | 21 +++++++++++++++++----
 1 file changed, 17 insertions(+), 4 deletions(-)

diff --git a/src/backend/postmaster/bgwriter.c b/src/backend/postmaster/bgwriter.c
index 0f75548759a..99c2e6eecc3 100644
--- a/src/backend/postmaster/bgwriter.c
+++ b/src/backend/postmaster/bgwriter.c
@@ -273,6 +273,7 @@ BackgroundWriterMain(char *startup_data, size_t startup_data_len)
 		{
 			TimestampTz timeout = 0;
 			TimestampTz now = GetCurrentTimestamp();
+			XLogRecPtr	current_lsn;
 
 			timeout = TimestampTzPlusMilliseconds(last_snapshot_ts,
 												  LOG_SNAPSHOT_INTERVAL_MS);
@@ -284,11 +285,23 @@ BackgroundWriterMain(char *startup_data, size_t startup_data_len)
 			 * start of a record, whereas last_snapshot_lsn points just past
 			 * the end of the record.
 			 */
-			if (now >= timeout &&
-				last_snapshot_lsn <= GetLastImportantRecPtr())
+			if (now >= timeout)
 			{
-				last_snapshot_lsn = LogStandbySnapshot();
-				last_snapshot_ts = now;
+				current_lsn = GetLastImportantRecPtr();
+				if (last_snapshot_lsn <= current_lsn)
+				{
+					last_snapshot_lsn = LogStandbySnapshot();
+					last_snapshot_ts = now;
+
+					/*
+					 * After a restart GetXLogInsertRecPtr() may return 0. We
+					 * don't want the timeline to move backwards, though, so
+					 * get the insert LSN instead.
+					 */
+					if (current_lsn == 0)
+						current_lsn = GetXLogInsertRecPtr();
+					pgstat_wal_update_lsntime_stream(now, current_lsn);
+				}
 			}
 		}
 
-- 
2.34.1

From 1e8bf7042e1c652c490f9ccd2940d200617cbfee Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Mon, 5 Aug 2024 20:33:15 -0400
Subject: [PATCH v7 2/4] Add global LSNTimeStream to PgStat_WalStats

Add a globally maintained instance of an LSNTimeStream to
PgStat_WalStats and a utility function to insert new values.
The WAL generation rate is meant to be used for statistical purposes, so
it makes sense for it to live in the WAL stats data structure.

Background writer is tasked with inserting new LSN, time pairs to the
global stream in its main loop at regular intervals. There is precedent
for background writer performing such tasks: bgwriter already
periodically logs snapshots into the WAL for the benefit of standbys.
---
 src/backend/postmaster/bgwriter.c       | 81 +++++++++++++++++++++----
 src/backend/utils/activity/pgstat_wal.c | 15 +++++
 src/include/pgstat.h                    |  5 ++
 3 files changed, 89 insertions(+), 12 deletions(-)

diff --git a/src/backend/postmaster/bgwriter.c b/src/backend/postmaster/bgwriter.c
index 0f75548759a..bb5e2d8ec5d 100644
--- a/src/backend/postmaster/bgwriter.c
+++ b/src/backend/postmaster/bgwriter.c
@@ -76,6 +76,21 @@ int			BgWriterDelay = 200;
 static TimestampTz last_snapshot_ts;
 static XLogRecPtr last_snapshot_lsn = InvalidXLogRecPtr;
 
+/*
+ * Interval at which new LSN, time pairs are added into the global
+ * LSNTimeStream, in milliseconds.
+ */
+#define LOG_STREAM_INTERVAL_MS 30000
+
+/*
+ * The timestamp at which we last checked whether or not to update the global
+ * LSNTimeStream.
+ */
+static TimestampTz last_stream_check_ts;
+
+/* The LSN we last updated the LSNTimeStream with */
+static XLogRecPtr last_stream_update_lsn = InvalidXLogRecPtr;
+
 
 /*
  * Main entry point for bgwriter process
@@ -119,6 +134,12 @@ BackgroundWriterMain(char *startup_data, size_t startup_data_len)
 	 */
 	last_snapshot_ts = GetCurrentTimestamp();
 
+	/* Insert an entry to the global LSNTimeStream as soon as we can. */
+	last_stream_check_ts = last_snapshot_ts;
+	last_stream_update_lsn = GetXLogInsertRecPtr();
+	pgstat_wal_update_lsntime_stream(last_stream_update_lsn,
+									 last_stream_check_ts);
+
 	/*
 	 * Create a memory context that we will do all our work in.  We do this so
 	 * that we can reset the context during error recovery and thereby avoid
@@ -269,26 +290,62 @@ BackgroundWriterMain(char *startup_data, size_t startup_data_len)
 		 * Checkpointer, when active, is barely ever in its mainloop and thus
 		 * makes it hard to log regularly.
 		 */
-		if (XLogStandbyInfoActive() && !RecoveryInProgress())
+
+		if (!RecoveryInProgress())
 		{
 			TimestampTz timeout = 0;
 			TimestampTz now = GetCurrentTimestamp();
 
-			timeout = TimestampTzPlusMilliseconds(last_snapshot_ts,
-												  LOG_SNAPSHOT_INTERVAL_MS);
+			if (XLogStandbyInfoActive())
+			{
+				timeout = TimestampTzPlusMilliseconds(last_snapshot_ts,
+													  LOG_SNAPSHOT_INTERVAL_MS);
+
+				/*
+				 * Only log if enough time has passed and interesting records
+				 * have been inserted since the last snapshot.  Have to
+				 * compare with <= instead of < because
+				 * GetLastImportantRecPtr() points at the start of a record,
+				 * whereas last_snapshot_lsn points just past the end of the
+				 * record.
+				 */
+				if (now >= timeout &&
+					last_snapshot_lsn <= GetLastImportantRecPtr())
+				{
+					last_snapshot_lsn = LogStandbySnapshot();
+					last_snapshot_ts = now;
+				}
+			}
+
+			timeout = TimestampTzPlusMilliseconds(last_stream_check_ts,
+												  LOG_STREAM_INTERVAL_MS);
 
 			/*
-			 * Only log if enough time has passed and interesting records have
-			 * been inserted since the last snapshot.  Have to compare with <=
-			 * instead of < because GetLastImportantRecPtr() points at the
-			 * start of a record, whereas last_snapshot_lsn points just past
-			 * the end of the record.
+			 * Periodically insert a new LSNTime into the global
+			 * LSNTimeStream. It makes sense for the background writer to
+			 * maintain the global LSNTimeStream because it runs regularly and
+			 * returns to its main loop frequently.
 			 */
-			if (now >= timeout &&
-				last_snapshot_lsn <= GetLastImportantRecPtr())
+			if (now >= timeout)
 			{
-				last_snapshot_lsn = LogStandbySnapshot();
-				last_snapshot_ts = now;
+				XLogRecPtr	insert_lsn = GetXLogInsertRecPtr();
+
+				Assert(insert_lsn != InvalidXLogRecPtr);
+
+				/*
+				 * We only insert an LSNTime if the LSN has changed since the
+				 * last update. This sacrifices accuracy on LSN -> time
+				 * conversions but saves space, which increases the accuracy
+				 * of time -> LSN conversions.
+				 */
+				if (insert_lsn > last_stream_update_lsn)
+				{
+					pgstat_wal_update_lsntime_stream(insert_lsn,
+													 now);
+					last_stream_update_lsn = insert_lsn;
+				}
+
+				last_stream_check_ts = now;
 			}
 		}
 
diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index 95ec65a51ff..1ce9060641c 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -369,6 +369,21 @@ lsntime_insert(LSNTimeStream *stream, TimestampTz time,
 }
 
 
+/*
+ * Utility function for inserting a new member into the LSNTimeStream member
+ * of WAL stats.
+ */
+void
+pgstat_wal_update_lsntime_stream(XLogRecPtr lsn, TimestampTz time)
+{
+	PgStatShared_Wal *stats_shmem = &pgStatLocal.shmem->wal;
+
+	LWLockAcquire(&stats_shmem->lock, LW_EXCLUSIVE);
+	lsntime_insert(&stats_shmem->stats.stream, time, lsn);
+	LWLockRelease(&stats_shmem->lock);
+}
+
+
 /*
  * Returns a range of LSNTimes starting at lower and ending at upper and
  * covering the target_time. If target_time is before the stream, lower will
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index 13856e2bef3..43df60ce24c 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -507,6 +507,7 @@ typedef struct PgStat_WalStats
 	PgStat_Counter wal_sync;
 	PgStat_Counter wal_write_time;
 	PgStat_Counter wal_sync_time;
+	LSNTimeStream stream;
 	TimestampTz stat_reset_timestamp;
 } PgStat_WalStats;
 
@@ -795,6 +796,10 @@ extern void time_bounds_for_lsn(const LSNTimeStream *stream,
 								XLogRecPtr target_lsn,
 								LSNTime *lower, LSNTime *upper);
 
+/* Helper for maintaining the global LSNTimeStream */
+extern void pgstat_wal_update_lsntime_stream(XLogRecPtr lsn,
+											 TimestampTz time);
+
 
 /*
  * Variables in pgstat.c
-- 
2.34.1

From eeb936816924b91a194ed03a4296b4f669e72071 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Wed, 7 Aug 2024 10:57:45 -0400
Subject: [PATCH v7 3/4] Add time <-> LSN translation range functions

Previous commits added a global LSNTimeStream, maintained by background
writer and functions to return a range of LSNs covering a time or time
covering an LSN.

Add SQL-callable functions to produce these ranges and a SQL-callable
function returning the entire LSNTimeStream.

This could be useful in combination with SQL-callable functions
accessing a page LSN to approximate the time of last modification of a
page or estimating the LSN consumption rate to moderate maintenance
processes and balance system resource utilization.
---
 doc/src/sgml/monitoring.sgml        |  75 +++++++++++++++++++
 src/backend/utils/adt/pgstatfuncs.c | 107 ++++++++++++++++++++++++++++
 src/include/catalog/pg_proc.dat     |  27 +++++++
 src/test/regress/expected/stats.out |  43 +++++++++++
 src/test/regress/sql/stats.sql      |  28 ++++++++
 5 files changed, 280 insertions(+)

diff --git a/doc/src/sgml/monitoring.sgml b/doc/src/sgml/monitoring.sgml
index 55417a6fa9d..9b63659900b 100644
--- a/doc/src/sgml/monitoring.sgml
+++ b/doc/src/sgml/monitoring.sgml
@@ -3195,6 +3195,81 @@ description | Waiting for a newly initialized WAL file to reach durable storage
    </tgroup>
   </table>
 
+  <para>
+  In addition to these WAL stats, a stream of LSN-time pairs is accessible
+  via the functions shown in <xref linkend="functions-lsn-time-stream"/>.
+  </para>
+
+  <table id="functions-lsn-time-stream">
+   <title>LSN Time Stream Information Functions</title>
+   <tgroup cols="1">
+    <thead>
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       Function
+      </para>
+      <para>
+       Description
+      </para></entry>
+     </row>
+    </thead>
+
+    <tbody>
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_stat_lsn_bounds_for_time</primary>
+       </indexterm>
+       <function>pg_stat_lsn_bounds_for_time</function>
+       ( <type>timestamp with time zone</type> )
+       <returnvalue>record</returnvalue>
+       (<parameter>lsn</parameter> <type>pg_lsn</type>,
+       <parameter>lsn</parameter> <type>pg_lsn</type>)
+      </para>
+      <para>
+       Returns the upper and lower bound of the LSN range on the global
+       LSNTimeLine in which the time falls.
+      </para></entry>
+     </row>
+
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_stat_time_bounds_for_lsn</primary>
+       </indexterm>
+       <function>pg_stat_time_bounds_for_lsn</function>
+       ( <type>pg_lsn</type> )
+       <returnvalue>record</returnvalue>
+       ( <parameter>time</parameter> <type>timestamp with time zone</type>,
+       <parameter>time</parameter> <type>timestamp with time zone</type>)
+      </para>
+      <para>
+       Returns the upper and lower bound of the time range on the global
+       LSNTimeLine in which the LSN falls.
+      </para></entry>
+     </row>
+
+     <row>
+      <entry role="func_table_entry"><para role="func_signature">
+       <indexterm>
+        <primary>pg_stat_lsntime_stream</primary>
+       </indexterm>
+       <function>pg_stat_lsntime_stream</function> ()
+       <returnvalue>setof record</returnvalue>
+       ( <parameter>lsn</parameter> <type>pg_lsn</type>,
+       <parameter>time</parameter> <type>timestamp with time zone</type>)
+      </para>
+      <para>
+       Returns all of the LSN-time pairs currently in the global LSN time
+       stream.
+      </para></entry>
+     </row>
+    </tbody>
+   </tgroup>
+  </table>
+
+
+
 </sect2>
 
  <sect2 id="monitoring-pg-stat-database-view">
diff --git a/src/backend/utils/adt/pgstatfuncs.c b/src/backend/utils/adt/pgstatfuncs.c
index 32211371237..ac862fb679a 100644
--- a/src/backend/utils/adt/pgstatfuncs.c
+++ b/src/backend/utils/adt/pgstatfuncs.c
@@ -30,6 +30,7 @@
 #include "storage/procarray.h"
 #include "utils/acl.h"
 #include "utils/builtins.h"
+#include "utils/pg_lsn.h"
 #include "utils/timestamp.h"
 
 #define UINT32_ACCESS_ONCE(var)		 ((uint32)(*((volatile uint32 *)&(var))))
@@ -1526,6 +1527,112 @@ pg_stat_get_wal(PG_FUNCTION_ARGS)
 	PG_RETURN_DATUM(HeapTupleGetDatum(heap_form_tuple(tupdesc, values, nulls)));
 }
 
+/*
+ * Returns the LSN, time pairs making up the global LSNTimeStream maintained
+ * in WAL statistics.
+ */
+Datum
+pg_stat_lsntime_stream(PG_FUNCTION_ARGS)
+{
+	ReturnSetInfo *rsinfo;
+	PgStat_WalStats *stats;
+	LSNTimeStream *stream;
+
+	InitMaterializedSRF(fcinfo, 0);
+	rsinfo = (ReturnSetInfo *) fcinfo->resultinfo;
+
+	stats = pgstat_fetch_stat_wal();
+	stream = &stats->stream;
+
+	for (size_t i = 0; i < stream->length; i++)
+	{
+		Datum		values[2] = {0};
+		bool		nulls[2] = {0};
+
+		values[0] = stream->data[i].lsn;
+		values[1] = stream->data[i].time;
+		tuplestore_putvalues(rsinfo->setResult, rsinfo->setDesc,
+							 values, nulls);
+	}
+
+	return (Datum) 0;
+}
+
+/*
+ * Returns the upper and lower bounds of an LSN range covering the passed-in
+ * time. If the passed-in time is far enough in the past that we don't have
+ * data, the lower bound will be InvalidXLogRecPtr. If it is in the future,
+ * the upper bound will be FFFFFFFF/FFFFFFFF.
+ */
+Datum
+pg_stat_lsn_bounds_for_time(PG_FUNCTION_ARGS)
+{
+	PgStat_WalStats *wal_stats;
+	TimestampTz target_time;
+	LSNTime		lower,
+				upper;
+	TupleDesc	tupdesc;
+	Datum		values[2] = {0};
+	bool		nulls[2] = {0};
+
+	target_time = PG_GETARG_TIMESTAMPTZ(0);
+
+	tupdesc = CreateTemplateTupleDesc(2);
+	TupleDescInitEntry(tupdesc, (AttrNumber) 1, "lower",
+					   PG_LSNOID, -1, 0);
+	TupleDescInitEntry(tupdesc, (AttrNumber) 2, "upper",
+					   PG_LSNOID, -1, 0);
+	BlessTupleDesc(tupdesc);
+
+	wal_stats = pgstat_fetch_stat_wal();
+	lsn_bounds_for_time(&wal_stats->stream, target_time, &lower, &upper);
+
+	values[0] = lower.lsn;
+	values[1] = upper.lsn;
+
+	PG_RETURN_DATUM(HeapTupleGetDatum(heap_form_tuple(tupdesc,
+													  values,
+													  nulls)));
+}
+
+
+/*
+ * Returns the upper and lower bounds of a TimestampTz range covering the
+ * passed-in LSN. If the passed-in LSN is far enough in the past that we don't
+ * have data, the lower bound will be -infinity. If the passed-in LSN is in
+ * the future, the upper bound will be infinity.
+ */
+Datum
+pg_stat_time_bounds_for_lsn(PG_FUNCTION_ARGS)
+{
+	PgStat_WalStats *wal_stats;
+	XLogRecPtr	target_lsn;
+	LSNTime		lower,
+				upper;
+	TupleDesc	tupdesc;
+	Datum		values[2] = {0};
+	bool		nulls[2] = {0};
+
+	target_lsn = PG_GETARG_LSN(0);
+
+	tupdesc = CreateTemplateTupleDesc(2);
+	TupleDescInitEntry(tupdesc, (AttrNumber) 1, "lower",
+					   TIMESTAMPTZOID, -1, 0);
+	TupleDescInitEntry(tupdesc, (AttrNumber) 2, "upper",
+					   TIMESTAMPTZOID, -1, 0);
+	BlessTupleDesc(tupdesc);
+
+	wal_stats = pgstat_fetch_stat_wal();
+	time_bounds_for_lsn(&wal_stats->stream, target_lsn, &lower, &upper);
+
+	values[0] = lower.time;
+	values[1] = upper.time;
+
+	PG_RETURN_DATUM(HeapTupleGetDatum(heap_form_tuple(tupdesc,
+													  values,
+													  nulls)));
+}
+
 /*
  * Returns statistics of SLRU caches.
  */
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index d36f6001bb1..c59f42bc974 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -6375,6 +6375,33 @@
   prorettype => 'timestamptz', proargtypes => 'xid',
   prosrc => 'pg_xact_commit_timestamp' },
 
+{ oid => '9997', descr => 'get upper and lower time bounds for LSN',
+  proname => 'pg_stat_time_bounds_for_lsn', provolatile => 'v',
+  proisstrict => 't', proparallel => 'u',
+  prorettype => 'record', proargtypes => 'pg_lsn',
+  proallargtypes => '{pg_lsn,timestamptz,timestamptz}',
+  proargmodes => '{i,o,o}',
+  proargnames => '{target_lsn, lower, upper}',
+  prosrc => 'pg_stat_time_bounds_for_lsn' },
+
+{ oid => '9996', descr => 'get upper and lower LSN bounds for time',
+  proname => 'pg_stat_lsn_bounds_for_time', provolatile => 'v',
+  proisstrict => 't', proparallel => 'u',
+  prorettype => 'record', proargtypes => 'timestamptz',
+  proallargtypes => '{timestamptz,pg_lsn,pg_lsn}',
+  proargmodes => '{i,o,o}',
+  proargnames => '{target_time, lower, upper}',
+  prosrc => 'pg_stat_lsn_bounds_for_time' },
+
+{ oid => '9994',
+  descr => 'print the LSN Time Stream',
+  proname => 'pg_stat_lsntime_stream', prorows => '64',
+  provolatile => 'v', proparallel => 'u',
+  proretset => 't', prorettype => 'record',
+  proargtypes => '', proallargtypes => '{pg_lsn,timestamptz}',
+  proargmodes => '{o,o}', proargnames => '{lsn,time}',
+  prosrc => 'pg_stat_lsntime_stream' },
+
 { oid => '6168',
   descr => 'get commit timestamp and replication origin of a transaction',
   proname => 'pg_xact_commit_timestamp_origin', provolatile => 'v',
diff --git a/src/test/regress/expected/stats.out b/src/test/regress/expected/stats.out
index 6e08898b183..5f32e3bd9e0 100644
--- a/src/test/regress/expected/stats.out
+++ b/src/test/regress/expected/stats.out
@@ -813,6 +813,49 @@ SELECT (n_tup_ins + n_tup_upd) > 0 AS has_data FROM pg_stat_all_tables
 -----
 -- Test that various stats views are being properly populated
 -----
+-- Test the functions querying the global LSNTimeStream stored in WAL stats.
+-- An LSN range covering a time 100 years in the past should be from 0 to a
+-- non-zero LSN (either the oldest LSN in the stream or the current insert
+-- LSN).
+SELECT lower = pg_lsn(0),
+       upper > pg_lsn(0)
+  FROM pg_stat_lsn_bounds_for_time(now() - make_interval(years=> 100));
+ ?column? | ?column? 
+----------+----------
+ t        | t
+(1 row)
+
+-- An LSN range covering a time 100 years in the future should be from roughly
+-- the current time to FFFFFFFF/FFFFFFFF (UINT64_MAX).
+SELECT lower > pg_lsn(0),
+       upper = pg_lsn('FFFFFFFF/FFFFFFFF')
+    FROM pg_stat_lsn_bounds_for_time(now() + make_interval(years=> 100));
+ ?column? | ?column? 
+----------+----------
+ t        | t
+(1 row)
+
+-- A TimestampTz range covering LSN 0 should be from -infinity to a positive
+-- time (either the oldest time in the stream or the current time).
+SELECT lower = timestamptz('-infinity'),
+       upper::time > 'allballs'::time
+    FROM pg_stat_time_bounds_for_lsn(pg_lsn(0));
+ ?column? | ?column? 
+----------+----------
+ t        | t
+(1 row)
+
+-- A TimestampTz range covering an LSN 1 GB in the future should be from
+-- roughly the current time to infinity.
+SELECT lower::time > 'allballs'::time,
+       upper = timestamptz('infinity')
+    FROM pg_stat_time_bounds_for_lsn(
+         pg_current_wal_insert_lsn() + 1000000000);
+ ?column? | ?column? 
+----------+----------
+ t        | t
+(1 row)
+
 -- Test that sessions is incremented when a new session is started in pg_stat_database
 SELECT sessions AS db_stat_sessions FROM pg_stat_database WHERE datname = (SELECT current_database()) \gset
 \c
diff --git a/src/test/regress/sql/stats.sql b/src/test/regress/sql/stats.sql
index d8ac0d06f48..0260779141c 100644
--- a/src/test/regress/sql/stats.sql
+++ b/src/test/regress/sql/stats.sql
@@ -411,6 +411,34 @@ SELECT (n_tup_ins + n_tup_upd) > 0 AS has_data FROM pg_stat_all_tables
 -- Test that various stats views are being properly populated
 -----
 
+-- Test the functions querying the global LSNTimeStream stored in WAL stats.
+
+-- An LSN range covering a time 100 years in the past should be from 0 to a
+-- non-zero LSN (either the oldest LSN in the stream or the current insert
+-- LSN).
+SELECT lower = pg_lsn(0),
+       upper > pg_lsn(0)
+  FROM pg_stat_lsn_bounds_for_time(now() - make_interval(years=> 100));
+
+-- An LSN range covering a time 100 years in the future should be from roughly
+-- the current time to FFFFFFFF/FFFFFFFF (UINT64_MAX).
+SELECT lower > pg_lsn(0),
+       upper = pg_lsn('FFFFFFFF/FFFFFFFF')
+    FROM pg_stat_lsn_bounds_for_time(now() + make_interval(years=> 100));
+
+-- A TimestampTz range covering LSN 0 should be from -infinity to a positive
+-- time (either the oldest time in the stream or the current time).
+SELECT lower = timestamptz('-infinity'),
+       upper::time > 'allballs'::time
+    FROM pg_stat_time_bounds_for_lsn(pg_lsn(0));
+
+-- A TimestampTz range covering an LSN 1 GB in the future should be from
+-- roughly the current time to infinity.
+SELECT lower::time > 'allballs'::time,
+       upper = timestamptz('infinity')
+    FROM pg_stat_time_bounds_for_lsn(
+         pg_current_wal_insert_lsn() + 1000000000);
+
 -- Test that sessions is incremented when a new session is started in pg_stat_database
 SELECT sessions AS db_stat_sessions FROM pg_stat_database WHERE datname = (SELECT current_database()) \gset
 \c
-- 
2.34.1

From 54d6baf71e0e73131bb03fe641fd9bdaddf18a93 Mon Sep 17 00:00:00 2001
From: Melanie Plageman <melanieplageman@gmail.com>
Date: Mon, 5 Aug 2024 20:29:51 -0400
Subject: [PATCH v7 1/4] Add LSNTimeStream API for converting LSN <-> time

Add a new structure, LSNTimeStream, consisting of LSNTimes -- each an
LSN, time pair. This structure is intended to reflect the WAL generation
rate. It can be used to determine a time range in which an LSN was
inserted or an LSN range covering a particular time. These could be used
to interpolate a more specific point in the range.

It produces ranges and not specific time <-> LSN conversions because an
LSNTimeStream is lossy. An LSNTimeStream is fixed size, so when a new
LSNTime is inserted to a full LSNTimeStream, an LSNTime is dropped and
the new LSNTime is inserted. We drop the LSNTime whose absence would
cause the least error when interpolating between its adjoining points.

This commit does not add any instances of LSNTimeStream.
---
 src/backend/utils/activity/pgstat_wal.c | 414 ++++++++++++++++++++++++
 src/include/pgstat.h                    |  45 +++
 src/tools/pgindent/typedefs.list        |   2 +
 3 files changed, 461 insertions(+)

diff --git a/src/backend/utils/activity/pgstat_wal.c b/src/backend/utils/activity/pgstat_wal.c
index e2a3f6b865c..95ec65a51ff 100644
--- a/src/backend/utils/activity/pgstat_wal.c
+++ b/src/backend/utils/activity/pgstat_wal.c
@@ -17,8 +17,11 @@
 
 #include "postgres.h"
 
+#include "access/xlog.h"
 #include "executor/instrument.h"
+#include "math.h"
 #include "utils/pgstat_internal.h"
+#include "utils/timestamp.h"
 
 
 PgStat_PendingWalStats PendingWalStats = {0};
@@ -31,6 +34,23 @@ PgStat_PendingWalStats PendingWalStats = {0};
  */
 static WalUsage prevWalUsage;
 
+static double lsn_ts_calculate_error_area(LSNTime *left,
+										  LSNTime *mid,
+										  LSNTime *right);
+static unsigned char lsntime_to_drop(LSNTimeStream *stream);
+static void lsntime_insert(LSNTimeStream *stream, TimestampTz time,
+						   XLogRecPtr lsn);
+
+static void stream_get_bounds_for_lsn(const LSNTimeStream *stream,
+									  XLogRecPtr target_lsn,
+									  LSNTime *lower,
+									  LSNTime *upper);
+
+static void stream_get_bounds_for_time(const LSNTimeStream *stream,
+									   TimestampTz target_time,
+									   LSNTime *lower,
+									   LSNTime *upper);
+
 
 /*
  * Calculate how much WAL usage counters have increased and update
@@ -192,3 +212,397 @@ pgstat_wal_snapshot_cb(void)
 		   sizeof(pgStatLocal.snapshot.wal));
 	LWLockRelease(&stats_shmem->lock);
 }
+
+/*
+ * Given three LSNTimes, calculate the area of the triangle they form were
+ * they plotted with time on the X axis and LSN on the Y axis. An
+ * illustration:
+ *
+ *   LSN
+ *    |
+ *    |                                                         * right
+ *    |
+ *    |
+ *    |
+ *    |                                                * mid    * C
+ *    |
+ *    |
+ *    |
+ *    |  * left                                        * B      * A
+ *    |
+ *    +------------------------------------------------------------------
+ *
+ * The area of the triangle with vertices (left, mid, right) is the error
+ * incurred over the interval [left, right] were we to interpolate with just
+ * [left, right] rather than [left, mid] and [mid, right].
+ */
+static double
+lsn_ts_calculate_error_area(LSNTime *left, LSNTime *mid, LSNTime *right)
+{
+	double		left_time = left->time,
+				left_lsn = left->lsn;
+	double		mid_time = mid->time,
+				mid_lsn = mid->lsn;
+	double		right_time = right->time,
+				right_lsn = right->lsn;
+	double		rectangle_all,
+				triangle1,
+				triangle2,
+				triangle3,
+				rectangle_part,
+				area_to_subtract;
+
+	/* Area of the rectangle with opposing corners left and right */
+	rectangle_all = (right_time - left_time) * (right_lsn - left_lsn);
+
+	/* Area of the right triangle with vertices left, right, and A */
+	triangle1 = rectangle_all / 2;
+
+	/* Area of the right triangle with vertices left, mid, and B */
+	triangle2 = (mid_lsn - left_lsn) * (mid_time - left_time) / 2;
+
+	/* Area of the right triangle with vertices mid, right, and C */
+	triangle3 = (right_lsn - mid_lsn) * (right_time - mid_time) / 2;
+
+	/* Area of the rectangle with vertices mid, A, B, and C */
+	rectangle_part = (right_lsn - mid_lsn) * (mid_time - left_time);
+
+	/* Sum up the area to subtract first to produce a more precise answer */
+	area_to_subtract = triangle2 + triangle3 + rectangle_part;
+
+	/* Area of the triangle with vertices left, mid, and right */
+	return fabs(triangle1 - area_to_subtract);
+}
+
+/*
+ * Determine which LSNTime to drop from a full LSNTimeStream.
+ * Drop the LSNTime whose absence would introduce the least error into future
+ * linear interpolation on the stream.
+ *
+ * We determine the error that would be introduced by dropping a point on the
+ * stream by calculating the area of the triangle formed by the LSNTime and
+ * its adjacent LSNTimes. We do this for each LSNTime in the stream (except
+ * for the first and last LSNTimes) and choose the LSNTime with the smallest
+ * error (area).
+ *
+ * We avoid extrapolation by never dropping the first or last points.
+ */
+static unsigned char
+lsntime_to_drop(LSNTimeStream *stream)
+{
+	double		min_area;
+	unsigned char target_point;
+
+	/* Don't drop points if free spots available are available */
+	Assert(stream->length == LSNTIMESTREAM_VOLUME);
+	StaticAssertStmt(LSNTIMESTREAM_VOLUME >= 3, "LSNTIMESTREAM_VOLUME < 3");
+
+	min_area = lsn_ts_calculate_error_area(&stream->data[0],
+										   &stream->data[1],
+										   &stream->data[2]);
+
+	target_point = 1;
+
+	for (size_t i = 2; i < stream->length - 1; i++)
+	{
+		LSNTime    *left = &stream->data[i - 1];
+		LSNTime    *mid = &stream->data[i];
+		LSNTime    *right = &stream->data[i + 1];
+		double		area = lsn_ts_calculate_error_area(left, mid, right);
+
+		if (area < min_area)
+		{
+			min_area = area;
+			target_point = i;
+		}
+	}
+
+	return target_point;
+}
+
+/*
+ * Insert a new LSNTime into the LSNTimeStream in the first available element.
+ * If there are no empty elements, drop an LSNTime from the stream to make
+ * room for the new LSNTime.
+ */
+static void
+lsntime_insert(LSNTimeStream *stream, TimestampTz time,
+			   XLogRecPtr lsn)
+{
+	unsigned char drop;
+	LSNTime		entrant = {.lsn = lsn,.time = time};
+
+	if (stream->length < LSNTIMESTREAM_VOLUME)
+	{
+		/*
+		 * Time must move forward on the stream. If the clock moves backwards,
+		 * for example in an NTP correction, we'll just skip inserting this
+		 * LSNTime.
+		 *
+		 * Translating LSN <-> time is most meaningful if the LSNTimeStream
+		 * entries are the position of a single location in the WAL over time.
+		 * Though time must monotonically increase, it is valid to insert
+		 * multiple LSNTimes with the same LSN. Imagine a period of time in
+		 * which no new WAL records are inserted.
+		 */
+		if (stream->length > 0 &&
+			(time <= stream->data[stream->length - 1].time ||
+			 lsn < stream->data[stream->length - 1].lsn))
+		{
+			ereport(WARNING,
+					errmsg("Won't insert non-monotonic \"%lu, %s\" to LSNTimeStream.",
+						   lsn, timestamptz_to_str(time)));
+			return;
+		}
+
+		stream->data[stream->length++] = entrant;
+		return;
+	}
+
+	drop = lsntime_to_drop(stream);
+
+	memmove(&stream->data[drop],
+			&stream->data[drop + 1],
+			sizeof(LSNTime) * (stream->length - 1 - drop));
+
+	stream->data[stream->length - 1] = entrant;
+}
+
+
+/*
+ * Returns a range of LSNTimes starting at lower and ending at upper and
+ * covering the target_time. If target_time is before the stream, lower will
+ * contain the minimum values for the datatypes. If target_time is newer than
+ * the stream, upper will contain the maximum values for the datatypes.
+ */
+static void
+stream_get_bounds_for_time(const LSNTimeStream *stream,
+						   TimestampTz target_time,
+						   LSNTime *lower,
+						   LSNTime *upper)
+{
+	Assert(lower && upper);
+
+	/*
+	 * If the target_time is "off the stream" -- either the stream has no
+	 * members or the target_time is older than all values in the stream or
+	 * newer than all values -- the lower and/or upper bounds may be the min
+	 * or max value for the datatypes, respectively.
+	 */
+	*lower = LSNTIME_INIT(InvalidXLogRecPtr, INT64_MIN);
+	*upper = LSNTIME_INIT(UINT64_MAX, INT64_MAX);
+
+	/*
+	 * If the LSNTimeStream has no members, it provides no information about
+	 * the range.
+	 */
+	if (stream->length == 0)
+	{
+		elog(DEBUG1,
+			 "Attempt to identify LSN bounds for time: \"%s\" using empty LSNTimeStream.",
+			 timestamptz_to_str(target_time));
+		return;
+	}
+
+	/*
+	 * If the target_time is older than the stream, the oldest member in the
+	 * stream is our upper bound.
+	 */
+	if (target_time <= stream->data[0].time)
+	{
+		*upper = stream->data[0];
+		if (target_time == stream->data[0].time)
+			*lower = stream->data[0];
+		return;
+	}
+
+	/*
+	 * Loop through the stream and stop at the first LSNTime newer than or
+	 * equal to our target time. Skip the first LSNTime, as we know it is
+	 * older than our target time.
+	 */
+	for (size_t i = 1; i < stream->length; i++)
+	{
+		if (target_time == stream->data[i].time)
+		{
+			*lower = stream->data[i];
+			*upper = stream->data[i];
+			return;
+		}
+
+		if (target_time < stream->data[i].time)
+		{
+			/* Time must increase monotonically on the stream. */
+			Assert(stream->data[i - 1].time <
+				   stream->data[i].time);
+			*lower = stream->data[i - 1];
+			*upper = stream->data[i];
+			return;
+		}
+	}
+
+	/*
+	 * target_time is newer than the stream, so the newest member in the
+	 * stream is our lower bound.
+	 */
+	*lower = stream->data[stream->length - 1];
+}
+
+/*
+ * Try to find an upper and lower bound for the possible LSN values at the
+ * provided target_time. If the target_time doesn't fall on the provided
+ * LSNTimeStream, we compare the target_time to the current time and see if we
+ * can fill in a missing boundary. Note that we do not consult the
+ * current time if the target_time fell on the stream -- even if doing so
+ * might provide a tighter range.
+ */
+void
+lsn_bounds_for_time(const LSNTimeStream *stream, TimestampTz target_time,
+					LSNTime *lower, LSNTime *upper)
+{
+	TimestampTz current_time;
+	XLogRecPtr	current_lsn;
+
+	stream_get_bounds_for_time(stream, target_time, lower, upper);
+
+	/*
+	 * We found valid upper and lower bounds for target_time, so we're done.
+	 */
+	if (lower->lsn != InvalidXLogRecPtr && upper->lsn != UINT64_MAX)
+		return;
+
+	/*
+	 * The target_time was either off the stream or the stream has no members.
+	 * In either case, see if we can use the current time and LSN to provide
+	 * one (or both) of the bounds.
+	 */
+	current_time = GetCurrentTimestamp();
+	current_lsn = GetXLogInsertRecPtr();
+
+	if (lower->lsn == InvalidXLogRecPtr && target_time >= current_time)
+		*lower = LSNTIME_INIT(current_lsn, current_time);
+
+	if (upper->lsn == UINT64_MAX && target_time <= current_time)
+		*upper = LSNTIME_INIT(current_lsn, current_time);
+
+	Assert(upper->lsn >= lower->lsn);
+}
+
+/*
+ * Returns a range of LSNTimes starting at lower and ending at upper and
+ * covering the target_lsn. If target_lsn is before the stream, lower will
+ * contain the minimum values for the datatypes. If target_time is newer than
+ * the stream, upper will contain the maximum values for the datatypes.
+ */
+static void
+stream_get_bounds_for_lsn(const LSNTimeStream *stream,
+						  XLogRecPtr target_lsn,
+						  LSNTime *lower,
+						  LSNTime *upper)
+{
+	Assert(lower && upper);
+
+	/*
+	 * If the target_time is "off the stream" -- either the stream has no
+	 * members or the target_time is older than all values in the stream or
+	 * newer than all values -- the lower and/or upper bounds may be the min
+	 * or max value for the datatypes, respectively.
+	 */
+	*lower = LSNTIME_INIT(InvalidXLogRecPtr, INT64_MIN);
+	*upper = LSNTIME_INIT(UINT64_MAX, INT64_MAX);
+
+	/*
+	 * If the LSNTimeStream has no members, it provides no information about
+	 * the range.
+	 */
+	if (stream->length == 0)
+	{
+		elog(DEBUG1,
+			 "Attempt to identify time bounds for LSN: \"%lu\" using empty LSNTimeStream.",
+			 target_lsn);
+		return;
+	}
+
+	/*
+	 * If the target_lsn is older than the stream, the oldest member in the
+	 * stream is our upper bound.
+	 */
+	if (target_lsn <= stream->data[0].lsn)
+	{
+		*upper = stream->data[0];
+		if (target_lsn == stream->data[0].lsn)
+			*lower = stream->data[0];
+		return;
+	}
+
+	/*
+	 * Loop through the stream and stop at the first LSNTime newer than or
+	 * equal to our target time. Skip the first LSNTime, as we know it is
+	 * older than our target time.
+	 */
+	for (size_t i = 1; i < stream->length; i++)
+	{
+		if (target_lsn == stream->data[i].lsn)
+		{
+			*lower = stream->data[i - 1];
+			*upper = stream->data[i];
+			return;
+		}
+
+		if (target_lsn < stream->data[i].lsn)
+		{
+			/* LSNs must not decrease on the stream. */
+			Assert(stream->data[i - 1].lsn <=
+				   stream->data[i].lsn);
+			*lower = stream->data[i - 1];
+			*upper = stream->data[i];
+			return;
+		}
+	}
+
+	/*
+	 * target_lsn is newer than the stream, so the newest member in the stream
+	 * is our lower bound.
+	 */
+	*lower = stream->data[stream->length - 1];
+}
+
+/*
+ * Try to find an upper and lower bound for the possible times covering the
+ * provided target_lsn. If the target_lsn doesn't fall on the provided
+ * LSNTimeStream, we compare the target_lsn to the current insert LSN and see
+ * if we can fill in a missing boundary. Note that we do not consult
+ * the current insert LSN if the target_lsn fell on the stream -- even if
+ * doing so might provide a tighter range.
+ */
+void
+time_bounds_for_lsn(const LSNTimeStream *stream, XLogRecPtr target_lsn,
+					LSNTime *lower, LSNTime *upper)
+{
+	TimestampTz current_time;
+	XLogRecPtr	current_lsn;
+
+	stream_get_bounds_for_lsn(stream, target_lsn, lower, upper);
+
+	/*
+	 * We found valid upper and lower bounds for target_lsn, so we're done.
+	 */
+	if (lower->time != INT64_MIN && upper->time != INT64_MAX)
+		return;
+
+	/*
+	 * The target_lsn was either off the stream or the stream has no members.
+	 * In either case, see if we can use the current time and LSN to provide
+	 * one (or both) of the bounds.
+	 */
+	current_time = GetCurrentTimestamp();
+	current_lsn = GetXLogInsertRecPtr();
+
+	if (lower->time == INT64_MIN && target_lsn >= current_lsn)
+		*lower = LSNTIME_INIT(current_lsn, current_time);
+
+	if (upper->time == INT64_MAX && target_lsn <= current_lsn)
+		*upper = LSNTIME_INIT(current_lsn, current_time);
+
+	Assert(upper->time >= lower->time);
+}
diff --git a/src/include/pgstat.h b/src/include/pgstat.h
index f63159c55ca..13856e2bef3 100644
--- a/src/include/pgstat.h
+++ b/src/include/pgstat.h
@@ -458,6 +458,45 @@ typedef struct PgStat_StatTabEntry
 	PgStat_Counter autoanalyze_count;
 } PgStat_StatTabEntry;
 
+/*
+ * The elements of an LSNTimeStream. For the LSNTimeStream to be meaningful,
+ * the lsn should be a consistent position in the WAL over time (e.g. the
+ * insert LSN at each time in the stream or the flush LSN at each time).
+ */
+typedef struct LSNTime
+{
+	TimestampTz time;
+	XLogRecPtr	lsn;
+} LSNTime;
+
+/*
+ * Convenience macro returning an LSNTime with the time and LSN set to the
+ * passed in values.
+ */
+#define LSNTIME_INIT(i_lsn, i_time) \
+	((LSNTime) { .lsn = (i_lsn), .time = (i_time) })
+
+#define LSNTIMESTREAM_VOLUME 64
+
+/*
+ * An LSN time stream is an array consisting of LSNTimes from least to most
+ * recent. The array is filled before any element is dropped. Once the
+ * LSNTimeStream length == volume (the array is full), an LSNTime is dropped,
+ * the subsequent LSNTimes are moved down by 1, and the new LSNTime is
+ * inserted at the tail.
+ *
+ * When dropping an LSNTime, we attempt to pick the member which would
+ * introduce the least error into the stream. See lsntime_to_drop() for more
+ * details.
+ *
+ * Use the stream for LSN <-> time conversions.
+ */
+typedef struct LSNTimeStream
+{
+	unsigned char length;
+	LSNTime		data[LSNTIMESTREAM_VOLUME];
+} LSNTimeStream;
+
 typedef struct PgStat_WalStats
 {
 	PgStat_Counter wal_records;
@@ -749,6 +788,12 @@ extern void pgstat_execute_transactional_drops(int ndrops, struct xl_xact_stats_
 
 extern void pgstat_report_wal(bool force);
 extern PgStat_WalStats *pgstat_fetch_stat_wal(void);
+extern void lsn_bounds_for_time(const LSNTimeStream *stream,
+								TimestampTz target_time,
+								LSNTime *lower, LSNTime *upper);
+extern void time_bounds_for_lsn(const LSNTimeStream *stream,
+								XLogRecPtr target_lsn,
+								LSNTime *lower, LSNTime *upper);
 
 
 /*
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 547d14b3e7c..c8d84122976 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -1587,6 +1587,8 @@ LogicalTapeSet
 LsnReadQueue
 LsnReadQueueNextFun
 LsnReadQueueNextStatus
+LSNTime
+LSNTimeStream
 LtreeGistOptions
 LtreeSignature
 MAGIC
-- 
2.34.1

�PNG


IHDR�
�5���9tEXtSoftwareMatplotlib version3.9.0, https://matplotlib.org/4H�	pHYsaa
�?�i>;IDATx���yxT����{&�$�d ��,����&n��"�E�m�E[����E�+�ntQ�}�7*Xl�"J�]�`!a�d!�d����DY$y&s���:�37s���s�y�eY�`N�
��(�6C
�
 ��P
l�`3@����f(�6C
�
 ��P
l�`3@����f(�6C
�
 ��P
l�`3@����f(�6C
�
 ��P
l�`3@����f(�6C
�
 ��P
l�`3@����f(�6C
�
 ��P
l�`3@����f(�6C
�
 ��P
l�`3@���L������WAA�����p8L�
�`Y�JJJ���,���ca�PPP���T�1�y���WJJ��FP/@tt����@111�����x<JMM���#
�8q�7&&�@3c����y���(�6C
�
 ��P
l�`3@����f(�6C
�
 ��P
h"����h��r�Q`s@���oi��/������R��,W>�e:l*h���3���������h��A�?~���<y���i��-[j��q***2��r�P������J����5v�g�R�1�v�0%%E�=����Y���W��+��u�]�M�6I����~��7O����rrrTPP��c�N
V�/�Z�t������{*��u�G��?/�����g8!��aY�m��ccc������nP\\�f���n�A��e�u��]��/�����z�Gn�[������i���f,�p��=��,KZ��K�1���<�����`S�$�C�ztl/
���p����w���������RYY�
�5k����J���}L�n����������u�^�<O�
����y�,K���:���$%�D��������*>��]�t��+4���*>Ve81�]P�
6�e��r�\����5g�]t�E*,,Txx�Z�jU��			*,,<��M�>]n��vKMMm�?
���V����|I�m��u��=�h���%;M������T��o�'�C���kW�]�V+W��=����'j�����z��MSqqq������i
�h��B.�TbL��w�?�c��az��^z����!���xu�_���QaqE'�u
W�N���o_M�>]YYY�������DUVV����u_TT����������������������[��r���
����/�������m.�UO���_���1h@A]��������o��
����k���u����4h� �	
�dSA��|}D�N�n�_���"�B4uDW}p�%�8��J����������������.BMh,��M��Q���������5KK�,����v�5i�$M�:U�������}���A���
`���y���=qN�����w��+��l������?-��.��{.�(WhHcD�Mm
�������i��}r��������u�UWI��~�i9�N�7N^�W#G����>k85 Xx*�4�����������q:4qp{]uQ�~5w�>��_3>�������e�oz�����<�
�y������zx�fuIh��S���p\��Y�����#�6�`i�����������k��������
�)X�U{����/��I������d}8�R���"��^]��F<�Tnf)S�
 
l��C�y�L-�C4��v
��������,��?�Jo�}���WWk��/���)cP?@���G���������V~2Lw_�Q!N���~��?��wV�3�4��@*�Th���C��Z��!E��������C���[��j���u��W*�`Y���h�(�4�7?���oi@�XuKl�z�sk����k�+"������K�������$�
 
���������w���������?���3�R]�����~�q�V}���j]��&���G
��|��HE�����=N��hcJk�W���&d�uT�������~��}�Y���F2!�P
h '�~����C�}�:�����^�1�������j��K�����\@���%�l�!9���i��H���ti�M��;��]�H�9rL_�\���V��*M��A@��u����v�"
����������t��9��/���'�h��{�2��(�\���j�c�I5+��P�f�Ez�GC�-1ZG��t���4��U�?\n:������x���M��vjk:��Nm�y�
��FvUx�SK�������>��j���
 ��,������������u�S�/��?�D;��X�O���W;�3m.����&@
�|�wT��y�
u���)����q-�����z)&"T��k�_������g:�pb���f%�UT��4���p���i������^I��-�\�SW�X��v4���y:T������$���+4���=sk��{������u�����g���r��	6@��;�����WV�[�)�L�iW]��ES�����r8j��������2&�P
8>��7V����`�����w8H��[�`i���������*8z�t<4
 �!g�~�9rL��0��J6�Q�k��x������o��������w��g4�9�pNL�2�_�"�B�i<��M�E���%���Ze�>���M��������t<�'
 �(�P��l; I�5;���N��h���A��u=���/����?��m���)c�
 ������eI����}���4���������4�{��|���x����'Z����x8@�AE�O�������6�$w�����z��>��vi��2�n���A��*��P@���7����*�k�+����c����5������������7V����r�pS��t8
 ����+�����f��ocsG���q�z�������<^���5���5*�T�����PO�����
qhB�T�q���m4�'�h���th��B
*G�V�1eL�PO'�~�3Iq�.�iODX�~6����7TY)n�TT��s6����������$@����J���+�������'���
���s�"�B�y�a���'��G�UY�7�P/�����*��%F�_zk�q^���IC3������.q������l���,��yGL��=
 g��[z}���u8����Rc��������z+�E���h������M*�V��g[@������{�L-]�sq;�q�����z���S/��>�dY�K��������-�M��%
 g�������}���+�l�f,�E����[��5@����{���|y�~���:X�5�V(�����cZ��HR��_\�a]��p�0}��9�?�h�S9��f�,�)c��3xse���4�C��$D��4��C������CuQR���W��w���>����L�z@N����7k��mo6L��������/Fu�+��e;j����[�NU��2��P
8��l.�����]�#�t������v��)�4�cUT�5}�]�������t��D
�4N��q��4��������m�7�'[���)wd�6x��g�M�
J\��)l+*����
q:t���m*�C�������zj�6�|dW����S81��U����4��~��]�>���A��l���[���`�_/
 �0���*�V�C\
���t��Q
8�e���o6��"8Q
8����hKa�"���7�t�QP
8���_��n'wd��4@��8}�t���_��������1c�u��:������p8�lw�}�����x5�>I�����0''G�'O��+�h�"UUUi��*+�������}����v���h(1��wV���g���V���m:�h�v������/+>>^k����a�j�GEE)11���
��o�������\��~Sqq�Z����u����j���z���i����������z��x�l������*(�P��0]�+�t�Q����~��L��!C��g����o�����+99Y�����>��[�����;��L�>]�<�HS�4�����M������i����,�2���s�=�?��-[����_���G��+���;��c�o���z��zko{<������X111����v,�eO,��!�<p���D���F��x�v�m���#���{�>��-]����O����%����r��r5JN�9o�����K�����,�w�}�3g��,Y�����>g������$���������{$��/�#h����5k�,�������Vaa�$��v+22R;w���Y�t�5��M�6Z�~����~
6L��������u*>V������K��8@��8s�LI5�=����^�w����p}����1c��������q���W�����SN��{kv�B���{�x�k[RSS����Di�h]�Q��S���&�c�_��m�
��N��]���6-���A
����J�s]�$����P
�4{�y���()F}�Z��4)
 �v�~��������pp�����e;j��rE�Bu]�d�q�&G
���u��MQTx�N�
�`+{�����$q�����7W��oI�;�Q�����FP
�QY��[��$I�3��lc��}:XZ����_�`:``'�~�y@��B�
�}��`_��h��#
q:t��4�q�(�[81�7�G�b"�
���^IE��|�W�t���f�
�zs����J�:��������Q
A��,������Y��(�� �2����/UTx�����t  P
A����c.n���0�i��@
���
-�X(I�-��?�(������|U�-�Ko���cL�
��}~�Zy|��A��
'����_�W��BmZ�������
�J'V����\�!����:;�j���r8�[�Y��&
  �������+��+�u��4@���Jye��]�/I�m �B
�y�
TRQ���(
�g:�(���aY�^=���m��t��/p*@@�X�T�
<
uj|�T�q��E
�����LV������
��*���}�X�8
  (��:_��~�j�VV��t �Q
���o���5�o�.���?�3��������b"B5:+�t �Q
�����~�/U�����
���.�G[�K�ne�_�^(��fm��y�,���m�!���8@�@
4[�j��^���������
u��RI�]�-�t�����+�2 M�!|�
���@����Xk�>�P�C7`�_�\P
���+�$IW�LT|t��4@�B
4;��*��r����?�
 ��yo����KBK
��5hv��N�>]���Wtt����5f�m����c***4y�d�i�F-[���q�TTTd(1�>,�����u���0''G�'O��+�h�"UUUi��*++�}�����y����w�UNN�


4v�X��
g�|�!�<P��!sq;�q�f)�t���`��:�_~�e���k��56l������/h��Y���+$I/����w��+Vh���&b�������i���0�i��)hG����X����5kTUU�����>�[�nJKK�����d�Yaq�n�9U������
���
<�����)S4d����S�TXX���p�j���cTXXx���z��z���=O�e|�������4 #V]�M�
�-[�N�<Y7n�[o�uA�3}�t����-5��G
��T��z��������0A_���^}���������R�?11Q���:z�h��)11���5m�4�n����p�E�������-]������'h�eY���{5g�}��G����s��}�������u����4h��S����RLLL�
�4^[^s���R�__@��s'O��Y�f����Wttt�y}n�[���r���4i��N����X���������A�����%Z������
i���^���3gJ�.���:�_z�%�q�����~ZN�S���������#����6qR���X�wx�%��4�h��eY�C4W�Gn�[����FR����G��[��&
�%��LGB3��w���-P��Zm[hH����A�X�e����%I�f���d�_�!P

���#�RX��0���e�U��P

���/��J�;�u��B
���^�{C�^��4,
   ��:_�>��R[�W��t �P

�����
��p�l���G��UT����d:t(��������?&�KUDX��4@��������������4<
  ��Z�'��.���6-L�
�0*�|z{u�$.�0��~���W�]�H]�-�t hQ

����d�)�u�FC
�
{��6���B��?��������W���tN7
 ����*��n�$.��`��/�����n������t �Q
F��V�����������Q
F}���r���+Tcz�3�
 ���V��$���N-\�f�6A
����m.�$���@���yse���4�C�:'D���`De�_o�:��o{�a������B(�*.��=L�
l�0���5S��< Ma!|
M�q�&���D+s+����X�hj@@�;1��U����4��
 �I�z��������/�	@@����^�z��!��wlc:`K@@����������)@@�Y�����(2,Dc������d^;>�7��d�#��
��h�K*�`�>I���F
4�wV���g�OZ+�Hv������}~�Z�'��_�@@
4����WAq�b[�kT�$�q�����?&�KUDX��4(��F�{�L�l?(�C�5;�t���G�.����(�iH@@#:V���k�H�Y�@`����*>V���H
�g:��(��Fsb��[���d�_ PP
�b]�Q��S��P�&�K5�I��.]�T�G�Vrr�����[��;��C���v��W�	A���/��������8Y����2eee��g�9�c���j����v{��7�0!�#e����@�t+
'�t��2j�(�5���q�\JLLl�D`��������1�8���8�!hG�c��%���W��]u�=����C�#
@���[z}e��������� ����\}��;v�222�s�N������Q��|�r���z�"��+��[{���4U\h6>�qP_*WtD���;�t�`�x�M7����W/eff�c��Z�d�����S>g���z��G�*"4K�-����o���m�54[>Y���m[�������6m����k����&L�o��r}��H�t+
����g�:tHIII�}������j�T����y���4�Su�ki:���XZZZg4/77Wk��Ull�bcc��#�h��qJLL���;����\�:u���#
����[����j����/����^�Z�_~y���S�J�&N���3gj���z��Wt��Q%''k�����~���u��R	1.
��`:�3�x�e�������p��&L������HWh��������>�V�>�P�C7
`�_ �Q
������J��0���P
���Js��+��_���� s����J�:��������
 ��UT����\I��4'@�y{b�V�>T��h���ig:�z����]����5�����0���p�J�����u�,������[��H�
p���W�?|L�ZE��k����Q
�$g�
�Z�'Iz|<�~�������*=8{�$����5�c[���
 ����I��
e�m���f:��D
�����z���r:�'�g)2<�t$��8�C�^=4g�$���vT����
�@�Y����l���JuK�����MGp�(��3���-�T�P�CON��+�C�@sG
�V��B���Q���+;�G��p"
�8%����?��SQ��������HpJo����������W,����������%I?�U���
'��(��:�~K?��Ne�>
h�;�d����Q
u���n��uXQ�!z||�B���40
 �������-��_^�]�mZN�1P
��j�_?}g���~]���n�N3	@#�$I[�Kk��*:"T�)��C�@����>�f|�M����Jni8��D
����k�;�T��t�E	����Hl�/m�W�<j�G����_�(�`ck����%;%I�{}/�E�'�(�`SU>������-}7+Y��J2	@��M=�p�v(S\�K�����hB@������Os%I��VQ��
hJ@��2o���N�%��?U�w�7	@���<����������C�v7�
@���m���<I���3f8(�`��Uzp�zI���kp���
0�6���M*�T(�m=xu7�qD
X��P�}�WN����,E����� 
 �C�^=4g�$���vT����
0�A��,=4g��U�kB���l:�@
� ��uZ��P�N����%W(�~
P
 hy*���%I?���z�sN PP
 Y����^��je��u�eMG@(���^��%[(<��'�g),��{��'�������%I?�U��
'h��.]�T�G�Vrr�����[�~������FIII��������}�v3a
�����~6{��*}������a:�����LYYYz��gNy���G����s�=��+W�E�9r�***�8)4�W����]��'�g)��0	@
5���5J�F�:�}�ei�����~����N�����*!!As���M7���Q
�A�<P���o�$����Jo��p"�*hG�$77W���>|x�>�����l-_�����z��x<u6�>�xw���~]���n�N3	@�e
,,,�$%$$�����P{��L�>]n��vKMMm��P_[�K_�UtD��0.S�~
��-���6m����k���|��@_��h���$I����V��
t�,���������:����j�;������:�TY���w���g���4�O;��4�,�JLL����k�y<�\�R�
2���_>����y�:*L�^��C��%h�.--��;jo���j������UZZ��L����������222��_�Z���3f���p����KvJ����^��vN����z�j]~�����N�*I�8q�^~�e���?WYY�~������:t�,X���S�
��*�|��;k��[�nV����d:�f�aY�e:Ds��x�v�U\\������?���[���h��?L���MG�
��mz 4g+w���J��0���9�@3R������������n	g|��G����S�V���w������@3�����X�'Iz��LEG�N���@3P|�J�^/I�cp{
���p"���G�mR��Bm[���������@�[��P�}�WN����LE�������@;T��Cs6H�~0�����N P
 @Y��_���������R�_��t$A�
���
4c�B�=5��\���0(���<��������������
&@0�e������Z�)n�����#
2@0o�����������G5����
�������%I?�U��
'�(� �~K?��Ne�>�o�Zw
�0	@��@�xe�n��uX�a!zb|�B���)
 ��J���-��_^�]�mZN �Q
��j�_��N�j�.��V�e��� �Q
���?��/��*��?������_��m)���E�$I��n%��4��P
���j����NU>K��'h\�v�#
�	
 ����k�>�ZG����=9���P
��u�G���������������	�XE�OS�Y+�����d]��d:��@{b�V�<P��h���w{����(���V�:�>��$=6��Z�7��Q
���y����u�,iB�]�=�t$6E
�&����R��cj�*R���E���1
 4��m���<I��7d*:"�p"vF
�FV|�J�^/I�cp{
���p"vG
�F���M*�T(�m=xu7�q��i��B���^9��3b:P
��*���9$I?�Q}�c
'�@h�e�Ws7�`i��$���Wu6	jQ
��s]��o,T����&��+�C�X��B�y�$��+:�g;��DP�eYz��U|�J������;���B
����|-�z@��N=9!Ka!|�<|2
@�?\��}�Y����.��m8���o�g������~��5ih����(��^Y�[+vVdX������t$8-
 \��J���-��_^�M���0�������������������t����(�p
��d���;�hW��pC������>���r8u�n�������R�����I�~3�"�ki8�O������C~�a���P��%������o�S��������o��HPo�o;���JLL4@3����k�>�ZG������pp�@�a�C���}�v%''�C����[���w��z�^y<�:�Y�T�,�)I���^���0����`vv�^~�e-X�@3g�Tnn�.����������O�����RSS�81�*�|������[���k3�LG�s��,�2"P=zT���z���4i��o���z��zko{<������X111M�!������'���v�?S��u�p���#��#��m��o��x�V�Z�K�.��c�)�w�\r�\M�
@��<���oY�$����(�-[����R���SII�
PW��Z��N�%M���+�'�������PNN�v����>�L�_�BBBt��7�� �<����w�\�ZE�����t� �>�g��|��:t�����4t�P�X�Bqqq��
 9����53���LEG�N������2
@�+>V�g��$M��!��N����
�l��I��
�o�G�T$��@
��X��P�}�WN����,E����	� B
�S8T��Cs6H��?�����N
����H����NK+�%�����t$hP����|}D/.��������P�CO��������AQ
�Z�������\��?Z�H�6����+�m.4
 [*.�������g�UP\!I
q�����kh��'�s}P�@
`+��������f��+}��6-�u��t�60]q���
 �Q
=���|�!��,W����e�������d����9���P
-o�O������r�y��v��]�4ih
��F��`B0� �*����yzm��:P��$E�9uC��9$C�ZNfQ
�mE%zqY��|�W�j�$)1&B���[��UT���(��5��������\}��`����&
��5�����p2
 �f�X�O�}�G/}�[;��J��i�E��tI������>8
 �f��S�W�����y:R^%Ij�
��~��sH{��FN���Y���X/,���T����%�u���^7�OUtD����|P
,����_��e��<�p��~��5ih�F�HT����p�(�N��Z�����������%I�N�����IC3����l@h�(���#�z���zkU�J*�%I��0�����
JW�;�pB@�����^\���
�������m�94C���ST8U���T`D�������\��?Z�H�6�44C�u������QP
4���*��*O�~�[�����������f�{R����(��D��2��i�f����J�$�M�p�60]�
LW\��pB�
 �FcY���:���j����jN�S��h�5$C�������!
��(�����y����e����S����q�4���tj�2m`@�9T��+�����u��+I�sj\��9$C��[N�(������,Ws��+o�_����
N�-��**�pB��(���eY��v@/,��'����Lqk��]�+Ia!N�	
�C
pN*�|z���z��\��_*Ir:�%j�%������ �Q
��~O�^]���X����WI�Z�B5�_���^��Q�����6�-��r���U�j�qIi�;����Sf8!�\Q
|��o�������\}�{�v����44C#z$*�e�����U��������g����rIR���kz%i��e��2� (���H�^�l��Z����jI�;2L7H����JrGNhH@���|}D/.���M���k���������q}�)*��F|�6S��k��B��,Wk�������&
��e]����>j@ �Y��#�U�;\�������T�W����B���u��u��uO�1��T(�@3���i��c�;\�=��^�vL���U����s���m�u��t�E���D
�eY:P�U��r�>vR�+W��rz*dYg~�����F)%6R;��w���4@��
�X�O�Gj
���.�x�;V�;��[��(56Ji'�6Q�������
��M����������?(����N�����S�RZ��vl�p���h ����F�����=G������GG�*�MM�K��Rj����%��Tx����$�`G
��������7
�o.�<��C��k���Qu���Q��h@�$����5z�|�s����g���uTX����.56JI���0�0����g����?���Beee�/��`:I��������������������RZG�)x���F*:�Q<@��u
|���5u�T=��s�����34r�Hm��U������<|s������;T��#5���Y����Ki���(xQJ��P�d�9�e�m�������������$���+55U��w�~��_����Gn�[�����i��(X�%�Us���o�g���?���_�}��'��,���������>��~�I�9��'=����}}�����*�_���3N||2W������(��@p����a�o���J�Y�F��M���t:5|�p-_��`2i��}��������R�������o���2W������\�jK�7,N����[�E��2`k�-����SBBB��			��e�)���z���w�6���(���W���4�k_�C
q:�t8�t��t(��P��������o'?����||����sO������p(�)9�5Y��#jG�RZ3�1gb�x>�O��Gy���a]�Z��tr���K�I��[�t��9�t�[��T���C��
$l[��m�����_TT����S>g��i�:uj�m��������7�����n���$�NJ��}�j������~�/^�A���9.�K111u6����#��4u�TM�8Q�����
4c������;�4
�����x��:p��~������P�{����ua@0��<��y�h~����9�vE
�
 ��P
l�`3@����f(�6c���.��ET<��$��N|o�y14
�())�$���N�UII��n��F�����*((Ptt�G�����Qjj����m�Na}�^��U��^��U��^�_c�W�e���D���r:�y6#���t*%%�Q���>$�����x������x������������	���6F
�
`�r�\��o+��e:J����?������?������?����E 6� ��P
l�`3@���g�yF���WDD������������.]���G+99Y�Cs��5) M�>]���Wtt����5f�m���t��5s�Leff�N>;h� ��?�t����c���ph��)����~X�����[7�����{u�m��M�6���T�^��z�j���
0������:u�~�����/�PVV�F�������p�������g�y�t��������'k��Z�h����4b�������RRR��c�i��5Z�z����
]w�u��i��h
k��U�������L�QZ�=�o���m��e�#�#G�h��!
�����y�f=���j����hA�i`Lvv����������j�NMM�}���_����.���9s�h��1���(>>^9996l��8�Bll��qM�4�t��SZZ�>}���g����{���[3f�0+�<����;w���]k:J���/~�O?�T�|���(A��RYY�5k�h������N������L�`R\\,�����|>��z�-���i��A�����'��k�����S��}������C�z�����3) ����T�~�4~�x������/����w���0�<xP>�O			u�'$$����P*���)S�h��!�����8
k��
j���\.����n��3G]t��X
�����_|�������������/k���9s�rssu�%�����t���k�.��9S�;w���u�=���?��^y����J��������q�F�=:��]�j���*..����5q�D���PO�������'Z�h�"""L�	x�F���933S���JOO�;����������_?=������/�X7n�s�=��'N<
 m��UHH������/**Rbb��T��{�>��}���JII1'�����S�N�����O����,��O2+��Y�F���W�>}���P�������BCC���LGh�Z�R�.]�c��QNRR������{w�70
`	W��}�x���}~�_�/��#�7��t���j��9�������a:R������zM�(W^y�6l���k��n���������k�*$$�t��VZZ��;w*))�t��3d��oMU�m�6���J�8`�N���'�_�~0`�f�����2�y��������:�{������k���4������5k�,��������=���v+22�p��3m�4�5Jiii*))��Y��d�-\��t�����H[�h�6m�p~�)<��=z����UPP�����
		��7�l:Z�����5x�`=����0a�>��s=���z���MG.�_��+--�
�`�X��t�����[���M�8�t��r��H���K/������.+==�
�����+������c:V�p���Z?��OL�H7�x����d���[����n��Fk���c�y��Y={��\.���[7����7)�0 ��p ��P
l�`3@����f(�6C
�
 ��P
l�`3@����f(�6C
�
 ��P
l�`3@����f(�6C
�
 ��P
l�`3@����f(�6��
�f}�4���IEND�B`�

�PNG


IHDR�
�5���9tEXtSoftwareMatplotlib version3.9.0, https://matplotlib.org/4H�	pHYsaa
�?�iUIDATx���yX�u����9�
�
�����IT�TSYM�Z�k���X�e�T������4�L6�{S��i��V����n�D�s>�?�z�Q���
�����uy��}����p^����e�1����:j��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<��P
<���Z�.s�\:r��5j$///���
0�(??_������(����#����:�T�V���a	
�Eh�����Y�T���Pdd��u�Q/���}���(��1���[���7��x
 ���x
 ���x
 ���x
 ���x
 ����Z�cu�z������u�]w�i��
P�=������c4a��h�B


JHH���������6l��������O�O�.7�i�&���_�������K/���,,P�������=zh��%��W$�ys5���u�D��Q��*-��N����_.???}����m�^}�U5n��=��K/�����;�������A�JLLTQQ�{f��a��u��/_�E�i��5z��������zEGG+55U/����}�Y�������k�j��!���������j�����eK����c���R���w�jGV��|���H���B���3W\q���w�\&<<������m����n��9s�c���m��d���;��_|a��������1�L�>�4n���{�N�:��4�$%%�{���8��?���Y�'//�H2yyy���tQ�yhv����D�[d����M^aI�?���T�;�.T��}u�w(44T}���{�����o�>eee)!!��-88XqqqJII�$���($$D}��u�$$$���[���w�\y����l����D���S�N�r���y���}��d����b9�r7p�vg���i�j��#�����I]4����Y�^���w�^��1C:t��e�4b�=������%IYYY�����r�s����Rhhh�����j��I��s����k3?��,?7y�d�o�����-
������y����sZaAv�}�R���������Vo�V��\.�����_|Q���Om��E�����^�Oe����k��1�����*.s��E���u$I��o�7���f
�'�����-Z�k����u��E�������pIRvvv����l����p�����_VV��'O��9�1~��6������sv�]AAA�n���<�;�Iq����i��1��WC��^~����sg�m�v�Rtt�$�M�6
��+�����_���xIR||�rss�����Y�r�\.�����3k��Qii�{f�������������r�sv���T$�z+wd��o�M������Dc��$o>��1UyF��
����y��������Y�L``������3S�L1!!!�?�����i����[L�6mLaa�{��n0}��1���7�|������2d�{nn�	3w�}���e��;w�	4����3�~�����5������}��8q����3�7o�T���YDT\��e^^��}���S�1�N����~S��c>��s��{wc��M�������[n���2�<��	3v��\{��f����fN�8a�b6lh�������k�����l���\q��n���-[�)S��"����M����f3��u3�/�t���_ *&�Qd����.>�l�J�,����1^�p���p8���<��_�a�I������b�|4�����W�eyx�����
�2�������Kw��2��P3��Q��FVG�x@P��
K5v�F}�����1�w�^���mT���?P�����Yi:p��l>��pSW
���;�"@Pe�}��g��U%e.�	���b��U����3@p�
K����-Z�zH�tM�P�6��Bm'��P
�E�w�@#>J���|y{I�]�I#�j'o~�s�E
���G5��M:]\�f
mzkH]�����p@Pi�N��|�C�f�$�_�&z{h��[�A
���W���iJ=pJ���+�jlb'��x[�E
����zdn�N�����^�����[�D
��rM�j�^��.#um�w�(�i���P
�o:UP���2�z�1I��~��xS7���X��~Uz�)%�J���"��y���=���VV��E��_0���)���m*u�i�@����K� ���
P
@9���4����|�I��=����{������PU(��mWv�F|������K�o��?^�Z^^\��>�I�g��5���*,u*<�_���Qlt�c�P
�pE�N=�h�f���$���Lo���
�'Cu����<������p����������� o>���(�x���5f�F���q��^�[��ju,�
 ����k�wi��$I�#C4mX�Z�X�5����/��s��n�II������|c�|�-N��D
�C��{B�IWN~��|��?���{FX�P�c����zi�N9]F�j��X�mhu4X�@=�WX��l��m���[����vW��
�������r8O#g�)���|�����4�_$W�����y����[UR�R��
�1,V=Z[
��z�����?����$]�9T�
���@?���6�PO�=vZ#g�iGV���������+����z�g(��K6�o���25kh��C�(�]S�c���P��:]������}��~m�h��>

��8j3
 u���B������$I^�N�_�Q�>\���@���czdn�N�����^�[�u
�:�
 u��e���=zc�.#uo��Cc�4��h�C(��'J4z^���:&I�/Ro�&?�����P�g�R��4�+������C�meu,�Q@j1c�>\�_/,��R�Q�f
4��u�:�0
 ����2=��MZ���$������=����z��P
��ve����R��X�|��������[����z��Q
�e>M?�?�E��N�����1��nlu,�#@j��R���h�f���$���Lo���
�'C}C
�8x��F�J���y���������|���U�����-[c�g�QT���~z��>��cs�c��`�2�K�.���~�$��
���1�	�8��*�Z���>+//�r���;��)99YM�6U��
u���+;;��1233������@���j���*+++7�j�*����n��}���9s�/�L�6M�[���������a��r�+�����_�����]������=O�C���(I��u���G��o������G����h���:r��n��6�~�����$���h������5s�LM�0�=�o�>%%%����VFF�F�����_��-s���7Oc���������^�z)11Q999�@uY������F���T������7u����_��s3Uh����W�^�����k��������o�n$���c�1K�,1���&++�=3c�d����1�<���[�n��=x�`�������_?������t:MDD��<yr��TD^^��d���*���r�\f��=����&z�"s�k����|�cy^�����j���[j����
���OeOMMUii����;wVTT�RRR$I)))��������3���r8��u�{���8;s�%%%JMM-7�������LE�P��
K�?�L��/v��2��OK}�|��5ohu4x�*=	$..N3g�T�N�t��QM�4I�����-[���%������r�	SVV�$)++�\�;������q8*,,��S��t:�9�c��1���\���U\\���p8��;���p�F�J������x����iH�H��
�Ti
0`���={�T\\����5�|��oj�<y�&M�du@a����j���*)s)�I���U�V�VG�����6
		Q���g�������D����f���.I
����g��o&((H


j���|||�9��c�/���?^yyy����+�
�8�%N=�`���Y%e.%t	��Q�)����>}Z?���Z�h���X���i����;w�Tff����%I�����ys��u�/_��� u���=��c��9{������r3.�K+V�p�T$����v��
�s{����i����������Y���W��~VG~T�g�<��cf��Uf��}��o�5			�Y�f&''�c��>h������+���o���M||���eee�{������7f����y��f������{����@3v�X�}�v3m�4���c�.]���;w����f���f��m��0!!!��.>_���,"��-�x�t���D�[db�[nR~8nu$����Ti
<x�i�����l�e��f���f��=�����f����q��&00��z����������~3`�`�5kf{�1SZZZn����2�{�66���m��|�������o���(c��L�~���u����H���/���R�yv�=n����zg���+�:���oc��1��� �.�����`����q0x�#��J�����\I�����c�u��?��6���k
pQ��:���2t��DA��zmPo%t
;�
Q
�N���+w���e���e���UT�@��
�E
��N������z�qI���(M�}W���X��
 ���yJ���t4�H�~�z���-�����J�P
��\�_/,��2�Q�f
4��Xu
odu4��(��G~Q����f-�|T������z{O5��2�������Y��(M{����KO��E�/k-///��
����$�����f������b���X�E��3E�NM�|��l��$���Lo��GM�,NT
 ?�y��F�J��#yyI����Q����7�������o��c�3�(*S�6�ygo�����X@��<^���W���wV� I��
���1�	�8P=(����(��9�����$������:���mq2��P
+��zhN���.VC��^�CO�������jG
x���ok���e;�2R��F�>,Fm�7�:P#(���w�T�-����H�n�i��P����d@��<��Cy1+U�N�������M�/����8@@�g���
���p�J�.E5	��a1��2��h�%(��z�LI���t�>I?,I��k�^�����,NX���~8vZ#>J�������������m�����m:�qoRA�S��5uH��mju,�V����2�^\�]3���$]�����G����
�"@@�q8�P����q0W�4�w�4��������OQ
���]�4zn�N�)U���^�[�v	�:P+Q
u��e����z{�n#�h���b�$��h@�E
�Y'Nk��}���$iX\���}W��qU��P
uR���J���,G��|��m�uk�VV��
 �N1������%�U�2j�����+V�Y
�3(��:#��T���IK6gI�~������S
���
���@��#���i����x�����'>��z���>N=��?���R�"��5mX��D5�:PgQ
�VQ�S�.�����$]�����[��,N�m@@�t�D�F�J��#yyI�&t��������|��E
�:_n��c6*��LM����}tE�fV��
 ��(s���������������:��ZX��_(��Z!�Q�Q���a�II��W���
����mq2���,����zxN���.VC��^�CO
����X@�E
X��2������N���9��f��6�X
��(�K��)����rG�$�����-�`��8P�Q
5n��\����C�
e���s�t��K"��x
 ��c4k}����6�8]�n���b�-"��h�G�j���2�����,��$���az��^
��8�y(��j�'��F|���9�����'o�������W��@
T�����o���B�5uh���ibu,��Q
�����o��)$I�m���!}�����d����O�2E^^^=z�{[QQ������iS5l�P��~�����=.33SIII
Thh�������r3�V�RLL��v���o��3g����M����[���_qqq��aC����0�s5�o)���|u;���~�?������w��o��z��Yn���>��?�\,����u���v�m��N�SIII*))���k���j����0a�{f��}JJJ��W_����=Z����-[���7o�����'*--M�z�Rbb�rrr*�paV��Q�[_+�`�������Wc;��K�
���b����C�f�������2�<��1����\���g,X����}��dRRR�1�,Y��x{{���,���3LPP�)..6���O�n���{������D��~�����d�}��i"""����+��"����$���W��@}U�t�W��iZ?��D�[dnz�k�y���X�/��mL��w,99YIIIJHH(�=55U�����w��YQQQJII�$����G�
s�$&&��ph������;11�}�����������VBB�{�"Y����X���
 �8]������V��1�]�Fi����lhu4�P�'���;Wiii����~�/++K6�M!!!�����)++�=���wv��}�5�p8TXX�S�N��t�sf���r.�'O��I�~u?x��'�<+]Y�"��h�m=4�OK�c
�
U������#�h��Y�������*���W^^��v��A�#
�e�1z�����u�r�]�Z8�r�PT�;�������QLL�{�����5k4u�T-[�L%%%���-��[vv����%I����8[����?��������


R@@�|||���s����|Y��n��n�6�/*�o�[~����^�r[5���������
���k�y�fedd�o}����a��������+����s�233/I�����������|�r�k���������c�l6�����q�\Z�b�{&66��Y����C7O�V_l������rK7�ugo�P�T���F��{����5h�@M�6uo����4f�5i�DAAAz����K/�T�t����k��������K/)++KO?��������=����:u��x�	������+5�|-^����c��������o_���Oo���


t���J�������K�?��?���2�Z�h�����:�J������������������b%&&j�����>>>Z�h�F����x5h�@���_���L�6m�x�b=���z��7��U+����JLLt�<X����	������{k����N9_��)*u���[5�����w����A������d.��1�X��r8
V^^������������(M��:��%�I����������h����k
~���Yz|�F���i����������X.��N�^^�S���+I��XS��(<�~��/��P
�d;����tm�R�t�m4n@g�q-_������p\�I���%jd���w��
�[X@��r�X��^�r�\F��H3��U�f
���P
����)����r��?����Vzn`w���X�@u���t(W#>J���B�}���-�5��H�c
�f@�@�}�>S�}�M%N���j��u��:�@
SP\��>���2�H�����;z)����dj
<���|��(M�sN���KO��Y��o#//��
x
 x�����o���B�5mX�.i���X,@
�z����o�?SH�.k�To��G��-N�*@���:�����x0W���5�5:��|����d@������G�e(�L���������s����@�g�.�7��Ko��#I��*X����U�@��
�-(�P�?]�G����='$I��G���.��rU������O*yv���
��h�m=tK��V�PQ
��3�������/v��2j�P3���CX#��
��(�P�9�J5v�F-��-I��W�&��C
�|y���

u��#�����'�����gn����������@4���z��-*.s�eH���Q���c
�#(�P��:5�?[4��C���;5�k�z�q����%@�#�/��Yi�~�!o/���;i�U���U=T���[�4v�F���YC�����.k���X�(
 �b�N�^Z�C�}�O�tI��z{H����-N�.�@-��W�Q�����S���l�������mq2uj�o��#s�u�t��}���tC�p�c
�'(�P��\F�W��k�w�e�.-�4cX�Z7k`u4�j�S%zt~�V�<&I�7R�n�&?��
�o(�Pd�U��4�-���[�
��A}#��������1�h�
�e�6�:�Z7
��a��du4�,RP\���l���G$I7t�Kw�T������w@����|����=9�����'t�}W���W�P�(�P���qXO�{�
K�
�k���m���X<jHq�S�/���; I��}S�yg5kh�8OC
�p��%�N��Cy����i�G:����|
�<
 T��;������+,UH��^�[Ww
�:F
�j�t��|��~�G��+2D����eH���x:
 T�c��zdn���pB�4<>ZN�"�/W�`=
 T�
�Nj��4��+���)�����"��n@�"����^�u�N9]FBj�]1j���hP�@^a��.��/�eK�������P��/�j�2
�E�z$O#g����3��xk�M]5,.��z��(�p�}��g��U%e.�	���b��U����7yW��f����={*((HAAA����_|��_TT���d5m�T
6��������r����TRR���c��������U�#������k�����2m�4�n�Z��������
���H�5�%N�]�Q���Y%e.]�9T�����N����U+M�2E�������u�5���[n���[%I�>��>��s-X�@�W���#Gt�m���t:�������]�V~��f���	&�g������$]}���������u���k��e��y��i��1�8q������W/%&&*''�=s�,�k�/�������C����&v����UH���hP1��5n������&77�������m���H2)))�c�,Yb���MVV�{f��&((�c�y��'L�n��=����Mbb��~�~�Lrr�����4f����S�,���g$����
?@��d��m�R=n��}�K���cVGPI�~S���������sUPP���x������T			����;+**J)))�������Caaa����D9���)))��qv��1JJJ���Zn���[			���d
��*u����m1+M�����u-~��.k���hPiU~�������"5l�P�~���v�����l6�����SVV�$)++�\�;������q8*,,��S��t:�9�c��1���\���U\\���p8���
�>��+R��4�8%I���m56��|}����P���v��I���������k���U�4��<y�&M�du5�������t�((Q#_�rG/%v�:\�*����fS������'�W�^z��7�����������Vx��_L���q&�����	

R@@��5k&�s�����r.���W^^��v�������s\.��V����X�%��"H�����^���/\.����+???�X���o������T||�$)>>^�7o.w�������]��g~z��3g�a����ri�����d9����7go��S%�w�wzm�.#
��OF^���
��U�J??~����(���k���Z�j��-[���`�w�}3f��4i��� =��C������^*I������kW�}��z���������~Z��������|PS�N�O<�?���Z�r��������s�3F��W��}��_?���*((����+I��3�g�R��4�+���[/��C�meu,�ZUyJ���Gml6�i������k��_~��_XXhF�i7nl����j�=Z����70


�Y�f���3����f���+��woc��L��m�|��,o������26�������[�����d9N#���ef~�����b=n�����f��m����xc��%��r8
V^^u���2��d�>�xD�4�{�����
���8����7���ve�k�G���X�|��4��.�������eu4�6@������f�:��i��(6������Q
x��R��[�M��gJ��h�Lo��[��-N5���<yF#g�i��<yyI]�A�\�A>�|��sP
x��;������+,UH����[��ju,�q@�^������K���A��+2D����eH����@����b=<']){OH���e������[�B�Z�������F�NSN~��|4�����W����r@��1F�}�W]�SN�Q����>,V�CZ
j
 �z%��Tcl����%I{G���z(���;8�����-��4rV�2O����[o��������@�g�������lUI�K�h��X�hlu4��(��������}�zH�tm�P�:��Bm'������{��F�J���|y{I�'v��W��7W���D
P'-�|TO|�I������]o���vM��u@�R�ti�;��o�I���i��C�(4���dPwP
�G�
5jv�R��$����{}'��pU�
 �:��������,(Q#_�zG/]�-��XP'Q
�j.���+����d��-"H3��*�i��������N�h����uL�4�_�&��M�~>'����VJ�<��Yi:�W$?o=?������XP/P
�*�}�v�^X�]�N�6�h�]1�du4�7(�j���ez����h�QI��=����{�������~��ve����R��X�|��������[����z@U��������O��������:4F�������e�J����m��>S���C3�1���6�[��7
 K<yF#g�i��<yyI_�A_�A>�|������w[�������L�����}tU��V��A
Pc��.��|�f��A��'*D���("$��d�Y(�jDN~����u{OJ�������"�������P
T��{Oh��t�/V�������}��c
����6��m�^��l��.��a
5��X�k���h��(��E^a���Q���-I��OK=kw���V�+1�*��p�F�J������x����iH�H��
�@�1�h�w5q�V����$@����G�`��
~��J�8��g��I�aIRB�P�zGo�Y��s@m����Q�vf���Kz���z�[ysU��(�.��MG5���t��L��5uh]������������4����������6M���>

��6��(�*�Hn��g�)=3W�4�w���u���U=�.���5��i���,(Q���^�[	]����
 �
q���^�[o��-c��-�4}h���Z
PI@�u��D��M����K���Ei��������d�A
���2O)yV������[/��C����:�"P
��1F3�������e��Y��+V��Y
p�������'��K.Q�F���j����f��������M��a���������]n&33SIII
Thh�������r3�V�RLL��v���o��3g�"��i���uk���+..N6l�t���j��tM�|��\FI=[h�CWP������z�j%''k��uZ�|�JKKu�������=�������?���z�j9rD��v�{���TRR�JJJ�v�Z}����9s�&L�����o����t��W+##C�G������e���g����1c�h���JKKS�^��������
g
<��,�n���o>*?/={SWM�G
�|`���F999F�Y�z�1����\���g,X����}��dRRR�1�,Y��x{{���,���3LPP�)..6���O�n���{������D��~�����d�}��i"""����+��|����$���W�y���w�A���%&z�"��M���VG�*���1��S[���$IM�4�$������T			����;+**J)))�������Caa��s��p8�u�V��O�qv��1JJJ���Zn���[			���d����b9�r7�>(*uj�'�5f�F����C3-z��b�[
P
���\.�=Z�_~��w�.I�����fSHHH����0eee�g~Z���?���f�
u��q9��s������s�'OVpp��Y��
���<qF��X�92��%=��Q3���&
lVGT�j+������e����[]OQ������<�����VG.��m����_k���4�����G:�����h�jT-��=j�(-Z�Hk��Q�V�������URR����r��egg+<<�=���u��������������� ���G>>>����1�����v��v{%~'������+_��;��$�D�h��E�X�P��@c�F��O?�T+W�T�6m���������V�X���s�Neff*>>^����7�;[w���


R��]�3?=�������l���-7�r��b�
�LE��Q��HC�_�.����>O�OR�g��1��U�V��G��og��q�<���&**��\��|���&>>������������������ddd��K����������g���k���c������i�����Y�t�{f����n���3g�m���x�����;��|Y����P���s��>��D�[d�MXjo:bu$�q�~S�P�9o|��{�����9�4n���[o��=z��q���o`L�f��c�=fJKK��|��W�w���f���m��{���~�mel6�����Y�n]����[�����t��_�1m�\d��-2���6?��[,���1^�c���u���Ppp����du����������������za`�|,N����k
���Cy1+U�N�������M�/���g��'���1F�7dj��m*q��$P����{�`��
j

 P��))���n�'��%I�u
�+w�Rp������G~8vZ#>J�������������m��P�'m:�qoRA�S��5uH��mju,@-D
���2�^\�]3���$]�����G����
��(�@v8�P����q0W�4�w���u��Sm���@��Z���F�M��3�
���k�z+�k���u�c�.�7W���+w��{� ���&�VG�@�9q�X��e����%I�����������z*���N*yV��E
����v�m1�����(�@-g��?����K���e��y��N������(�@-�_T�q���%��$II=[����TC;�t
�W�����������x��|��tRW��U=��B����mVQ�K���:,F1Q����'(�@-RT����j�w%IWvl�7�V�6��
�
 PK8Q�������C^^��	5������#_@�����[������/*S�6�ygo�����X�z�X������v�ok�J�b�B4mX�ZX�P�Q
��8�4jN�6�;)I���6zr@g��x[�P�Q
��pB�I����jh�����
=ZX�!(�@
r���Y��^Y�S.#uo���b��yC��
<�!ygJ5f~�V���$��J�����������M�r5rV��*���[���M��FrU�%(�@52�h��LMZ�M%N���j��uolu4����LI���t�>M?,I��k�^�����,N�t@���9���R�+��|��4��N���m��P+P�*���#z���TP�Th#���Q�6M����"%e.��d�f��/I�o�To���F���g(�@8�[��Yi�8�+IJ���M�(_��
��(��EZ�3G��e(�L������^��s����U@�9]Fo����W��1R�V��64F�M���o����b=27C��9.I���(=�����rU@�G
*)��I%�JW��H
~>�|[
����XT� c����>M�b��\F��7�;w��CX#��
P)@���J�������,I�M�"4��j`������8��G9+M�����K������4��z�,
 �|PO�E�e.�	��a1�bu,.
8��R��]�Us�;(I�]��z}Po5n`�8�����Q��u��K��Q�W���7��
 ���f���_T��
lz��>��C3�c
P�(���R�K//��w���$��n��Cc�oq2�/�Q��f�k�������h�q:�����dT
 <�����9�:~�D���z�����{�c
P���-�5k����nRDD������g���o���	��E(!!A�w�.7s��I
6LAAA
		�}�����O����i����/EFF���^�E��s�����W�=�d��JgA��rM�j��z���.Q��FZ���?�G��XPP�^�zi��i����K/�����;�������A�JLLTQQ�{f��a��u��/_�E�i��5z��������zEGG+55U/����}�Y�������k�j��!���������j�����eK���~�=S�����^^�S.#��J�%_�6�X
��a��$�������\.n^~�e����\c����9s�1�l���H2�}��{��/�0^^^�����c�O�n7nl����3���3�:ur�4h�IJJ*�'..���O�p�����3�L^^^�km<x�\6y����t|j���!��H����15�]����SVV���������IRJJ�BBB��o_�LBB�����~�z���W^)���~ obb�v���S�N�g~�<gg�>OE��~1��_��3Rt8�P�M����4��H��
P�j�$���,IRXXX��aaa�}YYY


-����WM�4)7��M�_�����+++���s�,�R\\���b�}���+FmQP\��>���2�H�����;z)����dX���+a����4i��1P	{r�5��4��9-o/=yCg���������s��G���������r������������SnYY�N�<Yn�\���s���O��/���?^yyy������jXi��#�y����sZ���������+�R���
`�6m�+V��9�_�^�������x���*55�=�r�J�\.����g��Y���R�������S'5n��=���9;s�y*��\�v������P��95�?[���t�)q��vM������u��
P+T�G��O���={��������5i�DQQQ=z���yu��Am���3�<���
8P���K�p�
�������;*--��Q�t��w*""B�4t�PM�4I��w����-[���7������~�GyDW]u�^}�U%%%i��������?*�����YP7:uF�����`�$��k�ktBG�x��nUyJ�W_}e$��6|�pc��?~��g�1aaa�n��k��������1N�8a�b6lh�������k�����l���\q��n���-[�)S��"����M����f3��u3�/.��"Y����k��;�M�I�L��E��������VG�B�~�e�1��:��p(88Xyyy|l!��������+|��W�`M�V�-N��x��,`�qs���Z��	I�=��z*����>'�����),q��MG����t(O�h����z���--N@�G
D���x�f�;����W��Y�6o��g%_�^��7�8!u���e�rG�������:����q���4Zw��R��vP�PQ+�/���j��L�-�$yyI���\w�G�����h.��1F�N�_�h���*u�x�z�@?
�$R��E+�)g�p�(��\Aq�>�8�����|����!���h%�l!?����Pa�=9��h]���zH��e�$?o������4Z=Z[�����U�ti��l�+��R��poo�4�O��Tp���	
��(����"����92��(�$y{I�v	�=����]3ysR5��jc�Q���h�
-��-����:�5���K�4$.J-C,N	�����9�J�i�a�k�
��9��~I���;��n�.����	
�l@T��G����,����8%�x��[��xRG��y�mj
 .JI�K_l9����w�O���m�{��uk��j��I�&@\���������}wP�O�H�|����-\w]�K�6��'uPQQa.��7{��_�h��l��9
�kH�(
��� kC��������jA�A�Z��}���/k�Tw_���a�����

 ~��Cy����Z����J]��Fv_��Jw]����,N.��:�x�Q�s�
m<����9����o�[zG����6�e��C��y��f�?�����3��$?/������4Z���9��z����.���r���Z��������2$@C��4��H5kh�6$�r@t�t��H����S���Wvl��/��5�C��uy
��(�������(��m:���'u�iP�V���X��
`=w��L3��_�h��{{����;>Z7�������	
@M��SE�N��|�fo�T~Q�$�����{E��K��+2����2�z�Hn����Tm>�'I�j��.����j��fq:`5
`=�����Q���.Q�@?M�����&oN���X��Z@�.��R�Q��Fz����lhu,P�P���2�&}�U��gJ��z�����@���hu���b��������������4�w��j�U�:l��\��_�:�W�Fv_�9����fu,P�Q����k��7��������{��]��V�u��q����t��]�W�tM�P�qgo��Y���:$�L�����w�$%_�Nc���u{
@�P��]����~�'�(��G/��S��au,PQ��e[�4f^�
J�j�w��U��`�c
�:�X��m����I��m�h��5mh�8��(������u�����]�ZO%u������@]G
����R.#�m�go�fuPO�vR-������KZ7�8	�O(������$I��4�8	�O(�����2m=�'I��;���Pk���\���Z��U����z�XKm�������������:�Z���������U����i���uk���+..N6l�:���.�e�X/i���
����p��y3f�&N����4���K�������4��#�)q*��WCY��?]_{�5��������^u��U���������\��:$I�������U�c`II�RSS����������������1���r8�n�!�L�$�YC[�x6�-������TXXX��aaa���:�c&O����`�-22�Z��:%I
~>�r|���p%�?^c��q�w8�R���\��}��EP��c`�f��������r����~����v���j��X����P=<�#`�����X�X�����ri������0@���w%i��1>|�����~����7�PAA����^��
T�.����c�4a�eee�w��Z�t�/N
�O��1��u���Ppp�����	��~{��x*
 ���x
 ���x
 ���x
 ���x����:{��aqPQg_�=�bh�����/I����8	����|[�\�"�\.9rD�5���W���p(22R���)d��k�<a��g��5��1F���������g~7�^ooo�j��Z�#((���>�5���~��5J��N���<����<��x0
 ����Rv�]'N��n�:J�a��k�<a��g��5�"8	��� ���x
 ���x
�E�M����[���_qqq��a�o�/X�@�;w����z���%K��P��S�u���{����7n���+!!���/�Ae�,��;w����4p���
X*����\%''�E�������c��;[�5��������G}TEEE5�����Y��n�I����g�}v���Z�J111���j���f��Y�9/Fe���'�����S������x-[��f�^��s<��o�����z��]m��������XO=�����e����uk������u������1c4q�D����W�^JLLTNN�9���]�!C�����Szz���j��-5��r*��U�Vi��!����������H]��:|�p
'������������W���k(����KJJt�u�i��������s�N���{j��e
'����q���z��'5q�Dm��]���5o�<������WPP�^�zi��i���o����t��W+##C�G�����_�Re��f�]w�uZ�d�RSSu��W���nRzzz5'�p�]�Y������{t���VS��u!�4h�V�X�������s�����N�:Uc�:�������$''��;�Na&O�|��A�����r���������j�y�*���+++3�52~�auE�h����2s�e�����>��r�-5���Uv�3f�0m��5%%%5��Uv������k�)�m��1���/���UE����Os��'�0��u+�m���&11��U����\�v�j&M�T���Ae�8x�`���O��'�^�zUk��V�u~��&88��8q�fB��X�JJJ�������6ooo%$$(%%���III)7/I����:_\�:���3*--U�&M�+�E��5��/Qhh�������yQ.d�.T||����������_�������r!k����������x���Z�d�n����\������r����_k��\�>�@{�������Rm.\��}����^R��-��cG=���*,,�:Z��kuOs��q9�N������;v��1YYY���������B��s���SDD�/^�j�Y�7�|������������B��w�^�\�R��
��%K�g��9R������B�8t�P?~\W\q��1*++��>X�?��_���p8TXX�����U�W^yE�O���A���Rev���'�|R_��|}��K���{��7����_�~���?��#G��������W+� j�)S�h������O���ou�*�������[�����5kfu�j�r��w�}W���<x��z�)���;VG�2�V���/�����+--M�|��/^���{��h�@�g���I�4�|���Z�J8�N
:T�&MR����S�\.����4k�,���O7�x�^{�5}�����+��j�f�����G�����ggg+<<���	��|mp!�<��W^��)S����W={������k�����~�t�M�m.�K������;w�]�v���.���E��������{[�.]�������l�j�\Y��g�yFw�}����~IR�=TPP�x@O=����������NPPP�{�o��������`��Z�������������t�5J��_s�1�����_~�k�����U�E�j���������t�"c�:�:X��v��_�������X�X�����ri�����?�c�����K����u�6��uJ�K/����{NK�.U��}k"���;w����7+##�}�����gYFFF�d�
��?��/�\{��q�[I��k�Z�hQ���tak<s��/J���k��������1g��{���3g������S����~�5��T�N�������8�#V��/�\G�������v��%ooo�j���d�����x��s���nf��i�m�fx�
b����1��}����'�t�����������+f���f�������l����%THe�9e�c����l�=�����[������.�\�5fff�F��Q�F��;w�E����P����[�����'N�h5jd���c���k���K��];3h� ��p^���&==����I���^3�������c�|�Is��w�����k���c������i�����Y�t�UK8���q��Y����L�6������\��p^�]������+����|��U+��?��l����^��t������V-���Z����6QQQ�f��~���u����]u�Uf��������o:v�hl6�����Y�xq
'�0�Ygtt�������k>x%T�����B
4��k\�v����3v���m����������SWNe�XZZj�}�Y��];���o"##���#��S�j>x}��W���uv]��7W]u�/��woc��L��m�|P��+��k����~s�6��?���+�B��}�v���`L�V���1c��3gj>|�eL=����x
 ���x
 ���x
 ���x
 �U��Y��n�I����g�}V��?���������A�����Z���@�z���i�.���?���=Z���kW�q�U�����Ze��
z���u����sqq��q�l�R
4P\\�V�Z����aC����o�����m�����ZA�G
u��Q������s�j��M���;t�
7h����������cG�������^@Pgdff��>�����k�N�?�����
}����/**��Y�x��g|�PQ�7o���T���m/..V��M1����*??_�����u��O�����RSS���Sn_��
1������������j*b�@
uF�>}�t:���s�����o����+-\�����@P��>}Z{��q���o�222��Iu��Q��
�=���W_}U}����c��b�
���SIII�����P�-4`�+�Q�yc��!�Z�j�����_l>|�f�����R=�����?�����Y�f���K5i�$���C��r��{��G/��BM/���x~���x
 ���x
 ���x
 ���x
 ���x
 ���x
 ����lB���_{IEND�B`�