Commit ab7271677 introduced code that attempts to order the child scans of a Parallel Append node in a way that will minimize execution time, based on total cost and startup cost. However, it failed to think hard about what to do when estimated costs are exactly equal; a case that's particularly likely to occur when comparing on startup cost. In such a case the ordering of the child paths would be left to the whims of qsort, an algorithm that isn't even stable.
We can improve matters by applying the rule used elsewhere in the planner: if total costs are equal, sort on startup cost, and
vice versa. When both cost estimates are exactly equal, rather than letting qsort do something unpredictable, sort based on the child paths' relids, which should typically result in sorting in inheritance order. (The latter provision requires inventing a qsort-style comparator for bitmapsets, but maybe we'll have use for that for other reasons in future.)
This results in a few plan changes in the select_parallel test, but those all look more reasonable than before, when the actual underlying cost numbers are taken into account.
624e440a47 Improve the heuristic for ordering child paths of a parallel append.
src/backend/nodes/bitmapset.c | 46 ++++++++++++++++++++++++++-
src/backend/optimizer/util/pathnode.c | 34 ++++++++++++--------
src/include/nodes/bitmapset.h | 1 +
src/test/regress/expected/select_parallel.out | 14 ++++----
4 files changed, 73 insertions(+), 22 deletions(-)