Slow respond time when file change to open with update&Add

I created a RPG program that reads an input file that contains about 2.5 mil+ 
records and write them to a output file if they meeting the criteria (about 1.2 
mil+ records).
 
1) It took about 35 mins to run when the input file is open as Input only with 
sequential access (No Key).  The output file is open as output only.
2) It took about 70 mins to run when the program is change to open the input 
file as Input only with key access and the outfile as Update & Add.  The only 
logic added to the program is it do a chain to outfile, if %found, update, 
otherwise write.
 
I think the increase of processing time on 2 is cause the outfile open as 
Update&ADD, which cause the program to not do record blocking when write to 
outfile.
 
I got several methods in mind that I can think of that might speed up 2.  
However, just wonder if anybody has had the same problem before and know a good 
method to speed it up.
 
thanks