diff --git a/java/com/google/gerrit/server/account/Emails.java b/java/com/google/gerrit/server/account/Emails.java
index 14f279b..1d53ed2 100644
--- a/java/com/google/gerrit/server/account/Emails.java
+++ b/java/com/google/gerrit/server/account/Emails.java
@@ -14,12 +14,14 @@
 
 package com.google.gerrit.server.account;
 
+import static com.google.common.collect.ImmutableList.toImmutableList;
 import static com.google.common.collect.ImmutableSet.toImmutableSet;
 
 import com.google.common.base.Throwables;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.ImmutableSetMultimap;
-import com.google.common.collect.Streams;
+import com.google.common.collect.MultimapBuilder;
+import com.google.common.collect.SetMultimap;
 import com.google.gerrit.exceptions.StorageException;
 import com.google.gerrit.reviewdb.client.Account;
 import com.google.gerrit.server.account.externalids.ExternalId;
@@ -32,6 +34,8 @@
 import com.google.inject.Provider;
 import com.google.inject.Singleton;
 import java.io.IOException;
+import java.util.Arrays;
+import java.util.List;
 
 /** Class to access accounts by email. */
 @Singleton
@@ -65,15 +69,20 @@
    * have no external ID for the preferred email. Having accounts with a preferred email that does
    * not exist as external ID is an inconsistency, but existing functionality relies on still
    * getting those accounts, which is why they are included. Accounts by preferred email are fetched
-   * from the account index.
+   * from the account index as a fallback for email addresses that could not be resolved using
+   * {@link ExternalIds}.
    *
    * @see #getAccountsFor(String...)
    */
   public ImmutableSet<Account.Id> getAccountFor(String email) throws IOException {
-    return Streams.concat(
-            externalIds.byEmail(email).stream().map(ExternalId::accountId),
-            executeIndexQuery(() -> queryProvider.get().byPreferredEmail(email).stream())
-                .map(a -> a.getAccount().id()))
+    ImmutableSet<Account.Id> accounts =
+        externalIds.byEmail(email).stream().map(ExternalId::accountId).collect(toImmutableSet());
+    if (!accounts.isEmpty()) {
+      return accounts;
+    }
+
+    return executeIndexQuery(() -> queryProvider.get().byPreferredEmail(email).stream())
+        .map(a -> a.getAccount().id())
         .collect(toImmutableSet());
   }
 
@@ -84,12 +93,18 @@
    */
   public ImmutableSetMultimap<String, Account.Id> getAccountsFor(String... emails)
       throws IOException {
-    ImmutableSetMultimap.Builder<String, Account.Id> builder = ImmutableSetMultimap.builder();
+    SetMultimap<String, Account.Id> result =
+        MultimapBuilder.hashKeys(emails.length).hashSetValues(1).build();
     externalIds.byEmails(emails).entries().stream()
-        .forEach(e -> builder.put(e.getKey(), e.getValue().accountId()));
-    executeIndexQuery(() -> queryProvider.get().byPreferredEmail(emails).entries().stream())
-        .forEach(e -> builder.put(e.getKey(), e.getValue().getAccount().id()));
-    return builder.build();
+        .forEach(e -> result.put(e.getKey(), e.getValue().accountId()));
+    List<String> emailsToBackfill =
+        Arrays.stream(emails).filter(e -> !result.containsKey(e)).collect(toImmutableList());
+    if (!emailsToBackfill.isEmpty()) {
+      executeIndexQuery(
+              () -> queryProvider.get().byPreferredEmail(emailsToBackfill).entries().stream())
+          .forEach(e -> result.put(e.getKey(), e.getValue().getAccount().id()));
+    }
+    return ImmutableSetMultimap.copyOf(result);
   }
 
   /**
diff --git a/java/com/google/gerrit/server/query/account/InternalAccountQuery.java b/java/com/google/gerrit/server/query/account/InternalAccountQuery.java
index 0253ede..c38c92f 100644
--- a/java/com/google/gerrit/server/query/account/InternalAccountQuery.java
+++ b/java/com/google/gerrit/server/query/account/InternalAccountQuery.java
@@ -31,7 +31,6 @@
 import com.google.gerrit.server.index.account.AccountField;
 import com.google.gerrit.server.index.account.AccountIndexCollection;
 import com.google.inject.Inject;
-import java.util.Arrays;
 import java.util.List;
 import java.util.Set;
 
@@ -93,15 +92,13 @@
    * @return multimap of the given emails to accounts that have a preferred email that exactly
    *     matches this email
    */
-  public Multimap<String, AccountState> byPreferredEmail(String... emails) {
-    List<String> emailList = Arrays.asList(emails);
-
+  public Multimap<String, AccountState> byPreferredEmail(List<String> emails) {
     if (hasPreferredEmailExact()) {
       List<List<AccountState>> r =
-          query(emailList.stream().map(AccountPredicates::preferredEmailExact).collect(toList()));
+          query(emails.stream().map(AccountPredicates::preferredEmailExact).collect(toList()));
       Multimap<String, AccountState> accountsByEmail = ArrayListMultimap.create();
-      for (int i = 0; i < emailList.size(); i++) {
-        accountsByEmail.putAll(emailList.get(i), r.get(i));
+      for (int i = 0; i < emails.size(); i++) {
+        accountsByEmail.putAll(emails.get(i), r.get(i));
       }
       return accountsByEmail;
     }
@@ -111,10 +108,10 @@
     }
 
     List<List<AccountState>> r =
-        query(emailList.stream().map(AccountPredicates::preferredEmail).collect(toList()));
+        query(emails.stream().map(AccountPredicates::preferredEmail).collect(toList()));
     Multimap<String, AccountState> accountsByEmail = ArrayListMultimap.create();
-    for (int i = 0; i < emailList.size(); i++) {
-      String email = emailList.get(i);
+    for (int i = 0; i < emails.size(); i++) {
+      String email = emails.get(i);
       Set<AccountState> matchingAccounts =
           r.get(i).stream()
               .filter(a -> a.getAccount().preferredEmail().equals(email))