diff --git a/Documentation/config-gerrit.txt b/Documentation/config-gerrit.txt
index b587e83..94ee7ab 100644
--- a/Documentation/config-gerrit.txt
+++ b/Documentation/config-gerrit.txt
@@ -819,18 +819,23 @@
 requires two HTTP requests, and this cache tries to carry state from
 the first request into the second to ensure it can complete.
 
-cache `"changes"`::
+cache `"change_refs"`::
++
+Cache entries are used to compute change ref visibility efficiently. Entries
+contain the minimal required information for this task.
 +
 The size of `memoryLimit` determines the number of projects for which
 all changes will be cached. If the cache is set to 1024, this means all
-changes for up to 1024 projects can be held in the cache.
+at maximum 1024 changes can be held in the cache.
 +
-Default value is 0 (disabled). It is disabled by default due to the fact
-that change updates are not communicated between Gerrit servers. Hence
-this cache should be disabled in an multi-master/multi-slave setup.
+Default value is 10.000.
 +
-The cache should be flushed whenever the database changes table is modified
-outside of Gerrit.
+If the size is set to 0, the cache is disabled. The change index will not
+be used at all. Instead, the change notes cache is used directly.
++
+A good size for this cache is twice the number of changes that the Gerrit
+instance has to allow it to hold all current changes and account for
+growth.
 
 cache `"diff"`::
 +
diff --git a/java/com/google/gerrit/httpd/init/WebAppInitializer.java b/java/com/google/gerrit/httpd/init/WebAppInitializer.java
index aa5362b..a8552f4 100644
--- a/java/com/google/gerrit/httpd/init/WebAppInitializer.java
+++ b/java/com/google/gerrit/httpd/init/WebAppInitializer.java
@@ -66,9 +66,9 @@
 import com.google.gerrit.server.config.SysExecutorModule;
 import com.google.gerrit.server.events.EventBroker;
 import com.google.gerrit.server.events.StreamEventsApiListener;
+import com.google.gerrit.server.git.ChangeRefCache;
 import com.google.gerrit.server.git.GarbageCollectionModule;
 import com.google.gerrit.server.git.GitRepositoryManagerModule;
-import com.google.gerrit.server.git.SearchingChangeCacheImpl;
 import com.google.gerrit.server.git.WorkQueue;
 import com.google.gerrit.server.index.IndexModule;
 import com.google.gerrit.server.index.IndexModule.IndexType;
@@ -288,7 +288,7 @@
     modules.add(cfgInjector.getInstance(GerritGlobalModule.class));
     modules.add(new GerritApiModule());
     modules.add(new PluginApiModule());
-    modules.add(new SearchingChangeCacheImpl.Module());
+    modules.add(new ChangeRefCache.Module());
     modules.add(new InternalAccountDirectory.Module());
     modules.add(new DefaultPermissionBackendModule());
     modules.add(new DefaultMemoryCacheModule());
diff --git a/java/com/google/gerrit/pgm/Daemon.java b/java/com/google/gerrit/pgm/Daemon.java
index c280a2d..3c4f89b 100644
--- a/java/com/google/gerrit/pgm/Daemon.java
+++ b/java/com/google/gerrit/pgm/Daemon.java
@@ -73,8 +73,8 @@
 import com.google.gerrit.server.config.SysExecutorModule;
 import com.google.gerrit.server.events.EventBroker;
 import com.google.gerrit.server.events.StreamEventsApiListener;
+import com.google.gerrit.server.git.ChangeRefCache;
 import com.google.gerrit.server.git.GarbageCollectionModule;
-import com.google.gerrit.server.git.SearchingChangeCacheImpl;
 import com.google.gerrit.server.git.WorkQueue;
 import com.google.gerrit.server.group.PeriodicGroupIndexer;
 import com.google.gerrit.server.index.IndexModule;
@@ -393,7 +393,7 @@
     modules.add(new GerritApiModule());
     modules.add(new PluginApiModule());
 
-    modules.add(new SearchingChangeCacheImpl.Module(slave));
+    modules.add(new ChangeRefCache.Module());
     modules.add(new InternalAccountDirectory.Module());
     modules.add(new DefaultPermissionBackendModule());
     modules.add(new DefaultMemoryCacheModule());
diff --git a/java/com/google/gerrit/pgm/util/BatchProgramModule.java b/java/com/google/gerrit/pgm/util/BatchProgramModule.java
index b0c1c25..f263786 100644
--- a/java/com/google/gerrit/pgm/util/BatchProgramModule.java
+++ b/java/com/google/gerrit/pgm/util/BatchProgramModule.java
@@ -56,8 +56,8 @@
 import com.google.gerrit.server.extensions.events.EventUtil;
 import com.google.gerrit.server.extensions.events.GitReferenceUpdated;
 import com.google.gerrit.server.extensions.events.RevisionCreated;
+import com.google.gerrit.server.git.ChangeRefCache;
 import com.google.gerrit.server.git.MergeUtil;
-import com.google.gerrit.server.git.SearchingChangeCacheImpl;
 import com.google.gerrit.server.git.TagCache;
 import com.google.gerrit.server.mail.send.ReplacePatchSetSender;
 import com.google.gerrit.server.notedb.NoteDbModule;
@@ -133,7 +133,7 @@
 
     // As Reindex is a batch program, don't assume the index is available for
     // the change cache.
-    bind(SearchingChangeCacheImpl.class).toProvider(Providers.of(null));
+    bind(ChangeRefCache.class).toProvider(Providers.of(null));
 
     bind(new TypeLiteral<ImmutableSet<GroupReference>>() {})
         .annotatedWith(AdministrateServerGroups.class)
