A straight SQL join statement is running horribly slow on my DB and our DBA can offer no suggestions for tuning.

Five million rows isn't that large, if the system is properly sized for it, and the database is tuned correctly. (which may be big 'if's).

I know nothing about your data, or what database you're using, so it's really hard to give specific help. (for instance, you can override Oracle's join behavior by giving hints). Even in other languages, exactly how you write your SQL can result in you doing a sort-merge join vs. a correlated join... In some situations, indexes can hurt you, and you'll want to make sure the tables are properly analyzed by the database so it knows when those times are. EXPLAIN PLAN in Oracle, and EXPLAIN in mySQL are your friends.

(I'm not going to say that your DBA hasn't already done this ... but I've worked with a few DBAs who weren't much more than an operator on a mainframe. Your database might not be tuned for this sort of operation, but that's no reason that you shouldn't be able to perform this in SQL, with a little prep work.)