diff --git a/src/applications/base/PhabricatorApplication.php b/src/applications/base/PhabricatorApplication.php
--- a/src/applications/base/PhabricatorApplication.php
+++ b/src/applications/base/PhabricatorApplication.php
@@ -468,6 +468,27 @@
     return $result;
   }
 
+  /**
+   * Determine if an application is installed at all, and if a viewer is given
+   * if the application is available to a viewer, by application class name.
+   *
+   * To check if an application is installed at all, use
+   * @{method:isClassInstalled}.
+   *
+   * @param string Application class name.
+   * @param PhabricatorUser|null Viewing user.
+   * @return bool True if the class is installed or if the installed class is
+   * available to the viewer when a viewer is given.
+   * @task meta
+   */
+  final public static function isClassInstalledForViewerIfAny(
+    $class,
+    PhabricatorUser $viewer) {
+
+    return $viewer
+      ? self::isClassInstalledForViewer($class, $viewer)
+      : self::isClassInstalled($class);
+  }
 
 /* -(  PhabricatorPolicyInterface  )----------------------------------------- */
 
diff --git a/src/applications/feed/query/PhabricatorFeedTransactionQuery.php b/src/applications/feed/query/PhabricatorFeedTransactionQuery.php
--- a/src/applications/feed/query/PhabricatorFeedTransactionQuery.php
+++ b/src/applications/feed/query/PhabricatorFeedTransactionQuery.php
@@ -155,6 +155,19 @@
       ->setAncestorClass('PhabricatorApplicationTransactionQuery')
       ->execute();
 
+    // Remove TransactionQuery classes of uninstalled apps. Increases query
+    // performance and decreases likeliness of a "Query Overheated" error if
+    // an app got uninstalled so data in it cannot be accessed anymore anyway.
+    // See https://secure.phabricator.com/T13133, https://we.phorge.it/T15642
+    foreach ($queries as $key => $query) {
+      $app = $query->getQueryApplicationClass();
+      if ($app !== null &&
+          PhabricatorApplication::isClassInstalledForViewerIfAny($app,
+            $viewer)) {
+        unset($queries[$key]);
+      }
+    }
+
     $type_map = array();
 
     // If we're querying for specific transaction PHIDs, we only need to