diff --git a/java/com/google/gitiles/CommitData.java b/java/com/google/gitiles/CommitData.java
index 203051b..25797d2 100644
--- a/java/com/google/gitiles/CommitData.java
+++ b/java/com/google/gitiles/CommitData.java
@@ -25,6 +25,8 @@
 import com.google.common.collect.Sets;
 import java.io.IOException;
 import java.util.Arrays;
+import java.util.HashMap;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -40,6 +42,7 @@
 import org.eclipse.jgit.lib.ObjectReader;
 import org.eclipse.jgit.lib.PersonIdent;
 import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.RefDatabase;
 import org.eclipse.jgit.lib.Repository;
 import org.eclipse.jgit.notes.NoteMap;
 import org.eclipse.jgit.revwalk.RevCommit;
@@ -84,7 +87,7 @@
 
   static class Builder {
     private ArchiveFormat archiveFormat;
-    private Map<AnyObjectId, Set<Ref>> refsById;
+    private Map<String, Map<AnyObjectId, Set<Ref>>> refsByIdByPrefix;
     private static final int MAX_NOTE_SIZE = 524288;
 
     Builder setArchiveFormat(@Nullable ArchiveFormat archiveFormat) {
@@ -204,17 +207,38 @@
     }
 
     private List<Ref> getRefsById(Repository repo, ObjectId id, String prefix) throws IOException {
+      if (refsByIdByPrefix == null) {
+        refsByIdByPrefix = new HashMap<>();
+      }
+      Map<AnyObjectId, Set<Ref>> refsById = refsByIdByPrefix.get(prefix);
       if (refsById == null) {
-        refsById = repo.getAllRefsByPeeledObjectId();
+        // Index only refs under this namespace. getAllRefsByPeeledObjectId peels every ref, which
+        // is catastrophic on repos with many refs (e.g. Gerrit's refs/changes/*).
+        refsById = new HashMap<>();
+        RefDatabase refDb = repo.getRefDatabase();
+        for (Ref ref : refDb.getRefsByPrefix(prefix)) {
+          ObjectId target;
+          try {
+            target = refDb.peel(ref).getPeeledObjectId();
+          } catch (IOException e) {
+            // Treat an unpeelable ref (e.g. missing target) as unpeeled rather than failing the
+            // whole page, like Repository#peel.
+            target = null;
+          }
+          if (target == null) {
+            target = ref.getObjectId();
+          }
+          if (target != null) {
+            refsById.computeIfAbsent(target, k -> new HashSet<>()).add(ref);
+          }
+        }
+        refsByIdByPrefix.put(prefix, refsById);
       }
       Set<Ref> refs = refsById.get(id);
       if (refs == null) {
         return ImmutableList.of();
       }
-      return refs.stream()
-          .filter(r -> r.getName().startsWith(prefix))
-          .sorted(comparing(Ref::getName))
-          .collect(toList());
+      return refs.stream().sorted(comparing(Ref::getName)).collect(toList());
     }
 
     private AbstractTreeIterator getTreeIterator(RevWalk walk, RevCommit commit)
diff --git a/javatests/com/google/gitiles/LogServletTest.java b/javatests/com/google/gitiles/LogServletTest.java
index 2916f3a..dcbf817 100644
--- a/javatests/com/google/gitiles/LogServletTest.java
+++ b/javatests/com/google/gitiles/LogServletTest.java
@@ -21,12 +21,22 @@
 import com.google.gitiles.CommitJsonData.Log;
 import com.google.gitiles.DateFormatter.Format;
 import com.google.gson.reflect.TypeToken;
+import java.io.IOException;
 import java.util.ArrayList;
+import java.util.Map;
+import java.util.Set;
 import org.eclipse.jgit.internal.storage.commitgraph.ChangedPathFilter;
 import org.eclipse.jgit.internal.storage.dfs.DfsGarbageCollector;
+import org.eclipse.jgit.internal.storage.dfs.DfsRepository;
+import org.eclipse.jgit.internal.storage.dfs.DfsRepositoryDescription;
+import org.eclipse.jgit.internal.storage.dfs.InMemoryRepository;
+import org.eclipse.jgit.junit.MockSystemReader;
+import org.eclipse.jgit.junit.TestRepository;
+import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.ConfigConstants;
 import org.eclipse.jgit.lib.NullProgressMonitor;
 import org.eclipse.jgit.lib.PersonIdent;
+import org.eclipse.jgit.lib.Ref;
 import org.eclipse.jgit.revwalk.RevCommit;
 import org.eclipse.jgit.revwalk.RevWalk;
 import org.junit.Test;
@@ -445,6 +455,74 @@
     assertThat(filter2).isNotNull();
   }
 
