diff --git a/java/com/android/dialer/calllog/CallLogModule.java b/java/com/android/dialer/calllog/CallLogModule.java
index 2f2f16d..9926ceb 100644
--- a/java/com/android/dialer/calllog/CallLogModule.java
+++ b/java/com/android/dialer/calllog/CallLogModule.java
@@ -19,12 +19,11 @@
 import com.android.dialer.calllog.datasources.CallLogDataSource;
 import com.android.dialer.calllog.datasources.DataSources;
 import com.android.dialer.calllog.datasources.contacts.ContactsDataSource;
+import com.android.dialer.calllog.datasources.phonelookup.PhoneLookupDataSource;
 import com.android.dialer.calllog.datasources.systemcalllog.SystemCallLogDataSource;
+import com.google.common.collect.ImmutableList;
 import dagger.Module;
 import dagger.Provides;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.List;
 
 /** Dagger module which satisfies call log dependencies. */
 @Module
@@ -32,10 +31,12 @@
 
   @Provides
   static DataSources provideCallLogDataSources(
-      SystemCallLogDataSource systemCallLogDataSource, ContactsDataSource contactsDataSource) {
+      SystemCallLogDataSource systemCallLogDataSource,
+      ContactsDataSource contactsDataSource,
+      PhoneLookupDataSource phoneLookupDataSource) {
     // System call log must be first, see getDataSourcesExcludingSystemCallLog below.
-    List<CallLogDataSource> allDataSources =
-        Collections.unmodifiableList(Arrays.asList(systemCallLogDataSource, contactsDataSource));
+    ImmutableList<CallLogDataSource> allDataSources =
+        ImmutableList.of(systemCallLogDataSource, contactsDataSource, phoneLookupDataSource);
     return new DataSources() {
       @Override
       public SystemCallLogDataSource getSystemCallLogDataSource() {
@@ -43,12 +44,12 @@
       }
 
       @Override
-      public List<CallLogDataSource> getDataSourcesIncludingSystemCallLog() {
+      public ImmutableList<CallLogDataSource> getDataSourcesIncludingSystemCallLog() {
         return allDataSources;
       }
 
       @Override
-      public List<CallLogDataSource> getDataSourcesExcludingSystemCallLog() {
+      public ImmutableList<CallLogDataSource> getDataSourcesExcludingSystemCallLog() {
         return allDataSources.subList(1, allDataSources.size());
       }
     };
diff --git a/java/com/android/dialer/calllog/database/AnnotatedCallLogDatabaseHelper.java b/java/com/android/dialer/calllog/database/AnnotatedCallLogDatabaseHelper.java
index 3062710..0d8e8ce 100644
--- a/java/com/android/dialer/calllog/database/AnnotatedCallLogDatabaseHelper.java
+++ b/java/com/android/dialer/calllog/database/AnnotatedCallLogDatabaseHelper.java
@@ -89,6 +89,13 @@
           + AnnotatedCallLog.CALL_TYPE
           + ");";
 
+  private static final String CREATE_INDEX_ON_NUMBER_SQL =
+      "create index number_index on "
+          + AnnotatedCallLog.TABLE
+          + " ("
+          + AnnotatedCallLog.NUMBER
+          + ");";
+
   @Override
   public void onCreate(SQLiteDatabase db) {
     LogUtil.enterBlock("AnnotatedCallLogDatabaseHelper.onCreate");
@@ -96,6 +103,7 @@
     db.execSQL(CREATE_TABLE_SQL);
     db.execSQL(String.format(Locale.US, CREATE_TRIGGER_SQL, maxRows, maxRows));
     db.execSQL(CREATE_INDEX_ON_CALL_TYPE_SQL);
+    db.execSQL(CREATE_INDEX_ON_NUMBER_SQL);
     // TODO(zachh): Consider logging impression.
     LogUtil.i(
         "AnnotatedCallLogDatabaseHelper.onCreate",
diff --git a/java/com/android/dialer/calllog/datasources/DataSources.java b/java/com/android/dialer/calllog/datasources/DataSources.java
index 911ca3f..113a9f7 100644
--- a/java/com/android/dialer/calllog/datasources/DataSources.java
+++ b/java/com/android/dialer/calllog/datasources/DataSources.java
@@ -17,14 +17,14 @@
 package com.android.dialer.calllog.datasources;
 
 import com.android.dialer.calllog.datasources.systemcalllog.SystemCallLogDataSource;
-import java.util.List;
+import com.google.common.collect.ImmutableList;
 
 /** Immutable lists of data sources used to populate the annotated call log. */
 public interface DataSources {
 
   SystemCallLogDataSource getSystemCallLogDataSource();
 
-  List<CallLogDataSource> getDataSourcesIncludingSystemCallLog();
+  ImmutableList<CallLogDataSource> getDataSourcesIncludingSystemCallLog();
 
-  List<CallLogDataSource> getDataSourcesExcludingSystemCallLog();
+  ImmutableList<CallLogDataSource> getDataSourcesExcludingSystemCallLog();
 }
diff --git a/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java b/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
new file mode 100644
index 0000000..90298a1
--- /dev/null
+++ b/java/com/android/dialer/calllog/datasources/phonelookup/PhoneLookupDataSource.java
@@ -0,0 +1,139 @@
+/*
+ * Copyright (C) 2017 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.datasources.phonelookup;
+
+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;
+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.storage.Unencrypted;
+import com.google.common.collect.ImmutableSet;
+import com.google.protobuf.InvalidProtocolBufferException;
+import java.util.List;
+import java.util.concurrent.ExecutionException;
+import javax.inject.Inject;
+
+/**
+ * Responsible for maintaining the columns in the annotated call log which are derived from phone
+ * 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) {
+    this.phoneLookup = phoneLookup;
+    this.sharedPreferences = sharedPreferences;
+  }
+
+  @WorkerThread
+  @Override
+  public boolean isDirty(Context appContext) {
+    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();
+    } catch (InterruptedException | ExecutionException e) {
+      throw new IllegalStateException(e);
+    }
+  }
+
+  @WorkerThread
+  @Override
+  public void fill(Context appContext, CallLogMutations mutations) {
+    // TODO(zachh): Implementation.
+  }
+
+  @WorkerThread
+  @Override
+  public void onSuccessfulFill(Context appContext) {
+    // TODO(zachh): Implementation.
+  }
+
+  @WorkerThread
+  @Override
+  public ContentValues coalesce(List<ContentValues> individualRowsSortedByTimestampDesc) {
+    // TODO(zachh): Implementation.
+    return new ContentValues();
+  }
+
+  @MainThread
+  @Override
+  public void registerContentObservers(
+      Context appContext, ContentObserverCallbacks contentObserverCallbacks) {
+    // No content observers required for this data source.
+  }
+
+  private static ImmutableSet<DialerPhoneNumber>
+      queryDistinctDialerPhoneNumbersFromAnnotatedCallLog(Context appContext) {
+    ImmutableSet.Builder<DialerPhoneNumber> numbers = ImmutableSet.builder();
+
+    try (Cursor cursor =
+        appContext
+            .getContentResolver()
+            .query(
+                AnnotatedCallLog.DISTINCT_NUMBERS_CONTENT_URI,
+                new String[] {AnnotatedCallLog.NUMBER},
+                null,
+                null,
+                null)) {
+
+      if (cursor == null) {
+        LogUtil.e(
+            "PhoneLookupDataSource.queryDistinctDialerPhoneNumbersFromAnnotatedCallLog",
+            "null cursor");
+        return numbers.build();
+      }
+
+      if (cursor.moveToFirst()) {
+        int numberColumn = cursor.getColumnIndexOrThrow(AnnotatedCallLog.NUMBER);
+        do {
+          byte[] blob = cursor.getBlob(numberColumn);
+          if (blob == null) {
+            // Not all [incoming] calls have associated phone numbers.
+            continue;
+          }
+          try {
+            numbers.add(DialerPhoneNumber.parseFrom(blob));
+          } catch (InvalidProtocolBufferException e) {
+            throw new IllegalStateException(e);
+          }
+        } while (cursor.moveToNext());
+      }
+    }
+    return numbers.build();
+  }
+}
diff --git a/java/com/android/dialer/phonelookup/testing/FakePhoneLookup.java b/java/com/android/dialer/phonelookup/testing/FakePhoneLookup.java
new file mode 100644
index 0000000..853116f
--- /dev/null
+++ b/java/com/android/dialer/phonelookup/testing/FakePhoneLookup.java
@@ -0,0 +1,83 @@
+/*
+ * Copyright (C) 2017 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.phonelookup.testing;
+
+import android.support.annotation.NonNull;
+import android.telecom.Call;
+import com.android.dialer.DialerPhoneNumber;
+import com.android.dialer.phonelookup.PhoneLookup;
+import com.android.dialer.phonelookup.PhoneLookupInfo;
+import com.google.auto.value.AutoValue;
+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.SettableFuture;
+
+/** Fake implementation of {@link PhoneLookup} used for unit tests. */
+@AutoValue
+public abstract class FakePhoneLookup implements PhoneLookup {
+
+  abstract PhoneLookupInfo lookupResult();
+
+  abstract ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> bulkUpdateResult();
+
+  abstract boolean isDirtyResult();
+
+  public static Builder builder() {
+    return new AutoValue_FakePhoneLookup.Builder()
+        .setLookupResult(PhoneLookupInfo.getDefaultInstance())
+        .setBulkUpdateResult(ImmutableMap.of())
+        .setIsDirtyResult(false);
+  }
+
+  /** Builder. */
+  @AutoValue.Builder
+  public abstract static class Builder {
+
+    public abstract Builder setLookupResult(PhoneLookupInfo phoneLookupInfo);
+
+    public abstract Builder setBulkUpdateResult(
+        ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> map);
+
+    public abstract Builder setIsDirtyResult(boolean isDirty);
+
+    public abstract FakePhoneLookup build();
+  }
+
+  @Override
+  public ListenableFuture<PhoneLookupInfo> lookup(@NonNull Call call) {
+    SettableFuture<PhoneLookupInfo> future = SettableFuture.create();
+    future.set(lookupResult());
+    return future;
+  }
+
+  @Override
+  public ListenableFuture<Boolean> isDirty(
+      ImmutableSet<DialerPhoneNumber> phoneNumbers, long lastModified) {
+    SettableFuture<Boolean> future = SettableFuture.create();
+    future.set(isDirtyResult());
+    return future;
+  }
+
+  @Override
+  public ListenableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> bulkUpdate(
+      ImmutableMap<DialerPhoneNumber, PhoneLookupInfo> existingInfoMap, long lastModified) {
+    SettableFuture<ImmutableMap<DialerPhoneNumber, PhoneLookupInfo>> future =
+        SettableFuture.create();
+    future.set(bulkUpdateResult());
+    return future;
+  }
+}