diff --git a/java/com/android/dialer/calllog/database/AnnotatedCallLogContentProvider.java b/java/com/android/dialer/calllog/database/AnnotatedCallLogContentProvider.java
index 825e84f..2427624 100644
--- a/java/com/android/dialer/calllog/database/AnnotatedCallLogContentProvider.java
+++ b/java/com/android/dialer/calllog/database/AnnotatedCallLogContentProvider.java
@@ -245,12 +245,12 @@
         throw new IllegalArgumentException("Unknown uri: " + uri);
     }
     int rows = database.delete(AnnotatedCallLog.TABLE, selection, selectionArgs);
-    if (rows > 0) {
-      if (!isApplyingBatch()) {
-        notifyChange(uri);
-      }
-    } else {
+    if (rows == 0) {
       LogUtil.w("AnnotatedCallLogContentProvider.delete", "no rows deleted");
+      return rows;
+    }
+    if (!isApplyingBatch()) {
+      notifyChange(uri);
     }
     return rows;
   }
@@ -268,7 +268,15 @@
     int match = uriMatcher.match(uri);
     switch (match) {
       case ANNOTATED_CALL_LOG_TABLE_CODE:
-        break;
+        int rows = database.update(AnnotatedCallLog.TABLE, values, selection, selectionArgs);
+        if (rows == 0) {
+          LogUtil.w("AnnotatedCallLogContentProvider.update", "no rows updated");
+          return rows;
+        }
+        if (!isApplyingBatch()) {
+          notifyChange(uri);
+        }
+        return rows;
       case ANNOTATED_CALL_LOG_TABLE_ID_CODE:
         Assert.checkArgument(
             !values.containsKey(AnnotatedCallLog._ID), "Do not specify _ID when updating by ID");
@@ -276,23 +284,21 @@
         Assert.checkArgument(
             selectionArgs == null, "Do not specify selection args when updating by ID");
         selection = getSelectionWithId(ContentUris.parseId(uri));
-        break;
+        rows = database.update(AnnotatedCallLog.TABLE, values, selection, selectionArgs);
+        if (rows == 0) {
+          LogUtil.w("AnnotatedCallLogContentProvider.update", "no rows updated");
+          return rows;
+        }
+        if (!isApplyingBatch()) {
+          notifyChange(uri);
+        }
+        return rows;
       case ANNOTATED_CALL_LOG_TABLE_DISTINCT_NUMBER_CODE:
-        throw new UnsupportedOperationException();
       case COALESCED_ANNOTATED_CALL_LOG_TABLE_CODE:
         throw new UnsupportedOperationException();
       default:
         throw new IllegalArgumentException("Unknown uri: " + uri);
     }
