Charge cpu_tuple_cost * 0.5 for Append and MergeAppend nodes.

Previously, Append didn't charge anything at all, and MergeAppend
charged only cpu_operator_cost, about half the value used here.  This
change might make MergeAppend plans slightly more likely to be chosen
than before, since this commit increases the assumed cost for Append
-- with default values -- by 0.005 per tuple but MergeAppend by only
0.0025 per tuple.  Since the comparisons required by MergeAppend are
costed separately, it's not clear why MergeAppend needs to be
otherwise more expensive than Append, so hopefully this is OK.

Prior to partition-wise join, it didn't really matter whether or not
an Append node had any cost of its own, because every plan had to use
the same number of Append or MergeAppend nodes and in the same places.
Only the relative cost of Append vs. MergeAppend made a difference.
Now, however, it is possible to avoid some of the Append nodes using a
partition-wise join, so it's worth making an effort.  Pending patches
for partition-wise aggregate care too, because an Append of Aggregate
nodes will incur the Append overhead fewer times than an Aggregate
over an Append.  Although in most cases this change will favor the use
of partition-wise techniques, it does the opposite when the join
cardinality is greater than the sum of the input cardinalities.  Since
this situation arises in an existing regression test, I [rhaas]
adjusted it to keep the overall plan shape approximately the same.

Jeevan Chalke, per a suggestion from David Rowley.  Reviewed by
Ashutosh Bapat.  Some changes by me.  The larger patch series of which
this patch is a part was also reviewed and tested by Antonin Houska,
Rajkumar Raghuwanshi, David Rowley, Dilip Kumar, Konstantin Knizhnik,
Pascal Legrand, Rafia Sabih, and me.

Discussion: http://postgr.es/m/CAKJS1f9UXdk6ZYyqbJnjFO9a9hyHKGW7B=ZRh-rxy9qxfPA5Gw@mail.gmail.com

4 files changed, 91 insertions, 83 deletions

diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 16ef348f408..d8db0b29e1f 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -100,6 +100,13 @@
 
 #define LOG2(x)  (log(x) / 0.693147180559945)
 
+/*
+ * Append and MergeAppend nodes are less expensive than some other operations
+ * which use cpu_tuple_cost; instead of adding a separate GUC, estimate the
+ * per-tuple cost as cpu_tuple_cost multiplied by this value.
+ */
+#define APPEND_CPU_COST_MULTIPLIER 0.5
+
 
 double		seq_page_cost = DEFAULT_SEQ_PAGE_COST;
 double		random_page_cost = DEFAULT_RANDOM_PAGE_COST;
@@ -1828,10 +1835,6 @@ append_nonpartial_cost(List *subpaths, int numpaths, int parallel_workers)
 /*
  * cost_append
  *	  Determines and returns the cost of an Append node.
- *
- * We charge nothing extra for the Append itself, which perhaps is too
- * optimistic, but since it doesn't do any selection or projection, it is a
- * pretty cheap node.
  */
 void
 cost_append(AppendPath *apath)
@@ -1914,6 +1917,13 @@ cost_append(AppendPath *apath)
 								   apath->first_partial_path,
 								   apath->path.parallel_workers);
 	}
+
+	/*
+	 * Although Append does not do any selection or projection, it's not free;
+	 * add a small per-tuple overhead.
+	 */
+	apath->path.total_cost +=
+		cpu_tuple_cost * APPEND_CPU_COST_MULTIPLIER * apath->path.rows;
 }
 
 /*
@@ -1968,12 +1978,10 @@ cost_merge_append(Path *path, PlannerInfo *root,
 	run_cost += tuples * comparison_cost * logN;
 
 	/*
-	 * Also charge a small amount (arbitrarily set equal to operator cost) per
-	 * extracted tuple.  We don't charge cpu_tuple_cost because a MergeAppend
-	 * node doesn't do qual-checking or projection, so it has less overhead
-	 * than most plan nodes.
+	 * Although MergeAppend does not do any selection or projection, it's not
+	 * free; add a small per-tuple overhead.
 	 */
