diff --git a/java/com/android/dialer/calllog/AnnotatedCallLogMigrator.java b/java/com/android/dialer/calllog/AnnotatedCallLogMigrator.java
index f8c6fce..e2e112c 100644
--- a/java/com/android/dialer/calllog/AnnotatedCallLogMigrator.java
+++ b/java/com/android/dialer/calllog/AnnotatedCallLogMigrator.java
@@ -18,6 +18,7 @@
 
 import android.content.Context;
 import android.content.SharedPreferences;
+import com.android.dialer.common.LogUtil;
 import com.android.dialer.common.concurrent.Annotations.BackgroundExecutor;
 import com.android.dialer.configprovider.ConfigProviderBindings;
 import com.android.dialer.inject.ApplicationContext;
@@ -39,7 +40,7 @@
   private final Context appContext;
   private final SharedPreferences sharedPreferences;
   private final RefreshAnnotatedCallLogWorker refreshAnnotatedCallLogWorker;
-  private final ListeningExecutorService backgorundExecutor;
+  private final ListeningExecutorService backgroundExecutor;
 
   @Inject
   AnnotatedCallLogMigrator(
@@ -49,7 +50,7 @@
       RefreshAnnotatedCallLogWorker refreshAnnotatedCallLogWorker) {
     this.appContext = appContext;
     this.sharedPreferences = sharedPreferences;
-    this.backgorundExecutor = backgroundExecutor;
+    this.backgroundExecutor = backgroundExecutor;
     this.refreshAnnotatedCallLogWorker = refreshAnnotatedCallLogWorker;
   }
 
