2 files changed, 65 insertions, 15 deletions

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 733fe3cf2a0..edcd19a4fd7 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -173,6 +173,50 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
 }
 
 /*
+ * bms_compare - qsort-style comparator for bitmapsets
+ *
+ * This guarantees to report values as equal iff bms_equal would say they are
+ * equal.  Otherwise, the highest-numbered bit that is set in one value but
+ * not the other determines the result.  (This rule means that, for example,
+ * {6} is greater than {5}, which seems plausible.)
+ */
+int
+bms_compare(const Bitmapset *a, const Bitmapset *b)
+{
+	int			shortlen;
+	int			i;
+
+	/* Handle cases where either input is NULL */
+	if (a == NULL)
+		return bms_is_empty(b) ? 0 : -1;
+	else if (b == NULL)
+		return bms_is_empty(a) ? 0 : +1;
+	/* Handle cases where one input is longer than the other */
+	shortlen = Min(a->nwords, b->nwords);
+	for (i = shortlen; i < a->nwords; i++)
+	{
+		if (a->words[i] != 0)
+			return +1;
+	}
+	for (i = shortlen; i < b->nwords; i++)
+	{
+		if (b->words[i] != 0)
+			return -1;
+	}
+	/* Process words in common */
+	i = shortlen;
+	while (--i >= 0)
+	{
+		bitmapword	aw = a->words[i];
+		bitmapword	bw = b->words[i];
+
+		if (aw != bw)
+			return (aw > bw) ? +1 : -1;
+	}
+	return 0;
+}
+
+/*
  * bms_make_singleton - build a bitmapset containing a single member
  */
 Bitmapset *
@@ -838,7 +882,7 @@ bms_add_range(Bitmapset *a, int lower, int upper)
 	if (lwordnum == uwordnum)
 	{
 		a->words[lwordnum] |= ~(bitmapword) (((bitmapword) 1 << lbitnum) - 1)
-							  & (~(bitmapword) 0) >> ushiftbits;
+			& (~(bitmapword) 0) >> ushiftbits;
 	}
 	else
 	{
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);
 }
 
 /*