diff --git a/src/infrastructure/edges/query/PhabricatorEdgeQuery.php b/src/infrastructure/edges/query/PhabricatorEdgeQuery.php
--- a/src/infrastructure/edges/query/PhabricatorEdgeQuery.php
+++ b/src/infrastructure/edges/query/PhabricatorEdgeQuery.php
@@ -260,20 +260,31 @@
         'You must execute() a query before you you can getDestinationPHIDs().');
     }
 
-    $src_phids = array_fill_keys($src_phids, true);
-    $types = array_fill_keys($types, true);
-
     $result_phids = array();
-    foreach ($this->resultSet as $src => $edges_by_type) {
-      if ($src_phids && empty($src_phids[$src])) {
-        continue;
-      }
-      foreach ($edges_by_type as $type => $edges_by_dst) {
-        if ($types && empty($types[$type])) {
-          continue;
+
+    if (!empty($src_phids)) {
+      foreach ($src_phids as $src_phid) {
+        if (isset($this->resultSet[$src_phid])) {
+          if (empty($types)) {
+            $types = array_keys($this->resultSet[$src_phid]);
+          }
+          foreach ($types as $type) {
+            $result_phids = array_merge($result_phids,
+              $this->resultSet[$src_phid][$type]);
+          }
         }
-        foreach ($edges_by_dst as $dst => $edge) {
-          $result_phids[$dst] = true;
+      }
+    } else {
+      $types = array_fill_keys($types, true);
+
+      foreach ($this->resultSet as $src => $edges_by_type) {
+        foreach ($edges_by_type as $type => $edges_by_dst) {
+          if ($types && empty($types[$type])) {
+            continue;
+          }
+          foreach ($edges_by_dst as $dst => $edge) {
+            $result_phids[$dst] = true;
+          }
         }
       }
     }