-    int rows = database.update(AnnotatedCallLog.TABLE, values, selection, selectionArgs);
-    if (rows > 0) {
-      if (!isApplyingBatch()) {
-        notifyChange(uri);
-      }
-    } else {
-      LogUtil.w("AnnotatedCallLogContentProvider.update", "no rows updated");
-    }
-    return rows;
   }
 
   /**
diff --git a/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java b/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
index 17a09ce..fa7d3be 100644
--- a/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
+++ b/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
@@ -16,9 +16,13 @@
 
 package com.android.dialer.calllog.datasources.phonelookup;
 
+import android.content.ContentProviderOperation;
 import android.content.ContentValues;
 import android.content.Context;
+import android.content.OperationApplicationException;
 import android.database.Cursor;
+import android.net.Uri;
+import android.os.RemoteException;
 import android.support.annotation.MainThread;
 import android.support.annotation.WorkerThread;
 import android.text.TextUtils;
@@ -34,6 +38,7 @@
 import com.android.dialer.phonelookup.PhoneLookup;
 import com.android.dialer.phonelookup.PhoneLookupInfo;
 import com.android.dialer.phonelookup.PhoneLookupSelector;
+import com.android.dialer.phonelookup.database.contract.PhoneLookupHistoryContract;
 import com.android.dialer.phonelookup.database.contract.PhoneLookupHistoryContract.PhoneLookupHistory;
 import com.android.dialer.phonenumberproto.DialerPhoneNumberUtil;
 import com.google.common.collect.ImmutableMap;
@@ -44,6 +49,7 @@
 import com.google.common.util.concurrent.ListeningExecutorService;
 import com.google.i18n.phonenumbers.PhoneNumberUtil;
 import com.google.protobuf.InvalidProtocolBufferException;
+import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.List;
 import java.util.Map;
@@ -62,6 +68,23 @@
   private final ListeningExecutorService backgroundExecutorService;
   private final ListeningExecutorService lightweightExecutorService;
 
+  /**
+   * Keyed by normalized number (the primary key for PhoneLookupHistory).
+   *
+   * <p>This is state saved between the {@link #fill(Context, CallLogMutations)} and {@link
+   * #onSuccessfulFill(Context)} operations.
+   */
+  private final Map<String, PhoneLookupInfo> phoneLookupHistoryRowsToUpdate = new ArrayMap<>();
+
+  /**
+   * Normalized numbers (the primary key for PhoneLookupHistory) which should be deleted from
+   * PhoneLookupHistory.
+   *
+   * <p>This is state saved between the {@link #fill(Context, CallLogMutations)} and {@link
+   * #onSuccessfulFill(Context)} operations.
+   */
+  private final Set<String> phoneLookupHistoryRowsToDelete = new ArraySet<>();
+
   @Inject
   PhoneLookupDataSource(
       PhoneLookup phoneLookup,
@@ -108,6 +131,11 @@
    */
   @Override
   public ListenableFuture<Void> fill(Context appContext, CallLogMutations mutations) {
+    // Clear state saved since the last call to fill. This is necessary in case fill is called but
+    // onSuccessfulFill is not called during a previous flow.
+    phoneLookupHistoryRowsToUpdate.clear();
+    phoneLookupHistoryRowsToDelete.clear();
+
     // First query information from annotated call log.
     ListenableFuture<Map<DialerPhoneNumber, Set<Long>>> annotatedCallLogIdsByNumberFuture =
         backgroundExecutorService.submit(() -> queryIdAndNumberFromAnnotatedCallLog(appContext));
@@ -150,6 +178,13 @@
           }
           populateInserts(originalPhoneLookupHistoryDataByAnnotatedCallLogId.build(), mutations);
 
+          // Compute and save the PhoneLookupHistory rows which can be deleted in onSuccessfulFill.
+          DialerPhoneNumberUtil dialerPhoneNumberUtil =
+              new DialerPhoneNumberUtil(PhoneNumberUtil.getInstance());
+          phoneLookupHistoryRowsToDelete.addAll(
+              computePhoneLookupHistoryRowsToDelete(
+                  annotatedCallLogIdsByNumber, mutations, dialerPhoneNumberUtil));
+
           // Now compute the rows to update.
           ImmutableMap.Builder<Long, PhoneLookupInfo> rowsToUpdate = ImmutableMap.builder();
           for (Entry<DialerPhoneNumber, PhoneLookupInfo> entry : updatedInfoMap.entrySet()) {
@@ -159,6 +194,10 @@
               for (Long id : annotatedCallLogIdsByNumber.get(dialerPhoneNumber)) {
                 rowsToUpdate.put(id, upToDateInfo);
               }
+              // Also save the updated information so that it can be written to PhoneLookupHistory
+              // in onSuccessfulFill.
+              String normalizedNumber = dialerPhoneNumberUtil.formatToE164(dialerPhoneNumber);
+              phoneLookupHistoryRowsToUpdate.put(normalizedNumber, upToDateInfo);
             }
           }
           return rowsToUpdate.build();
@@ -167,9 +206,11 @@
     ListenableFuture<ImmutableMap<Long, PhoneLookupInfo>> rowsToUpdateFuture =
         Futures.whenAllSucceed(
                 annotatedCallLogIdsByNumberFuture, updatedInfoMapFuture, originalInfoMapFuture)
-            .call(computeRowsToUpdate, lightweightExecutorService);
+            .call(
+                computeRowsToUpdate,
+                backgroundExecutorService /* PhoneNumberUtil may do disk IO */);
 
