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 bc6dc9c..525bcb9 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
@@ -27,6 +27,8 @@
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Multimap;
 import com.google.common.collect.Sets;
+import com.google.common.util.concurrent.ListeningExecutorService;
+import com.google.common.util.concurrent.MoreExecutors;
 import com.google.common.util.concurrent.ThreadFactoryBuilder;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
@@ -92,7 +94,6 @@
 import java.util.Map;
 import java.util.Map.Entry;
 import java.util.Set;
-import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
 import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.logging.Logger;
@@ -112,7 +113,6 @@
 
   protected WalkableGraph graph;
 
-  private ImmutableList<TargetPatternKey> universeTargetPatternKeys;
   private Supplier<ImmutableSet<PathFragment>> blacklistPatternsSupplier;
 
   private final BlazeTargetAccessor accessor = new BlazeTargetAccessor(this);
@@ -132,6 +132,12 @@
       return target.getLabel();
     }
   };
+  private final ListeningExecutorService threadPool =
+      MoreExecutors.listeningDecorator(
+          Executors.newFixedThreadPool(
+              Runtime.getRuntime().availableProcessors(),
+              new ThreadFactoryBuilder().setNameFormat("GetPackages-%d").build()));
+  private RecursivePackageProviderBackedTargetPatternResolver resolver;
 
   private static class BlacklistSupplier implements Supplier<ImmutableSet<PathFragment>> {
     private final WalkableGraph graph;
@@ -179,9 +185,17 @@
     blacklistPatternsSupplier = Suppliers.memoize(new BlacklistSupplier(graph));
 
     SkyKey universeKey = graphFactory.getUniverseKey(universeScope, parserPrefix);
-    universeTargetPatternKeys =
+    ImmutableList<TargetPatternKey> universeTargetPatternKeys =
         PrepareDepsOfPatternsFunction.getTargetPatternKeys(
             PrepareDepsOfPatternsFunction.getSkyKeys(universeKey, eventHandler));
+    GraphBackedRecursivePackageProvider graphBackedRecursivePackageProvider =
+        new GraphBackedRecursivePackageProvider(graph, universeTargetPatternKeys, pkgPath);
+    resolver =
+        new RecursivePackageProviderBackedTargetPatternResolver(
+            graphBackedRecursivePackageProvider,
+            eventHandler,
+            TargetPatternEvaluator.DEFAULT_FILTERING_POLICY,
+            threadPool);
 
     // The prepareAndGet call above evaluates a single PrepareDepsOfPatterns SkyKey.
     // We expect to see either a single successfully evaluated value or a cycle in the result.
@@ -487,14 +501,6 @@
               TargetPatternValue.key(
                       pattern, TargetPatternEvaluator.DEFAULT_FILTERING_POLICY, parserPrefix)
                   .argument());
-      GraphBackedRecursivePackageProvider provider = new GraphBackedRecursivePackageProvider(
-          graph, universeTargetPatternKeys, pkgPath);
-      ExecutorService threadPool = Executors.newFixedThreadPool(
-          Runtime.getRuntime().availableProcessors(),
-          new ThreadFactoryBuilder().setNameFormat("GetPackages-%d").build());
-      RecursivePackageProviderBackedTargetPatternResolver resolver =
-          new RecursivePackageProviderBackedTargetPatternResolver(
-              provider, eventHandler, targetPatternKey.getPolicy(), threadPool);
       TargetPattern parsedPattern = targetPatternKey.getParsedPattern();
       ImmutableSet<PathFragment> subdirectoriesToExclude =
           targetPatternKey.getAllSubdirectoriesToExclude(blacklistPatternsSupplier);
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 46bd0c2..642d8ea 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
@@ -17,17 +17,20 @@
 
 import com.google.common.base.Function;
 import com.google.common.base.Throwables;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
+import com.google.common.util.concurrent.Futures;
+import com.google.common.util.concurrent.ListenableFuture;
+import com.google.common.util.concurrent.ListeningExecutorService;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 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.concurrent.ExecutorUtil;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
@@ -45,7 +48,7 @@
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Map;
-import java.util.concurrent.ExecutorService;
+import java.util.concurrent.ExecutionException;
 import java.util.concurrent.atomic.AtomicBoolean;
 import java.util.concurrent.atomic.AtomicReference;
 
@@ -62,13 +65,13 @@
   private final RecursivePackageProvider recursivePackageProvider;
   private final EventHandler eventHandler;
   private final FilteringPolicy policy;
