Optimize complex join to use where condition before join

Hello,

I am facing a problem in optimizing the query shown below.

Most queries in the application do only find about 20 to 100 matching rows.

The query joins the table taufgaben_mitarbeiter to taufgaben on which a
condition like the following "where clause" is frequently used.

where
am.fmitarbeiter_id = 54

then there is a nested join to taufgaben -> tprojekt -> tkunden_kst ->
tkunden.

What I would like to achieve is that before joining all the tables that
the join of

taufgaben_mitarbeiter
(... from
taufgaben left join taufgaben_mitarbeiter am
on taufgaben.fid = am.faufgaben_id)

is done and that the where condition is evaluated. Than an index scan to join the other data is run.
What is happening at the moment (if I understood the explain analyze) is that the full join is done and at the end the where condition is done.

The query with seqscan and nestloop enabled takes about 3 seconds.
The query with both disabled takes 0.52 seconds
The query with only nestlop disabled takes 0.6 seconds
and
with only sesscan disabled takes about 3 seconds.

Below you can find the explain analyze from "seqscan and nestloop enabled" and from both disabled. The problem seems to be right at the beginning when the rows are badly estimated.
...
Merge Cond: ("outer".fid = "inner".faufgaben_id)"
" -> Nested Loop (cost=1621.51..1729.28 rows=6 width=2541) (actual time=328.000..3125.000 rows=1118 loops=1)"
...
I am using PostgreSQL 8.0 on Windows

Thank you for any idea

--
Kind Regards / Viele Grüße

Sebastian Hennebrueder

-----
http://www.laliluna.de/tutorials.html
Tutorials for Java, Struts, JavaServer Faces, JSP, Hibernate, EJB and more.

enabled seqscan and nested_loop

