Date: Sun, 16 Jul 2023 20:54:24 -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: <20230717035424.GA541888@nathanxps13>
References: <3612876.1689443232@sss.pgh.pa.us>
 <cf80eacd-8446-2a25-370b-40b2eb1cf890@dunslane.net>
 <3787685.1689515154@sss.pgh.pa.us>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <3787685.1689515154@sss.pgh.pa.us>
Archived-At: <https://www.postgresql.org/message-id/20230717035424.GA541888%40nathanxps13>
Precedence: bulk

On Sun, Jul 16, 2023 at 09:45:54AM -0400, Tom Lane wrote:
> Actually, as long as we're talking about approximately-correct behavior:
> let's make the ready_list be a priority heap, and then just make
> pop_next_work_item scan forward from the array start until it finds an
> item that's runnable per the lock heuristic.  If the heap root is
> blocked, the next things we'll examine will be its two children.
> We might pick the lower-priority of those two, but it's still known to
> be higher priority than at least 50% of the remaining heap entries, so
> it shouldn't be too awful as a choice.  The argument gets weaker the
> further you go into the heap, but we're not expecting that having most
> of the top entries blocked will be a common case.  (Besides which, the
> priorities are pretty crude to begin with.)  Once selected, pulling out
> an entry that is not the heap root is no problem: you just start the
> sift-down process from there.
> 
> The main advantage of this over the only-sort-sometimes idea is that
> we can guarantee that the largest ready item will always be dispatched
> as soon as it can be (because it will be the heap root).  So cases
> involving one big table (with big indexes) and a lot of little ones
> should get scheduled sanely, which is the main thing we want this
> algorithm to ensure.  With the other approach we can't really promise
> much at all.

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.

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