With the assumption that the pattern suggested by olus is applicable to your real record format, I ran a quick test for the other part of your question -- how long this might take.

On my modest hardware (Intel Core 2 6600), 10 million records took about 37 seconds to process. Assuming a reasonable overhead from other operations, there should be no problem keeping within the time constraints.