Thread: 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
Attachment
>>> On Fri, Jan 4, 2008 at 12:16 PM, in message <477E238D.EE98.0025.0@wicourts.gov>, "Kevin Grittner" <Kevin.Grittner@wicourts.gov> 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
"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.
Can't do much with this without seeing the table and view definitions
involved.
regards, tom lane
"Kevin Grittner" <Kevin.Grittner@wicourts.gov> 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
>>> On Fri, Jan 4, 2008 at 4:29 PM, in message <23789.1199485772@sss.pgh.pa.us>, Tom Lane <tgl@sss.pgh.pa.us> 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
>>> On Fri, Jan 4, 2008 at 4:40 PM, in message <23936.1199486422@sss.pgh.pa.us>, Tom Lane <tgl@sss.pgh.pa.us> wrote: > what the heck is "CountyNoT"? bigbird=# \dD "CountyNoT" List of domainsSchema | 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
"Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes: > On Fri, Jan 4, 2008 at 4:29 PM, in message <23789.1199485772@sss.pgh.pa.us>, > Tom Lane <tgl@sss.pgh.pa.us> 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
>>> On Fri, Jan 4, 2008 at 4:46 PM, in message <24033.1199486819@sss.pgh.pa.us>, Tom Lane <tgl@sss.pgh.pa.us> wrote: > I don't see anything in that thread that shows the view definition It was in the first post on the other thread, but for convenience: bigbird=# \d "CaseTypeHistEvent" View "public.CaseTypeHistEvent" Column | Type | Modifiers ----------------+---------------+-----------caseType | "CaseTypeT" |eventType | "EventTypeT" |descr | "EventDescrT" |isActive | boolean |isKeyEvent | boolean |isMoneyEnabled | boolean |keyEventSeqNo | integer |countyNo | "CountyNoT" | View definition:SELECT b."caseType", b."eventType", b.descr, b."isActive", CASE WHEN d."eventType" IS NOTNULL THEN d."isKeyEvent" ELSE b."isKeyEvent" END AS "isKeyEvent", CASE WHEN d."eventType"IS NOT NULL THEN d."isMoneyEnabled" ELSE b."isMoneyEnabled" END AS "isMoneyEnabled", COALESCE( CASE WHEN d."eventType" IS NOT NULL THEN d."keyEventSeqNo"::smallint ELSE b."keyEventSeqNo"::smallint END::integer, 0) AS "keyEventSeqNo", c."countyNo" FROM ONLY "CaseTypeHistEventB" b JOINONLY "ControlRecord" c ON 1 = 1 LEFT JOIN ONLY "CaseTypeHistEventD" d ON d."caseType"::bpchar = b."caseType"::bpcharAND d."eventType"::bpchar = b."eventType"::bpchar AND d."countyNo"::smallint = c."countyNo"::smallint; > nor mentions the data types involved. I'll pull those together and post shortly. All are domains without modifiers or checks. -Kevin
>>> On Fri, Jan 4, 2008 at 4:46 PM, in message <24033.1199486819@sss.pgh.pa.us>,
Tom Lane <tgl@sss.pgh.pa.us> 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 |
charactervarying(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
>>> On Fri, Jan 4, 2008 at 4:51 PM, in message <477E640F.EE98.0025.0@wicourts.gov>, "Kevin Grittner" <Kevin.Grittner@wicourts.gov> 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
>>> On Fri, Jan 4, 2008 at 5:45 PM, in message
<477E70B1.EE98.0025.0@wicourts.gov>, "Kevin Grittner"
<Kevin.Grittner@wicourts.gov> wrote:
>>>> On Fri, Jan 4, 2008 at 4:51 PM, in message
> <477E640F.EE98.0025.0@wicourts.gov>, "Kevin Grittner"
> <Kevin.Grittner@wicourts.gov> 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.616rows=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)
JoinFilter: (("PC"."pleaCode")::bpchar = ("CH"."pleaCode")::bpchar) -> Merge Left Join
(cost=200531.04..211991.33rows=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.89rows=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.111rows=4 loops=1) Merge Cond: (("CH"."modSevClsCode")::bpchar
=("M"."sevClsCode")::bpchar) -> Sort (cost=10.36..10.37 rows=4 width=94)
(actualtime=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.24rows=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.002rows=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)
(neverexecuted) -> Sort (cost=200439.15..203304.21 rows=1146024 width=98) (never executed)
Sort Key: "CTHE"."eventType", "CTHE"."caseType", "CTHE"."countyNo" ->
SubqueryScan "CTHE" (cost=148.78..41732.12 rows=1146024 width=98) (never executed) ->
MergeLeft Join (cost=148.78..30271.88 rows=1146024 width=77) (never executed)
MergeCond: (((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) (never executed)
-> Index Scan using "CaseTypeHistEventB_pkey" on "CaseTypeHistEventB" b (cost=0.00..634.28
rows=15917width=65) (never executed) -> Materialize (cost=2.79..3.51
rows=72width=2) (never executed) -> Seq Scan on "ControlRecord" c
(cost=0.00..2.72rows=72 width=2) (never executed) -> Sort (cost=145.99..151.14
rows=2060width=15) (never executed) Sort Key: d."caseType", d."eventType"
-> Seq Scan on "CaseTypeHistEventD" d (cost=0.00..32.60 rows=2060 width=15)
(neverexecuted) -> Materialize (cost=1.11..1.21 rows=10 width=41) (actual time=0.004..0.023 rows=10 loops=4)
-> Seq Scan on "PleaCode" "PC" (cost=0.00..1.10 rows=10 width=41) (actual time=0.007..0.021 rows=10
loops=1)Totalruntime: 1.070 ms
-Kevin
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
usingt1_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
Scanusing t3_pkey on t3 (cost=0.00..8.27 rows=1 width=4) Index Cond: (f3 = 53) -> Index Scan
usingt1_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 clausesf2 = 53f3 = 53 (8.3 already knows to deduce this)f1 = 53 (this is
theone 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) -> Index Scan using t2_pkey on t2 (cost=0.00..5.82 rows=1 width=4)
Index Cond: (f2 = 53) -> Index Scan using t3_pkey on t3 (cost=0.00..4.82 rows=1 width=4)
IndexCond: (f3 = 53) -> Index Scan using t1_pkey on t1 (cost=0.00..5.82 rows=1 width=4) Index Cond: (f1 =
53)
I wonder where along the line it got broken?
regards, tom lane
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
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
"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
>>> On Fri, Jan 4, 2008 at 6:46 PM, in message <25278.1199493975@sss.pgh.pa.us>, Tom Lane <tgl@sss.pgh.pa.us> 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
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!
Gregory Stark <stark@enterprisedb.com> writes:
> "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?
> 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, considert1 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
"Tom Lane" <tgl@sss.pgh.pa.us> 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!
Gregory Stark <stark@enterprisedb.com> 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
>>> On Mon, Jan 7, 2008 at 9:01 AM, in message <4781EA7E.EE98.0025.0@wicourts.gov>, "Kevin Grittner" <Kevin.Grittner@wicourts.gov> wrote: >>>> 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! 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
"Kevin Grittner" <Kevin.Grittner@wicourts.gov> 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
>>> On Thu, Jan 17, 2008 at 12:30 PM, in message <11352.1200594651@sss.pgh.pa.us>, Tom Lane <tgl@sss.pgh.pa.us> wrote: > "Kevin Grittner" <Kevin.Grittner@wicourts.gov> 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
>>> On Thu, Jan 17, 2008 at 1:35 PM, in message <478F5985.EE98.0025.0@wicourts.gov>, "Kevin Grittner" <Kevin.Grittner@wicourts.gov> wrote: >>>> On Thu, Jan 17, 2008 at 12:30 PM, in message <11352.1200594651@sss.pgh.pa.us>, > Tom Lane <tgl@sss.pgh.pa.us> wrote: >> "Kevin Grittner" <Kevin.Grittner@wicourts.gov> 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