diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
index 4e79439..17ecb74 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -366,6 +366,16 @@
     }
   }
 
+  private Set<Target> filterTargetsNotInGraph(Set<Target> targets) {
+    Map<Target, SkyKey> map = Maps.toMap(targets, TARGET_TO_SKY_KEY);
+    Set<SkyKey> present = graph.getDoneValues(map.values()).keySet();
+    if (present.size() == targets.size()) {
+      // Optimize for case of all targets being in graph.
+      return targets;
+    }
+    return Maps.filterValues(map, Predicates.in(present)).keySet();
+  }
+
   @Override
   protected Map<String, Set<Target>> preloadOrThrow(
       QueryExpression caller, Collection<String> patterns)
@@ -406,7 +416,7 @@
                 targetPatternKey.getPolicy(), pkgPath);
         TargetPattern parsedPattern = targetPatternKey.getParsedPattern();
         try {
-          result.put(pattern, parsedPattern.eval(resolver).getTargets());
+          result.put(pattern, filterTargetsNotInGraph(parsedPattern.eval(resolver).getTargets()));
         } catch (TargetParsingException e) {
           targetParsingException = e;
         } catch (InterruptedException e) {
@@ -481,13 +491,16 @@
     return result.build();
   }
 
+  private static final Function<Target, SkyKey> TARGET_TO_SKY_KEY =
+      new Function<Target, SkyKey>() {
+        @Override
+        public SkyKey apply(Target target) {
+          return TransitiveTraversalValue.key(target.getLabel());
+        }
+      };
+
   private Iterable<SkyKey> makeKeys(Iterable<Target> targets) {
-    return Iterables.transform(targets, new Function<Target, SkyKey>() {
-      @Override
-      public SkyKey apply(Target target) {
-        return TransitiveTraversalValue.key(target.getLabel());
-      }
-    });
+    return Iterables.transform(targets, TARGET_TO_SKY_KEY);
   }
 
   @Override