From: Nathan Bossart <nathandbossart@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Andrew Dunstan <andrew@dunslane.net>
Cc: pgsql-hackers@lists.postgresql.org
Subject: Re: Inefficiency in parallel pg_restore with many tables
Date: Mon, 17 Jul 2023 21:57:01 -0700
Message-ID: <20230718045701.GA1090171@nathanxps13> (raw)
In-Reply-To: <20230717035424.GA541888@nathanxps13>
References: <3612876.1689443232@sss.pgh.pa.us>
<cf80eacd-8446-2a25-370b-40b2eb1cf890@dunslane.net>
<3787685.1689515154@sss.pgh.pa.us>
<20230717035424.GA541888@nathanxps13>
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.comAttachments:
[text/x-diff] expand_binaryheap_api.patch (3.7K, ../20230718045701.GA1090171@nathanxps13/2-expand_binaryheap_api.patch)
download | inline diff:diff --git a/src/backend/lib/binaryheap.c b/src/backend/lib/binaryheap.cindex 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.hindex 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)
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: nathandbossart@gmail.com, tgl@sss.pgh.pa.us, andrew@dunslane.net, pgsql-hackers@lists.postgresql.org
Subject: Re: Inefficiency in parallel pg_restore with many tables
In-Reply-To: <20230718045701.GA1090171@nathanxps13>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox