diff --git a/src/applications/audit/management/PhabricatorAuditManagementDeleteWorkflow.php b/src/applications/audit/management/PhabricatorAuditManagementDeleteWorkflow.php
--- a/src/applications/audit/management/PhabricatorAuditManagementDeleteWorkflow.php
+++ b/src/applications/audit/management/PhabricatorAuditManagementDeleteWorkflow.php
@@ -93,6 +93,12 @@
 
     if ($repos) {
       $query->withRepositoryIDs(mpull($repos, 'getID'));
+
+      // See T13457. If we're iterating over commits in a single large
+      // repository, the lack of a "<repositoryID, [id]>" key can slow things
+      // down. Iterate in a specific order to use a key which is present
+      // on the table ("<repositoryID, epoch, [id]>").
+      $query->setOrderVector(array('-epoch', '-id'));
     }
 
     $auditor_map = array();
@@ -105,7 +111,11 @@
       $query->withPHIDs(mpull($commits, 'getPHID'));
     }
 
-    $commit_iterator = new PhabricatorQueryIterator($query);
+    $commit_iterator = id(new PhabricatorQueryIterator($query));
+
+    // See T13457. We may be examining many commits; each commit is small so
+    // we can safely increase the page size to improve performance a bit.
+    $commit_iterator->setPageSize(1000);
 
     $audits = array();
     foreach ($commit_iterator as $commit) {
diff --git a/src/applications/repository/management/PhabricatorRepositoryManagementRebuildIdentitiesWorkflow.php b/src/applications/repository/management/PhabricatorRepositoryManagementRebuildIdentitiesWorkflow.php
--- a/src/applications/repository/management/PhabricatorRepositoryManagementRebuildIdentitiesWorkflow.php
+++ b/src/applications/repository/management/PhabricatorRepositoryManagementRebuildIdentitiesWorkflow.php
@@ -98,7 +98,12 @@
           ->needCommitData(true)
           ->withRepositoryIDs(array($repository->getID()));
 
-        $commit_iterator = new PhabricatorQueryIterator($commit_query);
+        // See T13457. Adjust ordering to hit keys better and tweak page size
+        // to improve performance slightly, since these records are small.
+        $commit_query->setOrderVector(array('-epoch', '-id'));
+
+        $commit_iterator = id(new PhabricatorQueryIterator($commit_query))
+          ->setPageSize(1000);
 
         $this->rebuildCommits($commit_iterator);
       }
diff --git a/src/infrastructure/storage/lisk/PhabricatorQueryIterator.php b/src/infrastructure/storage/lisk/PhabricatorQueryIterator.php
--- a/src/infrastructure/storage/lisk/PhabricatorQueryIterator.php
+++ b/src/infrastructure/storage/lisk/PhabricatorQueryIterator.php
@@ -10,7 +10,12 @@
   }
 
   protected function didRewind() {
-    $this->pager = new AphrontCursorPagerView();
+    $pager = new AphrontCursorPagerView();
+
+    $page_size = $this->getPageSize();
+    $pager->setPageSize($page_size);
+
+    $this->pager = $pager;
   }
 
   public function key() {