explain analyze
SELECT taufgaben.fid AS taufgaben_fid, taufgaben.fprojekt_id AS
taufgaben_fprojekt_id, taufgaben.fnummer AS taufgaben_fnummer,
taufgaben.fbudget AS taufgaben_fbudget, taufgaben.ftyp AS taufgaben_ftyp,
taufgaben.fberechnungsart AS taufgaben_fberechnungsart,
taufgaben.fverrechnung_extern AS taufgaben_fverrechnung_extern,
taufgaben.fverrechnungsbasis AS taufgaben_fverrechnungsbasis,
taufgaben.fstatus AS taufgaben_fstatus, taufgaben.fkurzbeschreibung AS
taufgaben_fkurzbeschreibung, taufgaben.fansprechpartner AS
taufgaben_fansprechpartner, taufgaben.fanforderer AS taufgaben_fanforderer,
taufgaben.fstandort_id AS taufgaben_fstandort_id, taufgaben.fwunschtermin
AS taufgaben_fwunschtermin, taufgaben.fstarttermin AS
taufgaben_fstarttermin, taufgaben.fgesamtaufwand AS
taufgaben_fgesamtaufwand, taufgaben.fistaufwand AS taufgaben_fistaufwand,
taufgaben.fprio AS taufgaben_fprio, taufgaben.ftester AS taufgaben_ftester,
taufgaben.ffaellig AS taufgaben_ffaellig, taufgaben.flevel AS
taufgaben_flevel, taufgaben.fkategorie AS taufgaben_fkategorie,
taufgaben.feintragbearbeitung AS taufgaben_feintragbearbeitung,
taufgaben.fbearbeitungsstatus AS taufgaben_fbearbeitungsstatus,
taufgaben.fsolllimit AS taufgaben_fsolllimit, taufgaben.fistlimit AS
taufgaben_fistlimit, taufgaben.fpauschalbetrag AS
taufgaben_fpauschalbetrag, taufgaben.frechnungslaeufe_id AS
taufgaben_frechnungslaeufe_id, taufgaben.fzuberechnen AS
taufgaben_fzuberechnen, tprojekte.fid AS tprojekte_fid,
tprojekte.fbezeichnung AS tprojekte_fbezeichnung, tprojekte.fprojektnummer
AS tprojekte_fprojektnummer, tprojekte.fbudget AS tprojekte_fbudget,
tprojekte.fverrechnung_extern AS tprojekte_fverrechnung_extern,
tprojekte.fstatus AS tprojekte_fstatus, tprojekte.fkunden_kst_id AS
tprojekte_fkunden_kst_id, tprojekte.fverrechnungsbasis AS
tprojekte_fverrechnungsbasis, tprojekte.fberechnungsart AS
tprojekte_fberechnungsart, tprojekte.fprojekttyp AS tprojekte_fprojekttyp,
tprojekte.fkostentraeger_id AS tprojekte_fkostentraeger_id,
tprojekte.fprojektleiter_id AS tprojekte_fprojektleiter_id,
tprojekte.fpauschalsatz AS tprojekte_fpauschalsatz,
tprojekte.frechnungslaeufe_id AS tprojekte_frechnungslaeufe_id,
tprojekte.fzuberechnen AS tprojekte_fzuberechnen, tprojekte.faufschlagrel
AS tprojekte_faufschlagrel, tprojekte.faufschlagabs AS
tprojekte_faufschlagabs, tprojekte.fbearbeitungsstatus AS
tprojekte_fbearbeitungsstatus, tuser.fusername AS tuser_fusername,
tuser.fpassword AS tuser_fpassword, tuser.fvorname AS tuser_fvorname,
tuser.fnachname AS tuser_fnachname, tuser.fismitarbeiter AS
tuser_fismitarbeiter, tuser.flevel AS tuser_flevel, tuser.fkuerzel AS
tuser_fkuerzel, taufgaben.floesungsbeschreibung AS
taufgaben_floesungsbeschreibung, taufgaben.ffehlerbeschreibung AS
taufgaben_ffehlerbeschreibung, taufgaben.faufgabenstellung AS
taufgaben_faufgabenstellung, taufgaben.fkritischeaenderungen AS
taufgaben_fkritischeaenderungen, taufgaben.fbdeaufgabenersteller_id AS
taufgaben_fbdeaufgabenersteller_id, taufgaben.fzufaktorieren AS
taufgaben_fzufaktorieren, tprojekte.fzufaktorieren AS
tprojekte_fzufaktorieren, taufgaben.fisdirty AS taufgaben_fisdirty,
taufgaben.fnf_kunde_stunden AS taufgaben_fnf_kunde_stunden,
taufgaben.fzf_kunde_stunden AS taufgaben_fzf_kunde_stunden,
taufgaben.fbf_kunde_stunden AS taufgaben_fbf_kunde_stunden,
taufgaben.fnf_kunde_betrag AS taufgaben_fnf_kunde_betrag,
taufgaben.fzf_kunde_betrag AS taufgaben_fzf_kunde_betrag,
taufgaben.fbf_kunde_betrag AS taufgaben_fbf_kunde_betrag,
tprojekte.feurobudget AS tprojekte_feurobudget, tprojekte.fnf_kunde_stunden
AS tprojekte_fnf_kunde_stunden, tprojekte.fzf_kunde_stunden AS
tprojekte_fzf_kunde_stunden, tprojekte.fbf_kunde_stunden AS
tprojekte_fbf_kunde_stunden, tprojekte.fnf_kunde_betrag AS
tprojekte_fnf_kunde_betrag, tprojekte.fzf_kunde_betrag AS
tprojekte_fzf_kunde_betrag, tprojekte.fbf_kunde_betrag AS
tprojekte_fbf_kunde_betrag, tprojekte.fisdirty AS tprojekte_fisdirty,
tprojekte.fgesamt_brutto_betrag AS tprojekte_fgesamt_brutto_betrag,
tprojekte.fgesamt_brutto_stunden AS tprojekte_fgesamt_brutto_stunden,
tprojekte.fgesamt_netto_stunden AS tprojekte_fgesamt_netto_stunden,
taufgaben.fgesamt_brutto_stunden AS taufgaben_fgesamt_brutto_stunden,
taufgaben.fgesamt_brutto_betrag AS taufgaben_fgesamt_brutto_betrag,
taufgaben.fhinweisgesendet AS taufgaben_fhinweisgesendet,
taufgaben.fwarnunggesendet AS taufgaben_fwarnunggesendet,
tprojekte.fhinweisgesendet AS tprojekte_fhinweisgesendet,
tprojekte.fwarnunggesendet AS tprojekte_fwarnunggesendet,
tuser.femailadresse AS tuser_femailadresse, taufgaben.fnfgesamtaufwand AS
taufgaben_fnfgesamtaufwand, taufgaben.fnf_netto_stunden AS
taufgaben_fnf_netto_stunden, taufgaben.fnf_brutto_stunden AS
taufgaben_fnf_brutto_stunden, taufgaben.fnfhinweisgesendet AS
taufgaben_fnfhinweisgesendet, taufgaben.fnfwarnunggesendet AS
taufgaben_fnfwarnunggesendet, tprojekte.fnfgesamtaufwand AS
tprojekte_fnfgesamtaufwand, tprojekte.fnf_netto_stunden AS
tprojekte_fnf_netto_stunden, tprojekte.fnf_brutto_stunden AS
tprojekte_fnf_brutto_stunden, tprojekte.fnfhinweisgesendet AS
tprojekte_fnfhinweisgesendet, tprojekte.fnfwarnunggesendet AS
tprojekte_fnfwarnunggesendet, taufgaben.fhatzeiten AS taufgaben_fhatzeiten,
tprojekte.fhatzeiten AS tprojekte_fhatzeiten,
taufgaben.fnichtpublicrechnungsfaehig AS
taufgaben_fnichtpublicrechnungsfaehig,
taufgaben.fnichtpublicrechnungsfaehigbetrag AS
taufgaben_fnichtpublicrechnungsfaehigbetrag, taufgaben.fnichtberechenbar AS
taufgaben_fnichtberechenbar, taufgaben.fnichtberechenbarbetrag AS
taufgaben_fnichtberechenbarbetrag, tprojekte.fnichtpublicrechnungsfaehig AS
tprojekte_fnichtpublicrechnungsfaehig,
tprojekte.fnichtpublicrechnungsfaehigbetrag AS
tprojekte_fnichtpublicrechnungsfaehigbetrag, tprojekte.fnichtberechenbar AS
tprojekte_fnichtberechenbar, tprojekte.fnichtberechenbarbetrag AS
tprojekte_fnichtberechenbarbetrag, taufgaben.finternertester AS
taufgaben_finternertester, taufgaben.finterngetestet AS
taufgaben_finterngetestet, tkunden_kst.fbezeichnung AS tkunden_kst_name,
tkunden.fname AS tkunden_name, tabteilungen.fname AS tabteilungen_fname,
tkostenstellen.fnummer AS tkostenstellen_fnummer, tkostentraeger.fnummer AS
tkostentraeger_fnummer, taufgaben.fanzahlbearbeiter AS
taufgaben_fanzahlbearbeiter, patchdaten.faufgaben_id AS pataid
FROM
taufgaben_mitarbeiter am
left join

