diff --git a/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java b/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java
index f9fc1a6..2878e27 100644
--- a/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java
+++ b/java/com/android/dialer/phonelookup/cp2/Cp2PhoneLookup.java
@@ -22,23 +22,47 @@
 import android.provider.ContactsContract.Contacts;
 import android.provider.ContactsContract.DeletedContacts;
 import android.support.annotation.NonNull;
+import android.support.v4.util.ArrayMap;
 import android.support.v4.util.ArraySet;
 import android.telecom.Call;
+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;
+import com.android.dialer.phonelookup.PhoneLookupInfo.Cp2Info;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.util.concurrent.ListenableFuture;
 import com.google.common.util.concurrent.MoreExecutors;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Objects;
 import java.util.Set;
 import javax.inject.Inject;
 
 /** PhoneLookup implementation for local contacts. */
 public final class Cp2PhoneLookup implements PhoneLookup {
 
+  private static final String[] CP2_INFO_PROJECTION =
+      new String[] {
+        Phone.DISPLAY_NAME_PRIMARY, // 0
+        Phone.PHOTO_THUMBNAIL_URI, // 1
+        Phone.PHOTO_ID, // 2
+        Phone.LABEL, // 3
+        Phone.NORMALIZED_NUMBER, // 4
+        Phone.CONTACT_ID, // 5
+      };
+
+  private static final int CP2_INFO_NAME_INDEX = 0;
+  private static final int CP2_INFO_PHOTO_URI_INDEX = 1;
+  private static final int CP2_INFO_PHOTO_ID_INDEX = 2;
+  private static final int CP2_INFO_LABEL_INDEX = 3;
+  private static final int CP2_INFO_NUMBER_INDEX = 4;
+  private static final int CP2_INFO_CONTACT_ID_INDEX = 5;
+
   private final Context appContext;
 
   @Inject
@@ -60,12 +84,12 @@
   }
 
   private boolean isDirtyInternal(ImmutableSet<DialerPhoneNumber> phoneNumbers, long lastModified) {
-    return contactsUpdated(getContactIdsFromPhoneNumbers(phoneNumbers), lastModified)
+    return contactsUpdated(queryPhoneTableForContactIds(phoneNumbers), lastModified)
         || contactsDeleted(lastModified);
   }
 
   /** Returns set of contact ids that correspond to {@code phoneNumbers} if the contact exists. */
