diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java
index 7940219..d7b9342 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java
@@ -38,6 +38,7 @@
 import org.slf4j.LoggerFactory;
 
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
 import java.util.concurrent.atomic.AtomicBoolean;
@@ -106,7 +107,7 @@
     try {
       try (ReviewDb db = schema.open()) {
         AccountExternalId.Key key = id(who);
-        AccountExternalId id = db.accountExternalIds().get(key);
+        AccountExternalId id = getAccountExternalId(db, key);
         if (id == null) {
           // New account, automatically create and return.
           //
@@ -130,6 +131,32 @@
     }
   }
 
+  private AccountExternalId getAccountExternalId(ReviewDb db,
+      AccountExternalId.Key key) throws OrmException {
+    String keyValue = key.get();
+    String keyScheme = keyValue.substring(0, keyValue.indexOf(':') + 1);
+
+    // We don't have at the moment an account_by_external_id cache
+    // but by using the accounts cache we get the list of external_ids
+    // without having to query the DB every time
+    if (keyScheme.equals(AccountExternalId.SCHEME_GERRIT)
+        || keyScheme.equals(AccountExternalId.SCHEME_USERNAME)) {
+      String username = keyValue.substring(keyScheme.length());
+      Collection<AccountExternalId> externalIds =
+          byIdCache.getByUsername(username).getExternalIds();
+      for (AccountExternalId accountExternalId : externalIds) {
+        if (accountExternalId.isScheme(keyScheme)) {
+          return accountExternalId;
+        }
+      }
+
+      log.warn(
+          "Cannot find account external id for user {} in cache, possibly a stale entry",
+          username);
+    }
+    return db.accountExternalIds().get(key);
+  }
+
   private void update(ReviewDb db, AuthRequest who, AccountExternalId extId)
       throws OrmException, NameAlreadyUsedException, InvalidUserNameException {
     IdentifiedUser user = userFactory.create(extId.getAccountId());
@@ -324,7 +351,7 @@
       who = realm.link(db, to, who);
 
       AccountExternalId.Key key = id(who);
-      AccountExternalId extId = db.accountExternalIds().get(key);
+      AccountExternalId extId = getAccountExternalId(db, key);
       if (extId != null) {
         if (!extId.getAccountId().equals(to)) {
           throw new AccountException("Identity in use by another account");
@@ -415,7 +442,7 @@
       who = realm.unlink(db, from, who);
 
       AccountExternalId.Key key = id(who);
-      AccountExternalId extId = db.accountExternalIds().get(key);
+      AccountExternalId extId = getAccountExternalId(db, key);
       if (extId != null) {
         if (!extId.getAccountId().equals(from)) {
           throw new AccountException("Identity in use by another account");