diff --git a/src/applications/paste/query/PhabricatorPasteQuery.php b/src/applications/paste/query/PhabricatorPasteQuery.php
--- a/src/applications/paste/query/PhabricatorPasteQuery.php
+++ b/src/applications/paste/query/PhabricatorPasteQuery.php
@@ -173,6 +173,7 @@
         'P'.$paste->getID(),
         $paste->getFilePHID(),
         $paste->getLanguage(),
+        PhabricatorHash::digestForIndex($paste->getTitle()),
       ));
   }
 
@@ -184,6 +185,7 @@
         $paste->getFilePHID(),
         $paste->getLanguage(),
         'snippet',
+        PhabricatorHash::digestForIndex($paste->getTitle()),
       ));
   }
 
diff --git a/src/applications/paste/xaction/PhabricatorPasteLanguageTransaction.php b/src/applications/paste/xaction/PhabricatorPasteLanguageTransaction.php
--- a/src/applications/paste/xaction/PhabricatorPasteLanguageTransaction.php
+++ b/src/applications/paste/xaction/PhabricatorPasteLanguageTransaction.php
@@ -13,12 +13,20 @@
     $object->setLanguage($value);
   }
 
+  private function renderLanguageValue($value) {
+    if (!strlen($value)) {
+      return $this->renderValue(pht('autodetect'));
+    } else {
+      return $this->renderValue($value);
+    }
+  }
+
   public function getTitle() {
     return pht(
       "%s updated the paste's language from %s to %s.",
       $this->renderAuthor(),
-      $this->renderOldValue(),
-      $this->renderNewValue());
+      $this->renderLanguageValue($this->getOldValue()),
+      $this->renderLanguageValue($this->getNewValue()));
   }
 
   public function getTitleForFeed() {
@@ -26,8 +34,8 @@
       '%s updated the language for %s from %s to %s.',
       $this->renderAuthor(),
       $this->renderObject(),
-      $this->renderOldValue(),
-      $this->renderNewValue());
+      $this->renderLanguageValue($this->getOldValue()),
+      $this->renderLanguageValue($this->getNewValue()));
   }
 
 }