diff --git a/src/com/android/settings/search/IndexDatabaseHelper.java b/src/com/android/settings/search/IndexDatabaseHelper.java
index 60378c2..76346ec 100644
--- a/src/com/android/settings/search/IndexDatabaseHelper.java
+++ b/src/com/android/settings/search/IndexDatabaseHelper.java
@@ -245,7 +245,7 @@
         return version;
     }
 
-    public static void clearLocalesIndexed(Context context) {
+    public static void clearCachedIndexed(Context context) {
         context.getSharedPreferences(INDEX, 0).edit().clear().commit();
     }
 
@@ -257,8 +257,16 @@
         return context.getSharedPreferences(INDEX, 0).getBoolean(locale, false);
     }
 
+    public static boolean isBuildIndexed(Context context, String buildNo) {
+        return context.getSharedPreferences(INDEX, 0).getBoolean(buildNo, false);
+    }
+
+    public static void setBuildIndexed(Context context, String buildNo) {
+        context.getSharedPreferences(INDEX, 0).edit().putBoolean(buildNo, true).commit();
+    }
+
     private void dropTables(SQLiteDatabase db) {
-        clearLocalesIndexed(mContext);
+        clearCachedIndexed(mContext);
         db.execSQL("DROP TABLE IF EXISTS " + Tables.TABLE_META_INDEX);
         db.execSQL("DROP TABLE IF EXISTS " + Tables.TABLE_PREFS_INDEX);
         db.execSQL("DROP TABLE IF EXISTS " + Tables.TABLE_SAVED_QUERIES);
diff --git a/src/com/android/settings/search2/DatabaseIndexingManager.java b/src/com/android/settings/search2/DatabaseIndexingManager.java
index 1e664ff..533884d 100644
--- a/src/com/android/settings/search2/DatabaseIndexingManager.java
+++ b/src/com/android/settings/search2/DatabaseIndexingManager.java
@@ -29,6 +29,7 @@
 import android.database.sqlite.SQLiteException;
 import android.net.Uri;
 import android.os.AsyncTask;
+import android.os.Build;
 import android.provider.SearchIndexableData;
 import android.provider.SearchIndexableResource;
 import android.provider.SearchIndexablesContract;
@@ -170,7 +171,16 @@
         final List<ResolveInfo> list =
                 mContext.getPackageManager().queryIntentContentProviders(intent, 0);
 
-        final boolean isLocaleIndexed = isLocaleIndexed();
+        final String localeStr = Locale.getDefault().toString();
+        final String fingerprint = Build.FINGERPRINT;
+        final boolean isFullIndex = isFullIndex(localeStr, fingerprint);
+
+        // Drop the database when the locale or build has changed. This eliminates rows which are
+        // dynamically inserted in the old language, or deprecated settings.
+        if (isFullIndex) {
+            final SQLiteDatabase db = getWritableDatabase();
+            IndexDatabaseHelper.getInstance(mContext).reconstruct(db);
+        }
 
         for (final ResolveInfo info : list) {
             if (!DatabaseIndexingUtils.isWellKnownProvider(info, mContext)) {
@@ -179,22 +189,32 @@
             final String authority = info.providerInfo.authority;
             final String packageName = info.providerInfo.packageName;
 
-            if (!isLocaleIndexed) {
+            if (isFullIndex) {
                 addIndexablesFromRemoteProvider(packageName, authority);
             }
             addNonIndexablesKeysFromRemoteProvider(packageName, authority);
         }
 
-        final String localeStr = Locale.getDefault().toString();
-        updateDatabase(isLocaleIndexed, localeStr);
+        updateDatabase(isFullIndex, localeStr);
 
         IndexDatabaseHelper.setLocaleIndexed(mContext, localeStr);
+        IndexDatabaseHelper.setBuildIndexed(mContext, fingerprint);
     }
 
+    /**
+     * Perform a full index on an OTA or when the locale has changed
+     *
+     * @param locale is the default for the device
+     * @param fingerprint id for the current build.
+     * @return true when the locale or build has changed since last index.
+     */
     @VisibleForTesting
-    boolean isLocaleIndexed() {
-        final String locale = Locale.getDefault().toString();
-        return IndexDatabaseHelper.getInstance(mContext).isLocaleAlreadyIndexed(mContext, locale);
+    boolean isFullIndex(String locale, String fingerprint) {
+        final boolean isLocaleIndexed = IndexDatabaseHelper.getInstance(mContext)
+                .isLocaleAlreadyIndexed(mContext, locale);
+        final boolean isBuildIndexed = IndexDatabaseHelper.getInstance(mContext)
+                .isBuildIndexed(mContext, fingerprint);
+        return !isLocaleIndexed || !isBuildIndexed;
     }
 
     /**
@@ -204,11 +224,11 @@
      * Then search results are verified to have the correct value of enabled.
      * Finally, we record that the locale has been indexed.
      *
-     * @param isIncrementalUpdate true when the language has already been indexed.
+     * @param needsReindexing true the database needs to be rebuilt.
      * @param localeStr the default locale for the device.
      */
     @VisibleForTesting
-    void updateDatabase(boolean isIncrementalUpdate, String localeStr) {
+    void updateDatabase(boolean needsReindexing, String localeStr) {
         mIsAvailable.set(false);
         final UpdateData copy;
 
@@ -236,7 +256,7 @@
 
             // Only check for non-indexable key updates after initial index.
             // Enabled state with non-indexable keys is checked when items are first inserted.
-            if (isIncrementalUpdate) {
+            if (!needsReindexing) {
                 updateDataInDatabase(database, nonIndexableKeys);
             }
 
@@ -284,7 +304,7 @@
      * @param database The database to validate.
      * @param nonIndexableKeys A map between package name and the set of non-indexable keys for it.
      */
-    @VisibleForTesting(otherwise = VisibleForTesting.PRIVATE)
+    @VisibleForTesting
     void updateDataInDatabase(SQLiteDatabase database,
             Map<String, Set<String>> nonIndexableKeys) {
         final String whereEnabled = ENABLED + " = 1";
@@ -348,7 +368,6 @@
     @VisibleForTesting
     boolean addIndexablesFromRemoteProvider(String packageName, String authority) {
         try {
-
             final Context context = mBaseAuthority.equals(authority) ?
                     mContext : mContext.createPackageContext(packageName, 0);
 
diff --git a/tests/robotests/src/com/android/settings/search2/DatabaseIndexingManagerTest.java b/tests/robotests/src/com/android/settings/search2/DatabaseIndexingManagerTest.java
index 327b910..aa4e4f9 100644
--- a/tests/robotests/src/com/android/settings/search2/DatabaseIndexingManagerTest.java
+++ b/tests/robotests/src/com/android/settings/search2/DatabaseIndexingManagerTest.java
@@ -30,6 +30,8 @@
 import android.database.MatrixCursor;
 import android.database.sqlite.SQLiteDatabase;
 import android.net.Uri;
+import android.os.Build;
+import android.provider.SearchIndexableData;
 import android.provider.SearchIndexableResource;
 import android.provider.SearchIndexablesContract;
 import android.util.ArrayMap;
@@ -74,7 +76,7 @@
 
 @RunWith(SettingsRobolectricTestRunner.class)
 @Config(manifest = TestConfig.MANIFEST_PATH, sdk = TestConfig.SDK_VERSION,
-        shadows={ShadowRunnableAsyncTask.class})
+        shadows = {ShadowRunnableAsyncTask.class})
 public class DatabaseIndexingManagerTest {
     private final String localeStr = "en_US";
 
@@ -122,7 +124,7 @@
     public void setUp() {
         MockitoAnnotations.initMocks(this);
         mContext = spy(RuntimeEnvironment.application);
-        mManager = spy(new DatabaseIndexingManager(mContext,"com.android.settings"));
+        mManager = spy(new DatabaseIndexingManager(mContext, PACKAGE_ONE));
         mDb = IndexDatabaseHelper.getInstance(mContext).getWritableDatabase();
 
         doReturn(mPackageManager).when(mContext).getPackageManager();
@@ -671,42 +673,95 @@
     // Test new public indexing flow
 
     @Test
-    @Config(shadows= {
-            ShadowDatabaseIndexingUtils.class,
-    })
+    @Config(shadows = {ShadowDatabaseIndexingUtils.class,})
     public void testPerformIndexing_fullIndex_getsDataFromProviders() {
         DummyProvider provider = new DummyProvider();
         provider.onCreate();
-        ShadowContentResolver.registerProvider(
-                AUTHORITY_ONE, provider
-        );
+        ShadowContentResolver.registerProvider(AUTHORITY_ONE, provider);
 
         // Test that Indexables are added for Full indexing
         when(mPackageManager.queryIntentContentProviders(any(Intent.class), anyInt()))
                 .thenReturn(getDummyResolveInfo());
 
         DatabaseIndexingManager manager =
-                spy(new DatabaseIndexingManager(mContext, "com.android.settings"));
-        doReturn(false).when(manager).isLocaleIndexed();
+                spy(new DatabaseIndexingManager(mContext, PACKAGE_ONE));
+        doReturn(true).when(manager).isFullIndex(anyString(), anyString());
 
         manager.performIndexing();
 
-        verify(manager).updateDatabase(false, Locale.getDefault().toString());
-
-        Cursor cursor = mDb.rawQuery("SELECT * FROM prefs_index", null);
-        cursor.moveToPosition(0);
-
-        // Data Title
-        assertThat(cursor.getString(2)).isEqualTo(TITLE_ONE);
+        verify(manager).addIndexablesFromRemoteProvider(PACKAGE_ONE, AUTHORITY_ONE);
+        verify(manager).updateDatabase(true /* isFullIndex */, Locale.getDefault().toString());
     }
 
     @Test
-    @Config(shadows= {
-            ShadowDatabaseIndexingUtils.class,
-    })
+    @Config(shadows = {ShadowDatabaseIndexingUtils.class,})
     public void testPerformIndexing_incrementalIndex_noDataAdded() {
         DummyProvider provider = new DummyProvider();
         provider.onCreate();
+        ShadowContentResolver.registerProvider(AUTHORITY_ONE, provider);
+
+        // Test that Indexables are added for Full indexing
+        when(mPackageManager.queryIntentContentProviders(any(Intent.class), anyInt()))
+                .thenReturn(getDummyResolveInfo());
+
+        DatabaseIndexingManager manager =
+                spy(new DatabaseIndexingManager(mContext, PACKAGE_ONE));
+        doReturn(false).when(manager).isFullIndex(anyString(), anyString());
+
+        manager.mDataToProcess.dataToUpdate.clear();
+
+        manager.performIndexing();
+
+        verify(manager, times(0)).addDataToDatabase(any(SQLiteDatabase.class), anyString(),
+                anyList(), anyMap());
+        verify(manager, times(0)).addIndexablesFromRemoteProvider(PACKAGE_ONE, AUTHORITY_ONE);
+        verify(manager).updateDataInDatabase(any(SQLiteDatabase.class), anyMap());
+    }
+
+    @Test
+    @Config(shadows = {ShadowDatabaseIndexingUtils.class,})
+    public void testPerformIndexing_localeChanged_databaseDropped() {
+        DummyProvider provider = new DummyProvider();
+        provider.onCreate();
+        ShadowContentResolver.registerProvider(AUTHORITY_ONE, provider);
+
+        // Test that Indexables are added for Full indexing
+        when(mPackageManager.queryIntentContentProviders(any(Intent.class), anyInt()))
+                .thenReturn(getDummyResolveInfo());
+
+        // Initialize the Manager
+        DatabaseIndexingManager manager =
+                spy(new DatabaseIndexingManager(mContext, PACKAGE_ONE));
+        doReturn(true).when(manager).isFullIndex(anyString(), anyString());
+
+        // Insert data point which will be dropped
+        final String oldTitle = "This is French";
+        insertSpecialCase(oldTitle, true, "key");
+
+        // Add a data point to be added by the indexing
+        SearchIndexableRaw raw = new SearchIndexableRaw(mContext);
+        final String newTitle = "This is English";
+        raw.title = newTitle;
+        manager.mDataToProcess.dataToUpdate.add(raw);
+
+        manager.performIndexing();
+
+        // Assert that the New Title is inserted
+        final Cursor newCursor = mDb.rawQuery("SELECT * FROM prefs_index WHERE data_title = '" +
+                newTitle + "'", null);
+        assertThat(newCursor.getCount()).isEqualTo(1);
+
+        // Assert that the Old Title is no longer in the database, since it was dropped
+        final Cursor oldCursor = mDb.rawQuery("SELECT * FROM prefs_index WHERE data_title = '" +
+                oldTitle + "'", null);
+        assertThat(oldCursor.getCount()).isEqualTo(0);
+    }
+
+    @Test
+    @Config(shadows = {ShadowDatabaseIndexingUtils.class,})
+    public void testPerformIndexing_onOta_FullIndex() {
+        DummyProvider provider = new DummyProvider();
+        provider.onCreate();
         ShadowContentResolver.registerProvider(
                 AUTHORITY_ONE, provider
         );
@@ -716,19 +771,40 @@
                 .thenReturn(getDummyResolveInfo());
 
         DatabaseIndexingManager manager =
-                spy(new DatabaseIndexingManager(mContext, "com.android.settings"));
-        doReturn(true).when(manager).isLocaleIndexed();
+                spy(new DatabaseIndexingManager(mContext, PACKAGE_ONE));
+        doReturn(true).when(manager).isFullIndex(anyString(), anyString());
 
         manager.performIndexing();
 
-        final Cursor cursor = mDb.rawQuery("SELECT * FROM prefs_index", null);
+        verify(manager).updateDatabase(true /* isFullIndex */, Locale.getDefault().toString());
+    }
 
-        assertThat(cursor.getCount()).isEqualTo(0);
+    @Test
+    @Config(shadows = {ShadowDatabaseIndexingUtils.class,})
+    public void testPerformIndexing_onOta_buildNumberIsCached() {
+        DummyProvider provider = new DummyProvider();
+        provider.onCreate();
+        ShadowContentResolver.registerProvider(
+                AUTHORITY_ONE, provider
+        );
+
+        // Test that Indexables are added for Full indexing
+        when(mPackageManager.queryIntentContentProviders(any(Intent.class), anyInt()))
+                .thenReturn(getDummyResolveInfo());
+
+        DatabaseIndexingManager manager =
+                spy(new DatabaseIndexingManager(mContext, PACKAGE_ONE));
+        doReturn(true).when(manager).isFullIndex(anyString(), anyString());
+
+        manager.performIndexing();
+
+        assertThat(IndexDatabaseHelper.getInstance(mContext).isBuildIndexed(mContext,
+                Build.FINGERPRINT)).isTrue();
     }
 
     @Test
     public void testFullUpdatedDatabase_noData_addDataToDatabaseNotCalled() {
-        mManager.updateDatabase(false, localeStr);
+        mManager.updateDatabase(true /* isFullIndex */, localeStr);
         mManager.mDataToProcess.dataToUpdate.clear();
         verify(mManager, times(0)).addDataToDatabase(any(SQLiteDatabase.class), anyString(),
                 anyList(), anyMap());
@@ -736,13 +812,13 @@
 
     @Test
     public void testFullUpdatedDatabase_updatedDataInDatabaseNotCalled() {
-        mManager.updateDatabase(false, localeStr);
+        mManager.updateDatabase(true /* isFullIndex */, localeStr);
         verify(mManager, times(0)).updateDataInDatabase(any(SQLiteDatabase.class), anyMap());
     }
 
     @Test
     public void testLocaleUpdated_afterIndexing_localeNotAdded() {
-        mManager.updateDatabase(false, localeStr);
+        mManager.updateDatabase(true /* isFullIndex */, localeStr);
         assertThat(IndexDatabaseHelper.getInstance(mContext)
                 .isLocaleAlreadyIndexed(mContext, localeStr)).isFalse();
     }
@@ -758,7 +834,7 @@
     public void testUpdateDatabase_newEligibleData_addedToDatabase() {
         // Test that addDataToDatabase is called when dataToUpdate is non-empty
         mManager.mDataToProcess.dataToUpdate.add(getFakeRaw());
-        mManager.updateDatabase(false, localeStr);
+        mManager.updateDatabase(true /* isFullIndex */, localeStr);
 
         Cursor cursor = mDb.rawQuery("SELECT * FROM prefs_index", null);
         cursor.moveToPosition(0);