Re: Parallel append plan instability/randomness

I wrote:
> BTW, I had not looked closely at list_qsort before, but now that I have
> it seems seriously bizarre.  Why is it allocating a new List header
> rather than reusing the old one?  Because it stomps on the next-links
> of the list cells, the old header is effectively corrupted and can't
> possibly be useful afterwards, so we might as well re-use it and save
> a palloc cycle.  (By the same token, it's pretty ludicrous that it
> claims the input List is "const".  Not stomping on the list header
> is a pretty poor definition of not modifying the list.)

Actually, after looking closer, I think the current implementation
of list_qsort is actively dangerous.  If we left the code like this,
we would have to document that create_append_path corrupts its caller's
copies of subpaths and partial_subpaths when parallel_aware is true
(and by "corrupt" I don't just mean "reorder": the list headers the
caller has pointers to are now flat wrong).  Even with the change
I imagine above, we'd have to document that the caller's lists get
reordered.  Although the sole caller that's currently affected doesn't
currently do anything with those lists after the call, it's not terribly
hard to imagine that future improvements there would lead to trying to
build multiple paths with the same lists or something like that, so
that we'd have hidden interactions between different Paths.  The same
types of hazards would apply to every future use of list_qsort.

(In fact, I spent some time trying to think of a way that this could have
led to the silverfish failure we started the thread with.  I couldn't
convince myself that it was possible, but I'm not entirely convinced it's
not, either.)

So I think that re-using the caller's list cells is another penny-wise-
but-pound-foolish idea, and that we ought to just build a new list to
avoid the hazard.  As per attached.

            regards, tom lane

diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index 083538f..fe085d2 100644
*** a/src/backend/nodes/list.c
--- b/src/backend/nodes/list.c
*************** list_copy_tail(const List *oldlist, int
*** 1250,1290 ****
  }

  /*
!  * Sort a list using qsort. A sorted list is built but the cells of the
!  * original list are re-used.  The comparator function receives arguments of
!  * type ListCell **
   */
  List *
  list_qsort(const List *list, list_qsort_comparator cmp)
  {
-     ListCell   *cell;
-     int            i;
      int            len = list_length(list);
      ListCell  **list_arr;
!     List       *new_list;

      if (len == 0)
          return NIL;

      i = 0;
-     list_arr = palloc(sizeof(ListCell *) * len);
      foreach(cell, list)
          list_arr[i++] = cell;

      qsort(list_arr, len, sizeof(ListCell *), cmp);

!     new_list = (List *) palloc(sizeof(List));
!     new_list->type = list->type;
!     new_list->length = len;
!     new_list->head = list_arr[0];
!     new_list->tail = list_arr[len - 1];

!     for (i = 0; i < len - 1; i++)
!         list_arr[i]->next = list_arr[i + 1];

!     list_arr[len - 1]->next = NULL;
      pfree(list_arr);
!     return new_list;
  }

  /*
--- 1250,1312 ----
  }

  /*
!  * Sort a list as though by qsort.
!  *
!  * A new list is built and returned.
!  * The comparator function receives arguments of type ListCell **.
   */
  List *
  list_qsort(const List *list, list_qsort_comparator cmp)
  {
      int            len = list_length(list);
      ListCell  **list_arr;
!     List       *newlist;
!     ListCell   *newlist_prev;
!     ListCell   *cell;
!     int            i;

+     /* Empty list is easy */
      if (len == 0)
          return NIL;

+     /* Flatten list cells into an array, so we can use qsort */
+     list_arr = (ListCell **) palloc(sizeof(ListCell *) * len);
      i = 0;
      foreach(cell, list)
          list_arr[i++] = cell;

      qsort(list_arr, len, sizeof(ListCell *), cmp);

!     /* Construct new list (this code is much like list_copy) */
!     newlist = new_list(list->type);
!     newlist->length = len;

!     /*
!      * Copy over the data in the first cell; new_list() has already allocated
!      * the head cell itself
!      */
!     newlist->head->data = list_arr[0]->data;

!     newlist_prev = newlist->head;
!     for (i = 1; i < len; i++)
!     {
!         ListCell   *newlist_cur;
!
!         newlist_cur = (ListCell *) palloc(sizeof(*newlist_cur));
!         newlist_cur->data = list_arr[i]->data;
!         newlist_prev->next = newlist_cur;
!
!         newlist_prev = newlist_cur;
!     }
!
!     newlist_prev->next = NULL;
!     newlist->tail = newlist_prev;
!
!     /* Might as well free the workspace array */
      pfree(list_arr);
!
!     check_list_invariants(newlist);
!     return newlist;
  }

  /*