diff --git a/src/applications/search/controller/PhabricatorApplicationSearchController.php b/src/applications/search/controller/PhabricatorApplicationSearchController.php
--- a/src/applications/search/controller/PhabricatorApplicationSearchController.php
+++ b/src/applications/search/controller/PhabricatorApplicationSearchController.php
@@ -238,6 +238,8 @@
           $nux_view = null;
         }
 
+        $is_overheated = $query->getIsOverheated();
+
         if ($nux_view) {
           $box->appendChild($nux_view);
         } else {
@@ -265,6 +267,10 @@
             $box->appendChild($list->getContent());
           }
 
+          if ($is_overheated) {
+            $box->appendChild($this->newOverheatedView($objects));
+          }
+
           $result_header = $list->getHeader();
           if ($result_header) {
             $box->setHeader($result_header);
@@ -525,4 +531,27 @@
       ->setDropdownMenu($action_list);
   }
 
+  private function newOverheatedView(array $results) {
+    if ($results) {
+      $message = pht(
+        'Most objects matching your query are not visible to you, so '.
+        'filtering results is taking a long time. Only some results are '.
+        'shown. Refine your query to find results more quickly.');
+    } else {
+      $message = pht(
+        'Most objects matching your query are not visible to you, so '.
+        'filtering results is taking a long time. Refine your query to '.
+        'find results more quickly.');
+    }
+
+    return id(new PHUIInfoView())
+      ->setSeverity(PHUIInfoView::SEVERITY_WARNING)
+      ->setFlush(true)
+      ->setTitle(pht('Query Overheated'))
+      ->setErrors(
+        array(
+          $message,
+        ));
+  }
+
 }
diff --git a/src/infrastructure/query/policy/PhabricatorPolicyAwareQuery.php b/src/infrastructure/query/policy/PhabricatorPolicyAwareQuery.php
--- a/src/infrastructure/query/policy/PhabricatorPolicyAwareQuery.php
+++ b/src/infrastructure/query/policy/PhabricatorPolicyAwareQuery.php
@@ -44,6 +44,7 @@
    * and `null` (inherit from parent query, with no exceptions by default).
    */
   private $raisePolicyExceptions;
+  private $isOverheated;
 
 
 /* -(  Query Configuration  )------------------------------------------------ */
@@ -215,6 +216,14 @@
 
     $this->willExecute();
 
+    // If we examine and filter significantly more objects than the query
+    // limit, we stop early. This prevents us from looping through a huge
+    // number of records when the viewer can see few or none of them. See
+    // T11773 for some discussion.
+    $this->isOverheated = false;
+    $overheat_limit = $limit * 10;
+    $total_seen = 0;
+
     do {
       if ($need) {
         $this->rawResultLimit = min($need - $count, 1024);
@@ -232,6 +241,8 @@
         $page = array();
       }
 
+      $total_seen += count($page);
+
       if ($page) {
         $maybe_visible = $this->willFilterPage($page);
         if ($maybe_visible) {
@@ -302,6 +313,11 @@
       }
 
       $this->nextPage($page);
+
+      if ($overheat_limit && ($total_seen >= $overheat_limit)) {
+        $this->isOverheated = true;
+        break;
+      }
     } while (true);
 
     $results = $this->didLoadResults($results);
@@ -369,6 +385,15 @@
     return $this;
   }
 
+
+  public function getIsOverheated() {
+    if ($this->isOverheated === null) {
+      throw new PhutilInvalidStateException('execute');
+    }
+    return $this->isOverheated;
+  }
+
+
   /**
    * Return a map of all object PHIDs which were loaded in the query but
    * filtered out by policy constraints. This allows a caller to distinguish