@@ -58,13 +59,13 @@
    * the latency the first time call log is shown.
    */
   public ListenableFuture<Void> migrate() {
-
     return Futures.transformAsync(
         shouldMigrate(),
         (shouldMigrate) -> {
           if (!shouldMigrate) {
             return Futures.immediateFuture(null);
           }
+          LogUtil.i("AnnotatedCallLogMigrator.migrate", "migrating annotated call log");
           return Futures.transform(
               refreshAnnotatedCallLogWorker.refreshWithoutDirtyCheck(),
               (unused) -> {
@@ -77,7 +78,7 @@
   }
 
   private ListenableFuture<Boolean> shouldMigrate() {
-    return backgorundExecutor.submit(
+    return backgroundExecutor.submit(
         () -> {
           if (!(ConfigProviderBindings.get(appContext)
               .getBoolean("is_nui_shortcut_enabled", false))) {
diff --git a/java/com/android/dialer/calllog/CallLogState.java b/java/com/android/dialer/calllog/CallLogState.java
new file mode 100644
index 0000000..bdb30a7
--- /dev/null
+++ b/java/com/android/dialer/calllog/CallLogState.java
@@ -0,0 +1,67 @@
+/*
+ * Copyright (C) 2018 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.android.dialer.calllog;
+
+import android.content.SharedPreferences;
+import android.support.annotation.AnyThread;
+import android.support.annotation.VisibleForTesting;
+import com.android.dialer.common.concurrent.Annotations.BackgroundExecutor;
+import com.android.dialer.storage.Unencrypted;
+import com.google.common.util.concurrent.ListenableFuture;
+import com.google.common.util.concurrent.ListeningExecutorService;
+import javax.annotation.concurrent.ThreadSafe;
+import javax.inject.Inject;
+
+/** Provides information about the state of the annotated call log. */
+@ThreadSafe
+public final class CallLogState {
+
+  private static final String ANNOTATED_CALL_LOG_BUILT_PREF = "annotated_call_log_built";
+
+  private final SharedPreferences sharedPreferences;
+  private final ListeningExecutorService backgroundExecutor;
+
+  @VisibleForTesting
+  @Inject
+  public CallLogState(
+      @Unencrypted SharedPreferences sharedPreferences,
+      @BackgroundExecutor ListeningExecutorService backgroundExecutor) {
+    this.sharedPreferences = sharedPreferences;
+    this.backgroundExecutor = backgroundExecutor;
+  }
+
+  /**
+   * Mark the call log as having been built. This is written to disk the first time the annotated
+   * call log has been built and shouldn't ever be reset unless the user clears data.
+   */
+  @AnyThread
+  public void markBuilt() {
+    sharedPreferences.edit().putBoolean(ANNOTATED_CALL_LOG_BUILT_PREF, true).apply();
+  }
+
+  /**
+   * Returns true if the annotated call log has been built at least once.
+   *
+   * <p>It may not yet have been built if the user was just upgraded to the new call log, or they
+   * just cleared data.
+   */
+  @AnyThread
+  public ListenableFuture<Boolean> isBuilt() {
+    return backgroundExecutor.submit(
+        () -> sharedPreferences.getBoolean(ANNOTATED_CALL_LOG_BUILT_PREF, false));
+  }
+}
diff --git a/java/com/android/dialer/calllog/RefreshAnnotatedCallLogWorker.java b/java/com/android/dialer/calllog/RefreshAnnotatedCallLogWorker.java
index 3765831..e05b772 100644
--- a/java/com/android/dialer/calllog/RefreshAnnotatedCallLogWorker.java
+++ b/java/com/android/dialer/calllog/RefreshAnnotatedCallLogWorker.java
@@ -37,6 +37,7 @@
 import com.google.common.util.concurrent.Futures;
 import com.google.common.util.concurrent.ListenableFuture;
 import com.google.common.util.concurrent.ListeningExecutorService;
+import com.google.common.util.concurrent.MoreExecutors;
 import java.util.ArrayList;
 import java.util.List;
 import javax.inject.Inject;
@@ -51,6 +52,7 @@
   private final SharedPreferences sharedPreferences;
   private final MutationApplier mutationApplier;
   private final FutureTimer futureTimer;
+  private final CallLogState callLogState;
   private final ListeningExecutorService backgroundExecutorService;
   private final ListeningExecutorService lightweightExecutorService;
   // Used to ensure that only one refresh flow runs at a time. (Note that
@@ -64,6 +66,7 @@
       @Unencrypted SharedPreferences sharedPreferences,
       MutationApplier mutationApplier,
       FutureTimer futureTimer,
+      CallLogState callLogState,
       @BackgroundExecutor ListeningExecutorService backgroundExecutorService,
       @LightweightExecutor ListeningExecutorService lightweightExecutorService) {
     this.appContext = appContext;
@@ -71,17 +74,18 @@
     this.sharedPreferences = sharedPreferences;
     this.mutationApplier = mutationApplier;
     this.futureTimer = futureTimer;
+    this.callLogState = callLogState;
     this.backgroundExecutorService = backgroundExecutorService;
     this.lightweightExecutorService = lightweightExecutorService;
   }
 
   /** Checks if the annotated call log is dirty and refreshes it if necessary. */
-  public ListenableFuture<Void> refreshWithDirtyCheck() {
+  ListenableFuture<Void> refreshWithDirtyCheck() {
     return refresh(true);
   }
 
   /** Refreshes the annotated call log, bypassing dirty checks. */
-  public ListenableFuture<Void> refreshWithoutDirtyCheck() {
+  ListenableFuture<Void> refreshWithoutDirtyCheck() {
     return refresh(false);
   }
 
@@ -131,7 +135,11 @@
               "RefreshAnnotatedCallLogWorker.checkDirtyAndRebuildIfNecessary",
               "isDirty: %b",
               Preconditions.checkNotNull(isDirty));
-          return isDirty ? rebuild() : Futures.immediateFuture(null);
+          if (isDirty) {
+            return Futures.transformAsync(
+                callLogState.isBuilt(), this::rebuild, MoreExecutors.directExecutor());
+          }
+          return Futures.immediateFuture(null);
         },
         lightweightExecutorService);
   }
@@ -152,14 +160,13 @@
     return isDirtyFuture;
   }
 
-  private ListenableFuture<Void> rebuild() {
+  private ListenableFuture<Void> rebuild(boolean isBuilt) {
     CallLogMutations mutations = new CallLogMutations();
 
     // Start by filling the data sources--the system call log data source must go first!
     CallLogDataSource systemCallLogDataSource = dataSources.getSystemCallLogDataSource();
     ListenableFuture<Void> fillFuture = systemCallLogDataSource.fill(appContext, mutations);
-    String systemEventName =
-        String.format(Metrics.FILL_TEMPLATE, systemCallLogDataSource.getClass().getSimpleName());
+    String systemEventName = eventNameForFill(systemCallLogDataSource, isBuilt);
     futureTimer.applyTiming(fillFuture, systemEventName);
 
     // After the system call log data source is filled, call fill sequentially on each remaining
@@ -171,14 +178,14 @@
               fillFuture,
               unused -> {
                 ListenableFuture<Void> dataSourceFuture = dataSource.fill(appContext, mutations);
-                String eventName =
-                    String.format(Metrics.FILL_TEMPLATE, dataSource.getClass().getSimpleName());
+                String eventName = eventNameForFill(dataSource, isBuilt);
                 futureTimer.applyTiming(dataSourceFuture, eventName);
                 return dataSourceFuture;
               },
               lightweightExecutorService);
     }
-    futureTimer.applyTiming(fillFuture, Metrics.FILL_EVENT_NAME);
+
+    futureTimer.applyTiming(fillFuture, eventNameForOverallFill(isBuilt));
 
     // After all data sources are filled, apply mutations (at this point "fillFuture" is the result
     // of filling the last data source).
@@ -188,7 +195,7 @@
             unused -> {
               ListenableFuture<Void> mutationApplierFuture =
                   mutationApplier.applyToDatabase(mutations, appContext);
-              futureTimer.applyTiming(mutationApplierFuture, Metrics.APPLY_MUTATIONS_EVENT_NAME);
+              futureTimer.applyTiming(mutationApplierFuture, eventNameForApplyMutations(isBuilt));
               return mutationApplierFuture;
             },
             lightweightExecutorService);
@@ -203,13 +210,11 @@
                   dataSources.getDataSourcesIncludingSystemCallLog()) {
                 ListenableFuture<Void> dataSourceFuture = dataSource.onSuccessfulFill(appContext);
                 onSuccessfulFillFutures.add(dataSourceFuture);
-                String eventName =
-                    String.format(
-                        Metrics.ON_SUCCESSFUL_FILL_TEMPLATE, dataSource.getClass().getSimpleName());
+                String eventName = eventNameForOnSuccessfulFill(dataSource, isBuilt);
                 futureTimer.applyTiming(dataSourceFuture, eventName);
               }
               ListenableFuture<List<Void>> allFutures = Futures.allAsList(onSuccessfulFillFutures);
-              futureTimer.applyTiming(allFutures, Metrics.ON_SUCCESSFUL_FILL_EVENT_NAME);
+              futureTimer.applyTiming(allFutures, eventNameForOverallOnSuccessfulFill(isBuilt));
               return allFutures;
             },
             lightweightExecutorService);
@@ -219,8 +224,40 @@
         onSuccessfulFillFuture,
         unused -> {
           sharedPreferences.edit().putBoolean(SharedPrefKeys.FORCE_REBUILD, false).apply();
+          callLogState.markBuilt();
           return null;
         },
         backgroundExecutorService);
   }