((((((((taufgaben LEFT JOIN (
SELECT DISTINCT taufgaben_patches.faufgaben_id
FROM taufgaben_patches
ORDER BY taufgaben_patches.faufgaben_id
) patchdaten ON ((taufgaben.fid = patchdaten.faufgaben_id))) JOIN tprojekte
ON ((taufgaben.fprojekt_id = tprojekte.fid))) JOIN tuser ON
((tprojekte.fprojektleiter_id = tuser.fid))) JOIN tkunden_kst ON
((tprojekte.fkunden_kst_id = tkunden_kst.fid))) JOIN tkunden ON
((tkunden_kst.fkunden_id = tkunden.fid))) JOIN tkostentraeger ON
((tprojekte.fkostentraeger_id = tkostentraeger.fid))) JOIN
tkostenstellen ON ((tkostentraeger.fkostenstellen_id =
tkostenstellen.fid))) JOIN tabteilungen ON
((tkostenstellen.fabteilungen_id = tabteilungen.fid)))
on taufgaben.fid = am.faufgaben_id
where
am.fmitarbeiter_id = 54
and
taufgaben.fbearbeitungsstatus <> 2

"Merge Join (cost=1729.11..1837.08 rows=1 width=2541) (actual time=531.000..3125.000 rows=62 loops=1)"
" Merge Cond: ("outer".fid = "inner".faufgaben_id)"
" -> Nested Loop (cost=1621.51..1729.28 rows=6 width=2541) (actual time=328.000..3125.000 rows=1118 loops=1)"
" Join Filter: ("outer".fprojekt_id = "inner".fid)"
" -> Merge Left Join (cost=1490.70..1497.67 rows=1120 width=1047) (actual time=172.000..220.000 rows=1118 loops=1)"
" Merge Cond: ("outer".fid = "inner".faufgaben_id)"
" -> Sort (cost=1211.46..1214.26 rows=1120 width=1043) (actual time=109.000..109.000 rows=1118 loops=1)"
" Sort Key: taufgaben.fid"
" -> Seq Scan on taufgaben (cost=0.00..853.88 rows=1120 width=1043) (actual time=0.000..109.000 rows=1120 loops=1)"
" Filter: (fbearbeitungsstatus <> 2)"
" -> Sort (cost=279.23..279.73 rows=200 width=4) (actual time=63.000..63.000 rows=4773 loops=1)"
" Sort Key: patchdaten.faufgaben_id"
" -> Subquery Scan patchdaten (cost=0.00..271.59 rows=200 width=4) (actual time=0.000..31.000 rows=4773 loops=1)"
" -> Unique (cost=0.00..269.59 rows=200 width=4) (actual time=0.000..31.000 rows=4773 loops=1)"
" -> Index Scan using idx_aufpa_aufgabeid on taufgaben_patches (cost=0.00..253.74 rows=6340 width=4) (actual time=0.000..0.000 rows=6340 loops=1)"
" -> Materialize (cost=130.81..130.85 rows=4 width=1494) (actual time=0.140..0.877 rows=876 loops=1118)"
" -> Merge Join (cost=130.53..130.81 rows=4 width=1494) (actual time=156.000..203.000 rows=876 loops=1)"
" Merge Cond: ("outer".fkunden_id = "inner".fid)"
" -> Sort (cost=127.06..127.08 rows=6 width=1455) (actual time=156.000..156.000 rows=876 loops=1)"
" Sort Key: tkunden_kst.fkunden_id"
" -> Merge Join (cost=126.35..126.99 rows=6 width=1455) (actual time=109.000..140.000 rows=876 loops=1)"
" Merge Cond: ("outer".fprojektleiter_id = "inner".fid)"
" -> Sort (cost=118.57..118.59 rows=9 width=580) (actual time=109.000..109.000 rows=876 loops=1)"
" Sort Key: tprojekte.fprojektleiter_id"
" -> Merge Join (cost=117.89..118.43 rows=9 width=580) (actual time=62.000..93.000 rows=876 loops=1)"
" Merge Cond: ("outer".fkunden_kst_id = "inner".fid)"
" -> Sort (cost=114.61..114.69 rows=31 width=508) (actual time=62.000..62.000 rows=876 loops=1)"
" Sort Key: tprojekte.fkunden_kst_id"
" -> Merge Join (cost=109.11..113.84 rows=31 width=508) (actual time=31.000..62.000 rows=876 loops=1)"
" Merge Cond: ("outer".fid = "inner".fkostentraeger_id)"
" -> Sort (cost=13.40..13.42 rows=7 width=162) (actual time=0.000..0.000 rows=158 loops=1)"
" Sort Key: tkostentraeger.fid"
" -> Merge Join (cost=12.41..13.31 rows=7 width=162) (actual time=0.000..0.000 rows=158 loops=1)"
" Merge Cond: ("outer".fid = "inner".fkostenstellen_id)"
" -> Sort (cost=3.06..3.08 rows=7 width=119) (actual time=0.000..0.000 rows=19 loops=1)"
" Sort Key: tkostenstellen.fid"
" -> Merge Join (cost=2.76..2.96 rows=7 width=119) (actual time=0.000..0.000 rows=19 loops=1)"
" Merge Cond: ("outer".fabteilungen_id = "inner".fid)"
" -> Sort (cost=1.59..1.64 rows=19 width=55) (actual time=0.000..0.000 rows=19 loops=1)"
" Sort Key: tkostenstellen.fabteilungen_id"
" -> Seq Scan on tkostenstellen (cost=0.00..1.19 rows=19 width=55) (actual time=0.000..0.000 rows=19 loops=1)"
" -> Sort (cost=1.17..1.19 rows=7 width=76) (actual time=0.000..0.000 rows=19 loops=1)"
" Sort Key: tabteilungen.fid"
" -> Seq Scan on tabteilungen (cost=0.00..1.07 rows=7 width=76) (actual time=0.000..0.000 rows=7 loops=1)"
" -> Sort (cost=9.35..9.74 rows=158 width=55) (actual time=0.000..0.000 rows=158 loops=1)"
" Sort Key: tkostentraeger.fkostenstellen_id"
" -> Seq Scan on tkostentraeger (cost=0.00..3.58 rows=158 width=55) (actual time=0.000..0.000 rows=158 loops=1)"
" -> Sort (cost=95.71..97.90 rows=878 width=354) (actual time=31.000..31.000 rows=877 loops=1)"
" Sort Key: tprojekte.fkostentraeger_id"
" -> Seq Scan on tprojekte (cost=0.00..52.78 rows=878 width=354) (actual time=0.000..31.000 rows=878 loops=1)"
" -> Sort (cost=3.28..3.42 rows=58 width=80) (actual time=0.000..0.000 rows=892 loops=1)"
" Sort Key: tkunden_kst.fid"
" -> Seq Scan on tkunden_kst (cost=0.00..1.58 rows=58 width=80) (actual time=0.000..0.000 rows=58 loops=1)"
" -> Sort (cost=7.78..8.05 rows=109 width=883) (actual time=0.000..0.000 rows=950 loops=1)"
" Sort Key: tuser.fid"
" -> Seq Scan on tuser (cost=0.00..4.09 rows=109 width=883) (actual time=0.000..0.000 rows=109 loops=1)"
" -> Sort (cost=3.46..3.56 rows=40 width=51) (actual time=0.000..0.000 rows=887 loops=1)"
" Sort Key: tkunden.fid"
" -> Seq Scan on tkunden (cost=0.00..2.40 rows=40 width=51) (actual time=0.000..0.000 rows=40 loops=1)"
" -> Sort (cost=107.60..107.69 rows=35 width=4) (actual time=0.000..0.000 rows=765 loops=1)"
" Sort Key: am.faufgaben_id"
" -> Index Scan using idx_tauf_mit_mitid on taufgaben_mitarbeiter am (cost=0.00..106.70 rows=35 width=4) (actual time=0.000..0.000 rows=765 loops=1)"
" Index Cond: (fmitarbeiter_id = 54)"
"Total runtime: 3125.000 ms"

