diff --git a/src/com/android/settings/search/DeviceIndexFeatureProvider.java b/src/com/android/settings/search/DeviceIndexFeatureProvider.java
index bf75ee8..1c25399 100644
--- a/src/com/android/settings/search/DeviceIndexFeatureProvider.java
+++ b/src/com/android/settings/search/DeviceIndexFeatureProvider.java
@@ -31,6 +31,7 @@
 import com.android.settings.slices.SettingsSliceProvider;
 
 import java.util.List;
+import java.util.Locale;
 import java.util.Objects;
 
 public interface DeviceIndexFeatureProvider {
@@ -39,15 +40,21 @@
     String TAG = "DeviceIndex";
 
     String INDEX_VERSION = "settings:index_version";
+    String INDEX_LANGUAGE = "settings:language";
 
     // Increment when new items are added to ensure they get pushed to the device index.
     String VERSION = Build.FINGERPRINT;
 
+    // When the device language changes, re-index so Slices trigger in device language.
+    Locale LANGUAGE = Locale.getDefault();
+
     boolean isIndexingEnabled();
 
     void index(Context context, CharSequence title, Uri sliceUri, Uri launchUri,
             List<String> keywords);
 
+    void clearIndex(Context context);
+
     default void updateIndex(Context context, boolean force) {
         if (!isIndexingEnabled()) {
             Log.w(TAG, "Skipping: device index is not enabled");
@@ -59,12 +66,14 @@
             return;
         }
 
-        if (!force && Objects.equals(
-                Settings.Secure.getString(context.getContentResolver(), INDEX_VERSION), VERSION)) {
+        if (!force && skipIndex(context)) {
             // No need to update.
             return;
         }
 
+        // Prevent scheduling multiple jobs
+        setIndexState(context);
+
         final ComponentName jobComponent = new ComponentName(context.getPackageName(),
                 DeviceIndexUpdateJobService.class.getName());
         final int jobId = context.getResources().getInteger(R.integer.device_index_update);
@@ -77,7 +86,6 @@
                         .setOverrideDeadline(1)
                         .build());
 
-        Settings.Secure.putString(context.getContentResolver(), INDEX_VERSION, VERSION);
     }
 
     static Uri createDeepLink(String s) {
@@ -86,4 +94,18 @@
                 .appendQueryParameter(INTENT, s)
                 .build();
     }
+
+    static boolean skipIndex(Context context) {
+        final boolean isSameVersion = Objects.equals(
+                Settings.Secure.getString(context.getContentResolver(), INDEX_VERSION), VERSION);
+        final boolean isSameLanguage = Objects.equals(
+                Settings.Secure.getString(context.getContentResolver(), INDEX_LANGUAGE), LANGUAGE);
+        return isSameLanguage && isSameVersion;
+    }
+
+    static void setIndexState(Context context) {
+        Settings.Secure.putString(context.getContentResolver(), INDEX_VERSION, VERSION);
+        Settings.Secure.putString(context.getContentResolver(), INDEX_LANGUAGE,
+                LANGUAGE.toString());
+    }
 }
diff --git a/src/com/android/settings/search/DeviceIndexFeatureProviderImpl.java b/src/com/android/settings/search/DeviceIndexFeatureProviderImpl.java
index 7a11bd4..087ecf8 100644
--- a/src/com/android/settings/search/DeviceIndexFeatureProviderImpl.java
+++ b/src/com/android/settings/search/DeviceIndexFeatureProviderImpl.java
@@ -31,4 +31,9 @@
             List<String> keywords) {
         // Not enabled by default.
     }
+
+    @Override
+    public void clearIndex(Context context) {
+        // Not enabled by default.
+    }
 }
diff --git a/src/com/android/settings/search/DeviceIndexUpdateJobService.java b/src/com/android/settings/search/DeviceIndexUpdateJobService.java
index 19b7d5e..97b0a61 100644
--- a/src/com/android/settings/search/DeviceIndexUpdateJobService.java
+++ b/src/com/android/settings/search/DeviceIndexUpdateJobService.java
@@ -25,6 +25,7 @@
 import android.content.Intent;
 import android.net.Uri;
 import android.net.Uri.Builder;
+import android.provider.SettingsSlicesContract;
 import android.util.Log;
 
 import com.android.internal.annotations.VisibleForTesting;
@@ -84,11 +85,19 @@
                 .scheme(ContentResolver.SCHEME_CONTENT)
                 .authority(SettingsSliceProvider.SLICE_AUTHORITY)
                 .build();
+        final Uri platformBaseUri = new Builder()
+                .scheme(ContentResolver.SCHEME_CONTENT)
+                .authority(SettingsSlicesContract.AUTHORITY)
+                .build();
         final Collection<Uri> slices = manager.getSliceDescendants(baseUri);