+  @Test
+  public void logHtmlDecorationDoesNotEnumerateAllRefs() throws Exception {
+    RefCountingRepository counter = new RefCountingRepository(new DfsRepositoryDescription("repo"));
+    TestRepository<DfsRepository> r = newRepoWithManyRefs(counter);
+    GitilesServlet s = TestGitilesServlet.create(r);
+
+    FakeHttpServletResponse res = renderHtmlLog(s, "/repo/+log/refs/heads/master");
+
+    assertThat(res.getStatus()).isEqualTo(SC_OK);
+    assertThat(counter.allRefsByPeeledObjectIdCalls).isEqualTo(0);
+  }
+
+  @Test
+  public void logHtmlShowsBranchAndAnnotatedTagLabels() throws Exception {
+    RefCountingRepository counter = new RefCountingRepository(new DfsRepositoryDescription("repo"));
+    TestRepository<DfsRepository> r = newRepoWithManyRefs(counter);
+    GitilesServlet s = TestGitilesServlet.create(r);
+
+    FakeHttpServletResponse res = renderHtmlLog(s, "/repo/+log/refs/heads/master");
+
+    assertThat(res.getStatus()).isEqualTo(SC_OK);
+    String body = res.getActualBodyString();
+    assertThat(body).contains("CommitLog-branchLabel");
+    // Tag label only appears if the annotated tag was peeled to its commit; guards peeling.
+    assertThat(body).contains("CommitLog-tagLabel");
+  }
+
+  /**
+   * Builds a repo whose tip has a branch and an annotated tag, plus many unrelated refs (as a
+   * Gerrit repo would have under refs/changes/*) that must be irrelevant to log decoration.
+   */
+  private static TestRepository<DfsRepository> newRepoWithManyRefs(RefCountingRepository counter)
+      throws Exception {
+    TestRepository<DfsRepository> r =
+        new TestRepository<>(counter, new RevWalk(counter), new MockSystemReader());
+    RevCommit tip = r.branch("refs/heads/master").commit().add("foo", "contents").create();
+    r.update("refs/tags/v1", r.tag("v1", tip));
+    for (int i = 0; i < 500; i++) {
+      r.update("refs/changes/" + (i % 100) + "/" + i + "/1", tip);
+    }
+    return r;
+  }
+
+  private static FakeHttpServletResponse renderHtmlLog(GitilesServlet servlet, String path)
+      throws Exception {
+    FakeHttpServletRequest req = FakeHttpServletRequest.newRequest();
+    req.setPathInfo(path);
+    req.setQueryString("format=html");
+    FakeHttpServletResponse res = new FakeHttpServletResponse();
+    servlet.service(req, res);
+    return res;
+  }
+
+  /** {@link InMemoryRepository} that counts calls to the whole-repo ref enumeration helper. */
+  private static final class RefCountingRepository extends InMemoryRepository {
+    int allRefsByPeeledObjectIdCalls;
+
+    RefCountingRepository(DfsRepositoryDescription description) {
+      super(description);
+    }
+
+    @Override
+    public Map<AnyObjectId, Set<Ref>> getAllRefsByPeeledObjectId() throws IOException {
+      allRefsByPeeledObjectIdCalls++;
+      return super.getAllRefsByPeeledObjectId();
+    }
+  }
+
   private void testPrettyHtmlOutput(
       String prettyType, boolean shouldShowAuthor, boolean shouldShowCommitter) throws Exception {
     RevCommit parent = repo.branch(MAIN).commit().add("foo", "contents").create();