diff --git a/src/main/java/com/google/devtools/build/lib/BUILD b/src/main/java/com/google/devtools/build/lib/BUILD
index 759b4ce..f289290 100644
--- a/src/main/java/com/google/devtools/build/lib/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/BUILD
@@ -542,6 +542,7 @@
         "//src/main/java/com/google/devtools/build/lib/buildeventstream/proto:build_event_stream_java_proto",
         "//src/main/java/com/google/devtools/build/lib/cmdline",
         "//src/main/java/com/google/devtools/build/lib/collect",
+        "//src/main/java/com/google/devtools/build/lib/collect/compacthashset",
         "//src/main/java/com/google/devtools/build/lib/collect/nestedset",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/lib/skyframe/serialization/autocodec",
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
index be65076..02a9985 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPattern.java
@@ -474,9 +474,7 @@
       }
 
       callback.process(
-          resolver
-              .getTargetsInPackage(getOriginalPattern(), packageIdentifier, rulesOnly)
-              .getTargets());
+          resolver.getTargetsInPackage(getOriginalPattern(), packageIdentifier, rulesOnly));
     }
 
     @Override
diff --git a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
index 69d3b22..7545d3a 100644
--- a/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/cmdline/TargetPatternResolver.java
@@ -21,6 +21,7 @@
 import com.google.devtools.build.lib.util.BatchCallback;
 import com.google.devtools.build.lib.util.ThreadSafeBatchCallback;
 import com.google.devtools.build.lib.vfs.PathFragment;
+import java.util.Collection;
 
 /**
  * A callback that is used during the process of converting target patterns (such as
@@ -57,8 +58,8 @@
    * @param packageIdentifier the identifier of the package
    * @param rulesOnly whether to return rules only
    */
-  public abstract ResolvedTargets<T> getTargetsInPackage(String originalPattern,
-      PackageIdentifier packageIdentifier, boolean rulesOnly)
+  public abstract Collection<T> getTargetsInPackage(
+      String originalPattern, PackageIdentifier packageIdentifier, boolean rulesOnly)
       throws TargetParsingException, InterruptedException;
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternPreloader.java b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternPreloader.java
index 445488b..bb14171 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternPreloader.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternPreloader.java
@@ -14,7 +14,6 @@
 
 package com.google.devtools.build.lib.pkgcache;
 
-import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.concurrent.ThreadSafety;
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
@@ -48,7 +47,7 @@
    * keepGoing} is set to true. In that case, the patterns that failed to load have the error flag
    * set.
    */
