diff --git a/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java b/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
index b3bbf3c..7a7f207 100644
--- a/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
+++ b/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
@@ -18,7 +18,6 @@
 
 import android.content.ContentValues;
 import android.content.Context;
-import android.content.SharedPreferences;
 import android.database.Cursor;
 import android.support.annotation.MainThread;
 import android.support.annotation.WorkerThread;
@@ -34,8 +33,6 @@
 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;
@@ -54,15 +51,12 @@
  * numbers.
  */
 public final class PhoneLookupDataSource implements CallLogDataSource {
-  private static final String PREF_LAST_TIMESTAMP_PROCESSED = "phoneLookupLastTimestampProcessed";
 
   private final PhoneLookup phoneLookup;
-  private final SharedPreferences sharedPreferences;
 
   @Inject
-  PhoneLookupDataSource(PhoneLookup phoneLookup, @Unencrypted SharedPreferences sharedPreferences) {
+  PhoneLookupDataSource(PhoneLookup phoneLookup) {
     this.phoneLookup = phoneLookup;
-    this.sharedPreferences = sharedPreferences;
   }
 
   @WorkerThread
@@ -71,15 +65,11 @@
     ImmutableSet<DialerPhoneNumber> uniqueDialerPhoneNumbers =
         queryDistinctDialerPhoneNumbersFromAnnotatedCallLog(appContext);
 
-    long lastTimestampProcessedSharedPrefValue =
-        sharedPreferences.getLong(PREF_LAST_TIMESTAMP_PROCESSED, 0L);
     try {
       // TODO(zachh): Would be good to rework call log architecture to properly use futures.
       // TODO(zachh): Consider how individual lookups should behave wrt timeouts/exceptions and
       // handle appropriately here.
-      return phoneLookup
-          .isDirty(uniqueDialerPhoneNumbers, lastTimestampProcessedSharedPrefValue)
-          .get();
+      return phoneLookup.isDirty(uniqueDialerPhoneNumbers).get();
     } catch (InterruptedException | ExecutionException e) {
       throw new IllegalStateException(e);
     }
@@ -101,16 +91,12 @@
    *   <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>Uses all of the numbers from AnnotatedCallLog 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>For each number, checks if the original PhoneLookupInfo differs from the new one
    *         <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.
+   *             new value back to the PhoneLookupHistory.
    *       </ul>
    * </ul>
    */
@@ -119,36 +105,23 @@
   public void fill(Context appContext, CallLogMutations mutations) {
     Map<DialerPhoneNumber, Set<Long>> annotatedCallLogIdsByNumber =
         queryIdAndNumberFromAnnotatedCallLog(appContext);
-    Map<DialerPhoneNumber, PhoneLookupInfoAndTimestamp> originalPhoneLookupHistoryDataByNumber =
+    ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> originalPhoneLookupInfosByNumber =
         queryPhoneLookupHistoryForNumbers(appContext, annotatedCallLogIdsByNumber.keySet());
     ImmutableMap.Builder<Long, PhoneLookupInfo> originalPhoneLookupHistoryDataByAnnotatedCallLogId =
         ImmutableMap.builder();
-    for (Entry<DialerPhoneNumber, PhoneLookupInfoAndTimestamp> entry :
-        originalPhoneLookupHistoryDataByNumber.entrySet()) {
+    for (Entry<DialerPhoneNumber, PhoneLookupInfo> entry :
+        originalPhoneLookupInfosByNumber.entrySet()) {
       DialerPhoneNumber dialerPhoneNumber = entry.getKey();
-      PhoneLookupInfoAndTimestamp phoneLookupInfoAndTimestamp = entry.getValue();
+      PhoneLookupInfo phoneLookupInfo = entry.getValue();
       for (Long id : annotatedCallLogIdsByNumber.get(dialerPhoneNumber)) {
-        originalPhoneLookupHistoryDataByAnnotatedCallLogId.put(
-            id, phoneLookupInfoAndTimestamp.phoneLookupInfo());
+        originalPhoneLookupHistoryDataByAnnotatedCallLogId.put(id, 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();
+      updatedInfoMap = phoneLookup.bulkUpdate(originalPhoneLookupInfosByNumber).get();
     } catch (InterruptedException | ExecutionException e) {
       throw new IllegalStateException(e);
     }
@@ -156,10 +129,7 @@
     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)) {
+      if (!originalPhoneLookupInfosByNumber.get(dialerPhoneNumber).equals(upToDateInfo)) {
         for (Long id : annotatedCallLogIdsByNumber.get(dialerPhoneNumber)) {
           rowsToUpdate.put(id, upToDateInfo);
         }
@@ -171,7 +141,7 @@
   @WorkerThread
   @Override
   public void onSuccessfulFill(Context appContext) {
-    // TODO(zachh): Implementation.
+    // TODO(zachh): Update PhoneLookupHistory.
   }
 
   @WorkerThread
@@ -275,7 +245,7 @@
     return idsByNumber;
   }
 
-  private Map<DialerPhoneNumber, PhoneLookupInfoAndTimestamp> queryPhoneLookupHistoryForNumbers(
+  private ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> queryPhoneLookupHistoryForNumbers(
       Context appContext, Set<DialerPhoneNumber> uniqueDialerPhoneNumbers) {
     DialerPhoneNumberUtil dialerPhoneNumberUtil =
         new DialerPhoneNumberUtil(PhoneNumberUtil.getInstance());
@@ -291,16 +261,14 @@
     String selection =
         PhoneLookupHistory.NORMALIZED_NUMBER + " in (" + TextUtils.join(",", questionMarks) + ")";
 
-    Map<String, PhoneLookupInfoAndTimestamp> normalizedNumberToInfoMap = new ArrayMap<>();
+    Map<String, PhoneLookupInfo> normalizedNumberToInfoMap = new ArrayMap<>();
     try (Cursor cursor =
         appContext
             .getContentResolver()
             .query(
                 PhoneLookupHistory.CONTENT_URI,
                 new String[] {
-                  PhoneLookupHistory.NORMALIZED_NUMBER,
-                  PhoneLookupHistory.PHONE_LOOKUP_INFO,
-                  PhoneLookupHistory.LAST_MODIFIED
+                  PhoneLookupHistory.NORMALIZED_NUMBER, PhoneLookupHistory.PHONE_LOOKUP_INFO,
                 },
                 selection,
                 normalizedNumbers,
@@ -316,7 +284,6 @@
             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;
@@ -325,27 +292,25 @@
           } catch (InvalidProtocolBufferException e) {
             throw new IllegalStateException(e);
           }
-          long lastModified = cursor.getLong(lastModifiedColumn);
-          normalizedNumberToInfoMap.put(
-              normalizedNumber, PhoneLookupInfoAndTimestamp.create(phoneLookupInfo, lastModified));
+          normalizedNumberToInfoMap.put(normalizedNumber, phoneLookupInfo);
         } 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;
-        });
+    return ImmutableMap.copyOf(
+        Maps.asMap(
+            uniqueDialerPhoneNumbers,
+            (dialerPhoneNumber) -> {
+              String normalizedNumber = dialerPhoneNumberToNormalizedNumbers.get(dialerPhoneNumber);
+              PhoneLookupInfo phoneLookupInfo = 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 phoneLookupInfo == null
+                  ? PhoneLookupInfo.getDefaultInstance()
+                  : phoneLookupInfo;
+            }));
   }
 
   private static void populateInserts(
@@ -418,16 +383,4 @@
     }
     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/PhoneLookup.java b/java/com/android/dialer/phonelookup/PhoneLookup.java
index 66f166d..1832775 100644
--- a/java/com/android/dialer/phonelookup/PhoneLookup.java
+++ b/java/com/android/dialer/phonelookup/PhoneLookup.java
@@ -27,8 +27,8 @@
  * Provides operations related to retrieving information about phone numbers.
  *
  * <p>Some operations defined by this interface are generally targeted towards specific use cases;
- * for example {@link #isDirty(ImmutableSet, long)} and {@link #bulkUpdate(ImmutableMap, long)} are
- * generally intended to be used by the call log.
+ * for example {@link #isDirty(ImmutableSet)}, {@link #bulkUpdate(ImmutableMap)}, and {@link
+ * #onSuccessfulBulkUpdate()} are generally intended to be used by the call log.
  */
 public interface PhoneLookup {
 
@@ -43,14 +43,14 @@
 
   /**
    * Returns a future which returns true if the information for any of the provided phone numbers
-   * has changed since {@code lastModified} according to this {@link PhoneLookup}.
+   * has changed, usually since {@link #onSuccessfulBulkUpdate()} was last invoked.
    */
-  ListenableFuture<Boolean> isDirty(
-      ImmutableSet<DialerPhoneNumber> phoneNumbers, long lastModified);
+  ListenableFuture<Boolean> isDirty(ImmutableSet<DialerPhoneNumber> phoneNumbers);
 
   /**
-   * Given a set of existing information and a timestamp, returns a set of information with any
-   * changes made since the timestamp according to this {@link PhoneLookup}.
+   * Performs a bulk update of this {@link PhoneLookup}. The returned map must contain the exact
+   * same keys as the provided map. Most implementations will rely on last modified timestamps to
+   * efficiently only update the data which needs to be updated.
    *
    * <p>If there are no changes required, it is valid for this method to simply return the provided
    * {@code existingInfoMap}.
@@ -59,5 +59,15 @@
    * deleted) the returned map should contain an empty {@link PhoneLookupInfo} for that number.
    */
   ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> bulkUpdate(
-      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, long lastModified);
+      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap);
+
+  /**
+   * Called when the results of the {@link #bulkUpdate(ImmutableMap)} have been applied by the
+   * caller.
+   *
+   * <p>Typically implementations will use this to store a "last processed" timestamp so that future
+   * invocations of {@link #isDirty(ImmutableSet)} and {@link #bulkUpdate(ImmutableMap)} can be
+   * efficiently implemented.
+   */
+  ListenableFuture<Void> onSuccessfulBulkUpdate();
 }
diff --git a/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java b/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java
index 59a8457..520c46f 100644
--- a/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java
+++ b/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java
@@ -70,11 +70,10 @@
   }
 
   @Override
-  public ListenableFuture<Boolean> isDirty(
-      ImmutableSet<DialerPhoneNumber> phoneNumbers, long lastModified) {
+  public ListenableFuture<Boolean> isDirty(ImmutableSet<DialerPhoneNumber> phoneNumbers) {
     List<ListenableFuture<Boolean>> futures = new ArrayList<>();
     for (PhoneLookup phoneLookup : phoneLookups) {
-      futures.add(phoneLookup.isDirty(phoneNumbers, lastModified));
+      futures.add(phoneLookup.isDirty(phoneNumbers));
     }
     // Executes all child lookups (possibly in parallel), completing when the first composite lookup
     // which returns "true" completes, and cancels the others.
@@ -90,11 +89,11 @@
    */
   @Override
   public ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> bulkUpdate(
-      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, long lastModified) {
+      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap) {
     List<ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>>> futures =
         new ArrayList<>();
     for (PhoneLookup phoneLookup : phoneLookups) {
-      futures.add(phoneLookup.bulkUpdate(existingInfoMap, lastModified));
+      futures.add(phoneLookup.bulkUpdate(existingInfoMap));
     }
     return Futures.transform(
         Futures.allAsList(futures),
@@ -118,4 +117,14 @@
         },
         MoreExecutors.directExecutor());
   }
+
+  @Override
+  public ListenableFuture<Void> onSuccessfulBulkUpdate() {
+    List<ListenableFuture<Void>> futures = new ArrayList<>();
+    for (PhoneLookup phoneLookup : phoneLookups) {
+      futures.add(phoneLookup.onSuccessfulBulkUpdate());
+    }
+    return Futures.transform(
+        Futures.allAsList(futures), unused -> null, MoreExecutors.directExecutor());
+  }
 }
diff --git a/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java b/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java
index 4ebd401..307f998 100644
--- a/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java
+++ b/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java
@@ -17,11 +17,13 @@
 package com.android.dialer.phonelookup.cp2;
 
 import android.content.Context;
+import android.content.SharedPreferences;
 import android.database.Cursor;
 import android.provider.ContactsContract.CommonDataKinds.Phone;
 import android.provider.ContactsContract.Contacts;
 import android.provider.ContactsContract.DeletedContacts;
 import android.support.annotation.NonNull;
+import android.support.annotation.Nullable;
 import android.support.v4.util.ArrayMap;
 import android.support.v4.util.ArraySet;
 import android.telecom.Call;
@@ -33,6 +35,7 @@
 import com.android.dialer.phonelookup.PhoneLookupInfo;
 import com.android.dialer.phonelookup.PhoneLookupInfo.Cp2Info;
 import com.android.dialer.phonelookup.PhoneLookupInfo.Cp2Info.Cp2ContactInfo;
+import com.android.dialer.storage.Unencrypted;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.util.concurrent.ListenableFuture;
@@ -46,6 +49,9 @@
 /** PhoneLookup implementation for local contacts. */
 public final class Cp2PhoneLookup implements PhoneLookup {
 
+  private static final String PREF_LAST_TIMESTAMP_PROCESSED =
+      "cp2PhoneLookupLastTimestampProcessed";
+
   private static final String[] CP2_INFO_PROJECTION =
       new String[] {
         Phone.DISPLAY_NAME_PRIMARY, // 0
@@ -64,10 +70,14 @@
   private static final int CP2_INFO_CONTACT_ID_INDEX = 5;
 
   private final Context appContext;
+  private final SharedPreferences sharedPreferences;
+  @Nullable private Long currentLastTimestampProcessed;
 
   @Inject
-  Cp2PhoneLookup(@ApplicationContext Context appContext) {
+  Cp2PhoneLookup(
+      @ApplicationContext Context appContext, @Unencrypted SharedPreferences sharedPreferences) {
     this.appContext = appContext;
+    this.sharedPreferences = sharedPreferences;
   }
 
   @Override
@@ -76,14 +86,13 @@
   }
 
   @Override
-  public ListenableFuture<Boolean> isDirty(
-      ImmutableSet<DialerPhoneNumber> phoneNumbers, long lastModified) {
+  public ListenableFuture<Boolean> isDirty(ImmutableSet<DialerPhoneNumber> phoneNumbers) {
     // TODO(calderwoodra): consider a different thread pool
-    return MoreExecutors.newDirectExecutorService()
-        .submit(() -> isDirtyInternal(phoneNumbers, lastModified));
+    return MoreExecutors.newDirectExecutorService().submit(() -> isDirtyInternal(phoneNumbers));
   }
 
-  private boolean isDirtyInternal(ImmutableSet<DialerPhoneNumber> phoneNumbers, long lastModified) {
+  private boolean isDirtyInternal(ImmutableSet<DialerPhoneNumber> phoneNumbers) {
+    long lastModified = sharedPreferences.getLong(PREF_LAST_TIMESTAMP_PROCESSED, 0L);
     return contactsUpdated(queryPhoneTableForContactIds(phoneNumbers), lastModified)
         || contactsDeleted(lastModified);
   }
@@ -149,7 +158,12 @@
 
     return appContext
         .getContentResolver()
-        .query(Contacts.CONTENT_URI, new String[] {Contacts._ID}, where, args, null);
+        .query(
+            Contacts.CONTENT_URI,
+            new String[] {Contacts._ID, Contacts.CONTACT_LAST_UPDATED_TIMESTAMP},
+            where,
+            args,
+            null);
   }
 
   /** Returns true if any contacts were deleted after {@code lastModified}. */
@@ -169,13 +183,16 @@
 
   @Override
   public ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> bulkUpdate(
-      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, long lastModified) {
+      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap) {
     return MoreExecutors.newDirectExecutorService()
-        .submit(() -> bulkUpdateInternal(existingInfoMap, lastModified));
+        .submit(() -> bulkUpdateInternal(existingInfoMap));
   }
 
   private ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> bulkUpdateInternal(
-      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, long lastModified) {
+      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap) {
+    currentLastTimestampProcessed = null;
+    long lastModified = sharedPreferences.getLong(PREF_LAST_TIMESTAMP_PROCESSED, 0L);
+
     // Build a set of each DialerPhoneNumber that was associated with a contact, and is no longer
     // associated with that same contact.
     Set<DialerPhoneNumber> deletedPhoneNumbers =
@@ -214,6 +231,21 @@
     return newInfoMapBuilder.build();
   }
 
+  @Override
+  public ListenableFuture<Void> onSuccessfulBulkUpdate() {
+    return MoreExecutors.newDirectExecutorService()
+        .submit(
+            () -> {
+              if (currentLastTimestampProcessed != null) {
+                sharedPreferences
+                    .edit()
+                    .putLong(PREF_LAST_TIMESTAMP_PROCESSED, currentLastTimestampProcessed)
+                    .apply();
+              }
+              return null;
+            });
+  }
+
   /**
    * 1. get all contact ids. if the id is unset, add the number to the list of contacts to look up.
    * 2. reduce our list of contact ids to those that were updated after lastModified. 3. Now we have
@@ -261,12 +293,18 @@
     // after lastModified, such that Contacts._ID is in our set of contact IDs we build above.
     try (Cursor cursor = queryContactsTableForContacts(contactIds, lastModified)) {
       int contactIdIndex = cursor.getColumnIndex(Contacts._ID);
+      int lastUpdatedIndex = cursor.getColumnIndex(Contacts.CONTACT_LAST_UPDATED_TIMESTAMP);
       cursor.moveToPosition(-1);
       while (cursor.moveToNext()) {
         // Find the DialerPhoneNumber for each contact id and add it to our updated numbers set.
         // These, along with our number not associated with any Cp2ContactInfo need to be updated.
         long contactId = cursor.getLong(contactIdIndex);
         updatedNumbers.addAll(getDialerPhoneNumber(existingInfoMap, contactId));
+        long lastUpdatedTimestamp = cursor.getLong(lastUpdatedIndex);
+        if (currentLastTimestampProcessed == null
+            || currentLastTimestampProcessed < lastUpdatedTimestamp) {
+          currentLastTimestampProcessed = lastUpdatedTimestamp;
+        }
       }
     }
 
@@ -379,7 +417,7 @@
         .getContentResolver()
         .query(
             DeletedContacts.CONTENT_URI,
-            new String[] {DeletedContacts.CONTACT_ID},
+            new String[] {DeletedContacts.CONTACT_ID, DeletedContacts.CONTACT_DELETED_TIMESTAMP},
             where,
             args,
             null);
@@ -389,11 +427,17 @@
   private Set<DialerPhoneNumber> findDeletedPhoneNumbersIn(
       ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, Cursor cursor) {
     int contactIdIndex = cursor.getColumnIndexOrThrow(DeletedContacts.CONTACT_ID);
+    int deletedTimeIndex = cursor.getColumnIndexOrThrow(DeletedContacts.CONTACT_DELETED_TIMESTAMP);
     Set<DialerPhoneNumber> deletedPhoneNumbers = new ArraySet<>();
     cursor.moveToPosition(-1);
     while (cursor.moveToNext()) {
       long contactId = cursor.getLong(contactIdIndex);
       deletedPhoneNumbers.addAll(getDialerPhoneNumber(existingInfoMap, contactId));
+      long deletedTime = cursor.getLong(deletedTimeIndex);
+      if (currentLastTimestampProcessed == null || currentLastTimestampProcessed < deletedTime) {
+        // TODO(zachh): There's a problem here if a contact for a new row is deleted?
+        currentLastTimestampProcessed = deletedTime;
+      }
     }
     return deletedPhoneNumbers;
   }