diff --git a/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java b/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
index 90298a1..b3bbf3c 100644
--- a/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
+++ b/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
@@ -22,16 +22,30 @@
 import android.database.Cursor;
 import android.support.annotation.MainThread;
 import android.support.annotation.WorkerThread;
+import android.text.TextUtils;
+import android.util.ArrayMap;
+import android.util.ArraySet;
 import com.android.dialer.DialerPhoneNumber;
 import com.android.dialer.calllog.database.contract.AnnotatedCallLogContract.AnnotatedCallLog;
 import com.android.dialer.calllog.datasources.CallLogDataSource;
 import com.android.dialer.calllog.datasources.CallLogMutations;
 import com.android.dialer.common.LogUtil;
 import com.android.dialer.phonelookup.PhoneLookup;
+import com.android.dialer.phonelookup.PhoneLookupInfo;
+import com.android.dialer.phonelookup.database.contract.PhoneLookupHistoryContract.PhoneLookupHistory;
+import com.android.dialer.phonenumberproto.DialerPhoneNumberUtil;
 import com.android.dialer.storage.Unencrypted;
+import com.google.auto.value.AutoValue;
+import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Maps;
+import com.google.i18n.phonenumbers.PhoneNumberUtil;
 import com.google.protobuf.InvalidProtocolBufferException;
+import java.util.Arrays;
 import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
 import java.util.concurrent.ExecutionException;
 import javax.inject.Inject;
 
@@ -71,10 +85,87 @@
     }
   }
 
+  /**
+   * {@inheritDoc}
+   *
+   * <p>This method uses the following algorithm:
+   *
+   * <ul>
+   *   <li>Selects the distinct DialerPhoneNumbers from the AnnotatedCallLog
+   *   <li>Uses them to fetch the current information from PhoneLookupHistory, in order to construct
+   *       a map from DialerPhoneNumber to PhoneLookupInfo
+   *       <ul>
+   *         <li>If no PhoneLookupInfo is found (e.g. app data was cleared?) an empty value is used.
+   *       </ul>
+   *   <li>Looks through the provided set of mutations
+   *   <li>For inserts, uses the contents of PhoneLookupHistory to populate the fields of the
+   *       provided mutations. (Note that at this point, data may not be fully up-to-date, but the
+   *       next steps will take care of that.)
+   *   <li>Uses all of the numbers from AnnotatedCallLog along with the callLogLastUpdated timestamp
+   *       to invoke CompositePhoneLookup:bulkUpdate
+   *   <li>Looks through the results of bulkUpdate
+   *       <ul>
+   *         <li>For each number, checks if the original PhoneLookupInfo differs from the new one or
+   *             if the lastModified date from PhoneLookupInfo table is newer than
+   *             callLogLastUpdated.
+   *         <li>If so, it applies the update to the mutations and (in onSuccessfulFill) writes the
+   *             new value back to the PhoneLookupHistory along with current time as the
+   *             lastModified date.
+   *       </ul>
+   * </ul>
+   */
   @WorkerThread
   @Override
   public void fill(Context appContext, CallLogMutations mutations) {
-    // TODO(zachh): Implementation.
+    Map<DialerPhoneNumber, Set<Long>> annotatedCallLogIdsByNumber =
+        queryIdAndNumberFromAnnotatedCallLog(appContext);
+    Map<DialerPhoneNumber, PhoneLookupInfoAndTimestamp> originalPhoneLookupHistoryDataByNumber =
+        queryPhoneLookupHistoryForNumbers(appContext, annotatedCallLogIdsByNumber.keySet());
+    ImmutableMap.Builder<Long, PhoneLookupInfo> originalPhoneLookupHistoryDataByAnnotatedCallLogId =
+        ImmutableMap.builder();
+    for (Entry<DialerPhoneNumber, PhoneLookupInfoAndTimestamp> entry :
+        originalPhoneLookupHistoryDataByNumber.entrySet()) {
+      DialerPhoneNumber dialerPhoneNumber = entry.getKey();
+      PhoneLookupInfoAndTimestamp phoneLookupInfoAndTimestamp = entry.getValue();
+      for (Long id : annotatedCallLogIdsByNumber.get(dialerPhoneNumber)) {
+        originalPhoneLookupHistoryDataByAnnotatedCallLogId.put(
+            id, phoneLookupInfoAndTimestamp.phoneLookupInfo());
+      }
+    }
+    populateInserts(originalPhoneLookupHistoryDataByAnnotatedCallLogId.build(), mutations);
+
+    ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> originalPhoneLookupInfosByNumber =
+        ImmutableMap.copyOf(
+            Maps.transformValues(
+                originalPhoneLookupHistoryDataByNumber,
+                PhoneLookupInfoAndTimestamp::phoneLookupInfo));
+
+    long lastTimestampProcessedSharedPrefValue =
+        sharedPreferences.getLong(PREF_LAST_TIMESTAMP_PROCESSED, 0L);
+    // TODO(zachh): Push last timestamp processed down into each individual lookup.
+    ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> updatedInfoMap;
+    try {
+      updatedInfoMap =
+          phoneLookup
+              .bulkUpdate(originalPhoneLookupInfosByNumber, lastTimestampProcessedSharedPrefValue)
+              .get();
+    } catch (InterruptedException | ExecutionException e) {
+      throw new IllegalStateException(e);
+    }
+    ImmutableMap.Builder<Long, PhoneLookupInfo> rowsToUpdate = ImmutableMap.builder();
+    for (Entry<DialerPhoneNumber, PhoneLookupInfo> entry : updatedInfoMap.entrySet()) {
+      DialerPhoneNumber dialerPhoneNumber = entry.getKey();
+      PhoneLookupInfo upToDateInfo = entry.getValue();
+      long numberLastModified =
+          originalPhoneLookupHistoryDataByNumber.get(dialerPhoneNumber).lastModified();
+      if (numberLastModified > lastTimestampProcessedSharedPrefValue
+          || !originalPhoneLookupInfosByNumber.get(dialerPhoneNumber).equals(upToDateInfo)) {
+        for (Long id : annotatedCallLogIdsByNumber.get(dialerPhoneNumber)) {
+          rowsToUpdate.put(id, upToDateInfo);
+        }
+      }
+    }
+    updateMutations(rowsToUpdate.build(), mutations);
   }
 
   @WorkerThread
