>You should examine the query plan. If you see table scans on large tables it's most definately bad. If you see it estimating more rows than you think should be output by a step then you may need to HINT the SQL to get it to use a better index for a JOIN or a WHERE. And that assumes you have an index that can be used to optimize the piece.
I will check for that next time. For now, the recommended approach by Sergey, by using the EXISTS, also mentioned in Naomi's message from the explanation on the issue, seems to have resolved the issue.