-	run_cost += cpu_operator_cost * tuples;
+	run_cost += cpu_tuple_cost * APPEND_CPU_COST_MULTIPLIER * tuples;
 
 	path->startup_cost = startup_cost + input_startup_cost;
 	path->total_cost = startup_cost + run_cost + input_total_cost;
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index 636bedadf2e..a72d8bc2082 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -1144,59 +1144,59 @@ INSERT INTO plt1_e SELECT i, i, 'A' || to_char(i/50, 'FM0000') FROM generate_ser
 ANALYZE plt1_e;
 -- test partition matching with N-way join
 EXPLAIN (COSTS OFF)
-SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM plt1 t1, plt2 t2, plt1_e t3 WHERE t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
+SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM plt1 t1, plt2 t2, plt1_e t3 WHERE t1.b = t2.b AND t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
                                       QUERY PLAN                                      
 --------------------------------------------------------------------------------------
- Sort
-   Sort Key: t1.c, t3.c
-   ->  HashAggregate
-         Group Key: t1.c, t2.c, t3.c
+ GroupAggregate
+   Group Key: t1.c, t2.c, t3.c
+   ->  Sort
+         Sort Key: t1.c, t3.c
          ->  Result
                ->  Append
                      ->  Hash Join
-                           Hash Cond: (t1.c = t2.c)
-                           ->  Seq Scan on plt1_p1 t1
-                           ->  Hash
-                                 ->  Hash Join
-                                       Hash Cond: (t2.c = ltrim(t3.c, 'A'::text))
+                           Hash Cond: (t1.c = ltrim(t3.c, 'A'::text))
+                           ->  Hash Join
+                                 Hash Cond: ((t1.b = t2.b) AND (t1.c = t2.c))
+                                 ->  Seq Scan on plt1_p1 t1
+                                 ->  Hash
                                        ->  Seq Scan on plt2_p1 t2
-                                       ->  Hash
-                                             ->  Seq Scan on plt1_e_p1 t3
-                     ->  Hash Join
-                           Hash Cond: (t1_1.c = t2_1.c)
-                           ->  Seq Scan on plt1_p2 t1_1
                            ->  Hash
-                                 ->  Hash Join
-                                       Hash Cond: (t2_1.c = ltrim(t3_1.c, 'A'::text))
-                                       ->  Seq Scan on plt2_p2 t2_1
-                                       ->  Hash
-                                             ->  Seq Scan on plt1_e_p2 t3_1
+                                 ->  Seq Scan on plt1_e_p1 t3
                      ->  Hash Join
-                           Hash Cond: (t1_2.c = t2_2.c)
-                           ->  Seq Scan on plt1_p3 t1_2
+                           Hash Cond: (t1_1.c = ltrim(t3_1.c, 'A'::text))
+                           ->  Hash Join
+                                 Hash Cond: ((t1_1.b = t2_1.b) AND (t1_1.c = t2_1.c))
+                                 ->  Seq Scan on plt1_p2 t1_1
+                                 ->  Hash
+                                       ->  Seq Scan on plt2_p2 t2_1
                            ->  Hash
-                                 ->  Hash Join
-                                       Hash Cond: (t2_2.c = ltrim(t3_2.c, 'A'::text))
+                                 ->  Seq Scan on plt1_e_p2 t3_1
+                     ->  Hash Join
+                           Hash Cond: (t1_2.c = ltrim(t3_2.c, 'A'::text))
+                           ->  Hash Join
+                                 Hash Cond: ((t1_2.b = t2_2.b) AND (t1_2.c = t2_2.c))
+                                 ->  Seq Scan on plt1_p3 t1_2
+                                 ->  Hash
                                        ->  Seq Scan on plt2_p3 t2_2
-                                       ->  Hash
-                                             ->  Seq Scan on plt1_e_p3 t3_2
+                           ->  Hash
+                                 ->  Seq Scan on plt1_e_p3 t3_2
 (33 rows)
 
-SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM plt1 t1, plt2 t2, plt1_e t3 WHERE t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
+SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM plt1 t1, plt2 t2, plt1_e t3 WHERE t1.b = t2.b AND t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
          avg          |         avg          |          avg          |  c   |  c   |   c   
 ----------------------+----------------------+-----------------------+------+------+-------
   24.0000000000000000 |  24.0000000000000000 |   48.0000000000000000 | 0000 | 0000 | A0000
-  74.0000000000000000 |  75.0000000000000000 |  148.0000000000000000 | 0001 | 0001 | A0001
- 124.0000000000000000 | 124.5000000000000000 |  248.0000000000000000 | 0002 | 0002 | A0002
+  75.0000000000000000 |  75.0000000000000000 |  148.0000000000000000 | 0001 | 0001 | A0001
+ 123.0000000000000000 | 123.0000000000000000 |  248.0000000000000000 | 0002 | 0002 | A0002
  174.0000000000000000 | 174.0000000000000000 |  348.0000000000000000 | 0003 | 0003 | A0003
- 224.0000000000000000 | 225.0000000000000000 |  448.0000000000000000 | 0004 | 0004 | A0004
- 274.0000000000000000 | 274.5000000000000000 |  548.0000000000000000 | 0005 | 0005 | A0005
+ 225.0000000000000000 | 225.0000000000000000 |  448.0000000000000000 | 0004 | 0004 | A0004
+ 273.0000000000000000 | 273.0000000000000000 |  548.0000000000000000 | 0005 | 0005 | A0005
  324.0000000000000000 | 324.0000000000000000 |  648.0000000000000000 | 0006 | 0006 | A0006
- 374.0000000000000000 | 375.0000000000000000 |  748.0000000000000000 | 0007 | 0007 | A0007
- 424.0000000000000000 | 424.5000000000000000 |  848.0000000000000000 | 0008 | 0008 | A0008
+ 375.0000000000000000 | 375.0000000000000000 |  748.0000000000000000 | 0007 | 0007 | A0007
+ 423.0000000000000000 | 423.0000000000000000 |  848.0000000000000000 | 0008 | 0008 | A0008
  474.0000000000000000 | 474.0000000000000000 |  948.0000000000000000 | 0009 | 0009 | A0009
- 524.0000000000000000 | 525.0000000000000000 | 1048.0000000000000000 | 0010 | 0010 | A0010
- 574.0000000000000000 | 574.5000000000000000 | 1148.0000000000000000 | 0011 | 0011 | A0011
+ 525.0000000000000000 | 525.0000000000000000 | 1048.0000000000000000 | 0010 | 0010 | A0010
+ 573.0000000000000000 | 573.0000000000000000 | 1148.0000000000000000 | 0011 | 0011 | A0011
 (12 rows)
 
 -- joins where one of the relations is proven empty
@@ -1289,59 +1289,59 @@ INSERT INTO pht1_e SELECT i, i, 'A' || to_char(i/50, 'FM0000') FROM generate_ser
 ANALYZE pht1_e;
 -- test partition matching with N-way join
 EXPLAIN (COSTS OFF)
-SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM pht1 t1, pht2 t2, pht1_e t3 WHERE t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
-                                      QUERY PLAN                                      
---------------------------------------------------------------------------------------
- Sort
-   Sort Key: t1.c, t3.c
-   ->  HashAggregate
-         Group Key: t1.c, t2.c, t3.c
+SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM pht1 t1, pht2 t2, pht1_e t3 WHERE t1.b = t2.b AND t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
+                                         QUERY PLAN                                         
+--------------------------------------------------------------------------------------------
+ GroupAggregate
+   Group Key: t1.c, t2.c, t3.c
+   ->  Sort
+         Sort Key: t1.c, t3.c
          ->  Result
                ->  Append
                      ->  Hash Join
-                           Hash Cond: (t1.c = t2.c)
-                           ->  Seq Scan on pht1_p1 t1
-                           ->  Hash
-                                 ->  Hash Join
-                                       Hash Cond: (t2.c = ltrim(t3.c, 'A'::text))
+                           Hash Cond: (t1.c = ltrim(t3.c, 'A'::text))
+                           ->  Hash Join
+                                 Hash Cond: ((t1.b = t2.b) AND (t1.c = t2.c))
+                                 ->  Seq Scan on pht1_p1 t1
+                                 ->  Hash
                                        ->  Seq Scan on pht2_p1 t2
