Re: Parallel append plan instability/randomness

I wrote:
>> In the regression test case at hand, the startup costs are all zero so
>> this change wouldn't improve the test case's stability.  So I'm thinking
>> that in addition, it would be a good idea for these functions to break
>> exact compare_path_costs ties in some arbitrary but deterministic way,
>> rather than letting qsort() have the final say on what happens.  If the
>> subplans were all simple relation scans we could order them by planner
>> relid, but I'm not sure what to do if they're not.

> Ah, I have an idea --- let's create a bms_compare() qsort comparator for
> bitmapsets, and use that on the paths' relid sets.  It hardly matters
> what the exact semantics of the comparator are, as long as it behaves
> sanely for equal sets.

Concretely, I propose the attached.  I spent a little bit of extra effort
on the comparator in hopes that it might be useful for something else.

            regards, tom lane

diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 733fe3c..edcd19a 100644
*** a/src/backend/nodes/bitmapset.c
--- b/src/backend/nodes/bitmapset.c
*************** bms_equal(const Bitmapset *a, const Bitm
*** 173,178 ****
--- 173,222 ----
  }

  /*
+  * 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 *
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 7df8761..5c2b996 100644
*** a/src/backend/optimizer/util/pathnode.c
--- b/src/backend/optimizer/util/pathnode.c
*************** create_append_path(RelOptInfo *rel,
*** 1274,1311 ****

  /*
   * append_total_cost_compare
!  *      list_qsort comparator for sorting append child paths by total_cost
   */
  static int
  append_total_cost_compare(const void *a, const void *b)
  {
      Path       *path1 = (Path *) lfirst(*(ListCell **) a);
      Path       *path2 = (Path *) lfirst(*(ListCell **) b);

!     if (path1->total_cost > path2->total_cost)
!         return -1;
!     if (path1->total_cost < path2->total_cost)
!         return 1;
!
!     return 0;
  }

  /*
   * append_startup_cost_compare
!  *      list_qsort comparator for sorting append child paths by startup_cost
   */
  static int
  append_startup_cost_compare(const void *a, const void *b)
  {
      Path       *path1 = (Path *) lfirst(*(ListCell **) a);
      Path       *path2 = (Path *) lfirst(*(ListCell **) b);

!     if (path1->startup_cost > path2->startup_cost)
!         return -1;
!     if (path1->startup_cost < path2->startup_cost)
!         return 1;
!
!     return 0;
  }

  /*
--- 1274,1317 ----

  /*
   * append_total_cost_compare
!  *      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;

!     cmp = compare_path_costs(path1, path2, TOTAL_COST);
!     if (cmp == 0)
!         cmp = bms_compare(path1->parent->relids, path2->parent->relids);
!     return -cmp;
  }

  /*
   * append_startup_cost_compare
!  *      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;

!     cmp = compare_path_costs(path1, path2, STARTUP_COST);
!     if (cmp == 0)
!         cmp = bms_compare(path1->parent->relids, path2->parent->relids);
!     return -cmp;
  }

  /*
diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h
index 15397e9..67e8920 100644
*** a/src/include/nodes/bitmapset.h
--- b/src/include/nodes/bitmapset.h
*************** typedef enum
*** 65,70 ****
--- 65,71 ----

  extern Bitmapset *bms_copy(const Bitmapset *a);
  extern bool bms_equal(const Bitmapset *a, const Bitmapset *b);
+ extern int    bms_compare(const Bitmapset *a, const Bitmapset *b);
  extern Bitmapset *bms_make_singleton(int x);
  extern void bms_free(Bitmapset *a);

diff --git a/src/test/regress/expected/select_parallel.out b/src/test/regress/expected/select_parallel.out
index 7824ca5..5f73be4 100644
*** a/src/test/regress/expected/select_parallel.out
--- b/src/test/regress/expected/select_parallel.out
*************** explain (costs off)
*** 21,32 ****
           Workers Planned: 3
           ->  Partial Aggregate
                 ->  Parallel Append
!                      ->  Parallel Seq Scan on a_star
!                      ->  Parallel Seq Scan on b_star
!                      ->  Parallel Seq Scan on c_star
                       ->  Parallel Seq Scan on d_star
                       ->  Parallel Seq Scan on e_star
!                      ->  Parallel Seq Scan on f_star
  (11 rows)

  select round(avg(aa)), sum(aa) from a_star a1;
--- 21,32 ----
           Workers Planned: 3
           ->  Partial Aggregate
                 ->  Parallel Append
!                      ->  Parallel Seq Scan on f_star
                       ->  Parallel Seq Scan on d_star
                       ->  Parallel Seq Scan on e_star
!                      ->  Parallel Seq Scan on c_star
!                      ->  Parallel Seq Scan on b_star
!                      ->  Parallel Seq Scan on a_star
  (11 rows)

  select round(avg(aa)), sum(aa) from a_star a1;
*************** explain (costs off)
*** 49,58 ****
                 ->  Parallel Append
                       ->  Seq Scan on d_star
                       ->  Seq Scan on c_star
-                      ->  Parallel Seq Scan on a_star
-                      ->  Parallel Seq Scan on b_star
-                      ->  Parallel Seq Scan on e_star
                       ->  Parallel Seq Scan on f_star
  (11 rows)

  select round(avg(aa)), sum(aa) from a_star a2;
--- 49,58 ----
                 ->  Parallel Append
                       ->  Seq Scan on d_star
                       ->  Seq Scan on c_star
                       ->  Parallel Seq Scan on f_star
+                      ->  Parallel Seq Scan on e_star
+                      ->  Parallel Seq Scan on b_star
+                      ->  Parallel Seq Scan on a_star
  (11 rows)

  select round(avg(aa)), sum(aa) from a_star a2;
*************** explain (costs off)
*** 75,85 ****
           Workers Planned: 3
           ->  Partial Aggregate
                 ->  Parallel Append
-                      ->  Seq Scan on d_star
                       ->  Seq Scan on f_star
                       ->  Seq Scan on e_star
-                      ->  Seq Scan on b_star
                       ->  Seq Scan on c_star
                       ->  Seq Scan on a_star
  (11 rows)

--- 75,85 ----
           Workers Planned: 3
           ->  Partial Aggregate
                 ->  Parallel Append
                       ->  Seq Scan on f_star
+                      ->  Seq Scan on d_star
                       ->  Seq Scan on e_star
                       ->  Seq Scan on c_star
+                      ->  Seq Scan on b_star
                       ->  Seq Scan on a_star
  (11 rows)