cleanup_database.pl deletes import_records and import_batches based on import_records.upload_timestamp, but this isn't an indexed field. That means the database needs to do a row scan through all rows in order to find which rows to delete. This is inefficient, so it's slow when you have a large number of rows.