Right now when you use the pegasus-s3 rm command, it deletes the keys one-by-one. Amazon added a bulk delete interface that enables keys to be deleted in batches of 1,000. We should use that interface to speed up the deletion process. In boto this is invoked with Bucket.delete_keys([key1,key2]). We could also do parallel deletes for very large sets of keys.