diff --git a/Documentation/user-search.txt b/Documentation/user-search.txt
index 565c491..e12c27c 100644
--- a/Documentation/user-search.txt
+++ b/Documentation/user-search.txt
@@ -43,6 +43,17 @@
 For more predictable results, use explicit search operators as described
 in the following section.
 
+[IMPORTANT]
+--
+The change search API is backed by a secondary index and might sometimes return
+stale results if the re-indexing operation failed for a change update.
+
+Please also note that changes are not re-indexed if the project configuration
+is updated with newly added or modified
+link:config-submit-requirements.html[submit requirements].
+--
+
+
 [[search-operators]]
 == Search Operators
 
diff --git a/java/com/google/gerrit/server/project/ProjectCacheImpl.java b/java/com/google/gerrit/server/project/ProjectCacheImpl.java
index 0afaa3f..6498d1b 100644
--- a/java/com/google/gerrit/server/project/ProjectCacheImpl.java
+++ b/java/com/google/gerrit/server/project/ProjectCacheImpl.java
@@ -76,7 +76,6 @@
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.locks.Lock;
 import java.util.concurrent.locks.ReentrantLock;
-import java.util.stream.Stream;
 import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.eclipse.jgit.errors.RepositoryNotFoundException;
 import org.eclipse.jgit.lib.Config;
@@ -301,20 +300,19 @@
   @Override
   public Set<AccountGroup.UUID> guessRelevantGroupUUIDs() {
     try (Timer0.Context ignored = guessRelevantGroupsLatency.start()) {
-      Stream<AccountGroup.UUID> configuredRelevantGroups =
-          Arrays.stream(config.getStringList("groups", /* subsection= */ null, "relevantGroup"))
-              .map(AccountGroup::uuid);
-
-      Stream<AccountGroup.UUID> guessedRelevantGroups =
-          inMemoryProjectCache.asMap().values().stream()
-              .filter(Objects::nonNull)
-              .flatMap(p -> p.getAllGroupUUIDs().stream())
-              // getAllGroupUUIDs shouldn't really return null UUIDs, but harden
-              // against them just in case there is a bug or corner case.
-              .filter(id -> id != null && id.get() != null);
-
       Set<AccountGroup.UUID> relevantGroupUuids =
-          Streams.concat(configuredRelevantGroups, guessedRelevantGroups).collect(toSet());
+          Streams.concat(
+                  Arrays.stream(
+                          config.getStringList("groups", /* subsection= */ null, "relevantGroup"))
+                      .map(AccountGroup::uuid),
+                  all().stream()
+                      .map(n -> inMemoryProjectCache.getIfPresent(n))
+                      .filter(Objects::nonNull)
+                      .flatMap(p -> p.getAllGroupUUIDs().stream())
+                      // getAllGroupUUIDs shouldn't really return null UUIDs, but harden
+                      // against them just in case there is a bug or corner case.
+                      .filter(id -> id != null && id.get() != null))
+              .collect(toSet());
       logger.atFine().log("relevant group UUIDs: %s", relevantGroupUuids);
       return relevantGroupUuids;
     }
diff --git a/polygerrit-ui/app/utils/attention-set-util.ts b/polygerrit-ui/app/utils/attention-set-util.ts
index 77834bd..4404e59 100644
--- a/polygerrit-ui/app/utils/attention-set-util.ts
+++ b/polygerrit-ui/app/utils/attention-set-util.ts
@@ -3,7 +3,12 @@
  * Copyright 2020 Google LLC
  * SPDX-License-Identifier: Apache-2.0
  */
-import {AccountInfo, ChangeInfo, ServerInfo} from '../types/common';
+import {
+  AccountInfo,
+  ChangeInfo,
+  DetailedLabelInfo,
+  ServerInfo,
+} from '../types/common';
 import {ParsedChangeInfo} from '../types/types';
 import {
   getAccountTemplate,
@@ -13,6 +18,7 @@
 } from './account-util';
 import {CommentThread, isMentionedThread, isUnresolved} from './comment-util';
 import {hasOwnProperty} from './common-util';
+import {getCodeReviewLabel} from './label-util';
 
 export function canHaveAttention(account?: AccountInfo): boolean {
   return !!account?._account_id && !isServiceUser(account);
@@ -101,9 +107,10 @@
 /**
  *  Sort order:
  * 1. The user themselves
- * 2. Human users in the attention set.
- * 3. Other human users.
- * 4. Service users.
+ * 2. Users in the attention set first.
+ * 3. Human users first.
+ * 4. Users that have voted first in this order of vote values:
+ *    -2, -1, +2, +1, 0 or no vote.
  */
 export function sortReviewers(
   r1: AccountInfo,
@@ -117,7 +124,22 @@
   }
   const a1 = hasAttention(r1, change) ? 1 : 0;
   const a2 = hasAttention(r2, change) ? 1 : 0;
-  const s1 = isServiceUser(r1) ? -2 : 0;
-  const s2 = isServiceUser(r2) ? -2 : 0;
-  return a2 - a1 + s2 - s1;
+  if (a2 - a1 !== 0) return a2 - a1;
+
+  const s1 = isServiceUser(r1) ? -1 : 0;
+  const s2 = isServiceUser(r2) ? -1 : 0;
+  if (s2 - s1 !== 0) return s2 - s1;
+
+  const crLabel = getCodeReviewLabel(change?.labels ?? {}) as DetailedLabelInfo;
+  let v1 =
+    crLabel?.all?.find(vote => vote._account_id === r1._account_id)?.value ?? 0;
+  let v2 =
+    crLabel?.all?.find(vote => vote._account_id === r2._account_id)?.value ?? 0;
+  // We want negative votes getting a higher score than positive votes, so
+  // we choose 10 as a random number that is higher than all positive votes that
+  // are in use, and then add the absolute value of the vote to that.
+  // So -2 becomes 12.
+  if (v1 < 0) v1 = 10 - v1;
+  if (v2 < 0) v2 = 10 - v2;
+  return v2 - v1;
 }
diff --git a/polygerrit-ui/app/utils/attention-set-util_test.ts b/polygerrit-ui/app/utils/attention-set-util_test.ts
index 8092a6e..5bd1924 100644
--- a/polygerrit-ui/app/utils/attention-set-util_test.ts
+++ b/polygerrit-ui/app/utils/attention-set-util_test.ts
@@ -6,9 +6,11 @@
 import '../test/common-test-setup';
 import {
   createAccountDetailWithIdNameAndEmail,
+  createAccountWithId,
   createChange,
   createComment,
   createCommentThread,
+  createParsedChange,
   createServerInfo,
 } from '../test/test-data-generators';
 import {
@@ -22,9 +24,10 @@
   getMentionedReason,
   getReason,
   hasAttention,
+  sortReviewers,
 } from './attention-set-util';
 import {DefaultDisplayNameConfig} from '../api/rest-api';
-import {AccountsVisibility} from '../constants/constants';
+import {AccountsVisibility, AccountTag} from '../constants/constants';
 import {assert} from '@open-wc/testing';
 
 const KERMIT: AccountInfo = {
@@ -101,6 +104,45 @@
     assert.equal(getReason(config, OTHER_ACCOUNT, change), 'Added by kermit');
   });
 