diff --git a/java/com/google/gerrit/server/git/ChangeRefCache.java b/java/com/google/gerrit/server/git/ChangeRefCache.java
new file mode 100644
index 0000000..dc1b946
--- /dev/null
+++ b/java/com/google/gerrit/server/git/ChangeRefCache.java
@@ -0,0 +1,226 @@
+// Copyright (C) 2019 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.git;
+
+import com.google.auto.value.AutoValue;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.cache.CacheLoader;
+import com.google.common.cache.LoadingCache;
+import com.google.common.flogger.FluentLogger;
+import com.google.gerrit.common.Nullable;
+import com.google.gerrit.index.RefState;
+import com.google.gerrit.reviewdb.client.Change;
+import com.google.gerrit.reviewdb.client.Project;
+import com.google.gerrit.reviewdb.client.RefNames;
+import com.google.gerrit.server.ReviewerSet;
+import com.google.gerrit.server.cache.CacheModule;
+import com.google.gerrit.server.config.GerritOptions;
+import com.google.gerrit.server.config.GerritServerConfig;
+import com.google.gerrit.server.index.change.ChangeField;
+import com.google.gerrit.server.logging.TraceContext;
+import com.google.gerrit.server.logging.TraceContext.TraceTimer;
+import com.google.gerrit.server.notedb.ChangeNotes;
+import com.google.gerrit.server.query.change.ChangeData;
+import com.google.gerrit.server.query.change.InternalChangeQuery;
+import com.google.gerrit.server.util.ManualRequestContext;
+import com.google.gerrit.server.util.OneOffRequestContext;
+import com.google.gwtorm.server.OrmException;
+import com.google.inject.Inject;
+import com.google.inject.Provider;
+import com.google.inject.Singleton;
+import com.google.inject.TypeLiteral;
+import com.google.inject.name.Named;
+import java.util.List;
+import java.util.NoSuchElementException;
+import java.util.Optional;
+import java.util.Set;
+import java.util.concurrent.CopyOnWriteArraySet;
+import org.eclipse.jgit.lib.Config;
+import org.eclipse.jgit.lib.ObjectId;
+
+/**
+ * Cache for the minimal information per change that we need to compute visibility. Used for ref
+ * filtering.
+ *
+ * <p>This class is thread safe.
+ */
+@Singleton
+public class ChangeRefCache {
+  private static final FluentLogger logger = FluentLogger.forEnclosingClass();
+
+  static final String ID_CACHE = "change_refs";
+
+  public static class Module extends CacheModule {
+    @Override
+    protected void configure() {
+      cache(ID_CACHE, Key.class, new TypeLiteral<CachedChange>() {})
+          .maximumWeight(10000)
+          .loader(Loader.class);
+
+      bind(ChangeRefCache.class);
+    }
+  }
+
+  @AutoValue
+  abstract static class Key {
+    abstract Project.NameKey project();
+
+    abstract Change.Id changeId();
+
+    abstract ObjectId metaId();
+  }
+
+  @AutoValue
+  abstract static class CachedChange {
+    // Subset of fields in ChangeData, specifically fields needed to serve
+    // VisibleRefFilter without touching the database. More can be added as
+    // necessary.
+    abstract Change change();
+
+    @Nullable
+    abstract ReviewerSet reviewers();
+  }
+
+  private final LoadingCache<Key, CachedChange> cache;
+  private final ChangeData.Factory changeDataFactory;
+  private final OneOffRequestContext requestContext;
+  private final Provider<InternalChangeQuery> queryProvider;
+  private final GerritOptions gerritOptions;
+  private final Config gerritConfig;
+  private final Set<Project.NameKey> bootstrappedProjects;
+
+  @Inject
+  ChangeRefCache(
+      @Named(ID_CACHE) LoadingCache<Key, CachedChange> cache,
+      ChangeData.Factory changeDataFactory,
+      OneOffRequestContext requestContext,
+      Provider<InternalChangeQuery> queryProvider,
+      GerritOptions gerritOptions,
+      @GerritServerConfig Config gerritConfig) {
+    this.cache = cache;
+    this.changeDataFactory = changeDataFactory;
+    this.requestContext = requestContext;
+    this.queryProvider = queryProvider;
+    this.gerritOptions = gerritOptions;
+    this.gerritConfig = gerritConfig;
+    // Uses a CopyOnWriteArraySet internally to keep track of projects that are already
+    // bootstrapped. This is efficient because we read from the set on every call to this method to
+    // check if bootstrapping is required. Writes occur only if we bootstrapped, so once per
+    // project.
+    this.bootstrappedProjects = new CopyOnWriteArraySet<>();
+  }
+
+  /**
+   * Read changes from the cache.
+   *
+   * <p>Returned changes only include the {@code Change} object (with id, branch) and the reviewers.
+   * There is no guarantee that additional fields are populated, although they can be.
+   *
+   * @param project project to read.
+   * @param changeId change ID to read
+   * @param metaId object ID of the meta branch to read. This is only used to ensure consistency. It
+   *     does not allow for reading non-current meta versions.
+   * @return change data
+   * @throws IllegalArgumentException in case no change is found
+   */
+  public ChangeData getChangeData(Project.NameKey project, Change.Id changeId, ObjectId metaId) {
+    Key key = new AutoValue_ChangeRefCache_Key(project, changeId, metaId);
+    CachedChange cached = cache.getUnchecked(key);
+    if (cached == null) {
+      throw new IllegalArgumentException("no change found for key " + key);
+    }
+    ChangeData cd = changeDataFactory.create(cached.change());
+    cd.setReviewers(cached.reviewers());
+    return cd;
+  }
+
+  /**
+   * This method bootstraps the cache by querying the change index if it hasn't been bootstrapped
+   * before, in which case it is a cheap no-op.
+   *
+   * @param project the project to bootstrap
+   */
+  public void bootstrapIfNecessary(Project.NameKey project) {
+    if (!gerritOptions.enableMasterFeatures()) {
+      // Bootstrapping using the ChangeIndex is only supported on master in a master-slave replica.
+      return;
+    }
+    if (gerritConfig.getInt("cache", ID_CACHE, "memoryLimit", -1) == 0) {
+      // The cache is disabled, don't bother bootstrapping.
+      return;
+    }
+    if (bootstrappedProjects.contains(project)) {
+      // We have bootstrapped for this project before. If the cache is too small, we might have
+      // evicted all entries by now. Don't bother about this though as we don't want to add the
+      // complexity of checking for existing projects, since that might not be authoritative as well
+      // since we could have already evicted the majority of the entries.
+      return;
+    }
+
+    try (TraceTimer ignored =
+            TraceContext.newTimer("bootstrapping ChangeRef cache for project " + project);
+        ManualRequestContext ignored2 = requestContext.open()) {
+      List<ChangeData> cds =
+          queryProvider
+              .get()
+              .setRequestedFields(ChangeField.CHANGE, ChangeField.REVIEWER, ChangeField.REF_STATE)
+              .byProject(project);
+      for (ChangeData cd : cds) {
+        Set<RefState> refStates = RefState.parseStates(cd.getRefStates()).get(project);
+        Optional<RefState> refState =
+            refStates
+                .stream()
+                .filter(r -> r.ref().equals(RefNames.changeMetaRef(cd.getId())))
+                .findAny();
+        if (!refState.isPresent()) {
+          continue;
+        }
+        cache.put(
+            new AutoValue_ChangeRefCache_Key(project, cd.change().getId(), refState.get().id()),
+            new AutoValue_ChangeRefCache_CachedChange(cd.change(), cd.getReviewers()));
+      }
+      // Mark the project as bootstrapped. We could have bootstrapped it multiple times for
+      // simultaneous requests. We accept this in favor of less thread synchronization and
+      // complexity.
+      bootstrappedProjects.add(project);
+    } catch (OrmException e) {
+      logger.atWarning().withCause(e).log(
+          "unable to bootstrap ChangeRef cache for project " + project);
+    }
+  }
+
+  static class Loader extends CacheLoader<Key, CachedChange> {
+    private final ChangeNotes.Factory notesFactory;
+
+    @Inject
+    Loader(ChangeNotes.Factory notesFactory) {
+      this.notesFactory = notesFactory;
+    }
+
+    @Override
+    public CachedChange load(Key key) throws Exception {
+      ChangeNotes notes = notesFactory.create(key.project(), key.changeId());
+      if (notes.getMetaId().equals(key.metaId())) {
+        return new AutoValue_ChangeRefCache_CachedChange(notes.getChange(), notes.getReviewers());
+      }
+      throw new NoSuchElementException("unable to load change");
+    }
+  }
+
+  @VisibleForTesting
+  public void resetBootstrappedProjects() {
+    bootstrappedProjects.clear();
+  }
+}
diff --git a/java/com/google/gerrit/server/git/SearchingChangeCacheImpl.java b/java/com/google/gerrit/server/git/SearchingChangeCacheImpl.java
deleted file mode 100644
index 0692ccf..0000000
--- a/java/com/google/gerrit/server/git/SearchingChangeCacheImpl.java
+++ /dev/null
@@ -1,162 +0,0 @@
-// Copyright (C) 2012 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package com.google.gerrit.server.git;
-
-import com.google.auto.value.AutoValue;
-import com.google.common.cache.CacheLoader;
-import com.google.common.cache.LoadingCache;
-import com.google.common.flogger.FluentLogger;
-import com.google.gerrit.common.Nullable;
-import com.google.gerrit.extensions.events.GitReferenceUpdatedListener;
-import com.google.gerrit.extensions.registration.DynamicSet;
-import com.google.gerrit.reviewdb.client.Change;
-import com.google.gerrit.reviewdb.client.Project;
-import com.google.gerrit.reviewdb.client.RefNames;
-import com.google.gerrit.server.ReviewerSet;
-import com.google.gerrit.server.cache.CacheModule;
-import com.google.gerrit.server.index.change.ChangeField;
-import com.google.gerrit.server.logging.TraceContext;
-import com.google.gerrit.server.logging.TraceContext.TraceTimer;
-import com.google.gerrit.server.query.change.ChangeData;
-import com.google.gerrit.server.query.change.InternalChangeQuery;
-import com.google.gerrit.server.util.ManualRequestContext;
-import com.google.gerrit.server.util.OneOffRequestContext;
-import com.google.inject.Inject;
-import com.google.inject.Provider;
-import com.google.inject.Singleton;
-import com.google.inject.TypeLiteral;
-import com.google.inject.name.Named;
-import com.google.inject.util.Providers;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.List;
-import java.util.concurrent.ExecutionException;
-
-@Singleton
-public class SearchingChangeCacheImpl implements GitReferenceUpdatedListener {
-  private static final FluentLogger logger = FluentLogger.forEnclosingClass();
-
-  static final String ID_CACHE = "changes";
-
-  public static class Module extends CacheModule {
-    private final boolean slave;
-
-    public Module() {
-      this(false);
-    }
-
-    public Module(boolean slave) {
-      this.slave = slave;
-    }
-
-    @Override
-    protected void configure() {
-      if (slave) {
-        bind(SearchingChangeCacheImpl.class).toProvider(Providers.of(null));
-      } else {
-        cache(ID_CACHE, Project.NameKey.class, new TypeLiteral<List<CachedChange>>() {})
-            .maximumWeight(0)
-            .loader(Loader.class);
-
-        bind(SearchingChangeCacheImpl.class);
-        DynamicSet.bind(binder(), GitReferenceUpdatedListener.class)
-            .to(SearchingChangeCacheImpl.class);
-      }
-    }
-  }
-
-  @AutoValue
-  abstract static class CachedChange {
-    // Subset of fields in ChangeData, specifically fields needed to serve
-    // VisibleRefFilter without touching the database. More can be added as
-    // necessary.
-    abstract Change change();
-
-    @Nullable
-    abstract ReviewerSet reviewers();
-  }
-
-  private final LoadingCache<Project.NameKey, List<CachedChange>> cache;
-  private final ChangeData.Factory changeDataFactory;
-
-  @Inject
-  SearchingChangeCacheImpl(
-      @Named(ID_CACHE) LoadingCache<Project.NameKey, List<CachedChange>> cache,
-      ChangeData.Factory changeDataFactory) {
-    this.cache = cache;
-    this.changeDataFactory = changeDataFactory;
-  }
-
-  /**
-   * Read changes for the project from the secondary index.
-   *
-   * <p>Returned changes only include the {@code Change} object (with id, branch) and the reviewers.
-   * Additional stored fields are not loaded from the index.
-   *
-   * @param project project to read.
-   * @return list of known changes; empty if no changes.
-   */
-  public List<ChangeData> getChangeData(Project.NameKey project) {
-    try {
-      List<CachedChange> cached = cache.get(project);
-      List<ChangeData> cds = new ArrayList<>(cached.size());
-      for (CachedChange cc : cached) {
-        ChangeData cd = changeDataFactory.create(cc.change());
-        cd.setReviewers(cc.reviewers());
-        cds.add(cd);
-      }
-      return Collections.unmodifiableList(cds);
-    } catch (ExecutionException e) {
-      logger.atWarning().withCause(e).log("Cannot fetch changes for %s", project);
-      return Collections.emptyList();
-    }
-  }
-
-  @Override
-  public void onGitReferenceUpdated(GitReferenceUpdatedListener.Event event) {
-    if (event.getRefName().startsWith(RefNames.REFS_CHANGES)) {
-      cache.invalidate(new Project.NameKey(event.getProjectName()));
-    }
-  }
-
-  static class Loader extends CacheLoader<Project.NameKey, List<CachedChange>> {
-    private final OneOffRequestContext requestContext;
-    private final Provider<InternalChangeQuery> queryProvider;
-
-    @Inject
-    Loader(OneOffRequestContext requestContext, Provider<InternalChangeQuery> queryProvider) {
-      this.requestContext = requestContext;
-      this.queryProvider = queryProvider;
-    }
-
-    @Override
-    public List<CachedChange> load(Project.NameKey key) throws Exception {
-      try (TraceTimer timer = TraceContext.newTimer("Loading changes of project %s", key);
-          ManualRequestContext ctx = requestContext.open()) {
-        List<ChangeData> cds =
-            queryProvider
-                .get()
-                .setRequestedFields(ChangeField.CHANGE, ChangeField.REVIEWER)
-                .byProject(key);
-        List<CachedChange> result = new ArrayList<>(cds.size());
-        for (ChangeData cd : cds) {
-          result.add(
-              new AutoValue_SearchingChangeCacheImpl_CachedChange(cd.change(), cd.getReviewers()));
-        }
-        return Collections.unmodifiableList(result);
-      }
-    }
-  }
-}
diff --git a/java/com/google/gerrit/server/permissions/DefaultRefFilter.java b/java/com/google/gerrit/server/permissions/DefaultRefFilter.java
index 879fddd..56c22e1 100644
--- a/java/com/google/gerrit/server/permissions/DefaultRefFilter.java
+++ b/java/com/google/gerrit/server/permissions/DefaultRefFilter.java
@@ -14,7 +14,6 @@
 
 package com.google.gerrit.server.permissions;
 