+
+  private static String eventNameForFill(CallLogDataSource dataSource, boolean isBuilt) {
+    return String.format(
+        !isBuilt ? Metrics.INITIAL_FILL_TEMPLATE : Metrics.FILL_TEMPLATE,
+        dataSource.getClass().getSimpleName());
+  }
+
+  private static String eventNameForOverallFill(boolean isBuilt) {
+    return !isBuilt ? Metrics.INITIAL_FILL_EVENT_NAME : Metrics.FILL_EVENT_NAME;
+  }
+
+  private static String eventNameForOnSuccessfulFill(
+      CallLogDataSource dataSource, boolean isBuilt) {
+    return String.format(
+        !isBuilt
+            ? Metrics.INITIAL_ON_SUCCESSFUL_FILL_TEMPLATE
+            : Metrics.ON_SUCCESSFUL_FILL_TEMPLATE,
+        dataSource.getClass().getSimpleName());
+  }
+
+  private static String eventNameForOverallOnSuccessfulFill(boolean isBuilt) {
+    return !isBuilt
+        ? Metrics.INITIAL_ON_SUCCESSFUL_FILL_EVENT_NAME
+        : Metrics.ON_SUCCESSFUL_FILL_EVENT_NAME;
+  }
+
+  private static String eventNameForApplyMutations(boolean isBuilt) {
+    return !isBuilt
+        ? Metrics.INITIAL_APPLY_MUTATIONS_EVENT_NAME
+        : Metrics.APPLY_MUTATIONS_EVENT_NAME;
+  }
 }
diff --git a/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java b/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
index 40788f4..ff8c931 100644
--- a/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
+++ b/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
@@ -39,6 +39,7 @@
 import com.android.dialer.common.concurrent.Annotations.LightweightExecutor;
 import com.android.dialer.phonelookup.PhoneLookup;
 import com.android.dialer.phonelookup.PhoneLookupInfo;
+import com.android.dialer.phonelookup.composite.CompositePhoneLookup;
 import com.android.dialer.phonelookup.database.contract.PhoneLookupHistoryContract;
 import com.android.dialer.phonelookup.database.contract.PhoneLookupHistoryContract.PhoneLookupHistory;
 import com.google.common.collect.ImmutableMap;
