Index fragmentation increase as more row being deleted I have a table that contains more than 18 million records. I have a process that clears data out of that table everyday.  Index fragmentation was low.

This table has high transaction throughput. Every second it stores about 3 to 5 new records, so we know that clearing old records for this table needs to be fast. 

The delete statement is like this:

Delete top 1000 
From MyTable 
Where CreationDate &lt; 'Some Date'


Ideally, we keep running it until no more rows can be deleted.

For the first 6 million records the delete process goes well, but as time passes the delete starts slowing down until it impacts other application that access the same table. In addition, many foreign key indexes become fragmented.

My questions are:


Does deleting a lot of rows cause fragmentation on the foreign key indexes? (that is, indexes the dependent tables)
Does the deletion become slow because of the fragmented foreign key indexes? (slower reference data lookup)
Is there a balanced strategy that can keep the performance of both the deletes and the foreign key indexes high?


I'm on SQL Server 2005 Standard edition.

[Update] I have included more information here
The actual table name is called "VehicleLocation"
Key columns:


VehicleLocationKey (PK, char(36), not null) 
AgencyVehicleKey (FK, char(36), not null) 
AssignmentKey (FK, char(36, null)
EmployeeKey (FK, char(36), null)


Indexes


VehicleLocation_AssignmentKey (Non-Unique, Non-Clustered)
VehicleLocation_CreationDate (Non-Unique, Non-Clustered)
VehicleLocation_MessageGenerationDate (Non-Unique, Clustered)
VehicleLocation_pk (Unique, Non-Clustered)


Object Dependencies for VehicleLocation (~ 10.5 mil rows)


VehicleLocationAPC (~76000 rows)
VehicleLocationFare (0 rows)
VehicleLocationGF ( 0 rows)
VehicleLocationInpt (0 rows)
VehicleLocationOBD (~ 15000 rows)
VehicleLocationTP (~8.3 million rows)


All the above tables has indexes on their primary key and on VehicleLocationKey (FK) table.

In addition, we use GUID as primary key (bad idea, but it is legacy). On top of that I see that VehicleLocationTP index has a fragmentation of 96%, which is very high.
This isn't fragmentation. 

Fragmentation is generated of course, but deletes will simply create "islands" of remaining pages, which is less evil then GUID/clustered key INSERT fragmentation.

If you're PK is an IDENTITY, then CreationDate should roughly track this so you're actually deleting chunks of contiguous rows anyway.


Do you have an index on CreationDate
Do you have delete cascades?
Is the TOP 1000 in a single transaction?


For point 3, doing a loop inside a transaction is pointless: is this it?

At some point, a statistics update may be needed if you delete enough rows but I don't think it's that.

Other options: 


why not use TRUNCATE TABLE, wrapped in a stored procedure with EXECUTE AS OWNER
use SYNONYMs for poor man's partitioning