Date: Mon, 17 Jul 2023 21:57:01 -0700
From: Nathan Bossart <nathandbossart@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Andrew Dunstan <andrew@dunslane.net>,
	pgsql-hackers@lists.postgresql.org
Subject: Re: Inefficiency in parallel pg_restore with many tables
Message-ID: <20230718045701.GA1090171@nathanxps13>
References: <3612876.1689443232@sss.pgh.pa.us>
 <cf80eacd-8446-2a25-370b-40b2eb1cf890@dunslane.net>
 <3787685.1689515154@sss.pgh.pa.us>
 <20230717035424.GA541888@nathanxps13>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="jI8keyz6grp/JLjh"
Content-Disposition: inline
In-Reply-To: <20230717035424.GA541888@nathanxps13>
Archived-At: <https://www.postgresql.org/message-id/20230718045701.GA1090171%40nathanxps13>
Precedence: bulk


--jI8keyz6grp/JLjh
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

On Sun, Jul 16, 2023 at 08:54:24PM -0700, Nathan Bossart wrote:
> This seems worth a try.  IIUC you are suggesting making binaryheap.c
> frontend-friendly and expanding its API a bit.  If no one has volunteered,
> I could probably hack something together.

I spent some time on the binaryheap changes.  I haven't had a chance to
plug it into the ready_list yet.

-- 
Nathan Bossart
Amazon Web Services: https://aws.amazon.com

--jI8keyz6grp/JLjh
Content-Type: text/x-diff; charset=us-ascii
Content-Disposition: attachment; filename="expand_binaryheap_api.patch"

diff --git a/src/backend/lib/binaryheap.c b/src/backend/lib/binaryheap.c
index 1737546757..36b6f5c51f 100644
--- a/src/backend/lib/binaryheap.c
+++ b/src/backend/lib/binaryheap.c
@@ -11,10 +11,17 @@
  *-------------------------------------------------------------------------
  */
 
+#ifndef FRONTEND
 #include "postgres.h"
+#else
+#include "postgres_fe.h"
+#endif
 
 #include <math.h>
 
+#ifdef FRONTEND
+#include "common/logging.h"
+#endif
 #include "lib/binaryheap.h"
 
 static void sift_down(binaryheap *heap, int node_off);
@@ -35,7 +42,11 @@ binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
 	binaryheap *heap;
 
 	sz = offsetof(binaryheap, bh_nodes) + sizeof(Datum) * capacity;
+#ifdef FRONTEND
+	heap = (binaryheap *) pg_malloc(sz);
+#else
 	heap = (binaryheap *) palloc(sz);
+#endif
 	heap->bh_space = capacity;
 	heap->bh_compare = compare;
 	heap->bh_arg = arg;
@@ -109,7 +120,11 @@ void
 binaryheap_add_unordered(binaryheap *heap, Datum d)
 {
 	if (heap->bh_size >= heap->bh_space)
+#ifdef FRONTEND
+		pg_fatal("out of binary heap slots");
+#else
 		elog(ERROR, "out of binary heap slots");
+#endif
 	heap->bh_has_heap_property = false;
 	heap->bh_nodes[heap->bh_size] = d;
 	heap->bh_size++;
@@ -141,7 +156,11 @@ void
 binaryheap_add(binaryheap *heap, Datum d)
 {
 	if (heap->bh_size >= heap->bh_space)
+#ifdef FRONTEND
+		pg_fatal("out of binary heap slots");
+#else
 		elog(ERROR, "out of binary heap slots");
+#endif
 	heap->bh_nodes[heap->bh_size] = d;
 	heap->bh_size++;
 	sift_up(heap, heap->bh_size - 1);
@@ -196,6 +215,65 @@ binaryheap_remove_first(binaryheap *heap)
 	return result;
 }
 
+/*
+ * binaryheap_remove
+ *
+ * Removes the given datum from the heap.  The caller must ensure that the
+ * datum exists in the heap.  Always O(n).
+ */
+void
+binaryheap_remove(binaryheap *heap, Datum d)
+{
+	Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
+
+	for (int i = 0; i < heap->bh_size; i++)
+	{
+		if (heap->bh_compare(heap->bh_nodes[i],
+							 d,
+							 heap->bh_arg) == 0)
+		{
+			binaryheap_remove_node(heap, &heap->bh_nodes[i]);
+			return;
+		}
+	}
+
+#ifdef FRONTEND
+	pg_fatal("datum not found in heap");
+#else
+	elog(ERROR, "datum not found in heap");
+#endif
+}
+
+/*
+ * binaryheap_remove_node
+ *
+ * Removes the given node from the heap.  The caller must ensure that the node
+ * exists in the heap.  O(log n) worst case.
+ */
+void
+binaryheap_remove_node(binaryheap *heap, Datum *n)
+{
+	int			cmp;
+
+	Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
+	Assert(n >= &heap->bh_nodes[0]);
+	Assert(n <= &heap->bh_nodes[heap->bh_size - 1]);
+
+	/* compare last node to the one that is being removed */
+	cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size],
+						   *n,
+						   heap->bh_arg);
+
+	/* remove the last node, placing it in the vacated entry */
+	*n = heap->bh_nodes[heap->bh_size];
+
+	/* sift as needed to preserve the heap property */
+	if (cmp > 0)
+		sift_up(heap, n - &heap->bh_nodes[0]);
+	else if (cmp < 0)
+		sift_down(heap, n - &heap->bh_nodes[0]);
+}
+
 /*
  * binaryheap_replace_first
  *
diff --git a/src/include/lib/binaryheap.h b/src/include/lib/binaryheap.h
index 52f7b06b25..411f7358ba 100644
--- a/src/include/lib/binaryheap.h
+++ b/src/include/lib/binaryheap.h
@@ -47,6 +47,8 @@ extern void binaryheap_build(binaryheap *heap);
 extern void binaryheap_add(binaryheap *heap, Datum d);
 extern Datum binaryheap_first(binaryheap *heap);
 extern Datum binaryheap_remove_first(binaryheap *heap);
+extern void binaryheap_remove(binaryheap *heap, Datum d);
+extern void binaryheap_remove_node(binaryheap *heap, Datum *n);
 extern void binaryheap_replace_first(binaryheap *heap, Datum d);
 
 #define binaryheap_empty(h)			((h)->bh_size == 0)

--jI8keyz6grp/JLjh--