-import static com.google.common.collect.ImmutableList.toImmutableList;
 import static com.google.gerrit.reviewdb.client.RefNames.REFS_CACHE_AUTOMERGE;
 import static com.google.gerrit.reviewdb.client.RefNames.REFS_CHANGES;
 import static com.google.gerrit.reviewdb.client.RefNames.REFS_CONFIG;
@@ -22,10 +21,7 @@
 import static java.util.Objects.requireNonNull;
 import static java.util.stream.Collectors.toMap;
 
-import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Maps;
-import com.google.common.flogger.FluentLogger;
 import com.google.gerrit.common.Nullable;
 import com.google.gerrit.extensions.restapi.AuthException;
 import com.google.gerrit.metrics.Counter0;
@@ -41,12 +37,11 @@
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.account.GroupCache;
 import com.google.gerrit.server.config.GerritServerConfig;
-import com.google.gerrit.server.git.SearchingChangeCacheImpl;
+import com.google.gerrit.server.git.ChangeRefCache;
 import com.google.gerrit.server.git.TagCache;
 import com.google.gerrit.server.git.TagMatcher;
 import com.google.gerrit.server.group.InternalGroup;
 import com.google.gerrit.server.notedb.ChangeNotes;
-import com.google.gerrit.server.notedb.ChangeNotes.Factory.ChangeNotesResult;
 import com.google.gerrit.server.permissions.PermissionBackend.RefFilterOptions;
 import com.google.gerrit.server.project.ProjectState;
 import com.google.gerrit.server.query.change.ChangeData;