-                                       ->  Hash
-                                             ->  Seq Scan on pht1_e_p1 t3
+                           ->  Hash
+                                 ->  Seq Scan on pht1_e_p1 t3
                      ->  Hash Join
-                           Hash Cond: (t1_1.c = t2_1.c)
-                           ->  Seq Scan on pht1_p2 t1_1
+                           Hash Cond: (ltrim(t3_1.c, 'A'::text) = t1_1.c)
+                           ->  Seq Scan on pht1_e_p2 t3_1
                            ->  Hash
                                  ->  Hash Join
-                                       Hash Cond: (t2_1.c = ltrim(t3_1.c, 'A'::text))
-                                       ->  Seq Scan on pht2_p2 t2_1
+                                       Hash Cond: ((t1_1.b = t2_1.b) AND (t1_1.c = t2_1.c))
+                                       ->  Seq Scan on pht1_p2 t1_1
                                        ->  Hash
-                                             ->  Seq Scan on pht1_e_p2 t3_1
+                                             ->  Seq Scan on pht2_p2 t2_1
                      ->  Hash Join
-                           Hash Cond: (t1_2.c = t2_2.c)
-                           ->  Seq Scan on pht1_p3 t1_2
+                           Hash Cond: (ltrim(t3_2.c, 'A'::text) = t1_2.c)
+                           ->  Seq Scan on pht1_e_p3 t3_2
                            ->  Hash
                                  ->  Hash Join
-                                       Hash Cond: (t2_2.c = ltrim(t3_2.c, 'A'::text))
-                                       ->  Seq Scan on pht2_p3 t2_2
+                                       Hash Cond: ((t1_2.b = t2_2.b) AND (t1_2.c = t2_2.c))
+                                       ->  Seq Scan on pht1_p3 t1_2
                                        ->  Hash
-                                             ->  Seq Scan on pht1_e_p3 t3_2
+                                             ->  Seq Scan on pht2_p3 t2_2
 (33 rows)
 
-SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM pht1 t1, pht2 t2, pht1_e t3 WHERE t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
+SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM pht1 t1, pht2 t2, pht1_e t3 WHERE t1.b = t2.b AND t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
          avg          |         avg          |          avg          |  c   |  c   |   c   
 ----------------------+----------------------+-----------------------+------+------+-------
   24.0000000000000000 |  24.0000000000000000 |   48.0000000000000000 | 0000 | 0000 | A0000
-  74.0000000000000000 |  75.0000000000000000 |  148.0000000000000000 | 0001 | 0001 | A0001
- 124.0000000000000000 | 124.5000000000000000 |  248.0000000000000000 | 0002 | 0002 | A0002
+  75.0000000000000000 |  75.0000000000000000 |  148.0000000000000000 | 0001 | 0001 | A0001
+ 123.0000000000000000 | 123.0000000000000000 |  248.0000000000000000 | 0002 | 0002 | A0002
  174.0000000000000000 | 174.0000000000000000 |  348.0000000000000000 | 0003 | 0003 | A0003
- 224.0000000000000000 | 225.0000000000000000 |  448.0000000000000000 | 0004 | 0004 | A0004
- 274.0000000000000000 | 274.5000000000000000 |  548.0000000000000000 | 0005 | 0005 | A0005
+ 225.0000000000000000 | 225.0000000000000000 |  448.0000000000000000 | 0004 | 0004 | A0004
+ 273.0000000000000000 | 273.0000000000000000 |  548.0000000000000000 | 0005 | 0005 | A0005
  324.0000000000000000 | 324.0000000000000000 |  648.0000000000000000 | 0006 | 0006 | A0006
