diff --git a/resources/sql/autopatches/20190215.harbor.01.stringindex.sql b/resources/sql/autopatches/20190215.harbor.01.stringindex.sql
new file mode 100644
--- /dev/null
+++ b/resources/sql/autopatches/20190215.harbor.01.stringindex.sql
@@ -0,0 +1,6 @@
+CREATE TABLE {$NAMESPACE}_harbormaster.harbormaster_string (
+  id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
+  stringIndex BINARY(12) NOT NULL,
+  stringValue LONGTEXT NOT NULL,
+  UNIQUE KEY `key_string` (stringIndex)
+) ENGINE=InnoDB, COLLATE {$COLLATE_TEXT};
diff --git a/resources/sql/autopatches/20190215.harbor.02.stringcol.sql b/resources/sql/autopatches/20190215.harbor.02.stringcol.sql
new file mode 100644
--- /dev/null
+++ b/resources/sql/autopatches/20190215.harbor.02.stringcol.sql
@@ -0,0 +1,2 @@
+ALTER TABLE {$NAMESPACE}_harbormaster.harbormaster_buildunitmessage
+  ADD nameIndex BINARY(12) NOT NULL;
diff --git a/src/__phutil_library_map__.php b/src/__phutil_library_map__.php
--- a/src/__phutil_library_map__.php
+++ b/src/__phutil_library_map__.php
@@ -1441,6 +1441,7 @@
     'HarbormasterStepDeleteController' => 'applications/harbormaster/controller/HarbormasterStepDeleteController.php',
     'HarbormasterStepEditController' => 'applications/harbormaster/controller/HarbormasterStepEditController.php',
     'HarbormasterStepViewController' => 'applications/harbormaster/controller/HarbormasterStepViewController.php',
+    'HarbormasterString' => 'applications/harbormaster/storage/HarbormasterString.php',
     'HarbormasterTargetEngine' => 'applications/harbormaster/engine/HarbormasterTargetEngine.php',
     'HarbormasterTargetSearchAPIMethod' => 'applications/harbormaster/conduit/HarbormasterTargetSearchAPIMethod.php',
     'HarbormasterTargetWorker' => 'applications/harbormaster/worker/HarbormasterTargetWorker.php',
@@ -7070,6 +7071,7 @@
     'HarbormasterStepDeleteController' => 'HarbormasterPlanController',
     'HarbormasterStepEditController' => 'HarbormasterPlanController',
     'HarbormasterStepViewController' => 'HarbormasterPlanController',
+    'HarbormasterString' => 'HarbormasterDAO',
     'HarbormasterTargetEngine' => 'Phobject',
     'HarbormasterTargetSearchAPIMethod' => 'PhabricatorSearchEngineAPIMethod',
     'HarbormasterTargetWorker' => 'HarbormasterWorker',
diff --git a/src/applications/harbormaster/query/HarbormasterBuildUnitMessageQuery.php b/src/applications/harbormaster/query/HarbormasterBuildUnitMessageQuery.php
--- a/src/applications/harbormaster/query/HarbormasterBuildUnitMessageQuery.php
+++ b/src/applications/harbormaster/query/HarbormasterBuildUnitMessageQuery.php
@@ -57,6 +57,37 @@
     return $where;
   }
 
+  protected function didFilterPage(array $messages) {
+    $indexes = array();
+    foreach ($messages as $message) {
+      $index = $message->getNameIndex();
+      if (strlen($index)) {
+        $indexes[$index] = $index;
+      }
+    }
+
+    if ($indexes) {
+      $map = HarbormasterString::newIndexMap($indexes);
+
+      foreach ($messages as $message) {
+        $index = $message->getNameIndex();
+
+        if (!strlen($index)) {
+          continue;
+        }
+
+        $name = idx($map, $index);
+        if ($name === null) {
+          $name = pht('Unknown Unit Message ("%s")', $index);
+        }
+
+        $message->setName($name);
+      }
+    }
+
+    return $messages;
+  }
+
   public function getQueryApplicationClass() {
     return 'PhabricatorHarbormasterApplication';
   }
diff --git a/src/applications/harbormaster/storage/HarbormasterString.php b/src/applications/harbormaster/storage/HarbormasterString.php
new file mode 100644
--- /dev/null
+++ b/src/applications/harbormaster/storage/HarbormasterString.php
@@ -0,0 +1,54 @@
+<?php
+
+final class HarbormasterString
+  extends HarbormasterDAO {
+
+  protected $stringIndex;
+  protected $stringValue;
+
+  protected function getConfiguration() {
+    return array(
+      self::CONFIG_TIMESTAMPS => false,
+      self::CONFIG_COLUMN_SCHEMA => array(
+        'stringIndex' => 'bytes12',
+        'stringValue' => 'text',
+      ),
+      self::CONFIG_KEY_SCHEMA => array(
+        'key_string' => array(
+          'columns' => array('stringIndex'),
+          'unique' => true,
+        ),
+      ),
+    ) + parent::getConfiguration();
+  }
+
+  public static function newIndex($string) {
+    $index = PhabricatorHash::digestForIndex($string);
+
+    $table = new self();
+    $conn = $table->establishConnection('w');
+
+    queryfx(
+      $conn,
+      'INSERT IGNORE INTO %R (stringIndex, stringValue) VALUES (%s, %s)',
+      $table,
+      $index,
+      $string);
+
+    return $index;
+  }
+
+  public static function newIndexMap(array $indexes) {
+    $table = new self();
+    $conn = $table->establishConnection('r');
+
+    $rows = queryfx_all(
+      $conn,
+      'SELECT stringIndex, stringValue FROM %R WHERE stringIndex IN (%Ls)',
+      $table,
+      $indexes);
+
+    return ipull($rows, 'stringValue', 'stringIndex');
+  }
+
+}
diff --git a/src/applications/harbormaster/storage/build/HarbormasterBuildUnitMessage.php b/src/applications/harbormaster/storage/build/HarbormasterBuildUnitMessage.php
--- a/src/applications/harbormaster/storage/build/HarbormasterBuildUnitMessage.php
+++ b/src/applications/harbormaster/storage/build/HarbormasterBuildUnitMessage.php
@@ -8,6 +8,7 @@
   protected $engine;
   protected $namespace;
   protected $name;
+  protected $nameIndex;
   protected $result;
   protected $duration;
   protected $properties = array();
@@ -132,6 +133,7 @@
         'engine' => 'text255',
         'namespace' => 'text255',
         'name' => 'text255',
+        'nameIndex' => 'bytes12',
         'result' => 'text32',
         'duration' => 'double?',
       ),
@@ -260,6 +262,33 @@
     return implode("\0", $parts);
   }
 
+  public function save() {
+    if ($this->nameIndex === null) {
+      $this->nameIndex = HarbormasterString::newIndex($this->getName());
+    }
+
+    // See T13088. While we're letting installs do online migrations to avoid
+    // downtime, don't populate the "name" column for new writes. New writes
+    // use the "HarbormasterString" table instead.
+    $old_name = $this->name;
+    $this->name = '';
+
+    $caught = null;
+    try {
+      $result = parent::save();
+    } catch (Exception $ex) {
+      $caught = $ex;
+    }
+
+    $this->name = $old_name;
+
+    if ($caught) {
+      throw $caught;
+    }
+
+    return $result;
+  }
+
 
 /* -(  PhabricatorPolicyInterface  )----------------------------------------- */