>The fields used as join conditions are indexed in both tables and are both the same size and data type (char 15). Any one have an idea where to start looking?

I'm far from an expert, but i think if it's a complex join, you need to index the same way. ex: Join a..b on a.f1+a.f2 = b.f1+b.f2 you need to index on f1+f2.

If you already know this, it sounds dumb, but I learned the hard way: When creating the index, do NOT use the name.field convention - it'll make the index not optimizable. I took the table-name out of the index, and the optimization level of my query went from none to full. (use sys(3054,1) to enable the output of optimization levels, it's a useful diagnostic)