From 23886581b58c7e5d005d6346c0024a45801cc5a9 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Sat, 3 Jun 2017 13:48:15 -0400 Subject: [PATCH] Fix old corner-case logic error in final_cost_nestloop(). 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 9c7f5229a, 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 --- src/backend/optimizer/path/costsize.c | 30 ++++++++++------ src/test/regress/expected/join.out | 50 ++++++++++++--------------- 2 files changed, 42 insertions(+), 38 deletions(-) diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index cdb18d978d..f062c6b9f1 100644 --- 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 index d08b1e1ae5..9cad4e6992 100644 --- 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 -- 2.40.0