diff --git a/src/main/java/com/google/devtools/build/lib/includescanning/IncludeParser.java b/src/main/java/com/google/devtools/build/lib/includescanning/IncludeParser.java
index 60be6d6..ab79b94 100644
--- a/src/main/java/com/google/devtools/build/lib/includescanning/IncludeParser.java
+++ b/src/main/java/com/google/devtools/build/lib/includescanning/IncludeParser.java
@@ -38,6 +38,7 @@
 import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.profiler.SilentCloseable;
 import com.google.devtools.build.lib.skyframe.ContainingPackageLookupValue;
+import com.google.devtools.build.lib.skyframe.GlobDescriptor;
 import com.google.devtools.build.lib.skyframe.GlobValue;
 import com.google.devtools.build.lib.skyframe.GlobValue.InvalidGlobPatternException;
 import com.google.devtools.build.lib.skyframe.PerBuildSyscallCache;
@@ -50,12 +51,14 @@
 import com.google.devtools.build.skyframe.SkyFunction.Environment;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
+import com.google.devtools.build.skyframe.ValueOrException;
 import java.io.IOException;
 import java.io.InputStream;
 import java.io.InputStreamReader;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.atomic.AtomicReference;
 import java.util.logging.Level;
@@ -247,34 +250,49 @@
     }
 
     /**
-     * Returns the "path" type hinted inclusions for a given path. Callers are responsible for
+     * Returns the "path" type hinted inclusions for the given paths. Callers are responsible for
      * caching.
      */