@@ -63,7 +64,7 @@
  */
 public final class PhoneLookupDataSource implements CallLogDataSource {
 
-  private final PhoneLookup<PhoneLookupInfo> phoneLookup;
+  private final CompositePhoneLookup compositePhoneLookup;
   private final ListeningExecutorService backgroundExecutorService;
   private final ListeningExecutorService lightweightExecutorService;
 
@@ -86,10 +87,10 @@
 
   @Inject
   PhoneLookupDataSource(
-      PhoneLookup<PhoneLookupInfo> phoneLookup,
+      CompositePhoneLookup compositePhoneLookup,
       @BackgroundExecutor ListeningExecutorService backgroundExecutorService,
       @LightweightExecutor ListeningExecutorService lightweightExecutorService) {
-    this.phoneLookup = phoneLookup;
+    this.compositePhoneLookup = compositePhoneLookup;
     this.backgroundExecutorService = backgroundExecutorService;
     this.lightweightExecutorService = lightweightExecutorService;
   }
@@ -99,7 +100,8 @@
     ListenableFuture<ImmutableSet<DialerPhoneNumber>> phoneNumbers =
         backgroundExecutorService.submit(
             () -> queryDistinctDialerPhoneNumbersFromAnnotatedCallLog(appContext));
-    return Futures.transformAsync(phoneNumbers, phoneLookup::isDirty, lightweightExecutorService);
+    return Futures.transformAsync(
+        phoneNumbers, compositePhoneLookup::isDirty, lightweightExecutorService);
   }
 
   /**
@@ -157,10 +159,13 @@
                 queryPhoneLookupHistoryForNumbers(appContext, annotatedCallLogIdsByNumber.keySet()),
             backgroundExecutorService);
 
-    // Use the original info map to generate the updated info map by delegating to phoneLookup.
+    // Use the original info map to generate the updated info map by delegating to
+    // compositePhoneLookup.
     ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> updatedInfoMapFuture =
         Futures.transformAsync(
-            originalInfoMapFuture, phoneLookup::getMostRecentInfo, lightweightExecutorService);
+            originalInfoMapFuture,
+            compositePhoneLookup::getMostRecentInfo,
+            lightweightExecutorService);
 
     // This is the computation that will use the result of all of the above.
     Callable<ImmutableMap<Long, PhoneLookupInfo>> computeRowsToUpdate =
@@ -241,7 +246,7 @@
     // the AnnotatedCallLog and PhoneLookupHistory have been successfully updated.
     return Futures.transformAsync(
         writePhoneLookupHistory,
-        unused -> phoneLookup.onSuccessfulBulkUpdate(),
+        unused -> compositePhoneLookup.onSuccessfulBulkUpdate(),
         lightweightExecutorService);
   }
 
@@ -286,7 +291,7 @@
   @MainThread
   @Override
   public void registerContentObservers(Context appContext) {
-    phoneLookup.registerContentObservers(appContext);
+    compositePhoneLookup.registerContentObservers(appContext);
   }
 
   private static ImmutableSet<DialerPhoneNumber>
diff --git a/java/com/android/dialer/calllog/ui/RealtimeRowProcessor.java b/java/com/android/dialer/calllog/ui/RealtimeRowProcessor.java
index 69c4319..22c3a3c 100644
--- a/java/com/android/dialer/calllog/ui/RealtimeRowProcessor.java
+++ b/java/com/android/dialer/calllog/ui/RealtimeRowProcessor.java
@@ -31,8 +31,8 @@
 import com.android.dialer.common.concurrent.Annotations.Ui;
 import com.android.dialer.common.concurrent.ThreadUtil;
 import com.android.dialer.inject.ApplicationContext;
-import com.android.dialer.phonelookup.PhoneLookup;
 import com.android.dialer.phonelookup.PhoneLookupInfo;
+import com.android.dialer.phonelookup.composite.CompositePhoneLookup;
 import com.android.dialer.phonelookup.database.contract.PhoneLookupHistoryContract;
 import com.android.dialer.phonelookup.database.contract.PhoneLookupHistoryContract.PhoneLookupHistory;
 import com.google.common.collect.ImmutableMap;
@@ -68,7 +68,7 @@
   @VisibleForTesting static final long BATCH_WAIT_MILLIS = TimeUnit.SECONDS.toMillis(3);
 
   private final Context appContext;
-  private final PhoneLookup<PhoneLookupInfo> phoneLookup;
+  private final CompositePhoneLookup compositePhoneLookup;
   private final ListeningExecutorService uiExecutor;
   private final ListeningExecutorService backgroundExecutor;
 
@@ -83,11 +83,11 @@
       @ApplicationContext Context appContext,
       @Ui ListeningExecutorService uiExecutor,
       @BackgroundExecutor ListeningExecutorService backgroundExecutor,
-      PhoneLookup<PhoneLookupInfo> phoneLookup) {
+      CompositePhoneLookup compositePhoneLookup) {
     this.appContext = appContext;
     this.uiExecutor = uiExecutor;
     this.backgroundExecutor = backgroundExecutor;
-    this.phoneLookup = phoneLookup;
+    this.compositePhoneLookup = compositePhoneLookup;
   }
 
   /**
@@ -106,7 +106,8 @@
       return Futures.immediateFuture(applyPhoneLookupInfoToRow(cachedPhoneLookupInfo, row));
     }
 
-    ListenableFuture<PhoneLookupInfo> phoneLookupInfoFuture = phoneLookup.lookup(row.number());
+    ListenableFuture<PhoneLookupInfo> phoneLookupInfoFuture =
+        compositePhoneLookup.lookup(row.number());
     return Futures.transform(
         phoneLookupInfoFuture,
         phoneLookupInfo -> {
diff --git a/java/com/android/dialer/metrics/Metrics.java b/java/com/android/dialer/metrics/Metrics.java
index 8c18ac9..383b3a3 100644
--- a/java/com/android/dialer/metrics/Metrics.java
+++ b/java/com/android/dialer/metrics/Metrics.java
@@ -34,12 +34,21 @@
   String NEW_CALL_LOG_JANK_EVENT_NAME = "NewCallLog.Jank";
 
   // Events related to refreshing the annotated call log.
+  String INITIAL_FILL_EVENT_NAME = "RefreshAnnotatedCallLog.Initial.Fill";
+  String INITIAL_ON_SUCCESSFUL_FILL_EVENT_NAME = "RefreshAnnotatedCallLog.Initial.OnSuccessfulFill";
+  String INITIAL_APPLY_MUTATIONS_EVENT_NAME = "RefreshAnnotatedCallLog.Initial.ApplyMutations";
+
   String IS_DIRTY_EVENT_NAME = "RefreshAnnotatedCallLog.IsDirty";
   String FILL_EVENT_NAME = "RefreshAnnotatedCallLog.Fill";
   String ON_SUCCESSFUL_FILL_EVENT_NAME = "RefreshAnnotatedCallLog.OnSuccessfulFill";
   String APPLY_MUTATIONS_EVENT_NAME = "RefreshAnnotatedCallLog.ApplyMutations";
 
   // These templates are prefixed with a CallLogDataSource or PhoneLookup simple class name.
+  String INITIAL_FILL_TEMPLATE = "%s.Initial.Fill";
+  String INITIAL_GET_MOST_RECENT_INFO_TEMPLATE = "%s.Initial.GetMostRecentInfo";
+  String INITIAL_ON_SUCCESSFUL_FILL_TEMPLATE = "%s.Initial.OnSuccessfulFill";
+  String INITIAL_ON_SUCCESSFUL_BULK_UPDATE_TEMPLATE = "%s.Initial.OnSuccessfulBulkUpdate";
+
   String IS_DIRTY_TEMPLATE = "%s.IsDirty";
   String FILL_TEMPLATE = "%s.Fill";
   String GET_MOST_RECENT_INFO_TEMPLATE = "%s.GetMostRecentInfo";
diff --git a/java/com/android/dialer/phonelookup/PhoneLookupComponent.java b/java/com/android/dialer/phonelookup/PhoneLookupComponent.java
index f59886b..832587c 100644
--- a/java/com/android/dialer/phonelookup/PhoneLookupComponent.java
+++ b/java/com/android/dialer/phonelookup/PhoneLookupComponent.java
@@ -17,13 +17,14 @@
 
 import android.content.Context;
 import com.android.dialer.inject.HasRootComponent;
+import com.android.dialer.phonelookup.composite.CompositePhoneLookup;
 import dagger.Subcomponent;
 
 /** Dagger component for the PhoneLookup package. */
 @Subcomponent
 public abstract class PhoneLookupComponent {
 
-  public abstract PhoneLookup<PhoneLookupInfo> phoneLookup();
+  public abstract CompositePhoneLookup compositePhoneLookup();
 
   public static PhoneLookupComponent get(Context context) {
     return ((HasComponent) ((HasRootComponent) context.getApplicationContext()).component())
diff --git a/java/com/android/dialer/phonelookup/PhoneLookupModule.java b/java/com/android/dialer/phonelookup/PhoneLookupModule.java
index d4cd60a..3e21e7c 100644
--- a/java/com/android/dialer/phonelookup/PhoneLookupModule.java
+++ b/java/com/android/dialer/phonelookup/PhoneLookupModule.java
@@ -18,7 +18,6 @@
 
 import com.android.dialer.phonelookup.blockednumber.DialerBlockedNumberPhoneLookup;
 import com.android.dialer.phonelookup.blockednumber.SystemBlockedNumberPhoneLookup;
-import com.android.dialer.phonelookup.composite.CompositePhoneLookup;
 import com.android.dialer.phonelookup.cp2.Cp2LocalPhoneLookup;
 import com.android.dialer.phonelookup.cp2.Cp2RemotePhoneLookup;
 import com.android.dialer.phonelookup.spam.SpamPhoneLookup;
@@ -45,10 +44,4 @@
         systemBlockedNumberPhoneLookup,
         spamPhoneLookup);
   }
