I am looking to see if there could be a way to optimize a delete SQL I have.

Basically, I do something like this every 15 minutes:

DELETE FROM Hit WHERE AddDate<something

As this is executed every 15 minutes, usually, this is executed in a flash. So, all records from the Hit table which are older than the parameter will be removed. The situation is when I run this command on a test server, where this procedure hasn't been executed since a while, the process may take several minutes.

Is it because I am working on a date field? If yes, I can do a SQL at first to get the primary key and then remove anything older than that primary key.

Or, is it that it is because there are a lot of records? If this is the case, what can I do to optimize?