I am still curious about your 75 Million rows
I would like to know the performance of the query posted using sp_excecutesql @STR with the hard coded numbers in @STR. My guess is that for such a big table a recompilation of the procedure using harcoded numbers will be the fastest option!
can you post the results?