-    // Finally apply the computed rows to update to mutations.
+    // Finally update the mutations with the computed rows.
     return Futures.transform(
         rowsToUpdateFuture,
         rowsToUpdate -> {
@@ -181,12 +222,38 @@
 
   @Override
   public ListenableFuture<Void> onSuccessfulFill(Context appContext) {
-    return backgroundExecutorService.submit(this::onSuccessfulFillInternal);
+    // First update and/or delete the appropriate rows in PhoneLookupHistory.
+    ListenableFuture<Void> writePhoneLookupHistory =
+        backgroundExecutorService.submit(() -> writePhoneLookupHistory(appContext));
+
+    // If that succeeds, delegate to the composite PhoneLookup to notify all PhoneLookups that both
+    // the AnnotatedCallLog and PhoneLookupHistory have been successfully updated.
+    return Futures.transformAsync(
+        writePhoneLookupHistory,
+        unused -> phoneLookup.onSuccessfulBulkUpdate(),
+        lightweightExecutorService);
   }
 
   @WorkerThread
-  private Void onSuccessfulFillInternal() {
-    // TODO(zachh): Update PhoneLookupHistory.
+  private Void writePhoneLookupHistory(Context appContext)
+      throws RemoteException, OperationApplicationException {
+    ArrayList<ContentProviderOperation> operations = new ArrayList<>();
+    long currentTimestamp = System.currentTimeMillis();
+    for (Entry<String, PhoneLookupInfo> entry : phoneLookupHistoryRowsToUpdate.entrySet()) {
+      String normalizedNumber = entry.getKey();
+      PhoneLookupInfo phoneLookupInfo = entry.getValue();
+      ContentValues contentValues = new ContentValues();
+      contentValues.put(PhoneLookupHistory.PHONE_LOOKUP_INFO, phoneLookupInfo.toByteArray());
+      contentValues.put(PhoneLookupHistory.LAST_MODIFIED, currentTimestamp);
+      operations.add(
+          ContentProviderOperation.newUpdate(numberUri(normalizedNumber))
+              .withValues(contentValues)
+              .build());
+    }
+    for (String normalizedNumber : phoneLookupHistoryRowsToDelete) {
+      operations.add(ContentProviderOperation.newDelete(numberUri(normalizedNumber)).build());
+    }
+    appContext.getContentResolver().applyBatch(PhoneLookupHistoryContract.AUTHORITY, operations);
     return null;
   }
 
@@ -422,7 +489,47 @@
     }
   }
 
+  private Set<String> computePhoneLookupHistoryRowsToDelete(
+      Map<DialerPhoneNumber, Set<Long>> annotatedCallLogIdsByNumber,
+      CallLogMutations mutations,
+      DialerPhoneNumberUtil dialerPhoneNumberUtil) {
+    if (mutations.getDeletes().isEmpty()) {
+      return ImmutableSet.of();
+    }
+    // First convert the dialer phone numbers to normalized numbers; we need to combine entries
+    // because different DialerPhoneNumbers can map to the same normalized number.
+    Map<String, Set<Long>> idsByNormalizedNumber = new ArrayMap<>();
+    for (Entry<DialerPhoneNumber, Set<Long>> entry : annotatedCallLogIdsByNumber.entrySet()) {
+      DialerPhoneNumber dialerPhoneNumber = entry.getKey();
+      Set<Long> idsForDialerPhoneNumber = entry.getValue();
+      String normalizedNumber = dialerPhoneNumberUtil.formatToE164(dialerPhoneNumber);
+      Set<Long> idsForNormalizedNumber = idsByNormalizedNumber.get(normalizedNumber);
+      if (idsForNormalizedNumber == null) {
+        idsForNormalizedNumber = new ArraySet<>();
+        idsByNormalizedNumber.put(normalizedNumber, idsForNormalizedNumber);
+      }
+      idsForNormalizedNumber.addAll(idsForDialerPhoneNumber);
+    }
+    // Now look through and remove all IDs that were scheduled for delete; after doing that, if
+    // there are no remaining IDs left for a normalized number, the number can be deleted from
+    // PhoneLookupHistory.
+    Set<String> normalizedNumbersToDelete = new ArraySet<>();
+    for (Entry<String, Set<Long>> entry : idsByNormalizedNumber.entrySet()) {
+      String normalizedNumber = entry.getKey();
+      Set<Long> idsForNormalizedNumber = entry.getValue();
+      idsForNormalizedNumber.removeAll(mutations.getDeletes());
+      if (idsForNormalizedNumber.isEmpty()) {
+        normalizedNumbersToDelete.add(normalizedNumber);
+      }
+    }
+    return normalizedNumbersToDelete;
+  }
+
   private static String selectName(PhoneLookupInfo phoneLookupInfo) {
     return PhoneLookupSelector.selectName(phoneLookupInfo);
   }
+
+  private static Uri numberUri(String number) {
+    return PhoneLookupHistory.CONTENT_URI.buildUpon().appendEncodedPath(number).build();
+  }
 }
diff --git a/java/com/android/dialer/phonelookup/database/PhoneLookupHistoryContentProvider.java b/java/com/android/dialer/phonelookup/database/PhoneLookupHistoryContentProvider.java
index e85654e..5c0c00f 100644
--- a/java/com/android/dialer/phonelookup/database/PhoneLookupHistoryContentProvider.java
+++ b/java/com/android/dialer/phonelookup/database/PhoneLookupHistoryContentProvider.java
@@ -17,7 +17,10 @@
 package com.android.dialer.phonelookup.database;
 
 import android.content.ContentProvider;