-  private Set<Long> getContactIdsFromPhoneNumbers(ImmutableSet<DialerPhoneNumber> phoneNumbers) {
+  private Set<Long> queryPhoneTableForContactIds(ImmutableSet<DialerPhoneNumber> phoneNumbers) {
     Set<Long> contactIds = new ArraySet<>();
     try (Cursor cursor =
         appContext
@@ -73,7 +97,7 @@
             .query(
                 Phone.CONTENT_URI,
                 new String[] {Phone.CONTACT_ID},
-                columnInSetWhereStatement(Phone.NORMALIZED_NUMBER, phoneNumbers.size()),
+                Phone.NORMALIZED_NUMBER + " IN (" + questionMarks(phoneNumbers.size()) + ")",
                 contactIdsSelectionArgs(phoneNumbers),
                 null)) {
       cursor.moveToPosition(-1);
@@ -100,37 +124,32 @@
 
   /** Returns true if any contacts were modified after {@code lastModified}. */
   private boolean contactsUpdated(Set<Long> contactIds, long lastModified) {
-    try (Cursor cursor =
-        appContext
-            .getContentResolver()
-            .query(
-                Contacts.CONTENT_URI,
-                new String[] {Contacts._ID},
-                contactsIsDirtyWhereStatement(contactIds.size()),
-                contactsIsDirtySelectionArgs(lastModified, contactIds),
-                null)) {
+    try (Cursor cursor = queryContactsTableForContacts(contactIds, lastModified)) {
       return cursor.getCount() > 0;
     }
   }
 
-  private static String contactsIsDirtyWhereStatement(int numberOfContactIds) {
-    StringBuilder where = new StringBuilder();
-    // Filter to after last modified time
-    where.append(Contacts.CONTACT_LAST_UPDATED_TIMESTAMP).append(" > ?");
+  private Cursor queryContactsTableForContacts(Set<Long> contactIds, long lastModified) {
+    // Filter to after last modified time based only on contacts we care about
+    String where =
+        Contacts.CONTACT_LAST_UPDATED_TIMESTAMP
+            + " > ?"
+            + " AND "
+            + Contacts._ID
+            + " IN ("
+            + questionMarks(contactIds.size())
+            + ")";
 
-    // Filter based only on contacts we care about
-    where.append(" AND ").append(columnInSetWhereStatement(Contacts._ID, numberOfContactIds));
-    return where.toString();
-  }
-
-  private String[] contactsIsDirtySelectionArgs(long lastModified, Set<Long> contactIds) {
     String[] args = new String[contactIds.size() + 1];
     args[0] = Long.toString(lastModified);
     int i = 1;
     for (Long contactId : contactIds) {
       args[i++] = Long.toString(contactId);
     }
-    return args;
+
+    return appContext
+        .getContentResolver()
+        .query(Contacts.CONTENT_URI, new String[] {Contacts._ID}, where, args, null);
   }
 
   /** Returns true if any contacts were deleted after {@code lastModified}. */
@@ -148,22 +167,272 @@
     }
   }
 
-  private static String columnInSetWhereStatement(String columnName, int setSize) {
+  @Override
+  public ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> bulkUpdate(
+      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, long lastModified) {
+    return MoreExecutors.listeningDecorator(DialerExecutors.getLowPriorityThreadPool(appContext))
+        .submit(() -> bulkUpdateInternal(existingInfoMap, lastModified));
+  }
+
+  private ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> bulkUpdateInternal(
+      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, long lastModified) {
+    // Build a set of each DialerPhoneNumber that was associated with a contact, and is no longer
+    // associated with that same contact.
+    Set<DialerPhoneNumber> deletedPhoneNumbers =
+        getDeletedPhoneNumbers(existingInfoMap, lastModified);
+
+    // For each DialerPhoneNumber that was associated with a contact or added to a contact,
+    // build a map of those DialerPhoneNumbers to a set Cp2Infos, where each Cp2Info represents a
+    // contact.
+    ImmutableMap<DialerPhoneNumber, Set<Cp2Info>> updatedContacts =
+        buildMapForUpdatedOrAddedContacts(existingInfoMap, lastModified, deletedPhoneNumbers);
+
+    // Start build a new map of updated info. This will replace existing info.
+    ImmutableMap.Builder<DialerPhoneNumber, PhoneLookupInfo> newInfoMapBuilder =
+        ImmutableMap.builder();
+
+    // For each DialerPhoneNumber in existing info...
+    for (Entry<DialerPhoneNumber, PhoneLookupInfo> entry : existingInfoMap.entrySet()) {
+      // Build off the existing info
+      PhoneLookupInfo.Builder infoBuilder = PhoneLookupInfo.newBuilder(entry.getValue());
+
+      // If the contact was updated, replace the Cp2Info list
+      if (updatedContacts.containsKey(entry.getKey())) {
+        infoBuilder.clearCp2Info();
+        infoBuilder.addAllCp2Info(updatedContacts.get(entry.getKey()));
+
+        // If it was deleted and not added to a new contact, replace the Cp2Info list with
+        // the default instance of Cp2Info
+      } else if (deletedPhoneNumbers.contains(entry.getKey())) {
+        infoBuilder.clearCp2Info();
+        infoBuilder.addCp2Info(Cp2Info.getDefaultInstance());
+      }
+
+      // If the DialerPhoneNumber didn't change, add the unchanged existing info.
+      newInfoMapBuilder.put(entry.getKey(), infoBuilder.build());
+    }
+    return newInfoMapBuilder.build();
+  }
+
+  /**
+   * 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
+   * the smallest set of dialer phone numbers to query cp2 against. 4. build and return the map of
+   * dialerphonenumbers to their new cp2info
+   *
+   * @return Map of {@link DialerPhoneNumber} to {@link PhoneLookupInfo} with updated {@link
+   *     Cp2Info}.
+   */
+  private ImmutableMap<DialerPhoneNumber, Set<Cp2Info>> buildMapForUpdatedOrAddedContacts(
+      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap,
+      long lastModified,
+      Set<DialerPhoneNumber> deletedPhoneNumbers) {
+
+    // Start building a set of DialerPhoneNumbers that we want to update.
+    Set<DialerPhoneNumber> updatedNumbers = new ArraySet<>();
+
+    Set<Long> contactIds = new ArraySet<>();
+    for (Entry<DialerPhoneNumber, PhoneLookupInfo> entry : existingInfoMap.entrySet()) {
+      // If the number was deleted, we need to check if it was added to a new contact.
+      if (deletedPhoneNumbers.contains(entry.getKey())) {
+        updatedNumbers.add(entry.getKey());
+        continue;
+      }
+
+      // For each Cp2Info for each existing DialerPhoneNumber...
+      // Store the contact id if it exist, else automatically add the DialerPhoneNumber to our
+      // set of DialerPhoneNumbers we want to update.
+      for (Cp2Info cp2Info : entry.getValue().getCp2InfoList()) {
+        if (Objects.equals(cp2Info, Cp2Info.getDefaultInstance())) {
+          // If the number doesn't have any Cp2Info set to it, for various reasons, we need to look
+          // up the number to check if any exists.
+          // The various reasons this might happen are:
+          //  - An existing contact that wasn't in the call log is now in the call log.
+          //  - A number was in the call log before but has now been added to a contact.
+          //  - A number is in the call log, but isn't associated with any contact.
+          updatedNumbers.add(entry.getKey());
+        } else {
+          contactIds.add(cp2Info.getContactId());
+        }
+      }
+    }
+
+    // Query the contacts table and get those that whose Contacts.CONTACT_LAST_UPDATED_TIMESTAMP is
+    // 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);
+      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 Cp2Info need to be updated.
+        long contactId = cursor.getLong(contactIdIndex);
+        updatedNumbers.addAll(getDialerPhoneNumber(existingInfoMap, contactId));
+      }
+    }
+
+    // Query the Phone table and build Cp2Info for each DialerPhoneNumber in our updatedNumbers set.
+    Map<DialerPhoneNumber, Set<Cp2Info>> map = new ArrayMap<>();
+    try (Cursor cursor = getAllCp2Rows(updatedNumbers)) {
+      cursor.moveToPosition(-1);
+      while (cursor.moveToNext()) {
+        // Map each dialer phone number to it's new cp2 info
+        Set<DialerPhoneNumber> phoneNumbers =
+            getDialerPhoneNumbers(updatedNumbers, cursor.getString(CP2_INFO_NUMBER_INDEX));
+        Cp2Info info = buildCp2InfoFromUpdatedContactsCursor(cursor);
+        for (DialerPhoneNumber phoneNumber : phoneNumbers) {
+          if (map.containsKey(phoneNumber)) {
+            map.get(phoneNumber).add(info);
+          } else {
+            Set<Cp2Info> cp2Infos = new ArraySet<>();
+            cp2Infos.add(info);
+            map.put(phoneNumber, cp2Infos);
+          }
+        }
+      }
+    }
+    return ImmutableMap.copyOf(map);
+  }
+
+  /**
+   * Returns cursor with projection {@link #CP2_INFO_PROJECTION} and only phone numbers that are in
+   * {@code updateNumbers}.
+   */
+  private Cursor getAllCp2Rows(Set<DialerPhoneNumber> updatedNumbers) {
+    String where = Phone.NORMALIZED_NUMBER + " IN (" + questionMarks(updatedNumbers.size()) + ")";
+    String[] selectionArgs = new String[updatedNumbers.size()];
+    int i = 0;
+    for (DialerPhoneNumber phoneNumber : updatedNumbers) {
+      selectionArgs[i++] = getNormalizedNumber(phoneNumber);
+    }
+
+    return appContext
+        .getContentResolver()
+        .query(Phone.CONTENT_URI, CP2_INFO_PROJECTION, where, selectionArgs, null);
+  }
+
+  /**
+   * @param cursor with projection {@link #CP2_INFO_PROJECTION}.
+   * @return new {@link Cp2Info} based on current row of {@code cursor}.
+   */
+  private static Cp2Info buildCp2InfoFromUpdatedContactsCursor(Cursor cursor) {
+    String displayName = cursor.getString(CP2_INFO_NAME_INDEX);
+    String photoUri = cursor.getString(CP2_INFO_PHOTO_URI_INDEX);
+    String label = cursor.getString(CP2_INFO_LABEL_INDEX);
+
+    Cp2Info.Builder infoBuilder = Cp2Info.newBuilder();
+    if (!TextUtils.isEmpty(displayName)) {
+      infoBuilder.setName(displayName);
+    }
+    if (!TextUtils.isEmpty(photoUri)) {
+      infoBuilder.setPhotoUri(photoUri);
+    }
+    if (!TextUtils.isEmpty(label)) {
+      infoBuilder.setLabel(label);
+    }
+    infoBuilder.setPhotoId(cursor.getLong(CP2_INFO_PHOTO_ID_INDEX));
+    infoBuilder.setContactId(cursor.getLong(CP2_INFO_CONTACT_ID_INDEX));
+    return infoBuilder.build();
+  }
+
+  /** Returns set of DialerPhoneNumbers that were associated with now deleted contacts. */
+  private Set<DialerPhoneNumber> getDeletedPhoneNumbers(
+      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, long lastModified) {
+    // Build set of all contact IDs from our existing data. We're going to use this set to query
+    // against the DeletedContacts table and see if any of them were deleted.
+    Set<Long> contactIds = findContactIdsIn(existingInfoMap);
+
+    // Start building a set of DialerPhoneNumbers that were associated with now deleted contacts.
+    try (Cursor cursor = queryDeletedContacts(contactIds, lastModified)) {
+      // We now have a cursor/list of contact IDs that were associated with deleted contacts.
+      return findDeletedPhoneNumbersIn(existingInfoMap, cursor);
+    }
+  }
+
+  private Set<Long> findContactIdsIn(ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> map) {
+    Set<Long> contactIds = new ArraySet<>();
+    for (PhoneLookupInfo info : map.values()) {
+      for (Cp2Info cp2Info : info.getCp2InfoList()) {
+        contactIds.add(cp2Info.getContactId());
+      }
+    }
+    return contactIds;
+  }
+
+  private Cursor queryDeletedContacts(Set<Long> contactIds, long lastModified) {
+    String where =
+        DeletedContacts.CONTACT_DELETED_TIMESTAMP
+            + " > ?"
+            + " AND "
+            + DeletedContacts.CONTACT_ID
+            + " IN ("
+            + questionMarks(contactIds.size())
+            + ")";
+    String[] args = new String[contactIds.size() + 1];
+    args[0] = Long.toString(lastModified);
+    int i = 1;
+    for (Long contactId : contactIds) {
+      args[i++] = Long.toString(contactId);
+    }
+
+    return appContext
+        .getContentResolver()
+        .query(
+            DeletedContacts.CONTENT_URI,
+            new String[] {DeletedContacts.CONTACT_ID},
+            where,
+            args,
+            null);
+  }
+
+  /** Returns set of DialerPhoneNumbers that are associated with deleted contact IDs. */
+  private Set<DialerPhoneNumber> findDeletedPhoneNumbersIn(
+      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, Cursor cursor) {
+    int contactIdIndex = cursor.getColumnIndexOrThrow(DeletedContacts.CONTACT_ID);
+    Set<DialerPhoneNumber> deletedPhoneNumbers = new ArraySet<>();
+    cursor.moveToPosition(-1);
+    while (cursor.moveToNext()) {
+      long contactId = cursor.getLong(contactIdIndex);
+      deletedPhoneNumbers.addAll(getDialerPhoneNumber(existingInfoMap, contactId));
+    }
+    return deletedPhoneNumbers;
+  }
+
+  private static Set<DialerPhoneNumber> getDialerPhoneNumbers(
+      Set<DialerPhoneNumber> phoneNumbers, String number) {
+    Set<DialerPhoneNumber> matches = new ArraySet<>();
+    for (DialerPhoneNumber phoneNumber : phoneNumbers) {
+      if (getNormalizedNumber(phoneNumber).equals(number)) {
+        matches.add(phoneNumber);
+      }
+    }
+    Assert.checkArgument(
+        matches.size() > 0, "Couldn't find DialerPhoneNumber for number: " + number);
+    return matches;
+  }
+
+  private static Set<DialerPhoneNumber> getDialerPhoneNumber(
+      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, long contactId) {
+    Set<DialerPhoneNumber> matches = new ArraySet<>();
+    for (Entry<DialerPhoneNumber, PhoneLookupInfo> entry : existingInfoMap.entrySet()) {
+      for (Cp2Info cp2Info : entry.getValue().getCp2InfoList()) {
+        if (cp2Info.getContactId() == contactId) {
+          matches.add(entry.getKey());
+        }
+      }
+    }
+    Assert.checkArgument(
+        matches.size() > 0, "Couldn't find DialerPhoneNumber for contact ID: " + contactId);
+    return matches;
+  }
+
+  private static String questionMarks(int count) {
     StringBuilder where = new StringBuilder();
-    where.append(columnName).append(" IN (");
-    for (int i = 0; i < setSize; i++) {
+    for (int i = 0; i < count; i++) {
       if (i != 0) {
         where.append(", ");
       }
       where.append("?");
     }
-    return where.append(")").toString();
-  }
-
-  @Override
-  public ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> bulkUpdate(
-      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, long lastModified) {
-    // TODO(calderwoodra)
-    return null;
+    return where.toString();
   }
 }
diff --git a/java/com/android/dialer/phonelookup/phone_lookup_info.proto b/java/com/android/dialer/phonelookup/phone_lookup_info.proto
index 1027e5c..cb89a64 100644
--- a/java/com/android/dialer/phonelookup/phone_lookup_info.proto
+++ b/java/com/android/dialer/phonelookup/phone_lookup_info.proto
@@ -17,10 +17,23 @@
   // Information about a PhoneNumber retrieved from CP2. Cp2PhoneLookup is
   // responsible for populating the data in this message.
   message Cp2Info {
+    // android.provider.ContactsContract.CommonDataKinds.Phone.DISPLAY_NAME_PRIMARY
     optional string name = 1;
+
+    // android.provider.ContactsContract.CommonDataKinds.Phone.PHOTO_THUMBNAIL_URI
     optional string photo_uri = 2;
+
+    // android.provider.ContactsContract.CommonDataKinds.Phone.PHOTO_ID
     optional fixed64 photo_id = 3;
-    optional string label = 4;  // "Home", "Mobile", ect.
+
+    // android.provider.ContactsContract.CommonDataKinds.Phone.LABEL
+    // "Home", "Mobile", ect.
+    optional string label = 4;
+
+    // android.provider.ContactsContract.CommonDataKinds.Phone.CONTACT_ID
+    optional fixed64 contact_id = 5;
   }
-  optional Cp2Info cp2_info = 1;
+  // Repeated because one phone number can be associated with multiple CP2
+  // contacts.
+  repeated Cp2Info cp2_info = 1;
 }
\ No newline at end of file