+  test('sortReviewers', () => {
+    const a1 = createAccountWithId(1);
+    a1.tags = [AccountTag.SERVICE_USER];
+    const a2 = createAccountWithId(2);
+    a2.tags = [AccountTag.SERVICE_USER];
+    const a3 = createAccountWithId(3);
+    const a4 = createAccountWithId(4);
+    const a5 = createAccountWithId(5);
+    const a6 = createAccountWithId(6);
+    const a7 = createAccountWithId(7);
+
+    const reviewers = [a1, a2, a3, a4, a5, a6, a7];
+    const change = {
+      ...createParsedChange(),
+      attention_set: {'6': {account: a6}},
+      labels: {
+        'Code-Review': {
+          all: [
+            {...a2, value: 1},
+            {...a4, value: 1},
+            {...a5, value: -1},
+          ],
+        },
+      },
+    };
+    assert.sameOrderedMembers(
+      reviewers.sort((r1, r2) => sortReviewers(r1, r2, change, a7)),
+      [
+        a7, // self
+        a6, // is in the attention set
+        a5, // human user, has voted -1
+        a4, // human user, has voted +1
+        a3, // human user, has not voted
+        a2, // service user, has voted
+        a1, // service user, has not voted
+      ]
+    );
+  });
+
   test('getMentionReason', () => {
     let comment = {
       ...createComment(),