diff -r fb2df4506c87 -r 2efd608473fb mercurial/revset.py
--- a/mercurial/revset.py	Thu Feb 13 13:54:45 2014 -0800
+++ b/mercurial/revset.py	Thu Feb 13 14:04:47 2014 -0800
@@ -1749,7 +1749,24 @@
     elif op == 'and':
         wa, ta = optimize(x[1], True)
         wb, tb = optimize(x[2], True)
+
+        # (::x and not ::y)/(not ::y and ::x) have a fast path
+        def ismissingancestors(revs, bases):
+            return (
+                revs[0] == 'func'
+                and getstring(revs[1], _('not a symbol')) == 'ancestors'
+                and bases[0] == 'not'
+                and bases[1][0] == 'func'
+                and getstring(bases[1][1], _('not a symbol')) == 'ancestors')
+
         w = min(wa, wb)
+        if ismissingancestors(ta, tb):
+            return w, ('func', ('symbol', '_missingancestors'),
+                       ('list', ta[2], tb[1][2]))
+        if ismissingancestors(tb, ta):
+            return w, ('func', ('symbol', '_missingancestors'),
+                       ('list', tb[2], ta[1][2]))
+
         if wa > wb:
             return w, (op, tb, ta)
         return w, (op, ta, tb)