-
-  @Provides
-  static PhoneLookup<PhoneLookupInfo> providePhoneLookup(
-      CompositePhoneLookup compositePhoneLookup) {
-    return compositePhoneLookup;
-  }
 }
diff --git a/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java b/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java
index 7be7732..0d84a2e 100644
--- a/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java
+++ b/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java
@@ -18,7 +18,9 @@
 
 import android.content.Context;
 import android.support.annotation.MainThread;
+import android.support.annotation.VisibleForTesting;
 import com.android.dialer.DialerPhoneNumber;
+import com.android.dialer.calllog.CallLogState;
 import com.android.dialer.common.LogUtil;
 import com.android.dialer.common.concurrent.Annotations.LightweightExecutor;
 import com.android.dialer.common.concurrent.DialerFutures;
@@ -36,6 +38,7 @@
 import com.google.common.util.concurrent.Futures;
 import com.google.common.util.concurrent.ListenableFuture;
 import com.google.common.util.concurrent.ListeningExecutorService;
+import com.google.common.util.concurrent.MoreExecutors;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Map;
@@ -44,20 +47,26 @@
 /**
  * {@link PhoneLookup} which delegates to a configured set of {@link PhoneLookup PhoneLookups},
  * iterating, prioritizing, and coalescing data as necessary.
+ *
+ * <p>TODO(zachh): Consider renaming and moving this file since it does not implement PhoneLookup.
  */
