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
