I followed your advice and created indexes, one at a time.

Having an index on each of the columns has reduced response time for the query:

select count(*) from theTable A inner join theTable B where A.column_1 = 123 and B_column_1 = 456 and A.column_2 = B.column_2;

to 30-seconds. A seven fold improvement over 3 1/2 minutes to be sure, but having dozens of these to run while an analyst waits for his page of data, noone's going to wait the 20-minutes or so that will take. The objectives call for 5 to 10 seconds to generate the whole page. I might get away with 15.

Now, these were just plain indexes. Neither column has a clustered index on it, so that'll be the next thing I try, but I somehow doubt even a clustered index is going to reduce my time to the ~0.5 seconds I'm looking for.

Any and all advice will be appreciated. Thanks.