@@ -136,4 +227,207 @@
     }
     return numbers.build();
   }
+
+  private Map<DialerPhoneNumber, Set<Long>> queryIdAndNumberFromAnnotatedCallLog(
+      Context appContext) {
+    Map<DialerPhoneNumber, Set<Long>> idsByNumber = new ArrayMap<>();
+
+    try (Cursor cursor =
+        appContext
+            .getContentResolver()
+            .query(
+                AnnotatedCallLog.CONTENT_URI,
+                new String[] {AnnotatedCallLog._ID, AnnotatedCallLog.NUMBER},
+                null,
+                null,
+                null)) {
+
+      if (cursor == null) {
+        LogUtil.e("PhoneLookupDataSource.queryIdAndNumberFromAnnotatedCallLog", "null cursor");
+        return ImmutableMap.of();
+      }
+
+      if (cursor.moveToFirst()) {
+        int idColumn = cursor.getColumnIndexOrThrow(AnnotatedCallLog._ID);
+        int numberColumn = cursor.getColumnIndexOrThrow(AnnotatedCallLog.NUMBER);
+        do {
+          long id = cursor.getLong(idColumn);
+          byte[] blob = cursor.getBlob(numberColumn);
+          if (blob == null) {
+            // Not all [incoming] calls have associated phone numbers.
+            continue;
+          }
+          DialerPhoneNumber dialerPhoneNumber;
+          try {
+            dialerPhoneNumber = DialerPhoneNumber.parseFrom(blob);
+          } catch (InvalidProtocolBufferException e) {
+            throw new IllegalStateException(e);
+          }
+          Set<Long> ids = idsByNumber.get(dialerPhoneNumber);
+          if (ids == null) {
+            ids = new ArraySet<>();
+            idsByNumber.put(dialerPhoneNumber, ids);
+          }
+          ids.add(id);
+        } while (cursor.moveToNext());
+      }
+    }
+    return idsByNumber;
+  }
+
+  private Map<DialerPhoneNumber, PhoneLookupInfoAndTimestamp> queryPhoneLookupHistoryForNumbers(
+      Context appContext, Set<DialerPhoneNumber> uniqueDialerPhoneNumbers) {
+    DialerPhoneNumberUtil dialerPhoneNumberUtil =
+        new DialerPhoneNumberUtil(PhoneNumberUtil.getInstance());
+    Map<DialerPhoneNumber, String> dialerPhoneNumberToNormalizedNumbers =
+        Maps.asMap(uniqueDialerPhoneNumbers, dialerPhoneNumberUtil::formatToE164);
+
+    // Convert values to a set to remove any duplicates that are the result of two
+    // DialerPhoneNumbers mapping to the same normalized number.
+    String[] normalizedNumbers =
+        dialerPhoneNumberToNormalizedNumbers.values().toArray(new String[] {});
+    String[] questionMarks = new String[normalizedNumbers.length];
+    Arrays.fill(questionMarks, "?");
+    String selection =
+        PhoneLookupHistory.NORMALIZED_NUMBER + " in (" + TextUtils.join(",", questionMarks) + ")";
+
+    Map<String, PhoneLookupInfoAndTimestamp> normalizedNumberToInfoMap = new ArrayMap<>();
+    try (Cursor cursor =
+        appContext
+            .getContentResolver()
+            .query(
+                PhoneLookupHistory.CONTENT_URI,
+                new String[] {
+                  PhoneLookupHistory.NORMALIZED_NUMBER,
+                  PhoneLookupHistory.PHONE_LOOKUP_INFO,
+                  PhoneLookupHistory.LAST_MODIFIED
+                },
+                selection,
+                normalizedNumbers,
+                null)) {
+
+      if (cursor == null) {
+        LogUtil.e("PhoneLookupDataSource.queryPhoneLookupHistoryForNumbers", "null cursor");
+        return ImmutableMap.of();
+      }
+
+      if (cursor.moveToFirst()) {
+        int normalizedNumberColumn =
+            cursor.getColumnIndexOrThrow(PhoneLookupHistory.NORMALIZED_NUMBER);
+        int phoneLookupInfoColumn =
+            cursor.getColumnIndexOrThrow(PhoneLookupHistory.PHONE_LOOKUP_INFO);
+        int lastModifiedColumn = cursor.getColumnIndexOrThrow(PhoneLookupHistory.LAST_MODIFIED);
+        do {
+          String normalizedNumber = cursor.getString(normalizedNumberColumn);
+          PhoneLookupInfo phoneLookupInfo;
+          try {
+            phoneLookupInfo = PhoneLookupInfo.parseFrom(cursor.getBlob(phoneLookupInfoColumn));
+          } catch (InvalidProtocolBufferException e) {
+            throw new IllegalStateException(e);
+          }
+          long lastModified = cursor.getLong(lastModifiedColumn);
+          normalizedNumberToInfoMap.put(
+              normalizedNumber, PhoneLookupInfoAndTimestamp.create(phoneLookupInfo, lastModified));
+        } while (cursor.moveToNext());
+      }
+    }
+
+    // We have the required information in normalizedNumberToInfoMap but it's keyed by normalized
+    // number instead of DialerPhoneNumber. Build and return a new map keyed by DialerPhoneNumber.
+    return Maps.asMap(
+        uniqueDialerPhoneNumbers,
+        (dialerPhoneNumber) -> {
+          String normalizedNumber = dialerPhoneNumberToNormalizedNumbers.get(dialerPhoneNumber);
+          PhoneLookupInfoAndTimestamp infoAndTimestamp =
+              normalizedNumberToInfoMap.get(normalizedNumber);
+          // If data is cleared or for other reasons, the PhoneLookupHistory may not contain an
+          // entry for a number. Just use an empty value for that case.
+          return infoAndTimestamp == null
+              ? PhoneLookupInfoAndTimestamp.create(PhoneLookupInfo.getDefaultInstance(), 0L)
+              : infoAndTimestamp;
+        });
+  }
+
+  private static void populateInserts(
+      ImmutableMap<Long, PhoneLookupInfo> existingInfo, CallLogMutations mutations) {
+    for (Entry<Long, ContentValues> entry : mutations.getInserts().entrySet()) {
+      long id = entry.getKey();
+      ContentValues contentValues = entry.getValue();
+      PhoneLookupInfo phoneLookupInfo = existingInfo.get(id);
+      // Existing info might be missing if data was cleared or for other reasons.
+      if (phoneLookupInfo != null) {
+        contentValues.put(AnnotatedCallLog.NAME, selectName(phoneLookupInfo));
+      }
+    }
+  }
+
+  private static void updateMutations(
+      ImmutableMap<Long, PhoneLookupInfo> updatesToApply, CallLogMutations mutations) {
+    for (Entry<Long, PhoneLookupInfo> entry : updatesToApply.entrySet()) {
+      long id = entry.getKey();
+      PhoneLookupInfo phoneLookupInfo = entry.getValue();
+      ContentValues contentValuesToInsert = mutations.getInserts().get(id);
+      if (contentValuesToInsert != null) {
+        /*
+         * This is a confusing case. Consider:
+         *
+         * 1) An incoming call from "Bob" arrives; "Bob" is written to PhoneLookupHistory.
+         * 2) User changes Bob's name to "Robert".
+         * 3) User opens call log, and this code is invoked with the inserted call as a mutation.
+         *
+         * In populateInserts, we retrieved "Bob" from PhoneLookupHistory and wrote it to the insert
+         * mutation, which is wrong. We need to actually ask the phone lookups for the most up to
+         * date information ("Robert"), and update the "insert" mutation again.
+         *
+         * Having understood this, you may wonder why populateInserts() is needed at all--excellent
+         * question! Consider:
+         *
+         * 1) An incoming call from number 123 ("Bob") arrives at time T1; "Bob" is written to
+         * PhoneLookupHistory.
+         * 2) User opens call log at time T2 and "Bob" is written to it, and everything is fine; the
+         * call log can be considered accurate as of T2.
+         * 3) An incoming call from number 456 ("John") arrives at time T3. Let's say the contact
+         * info for John was last modified at time T0.
+         * 4) Now imagine that populateInserts() didn't exist; the phone lookup will ask for any
+         * information for phone number 456 which has changed since T2--but "John" hasn't changed
+         * since then so no contact information would be found.
+         *
+         * The populateInserts() method avoids this problem by always first populating inserted
+         * mutations from PhoneLookupHistory; in this case "John" would be copied during
+         * populateInserts() and there wouldn't be further updates needed here.
+         */
+        contentValuesToInsert.put(AnnotatedCallLog.NAME, selectName(phoneLookupInfo));
+        continue;
+      }
+      ContentValues contentValuesToUpdate = mutations.getUpdates().get(id);
+      if (contentValuesToUpdate != null) {
+        contentValuesToUpdate.put(AnnotatedCallLog.NAME, selectName(phoneLookupInfo));
+        continue;
+      }
+      // Else this row is not already scheduled for insert or update and we need to schedule it.
+      ContentValues contentValues = new ContentValues();
+      contentValues.put(AnnotatedCallLog.NAME, selectName(phoneLookupInfo));
+      mutations.getUpdates().put(id, contentValues);
+    }
+  }
+
+  // TODO(zachh): Extract this logic into a proper selection class or package.
+  private static String selectName(PhoneLookupInfo phoneLookupInfo) {
+    if (phoneLookupInfo.getCp2Info().getCp2ContactInfoCount() > 0) {
+      return phoneLookupInfo.getCp2Info().getCp2ContactInfo(0).getName();
+    }
+    return "";
+  }
+
+  @AutoValue
+  abstract static class PhoneLookupInfoAndTimestamp {
+    abstract PhoneLookupInfo phoneLookupInfo();
+
+    abstract long lastModified();
+
+    static PhoneLookupInfoAndTimestamp create(PhoneLookupInfo phoneLookupInfo, long lastModified) {
+      return new AutoValue_PhoneLookupDataSource_PhoneLookupInfoAndTimestamp(
+          phoneLookupInfo, lastModified);
+    }
+  }
 }
