diff --git a/hgext/transplant.py b/hgext/transplant.py
--- a/hgext/transplant.py
+++ b/hgext/transplant.py
@@ -548,8 +548,8 @@ def transplant(ui, repo, *revs, **opts):
     if source:
         sourcerepo = ui.expandpath(source)
         source = hg.repository(ui, sourcerepo)
-        source, incoming, bundle = bundlerepo.getremotechanges(ui, repo, source,
-                                    force=True)
+        source, common, incoming, bundle = bundlerepo.getremotechanges(ui, repo,
+                                            source, force=True)
     else:
         source = repo
 
diff --git a/mercurial/bundlerepo.py b/mercurial/bundlerepo.py
--- a/mercurial/bundlerepo.py
+++ b/mercurial/bundlerepo.py
@@ -286,15 +286,17 @@ def instance(ui, path, create):
         repopath, bundlename = parentpath, path
     return bundlerepository(ui, repopath, bundlename)
 
-def getremotechanges(ui, repo, other, revs=None, bundlename=None, force=False):
-    tmp = discovery.findcommonincoming(repo, other, heads=revs, force=force)
+def getremotechanges(ui, repo, other, revs=None, bundlename=None,
+                     force=False, usecommon=False):
+    tmp = discovery.findcommonincoming(repo, other, heads=revs, force=force,
+                                       commononly=usecommon)
     common, incoming, rheads = tmp
     if not incoming:
         try:
             os.unlink(bundlename)
         except:
             pass
-        return other, None, None
+        return other, None, None, None
 
     bundle = None
     if bundlename or not other.local():
