Improve the heuristic for ordering child paths of a parallel append.

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.

Discussion: https://postgr.es/m/4944.1515446989@sss.pgh.pa.us

1 files changed, 20 insertions, 14 deletions

diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 7df87617100..48b4db72bc8 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1274,38 +1274,44 @@ create_append_path(RelOptInfo *rel,
 
 /*
  * append_total_cost_compare
- *	  list_qsort comparator for sorting append child paths by total_cost
+ *	  qsort comparator for sorting append child paths by total_cost descending
+ *
+ * For equal total costs, we fall back to comparing startup costs; if those
+ * are equal too, break ties using bms_compare on the paths' relids.
+ * (This is to avoid getting unpredictable results from qsort.)
  */
 static int
 append_total_cost_compare(const void *a, const void *b)
 {
 	Path	   *path1 = (Path *) lfirst(*(ListCell **) a);
 	Path	   *path2 = (Path *) lfirst(*(ListCell **) b);
+	int			cmp;
 
-	if (path1->total_cost > path2->total_cost)
-		return -1;
-	if (path1->total_cost < path2->total_cost)
-		return 1;
-
-	return 0;
+	cmp = compare_path_costs(path1, path2, TOTAL_COST);
+	if (cmp != 0)
+		return -cmp;
+	return bms_compare(path1->parent->relids, path2->parent->relids);
 }
 
 /*
  * append_startup_cost_compare
- *	  list_qsort comparator for sorting append child paths by startup_cost
+ *	  qsort comparator for sorting append child paths by startup_cost descending
+ *
+ * For equal startup costs, we fall back to comparing total costs; if those
+ * are equal too, break ties using bms_compare on the paths' relids.
+ * (This is to avoid getting unpredictable results from qsort.)
  */
 static int
 append_startup_cost_compare(const void *a, const void *b)
 {
 	Path	   *path1 = (Path *) lfirst(*(ListCell **) a);
 	Path	   *path2 = (Path *) lfirst(*(ListCell **) b);
+	int			cmp;
 
-	if (path1->startup_cost > path2->startup_cost)
-		return -1;
-	if (path1->startup_cost < path2->startup_cost)
-		return 1;
-
-	return 0;
+	cmp = compare_path_costs(path1, path2, STARTUP_COST);
+	if (cmp != 0)
+		return -cmp;
+	return bms_compare(path1->parent->relids, path2->parent->relids);
 }
 
 /*