############################################################################
set enable_nestloop to off;
set enable_seqscan to off;

"Merge Join (cost=4230.83..4231.04 rows=1 width=2541) (actual time=485.000..500.000 rows=62 loops=1)"
" Merge Cond: ("outer".fid = "inner".faufgaben_id)"
" -> Sort (cost=4123.23..4123.24 rows=6 width=2541) (actual time=469.000..485.000 rows=1118 loops=1)"
" Sort Key: taufgaben.fid"
" -> Merge Join (cost=4117.47..4123.15 rows=6 width=2541) (actual time=297.000..406.000 rows=1120 loops=1)"
" Merge Cond: ("outer".fid = "inner".fprojekt_id)"
" -> Sort (cost=263.53..263.54 rows=4 width=1494) (actual time=141.000..141.000 rows=876 loops=1)"
" Sort Key: tprojekte.fid"
" -> Merge Join (cost=247.95..263.49 rows=4 width=1494) (actual time=94.000..109.000 rows=876 loops=1)"
" Merge Cond: ("outer".fprojektleiter_id = "inner".fid)"
" -> Sort (cost=247.95..247.96 rows=7 width=619) (actual time=94.000..94.000 rows=876 loops=1)"
" Sort Key: tprojekte.fprojektleiter_id"
" -> Merge Join (cost=246.86..247.85 rows=7 width=619) (actual time=47.000..78.000 rows=876 loops=1)"
" Merge Cond: ("outer".fkostentraeger_id = "inner".fid)"
" -> Sort (cost=222.01..222.45 rows=176 width=465) (actual time=47.000..47.000 rows=878 loops=1)"
" Sort Key: tprojekte.fkostentraeger_id"
" -> Merge Join (cost=20.63..215.44 rows=176 width=465) (actual time=0.000..32.000 rows=878 loops=1)"
" Merge Cond: ("outer".fid = "inner".fkunden_kst_id)"
" -> Sort (cost=20.63..20.73 rows=40 width=119) (actual time=0.000..0.000 rows=58 loops=1)"
" Sort Key: tkunden_kst.fid"
" -> Merge Join (cost=8.34..19.57 rows=40 width=119) (actual time=0.000..0.000 rows=58 loops=1)"
" Merge Cond: ("outer".fkunden_id = "inner".fid)"
" -> Sort (cost=8.34..8.48 rows=58 width=80) (actual time=0.000..0.000 rows=58 loops=1)"
" Sort Key: tkunden_kst.fkunden_id"
" -> Index Scan using pk__kunden_kst__30c33ec3 on tkunden_kst (cost=0.00..6.64 rows=58 width=80) (actual time=0.000..0.000 rows=58 loops=1)"
" -> Index Scan using tkunden_tbl_kunden_pk on tkunden (cost=0.00..10.44 rows=40 width=51) (actual time=0.000..0.000 rows=59 loops=1)"
" -> Index Scan using idx_kunden_kst_id on tprojekte (cost=0.00..190.66 rows=878 width=354) (actual time=0.000..0.000 rows=878 loops=1)"
" -> Sort (cost=24.86..24.87 rows=7 width=162) (actual time=0.000..0.000 rows=923 loops=1)"
" Sort Key: tkostentraeger.fid"
" -> Merge Join (cost=12.52..24.76 rows=7 width=162) (actual time=0.000..0.000 rows=158 loops=1)"
" Merge Cond: ("outer".fid = "inner".fkostenstellen_id)"
" -> Sort (cost=12.52..12.54 rows=7 width=119) (actual time=0.000..0.000 rows=19 loops=1)"
" Sort Key: tkostenstellen.fid"
" -> Merge Join (cost=0.00..12.42 rows=7 width=119) (actual time=0.000..0.000 rows=19 loops=1)"
" Merge Cond: ("outer".fabteilungen_id = "inner".fid)"
" -> Index Scan using abteilungkostenstellen on tkostenstellen (cost=0.00..6.21 rows=19 width=55) (actual time=0.000..0.000 rows=19 loops=1)"
" -> Index Scan using fld_id on tabteilungen (cost=0.00..6.08 rows=7 width=76) (actual time=0.000..0.000 rows=19 loops=1)"
" -> Index Scan using idx_kostenstellen_id on tkostentraeger (cost=0.00..11.74 rows=158 width=55) (actual time=0.000..0.000 rows=158 loops=1)"
" -> Index Scan using pk_tuser on tuser (cost=0.00..15.20 rows=109 width=883) (actual time=0.000..0.000 rows=950 loops=1)"
" -> Sort (cost=3853.94..3856.74 rows=1120 width=1047) (actual time=156.000..156.000 rows=1120 loops=1)"
" Sort Key: taufgaben.fprojekt_id"
" -> Merge Left Join (cost=279.23..3496.35 rows=1120 width=1047) (actual time=47.000..156.000 rows=1120 loops=1)"
" Merge Cond: ("outer".fid = "inner".faufgaben_id)"
" -> Index Scan using idx_taufgaben_fid on taufgaben (cost=0.00..3212.95 rows=1120 width=1043) (actual time=0.000..31.000 rows=1120 loops=1)"
" Filter: (fbearbeitungsstatus <> 2)"
" -> Sort (cost=279.23..279.73 rows=200 width=4) (actual time=47.000..47.000 rows=4773 loops=1)"
" Sort Key: patchdaten.faufgaben_id"
" -> Subquery Scan patchdaten (cost=0.00..271.59 rows=200 width=4) (actual time=0.000..31.000 rows=4773 loops=1)"
" -> Unique (cost=0.00..269.59 rows=200 width=4) (actual time=0.000..31.000 rows=4773 loops=1)"
" -> Index Scan using idx_aufpa_aufgabeid on taufgaben_patches (cost=0.00..253.74 rows=6340 width=4) (actual time=0.000..16.000 rows=6340 loops=1)"
" -> Sort (cost=107.60..107.69 rows=35 width=4) (actual time=0.000..0.000 rows=765 loops=1)"
" Sort Key: am.faufgaben_id"
" -> Index Scan using idx_tauf_mit_mitid on taufgaben_mitarbeiter am (cost=0.00..106.70 rows=35 width=4) (actual time=0.000..0.000 rows=765 loops=1)"
" Index Cond: (fmitarbeiter_id = 54)"
"Total runtime: 500.000 ms"