+        slices.addAll(manager.getSliceDescendants(platformBaseUri));
+
         if (DEBUG) {
             Log.d(TAG, "Indexing " + slices.size() + " slices");
         }
 
+        indexProvider.clearIndex(this /* context */);
+
         for (Uri slice : slices) {
             if (!mRunningJob) {
                 return;
diff --git a/tests/robotests/src/com/android/settings/search/DeviceIndexFeatureProviderTest.java b/tests/robotests/src/com/android/settings/search/DeviceIndexFeatureProviderTest.java
index d4c1580..a900db0 100644
--- a/tests/robotests/src/com/android/settings/search/DeviceIndexFeatureProviderTest.java
+++ b/tests/robotests/src/com/android/settings/search/DeviceIndexFeatureProviderTest.java
@@ -23,6 +23,7 @@
 
 import android.app.Activity;
 import android.app.job.JobScheduler;
+import android.os.Build;
 import android.provider.Settings;
 
 import com.android.settings.testutils.FakeFeatureFactory;
@@ -76,4 +77,51 @@
         mProvider.updateIndex(mActivity, false);
         verify(jobScheduler).schedule(any());
     }
+
+    @Test
+    public void updateIndex_enabled_provisioned_newBuild_shouldIndex() {
+        Settings.Global.putInt(mActivity.getContentResolver(),
+                Settings.Global.DEVICE_PROVISIONED, 1);
+        DeviceIndexFeatureProvider.setIndexState(mActivity);
+        Settings.Global.putString(mActivity.getContentResolver(),
+                DeviceIndexFeatureProvider.INDEX_VERSION, "new version");
+        Settings.Global.putString(mActivity.getContentResolver(),
+                DeviceIndexFeatureProvider.LANGUAGE.toString(),
+                DeviceIndexFeatureProvider.INDEX_LANGUAGE);
+        JobScheduler jobScheduler = mock(JobScheduler.class);
+        when(mProvider.isIndexingEnabled()).thenReturn(true);
+        when(mActivity.getSystemService(JobScheduler.class)).thenReturn(jobScheduler);
+
+        mProvider.updateIndex(mActivity, false);
+        verify(jobScheduler).schedule(any());
+    }
+
+    @Test
+    public void updateIndex_enabled_provisioned_newIndex_shouldIndex() {
+        Settings.Global.putInt(mActivity.getContentResolver(),
+                Settings.Global.DEVICE_PROVISIONED, 1);
+        DeviceIndexFeatureProvider.setIndexState(mActivity);
+        Settings.Global.putString(mActivity.getContentResolver(),
+                DeviceIndexFeatureProvider.INDEX_LANGUAGE, "new language");
+        JobScheduler jobScheduler = mock(JobScheduler.class);
+        when(mProvider.isIndexingEnabled()).thenReturn(true);
+        when(mActivity.getSystemService(JobScheduler.class)).thenReturn(jobScheduler);
+
+        mProvider.updateIndex(mActivity, false);
+        verify(jobScheduler).schedule(any());
+    }
+
+    @Test
+    public void updateIndex_enabled_provisioned_sameBuild_sameLang_shouldNotIndex() {
+        Settings.Global.putInt(mActivity.getContentResolver(),
+                Settings.Global.DEVICE_PROVISIONED, 1);
+        DeviceIndexFeatureProvider.setIndexState(mActivity);
+        JobScheduler jobScheduler = mock(JobScheduler.class);
+        when(mProvider.isIndexingEnabled()).thenReturn(true);
+        when(mActivity.getSystemService(JobScheduler.class)).thenReturn(jobScheduler);
+
+        mProvider.updateIndex(mActivity, false);
+
+        verify(mProvider, never()).index(any(), any(), any(), any(), any());
+    }
 }
diff --git a/tests/robotests/src/com/android/settings/search/DeviceIndexUpdateJobServiceTest.java b/tests/robotests/src/com/android/settings/search/DeviceIndexUpdateJobServiceTest.java
index ec16893..b5de973 100644
--- a/tests/robotests/src/com/android/settings/search/DeviceIndexUpdateJobServiceTest.java
+++ b/tests/robotests/src/com/android/settings/search/DeviceIndexUpdateJobServiceTest.java
@@ -124,6 +124,7 @@
 
         DeviceIndexFeatureProvider indexFeatureProvider = FakeFeatureFactory.getFactory(mActivity)
                 .getDeviceIndexFeatureProvider();
+        verify(indexFeatureProvider).clearIndex(any());
         verify(indexFeatureProvider, times(1)).index(any(), any(), any(), any(), any());
     }