@@ -55,10 +50,11 @@
 import com.google.inject.assistedinject.Assisted;
 import java.io.IOException;
 import java.util.ArrayList;
-import java.util.Collections;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import org.eclipse.jgit.lib.Config;
 import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.lib.Ref;
@@ -66,15 +62,13 @@
 import org.eclipse.jgit.lib.SymbolicRef;
 
 class DefaultRefFilter {
-  private static final FluentLogger logger = FluentLogger.forEnclosingClass();
-
   interface Factory {
     DefaultRefFilter create(ProjectControl projectControl);
   }
 
   private final TagCache tagCache;
   private final ChangeNotes.Factory changeNotesFactory;
-  @Nullable private final SearchingChangeCacheImpl changeCache;
+  @Nullable private final ChangeRefCache changeCache;
   private final GroupCache groupCache;
   private final PermissionBackend permissionBackend;
   private final ProjectControl projectControl;
@@ -84,14 +78,14 @@
   private final Counter0 fullFilterCount;
   private final Counter0 skipFilterCount;
   private final boolean skipFullRefEvaluationIfAllRefsAreVisible;
-
-  private Map<Change.Id, Branch.NameKey> visibleChanges;
+  private final Map<Change.Id, Branch.NameKey> visibleChanges;
+  private final Set<Change.Id> inVisibleChanges;
 
   @Inject
   DefaultRefFilter(
       TagCache tagCache,
       ChangeNotes.Factory changeNotesFactory,
-      @Nullable SearchingChangeCacheImpl changeCache,
+      @Nullable ChangeRefCache changeCache,
       GroupCache groupCache,
       PermissionBackend permissionBackend,
       @GerritServerConfig Config config,
@@ -121,6 +115,9 @@
                     "Rate of ref filter operations where we skip full evaluation"
                         + " because the user can read all refs")
                 .setRate());
