diff --git a/mercurial/setdiscovery.py b/mercurial/setdiscovery.py
--- a/mercurial/setdiscovery.py
+++ b/mercurial/setdiscovery.py
@@ -219,6 +219,7 @@
         if len(revs) <= size:
             return list(revs)
         sample = set(self._repo.revs('heads(%ld)', revs))
+        size = max(size, len(sample))
 
         if len(sample) >= size:
             return _limitsample(sample, size)
@@ -233,6 +234,7 @@
             return list(revs)
         repo = self._repo
         sample = set(repo.revs('heads(%ld)', revs))
+        size = max(size, len(sample))
         parentrevs = self._parentsgetter()
 
         # update from heads
diff --git a/tests/test-setdiscovery.t b/tests/test-setdiscovery.t
--- a/tests/test-setdiscovery.t
+++ b/tests/test-setdiscovery.t
@@ -974,20 +974,17 @@
   searching for changes
   taking quick initial sample
   searching: 2 queries
-  query 2; still undecided: 1240, sample size is: 100
+  query 2; still undecided: 1240, sample size is: 260
   sampling from both directions
   searching: 3 queries
-  query 3; still undecided: 1140, sample size is: 200
+  query 3; still undecided: 980, sample size is: 260
   sampling from both directions
   searching: 4 queries
-  query 4; still undecided: \d+, sample size is: 200 (re)
+  query 4; still undecided: \d+, sample size is: \d+ (re)
   sampling from both directions
   searching: 5 queries
-  query 5; still undecided: \d+, sample size is: 200 (re)
-  sampling from both directions
-  searching: 6 queries
-  query 6; still undecided: \d+, sample size is: \d+ (re)
-  6 total queries in *.????s (glob)
+  query 5; still undecided: 131, sample size is: \d+ (re)
+  5 total queries in *.????s (glob)
   elapsed time:  * seconds (glob)
   heads summary:
     total common heads:          1