Fix old corner-case logic error in final_cost_nestloop().

tglsfdc · tglsfdc · commit 23886581b58c · 2017-06-03T13:48:15.000-04:00
When costing a nestloop with stop-at-first-inner-match semantics, and a non-indexscan inner path, final_cost_nestloop() wants to charge the full scan cost of the inner rel at least once, with additional scans charged at inner_rescan_run_cost which might be less. However the logic for doing this effectively assumed that outer_matched_rows is at least 1. If it's zero, which is not unlikely for a small outer rel, we ended up charging inner_run_cost plus N times inner_rescan_run_cost, as much as double the correct charge for an outer rel with only one row that we're betting won't be matched. (Unless the inner rel is materialized, in which case it has very small inner_rescan_run_cost and the cost is not so far off what it should have been.) The upshot of this was that the planner had a tendency to select plans that failed to make effective use of the stop-at-first-inner-match semantics, and that might have Materialize nodes in them even when the predicted number of executions of the Materialize subplan was only 1. This was not so obvious before commit 9c7f522, because the case only arose in connection with semi/anti joins where there's not freedom to reverse the join order. But with the addition of unique-inner joins, it could result in some fairly bad planning choices, as reported by Teodor Sigaev. Indeed, some of the test cases added by that commit have plans that look dubious on closer inspection, and are changed by this patch. Fix the logic to ensure that we don't charge for too many inner scans. I chose to adjust it so that the full-freight scan cost is associated with an unmatched outer row if possible, not a matched one, since that seems like a better model of what would happen at runtime. This is a longstanding bug, but given the lesser impact in back branches, and the lack of field complaints, I won't risk a back-patch. Discussion: https://postgr.es/m/CAKJS1f-LzkUsFxdJ_-Luy38orQ+AdEXM5o+vANR+-pHAWPSecg@mail.gmail.com
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
@@ -2214,6 +2214,7 @@ final_cost_nestloop(PlannerInfo *root, NestPath *path,
 		Cost		inner_run_cost = workspace->inner_run_cost;
 		Cost		inner_rescan_run_cost = workspace->inner_rescan_run_cost;
 		double		outer_matched_rows;
+		double		outer_unmatched_rows;
 		Selectivity inner_scan_frac;
 
 		/*
@@ -2226,6 +2227,7 @@ final_cost_nestloop(PlannerInfo *root, NestPath *path,
 		 * least 1, no such clamp is needed now.)
 		 */
 		outer_matched_rows = rint(outer_path_rows * extra->semifactors.outer_match_frac);
+		outer_unmatched_rows = outer_path_rows - outer_matched_rows;
 		inner_scan_frac = 2.0 / (extra->semifactors.match_count + 1.0);
 
 		/*
@@ -2269,7 +2271,7 @@ final_cost_nestloop(PlannerInfo *root, NestPath *path,
 			 * of a nonempty scan.  We consider that these are all rescans,
 			 * since we used inner_run_cost once already.
 			 */
-			run_cost += (outer_path_rows - outer_matched_rows) *
+			run_cost += outer_unmatched_rows *
 				inner_rescan_run_cost / inner_path_rows;
 
 			/*
@@ -2287,20 +2289,28 @@ final_cost_nestloop(PlannerInfo *root, NestPath *path,
 			 * difficult to estimate whether that will happen (and it could
 			 * not happen if there are any unmatched outer rows!), so be
 			 * conservative and always charge the whole first-scan cost once.
+			 * We consider this charge to correspond to the first unmatched
+			 * outer row, unless there isn't one in our estimate, in which
+			 * case blame it on the first matched row.
 			 */
+
+			/* First, count all unmatched join tuples as being processed */
+			ntuples += outer_unmatched_rows * inner_path_rows;
+
+			/* Now add the forced full scan, and decrement appropriate count */
 			run_cost += inner_run_cost;
+			if (outer_unmatched_rows >= 1)
+				outer_unmatched_rows -= 1;
+			else
+				outer_matched_rows -= 1;
 
 			/* Add inner run cost for additional outer tuples having matches */
-			if (outer_matched_rows > 1)
-				run_cost += (outer_matched_rows - 1) * inner_rescan_run_cost * inner_scan_frac;
-
-			/* Add inner run cost for unmatched outer tuples */
-			run_cost += (outer_path_rows - outer_matched_rows) *
-				inner_rescan_run_cost;
+			if (outer_matched_rows > 0)
+				run_cost += outer_matched_rows * inner_rescan_run_cost * inner_scan_frac;
 
-			/* And count the unmatched join tuples as being processed */
-			ntuples += (outer_path_rows - outer_matched_rows) *
-				inner_path_rows;
+			/* Add inner run cost for additional unmatched outer tuples */
+			if (outer_unmatched_rows > 0)
+				run_cost += outer_unmatched_rows * inner_rescan_run_cost;
 		}
 	}
 	else
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
@@ -5476,48 +5476,44 @@ select * from j1 natural join j2;
 explain (verbose, costs off)
 select * from j1
 inner join (select distinct id from j3) j3 on j1.id = j3.id;
-                  QUERY PLAN                   
------------------------------------------------
+               QUERY PLAN                
+-----------------------------------------
  Nested Loop
    Output: j1.id, j3.id
    Inner Unique: true
    Join Filter: (j1.id = j3.id)
-   ->  Seq Scan on public.j1
-         Output: j1.id
-   ->  Materialize
+   ->  Unique
          Output: j3.id
-         ->  Unique
+         ->  Sort
                Output: j3.id
-               ->  Sort
+               Sort Key: j3.id
+               ->  Seq Scan on public.j3
                      Output: j3.id
-                     Sort Key: j3.id
-                     ->  Seq Scan on public.j3
-                           Output: j3.id
-(15 rows)
+   ->  Seq Scan on public.j1
+         Output: j1.id
+(13 rows)
 
 -- ensure group by clause allows the inner to become unique
 explain (verbose, costs off)
 select * from j1
 inner join (select id from j3 group by id) j3 on j1.id = j3.id;
-                  QUERY PLAN                   
------------------------------------------------
+               QUERY PLAN                
+-----------------------------------------
  Nested Loop
    Output: j1.id, j3.id
    Inner Unique: true
    Join Filter: (j1.id = j3.id)
-   ->  Seq Scan on public.j1
-         Output: j1.id
-   ->  Materialize
+   ->  Group
          Output: j3.id
-         ->  Group
+         Group Key: j3.id
+         ->  Sort
                Output: j3.id
-               Group Key: j3.id
-               ->  Sort
+               Sort Key: j3.id
+               ->  Seq Scan on public.j3
                      Output: j3.id
-                     Sort Key: j3.id
-                     ->  Seq Scan on public.j3
-                           Output: j3.id
-(16 rows)
+   ->  Seq Scan on public.j1
+         Output: j1.id
+(14 rows)
 
 drop table j1;
 drop table j2;
@@ -5558,13 +5554,11 @@ inner join j2 on j1.id1 = j2.id1 and j1.id2 = j2.id2;
    Output: j1.id1, j1.id2, j2.id1, j2.id2
    Inner Unique: true
    Join Filter: ((j1.id1 = j2.id1) AND (j1.id2 = j2.id2))
+   ->  Seq Scan on public.j2
+         Output: j2.id1, j2.id2
    ->  Seq Scan on public.j1
          Output: j1.id1, j1.id2
-   ->  Materialize
-         Output: j2.id1, j2.id2
-         ->  Seq Scan on public.j2
-               Output: j2.id1, j2.id2
-(10 rows)
+(8 rows)
 
 -- ensure we don't detect the join to be unique when quals are not part of the
 -- join condition