diff --git a/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java b/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java
index 29aa909..4ebd401 100644
--- a/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java
+++ b/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java
@@ -28,7 +28,6 @@
 import android.text.TextUtils;
 import com.android.dialer.DialerPhoneNumber;
 import com.android.dialer.common.Assert;
-import com.android.dialer.common.concurrent.DialerExecutors;
 import com.android.dialer.inject.ApplicationContext;
 import com.android.dialer.phonelookup.PhoneLookup;
 import com.android.dialer.phonelookup.PhoneLookupInfo;
@@ -80,7 +79,7 @@
   public ListenableFuture<Boolean> isDirty(
       ImmutableSet<DialerPhoneNumber> phoneNumbers, long lastModified) {
     // TODO(calderwoodra): consider a different thread pool
-    return MoreExecutors.listeningDecorator(DialerExecutors.getLowPriorityThreadPool(appContext))
+    return MoreExecutors.newDirectExecutorService()
         .submit(() -> isDirtyInternal(phoneNumbers, lastModified));
   }
 
@@ -171,7 +170,7 @@
   @Override
   public ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> bulkUpdate(
       ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, long lastModified) {
-    return MoreExecutors.listeningDecorator(DialerExecutors.getLowPriorityThreadPool(appContext))
+    return MoreExecutors.newDirectExecutorService()
         .submit(() -> bulkUpdateInternal(existingInfoMap, lastModified));
   }
 
