diff --git a/src/com/android/dialer/database/DialerDatabaseHelper.java b/src/com/android/dialer/database/DialerDatabaseHelper.java
index d36a0f6..413e867 100644
--- a/src/com/android/dialer/database/DialerDatabaseHelper.java
+++ b/src/com/android/dialer/database/DialerDatabaseHelper.java
@@ -184,6 +184,23 @@
                 SELECT_IGNORE_LOOKUP_KEY_TOO_LONG_CLAUSE;
     }
 
+    /**
+     * Query for all contacts that have been updated since the last time the smart dial database
+     * was updated.
+     */
+    public static interface UpdatedContactQuery {
+        static final Uri URI = ContactsContract.Contacts.CONTENT_URI;
+
+        static final String[] PROJECTION = new String[] {
+                ContactsContract.Contacts._ID  // 0
+        };
+
+        static final int UPDATED_CONTACT_ID = 0;
+
+        static final String SELECT_UPDATED_CLAUSE =
+                ContactsContract.Contacts.CONTACT_LAST_UPDATED_TIMESTAMP + " > ?";
+    }
+
     /** Query options for querying the deleted contact database.*/
     public static interface DeleteContactQuery {
        static final Uri URI = ContactsContract.DeletedContacts.CONTENT_URI;
@@ -563,15 +580,11 @@
      * Removes rows in the smartdial database that matches the contacts that have been deleted
      * by other apps since last update.
      *
-     * @param db Database pointer to the dialer database.
-     * @param last_update_time Time stamp of last update on the smartdial database
+     * @param db Database to operate on.
+     * @param deletedContactCursor Cursor containing rows of deleted contacts
      */
-    private void removeDeletedContacts(SQLiteDatabase db, String last_update_time) {
-        final Cursor deletedContactCursor = mContext.getContentResolver().query(
-                DeleteContactQuery.URI,
-                DeleteContactQuery.PROJECTION,
-                DeleteContactQuery.SELECT_UPDATED_CLAUSE,
-                new String[] {last_update_time}, null);
+    @VisibleForTesting
+    void removeDeletedContacts(SQLiteDatabase db, Cursor deletedContactCursor) {
         if (deletedContactCursor == null) {
             return;
         }
@@ -594,6 +607,15 @@
         }
     }
 
+    private Cursor getDeletedContactCursor(String lastUpdateMillis) {
+        return mContext.getContentResolver().query(
+                DeleteContactQuery.URI,
+                DeleteContactQuery.PROJECTION,
+                DeleteContactQuery.SELECT_UPDATED_CLAUSE,
+                new String[] {lastUpdateMillis},
+                null);
+    }
+
     /**
      * Removes potentially corrupted entries in the database. These contacts may be added before
      * the previous instance of the dialer was destroyed for some reason. For data integrity, we
@@ -637,11 +659,14 @@
      * @param db Database pointer to the smartdial database
      * @param updatedContactCursor Cursor pointing to the list of recently updated contacts.
      */
-    private void removeUpdatedContacts(SQLiteDatabase db, Cursor updatedContactCursor) {
+    @VisibleForTesting
+    void removeUpdatedContacts(SQLiteDatabase db, Cursor updatedContactCursor) {
         db.beginTransaction();
         try {
+            updatedContactCursor.moveToPosition(-1);
             while (updatedContactCursor.moveToNext()) {
-                final Long contactId = updatedContactCursor.getLong(PhoneQuery.PHONE_CONTACT_ID);
+                final Long contactId =
+                        updatedContactCursor.getLong(UpdatedContactQuery.UPDATED_CONTACT_ID);
 
                 db.delete(Tables.SMARTDIAL_TABLE, SmartDialDbColumns.CONTACT_ID + "=" +
                         contactId, null);
@@ -814,59 +839,75 @@
             if (DEBUG) {
                 Log.v(TAG, "Last updated at " + lastUpdateMillis);
             }
-            /** Queries the contact database to get contacts that have been updated since the last
-             * update time.
-             */
-            final Cursor updatedContactCursor = mContext.getContentResolver().query(PhoneQuery.URI,
-                    PhoneQuery.PROJECTION, PhoneQuery.SELECTION,
-                    new String[]{lastUpdateMillis}, null);
-            if (updatedContactCursor == null) {
-                if (DEBUG) {
-                    Log.e(TAG, "SmartDial query received null for cursor");
-                }
-                return;
-            }
 
             /** Sets the time after querying the database as the current update time. */
             final Long currentMillis = System.currentTimeMillis();
 
-            try {
-                if (DEBUG) {
-                    stopWatch.lap("Queried the Contacts database");
-                }
+            if (DEBUG) {
+                stopWatch.lap("Queried the Contacts database");
+            }
 
-                /** Prevents the app from reading the dialer database when updating. */
-                sInUpdate.getAndSet(true);
+            /** Prevents the app from reading the dialer database when updating. */
+            sInUpdate.getAndSet(true);
 
-                /** Removes contacts that have been deleted. */
-                removeDeletedContacts(db, lastUpdateMillis);
-                removePotentiallyCorruptedContacts(db, lastUpdateMillis);
+            /** Removes contacts that have been deleted. */
+            removeDeletedContacts(db, getDeletedContactCursor(lastUpdateMillis));
+            removePotentiallyCorruptedContacts(db, lastUpdateMillis);
 
-                if (DEBUG) {
-                    stopWatch.lap("Finished deleting deleted entries");
-                }
+            if (DEBUG) {
+                stopWatch.lap("Finished deleting deleted entries");
+            }
 
-                /** If the database did not exist before, jump through deletion as there is nothing
-                 * to delete.
+            /** If the database did not exist before, jump through deletion as there is nothing
+             * to delete.
+             */
+            if (!lastUpdateMillis.equals("0")) {
+                /** Removes contacts that have been updated. Updated contact information will be
+                 * inserted later. Note that this has to use a separate result set from
+                 * updatePhoneCursor, since it is possible for a contact to be updated (e.g.
+                 * phone number deleted), but have no results show up in updatedPhoneCursor (since
+                 * all of its phone numbers have been deleted).
                  */
-                if (!lastUpdateMillis.equals("0")) {
-                    /** Removes contacts that have been updated. Updated contact information will be
-                     * inserted later.
-                     */
-                    removeUpdatedContacts(db, updatedContactCursor);
-                    if (DEBUG) {
-                        stopWatch.lap("Finished deleting updated entries");
-                    }
+                final Cursor updatedContactCursor = mContext.getContentResolver().query(
+                        UpdatedContactQuery.URI,
+                        UpdatedContactQuery.PROJECTION,
+                        UpdatedContactQuery.SELECT_UPDATED_CLAUSE,
+                        new String[] {lastUpdateMillis},
+                        null
+                        );
+                if (updatedContactCursor == null) {
+                    Log.e(TAG, "SmartDial query received null for cursor");
+                    return;
                 }
+                try {
+                    removeUpdatedContacts(db, updatedContactCursor);
+                } finally {
+                    updatedContactCursor.close();
+                }
+                if (DEBUG) {
+                    stopWatch.lap("Finished deleting entries belonging to updated contacts");
+                }
+            }
 
-                /** Inserts recently updated contacts to the smartdial database.*/
-                insertUpdatedContactsAndNumberPrefix(db, updatedContactCursor, currentMillis);
+            /** Queries the contact database to get all phone numbers that have been updated since the last
+             * update time.
+             */
+            final Cursor updatedPhoneCursor = mContext.getContentResolver().query(PhoneQuery.URI,
+                    PhoneQuery.PROJECTION, PhoneQuery.SELECTION,
+                    new String[]{lastUpdateMillis}, null);
+            if (updatedPhoneCursor == null) {
+                Log.e(TAG, "SmartDial query received null for cursor");
+                return;
+            }
+
+            try {
+                /** Inserts recently updated phone numbers to the smartdial database.*/
+                insertUpdatedContactsAndNumberPrefix(db, updatedPhoneCursor, currentMillis);
                 if (DEBUG) {
                     stopWatch.lap("Finished building the smart dial table");
                 }
             } finally {
-                /** Inserts prefixes of phone numbers into the prefix table.*/
-                updatedContactCursor.close();
+                updatedPhoneCursor.close();
             }
 
             /** Gets a list of distinct contacts which have been updated, and adds the name prefixes
diff --git a/tests/src/com/android/dialer/database/DatabaseTestUtils.java b/tests/src/com/android/dialer/database/DatabaseTestUtils.java
new file mode 100644
index 0000000..671497d
--- /dev/null
+++ b/tests/src/com/android/dialer/database/DatabaseTestUtils.java
@@ -0,0 +1,81 @@
+/*
+ * Copyright (C) 2015 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.database;
+
+import android.database.MatrixCursor;
+import android.provider.ContactsContract.Contacts;
+import android.provider.ContactsContract.Data;
+import android.provider.ContactsContract.CommonDataKinds.Phone;
+import android.text.TextUtils;
+
+import com.android.dialer.database.DialerDatabaseHelper.ContactNumber;
+
+public class DatabaseTestUtils {
+    public static MatrixCursor constructNewNameCursor() {
+        final MatrixCursor cursor = new MatrixCursor(new String[]{
+                DialerDatabaseHelper.SmartDialDbColumns.DISPLAY_NAME_PRIMARY,
+                DialerDatabaseHelper.SmartDialDbColumns.CONTACT_ID});
+        return cursor;
+    }
+
+    public static MatrixCursor constructNewContactCursor() {
+        final MatrixCursor cursor = new MatrixCursor(new String[]{
+                    Phone._ID,                          // 0
+                    Phone.TYPE,                         // 1
+                    Phone.LABEL,                        // 2
+                    Phone.NUMBER,                       // 3
+                    Phone.CONTACT_ID,                   // 4
+                    Phone.LOOKUP_KEY,                   // 5
+                    Phone.DISPLAY_NAME_PRIMARY,         // 6
+                    Phone.PHOTO_ID,                     // 7
+                    Data.LAST_TIME_USED,                // 8
+                    Data.TIMES_USED,                    // 9
+                    Contacts.STARRED,                   // 10
+                    Data.IS_SUPER_PRIMARY,              // 11
+                    Contacts.IN_VISIBLE_GROUP,          // 12
+                    Data.IS_PRIMARY});                  // 13
+        return cursor;
+    }
+
+    public static ContactNumber constructNewContactWithDummyIds(MatrixCursor contactCursor,
+            MatrixCursor nameCursor, String number, int id, String displayName) {
+        return constructNewContact(contactCursor, nameCursor, id, number, id, String.valueOf(id),
+                displayName, 0, 0, 0, 0, 0, 0, 0);
+    }
+
+    public static ContactNumber constructNewContact(MatrixCursor contactCursor,
+            MatrixCursor nameCursor, int id, String number, int contactId, String lookupKey,
+            String displayName, int photoId, int lastTimeUsed, int timesUsed, int starred,
+            int isSuperPrimary, int inVisibleGroup, int isPrimary) {
+        if (contactCursor == null || nameCursor == null) {
+            throw new IllegalArgumentException("Provided MatrixCursors cannot be null");
+        }
+
+        if (TextUtils.isEmpty(number)) {
+            // Add a dummy number, otherwise DialerDatabaseHelper simply ignores the entire
+            // row if the number is empty
+            number = "0";
+        }
+
+        contactCursor.addRow(new Object[]{id, "", "", number, contactId, lookupKey, displayName,
+                photoId, lastTimeUsed, timesUsed, starred, isSuperPrimary, inVisibleGroup,
+                isPrimary});
+        nameCursor.addRow(new Object[]{displayName, contactId});
+
+        return new ContactNumber(contactId, id, displayName, number, lookupKey, 0);
+    }
+}
diff --git a/tests/src/com/android/dialer/database/DialerDatabaseHelperTest.java b/tests/src/com/android/dialer/database/DialerDatabaseHelperTest.java
new file mode 100644
index 0000000..a95a79e
--- /dev/null
+++ b/tests/src/com/android/dialer/database/DialerDatabaseHelperTest.java
@@ -0,0 +1,154 @@
+/*
+ * Copyright (C) 2013 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.database;
+
+import static com.android.dialer.database.DatabaseTestUtils.*;
+
+import android.database.MatrixCursor;
+import android.database.sqlite.SQLiteDatabase;
+import android.test.suitebuilder.annotation.SmallTest;
+import android.test.suitebuilder.annotation.Suppress;
+import android.test.AndroidTestCase;
+
+import com.android.dialer.database.DialerDatabaseHelper;
+import com.android.dialer.database.DialerDatabaseHelper.ContactNumber;
+import com.android.dialer.dialpad.SmartDialNameMatcher;
+import com.android.dialer.dialpad.SmartDialPrefix;
+
+import java.lang.Exception;
+import java.lang.Override;
+import java.util.ArrayList;
+
+/**
+ * Validates the behavior of the smart dial database helper with regards to contact updates and
+ * deletes.
+ * To run this test, use the command:
+ * adb shell am instrument -w -e class com.android.dialer.database.DialerDatabaseHelperTest /
+ * com.android.dialer.tests/android.test.InstrumentationTestRunner
+ */
+@SmallTest
+public class DialerDatabaseHelperTest extends AndroidTestCase {
+
+    private DialerDatabaseHelper mTestHelper;
+    private SQLiteDatabase mDb;
+
+    @Override
+    protected void setUp() {
+        mTestHelper = DialerDatabaseHelper.getNewInstanceForTest(getContext());
+        mDb = mTestHelper.getWritableDatabase();
+    }
+
+    @Override
+    protected void tearDown() throws Exception {
+        final SQLiteDatabase db = mTestHelper.getWritableDatabase();
+        mTestHelper.removeAllContacts(db);
+        super.tearDown();
+    }
+
+    /**
+     * Verifies that a new contact added into the database is a match after the update.
+     */
+    public void testForNewContacts() {
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(mDb, contactCursor, 0L);
+        mTestHelper.insertNamePrefixes(mDb, nameCursor);
+        assertEquals(0, getMatchesFromDb("5105272357").size());
+
+        // Insert new contact
+        constructNewContactWithDummyIds(contactCursor, nameCursor,
+                "510-527-2357", 0,  "James");
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(mDb, contactCursor, 1L);
+        mTestHelper.insertNamePrefixes(mDb, nameCursor);
+        assertEquals(1, getMatchesFromDb("5105272357").size());
+    }
+
+    /**
+     * Verifies that a contact that has its phone number changed is a match after the update.
+     */
+    public void testForUpdatedContacts() {
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        constructNewContactWithDummyIds(contactCursor, nameCursor,
+                "510-527-2357", 0,  "James");
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(mDb, contactCursor, 0L);
+        mTestHelper.insertNamePrefixes(mDb, nameCursor);
+        assertEquals(1, getMatchesFromDb("5105272357").size());
+        assertEquals(0, getMatchesFromDb("6501234567").size());
+
+        // Update the database with the new contact information
+        final MatrixCursor nameCursor2 =  constructNewNameCursor();
+        final MatrixCursor contactCursor2 = constructNewContactCursor();
+        constructNewContactWithDummyIds(contactCursor2, nameCursor2,
+                "650-123-4567", 0,  "James");
+        mTestHelper.removeUpdatedContacts(mDb, contactCursor2);
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(mDb, contactCursor2, 1L);
+        mTestHelper.insertNamePrefixes(mDb, nameCursor2);
+
+        // Now verify the matches are correct based on the new information
+        assertEquals(0, getMatchesFromDb("5105272357").size());
+        assertEquals(1, getMatchesFromDb("6501234567").size());
+    }
+
+    /**
+     * Verifies that a contact that is deleted from CP2 is similarly deleted from the database
+     */
+    public void testForDeletedContacts() {
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        constructNewContactWithDummyIds(contactCursor, nameCursor,
+                "510-527-2357", 0,  "James");
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(mDb, contactCursor, 0L);
+        mTestHelper.insertNamePrefixes(mDb, nameCursor);
+        assertEquals(1, getMatchesFromDb("5105272357").size());
+
+        // Delete the contact and update its projection.
+        final MatrixCursor deletedCursor =
+                new MatrixCursor(DialerDatabaseHelper.DeleteContactQuery.PROJECTION);
+        deletedCursor.addRow(new Object[] {0, 1L});
+        mTestHelper.removeDeletedContacts(mDb, deletedCursor);
+        assertEquals(0, getMatchesFromDb("5105272357").size());
+    }
+
+    /**
+     * Verifies that when a contact's number is deleted (but not the entire contact), the
+     * number is correctly deleted from the database.
+     */
+    public void testForDeletedNumber() {
+        final MatrixCursor nameCursor =  constructNewNameCursor();
+        final MatrixCursor contactCursor = constructNewContactCursor();
+        constructNewContactWithDummyIds(contactCursor, nameCursor,
+                "510-527-2357", 0,  "James");
+        mTestHelper.insertUpdatedContactsAndNumberPrefix(mDb, contactCursor, 0L);
+        mTestHelper.insertNamePrefixes(mDb, nameCursor);
+        assertEquals(1, getMatchesFromDb("5105272357").size());
+
+        // Match no longer exists after number was deleted from contact
+        final MatrixCursor updatedContactCursor =
+                new MatrixCursor(DialerDatabaseHelper.UpdatedContactQuery.PROJECTION);
+        updatedContactCursor.addRow(new Object[] {0});
+        mTestHelper.removeUpdatedContacts(mDb, updatedContactCursor);
+        assertEquals(0, getMatchesFromDb("5105272357").size());
+    }
+
+    private ArrayList<ContactNumber> getMatchesFromDb(String query) {
+        final SmartDialNameMatcher nameMatcher = new SmartDialNameMatcher(query,
+                SmartDialPrefix.getMap());
+        return mTestHelper.getLooseMatches(query, nameMatcher);
+    }
+}
diff --git a/tests/src/com/android/dialer/database/SmartDialPrefixTest.java b/tests/src/com/android/dialer/database/SmartDialPrefixTest.java
index 9cb842e..78962e3 100644
--- a/tests/src/com/android/dialer/database/SmartDialPrefixTest.java
+++ b/tests/src/com/android/dialer/database/SmartDialPrefixTest.java
@@ -16,16 +16,12 @@
 
 package com.android.dialer.database;
 
+import static com.android.dialer.database.DatabaseTestUtils.*;
+
 import android.database.MatrixCursor;
 import android.database.sqlite.SQLiteDatabase;
 import android.test.suitebuilder.annotation.SmallTest;
-import android.test.suitebuilder.annotation.Suppress;
 import android.test.AndroidTestCase;
-import android.text.TextUtils;
-import android.util.Log;
-import android.provider.ContactsContract.CommonDataKinds.Phone;
-import android.provider.ContactsContract.Contacts;
-import android.provider.ContactsContract.Data;
 
 import com.android.dialer.database.DialerDatabaseHelper;
 import com.android.dialer.database.DialerDatabaseHelper.ContactNumber;
@@ -91,76 +87,6 @@
         super.tearDown();
     }
 
-    @Suppress
-    public void testForNewContacts() {
-    }
-
-    @Suppress
-    public void testForUpdatedContacts() {
-    }
-
-    @Suppress
-    public void testForDeletedContacts() {
-    }
-
-    @Suppress
-    public void testSize() {
-    }
-
-
-    private MatrixCursor constructNewNameCursor() {
-        final MatrixCursor cursor = new MatrixCursor(new String[]{
-                DialerDatabaseHelper.SmartDialDbColumns.DISPLAY_NAME_PRIMARY,
-                DialerDatabaseHelper.SmartDialDbColumns.CONTACT_ID});
-        return cursor;
-    }
-
-    private MatrixCursor constructNewContactCursor() {
-        final MatrixCursor cursor = new MatrixCursor(new String[]{
-                    Phone._ID,                          // 0
-                    Phone.TYPE,                         // 1
-                    Phone.LABEL,                        // 2
-                    Phone.NUMBER,                       // 3
-                    Phone.CONTACT_ID,                   // 4
-                    Phone.LOOKUP_KEY,                   // 5
-                    Phone.DISPLAY_NAME_PRIMARY,         // 6
-                    Phone.PHOTO_ID,                     // 7
-                    Data.LAST_TIME_USED,                // 8
-                    Data.TIMES_USED,                    // 9
-                    Contacts.STARRED,                   // 10
-                    Data.IS_SUPER_PRIMARY,              // 11
-                    Contacts.IN_VISIBLE_GROUP,          // 12
-                    Data.IS_PRIMARY});                  // 13
-        return cursor;
-    }
-
-    private ContactNumber constructNewContactWithDummyIds(MatrixCursor contactCursor,
-            MatrixCursor nameCursor, String number, int id, String displayName) {
-        return constructNewContact(contactCursor, nameCursor, id, number, id, String.valueOf(id),
-                displayName, 0, 0, 0, 0, 0, 0, 0);
-    }
-
-    private ContactNumber constructNewContact(MatrixCursor contactCursor, MatrixCursor nameCursor,
-            int id, String number, int contactId, String lookupKey, String displayName, int photoId,
-            int lastTimeUsed, int timesUsed, int starred, int isSuperPrimary, int inVisibleGroup,
-            int isPrimary) {
-        assertNotNull(contactCursor);
-        assertNotNull(nameCursor);
-
-        if (TextUtils.isEmpty(number)) {
-            // Add a dummy number, otherwise DialerDatabaseHelper simply ignores the entire
-            // row if the number is empty
-            number = "0";
-        }
-
-        contactCursor.addRow(new Object[]{id, "", "", number, contactId, lookupKey, displayName,
-                photoId, lastTimeUsed, timesUsed, starred, isSuperPrimary, inVisibleGroup,
-                isPrimary});
-        nameCursor.addRow(new Object[]{displayName, contactId});
-
-        return new ContactNumber(contactId, id, displayName, number, lookupKey, 0);
-    }
-
     private ArrayList<ContactNumber> getLooseMatchesFromDb(String query) {
         final SmartDialNameMatcher nameMatcher = new SmartDialNameMatcher(query,
                 SmartDialPrefix.getMap());