Deleting rows from a table with a very small amount of expansion space
As things stand, the query:

DELETE TOP (4000)
FROM   [OLD_TABLE] WITH (TABLOCKX)
WHERE  [Date] &lt; '2014-01-01 00:00:00'


...has to scan the whole heap table, testing each row it finds, until it eventually finds 4000 to delete. On the next iteration, the whole business starts again from square one. Assuming the scanning process is performed in the same (allocation unit) order each time, these scans will take longer and longer to find 4000 rows as time goes by.

Creating an index on the [Date] column will allow SQL Server to find the 4000 rows much more efficiently. It does add a small overhead to each delete (as the new nonclustered index needs to be maintained as well) but this is nothing compared to the effort that will be saved by not performing a scan each time. The index will also require a certain amount of space, but it should not be too large. You should create the following index before resuming your data removal process:

CREATE NONCLUSTERED INDEX &lt;index_name&gt;
ON dbo.OLD_TABLE ([Date]);


By the way, if the database has snapshot isolation or read committed snapshot isolation enabled (even if not actively used!), the TABLOCKX hint will not be enough to ensure that empty heap pages are deallocated. Your heap table may therefore contain many empty pages - a concern since you are so low on space.

The standard way to address this space management issue is to create a clustered index (or issue an ALTER TABLE REBUILD statement, but that requires SQL Server 2008). It seems that creating a clustered index might also not be an option for you, due to space constraints. There isn't an obvious way to resolve this right now, given the space issue.

One thing to keep an eye on while the delete is progressing is the space used by the transaction log. If the database is in FULL or BULK_LOGGED recovery, you will need to keep on top of backing up the log. If the database is using SIMPLE recovery, you may need to issue a manual CHECKPOINT from time to time to release transaction log space for reuse (otherwise the physical file might grow).

If you can get hold of some additional temporary storage, a better way might be to bulk export the data you want to keep to a safe location, drop the table, recreate it (preferably with a clustered index!) and reload the saved data. This is generally faster than the incremental-delete process, but it depends on your objectives and priorities.