From: Tom Lane <tgl@sss.pgh.pa.us>
To: Robert Haas <robertmhaas@gmail.com>
Cc: Amit Kapila <amit.kapila16@gmail.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Parallel append plan instability/randomness
Date: Mon, 08 Jan 2018 16:29:49 -0500
Message-ID: <4944.1515446989@sss.pgh.pa.us> (raw)
In-Reply-To: <14123.1515441027@sss.pgh.pa.us>
References: <7752.1515284083@sss.pgh.pa.us>
<CAA4eK1LegxN9of0sydNM5n4up=7oCj=-E94edKDOsYFKyb1R0Q@mail.gmail.com>
<CA+TgmoaAWXyFUY1BgkYcH3DE4Xrot1qPgAOLW2Gj8OgQOVNg0w@mail.gmail.com>
<12879.1515439091@sss.pgh.pa.us>
<14123.1515441027@sss.pgh.pa.us>
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
Attachments:improve-parallel-append-sorting.patch (text/x-diff, 7.5K) downloaddiff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.cindex 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.cindex 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.hindex 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.outindex 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)
=
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: tgl@sss.pgh.pa.us, robertmhaas@gmail.com, amit.kapila16@gmail.com, pgsql-hackers@lists.postgresql.org
Subject: Re: Parallel append plan instability/randomness
In-Reply-To: <4944.1515446989@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox