Delete Query Taking Too Much Resources

[Vipin Kumar R Jaiswar]

Hi Team,
one day in every week i am running one script which is deleting the data from database base.
1) IN the table there always more then 3m of record
2) Delete query delete 25000 rows at a time.
3) database base is INNODB.
4) Delete query where caluse column name is have key to make this process fast.
(I have tested with removing the key as well)

IN first 2 (in 2 weeks) execution went smoothly with out any server load and issue. now days same script taking lots of time where

1) Data weight is not change
2) No other services asking for same table or mysql request in that duration.
3) No hardware changes.

I really want your helps in that. Can any one tell me how to optimize the process more on the query level.

Thanks
Jaiswar Vipin Kumar R