speeding up INTERSECT/EXCEPT

I've searched the archives and docs without finding any help on this.

I want to use:

select * from rel1 except select * from rel2;

where rel1 and and rel2 each currently have about 2000 records and are likely to grow to twice that size or more.

The query works but takes inordinately long. Looking at the query plan, it seems that the statement is being executed using a nested scan, so the query is taking time proportional to the product of the sizes of the two relations. The result set will usually be a few hundred records.

My question: are there any indices I could define on the relations that would speed up the query? Since noting the problem, I've added an index on one of the fields (the same for both relations). Another index covers 7 of the fields in both relations (7 because that is the maximum for an index). Creating these indices made no difference in the query plan nor in the execution time of the query.

Should I pursue this approach further or do the differencing outside of the database?

-- Carl Hauser
-- Xerox Palo Alto Research Center