Just wanted to share a solution with you. Slow SQL deletes had begun to make an application perform poorly.
I had optimized a delete sproc as much as possible using WITH (ROWLOCK) and all the other performance tricks I could find. Showing Execution Plan in Query Analyser shed no light on the problem - it reckoned the delete was putting little load on the server. However, deleting 500 rows from a table was taking 40 seconds!
Turns out that if you have referential integrity set up between your tables (i.e. foreign key relationships with Foreign Key Constraints enforced), you need to ensure that all foreign key columns in your tables have an index. Otherwise, when you delete a record from a primary key table, referential integrity checks will cause table scans on the referring foreign key tables - and scans are terribly slow compared to index lookups. Sure enough I had neglected to put an index on one of the referring tables; when fixed the same query took less than 2 seconds.
CustomerID (Primary Key)
OrderID (Primary Key)
CustomerID (Foreign Key - Relationship with Customer table - THIS FIELD SHOULD BE INDEXED)
Order Details etc.
If I helped you out today, you can buy me a beer below. Cheers!