-    Collection<Artifact> getPathLevelHintedInclusions(PathFragment path, Environment env)
-        throws InterruptedException {
-      return getHintedInclusionsWithSkyframe(Rule.Type.PATH, path, env);
+    Collection<Artifact> getPathLevelHintedInclusions(
+        ImmutableList<PathFragment> paths, Environment env) throws InterruptedException {
+      return getHintedInclusionsWithSkyframe(Rule.Type.PATH, paths, env);
     }
 
     /**
-     * Performs the work of matching a given path against the hints and returns the matching files.
-     * This is semantically different from {@link #getHintedInclusionsLegacy} in that it will not
-     * cross package boundaries.
+     * Performs the work of matching the given paths against the hints and returns the matching
+     * files. This is semantically different from {@link #getHintedInclusionsLegacy} in that it will
+     * not cross package boundaries.
      */
     private Collection<Artifact> getHintedInclusionsWithSkyframe(
-        Rule.Type type, PathFragment path, Environment env) throws InterruptedException {
-      String pathString = path.getPathString();
-      if (!pathString.startsWith(ALLOWED_PREFIX)) {
+        Rule.Type type, ImmutableList<PathFragment> paths, Environment env)
+        throws InterruptedException {
+      ImmutableList<String> pathStrings =
+          paths.stream()
+              .map(PathFragment::getPathString)
+              .filter((p) -> p.startsWith(ALLOWED_PREFIX))
+              .collect(ImmutableList.toImmutableList());
+      if (pathStrings.isEmpty()) {
         return ImmutableList.of();
       }
       // Delay creation until we know we need one. Use a TreeSet to make sure that the results are
       // sorted with a stable order and unique.
       Set<Artifact> hints = null;
+      List<ContainingPackageLookupValue.Key> rulePaths = new ArrayList<>(rules.size());
+      List<String> findFilters = new ArrayList<>(rules.size());
       for (Rule rule : rules) {
         if (type != rule.type) {
           continue;
         }
-        Matcher m = rule.pattern.matcher(pathString);
-        if (!m.matches()) {
+        String firstMatchPathString = null;
+        Matcher m = null;
+        for (String pathString : pathStrings) {
+          m = rule.pattern.matcher(pathString);
+          if (m.matches()) {
+            firstMatchPathString = pathString;
+            break;
+          }
+        }
+        if (firstMatchPathString == null) {
           continue;
         }
         if (hints == null) {
@@ -282,7 +300,8 @@
         }
         PathFragment relativePath = PathFragment.create(m.replaceFirst(rule.findRoot));
         if (LOG_FINE) {
-          logger.fine("hint for " + rule.type + " " + pathString + " root: " + relativePath);
+          logger.fine(
+              "hint for " + rule.type + " " + firstMatchPathString + " root: " + relativePath);
         }
         if (!relativePath.getPathString().startsWith(ALLOWED_PREFIX)) {
           logger.warning(
@@ -292,12 +311,24 @@
                   + ALLOWED_PREFIX);
           continue;
         }
+        rulePaths.add(
+            ContainingPackageLookupValue.key(PackageIdentifier.createInMainRepo(relativePath)));
+        findFilters.add(rule.findFilter);
+      }
+      Map<SkyKey, ValueOrException<NoSuchPackageException>> containingPackageLookupValues =
+          env.getValuesOrThrow(rulePaths, NoSuchPackageException.class);
+      if (env.valuesMissing()) {
+        return null;
+      }
+      List<GlobDescriptor> globKeys = new ArrayList<>(rulePaths.size());
+      for (int i = 0; i < rulePaths.size(); i++) {
         ContainingPackageLookupValue containingPackageLookupValue;
+        ContainingPackageLookupValue.Key relativePathKey = rulePaths.get(i);
+        PathFragment relativePath = relativePathKey.argument().getPackageFragment();
         try {
           containingPackageLookupValue =
-              (ContainingPackageLookupValue) env.getValueOrThrow(ContainingPackageLookupValue.key(
-                  PackageIdentifier.createInMainRepo(relativePath)),
-                  NoSuchPackageException.class);
+              (ContainingPackageLookupValue)
+                  containingPackageLookupValues.get(relativePathKey).get();
         } catch (NoSuchPackageException e) {
           logger.warning(
               "Unexpected exception when looking up containing package for "
@@ -306,45 +337,46 @@
                   + e.getMessage());
           continue;
         }
-        if (env.valuesMissing()) {
-          return null;
-        }
         if (!containingPackageLookupValue.hasContainingPackage()) {
           logger.warning(relativePath + " not contained in any package: skipping");
           continue;
         }
         PathFragment packageFragment =
             containingPackageLookupValue.getContainingPackageName().getPackageFragment();
-        SkyKey globKey;
+        String pattern = findFilters.get(i);
         try {
-          globKey =
+          globKeys.add(
               GlobValue.key(
                   containingPackageLookupValue.getContainingPackageName(),
                   containingPackageLookupValue.getContainingPackageRoot(),
-                  rule.findFilter,
+                  pattern,
                   /* excludeDirs= */ true,
-                  relativePath.relativeTo(packageFragment));
+                  relativePath.relativeTo(packageFragment)));
         } catch (InvalidGlobPatternException e) {
-          env.getListener().handle(
-              Event.warn("Error parsing pattern " + rule.findFilter + " for " + relativePath));
+          env.getListener()
+              .handle(Event.warn("Error parsing pattern " + pattern + " for " + relativePath));
           continue;
         }
-        GlobValue globValue = null;
+      }
+      Map<SkyKey, ValueOrException<IOException>> globResults =
+          env.getValuesOrThrow(globKeys, IOException.class);
+      if (env.valuesMissing()) {
+        return null;
+      }
+      for (Map.Entry<SkyKey, ValueOrException<IOException>> globEntry : globResults.entrySet()) {
+        GlobValue globValue;
+        GlobDescriptor globKey = (GlobDescriptor) globEntry.getKey();
+        PathFragment packageFragment = globKey.getPackageId().getPackageFragment();
         try {
-          globValue =
-              (GlobValue) env.getValueOrThrow(globKey, IOException.class);
+          globValue = (GlobValue) globEntry.getValue().get();
         } catch (IOException e) {
-          logger.warning("Error getting hints for " + relativePath + ": " + e);
+          logger.warning("Error getting hints for " + packageFragment + ": " + e);
           continue;
         }
-        if (env.valuesMissing()) {
-          return null;
-        }
         for (PathFragment file : globValue.getMatches()) {
           hints.add(
               artifactFactory.getSourceArtifact(
-                  packageFragment.getRelative(file),
-                  containingPackageLookupValue.getContainingPackageRoot()));
+                  packageFragment.getRelative(file), globKey.getPackageRoot()));
         }
       }
       return hints == null || hints.isEmpty() ? ImmutableList.<Artifact>of() : hints;
diff --git a/src/main/java/com/google/devtools/build/lib/includescanning/LegacyIncludeScanner.java b/src/main/java/com/google/devtools/build/lib/includescanning/LegacyIncludeScanner.java
index 931eadb..8e97737 100644
--- a/src/main/java/com/google/devtools/build/lib/includescanning/LegacyIncludeScanner.java
+++ b/src/main/java/com/google/devtools/build/lib/includescanning/LegacyIncludeScanner.java
@@ -484,18 +484,16 @@
     Preconditions.checkArgument(mainSource == null || sources.contains(mainSource),
         "The main source '%s' is not part of '%s'", mainSource, sources);
     ImmutableSet.Builder<Artifact> pathHints = null;
+    SkyFunction.Environment env = actionExecutionContext.getEnvironmentForDiscoveringInputs();
     if (parser.getHints() != null) {
       pathHints = ImmutableSet.builderWithExpectedSize(quoteIncludePaths.size());
-      SkyFunction.Environment env = actionExecutionContext.getEnvironmentForDiscoveringInputs();
-      for (PathFragment path : quoteIncludePaths) {
-        Collection<Artifact> artifacts = parser.getHints().getPathLevelHintedInclusions(path, env);
-        if (env.valuesMissing()) {
-          break;
-        }
-        pathHints.addAll(Preconditions.checkNotNull(artifacts, path));
+      Collection<Artifact> artifacts =
+          parser.getHints().getPathLevelHintedInclusions(quoteIncludePaths, env);
+      if (!env.valuesMissing()) {
+        pathHints.addAll(Preconditions.checkNotNull(artifacts, quoteIncludePaths));
       }
     }
-    if (actionExecutionContext.getEnvironmentForDiscoveringInputs().valuesMissing()) {
+    if (env.valuesMissing()) {
       throw new MissingDepException();
     }
 
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java
index c9a341e..f9cfb82 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/ContainingPackageLookupValue.java
@@ -23,6 +23,7 @@
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.skyframe.AbstractSkyKey;
 import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
 /**
@@ -83,9 +84,9 @@
     return message;
   }
 
-  @AutoCodec.VisibleForSerialization
+  /** {@link SkyKey} for {@code ContainingPackageLookupValue}. */
   @AutoCodec
-  static class Key extends AbstractSkyKey<PackageIdentifier> {
+  public static class Key extends AbstractSkyKey<PackageIdentifier> {
     private static final Interner<Key> interner = BlazeInterners.newWeakInterner();
 
     private Key(PackageIdentifier arg) {
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java
index e268135..bcc89fc 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java
@@ -23,7 +23,6 @@
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.devtools.build.lib.vfs.Root;
 import com.google.devtools.build.lib.vfs.UnixGlob;
-import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 
 /** A value corresponding to a glob. */
@@ -75,13 +74,13 @@
   }
 
   /**
-   * Constructs a {@link SkyKey} for a glob lookup. {@code packageName} is assumed to be an existing
-   * package. Trying to glob into a non-package is undefined behavior.
+   * Constructs a {@link GlobDescriptor} for a glob lookup. {@code packageName} is assumed to be an
+   * existing package. Trying to glob into a non-package is undefined behavior.
    *
    * @throws InvalidGlobPatternException if the pattern is not valid.
    */
   @ThreadSafe
-  public static SkyKey key(
+  public static GlobDescriptor key(
       PackageIdentifier packageId,
       Root packageRoot,
       String pattern,
@@ -101,12 +100,12 @@
   }
 
   /**
-   * Constructs a {@link SkyKey} for a glob lookup.
+   * Constructs a {@link GlobDescriptor} for a glob lookup.
    *
    * <p>Do not use outside {@code GlobFunction}.
    */
   @ThreadSafe
-  static SkyKey internalKey(
+  static GlobDescriptor internalKey(
       PackageIdentifier packageId,
       Root packageRoot,
       PathFragment subdir,
@@ -116,21 +115,6 @@
   }
 
   /**
-   * Constructs a {@link SkyKey} for a glob lookup.
-   *
-   * <p>Do not use outside {@code GlobFunction}.
-   */
-  @ThreadSafe
-  static SkyKey internalKey(GlobDescriptor glob, String subdirName) {
-    return internalKey(
-        glob.getPackageId(),
-        glob.getPackageRoot(),
-        glob.getSubdir().getRelative(subdirName),
-        glob.getPattern(),
-        glob.excludeDirs());
-  }
-
-  /**
    * An exception that indicates that a glob pattern is syntactically invalid.
    */
   @ThreadSafe