- 374.0000000000000000 | 375.0000000000000000 |  748.0000000000000000 | 0007 | 0007 | A0007
- 424.0000000000000000 | 424.5000000000000000 |  848.0000000000000000 | 0008 | 0008 | A0008
+ 375.0000000000000000 | 375.0000000000000000 |  748.0000000000000000 | 0007 | 0007 | A0007
+ 423.0000000000000000 | 423.0000000000000000 |  848.0000000000000000 | 0008 | 0008 | A0008
  474.0000000000000000 | 474.0000000000000000 |  948.0000000000000000 | 0009 | 0009 | A0009
- 524.0000000000000000 | 525.0000000000000000 | 1048.0000000000000000 | 0010 | 0010 | A0010
- 574.0000000000000000 | 574.5000000000000000 | 1148.0000000000000000 | 0011 | 0011 | A0011
+ 525.0000000000000000 | 525.0000000000000000 | 1048.0000000000000000 | 0010 | 0010 | A0010
+ 573.0000000000000000 | 573.0000000000000000 | 1148.0000000000000000 | 0011 | 0011 | A0011
 (12 rows)
 
 --
diff --git a/src/test/regress/expected/subselect.out b/src/test/regress/expected/subselect.out
index 4b893856cfc..3b2bf3273e8 100644
--- a/src/test/regress/expected/subselect.out
+++ b/src/test/regress/expected/subselect.out
@@ -235,7 +235,7 @@ SELECT *, pg_typeof(f1) FROM
 explain verbose select '42' union all select '43';
                    QUERY PLAN                    
 -------------------------------------------------
- Append  (cost=0.00..0.04 rows=2 width=32)
+ Append  (cost=0.00..0.05 rows=2 width=32)
    ->  Result  (cost=0.00..0.01 rows=1 width=32)
          Output: '42'::text
    ->  Result  (cost=0.00..0.01 rows=1 width=32)
@@ -245,7 +245,7 @@ explain verbose select '42' union all select '43';
 explain verbose select '42' union all select 43;
                    QUERY PLAN                   
 ------------------------------------------------
- Append  (cost=0.00..0.04 rows=2 width=4)
+ Append  (cost=0.00..0.05 rows=2 width=4)
    ->  Result  (cost=0.00..0.01 rows=1 width=4)
          Output: 42
    ->  Result  (cost=0.00..0.01 rows=1 width=4)
diff --git a/src/test/regress/sql/partition_join.sql b/src/test/regress/sql/partition_join.sql
index 4b2e7810601..17772a9300b 100644
--- a/src/test/regress/sql/partition_join.sql
+++ b/src/test/regress/sql/partition_join.sql
@@ -213,8 +213,8 @@ ANALYZE plt1_e;
 
 -- test partition matching with N-way join
 EXPLAIN (COSTS OFF)
-SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM plt1 t1, plt2 t2, plt1_e t3 WHERE t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
-SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM plt1 t1, plt2 t2, plt1_e t3 WHERE t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
+SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM plt1 t1, plt2 t2, plt1_e t3 WHERE t1.b = t2.b AND t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
+SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM plt1 t1, plt2 t2, plt1_e t3 WHERE t1.b = t2.b AND t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
 
 -- joins where one of the relations is proven empty
 EXPLAIN (COSTS OFF)
@@ -258,8 +258,8 @@ ANALYZE pht1_e;
 
 -- test partition matching with N-way join
 EXPLAIN (COSTS OFF)
-SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM pht1 t1, pht2 t2, pht1_e t3 WHERE t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
-SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM pht1 t1, pht2 t2, pht1_e t3 WHERE t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
+SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM pht1 t1, pht2 t2, pht1_e t3 WHERE t1.b = t2.b AND t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
+SELECT avg(t1.a), avg(t2.b), avg(t3.a + t3.b), t1.c, t2.c, t3.c FROM pht1 t1, pht2 t2, pht1_e t3 WHERE t1.b = t2.b AND t1.c = t2.c AND ltrim(t3.c, 'A') = t1.c GROUP BY t1.c, t2.c, t3.c ORDER BY t1.c, t2.c, t3.c;
 
 --
 -- multiple levels of partitioning