+import android.content.ContentProviderOperation;
+import android.content.ContentProviderResult;
 import android.content.ContentValues;
+import android.content.OperationApplicationException;
 import android.content.UriMatcher;
 import android.database.Cursor;
 import android.database.DatabaseUtils;
@@ -31,6 +34,7 @@
 import com.android.dialer.common.LogUtil;
 import com.android.dialer.phonelookup.database.contract.PhoneLookupHistoryContract;
 import com.android.dialer.phonelookup.database.contract.PhoneLookupHistoryContract.PhoneLookupHistory;
+import java.util.ArrayList;
 
 /**
  * {@link ContentProvider} for the PhoneLookupHistory.
@@ -50,13 +54,6 @@
  */
 public class PhoneLookupHistoryContentProvider extends ContentProvider {
 
-  /**
-   * We sometimes run queries where we potentially pass numbers into a where clause using the
-   * (?,?,?,...) syntax. The maximum number of host parameters is 999, so that's the maximum size
-   * this table can be. See https://www.sqlite.org/limits.html for more details.
-   */
-  private static final int MAX_ROWS = 999;
-
   // For operations against: content://com.android.dialer.phonelookuphistory/PhoneLookupHistory
   private static final int PHONE_LOOKUP_HISTORY_TABLE_CODE = 1;
   // For operations against: content://com.android.dialer.phonelookuphistory/PhoneLookupHistory/+123
@@ -77,9 +74,16 @@
 
   private PhoneLookupHistoryDatabaseHelper databaseHelper;
 
+  private final ThreadLocal<Boolean> applyingBatch = new ThreadLocal<>();
+
+  /** Ensures that only a single notification is generated from {@link #applyBatch(ArrayList)}. */
+  private boolean isApplyingBatch() {
+    return applyingBatch.get() != null && applyingBatch.get();
+  }
+
   @Override
   public boolean onCreate() {
-    databaseHelper = new PhoneLookupHistoryDatabaseHelper(getContext(), MAX_ROWS);
+    databaseHelper = new PhoneLookupHistoryDatabaseHelper(getContext());
     return true;
   }
 
@@ -168,7 +172,9 @@
             .buildUpon()
             .appendEncodedPath(values.getAsString(PhoneLookupHistory.NORMALIZED_NUMBER))
             .build();
-    notifyChange(insertedUri);
+    if (!isApplyingBatch()) {
+      notifyChange(insertedUri);
+    }
     return insertedUri;
   }
 
@@ -197,7 +203,9 @@
       LogUtil.w("PhoneLookupHistoryContentProvider.delete", "no rows deleted");
       return rows;
     }
-    notifyChange(uri);
+    if (!isApplyingBatch()) {
+      notifyChange(uri);
+    }
     return rows;
   }
 
@@ -206,6 +214,9 @@
    * "content://com.android.dialer.phonelookuphistory/PhoneLookupHistory/+123") then the update
    * operation will actually be a "replace" operation, inserting a new row if one does not already
    * exist.
+   *
+   * <p>All columns in an existing row will be replaced which means you must specify all required
+   * columns in {@code values} when using this method.
    */
   @Override
   public int update(
@@ -225,7 +236,9 @@
           LogUtil.w("PhoneLookupHistoryContentProvider.update", "no rows updated");
           return rows;
         }
-        notifyChange(uri);
+        if (!isApplyingBatch()) {
+          notifyChange(uri);
+        }
         return rows;
       case PHONE_LOOKUP_HISTORY_TABLE_ID_CODE:
         Assert.checkArgument(
@@ -237,14 +250,65 @@
 
         String normalizedNumber = uri.getLastPathSegment();
         values.put(PhoneLookupHistory.NORMALIZED_NUMBER, normalizedNumber);
-        database.replace(PhoneLookupHistory.TABLE, null, values);
-        notifyChange(uri);
+        long result = database.replace(PhoneLookupHistory.TABLE, null, values);
+        Assert.checkArgument(result != -1, "replacing PhoneLookupHistory row failed");
+        if (!isApplyingBatch()) {
+          notifyChange(uri);
+        }
         return 1;
       default:
         throw new IllegalArgumentException("Unknown uri: " + uri);
     }
   }
 