@@ -303,7 +305,9 @@ def getremotechanges(ui, repo, other, re
         if revs is None and other.capable('changegroupsubset'):
             revs = rheads
 
-        if revs is None:
+        if usecommon:
+            cg = other.getbundle('incoming', common=common, heads=revs)
+        elif revs is None:
             cg = other.changegroup(incoming, "incoming")
         else:
             cg = other.changegroupsubset(incoming, revs, 'incoming')
@@ -315,5 +319,5 @@ def getremotechanges(ui, repo, other, re
         if not other.local():
             # use the created uncompressed bundlerepo
             other = bundlerepository(ui, repo.root, fname)
-    return (other, incoming, bundle)
+    return (other, common, incoming, bundle)
 
diff --git a/mercurial/discovery.py b/mercurial/discovery.py
--- a/mercurial/discovery.py
+++ b/mercurial/discovery.py
@@ -9,9 +9,10 @@ from node import nullid, short
 from i18n import _
 import util, error
 
-def findcommonincoming(repo, remote, heads=None, force=False):
-    """Return a tuple (common, missing roots, heads) used to identify
-    missing nodes from remote.
+def findcommonincoming(repo, remote, heads=None, force=False, commononly=False):
+    """Return a tuple (common, missing, heads) used to identify missing nodes
+    from remote. "missing" is either a boolean indicating if any nodes are missing
+    (when commononly=True), or else a list of the root nodes of the missing set.
 
     If a list of heads is specified, return only nodes which are heads
     or ancestors of these heads.
@@ -36,6 +37,13 @@ def findcommonincoming(repo, remote, hea
     # and start by examining the heads
     repo.ui.status(_("searching for changes\n"))
 
+    if commononly:
+        myheads = repo.heads()
+        known = remote.known(myheads)
+        if util.all(known):
+            hasincoming = set(heads).difference(set(myheads)) and True
+            return myheads, hasincoming, heads
+
     unknown = []
     for h in heads:
         if h not in m:
diff --git a/mercurial/hg.py b/mercurial/hg.py
--- a/mercurial/hg.py
+++ b/mercurial/hg.py
@@ -436,14 +436,19 @@ def _incoming(displaychlist, subreporecu
 
     if revs:
         revs = [other.lookup(rev) for rev in revs]
-    other, incoming, bundle = bundlerepo.getremotechanges(ui, repo, other, revs,
-                                opts["bundle"], opts["force"])
-    if incoming is None:
+    usecommon = other.capable('getbundle')
+    other, common, incoming, bundle = bundlerepo.getremotechanges(ui, repo, other,
+                                       revs, opts["bundle"], opts["force"],
+                                       usecommon=usecommon)
+    if not incoming:
         ui.status(_("no changes found\n"))
         return subreporecurse()
 
     try:
-        chlist = other.changelog.nodesbetween(incoming, revs)[0]
+        if usecommon:
+            chlist = other.changelog.findmissing(common, revs)
+        else:
+            chlist = other.changelog.nodesbetween(incoming, revs)[0]
         displayer = cmdutil.show_changeset(ui, other, opts, buffered)
 
         # XXX once graphlog extension makes it into core,
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -1325,20 +1325,24 @@ class localrepository(repo.repository):
     def pull(self, remote, heads=None, force=False):
         lock = self.lock()
         try:
+            usecommon = remote.capable('getbundle')
             tmp = discovery.findcommonincoming(self, remote, heads=heads,
-                                               force=force)
+                                               force=force, commononly=usecommon)
             common, fetch, rheads = tmp
             if not fetch:
                 self.ui.status(_("no changes found\n"))
                 result = 0
             else:
-                if heads is None and fetch == [nullid]:
+                if heads is None and list(common) == [nullid]:
                     self.ui.status(_("requesting all changes\n"))
                 elif heads is None and remote.capable('changegroupsubset'):
                     # issue1320, avoid a race if remote changed after discovery
                     heads = rheads
 
-                if heads is None:
+                if usecommon:
+                    cg = remote.getbundle('pull', common=common,
+                                          heads=heads or rheads)
+                elif heads is None:
                     cg = remote.changegroup(fetch, 'pull')
                 elif not remote.capable('changegroupsubset'):
                     raise util.Abort(_("partial pull cannot be done because "
diff --git a/tests/test-586.t b/tests/test-586.t
--- a/tests/test-586.t
+++ b/tests/test-586.t
@@ -17,6 +17,7 @@ dirstate
   pulling from ../a
   searching for changes
   warning: repository is unrelated
+  requesting all changes
   adding changesets
   adding manifests
   adding file changes
@@ -66,6 +67,7 @@ create test repos
   pulling from ../repob
   searching for changes
   warning: repository is unrelated
+  requesting all changes
   adding changesets
   adding manifests
   adding file changes
diff --git a/tests/test-globalopts.t b/tests/test-globalopts.t
--- a/tests/test-globalopts.t
+++ b/tests/test-globalopts.t
@@ -28,6 +28,7 @@
   pulling from ../b
   searching for changes
   warning: repository is unrelated
+  requesting all changes
   adding changesets
   adding manifests
   adding file changes
diff --git a/tests/test-http-clone-r.t b/tests/test-http-clone-r.t
--- a/tests/test-http-clone-r.t
+++ b/tests/test-http-clone-r.t
@@ -214,7 +214,7 @@ clone remote via stream
   adding changesets
   adding manifests
   adding file changes
-  added 1 changesets with 0 changes to 1 files (+1 heads)
+  added 1 changesets with 0 changes to 0 files (+1 heads)
   (run 'hg heads' to see heads, 'hg merge' to merge)
   $ hg verify
   checking changesets
@@ -238,7 +238,7 @@ clone remote via stream
   adding changesets
   adding manifests
   adding file changes
-  added 2 changesets with 0 changes to 1 files (+1 heads)
+  added 2 changesets with 0 changes to 0 files (+1 heads)
   (run 'hg heads' to see heads, 'hg merge' to merge)
   $ hg verify
   checking changesets
diff --git a/tests/test-http-proxy.t b/tests/test-http-proxy.t
--- a/tests/test-http-proxy.t
+++ b/tests/test-http-proxy.t
@@ -103,18 +103,18 @@ do not use the proxy if it is in the no 
   * - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys&namespace=bookmarks HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
-  * - - [*] "GET http://localhost:$HGPORT/?cmd=changegroup&roots=0000000000000000000000000000000000000000 HTTP/1.1" - - (glob)
+  * - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle&common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys&namespace=bookmarks HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
-  * - - [*] "GET http://localhost:$HGPORT/?cmd=changegroup&roots=0000000000000000000000000000000000000000 HTTP/1.1" - - (glob)
+  * - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle&common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys&namespace=bookmarks HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
-  * - - [*] "GET http://localhost:$HGPORT/?cmd=changegroup&roots=0000000000000000000000000000000000000000 HTTP/1.1" - - (glob)
+  * - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle&common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys&namespace=bookmarks HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=capabilities HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=heads HTTP/1.1" - - (glob)
-  * - - [*] "GET http://localhost:$HGPORT/?cmd=changegroup&roots=0000000000000000000000000000000000000000 HTTP/1.1" - - (glob)
+  * - - [*] "GET http://localhost:$HGPORT/?cmd=getbundle&common=0000000000000000000000000000000000000000&heads=83180e7845de420a1bb46896fd5fe05294f8d629 HTTP/1.1" - - (glob)
   * - - [*] "GET http://localhost:$HGPORT/?cmd=listkeys&namespace=bookmarks HTTP/1.1" - - (glob)
 
diff --git a/tests/test-schemes.t b/tests/test-schemes.t
--- a/tests/test-schemes.t
+++ b/tests/test-schemes.t
@@ -29,6 +29,7 @@ check that {1} syntax works
   comparing with parts://localhost
   sending heads command
   searching for changes
+  sending known command
   no changes found
   [1]
 
diff --git a/tests/test-ssh-clone-r.t b/tests/test-ssh-clone-r.t
--- a/tests/test-ssh-clone-r.t
+++ b/tests/test-ssh-clone-r.t
@@ -232,7 +232,7 @@ clone remote via stream
   adding changesets
   adding manifests
   adding file changes
-  added 1 changesets with 0 changes to 1 files (+1 heads)
+  added 1 changesets with 0 changes to 0 files (+1 heads)
   (run 'hg heads' to see heads, 'hg merge' to merge)
   $ hg verify
   checking changesets
@@ -256,7 +256,7 @@ clone remote via stream
   adding changesets
   adding manifests
   adding file changes
-  added 2 changesets with 0 changes to 1 files (+1 heads)
+  added 2 changesets with 0 changes to 0 files (+1 heads)
   (run 'hg heads' to see heads, 'hg merge' to merge)
   $ hg verify
   checking changesets
diff --git a/tests/test-unrelated-pull.t b/tests/test-unrelated-pull.t
--- a/tests/test-unrelated-pull.t
+++ b/tests/test-unrelated-pull.t
@@ -23,6 +23,7 @@
   pulling from ../a
   searching for changes
   warning: repository is unrelated
+  requesting all changes
   adding changesets
   adding manifests
   adding file changes