-  private final ExecutorService executor;
+  private final ListeningExecutorService executor;
 
   public RecursivePackageProviderBackedTargetPatternResolver(
       RecursivePackageProvider recursivePackageProvider,
       EventHandler eventHandler,
       FilteringPolicy policy,
-      ExecutorService executor) {
+      ListeningExecutorService executor) {
     this.recursivePackageProvider = recursivePackageProvider;
     this.eventHandler = eventHandler;
     this.policy = policy;
@@ -210,49 +213,61 @@
 
     // For very large sets of packages, we may not want to process all of them at once, so we split
     // into batches.
-    try {
-      for (final Iterable<PackageIdentifier> pkgIdBatch :
-          Iterables.partition(pkgIds, MAX_PACKAGES_BULK_GET)) {
-        executor.execute(new Runnable() {
-          @Override
-          public void run() {
-            Iterable<ResolvedTargets<Target>> resolvedTargets = null;
-            try {
-              resolvedTargets =
-                  bulkGetTargetsInPackage(originalPattern, pkgIdBatch, NO_FILTER).values();
-            } catch (InterruptedException e) {
-              interrupt.compareAndSet(null, e);
-              return;
-            } catch (TargetParsingException e) {
-              parsingException.compareAndSet(null, e);
-            }
+    List<List<PackageIdentifier>> partitions =
+        ImmutableList.copyOf(Iterables.partition(pkgIds, MAX_PACKAGES_BULK_GET));
+    ArrayList<ListenableFuture<?>> futures = new ArrayList<>(partitions.size());
+    for (final Iterable<PackageIdentifier> pkgIdBatch : partitions) {
+      futures.add(
+          executor.submit(
+              new Runnable() {
+                @Override
+                public void run() {
+                  Iterable<ResolvedTargets<Target>> resolvedTargets;
+                  try {
+                    resolvedTargets =
+                        bulkGetTargetsInPackage(originalPattern, pkgIdBatch, NO_FILTER).values();
+                  } catch (InterruptedException e) {
+                    interrupt.compareAndSet(null, e);
+                    return;
+                  } catch (TargetParsingException e) {
+                    parsingException.compareAndSet(null, e);
+                    return;
+                  } catch (RuntimeException e) {
+                    // In particular, we're interested in remembering any thrown
+                    // MissingDepExceptions.
+                    genericException.compareAndSet(null, e);
+                    return;
+                  }
 
-            List<Target> filteredTargets = new ArrayList<>(calculateSize(resolvedTargets));
-            for (ResolvedTargets<Target> targets : resolvedTargets) {
-              for (Target target : targets.getTargets()) {
-                // Perform the no-targets-found check before applying the filtering policy so we
-                // only return the error if the input directory's subtree really contains no
-                // targets.
-                foundTarget.set(true);
-                if (actualPolicy.shouldRetain(target, false)) {
-                  filteredTargets.add(target);
+                  List<Target> filteredTargets = new ArrayList<>(calculateSize(resolvedTargets));
+                  for (ResolvedTargets<Target> targets : resolvedTargets) {
+                    for (Target target : targets.getTargets()) {
+                      // Perform the no-targets-found check before applying the filtering policy
+                      // so we only return the error if the input directory's subtree really
+                      // contains no targets.
+                      foundTarget.set(true);
+                      if (actualPolicy.shouldRetain(target, false)) {
+                        filteredTargets.add(target);
+                      }
+                    }
+                  }
+                  try {
+                    synchronized (callbackLock) {
+                      callback.process(filteredTargets);
+                    }
+                  } catch (InterruptedException e) {
+                    interrupt.compareAndSet(null, e);
+                  } catch (Exception e) {
+                    genericException.compareAndSet(e, null);
+                  }
                 }
-              }
-            }
-            try {
-              synchronized (callbackLock) {
-                callback.process(filteredTargets);
-              }
-            } catch (InterruptedException e) {
-              interrupt.compareAndSet(null, e);
-            } catch (Exception e) {
-              genericException.compareAndSet(e, null);
-            }
-          }
-        });
-      }
-    } finally {
-      ExecutorUtil.interruptibleShutdown(executor);
+              }));
+    }
+
+    try {
+      Futures.allAsList(futures).get();
+    } catch (ExecutionException e) {
+      throw new IllegalStateException(e);
     }
 
     Throwables.propagateIfInstanceOf(interrupt.get(), InterruptedException.class);