SQL Newbie needs urgently help! [optimizing query]

[Toxic Head]

Hi all,

I've to optimize an Sql, which is called multiple times to create a tree of valid products.

I've tree Tables:
Products [more than 800.000 entries]
Categories [more than 80.000 entries]
Cat2ProdRel [more than 1.400.000 entries]

now I've to execute a query like this...

explain SELECT item_t0.PK
FROM Products item_t0
WHERE ( item_t0.PK IN ( {A big list of Product Keys} ))
AND (item_t0.TypePkString IN ( {a shorter List if Type Keys} )
AND (( item_t0.p_approvalstatus = { one state Key } )
AND (EXISTS
(SELECT item_t1.PK
FROM Categories item_t1 JOIN Cat2ProdRel item_t2
ON item_t1.PK = item_t2.SourcePK
WHERE ( item_t2.TargetPK = item_t0.PK )
AND ((item_t1.TypePkString IN ( { two type Keys } )
AND (( item_t1.p_catalogversion IN ( { short list of version keys } )))
AND item_t2.TypePkString = { one Type Key } ))))
AND (( item_t0.p_onlinedate IS NULL OR item_t0.p_onlinedate <= '2007-01-09 00:00:00.0' )
AND ( item_t0.p_offlinedate IS NULL OR item_t0.p_offlinedate >= '2007-01-09 00:00:00.0' ))) )

This statement will run 50 sek+ so the creation of the product tree will be very slow.

So my question for the sql professionals:

How can I speed up the query so that I get acceptable results?
I'm a absolutely newbie on sql and this tuning is very urgent.
Any help would be very appreciated.

Many ThanX in advance
Toxic