Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
On Mon, Jan 7, 2008 at 9:01 AM, in message [EMAIL PROTECTED], Kevin Grittner [EMAIL PROTECTED] wrote: On Sun, Jan 6, 2008 at 7:20 PM, in message [EMAIL PROTECTED], Tom Lane [EMAIL PROTECTED] wrote: Kevin Grittner [EMAIL PROTECTED] 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! I see this didn't make it into 8.3RC1. Will it be in the 8.3.0 release? For us, 8.3RC1 performance looks great with the patch, horrible without. -Kevin ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
On Thu, Jan 17, 2008 at 12:30 PM, in message [EMAIL PROTECTED], Tom Lane [EMAIL PROTECTED] wrote: Kevin Grittner [EMAIL PROTECTED] writes: I see this didn't make it into 8.3RC1. Will it be in the 8.3.0 release? You mean this patch? http://archives.postgresql.org/pgsql-committers/2008-01/msg00151.php I'm not subscribed to the patches list, so I missed that. It appears to have been refined from the version posted to hackers a few days earlier, and applied to the trunk shortly after RC1. I'll check out the current tip and repeat the tests. Thanks, -Kevin ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
Kevin Grittner [EMAIL PROTECTED] writes: I see this didn't make it into 8.3RC1. Will it be in the 8.3.0 release? You mean this patch? http://archives.postgresql.org/pgsql-committers/2008-01/msg00151.php regards, tom lane ---(end of broadcast)--- TIP 7: You can help support the PostgreSQL project by donating at http://www.postgresql.org/about/donate
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
On Thu, Jan 17, 2008 at 1:35 PM, in message [EMAIL PROTECTED], Kevin Grittner [EMAIL PROTECTED] wrote: On Thu, Jan 17, 2008 at 12:30 PM, in message [EMAIL PROTECTED], Tom Lane [EMAIL PROTECTED] wrote: Kevin Grittner [EMAIL PROTECTED] writes: I see this didn't make it into 8.3RC1. Will it be in the 8.3.0 release? You mean this patch? http://archives.postgresql.org/pgsql-committers/2008-01/msg00151.php I'm not subscribed to the patches list, so I missed that. It appears to have been refined from the version posted to hackers a few days earlier, and applied to the trunk shortly after RC1. I'll check out the current tip and repeat the tests. I'll leave it running, but so far it's looking great. -Kevin ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
Alvaro Herrera [EMAIL PROTECTED] 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! ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
Gregory Stark [EMAIL PROTECTED] writes: Alvaro Herrera [EMAIL PROTECTED] writes: 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? Not more join clauses, but any join clause at all. We will not explore join paths that don't have any join clause, unless forced to by lack of any other way to form the result. Even though some of those joins are entirely redundant and have no selectivity? You're confusing whether we explore a path (ie, cost it out) with whether we choose it. It's a necessary precondition, of course, but we won't pick the path unless it looks cheapest. Not exploring clauseless join paths is a heuristic that's needed to avoid exponential growth of the search space in large join problems. AFAIK every System-R-derived planner has done this. As an example, consider t1 join t2 on (...) join t3 on (...) ... join t8 on (...) and for simplicity suppose that each ON condition relates the new table to the immediately preceding table, and that we can't derive any additional join conditions through transitivity. In this situation there are going to be only seven ways to form a two-base-relation joinrel, as long as we allow only clauseful joins. But there are 8*7/2 = 28 distinct ways to form a join if we consider all possible join pairs whether they have a join clause or not. At the three-base-relation level there will be 12 joinrels if we only consider clauseful pairs, or 56 if we don't. It gets worse as you go up, and most if not all of those additional joinrels represent entirely useless variations on the theme of let's stupidly compute a cartesian product and then winnow it sometime later. This is not to say that there is never a case where an early cartesian product couldn't be a useful part of a plan, but rejecting them is a darn good heuristic. regards, tom lane ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
Tom Lane [EMAIL PROTECTED] writes: As an example, consider t1 join t2 on (...) join t3 on (...) ... join t8 on (...) and for simplicity suppose that each ON condition relates the new table to the immediately preceding table, and that we can't derive any additional join conditions through transitivity. So the problem is that if we happen to have some x=const clause for any variable listed in those join clauses then we drop that clause entirely and end up delaying that join until the very end? So is the fact that the user provided a useless clause the only information we have that these tables might be related? So if I write (along with some other joins): t1 join t2 on (t1.x=t2.x) where t1.x=3 I'll get a different result than if I write t1, t2 where t1.x=3 and t2.x=3 ? Perhaps we could be going the other direction and trying to add redundant selectivity 1.0 clauses when we have multiple variables which come out to the same value? -- Gregory Stark EnterpriseDB http://www.enterprisedb.com Ask me about EnterpriseDB's Slony Replication support! ---(end of broadcast)--- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
Gregory Stark [EMAIL PROTECTED] writes: So if I write (along with some other joins): t1 join t2 on (t1.x=t2.x) where t1.x=3 I'll get a different result than if I write t1, t2 where t1.x=3 and t2.x=3 In 8.3 you won't, because those are in fact exactly equivalent (and the new EquivalenceClass machinery can prove it). The cases that are interesting are more like t1 LEFT join t2 on (t1.x=t2.x) where t1.x=3 which is not equivalent to the other construction, because t2.x is only sort-of-equal to 3. Hmm ... now that I look at this, it might be a good idea if have_relevant_eclass_joinclause() didn't skip ec_has_const EquivalenceClasses. That would give us the same behavior for simple inner-join cases that I'm advocating for outer joins, namely that we can consider an early join between two rels that are related in the fashion you show. We don't actually need to invent dummy join clauses to make that happen, because the join search code believes have_relevant_eclass_joinclause() even if it doesn't see a joinclause for itself ... regards, tom lane ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
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 Herrerahttp://www.CommandPrompt.com/ PostgreSQL Replication, Consulting, Custom Development, 24x7 support ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
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 binOJTxejPTPF.bin Description: const-propagation-8.2.patch ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
Alvaro Herrera [EMAIL PROTECTED] 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 ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
On Sun, Jan 6, 2008 at 7:20 PM, in message [EMAIL PROTECTED], Tom Lane [EMAIL PROTECTED] wrote: Kevin Grittner [EMAIL PROTECTED] 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=4 loops=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=15917 loops=1) - Subquery Scan CTHE (cost=148.89..1360.64 rows=15917 width=98) (actual time=10.499..263.746 rows=15917 loops=1) - Merge Left Join (cost=148.89..1201.47 rows=15917 width=77) (actual time=10.497..225.505 rows=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.104 rows=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.002 rows=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.879 rows=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.024 rows=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
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
On Fri, Jan 4, 2008 at 6:46 PM, in message [EMAIL PROTECTED], Tom Lane [EMAIL PROTECTED] wrote: 8.2 (at least at branch tip, can't say for sure about earlier dot-releases) 8.2.4 and 8.2.5 both behave this way. f2 | f3 | f1 ++ 53 || 53 (1 row) which I claim is the wrong answer. I agree that it is the wrong answer. the first question for you is whether it is intentional that your query joins CTHE to CHST rather than to CH. CTHE.eventType has to match to CHST; there is not an eventType column in CH. The other values could refer to either; I would expect that to be logically equivalent (unless I'm missing something). -Kevin ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
Kevin Grittner [EMAIL PROTECTED] 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 binR1Zq8ZpMll.bin Description: const-propagation-8.3.patch.gz ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
I wrote: It's possible that we could teach 8.3 to propagate the constant and keep the join condition in cases like this; I think we actually can do this without too big a change. The main problem is that initsplan.c doesn't put the upper outer join's clause into the list of mergejoinable outer-join clauses, because it's afraid that propagating a constant through such a clause might generate a wrong answer. The case that we're worried about involves propagating an equal-to-a-constant constraint into the inner (nullable) side of a lower outer join; this might result in the lower join generating null-extended rows that should not have appeared in its result (because the rows on its outer side actually did have matches in the inner side, but those matches were suppressed by removal of rows not matching the constant). However, I think this is all right as long as (1) the upper join's clause is strict, and (2) we still apply the upper join's clause as such, rather than discarding it. The upper clause will reject the null-extended rows so it doesn't matter that they really shouldn't have looked the way they did. Anyone see any flaws in that reasoning? To implement this, we should allow distribute_qual_to_rels to put mergejoinable outer-join clauses into the left/right_join_clauses lists, even if check_outerjoin_delay returned TRUE for them. However the result of check_outerjoin_delay has to be made available to reconsider_outer_join_clauses, so that it will know whether it can discard clauses or not. The easiest way to do that is to pass it as the RestrictInfo's outerjoin_delayed flag. This is effectively a small change in the meaning of outerjoin_delayed: it now is true if the clause is affected by any *lower* outer join, and so it isn't automatically set true for an outer-join clause. The old meaning can now be computed as outerjoin_delayed || !is_pushed_down, since these days is_pushed_down is false for exactly those clauses that are non-degenerated outer join clauses. (Maybe we should rename that flag ... but not right now.) There is actually only one place in the system that is testing outerjoin_delayed, so this is an easy change. Then in reconsider_outer_join_clauses, we can propagate constants through outer-join clauses if the clause is either strict or not outerjoin_delayed. However, after a successful propagation, we can drop the original clause only if it isn't outerjoin_delayed (otherwise we must keep it to suppress nulls). Also, reconsider_outer_join_clauses has to be fixed so that if it successfully deduces any constant constraints, it makes another pass over the list of outer-join clauses, stopping only when a pass makes no progress. This is because when we deduce INNERVAR = CONSTANT, we might now have another clause where INNERVAR is the outer side, and we could push the constant across to the lower join's inner side. In 8.2 we accomplished that by having sub_generate_join_implications recurse after making a deduction, but at the moment 8.3 is failing to do any such thing. (Hmm, maybe a cheaper fix is to order the outer-join clauses highest-to-lowest in the list to start with? This would mean merging the three lists into one, though, which seems to require adding a field to RestrictInfo so that we can tell what's what.) Comments? regards, tom lane ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
[HACKERS] OUTER JOIN performance regression remains in 8.3beta4
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. The query: SELECT CH.caseNo, CH.countyNo, CH.chargeNo, CH.statuteCite, CH.sevClsCode, CH.modSevClsCode, S.descr AS sevClsCodeDescr, M.descr AS modSevClsCodeDescr, CH.descr, CH.offenseDate, CH.pleaCode, PC.descr AS pleaCodeDescr, CH.pleaDate, CH.chargeSeqNo, CHST.eventDate AS reopEventDate, CTHE.descr AS reopEventDescr FROM Charge CH LEFT OUTER JOIN SevClsCode S ON (S.sevClsCode = CH.sevClsCode) LEFT OUTER JOIN SevClsCode M ON (M.sevClsCode = CH.modSevClsCode) LEFT OUTER JOIN PleaCode PC ON (PC.pleaCode = CH.pleaCode) LEFT OUTER JOIN CaseHist CHST ON ( CHST.countyNo = CH.countyNo AND CHST.caseNo= CH.caseNo AND CHST.histSeqNo = CH.reopHistSeqNo ) LEFT OUTER JOIN CaseTypeHistEvent CTHE ON ( CHST.eventType = CTHE.eventType AND CHST.caseType = CTHE.caseType AND CHST.countyNo = CTHE.countyNo ) WHERE CH.caseNo = '2007CM003476' AND CH.countyNo = 53 ORDER BY chargeNo, chargeSeqNo ; The attached EXPLAIN ANALYZE results show: (1) A run of the above under 8.3beta4. (2) A run of the above under 8.2.4. (3) A run of the above with all OUTER JOINs changed to INNER under 8.3beta4. -Kevin Sort (cost=101161.84..101161.85 rows=4 width=226) (actual time=113110.725..113110.731 rows=4 loops=1) Sort Key: CH.chargeNo, CH.chargeSeqNo Sort Method: quicksort Memory: 18kB - Hash Left Join (cost=82004.90..101161.80 rows=4 width=226) (actual time=110701.127..113110.637 rows=4 loops=1) Hash Cond: ((CH.sevClsCode)::bpchar = (S.sevClsCode)::bpchar) - Hash Left Join (cost=82003.36..101160.20 rows=4 width=195) (actual time=110701.005..113110.503 rows=4 loops=1) Hash Cond: ((CH.modSevClsCode)::bpchar = (M.sevClsCode)::bpchar) - Hash Left Join (cost=82001.82..101158.64 rows=4 width=164) (actual time=110700.858..113110.345 rows=4 loops=1) Hash Cond: ((CH.pleaCode)::bpchar = (PC.pleaCode)::bpchar) - Hash Left Join (cost=82000.60..101157.37 rows=4 width=128) (actual time=110700.720..113110.191 rows=4 loops=1) Hash Cond: (((CHST.eventType)::bpchar = (CTHE.eventType)::bpchar) AND ((CHST.caseType)::bpchar = (CTHE.caseType)::bpchar) AND ((CHST.countyNo)::smallint = (CTHE.countyNo)::smallint)) - Nested Loop Left Join (cost=0.00..87.70 rows=4 width=107) (actual time=0.189..0.241 rows=4 loops=1) - Index Scan using Charge_pkey on Charge CH (cost=0.00..10.32 rows=4 width=94) (actual time=0.174..0.186 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..19.32 rows=2 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=44597.18..44597.18 rows=1146024 width=98) (actual time=110700.290..110700.290 rows=1146024 loops=1) - Subquery Scan CTHE (cost=148.78..44597.18 rows=1146024 width=98) (actual time=14.673..92707.265 rows=1146024 loops=1) - Merge Left Join (cost=148.78..33136.94 rows=1146024 width=77) (actual time=14.668..72106.330 rows=1146024 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.79..23557.55 rows=1146024 width=67) (actual time=0.114..32623.571 rows=1146024 loops=1) - Index Scan using CaseTypeHistEventB_pkey on CaseTypeHistEventB b (cost=0.00..634.28 rows=15917 width=65) (actual time=0.071..2405.293 rows=15917 loops=1) - Materialize (cost=2.79..3.51 rows=72 width=2) (actual time=0.002..0.516 rows=72 loops=15917) - Seq Scan on ControlRecord c (cost=0.00..2.72 rows=72 width=2) (actual time=0.031..0.183 rows=72 loops=1) - Sort (cost=145.99..151.14 rows=2060 width=15) (actual time=14.530..207.873 rows=148249 loops=1)
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
On Fri, Jan 4, 2008 at 12:16 PM, in message [EMAIL PROTECTED], Kevin Grittner [EMAIL PROTECTED] wrote: problems remain in 8.3beta4. As I poked around at this, it started to seem familiar. I had previously posted about this query's performance under 8.2.4. http://archives.postgresql.org/pgsql-performance/2007-10/msg00087.php To summarize, under 8.2.4 it runs in less than half a millisecond if I set enable_hashjoin = off and thousand times that long with enable_hashjoin = on. Under 8.3beta4 this has jumped to 113114 ms. -Kevin ---(end of broadcast)--- TIP 7: You can help support the PostgreSQL project by donating at http://www.postgresql.org/about/donate
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
Kevin Grittner [EMAIL PROTECTED] writes: As I poked around at this, it started to seem familiar. I had previously posted about this query's performance under 8.2.4. http://archives.postgresql.org/pgsql-performance/2007-10/msg00087.php Well, that thread gave some of the missing details, such as Table public.ControlRecord Column | Type | Modifiers ++--- countyNo | CountyNoT| not null but what the heck is CountyNoT? It looks like 8.3 is failing to realize that it can propagate the countyNo = 53 condition down to this table's scan, as 8.2 did; but there's not enough details here to guess why not. regards, tom lane ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
On Fri, Jan 4, 2008 at 4:40 PM, in message [EMAIL PROTECTED], Tom Lane [EMAIL PROTECTED] wrote: what the heck is CountyNoT? bigbird=# \dD CountyNoT List of domains Schema | Name| Type | Modifier | Check +---+--+--+--- public | CountyNoT | smallint | | Should I post a list of all the domains in these tables, or is that one enough? -Kevin ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
On Fri, Jan 4, 2008 at 4:29 PM, in message [EMAIL PROTECTED], Tom Lane [EMAIL PROTECTED] wrote: Can't do much with this without seeing the table and view definitions involved. Understood. It was while I was putting that together that it struck me as familiar. They are the same as in this thread. http://archives.postgresql.org/pgsql-performance/2007-10/msg00087.php I didn't figure there was much point re-posting them versus referencing that thread, but I can do so if it's helpful. -Kevin ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
Kevin Grittner [EMAIL PROTECTED] 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. Can't do much with this without seeing the table and view definitions involved. regards, tom lane ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
On Fri, Jan 4, 2008 at 4:46 PM, in message [EMAIL PROTECTED], Tom Lane [EMAIL PROTECTED] wrote: nor mentions the data types involved. Schema | Name | Type| Modifier | Check +---+-+--+--- public | ArrestCaseNoT | character(12) | | public | ArrestTrackingNoT | character(14) | | public | BookCaseNoT | character(12) | | public | CalDurationT | numeric(6,2)| | public | CaseNoT | character(14) | | public | CaseTypeT | character(2)| | public | ChargeIdT | character varying(15) | | public | ChargeNoT | smallint| | public | ChargeSeqNoT | smallint| | public | ChargeStatusCodeT | character varying(2)| | public | CountyNoT | smallint| | public | CtofcNoT | character(4)| | public | DateT | date| | public | DispoCodeT| character(5)| | public | EventDescrT | character(50) | | public | EventTypeT| character(5)| | public | HistSeqNoT| smallint| | public | IssAgencyNoT | smallint| | public | JdgmtSeqNoT | smallint| | public | KeyEventSeqT | smallint| | public | MoneyT| numeric(13,2) | | public | OffenseDateRangeT | character varying(100) | | public | PdCodeT | character(2)| | public | PleaCodeT | character(4)| | public | PlntfAgencyNoT| smallint| | public | SccaCaseNoT | character varying(14) | | public | SevClsCodeT | character(2)| | public | StatuteCiteT | character(21) | | public | StatuteDescrT | character varying(100) | | public | StatuteSevSeqNoT | smallint| | public | TagTypeT | character(2)| | public | TapeCounterNoT| character(16) | | public | TapeLocT | character(18) | | public | TextT | character varying(2000) | | public | UserIdT | character(8)| | public | WcisClsCodeT | character(5)| | We're in the process of converting all of the char to varchar, but both the previous report and this one still have char as shown here. -Kevin ---(end of broadcast)--- TIP 7: You can help support the PostgreSQL project by donating at http://www.postgresql.org/about/donate
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
Kevin Grittner [EMAIL PROTECTED] writes: On Fri, Jan 4, 2008 at 4:29 PM, in message [EMAIL PROTECTED], Tom Lane [EMAIL PROTECTED] wrote: Can't do much with this without seeing the table and view definitions involved. Understood. It was while I was putting that together that it struck me as familiar. They are the same as in this thread. http://archives.postgresql.org/pgsql-performance/2007-10/msg00087.php I don't see anything in that thread that shows the view definition nor mentions the data types involved. regards, tom lane ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
On Fri, Jan 4, 2008 at 4:51 PM, in message [EMAIL PROTECTED], Kevin Grittner [EMAIL PROTECTED] wrote: keyEventSeqNo | integer | COALESCE( CASE WHEN d.eventType IS NOT NULL THEN d.keyEventSeqNo::smallint ELSE b.keyEventSeqNo::smallint END::integer, 0) AS keyEventSeqNo, That seems like a potential problem. I should probably be casting the literal of zero to HistSeqNoT. -Kevin ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
Hmm ... I think I've managed to invent a test case, and unfortunately for you, what it shows is that 8.2 is optimizing the query incorrectly. create table t1 (f1 int primary key); create table t2 (f2 int primary key); create table t3 (f3 int primary key); insert into t1 values(53); insert into t2 values(53); explain select * from t2 left join t3 on (f2 = f3) left join t1 on (f3 = f1) where f2 = 53; select * from t2 left join t3 on (f2 = f3) left join t1 on (f3 = f1) where f2 = 53; What I get from this in 8.3 is f2 | f3 | f1 ++ 53 || (1 row) whereas 8.2 (at least at branch tip, can't say for sure about earlier dot-releases) returns f2 | f3 | f1 ++ 53 || 53 (1 row) which I claim is the wrong answer. If there is no matching t3 row, then the first join should produce a null-extended row with f3=NULL, and this row *cannot* match the t1 row with f1=53. We should therefore again do a null-extension. 8.2 produces this plan: Nested Loop Left Join (cost=0.00..24.82 rows=1 width=12) - Nested Loop Left Join (cost=0.00..16.55 rows=1 width=8) - Index Scan using t2_pkey on t2 (cost=0.00..8.27 rows=1 width=4) Index Cond: (f2 = 53) - Index Scan using t3_pkey on t3 (cost=0.00..8.27 rows=1 width=4) Index Cond: (f3 = 53) - Index Scan using t1_pkey on t1 (cost=0.00..8.27 rows=1 width=4) Index Cond: (f1 = 53) which shows it has incorrectly propagated the constant to replace both of the join conditions. 8.3 is doing this: Nested Loop Left Join (cost=0.00..24.83 rows=1 width=12) - Index Scan using t2_pkey on t2 (cost=0.00..8.27 rows=1 width=4) Index Cond: (f2 = 53) - Nested Loop Left Join (cost=0.00..16.55 rows=1 width=8) - Index Scan using t3_pkey on t3 (cost=0.00..8.27 rows=1 width=4) Index Cond: (f3 = 53) - Index Scan using t1_pkey on t1 (cost=0.00..8.27 rows=1 width=4) Index Cond: (t3.f3 = t1.f1) which shows it has replaced the f2=f3 join condition with constants, which is safe, but has not replaced f3=f1. If we were to write select * from t2 left join t3 on (f2 = f3) left join t1 on (f2 = f1) where f2 = 53; then we get the three-constant-indexscans plan out of 8.3 as well. So the first question for you is whether it is intentional that your query joins CTHE to CHST rather than to CH. It's possible that we could teach 8.3 to propagate the constant and keep the join condition in cases like this; that is, after EquivalenceClass processing we'd want to have the clauses f2 = 53 f3 = 53 (8.3 already knows to deduce this) f1 = 53 (this is the one at issue) f1 = f3 where the last is not redundant because of the possibility that one side has gone to null by the time it's applied. However, the clause f1 = 53 is OK to invent and apply at the t1 table scan because any row not meeting this condition can certainly not contribute to the join result. (Anyone see any flaws in that reasoning?) I'm a bit hesitant to monkey with it at this late stage of the release process, though. BTW, the two plans above are just about equivalent both in cost and real-world performance, so it might look like propagating the constant condition to f1 isn't really worth doing anyway. The problem is that you've got a non-optimizable view in the way. Extending the example, create view v as select *,'dummy'::text AS junk from t1; explain select * from t2 left join t3 on (f2 = f3) left join v on (f3 = f1) where f2 = 53; 8.2 generates the same plan as before, whereas 8.3 produces Nested Loop Left Join (cost=0.00..104.55 rows=1 width=44) - Index Scan using t2_pkey on t2 (cost=0.00..8.27 rows=1 width=4) Index Cond: (f2 = 53) - Nested Loop Left Join (cost=0.00..96.27 rows=1 width=40) Join Filter: (t1.f1 = t3.f3) - Index Scan using t3_pkey on t3 (cost=0.00..8.27 rows=1 width=4) Index Cond: (f3 = 53) - Seq Scan on t1 (cost=0.00..34.00 rows=2400 width=4) and it's that seqscan that is killing performance. The reason for this is that the v view can't be flattened due to the non-nullable output column, so it has to be planned separately and you get a seqscan. If we generate the constant condition f1 = 53 then it can be pushed down into the view and so you get the indexscan anyhow, even though it's really a separate planner invocation doing that. Fixing this would involve some fooling with the machinations around the left_join_clauses and right_join_clauses lists --- not sure how big a patch would be needed. We've also got to think about un-breaking 8.2. [ Pokes at older branches... ] Oh, that's interesting, 8.1 seems to do the right thing already! Nested Loop Left Join (cost=0.00..16.50 rows=1 width=44) Join Filter: (outer.f3 = inner.f1) - Nested Loop Left Join (cost=0.00..10.66 rows=1 width=8) -
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
On Fri, Jan 4, 2008 at 5:45 PM, in message [EMAIL PROTECTED], Kevin Grittner [EMAIL PROTECTED] wrote: On Fri, Jan 4, 2008 at 4:51 PM, in message [EMAIL PROTECTED], Kevin Grittner [EMAIL PROTECTED] wrote: keyEventSeqNo | integer | COALESCE( CASE WHEN d.eventType IS NOT NULL THEN d.keyEventSeqNo::smallint ELSE b.keyEventSeqNo::smallint END::integer, 0) AS keyEventSeqNo, That seems like a potential problem. I should probably be casting the literal of zero to HistSeqNoT. The cast generated a marginally lower cost estimate for the same plan. With set enable_hashjoin = off a good plan is still chosen: Sort (cost=211993.38..211993.39 rows=4 width=226) (actual time=0.611..0.616 rows=4 loops=1) Sort Key: CH.chargeNo, CH.chargeSeqNo Sort Method: quicksort Memory: 18kB - Nested Loop Left Join (cost=200532.15..211993.34 rows=4 width=226) (actual time=0.461..0.587 rows=4 loops=1) Join Filter: ((PC.pleaCode)::bpchar = (CH.pleaCode)::bpchar) - Merge Left Join (cost=200531.04..211991.33 rows=4 width=190) (actual time=0.400..0.417 rows=4 loops=1) Merge Cond: (((CHST.eventType)::bpchar = (CTHE.eventType)::bpchar) AND ((CHST.caseType)::bpchar = (CTHE.caseType)::bpchar) AND ((CHST.countyNo)::smallint = (CTHE.countyNo)::smallint)) - Sort (cost=91.88..91.89 rows=4 width=169) (actual time=0.395..0.399 rows=4 loops=1) Sort Key: CHST.eventType, CHST.caseType, CHST.countyNo Sort Method: quicksort Memory: 18kB - Nested Loop Left Join (cost=14.13..91.84 rows=4 width=169) (actual time=0.324..0.374 rows=4 loops=1) - Merge Left Join (cost=14.13..14.31 rows=4 width=156) (actual time=0.315..0.346 rows=4 loops=1) Merge Cond: ((CH.sevClsCode)::bpchar = (S.sevClsCode)::bpchar) - Sort (cost=12.34..12.35 rows=4 width=125) (actual time=0.153..0.158 rows=4 loops=1) Sort Key: CH.sevClsCode Sort Method: quicksort Memory: 17kB - Merge Left Join (cost=12.15..12.30 rows=4 width=125) (actual time=0.097..0.111 rows=4 loops=1) Merge Cond: ((CH.modSevClsCode)::bpchar = (M.sevClsCode)::bpchar) - Sort (cost=10.36..10.37 rows=4 width=94) (actual time=0.092..0.096 rows=4 loops=1) Sort Key: CH.modSevClsCode Sort Method: quicksort Memory: 17kB - Index Scan using Charge_pkey on Charge CH (cost=0.00..10.32 rows=4 width=94) (actual time=0.047..0.059 rows=4 loops=1) Index Cond: (((countyNo)::smallint = 53) AND ((caseNo)::bpchar = '2007CM003476'::bpchar)) - Sort (cost=1.79..1.85 rows=24 width=34) (never executed) Sort Key: M.sevClsCode - Seq Scan on SevClsCode M (cost=0.00..1.24 rows=24 width=34) (never executed) - Sort (cost=1.79..1.85 rows=24 width=34) (actual time=0.122..0.140 rows=18 loops=1) Sort Key: S.sevClsCode Sort Method: quicksort Memory: 18kB - Seq Scan on SevClsCode S (cost=0.00..1.24 rows=24 width=34) (actual time=0.009..0.043 rows=24 loops=1) - Index Scan using CaseHist_pkey on CaseHist CHST (cost=0.00..19.36 rows=2 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)) - Materialize (cost=200439.15..214764.45 rows=1146024 width=98) (never executed) - Sort (cost=200439.15..203304.21 rows=1146024 width=98) (never executed) Sort Key: CTHE.eventType, CTHE.caseType, CTHE.countyNo - Subquery Scan CTHE (cost=148.78..41732.12 rows=1146024 width=98) (never executed) - Merge Left Join (cost=148.78..30271.88 rows=1146024 width=77) (never executed) Merge Cond: (((b.caseType)::bpchar = (d.caseType)::bpchar) AND ((b.eventType)::bpchar = (d.eventType)::bpchar)) Join Filter: ((d.countyNo)::smallint = (c.countyNo)::smallint) - Nested
Re: [HACKERS] OUTER JOIN performance regression remains in 8.3beta4
I wrote: [ Pokes at older branches... ] Oh, that's interesting, 8.1 seems to do the right thing already! Seems that 8.1 does the right thing for the wrong reason :-(. Just like 8.2, it falsely concludes that the f3 = f1 clause can be deleted, but it fails to get rid of every copy of it. The reason is that initsplan.c puts the clause onto the joinlist of every rel mentioned in its required_relids, but the eventual remove_join_clause_from_rels() call only takes it off of the joinlists of rels specifically mentioned in the clause. In this test case, 8.1 thinks that t2 is part of the required_relids for the upper join's clause, so f3 = f1 survives on that rel's joinlist and eventually gets applied when its required_relids are satisfied. But 8.2 has outer-join rearrangement ability, so it correctly figures that the required_relids for f3 = f1 shouldn't include t2, and that means that the remove_join_clause_from_rels() call manages to knock off every copy of the clause. The net effect of this seems to be that 8.1 will preserve a copy of a redundant outer-join clause if that clause appeared above any rels that it didn't explicitly mention. This is certainly not the design intention, and it probably results in clauses being sometimes uselessly kept. But it prevents the bug at hand, so I'm not inclined to touch the logic in 8.1 unless we realize there's another bug there. Not sure yet what to do to fix 8.2. The whole business of adding and then deleting join clauses was pretty ugly, and I'm happy it's gone in 8.3; but it doesn't seem very prudent to try to change that basic approach in 8.2. Somehow generate_outer_join_implications() needs to be smarter about which clauses are really safe to remove. regards, tom lane ---(end of broadcast)--- TIP 7: You can help support the PostgreSQL project by donating at http://www.postgresql.org/about/donate