+    // TODO(hiesel): Rework who can see change edits so that we can keep just a single set here.
+    this.visibleChanges = new HashMap<>();
+    this.inVisibleChanges = new HashSet<>();
   }
 
   Map<String, Ref> filter(Map<String, Ref> refs, Repository repo, RefFilterOptions opts)
@@ -161,6 +158,7 @@
 
     Map<String, Ref> result = new HashMap<>();
     List<Ref> deferredTags = new ArrayList<>();
+    changeCache.bootstrapIfNecessary(projectState.getNameKey());
 
     for (Ref ref : refs.values()) {
       String name = ref.getName();
@@ -299,110 +297,64 @@
   }
 
   private boolean visible(Repository repo, Change.Id changeId) throws PermissionBackendException {
-    if (visibleChanges == null) {
-      if (changeCache == null) {
-        visibleChanges = visibleChangesByScan(repo);
-      } else {
-        visibleChanges = visibleChangesBySearch();
-      }
+    if (visibleChanges.containsKey(changeId)) {
+      return true;
     }
-    return visibleChanges.containsKey(changeId);
+    if (inVisibleChanges.contains(changeId)) {
+      return false;
+    }
+    // TODO(hiesel): The project state should be checked once in the beginning an left alone
+    // thereafter.
+    if (!projectState.statePermitsRead()) {
+      return false;
+    }
+
+    Project.NameKey project = projectState.getNameKey();
+    try {
+      ChangeData cd =
+          changeCache.getChangeData(
+              project, changeId, repo.exactRef(RefNames.changeMetaRef(changeId)).getObjectId());
+      ChangeNotes notes = changeNotesFactory.createFromIndexedChange(cd.change());
+      try {
+        permissionBackendForProject.indexedChange(cd, notes).check(ChangePermission.READ);
+        visibleChanges.put(cd.getId(), cd.change().getDest());
+        return true;
+      } catch (AuthException e) {
+        inVisibleChanges.add(changeId);
+        return false;
+      }
+    } catch (OrmException | IOException e) {
+      throw new PermissionBackendException(
+          "Cannot load change " + changeId + " for project " + project + ", assuming not visible",
+          e);
+    }
   }
 
   private boolean visibleEdit(Repository repo, String name) throws PermissionBackendException {
     Change.Id id = Change.Id.fromEditRefPart(name);
-    // Initialize if it wasn't yet
-    if (visibleChanges == null) {
-      visible(repo, id);
-    }
     if (id == null) {
       return false;
     }
+    if (!visible(repo, id)) {
+      // Can't see the change, so can't see the edit.
+      return false;
+    }
+
     if (user.isIdentifiedUser()
-        && name.startsWith(RefNames.refsEditPrefix(user.asIdentifiedUser().getAccountId()))
-        && visible(repo, id)) {
+        && name.startsWith(RefNames.refsEditPrefix(user.asIdentifiedUser().getAccountId()))) {
+      // Own edit
       return true;
     }
-    if (visibleChanges.containsKey(id)) {
-      try {
-        // Default to READ_PRIVATE_CHANGES as there is no special permission for reading edits.
-        permissionBackendForProject
-            .ref(visibleChanges.get(id).get())
-            .check(RefPermission.READ_PRIVATE_CHANGES);
-        return true;
-      } catch (AuthException e) {
-        return false;
-      }
-    }
-    return false;
-  }
-
-  private Map<Change.Id, Branch.NameKey> visibleChangesBySearch()
-      throws PermissionBackendException {
-    Project.NameKey project = projectState.getNameKey();
-    try {
-      Map<Change.Id, Branch.NameKey> visibleChanges = new HashMap<>();
-      for (ChangeData cd : changeCache.getChangeData(project)) {
-        ChangeNotes notes = changeNotesFactory.createFromIndexedChange(cd.change());
-        if (!projectState.statePermitsRead()) {
-          continue;
-        }
-        try {
-          permissionBackendForProject.indexedChange(cd, notes).check(ChangePermission.READ);
-          visibleChanges.put(cd.getId(), cd.change().getDest());
-        } catch (AuthException e) {
-          // Do nothing.
-        }
-      }
-      return visibleChanges;
-    } catch (OrmException e) {
-      logger.atSevere().withCause(e).log(
-          "Cannot load changes for project %s, assuming no changes are visible", project);
-      return Collections.emptyMap();
-    }
-  }
-
-  private Map<Change.Id, Branch.NameKey> visibleChangesByScan(Repository repo)
-      throws PermissionBackendException {
-    Project.NameKey p = projectState.getNameKey();
-    ImmutableList<ChangeNotesResult> changes;
-    try {
-      changes = changeNotesFactory.scan(repo, p).collect(toImmutableList());
-    } catch (IOException e) {
-      logger.atSevere().withCause(e).log(
-          "Cannot load changes for project %s, assuming no changes are visible", p);
-      return Collections.emptyMap();
-    }
-
-    Map<Change.Id, Branch.NameKey> result = Maps.newHashMapWithExpectedSize(changes.size());
-    for (ChangeNotesResult notesResult : changes) {
-      ChangeNotes notes = toNotes(notesResult);
-      if (notes != null) {
-        result.put(notes.getChangeId(), notes.getChange().getDest());
-      }
-    }
-    return result;
-  }
-
-  @Nullable
-  private ChangeNotes toNotes(ChangeNotesResult r) throws PermissionBackendException {
-    if (r.error().isPresent()) {
-      logger.atWarning().withCause(r.error().get()).log(
-          "Failed to load change %s in %s", r.id(), projectState.getName());
-      return null;
-    }
-
-    if (!projectState.statePermitsRead()) {
-      return null;
-    }
 
     try {
-      permissionBackendForProject.change(r.notes()).check(ChangePermission.READ);
-      return r.notes();
+      // Default to READ_PRIVATE_CHANGES as there is no special permission for reading edits.
+      permissionBackendForProject
+          .ref(visibleChanges.get(id).get())
+          .check(RefPermission.READ_PRIVATE_CHANGES);
+      return true;
     } catch (AuthException e) {
-      // Skip.
+      return false;
     }
-    return null;
   }
 
   private boolean isMetadata(String name) {
diff --git a/java/com/google/gerrit/testing/InMemoryModule.java b/java/com/google/gerrit/testing/InMemoryModule.java
index c8cea6f..2a030ac 100644
--- a/java/com/google/gerrit/testing/InMemoryModule.java
+++ b/java/com/google/gerrit/testing/InMemoryModule.java
@@ -58,10 +58,10 @@
 import com.google.gerrit.server.config.SitePath;
 import com.google.gerrit.server.config.TrackingFooters;
 import com.google.gerrit.server.config.TrackingFootersProvider;
+import com.google.gerrit.server.git.ChangeRefCache;
 import com.google.gerrit.server.git.GarbageCollection;
 import com.google.gerrit.server.git.GitRepositoryManager;
 import com.google.gerrit.server.git.PerThreadRequestScope;
-import com.google.gerrit.server.git.SearchingChangeCacheImpl;
 import com.google.gerrit.server.git.WorkQueue;
 import com.google.gerrit.server.index.IndexModule.IndexType;
 import com.google.gerrit.server.index.account.AccountSchemaDefinitions;
@@ -168,7 +168,7 @@
     factory(PluginUser.Factory.class);
     install(new PluginApiModule());
     install(new DefaultPermissionBackendModule());
-    install(new SearchingChangeCacheImpl.Module());
+    install(new ChangeRefCache.Module());
     factory(GarbageCollection.Factory.class);
     install(new AuditModule());
 
diff --git a/javatests/com/google/gerrit/acceptance/git/ChangeRefCacheIT.java b/javatests/com/google/gerrit/acceptance/git/ChangeRefCacheIT.java
new file mode 100644
index 0000000..bf7f726
--- /dev/null
+++ b/javatests/com/google/gerrit/acceptance/git/ChangeRefCacheIT.java
@@ -0,0 +1,269 @@
+// Copyright (C) 2019 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.acceptance.git;
+
+import static com.google.common.truth.Truth.assertThat;
+import static java.util.stream.Collectors.toMap;
+
+import com.google.common.collect.ImmutableList;
+import com.google.gerrit.acceptance.AbstractDaemonTest;
+import com.google.gerrit.acceptance.AcceptanceTestRequestScope;
+import com.google.gerrit.acceptance.NoHttpd;
+import com.google.gerrit.reviewdb.client.PatchSet;
+import com.google.gerrit.reviewdb.client.RefNames;
+import com.google.gerrit.server.git.ChangeRefCache;
+import com.google.gerrit.server.permissions.PermissionBackend;
+import com.google.gerrit.server.permissions.PermissionBackend.RefFilterOptions;
+import com.google.gerrit.server.query.change.ChangeData;
+import java.io.IOException;
+import java.util.List;
+import java.util.Map;
+import java.util.function.Function;
+import javax.inject.Inject;
+import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.Repository;
+import org.junit.Before;
+import org.junit.Test;
+
+/**
+ * Tests the ChangeRefCache by running ls-remote calls and conditionally disabling the index and
+ * NoteDb. The cache is enabled by default.
+ *
+ * <p>Why are we not just testing ChangeRefCache directly? Our ref filtering code is rather complex
+ * and it is easy to get something wrong there. We want our assumptions about the performance of the
+ * cache to be validated against the entire component rather than just the cache.
+ */
+@NoHttpd
+public class ChangeRefCacheIT extends AbstractDaemonTest {
+
+  @Inject private PermissionBackend permissionBackend;
+  @Inject private ChangeRefCache changeRefCache;
+
+  @Before
+  public void setUp() throws Exception {
+    // We want full ref evaluation so that we hit the cache every time.
+    baseConfig.setBoolean("auth", null, "skipFullRefEvaluationIfAllRefsAreVisible", false);
+  }
+
+  /**
+   * Ensure we use only the change index for getting initial data populated and don't touch NoteDb.
+   */
+  @Test
+  public void useIndexForBootstrapping() throws Exception {
+    ChangeData change = createChange().getChange();
+    // TODO(hiesel) Rework as AutoClosable. Here and below.
+    changeRefCache.resetBootstrappedProjects();
+    AcceptanceTestRequestScope.Context ctx = disableDb();
+    try {
+      assertUploadPackRefs(
+          "HEAD",
+          "refs/heads/master",
+          RefNames.changeMetaRef(change.getId()),
+          change.currentPatchSet().getId().toRefName());
+    } finally {
+      enableDb(ctx);
+    }
+  }
+
+  /**
+   * Ensure we use only the change index for getting initial data populated and don't require any
+   * storage backend after that as long the data didn't change.
+   */
+  @Test
+  public void serveResultsFromCacheAfterInitialBootstrap() throws Exception {
+    ChangeData change = createChange().getChange();
+    changeRefCache.resetBootstrappedProjects();
+    AcceptanceTestRequestScope.Context ctx = disableDb();
+    try {
+      assertUploadPackRefs(
+          "HEAD",
+          "refs/heads/master",
+          RefNames.changeMetaRef(change.getId()),
+          change.currentPatchSet().getId().toRefName());
+    } finally {
+      enableDb(ctx);
+    }
+
+    // No change since our first call, so this time we don't bootstrap or touch NoteDb
+    AcceptanceTestRequestScope.Context ctx2 = disableDb();
+    try {
+      try (AutoCloseable ignored = disableChangeIndex()) {
+        assertUploadPackRefs(
+            "HEAD",
+            "refs/heads/master",
+            RefNames.changeMetaRef(change.getId()),
+            change.currentPatchSet().getId().toRefName());
+      }
+    } finally {
+      enableDb(ctx2);
+    }
+  }
+
+  /**
+   * Ensure we use only the change index for getting initial data populated and NoteDb for reloading
+   * data that changed since.
+   */
+  @Test
+  public void useIndexForBootstrappingAndDbForDeltaReload() throws Exception {
+    ChangeData change1 = createChange().getChange();
+    AcceptanceTestRequestScope.Context ctx = disableDb();
+    // Bootstrap: No NoteDb access as we expect it to use the index.
+    changeRefCache.resetBootstrappedProjects();
+    try {
+      assertUploadPackRefs(
+          "HEAD",
+          "refs/heads/master",
+          RefNames.changeMetaRef(change1.getId()),
+          change1.currentPatchSet().getId().toRefName());
+    } finally {
+      enableDb(ctx);
+    }
+    // Delta reload: No index access as we expect it to use NoteDb.
+    ChangeData change2 = createChange().getChange();
+    try (AutoCloseable ignored = disableChangeIndex()) {
+      assertUploadPackRefs(
+          "HEAD",
+          "refs/heads/master",
+          RefNames.changeMetaRef(change1.getId()),
+          change1.currentPatchSet().getId().toRefName(),
+          RefNames.changeMetaRef(change2.getId()),
+          change2.currentPatchSet().getId().toRefName());
+    }
+  }
+
+  /**
+   * Ensure we use only the change index for getting initial data populated and NoteDb for reloading
+   * data that changed since.
+   */
+  @Test
+  public void useDbForDeltaReloadOnNewPatchSet() throws Exception {
+    ChangeData change1 =
+        pushFactory
+            .create(admin.getIdent(), testRepo, "original subject", "a", "a1")
+            .to("refs/for/master")
+            .getChange();
+
+    AcceptanceTestRequestScope.Context ctx = disableDb();
+    // Bootstrap: No NoteDb access as we expect it to use the index.
+    changeRefCache.resetBootstrappedProjects();
+    try {
+      assertUploadPackRefs(
+          "HEAD",
+          "refs/heads/master",
+          RefNames.changeMetaRef(change1.getId()),
+          change1.currentPatchSet().getId().toRefName());
+    } finally {
+      enableDb(ctx);
+    }
+
+    // Delta reload: No index access as we expect it to use NoteDb.
+    ChangeData change2 =
+        pushFactory
+            .create(
+                admin.getIdent(), testRepo, "subject2", "a", "a2", change1.change().getKey().get())
+            .to("refs/for/master")
+            .getChange();
+    List<PatchSet> patchSets = ImmutableList.copyOf(change2.patchSets());
+    assertThat(patchSets).hasSize(2);
+    try (AutoCloseable ctx2 = disableChangeIndex()) {
+      assertUploadPackRefs(
+          "HEAD",
+          "refs/heads/master",
+          RefNames.changeMetaRef(change1.getId()),
+          patchSets.get(0).getId().toRefName(),
+          patchSets.get(1).getId().toRefName());
+    }
+  }
+
+  /**
+   * Ensure we use only the change index for getting initial data populated and NoteDb for reloading
+   * data that changed since.
+   */
+  @Test
+  public void useDbForIterativeFetchingOnMetadataChange() throws Exception {
+    ChangeData change1 =
+        pushFactory
+            .create(admin.getIdent(), testRepo, "original subject", "a", "a1")
+            .to("refs/for/master")
+            .getChange();
+    // Bootstrap: No NoteDb access as we expect it to use the index.
+    AcceptanceTestRequestScope.Context ctx = disableDb();
+    try {
+      changeRefCache.resetBootstrappedProjects();
+      assertUploadPackRefs(
+          "HEAD",
+          "refs/heads/master",
+          RefNames.changeMetaRef(change1.getId()),
+          change1.currentPatchSet().getId().toRefName());
+    } finally {
+      enableDb(ctx);
+    }
+
+    try (AutoCloseable ignored = disableChangeIndex()) {
+      // user can see public change
+      setApiUser(user);
+      assertUploadPackRefs(
+          "HEAD",
+          "refs/heads/master",
+          RefNames.changeMetaRef(change1.getId()),
+          change1.currentPatchSet().getId().toRefName());
+    }
+
+    // Delta reload: No index access as we expect it to use NoteDb.
+    setApiUser(admin);
+    gApi.changes().id(change1.getId().id).setPrivate(true);
+
+    try (AutoCloseable ignored = disableChangeIndex()) {
+      // user can't see private change from admin
+      setApiUser(user);
+      assertUploadPackRefs("HEAD", "refs/heads/master");
+    }
+
+    // admin adds the user as reviewer
+    setApiUser(admin);
+    gApi.changes().id(change1.getId().id).addReviewer(user.email);
+
+    try (AutoCloseable ignored = disableChangeIndex()) {
+      // Use can see private change
+      setApiUser(user);
+      assertUploadPackRefs(
+          "HEAD",
+          "refs/heads/master",
+          RefNames.changeMetaRef(change1.getId()),
+          change1.currentPatchSet().getId().toRefName());
+    }
+  }
+
+  private void assertUploadPackRefs(String... expectedRefs) throws Exception {
+    try (Repository repo = repoManager.openRepository(project)) {
+      assertRefs(repo, permissionBackend.user(user(user)).project(project), expectedRefs);
+    }
+  }
+
+  private void assertRefs(
+      Repository repo, PermissionBackend.ForProject forProject, String... expectedRefs)
+      throws Exception {
+    Map<String, Ref> all = getAllRefs(repo);
+    assertThat(forProject.filter(all, repo, RefFilterOptions.defaults()).keySet())
+        .containsExactlyElementsIn(expectedRefs);
+  }
+
+  private static Map<String, Ref> getAllRefs(Repository repo) throws IOException {
+    return repo.getRefDatabase()
+        .getRefs()
+        .stream()
+        .collect(toMap(Ref::getName, Function.identity()));
+  }
+}
diff --git a/javatests/com/google/gerrit/acceptance/git/RefAdvertisementIT.java b/javatests/com/google/gerrit/acceptance/git/RefAdvertisementIT.java
index d1c5efb..79a6957 100644
--- a/javatests/com/google/gerrit/acceptance/git/RefAdvertisementIT.java
+++ b/javatests/com/google/gerrit/acceptance/git/RefAdvertisementIT.java
@@ -25,7 +25,6 @@
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
 import com.google.gerrit.acceptance.AbstractDaemonTest;
-import com.google.gerrit.acceptance.AcceptanceTestRequestScope;
 import com.google.gerrit.acceptance.GerritConfig;
 import com.google.gerrit.acceptance.NoHttpd;
 import com.google.gerrit.acceptance.PushOneCommit;
@@ -359,7 +358,6 @@
           repo,
           permissionBackend.user(user(user)).project(project),
           // Can't use stored values from the index so DB must be enabled.
-          false,
           "HEAD",
           psRef1,
           metaRef1,
@@ -379,10 +377,10 @@
   @Test
   public void uploadPackSequencesWithAccessDatabase() throws Exception {
     try (Repository repo = repoManager.openRepository(allProjects)) {
-      assertRefs(repo, newFilter(allProjects, user), true);
+      assertRefs(repo, newFilter(allProjects, user));
 
       allowGlobalCapabilities(REGISTERED_USERS, GlobalCapability.ACCESS_DATABASE);
-      assertRefs(repo, newFilter(allProjects, user), true, "refs/sequences/changes");
+      assertRefs(repo, newFilter(allProjects, user), "refs/sequences/changes");
     }
   }
 
@@ -730,29 +728,16 @@
    */
   private void assertUploadPackRefs(String... expectedRefs) throws Exception {
     try (Repository repo = repoManager.openRepository(project)) {
-      assertRefs(repo, permissionBackend.user(user(user)).project(project), true, expectedRefs);
+      assertRefs(repo, permissionBackend.user(user(user)).project(project), expectedRefs);
     }
   }
 
   private void assertRefs(
-      Repository repo,
-      PermissionBackend.ForProject forProject,
-      boolean disableDb,
-      String... expectedRefs)
+      Repository repo, PermissionBackend.ForProject forProject, String... expectedRefs)
       throws Exception {
-    AcceptanceTestRequestScope.Context ctx = null;
-    if (disableDb) {
-      ctx = disableDb();
-    }
-    try {
-      Map<String, Ref> all = getAllRefs(repo);
-      assertThat(forProject.filter(all, repo, RefFilterOptions.defaults()).keySet())
-          .containsExactlyElementsIn(expectedRefs);
-    } finally {
-      if (disableDb) {
-        enableDb(ctx);
-      }
-    }
+    Map<String, Ref> all = getAllRefs(repo);
+    assertThat(forProject.filter(all, repo, RefFilterOptions.defaults()).keySet())
+        .containsExactlyElementsIn(expectedRefs);
   }
 
   private ReceiveCommitsAdvertiseRefsHook.Result getReceivePackRefs() throws Exception {