-public final class CompositePhoneLookup implements PhoneLookup<PhoneLookupInfo> {
+public final class CompositePhoneLookup {
 
   private final ImmutableList<PhoneLookup> phoneLookups;
   private final FutureTimer futureTimer;
+  private final CallLogState callLogState;
   private final ListeningExecutorService lightweightExecutorService;
 
+  @VisibleForTesting
   @Inject
-  CompositePhoneLookup(
+  public CompositePhoneLookup(
       ImmutableList<PhoneLookup> phoneLookups,
       FutureTimer futureTimer,
+      CallLogState callLogState,
       @LightweightExecutor ListeningExecutorService lightweightExecutorService) {
     this.phoneLookups = phoneLookups;
     this.futureTimer = futureTimer;
+    this.callLogState = callLogState;
     this.lightweightExecutorService = lightweightExecutorService;
   }
 
@@ -68,7 +77,6 @@
    * the dependent lookups does not complete, the returned future will also not complete.
    */
   @SuppressWarnings({"unchecked", "rawtype"})
-  @Override
   public ListenableFuture<PhoneLookupInfo> lookup(DialerPhoneNumber dialerPhoneNumber) {
     // TODO(zachh): Add short-circuiting logic so that this call is not blocked on low-priority
     // lookups finishing when a higher-priority one has already finished.
@@ -98,7 +106,10 @@
     return combinedFuture;
   }
 
-  @Override
+  /**
+   * Delegates to sub-lookups' {@link PhoneLookup#isDirty(ImmutableSet)} completing when the first
+   * sub-lookup which returns true completes.
+   */
   public ListenableFuture<Boolean> isDirty(ImmutableSet<DialerPhoneNumber> phoneNumbers) {
     List<ListenableFuture<Boolean>> futures = new ArrayList<>();
     for (PhoneLookup<?> phoneLookup : phoneLookups) {
@@ -125,46 +136,50 @@
    * the dependent lookups does not complete, the returned future will also not complete.
    */
   @SuppressWarnings("unchecked")
-  @Override
   public ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> getMostRecentInfo(
       ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap) {
-    List<ListenableFuture<ImmutableMap<DialerPhoneNumber, ?>>> futures = new ArrayList<>();
-    for (PhoneLookup phoneLookup : phoneLookups) {
-      futures.add(buildSubmapAndGetMostRecentInfo(existingInfoMap, phoneLookup));
-    }
-    ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> combinedFuture =
-        Futures.transform(
-            Futures.allAsList(futures),
-            (allMaps) -> {
-              ImmutableMap.Builder<DialerPhoneNumber, PhoneLookupInfo> combinedMap =
-                  ImmutableMap.builder();
-              for (DialerPhoneNumber dialerPhoneNumber : existingInfoMap.keySet()) {
-                PhoneLookupInfo.Builder combinedInfo = PhoneLookupInfo.newBuilder();
-                for (int i = 0; i < allMaps.size(); i++) {
-                  ImmutableMap<DialerPhoneNumber, ?> map = allMaps.get(i);
-                  Object subInfo = map.get(dialerPhoneNumber);
-                  if (subInfo == null) {
-                    throw new IllegalStateException(
-                        "A sublookup didn't return an info for number: "
-                            + LogUtil.sanitizePhoneNumber(dialerPhoneNumber.getNormalizedNumber()));
-                  }
-                  phoneLookups.get(i).setSubMessage(combinedInfo, subInfo);
-                }
-                combinedMap.put(dialerPhoneNumber, combinedInfo.build());
-              }
-              return combinedMap.build();
-            },
-            lightweightExecutorService);
-    String eventName =
-        String.format(
-            Metrics.GET_MOST_RECENT_INFO_TEMPLATE, CompositePhoneLookup.class.getSimpleName());
-    futureTimer.applyTiming(combinedFuture, eventName);
-    return combinedFuture;
+    return Futures.transformAsync(
+        callLogState.isBuilt(),
+        isBuilt -> {
+          List<ListenableFuture<ImmutableMap<DialerPhoneNumber, ?>>> futures = new ArrayList<>();
+          for (PhoneLookup phoneLookup : phoneLookups) {
+            futures.add(buildSubmapAndGetMostRecentInfo(existingInfoMap, phoneLookup, isBuilt));
+          }
+          ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> combinedFuture =
+              Futures.transform(
+                  Futures.allAsList(futures),
+                  (allMaps) -> {
+                    ImmutableMap.Builder<DialerPhoneNumber, PhoneLookupInfo> combinedMap =
+                        ImmutableMap.builder();
+                    for (DialerPhoneNumber dialerPhoneNumber : existingInfoMap.keySet()) {
+                      PhoneLookupInfo.Builder combinedInfo = PhoneLookupInfo.newBuilder();
+                      for (int i = 0; i < allMaps.size(); i++) {
+                        ImmutableMap<DialerPhoneNumber, ?> map = allMaps.get(i);
+                        Object subInfo = map.get(dialerPhoneNumber);
+                        if (subInfo == null) {
+                          throw new IllegalStateException(
+                              "A sublookup didn't return an info for number: "
+                                  + LogUtil.sanitizePhoneNumber(
+                                      dialerPhoneNumber.getNormalizedNumber()));
+                        }
+                        phoneLookups.get(i).setSubMessage(combinedInfo, subInfo);
+                      }
+                      combinedMap.put(dialerPhoneNumber, combinedInfo.build());
+                    }
+                    return combinedMap.build();
+                  },
+                  lightweightExecutorService);
+          String eventName = getMostRecentInfoEventName(this, isBuilt);
+          futureTimer.applyTiming(combinedFuture, eventName);
+          return combinedFuture;
+        },
+        MoreExecutors.directExecutor());
   }
 
   private <T> ListenableFuture<ImmutableMap<DialerPhoneNumber, T>> buildSubmapAndGetMostRecentInfo(
       ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap,
-      PhoneLookup<T> phoneLookup) {
+      PhoneLookup<T> phoneLookup,
+      boolean isBuilt) {
     Map<DialerPhoneNumber, T> submap =
         Maps.transformEntries(
             existingInfoMap,
@@ -172,50 +187,54 @@
                 phoneLookup.getSubMessage(existingInfoMap.get(dialerPhoneNumber)));
     ListenableFuture<ImmutableMap<DialerPhoneNumber, T>> mostRecentInfoFuture =
         phoneLookup.getMostRecentInfo(ImmutableMap.copyOf(submap));
-    String eventName =
-        String.format(
-            Metrics.GET_MOST_RECENT_INFO_TEMPLATE, phoneLookup.getClass().getSimpleName());
+    String eventName = getMostRecentInfoEventName(phoneLookup, isBuilt);
     futureTimer.applyTiming(mostRecentInfoFuture, eventName);
     return mostRecentInfoFuture;
   }
 
-  @Override
-  public void setSubMessage(PhoneLookupInfo.Builder destination, PhoneLookupInfo source) {
-    throw new UnsupportedOperationException(
-        "This method is only expected to be called by CompositePhoneLookup itself");
-  }
-
-  @Override
-  public PhoneLookupInfo getSubMessage(PhoneLookupInfo phoneLookupInfo) {
-    throw new UnsupportedOperationException(
-        "This method is only expected to be called by CompositePhoneLookup itself");
-  }
-
-  @Override
+  /** Delegates to sub-lookups' {@link PhoneLookup#onSuccessfulBulkUpdate()}. */
   public ListenableFuture<Void> onSuccessfulBulkUpdate() {
-    List<ListenableFuture<Void>> futures = new ArrayList<>();
-    for (PhoneLookup<?> phoneLookup : phoneLookups) {
-      ListenableFuture<Void> phoneLookupFuture = phoneLookup.onSuccessfulBulkUpdate();
-      futures.add(phoneLookupFuture);
-      String eventName =
-          String.format(
-              Metrics.ON_SUCCESSFUL_BULK_UPDATE_TEMPLATE, phoneLookup.getClass().getSimpleName());
-      futureTimer.applyTiming(phoneLookupFuture, eventName);
-    }
-    ListenableFuture<Void> combinedFuture =
-        Futures.transform(Futures.allAsList(futures), unused -> null, lightweightExecutorService);
-    String eventName =
-        String.format(
-            Metrics.ON_SUCCESSFUL_BULK_UPDATE_TEMPLATE, CompositePhoneLookup.class.getSimpleName());
-    futureTimer.applyTiming(combinedFuture, eventName);
-    return combinedFuture;
+    return Futures.transformAsync(
+        callLogState.isBuilt(),
+        isBuilt -> {
+          List<ListenableFuture<Void>> futures = new ArrayList<>();
+          for (PhoneLookup<?> phoneLookup : phoneLookups) {
+            ListenableFuture<Void> phoneLookupFuture = phoneLookup.onSuccessfulBulkUpdate();
+            futures.add(phoneLookupFuture);
+            String eventName = onSuccessfulBulkUpdatedEventName(phoneLookup, isBuilt);
+            futureTimer.applyTiming(phoneLookupFuture, eventName);
+          }
+          ListenableFuture<Void> combinedFuture =
+              Futures.transform(
+                  Futures.allAsList(futures), unused -> null, lightweightExecutorService);
+          String eventName = onSuccessfulBulkUpdatedEventName(this, isBuilt);
+          futureTimer.applyTiming(combinedFuture, eventName);
+          return combinedFuture;
+        },
+        MoreExecutors.directExecutor());
   }
 
-  @Override
+  /** Delegates to sub-lookups' {@link PhoneLookup#registerContentObservers(Context)}. */
   @MainThread
   public void registerContentObservers(Context appContext) {
     for (PhoneLookup phoneLookup : phoneLookups) {
       phoneLookup.registerContentObservers(appContext);
     }
   }
+
+  private static String getMostRecentInfoEventName(Object classNameSource, boolean isBuilt) {
+    return String.format(
+        !isBuilt
+            ? Metrics.INITIAL_GET_MOST_RECENT_INFO_TEMPLATE
+            : Metrics.GET_MOST_RECENT_INFO_TEMPLATE,
+        classNameSource.getClass().getSimpleName());
+  }
+
+  private static String onSuccessfulBulkUpdatedEventName(Object classNameSource, boolean isBuilt) {
+    return String.format(
+        !isBuilt
+            ? Metrics.INITIAL_ON_SUCCESSFUL_BULK_UPDATE_TEMPLATE
+            : Metrics.ON_SUCCESSFUL_BULK_UPDATE_TEMPLATE,
+        classNameSource.getClass().getSimpleName());
+  }
 }
diff --git a/java/com/android/incallui/PhoneLookupHistoryRecorder.java b/java/com/android/incallui/PhoneLookupHistoryRecorder.java
index 017e6f4..802bf63 100644
--- a/java/com/android/incallui/PhoneLookupHistoryRecorder.java
+++ b/java/com/android/incallui/PhoneLookupHistoryRecorder.java
@@ -69,7 +69,9 @@
         Futures.transformAsync(
             numberFuture,
             dialerPhoneNumber ->
-                PhoneLookupComponent.get(appContext).phoneLookup().lookup(dialerPhoneNumber),
+                PhoneLookupComponent.get(appContext)
+                    .compositePhoneLookup()
+                    .lookup(dialerPhoneNumber),
             MoreExecutors.directExecutor());
 
     Futures.addCallback(