diff --git a/mercurial/debugcommands.py b/mercurial/debugcommands.py
--- a/mercurial/debugcommands.py
+++ b/mercurial/debugcommands.py
@@ -794,7 +794,7 @@
                 cl = repo.changelog
                 clnode = cl.node
                 dag = dagutil.revlogdag(cl)
-                all = dag.ancestorset(dag.internalizeall(common))
+                all = dag.ancestorset(cl.rev(n) for n in common)
                 common = {clnode(r) for r in dag.headsetofconnecteds(all)}
         else:
             nodes = None
diff --git a/mercurial/setdiscovery.py b/mercurial/setdiscovery.py
--- a/mercurial/setdiscovery.py
+++ b/mercurial/setdiscovery.py
@@ -143,11 +143,11 @@
     roundtrips = 0
     cl = local.changelog
     clnode = cl.node
+    clrev = cl.rev
     localsubset = None
 
     if ancestorsof is not None:
-        rev = local.changelog.rev
-        localsubset = [rev(n) for n in ancestorsof]
+        localsubset = [clrev(n) for n in ancestorsof]
     dag = dagutil.revlogdag(cl, localsubset=localsubset)
 
     # early exit if we know all the specified remote heads already
@@ -175,7 +175,17 @@
     # compatibility reasons)
     ui.status(_("searching for changes\n"))
 
-    srvheads = dag.internalizeall(srvheadhashes, filterunknown=True)
+    srvheads = []
+    for node in srvheadhashes:
+        if node == nullid:
+            continue
+
+        try:
+            srvheads.append(clrev(node))
+        # Catches unknown and filtered nodes.
+        except error.LookupError:
+            continue
+
     if len(srvheads) == len(srvheadhashes):
         ui.debug("all remote heads known locally\n")
         return srvheadhashes, False, srvheadhashes