Managing deleted entries in large database table Currently we are using Mysql 5.6 with Amazon RDS.

We have table tracking uploads and we have a deleted flag in this table, we don't delete rows when a user subsequently deletes an upload. We do this to maintain historical upload information.

Now we are finding searches in the table very slow. We are thinking of creating a new table with just the deleted entries, but not sure what the best practice would be here.

Any ideas?

EDIT - Added fields to show what is indexed

Field             Type                 Null Key Default Extra          Index
upload_id         int(10) unsigned     NO   PRI         auto_increment Primary Key
user_id           int(11)              NO   MUL                        Foreign Key
resource_id       int(10) unsigned     NO   MUL                        Foreign Key
upload_size       int(10) unsigned     NO               
upload_datetime   datetime             NO               
deleted_datetime  datetime             YES              
upload_name       varchar(150)         NO               
upload_url        varchar(2000)        YES              
upload_url_expiry datetime             YES              
download_count    smallint(5) unsigned NO       0


It is the deleted_datetime field that gets updated.
Partitioning is particularly useful for this.

See https://stackoverflow.com/questions/12929624/partitions-and-update for an example of how an update can cause rows to be moved to a different partition.

This enables you to keep your table structure as it is, including almost all existing code, while queries for active data will only query the appropriate parition.