Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eYezW-0001bw-Rb for pgsql-hackers@arkaria.postgresql.org; Mon, 08 Jan 2018 21:29:59 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.84_2) (envelope-from ) id 1eYezV-0001jH-6H for pgsql-hackers@arkaria.postgresql.org; Mon, 08 Jan 2018 21:29:57 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1eYezV-0001j2-00 for pgsql-hackers@lists.postgresql.org; Mon, 08 Jan 2018 21:29:57 +0000 Received: from sss.pgh.pa.us ([66.207.139.130]) by magus.postgresql.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_CBC_SHA384:256) (Exim 4.89) (envelope-from ) id 1eYezR-00070E-Iw for pgsql-hackers@lists.postgresql.org; Mon, 08 Jan 2018 21:29:55 +0000 Received: from sss1.sss.pgh.pa.us (localhost [127.0.0.1]) by sss.pgh.pa.us (8.14.4/8.14.4) with ESMTP id w08LTnYi004945; Mon, 8 Jan 2018 16:29:49 -0500 From: Tom Lane To: Robert Haas cc: Amit Kapila , PostgreSQL Hackers Subject: Re: Parallel append plan instability/randomness In-reply-to: <14123.1515441027@sss.pgh.pa.us> References: <7752.1515284083@sss.pgh.pa.us> <12879.1515439091@sss.pgh.pa.us> <14123.1515441027@sss.pgh.pa.us> Comments: In-reply-to Tom Lane message dated "Mon, 08 Jan 2018 14:50:27 -0500" MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----- =_aaaaaaaaaa0" Content-ID: <4852.1515446869.0@sss.pgh.pa.us> Date: Mon, 08 Jan 2018 16:29:49 -0500 Message-ID: <4944.1515446989@sss.pgh.pa.us> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Precedence: bulk ------- =_aaaaaaaaaa0 Content-Type: text/plain; charset="us-ascii" Content-ID: <4852.1515446869.1@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 ------- =_aaaaaaaaaa0 Content-Type: text/x-diff; name="improve-parallel-append-sorting.patch"; charset="us-ascii" Content-ID: <4852.1515446869.2@sss.pgh.pa.us> Content-Description: improve-parallel-append-sorting.patch Content-Transfer-Encoding: quoted-printable 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 the= y 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 exam= ple, + * {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 =3D=3D NULL) + return bms_is_empty(b) ? 0 : -1; + else if (b =3D=3D NULL) + return bms_is_empty(a) ? 0 : +1; + /* Handle cases where one input is longer than the other */ + shortlen =3D Min(a->nwords, b->nwords); + for (i =3D shortlen; i < a->nwords; i++) + { + if (a->words[i] !=3D 0) + return +1; + } + for (i =3D shortlen; i < b->nwords; i++) + { + if (b->words[i] !=3D 0) + return -1; + } + /* Process words in common */ + i =3D shortlen; + while (--i >=3D 0) + { + bitmapword aw =3D a->words[i]; + bitmapword bw =3D b->words[i]; + = + if (aw !=3D 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 =3D (Path *) lfirst(*(ListCell **) a); Path *path2 =3D (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_cos= t */ static int append_startup_cost_compare(const void *a, const void *b) { Path *path1 =3D (Path *) lfirst(*(ListCell **) a); Path *path2 =3D (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 desce= nding ! * ! * For equal total costs, we fall back to comparing startup costs; if th= ose ! * 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 =3D (Path *) lfirst(*(ListCell **) a); Path *path2 =3D (Path *) lfirst(*(ListCell **) b); + int cmp; = ! cmp =3D compare_path_costs(path1, path2, TOTAL_COST); ! if (cmp =3D=3D 0) ! cmp =3D bms_compare(path1->parent->relids, path2->parent->relids); ! return -cmp; } = /* * append_startup_cost_compare ! * qsort comparator for sorting append child paths by startup_cost des= cending ! * ! * For equal startup costs, we fall back to comparing total costs; if th= ose ! * 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 =3D (Path *) lfirst(*(ListCell **) a); Path *path2 =3D (Path *) lfirst(*(ListCell **) b); + int cmp; = ! cmp =3D compare_path_costs(path1, path2, STARTUP_COST); ! if (cmp =3D=3D 0) ! cmp =3D 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/regr= ess/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) = ------- =_aaaaaaaaaa0--