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)
