Re: Review: Revise parallel pg_restore's scheduling heuristic

I wrote:
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

>> Attached is a further small improvement that gets rid of the
>> find_ready_items() scans. After re-reading the patch I realized
>> that it wasn't *really* avoiding O(N^2) behavior ... but this
>> version does.
>
> I'll run a fresh set of benchmarks.

Over the weekend I ran 40 restores of Milwaukee County's production
data using Friday's snapshot with and without the patch. I alternated
between patched and unpatched. It appears that this latest version is
slightly slower for our production database on the same machine and
configuration where the previous patch appeared to be 1% to 2% faster
than unpatched (although I had fewer samples of that).

Although the actual runs were interleaved, I've separated them for
this email, because it seems easier to look them over this way:

8.5devel pg_restore -j2

real 77m13.737s
real 78m21.701s
real 78m21.536s
real 77m37.541s
real 79m10.068s
real 81m37.111s
real 77m52.252s
real 80m49.110s
real 76m50.093s
real 78m0.701s
real 77m30.674s
real 77m22.875s
real 80m43.914s
real 78m51.525s
real 80m46.329s
real 76m56.703s
real 78m44.960s
real 82m37.757s
real 84m12.938s
real 82m27.591s

8.5devel-alt pg_restore -j2

real 78m10.846s
real 78m5.584s
real 78m13.673s
real 79m43.939s
real 84m39.593s
real 80m25.240s
real 78m10.045s
real 82m34.320s
real 78m43.528s
real 77m12.211s
real 77m39.171s
real 79m58.421s
real 84m50.816s
real 85m56.248s
real 79m17.361s
real 79m0.778s
real 77m3.525s
real 77m22.750s
real 78m22.882s
real 78m51.617s

That's about 0.52% slower with the patch. Because there was over 10%
variation in the numbers with the patch, I tried leaving out the four
highest outliers on both, in case it was the result of some other
activity on the system (even though this machine should have been
pretty quiet over the weekend) and the difference fell to 0.09%.

I don't know if this difference is enough to worry about; it might
depend on whether we're comparing to the unpatched version or the
previous patch. If it comes to choosing between a 1% to 2%
performance gain for a "normal" case versus elimination of O(N^2)
behavior for a worst-case scenario, I'm not sure which should win --
especially in the absence of benchmarks showing the pessimal case.
What would be the most productive focus for benchmarks at this point?
The artificial pessimal case?

-Kevin