diff --git a/java/com/android/dialer/phonenumberproto/DialerPhoneNumberUtil.java b/java/com/android/dialer/phonenumberproto/DialerPhoneNumberUtil.java
index a00ee75..ac011d4 100644
--- a/java/com/android/dialer/phonenumberproto/DialerPhoneNumberUtil.java
+++ b/java/com/android/dialer/phonenumberproto/DialerPhoneNumberUtil.java
@@ -30,6 +30,8 @@
 import com.google.i18n.phonenumbers.NumberParseException;
 import com.google.i18n.phonenumbers.PhoneNumberUtil;
 import com.google.i18n.phonenumbers.PhoneNumberUtil.MatchType;
+import com.google.i18n.phonenumbers.PhoneNumberUtil.PhoneNumberFormat;
+import com.google.i18n.phonenumbers.Phonenumber.PhoneNumber;
 
 /**
  * Wrapper for selected methods in {@link PhoneNumberUtil} which uses the {@link DialerPhoneNumber}
@@ -123,4 +125,19 @@
         Converter.protoToPojo(Assert.isNotNull(firstNumberIn)),
         Converter.protoToPojo(Assert.isNotNull(secondNumberIn)));
   }
+
+  /**
+   * Formats the provided number to e164 format. May return raw number if number is unparseable.
+   *
+   * @see PhoneNumberUtil#format(PhoneNumber, PhoneNumberFormat)
+   */
+  @WorkerThread
+  public String formatToE164(@NonNull DialerPhoneNumber number) {
+    Assert.isWorkerThread();
+    if (number.hasDialerInternalPhoneNumber()) {
+      return phoneNumberUtil.format(
+          Converter.protoToPojo(number.getDialerInternalPhoneNumber()), PhoneNumberFormat.E164);
+    }
+    return number.getRawInput().getNumber();
+  }
 }