-  Map<String, ResolvedTargets<Target>> preloadTargetPatterns(
+  Map<String, Collection<Target>> preloadTargetPatterns(
       ExtendedEventHandler eventHandler,
       PathFragment relativeWorkingDirectory,
       Collection<String> patterns,
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternResolverUtil.java b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternResolverUtil.java
index 8cdfd51..fd8caa8 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternResolverUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternResolverUtil.java
@@ -14,20 +14,17 @@
 package com.google.devtools.build.lib.pkgcache;
 
 import com.google.devtools.build.lib.cmdline.LabelValidator;
-import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
-import com.google.devtools.build.lib.cmdline.TargetPatternResolver;
+import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.vfs.PathFragment;
+import java.util.Collection;
 
 /**
  * Common utility methods for target pattern resolution.
  */
 public final class TargetPatternResolverUtil {
-
-
   private TargetPatternResolverUtil() {
     // Utility class.
   }
@@ -40,33 +37,17 @@
     }
   }
 
-  public static ResolvedTargets<Target> resolvePackageTargets(Package pkg, FilteringPolicy policy) {
-    ResolvedTargets.Builder<Target> builder = ResolvedTargets.builder();
+  public static Collection<Target> resolvePackageTargets(Package pkg, FilteringPolicy policy) {
+    if (policy == FilteringPolicies.NO_FILTER) {
+      return pkg.getTargets().values();
+    }
+    CompactHashSet<Target> builder = CompactHashSet.create();
     for (Target target : pkg.getTargets().values()) {
       if (policy.shouldRetain(target, false)) {
         builder.add(target);
       }
     }
-    return builder.build();
-  }
-
-  public static void validatePatternPackage(
-      String originalPattern, PathFragment packageNameFragment, TargetPatternResolver<?> resolver)
-      throws TargetParsingException, InterruptedException {
-    String packageName = packageNameFragment.toString();
-    // It's possible for this check to pass, but for
-    // Label.validatePackageNameFull to report an error because the
-    // package name is illegal.  That's a little weird, but we can live with
-    // that for now--see test case: testBadPackageNameButGoodEnoughForALabel.
-    if (LabelValidator.validatePackageName(packageName) != null) {
-      throw new TargetParsingException("'" + packageName + "' is not a valid package name");
-    }
-    if (!resolver.isPackage(PackageIdentifier.createInMainRepo(packageName))) {
-      throw new TargetParsingException(
-          TargetPatternResolverUtil.getParsingErrorMessage(
-              "no such package '" + packageName + "': BUILD file not found on package path",
-              originalPattern));
-    }
+    return builder;
   }
 
   public static PathFragment getPathFragment(String pathPrefix) throws TargetParsingException {
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java b/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java
index 6f99765..fe669e0 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java
@@ -34,6 +34,7 @@
 
   public TargetLiteral(String pattern) {
     this.pattern = Preconditions.checkNotNull(pattern);
+    Preconditions.checkArgument(!pattern.startsWith("-"));
   }
 
   public String getPattern() {
diff --git a/src/main/java/com/google/devtools/build/lib/query2/query/BlazeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/query/BlazeQueryEnvironment.java
index cc2110b..5557482 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/query/BlazeQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/query/BlazeQueryEnvironment.java
@@ -19,10 +19,8 @@
 import com.google.common.base.Predicate;
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
-import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
@@ -79,7 +77,7 @@
  */
 public class BlazeQueryEnvironment extends AbstractBlazeQueryEnvironment<Target> {
   private static final int MAX_DEPTH_FULL_SCAN_LIMIT = 20;
-  private final Map<String, Set<Target>> resolvedTargetPatterns = new HashMap<>();
+  private final Map<String, Collection<Target>> resolvedTargetPatterns = new HashMap<>();
   private final TargetPatternPreloader targetPatternPreloader;
   private final PathFragment relativeWorkingDirectory;
   private final TransitivePackageLoader transitivePackageLoader;
@@ -173,12 +171,13 @@
     // We can safely ignore the boolean error flag. The evaluateQuery() method above wraps the
     // entire query computation in an error sensor.
 
-    Set<Target> targets = resolvedTargetPatterns.get(pattern);
+    // This must be a collections class with a fast contains() implementation, or the code below
+    // becomes quadratic in runtime.
+    Set<Target> targets = new LinkedHashSet<>(resolvedTargetPatterns.get(pattern));
 
     // Sets.filter would be more convenient here, but can't deal with exceptions.
     if (labelFilter != Predicates.<Label>alwaysTrue()) {
       // The labelFilter is always true for bazel query; it's only used for genquery rules.
-      targets = new LinkedHashSet<>(targets);
       Iterator<Target> targetIterator = targets.iterator();
       while (targetIterator.hasNext()) {
         Target target = targetIterator.next();
@@ -473,10 +472,8 @@
       // Note that this may throw a RuntimeException if deps are missing in Skyframe and this is
       // being called from within a SkyFunction.
       resolvedTargetPatterns.putAll(
-          Maps.transformValues(
-              targetPatternPreloader.preloadTargetPatterns(
-                  eventHandler, relativeWorkingDirectory, patterns, keepGoing, useForkJoinPool),
-              ResolvedTargets::getTargets));
+          targetPatternPreloader.preloadTargetPatterns(
+              eventHandler, relativeWorkingDirectory, patterns, keepGoing, useForkJoinPool));
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/BUILD b/src/main/java/com/google/devtools/build/lib/rules/genquery/BUILD
index 9a9f729..107125a 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/BUILD
@@ -21,6 +21,7 @@
         "//src/main/java/com/google/devtools/build/lib:packages-internal",
         "//src/main/java/com/google/devtools/build/lib:util",
         "//src/main/java/com/google/devtools/build/lib/actions",
+        "//src/main/java/com/google/devtools/build/lib/collect/compacthashset",
         "//src/main/java/com/google/devtools/build/lib/collect/nestedset",
         "//src/main/java/com/google/devtools/build/lib/concurrent",
         "//src/main/java/com/google/devtools/build/lib/profiler",
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
index fe5966c..77fc9e8 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
@@ -42,6 +42,7 @@
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
+import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
 import com.google.devtools.build.lib.collect.nestedset.Order;
@@ -415,7 +416,7 @@
     }
 
     @Override
-    public Map<String, ResolvedTargets<Target>> preloadTargetPatterns(
+    public Map<String, Collection<Target>> preloadTargetPatterns(
         ExtendedEventHandler eventHandler,
         PathFragment relativeWorkingDirectory,
         Collection<String> patterns,
@@ -425,7 +426,7 @@
       Preconditions.checkArgument(!keepGoing);
       Preconditions.checkArgument(relativeWorkingDirectory.isEmpty());
       boolean ok = true;
-      Map<String, ResolvedTargets<Target>> preloadedPatterns =
+      Map<String, Collection<Target>> preloadedPatterns =
           Maps.newHashMapWithExpectedSize(patterns.size());
       Map<TargetPatternKey, String> patternKeys = Maps.newHashMapWithExpectedSize(patterns.size());
       for (String pattern : patterns) {
@@ -482,14 +483,11 @@
       for (Map.Entry<String, ResolvedTargets<Label>> entry : resolvedLabelsMap.entrySet()) {
         String pattern = entry.getKey();
         ResolvedTargets<Label> resolvedLabels = resolvedLabelsMap.get(pattern);
-        ResolvedTargets.Builder<Target> builder = ResolvedTargets.builder();
+        Set<Target> builder = CompactHashSet.create();
         for (Label label : resolvedLabels.getTargets()) {
           builder.add(getExistingTarget(label, packages));
         }
-        for (Label label : resolvedLabels.getFilteredTargets()) {
-          builder.remove(getExistingTarget(label, packages));
-        }
-        preloadedPatterns.put(pattern, builder.build());
+        preloadedPatterns.put(pattern, builder);
       }
       return preloadedPatterns;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageFunction.java
index 7a085c4..5ca5a26 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/CollectTargetsInPackageFunction.java
@@ -52,8 +52,7 @@
     }
     env.getValues(
         Iterables.transform(
-            TargetPatternResolverUtil.resolvePackageTargets(pkg, argument.getFilteringPolicy())
-                .getTargets(),
+            TargetPatternResolverUtil.resolvePackageTargets(pkg, argument.getFilteringPolicy()),
             TO_TRANSITIVE_TRAVERSAL_KEY));
     if (env.valuesMissing()) {
       return null;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
index 6112c72..8f4a620 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternFunction.java
@@ -45,6 +45,7 @@
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.List;
 import java.util.concurrent.atomic.AtomicReference;
 import javax.annotation.Nullable;
@@ -191,7 +192,7 @@
     }
 
     @Override
-    public ResolvedTargets<Void> getTargetsInPackage(
+    public Collection<Void> getTargetsInPackage(
         String originalPattern, PackageIdentifier packageIdentifier, boolean rulesOnly)
         throws TargetParsingException, InterruptedException {
       FilteringPolicy policy =
@@ -199,15 +200,15 @@
       return getTargetsInPackage(originalPattern, packageIdentifier, policy);
     }
 
-    private ResolvedTargets<Void> getTargetsInPackage(
+    private Collection<Void> getTargetsInPackage(
         String originalPattern, PackageIdentifier packageIdentifier, FilteringPolicy policy)
         throws TargetParsingException, InterruptedException {
       try {
         Package pkg = packageProvider.getPackage(env.getListener(), packageIdentifier);
-        ResolvedTargets<Target> packageTargets =
+        Collection<Target> packageTargets =
             TargetPatternResolverUtil.resolvePackageTargets(pkg, policy);
         ImmutableList.Builder<SkyKey> builder = ImmutableList.builder();
-        for (Target target : packageTargets.getTargets()) {
+        for (Target target : packageTargets) {
           builder.add(TransitiveTraversalValue.key(target.getLabel()));
         }
         ImmutableList<SkyKey> skyKeys = builder.build();
@@ -215,7 +216,7 @@
         if (env.valuesMissing()) {
           throw new MissingDepException();
         }
-        return ResolvedTargets.empty();
+        return ImmutableSet.of();
       } catch (NoSuchThingException e) {
         String message = TargetPatternResolverUtil.getParsingErrorMessage(
             "package contains errors", originalPattern);
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
index 0ae0337..d63b8eb 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/RecursivePackageProviderBackedTargetPatternResolver.java
@@ -47,6 +47,7 @@
 import com.google.devtools.build.lib.util.ThreadSafeBatchCallback;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import java.util.ArrayList;
+import java.util.Collection;
 import java.util.List;
 import java.util.Map;
 import java.util.concurrent.ExecutionException;
@@ -122,7 +123,7 @@
   }
 
   @Override
-  public ResolvedTargets<Target> getTargetsInPackage(
+  public Collection<Target> getTargetsInPackage(
       String originalPattern, PackageIdentifier packageIdentifier, boolean rulesOnly)
       throws TargetParsingException, InterruptedException {
     FilteringPolicy actualPolicy = rulesOnly
@@ -138,18 +139,16 @@
     }
   }
 
-  private Map<PackageIdentifier, ResolvedTargets<Target>> bulkGetTargetsInPackage(
-          String originalPattern,
-          Iterable<PackageIdentifier> pkgIds, FilteringPolicy policy)
-          throws InterruptedException {
+  private Map<PackageIdentifier, Collection<Target>> bulkGetTargetsInPackage(
+      String originalPattern, Iterable<PackageIdentifier> pkgIds, FilteringPolicy policy)
+      throws InterruptedException {
     try {
       Map<PackageIdentifier, Package> pkgs = bulkGetPackages(pkgIds);
       if (pkgs.size() != Iterables.size(pkgIds)) {
         throw new IllegalStateException("Bulk package retrieval missing results: "
             + Sets.difference(ImmutableSet.copyOf(pkgIds), pkgs.keySet()));
       }
-      ImmutableMap.Builder<PackageIdentifier, ResolvedTargets<Target>> result =
-              ImmutableMap.builder();
+      ImmutableMap.Builder<PackageIdentifier, Collection<Target>> result = ImmutableMap.builder();
       for (PackageIdentifier pkgId : pkgIds) {
         Package pkg = pkgs.get(pkgId);
         result.put(pkgId,  TargetPatternResolverUtil.resolvePackageTargets(pkg, policy));
@@ -291,11 +290,11 @@
                 ImmutableSet<PackageIdentifier> pkgIdBatchSet = ImmutableSet.copyOf(pkgIdBatch);
                 packageSemaphore.acquireAll(pkgIdBatchSet);
                 try {
-                  Iterable<ResolvedTargets<Target>> resolvedTargets =
+                  Iterable<Collection<Target>> resolvedTargets =
                       bulkGetTargetsInPackage(originalPattern, pkgIdBatch, actualPolicy).values();
                   List<Target> filteredTargets = new ArrayList<>(calculateSize(resolvedTargets));
-                  for (ResolvedTargets<Target> targets : resolvedTargets) {
-                    filteredTargets.addAll(targets.getTargets());
+                  for (Collection<Target> targets : resolvedTargets) {
+                    filteredTargets.addAll(targets);
                   }
                   // TODO(bazel-core): Invoking the callback while holding onto the package
                   // semaphore can lead to deadlocks. Also, if the semaphore has a small count,
@@ -312,10 +311,10 @@
     return Futures.whenAllSucceed(futures).call(() -> null, directExecutor());
   }
 
-  private static <T> int calculateSize(Iterable<ResolvedTargets<T>> resolvedTargets) {
+  private static <T> int calculateSize(Iterable<Collection<T>> resolvedTargets) {
     int size = 0;
-    for (ResolvedTargets<T> targets : resolvedTargets) {
-      size += targets.getTargets().size();
+    for (Collection<T> targets : resolvedTargets) {
+      size += targets.size();
     }
     return size;
   }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java
index d81cb6d..ee4b9b5 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java
@@ -51,7 +51,7 @@
   }
 
   @Override
-  public Map<String, ResolvedTargets<Target>> preloadTargetPatterns(
+  public Map<String, Collection<Target>> preloadTargetPatterns(
       ExtendedEventHandler eventHandler,
       PathFragment relativeWorkingDirectory,
       Collection<String> patterns,
@@ -59,13 +59,14 @@
       boolean useForkJoinPool)
       throws TargetParsingException, InterruptedException {
     String offset = relativeWorkingDirectory.getPathString();
-    ImmutableMap.Builder<String, ResolvedTargets<Target>> resultBuilder = ImmutableMap.builder();
+    ImmutableMap.Builder<String, Collection<Target>> resultBuilder = ImmutableMap.builder();
     List<PatternLookup> patternLookups = new ArrayList<>();
     List<SkyKey> allKeys = new ArrayList<>();
     for (String pattern : patterns) {
+      Preconditions.checkArgument(!pattern.startsWith("-"));
       PatternLookup patternLookup = createPatternLookup(offset, eventHandler, pattern, keepGoing);
       if (patternLookup == null) {
-        resultBuilder.put(pattern, ResolvedTargets.failed());
+        resultBuilder.put(pattern, ImmutableSet.of());
       } else {
         patternLookups.add(patternLookup);
         allKeys.add(patternLookup.skyKey);
@@ -85,7 +86,7 @@
       SkyValue resultValue = result.get(key);
       if (resultValue != null) {
         try {
-          ResolvedTargets<Target> resolvedTargets =
+          Collection<Target> resolvedTargets =
               patternLookup.process(eventHandler, resultValue, walkableGraph, keepGoing);
           resultBuilder.put(patternLookup.pattern, resolvedTargets);
         } catch (TargetParsingException e) {
@@ -95,7 +96,7 @@
           eventHandler.handle(
               Event.error("Skipping '" + patternLookup.pattern + "': " + e.getMessage()));
           eventHandler.post(PatternExpandingError.skipped(patternLookup.pattern, e.getMessage()));
-          resultBuilder.put(patternLookup.pattern, ResolvedTargets.failed());
+          resultBuilder.put(patternLookup.pattern, ImmutableSet.of());
         }
       } else {
         String rawPattern = patternLookup.pattern;
@@ -124,7 +125,7 @@
           eventHandler.post(PatternExpandingError.failed(patternLookup.pattern, errorMessage));
           throw new TargetParsingException(errorMessage);
         }
-        resultBuilder.put(patternLookup.pattern, ResolvedTargets.failed());
+        resultBuilder.put(patternLookup.pattern, ImmutableSet.of());
       }
     }
     return resultBuilder.build();
@@ -177,7 +178,7 @@
       this.skyKey = skyKey;
     }
 
-    public abstract ResolvedTargets<Target> process(
+    public abstract Collection<Target> process(
         ExtendedEventHandler eventHandler,
         SkyValue value,
         WalkableGraph walkableGraph,
@@ -186,17 +187,15 @@
   }
 
   private static class NormalLookup extends PatternLookup {
-    private final TargetPatternKey key;
     private final TargetPatternsResultBuilder resultBuilder;
 
     private NormalLookup(String targetPattern, TargetPatternKey key) {
       super(targetPattern, key);
-      this.key = key;
       this.resultBuilder = new TargetPatternsResultBuilder();
     }
 
     @Override
-    public ResolvedTargets<Target> process(
+    public Collection<Target> process(
         ExtendedEventHandler eventHandler,
         SkyValue value,
         WalkableGraph walkableGraph,
@@ -204,11 +203,7 @@
         throws InterruptedException {
       TargetPatternValue resultValue = (TargetPatternValue) value;
       ResolvedTargets<Label> results = resultValue.getTargets();
-      if (key.isNegative()) {
-        resultBuilder.addLabelsOfNegativePattern(results);
-      } else {
-        resultBuilder.addLabelsOfPositivePattern(results);
-      }
+      resultBuilder.addLabelsOfPositivePattern(results);
       return resultBuilder.build(walkableGraph);
     }
   }
@@ -229,7 +224,7 @@
     }
 
     @Override
-    public ResolvedTargets<Target> process(
+    public Collection<Target> process(
         ExtendedEventHandler eventHandler,
         SkyValue value,
         WalkableGraph walkableGraph,
@@ -243,14 +238,16 @@
               eventHandler,
               FilteringPolicies.NO_FILTER,
               /* packageSemaphore= */ null);
-      AtomicReference<ResolvedTargets<Target>> result = new AtomicReference<>();
+      AtomicReference<Collection<Target>> result = new AtomicReference<>();
       targetPattern.eval(
           resolver,
           /*blacklistedSubdirectories=*/ ImmutableSet.<PathFragment>of(),
           /*excludedSubdirectories=*/ ImmutableSet.<PathFragment>of(),
           partialResult ->
               result.set(
-                  new ResolvedTargets<>(ImmutableSet.copyOf(partialResult), /*hasError=*/ false)),
+                  partialResult instanceof Collection
+                      ? (Collection<Target>) partialResult
+                      : ImmutableSet.copyOf(partialResult)),
           TargetParsingException.class);
       return result.get();
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java
index b195308..2725c22 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternFunction.java
@@ -15,13 +15,11 @@
 
 import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableSet;
-import com.google.common.collect.Iterables;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
 import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.cmdline.TargetPattern;
-import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
 import com.google.devtools.build.lib.concurrent.MultisetSemaphore;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.pkgcache.AbstractRecursivePackageProvider.MissingDepException;
@@ -32,7 +30,6 @@
 import com.google.devtools.build.skyframe.SkyFunctionException;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
-import java.util.Set;
 import javax.annotation.Nullable;
 
 /**
@@ -66,12 +63,14 @@
               MultisetSemaphore.<PackageIdentifier>unbounded());
       TargetPattern parsedPattern = patternKey.getParsedPattern();
       ImmutableSet<PathFragment> excludedSubdirectories = patternKey.getExcludedSubdirectories();
-      final Set<Target> results = CompactHashSet.create();
+      ResolvedTargets.Builder<Target> resolvedTargetsBuilder = ResolvedTargets.builder();
       BatchCallback<Target, RuntimeException> callback =
           new BatchCallback<Target, RuntimeException>() {
             @Override
             public void process(Iterable<Target> partialResult) {
-              Iterables.addAll(results, partialResult);
+              for (Target target : partialResult) {
+                resolvedTargetsBuilder.add(target);
+              }
             }
           };
       parsedPattern.eval(
@@ -82,8 +81,6 @@
           // The exception type here has to match the one on the BatchCallback. Since the callback
           // defined above never throws, the exact type here is not really relevant.
           RuntimeException.class);
-      ResolvedTargets.Builder<Target> resolvedTargetsBuilder =
-          ResolvedTargets.<Target>builder().addAll(results);
       if (provider.encounteredPackageErrors()) {
         resolvedTargetsBuilder.setError();
       }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternsResultBuilder.java b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternsResultBuilder.java
index 933c061..2f6c4dc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternsResultBuilder.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/TargetPatternsResultBuilder.java
@@ -14,16 +14,16 @@
 package com.google.devtools.build.lib.skyframe;
 
 import com.google.common.base.Preconditions;
-import com.google.common.base.Predicates;
-import com.google.common.collect.Iterables;
 import com.google.common.collect.Maps;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.ResolvedTargets;
+import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.skyframe.WalkableGraph;
+import java.util.Collection;
 import java.util.HashSet;
 import java.util.Map;
 import java.util.Set;
@@ -33,24 +33,13 @@
  * list of target patterns (eg, //foo:all -//bar/... //foo:test).
  */
 class TargetPatternsResultBuilder {
-  private final ResolvedTargets.Builder<Label> resolvedLabelsBuilder = ResolvedTargets.builder();
+  private final Set<Label> resolvedLabelsBuilder = CompactHashSet.create();
   private Map<PackageIdentifier, Package> packages;
-  private boolean hasError;
-
-  /** Sets that there was an error, during evaluation. */
-  public void setError() {
-    hasError = true;
-  }
 
   /** Returns final set of targets and sets error flag if required. */
-  public ResolvedTargets<Target> build(WalkableGraph walkableGraph) throws InterruptedException {
+  public Collection<Target> build(WalkableGraph walkableGraph) throws InterruptedException {
     precomputePackages(walkableGraph);
-    ResolvedTargets.Builder<Target> resolvedTargetsBuilder =
-        transformLabelsIntoTargets(resolvedLabelsBuilder.build());
-    if (hasError) {
-      resolvedTargetsBuilder.setError();
-    }
-    return resolvedTargetsBuilder.build();
+    return transformLabelsIntoTargets(resolvedLabelsBuilder);
   }
 
   /**
@@ -58,18 +47,14 @@
    * method is using information about packages, so {@link #precomputePackages} has to be called
    * before this method.
    */
-  private ResolvedTargets.Builder<Target> transformLabelsIntoTargets(
-      ResolvedTargets<Label> resolvedLabels) {
+  private Collection<Target> transformLabelsIntoTargets(Set<Label> resolvedLabels) {
     // precomputePackages has to be called before this method.
-    ResolvedTargets.Builder<Target> resolvedTargetsBuilder = ResolvedTargets.builder();
+    Set<Target> targets = CompactHashSet.create();
     Preconditions.checkNotNull(packages);
-    for (Label label : resolvedLabels.getTargets()) {
-      resolvedTargetsBuilder.add(getExistingTarget(label));
+    for (Label label : resolvedLabels) {
+      targets.add(getExistingTarget(label));
     }
-    for (Label label : resolvedLabels.getFilteredTargets()) {
-      resolvedTargetsBuilder.remove(getExistingTarget(label));
-    }
-    return resolvedTargetsBuilder;
+    return targets;
   }
 
   private void precomputePackages(WalkableGraph walkableGraph) throws InterruptedException {
@@ -94,7 +79,7 @@
 
   private Set<PackageIdentifier> getPackagesIdentifiers() {
     Set<PackageIdentifier> packagesIdentifiers = new HashSet<>();
-    for (Label label : getLabels()) {
+    for (Label label : resolvedLabelsBuilder) {
       packagesIdentifiers.add(label.getPackageIdentifier());
     }
     return packagesIdentifiers;
@@ -107,19 +92,9 @@
         .getPackage();
   }
 
-  /** Adds the result from expansion of positive target pattern (eg, "//foo:all"). */
-  void addLabelsOfNegativePattern(ResolvedTargets<Label> labels) {
-    resolvedLabelsBuilder.filter(Predicates.not(Predicates.in(labels.getTargets())));
-  }
-
   /** Adds the result from expansion of negative target pattern (eg, "-//foo:all"). */
   void addLabelsOfPositivePattern(ResolvedTargets<Label> labels) {
-    resolvedLabelsBuilder.merge(labels);
-  }
-
-  /** Returns target labels from all individual results. */
-  private Iterable<Label> getLabels() {
-    ResolvedTargets<Label> resolvedLabels = resolvedLabelsBuilder.build();
-    return Iterables.concat(resolvedLabels.getTargets(), resolvedLabels.getFilteredTargets());
+    Preconditions.checkArgument(labels.getFilteredTargets().isEmpty());
+    resolvedLabelsBuilder.addAll(labels.getTargets());
   }
 }