+  /**
+   * {@inheritDoc}
+   *
+   * <p>Note: When applyBatch is used with the PhoneLookupHistory, only a single notification for
+   * the content URI is generated, not individual notifications for each affected URI.
+   */
+  @NonNull
+  @Override
+  public ContentProviderResult[] applyBatch(@NonNull ArrayList<ContentProviderOperation> operations)
+      throws OperationApplicationException {
+    ContentProviderResult[] results = new ContentProviderResult[operations.size()];
+    if (operations.isEmpty()) {
+      return results;
+    }
+
+    SQLiteDatabase database = databaseHelper.getWritableDatabase();
+    try {
+      applyingBatch.set(true);
+      database.beginTransaction();
+      for (int i = 0; i < operations.size(); i++) {
+        ContentProviderOperation operation = operations.get(i);
+        int match = uriMatcher.match(operation.getUri());
+        switch (match) {
+          case PHONE_LOOKUP_HISTORY_TABLE_CODE:
+          case PHONE_LOOKUP_HISTORY_TABLE_ID_CODE:
+            ContentProviderResult result = operation.apply(this, results, i);
+            if (operation.isInsert()) {
+              if (result.uri == null) {
+                throw new OperationApplicationException("error inserting row");
+              }
+            } else if (result.count == 0) {
+              throw new OperationApplicationException("error applying operation");
+            }
+            results[i] = result;
+            break;
+          default:
+            throw new IllegalArgumentException("Unknown uri: " + operation.getUri());
+        }
+      }
+      database.setTransactionSuccessful();
+    } finally {
+      applyingBatch.set(false);
+      database.endTransaction();
+    }
+    notifyChange(PhoneLookupHistory.CONTENT_URI);
+    return results;
+  }
+
   private void notifyChange(Uri uri) {
     getContext().getContentResolver().notifyChange(uri, null);
   }
diff --git a/java/com/android/dialer/phonelookup/database/PhoneLookupHistoryDatabaseHelper.java b/java/com/android/dialer/phonelookup/database/PhoneLookupHistoryDatabaseHelper.java
index 70d88ce..43b6f10 100644
--- a/java/com/android/dialer/phonelookup/database/PhoneLookupHistoryDatabaseHelper.java
+++ b/java/com/android/dialer/phonelookup/database/PhoneLookupHistoryDatabaseHelper.java
@@ -22,17 +22,15 @@
 import android.os.SystemClock;
 import com.android.dialer.common.LogUtil;
 import com.android.dialer.phonelookup.database.contract.PhoneLookupHistoryContract.PhoneLookupHistory;
-import java.util.Locale;
 
 /** {@link SQLiteOpenHelper} for the PhoneLookupHistory database. */
 class PhoneLookupHistoryDatabaseHelper extends SQLiteOpenHelper {
-  private final int maxRows;
 
-  PhoneLookupHistoryDatabaseHelper(Context appContext, int maxRows) {
+  PhoneLookupHistoryDatabaseHelper(Context appContext) {
     super(appContext, "phone_lookup_history.db", null, 1);
-    this.maxRows = maxRows;
   }
 
+  // TODO(zachh): LAST_MODIFIED is no longer read and can be deleted.
   private static final String CREATE_TABLE_SQL =
       "create table if not exists "
           + PhoneLookupHistory.TABLE
@@ -42,28 +40,6 @@
           + (PhoneLookupHistory.LAST_MODIFIED + " long not null")
           + ");";
 
-  /** Deletes all but the first maxRows rows (by timestamp) to keep the table a manageable size. */
-  private static final String CREATE_TRIGGER_SQL =
-      "create trigger delete_old_rows after insert on "
-          + PhoneLookupHistory.TABLE
-          + " when (select count(*) from "
-          + PhoneLookupHistory.TABLE
-          + ") > %d"
-          + " begin delete from "
-          + PhoneLookupHistory.TABLE
-          + " where "
-          + PhoneLookupHistory.NORMALIZED_NUMBER
-          + " in (select "
-          + PhoneLookupHistory.NORMALIZED_NUMBER
-          + " from "
-          + PhoneLookupHistory.TABLE
-          + " order by "
-          + PhoneLookupHistory.LAST_MODIFIED
-          + " limit (select count(*)-%d"
-          + " from "
-          + PhoneLookupHistory.TABLE
-          + " )); end;";
-
   private static final String CREATE_INDEX_ON_LAST_MODIFIED_SQL =
       "create index last_modified_index on "
           + PhoneLookupHistory.TABLE
@@ -76,7 +52,6 @@
     LogUtil.enterBlock("PhoneLookupHistoryDatabaseHelper.onCreate");
     long startTime = SystemClock.uptimeMillis();
     db.execSQL(CREATE_TABLE_SQL);
-    db.execSQL(String.format(Locale.US, CREATE_TRIGGER_SQL, maxRows, maxRows));
     db.execSQL(CREATE_INDEX_ON_LAST_MODIFIED_SQL);
     // TODO(zachh): Consider logging impression.
     LogUtil.i(