Thread: Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
"Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
> There was a serious performance regression in OUTER JOIN planning
> going from 8.2.4 to 8.2.5. I know Tom came up with some patches to
> mitigate the issues in 8.2.5, but my testing shows that problems
> remain in 8.3beta4.
Please try the attached proposed patch. It seems to fix my simplified
test case, but I'm not sure if there are any additional considerations
involved in your real queries.
This is against CVS HEAD but I think it will apply cleanly to beta4.
Haven't looked closely at how to fix 8.2, yet.
regards, tom lane
Attachment
>>> On Sun, Jan 6, 2008 at 7:20 PM, in message <29913.1199668810@sss.pgh.pa.us>,
Tom Lane <tgl@sss.pgh.pa.us> wrote:
> "Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
>> There was a serious performance regression in OUTER JOIN planning
>> going from 8.2.4 to 8.2.5. I know Tom came up with some patches to
>> mitigate the issues in 8.2.5, but my testing shows that problems
>> remain in 8.3beta4.
>
> Please try the attached proposed patch. It seems to fix my simplified
> test case, but I'm not sure if there are any additional considerations
> involved in your real queries.
Applied and built cleanly. Check found no errors. Startup clean.
Query returns expected rows. Plan looks good. Thanks!
-Kevin
Sort (cost=1789.74..1789.75 rows=5 width=226) (actual time=308.768..308.772 rows=4 loops=1)
Sort Key: "CH"."chargeNo", "CH"."chargeSeqNo"
Sort Method: quicksort Memory: 18kB
-> Hash Left Join (cost=1643.49..1789.68 rows=5 width=226) (actual time=308.630..308.723 rows=4 loops=1)
Hash Cond: (("CH"."sevClsCode")::bpchar = ("S"."sevClsCode")::bpchar)
-> Hash Left Join (cost=1641.95..1788.07 rows=5 width=195) (actual time=308.522..308.601 rows=4 loops=1)
Hash Cond: (("CH"."modSevClsCode")::bpchar = ("M"."sevClsCode")::bpchar)
-> Hash Left Join (cost=1640.41..1786.50 rows=5 width=164) (actual time=308.397..308.466 rows=4
loops=1)
Hash Cond: (("CH"."pleaCode")::bpchar = ("PC"."pleaCode")::bpchar)
-> Hash Left Join (cost=1639.19..1785.23 rows=5 width=128) (actual time=308.312..308.369 rows=4
loops=1)
Hash Cond: ((("CHST"."countyNo")::smallint = ("CTHE"."countyNo")::smallint) AND
(("CHST"."eventType")::bpchar= ("CTHE"."eventType")::bpchar) AND (("CHST"."caseType")::bpchar =
("CTHE"."caseType")::bpchar))
-> Nested Loop Left Join (cost=0.00..116.14 rows=5 width=107) (actual time=0.049..0.093
rows=4loops=1)
-> Index Scan using "Charge_pkey" on "Charge" "CH" (cost=0.00..12.01 rows=5
width=94)(actual time=0.037..0.047 rows=4 loops=1)
Index Cond: ((("countyNo")::smallint = 53) AND (("caseNo")::bpchar =
'2007CM003476'::bpchar))
-> Index Scan using "CaseHist_pkey" on "CaseHist" "CHST" (cost=0.00..20.79 rows=3
width=32)(actual time=0.002..0.002 rows=0 loops=4)
Index Cond: ((("CHST"."countyNo")::smallint = 53) AND (("CHST"."caseNo")::bpchar
='2007CM003476'::bpchar) AND (("CHST"."histSeqNo")::smallint = ("CH"."reopHistSeqNo")::smallint))
-> Hash (cost=1360.64..1360.64 rows=15917 width=98) (actual time=308.227..308.227
rows=15917loops=1)
-> Subquery Scan "CTHE" (cost=148.89..1360.64 rows=15917 width=98) (actual
time=10.499..263.746rows=15917 loops=1)
-> Merge Left Join (cost=148.89..1201.47 rows=15917 width=77) (actual
time=10.497..225.505rows=15917 loops=1)
Merge Cond: (((b."caseType")::bpchar = (d."caseType")::bpchar) AND
((b."eventType")::bpchar= (d."eventType")::bpchar))
Join Filter: ((d."countyNo")::smallint = (c."countyNo")::smallint)
-> Nested Loop (cost=2.90..953.87 rows=15917 width=67) (actual
time=0.071..150.104rows=15917 loops=1)
-> Index Scan using "CaseTypeHistEventB_pkey" on
"CaseTypeHistEventB"b (cost=0.00..632.63 rows=15917 width=65) (actual time=0.029..30.370 rows=15917 loops=1)
-> Materialize (cost=2.90..2.91 rows=1 width=2) (actual
time=0.001..0.002rows=1 loops=15917)
-> Seq Scan on "ControlRecord" c (cost=0.00..2.90 rows=1
width=2)(actual time=0.029..0.049 rows=1 loops=1)
Filter: (("countyNo")::smallint = 53)
-> Sort (cost=145.99..151.14 rows=2060 width=15) (actual
time=10.416..12.879rows=2060 loops=1)
Sort Key: d."caseType", d."eventType"
Sort Method: quicksort Memory: 145kB
-> Seq Scan on "CaseTypeHistEventD" d (cost=0.00..32.60 rows=2060
width=15)(actual time=0.023..3.177 rows=2060 loops=1)
-> Hash (cost=1.10..1.10 rows=10 width=41) (actual time=0.048..0.048 rows=10 loops=1)
-> Seq Scan on "PleaCode" "PC" (cost=0.00..1.10 rows=10 width=41) (actual
time=0.008..0.024rows=10 loops=1)
-> Hash (cost=1.24..1.24 rows=24 width=34) (actual time=0.106..0.106 rows=24 loops=1)
-> Seq Scan on "SevClsCode" "M" (cost=0.00..1.24 rows=24 width=34) (actual time=0.008..0.044
rows=24loops=1)
-> Hash (cost=1.24..1.24 rows=24 width=34) (actual time=0.089..0.089 rows=24 loops=1)
-> Seq Scan on "SevClsCode" "S" (cost=0.00..1.24 rows=24 width=34) (actual time=0.005..0.041 rows=24
loops=1)
Total runtime: 309.717 ms
I wrote:
> Haven't looked closely at how to fix 8.2, yet.
After some study it seems that the simplest, most reliable fix for 8.2
is to dike out the code that removes "redundant" outer join conditions
after propagating a constant across them. This gives the right answer
in the cases of concern (where we actually need the join condition) and
doesn't really add much overhead in the cases where we don't need it.
One small problem is that the join condition is redundant with the
generated constant-equality constraints (mostly so, even if not entirely
so) which will cause the planner to underestimate the size of the join,
since clausesel.c is not very bright at all about redundant conditions.
However, we already have a hack we can use for that: we can force the
cached selectivity estimate for the join clause to 1.0, so that it's
not considered to reduce the join size any more than the constant
conditions already did. (This is also a problem in my earlier patch
for 8.3, with the same fix possible.)
That leads to the attached very simple patch. There is some dead code
left behind, but it doesn't seem worth removing it.
I'm rather tempted to patch 8.1 similarly, even though it doesn't fail
on the known test case --- I'm far from convinced that there are no
related cases that will make it fail, and in any case it's getting the
selectivity wrong. 8.0 and before don't try to propagate constants
like this, so they're not at risk.
Comparing the behavior of this to my patch for HEAD, I am coming to the
conclusion that this is actually a *better* planning method than
removing the redundant join conditions, even when they're truly
rendundant! The reason emerges as soon as you look at cases involving
more than a single join. If we strip the join condition from just one
of the joins, then we find that the planner insists on doing that join
last, whether it's a good idea or not, because clauseful joins are
always preferred to clauseless joins in the join search logic. What's
worse, knowing that this is an outer join, is that the only available
plan type for a clauseless outer join is a NestLoop with the inner side
on the right, which again may be a highly nonoptimal way to do it.
None of this matters a whole lot if the pushed-down constant conditions
select single rows, but it does if they select multiple rows. I'm
trying this in the regression database:
select * from tenk1 a left join tenk1 b on (a.hundred = b.hundred)
left join tenk1 c on (b.hundred = c.hundred) where a.hundred = 42;
and finding patched 8.2 about 2X faster than 8.3 because it selects a
better plan that avoids multiple rescans of subplans.
So I'm coming around to the idea that getting rid of the "redundant"
join conditions is foolish micro-optimization, and we should leave
them in place even when we know they're redundant. The extra execution
cycles paid to test the condition don't amount to much in any case,
and the risk of getting a bad plan is too high.
This is a reasonably simple adjustment to my prior patch for 8.3,
which I will go ahead and make if there are no objections...
regards, tom lane
Attachment
Tom Lane wrote: > Comparing the behavior of this to my patch for HEAD, I am coming to the > conclusion that this is actually a *better* planning method than > removing the redundant join conditions, even when they're truly > rendundant! The reason emerges as soon as you look at cases involving > more than a single join. If we strip the join condition from just one > of the joins, then we find that the planner insists on doing that join > last, whether it's a good idea or not, because clauseful joins are > always preferred to clauseless joins in the join search logic. Would it be a good idea to keep removing redundant clauses and rethink the preference for clauseful joins, going forward? -- Alvaro Herrera http://www.CommandPrompt.com/ PostgreSQL Replication, Consulting, Custom Development, 24x7 support
Alvaro Herrera <alvherre@commandprompt.com> writes:
> Would it be a good idea to keep removing redundant clauses and rethink
> the preference for clauseful joins, going forward?
No --- it would create an exponential growth in planning time for large
join problems, while not actually buying anything in the typical case.
It's possible that we could do something along the lines of inserting
"dummy" join conditions, to allow particular join paths to be explored,
without generating any clause that actually requires work at runtime.
I'm not convinced this complication is needed though; at least not if
the only thing it's good for is this rather specialized optimization
rule.
regards, tom lane
"Alvaro Herrera" <alvherre@commandprompt.com> writes: > Tom Lane wrote: > >> Comparing the behavior of this to my patch for HEAD, I am coming to the >> conclusion that this is actually a *better* planning method than >> removing the redundant join conditions, even when they're truly >> rendundant! The reason emerges as soon as you look at cases involving >> more than a single join. If we strip the join condition from just one >> of the joins, then we find that the planner insists on doing that join >> last, whether it's a good idea or not, because clauseful joins are >> always preferred to clauseless joins in the join search logic. > > Would it be a good idea to keep removing redundant clauses and rethink > the preference for clauseful joins, going forward? I don't understand what's going on here. The planner is choosing one join order over another because one join has more join clauses than the other? Even though some of those joins are entirely redundant and have no selectivity? That seems like a fortuitous choice made on entirely meaningless data. Is there some other source of data we could use to make this decision instead of the number of clauses? I would suggest the selectivity but from the sound of it that's not going to help at all. -- Gregory Stark EnterpriseDB http://www.enterprisedb.com Ask me about EnterpriseDB's RemoteDBA services!