The attached is...
Based on the Nintex Purge Workflow Data Stored Procedure
Selects 1000 random records, checks if items are deleted, if so then include those workflows instances to be purged.
Can be set to run on a schedule, running once will only process 1000 records, of those only a percentage may be against a deleted item.
Additional parameters can be set if required.
Note important information and disclaimer in my previous post. The CheckDeletedItem stored procedure is also required.