diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
index 5c22a05..27475db 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
@@ -126,4 +126,9 @@
     return result;
   }
 
+  @Override
+  public Iterable<SkyKey> getCurrentlyAvailableNodes(Iterable<SkyKey> keys, Reason reason) {
+    return graph.getCurrentlyAvailableNodes(keys, reason);
+  }
+
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java
index 77b1259..71c3ad3 100644
--- a/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java
+++ b/src/main/java/com/google/devtools/build/skyframe/InMemoryGraphImpl.java
@@ -17,6 +17,7 @@
 import com.google.common.base.Function;
 import com.google.common.base.Predicates;
 import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.MapMaker;
 import com.google.common.collect.Maps;
 import java.util.Collections;
@@ -127,4 +128,15 @@
   boolean keepsEdges() {
     return keepEdges;
   }
+
+  @Override
+  public Iterable<SkyKey> getCurrentlyAvailableNodes(Iterable<SkyKey> keys, Reason reason) {
+    ImmutableSet.Builder<SkyKey> builder = ImmutableSet.builder();
+    for (SkyKey key : keys) {
+      if (get(null, reason, key) != null) {
+        builder.add(key);
+      }
+    }
+    return builder.build();
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
index 0286844..7c4971e 100644
--- a/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/QueryableGraph.java
@@ -49,6 +49,17 @@
       @Nullable SkyKey requestor, Reason reason, Iterable<SkyKey> keys) throws InterruptedException;
 
   /**
+   * Examines all the given keys. Returns an iterable of keys whose corresponding nodes are
+   * currently available to be fetched.
+   *
+   * <p>Note: An unavailable node does not mean it is not in the graph. It only means it's not ready
+   * to be fetched immediately.
+   *
+   * @param reason the reason the nodes are being requested.
+   */
+  Iterable<SkyKey> getCurrentlyAvailableNodes(Iterable<SkyKey> keys, Reason reason);
+
+  /**
    * The reason that a node is being looked up in the Skyframe graph.
    *
    * <p>Alternate graph implementations may wish to make use of this information.
diff --git a/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
index 9f71f1f..240ea7c 100644
--- a/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
@@ -15,6 +15,7 @@
 
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.skyframe.QueryableGraph.Reason;
 import java.util.Collection;
 import java.util.Map;
 import javax.annotation.Nullable;
@@ -80,6 +81,15 @@
    */
   Map<SkyKey, Iterable<SkyKey>> getReverseDeps(Iterable<SkyKey> keys) throws InterruptedException;
 
+  /**
+   * Examines all the given keys. Returns an iterable of keys whose corresponding nodes are
+   * currently available to be fetched.
+   *
+   * <p>Note: An unavailable node does not mean it is not in the graph. It only means it's not ready
+   * to be fetched immediately.
+   */
+  Iterable<SkyKey> getCurrentlyAvailableNodes(Iterable<SkyKey> keys, Reason reason);
+
   /** Provides a WalkableGraph on demand after preparing it. */
   interface WalkableGraphFactory {
     EvaluationResult<SkyValue> prepareAndGet(Collection<String> roots, String offset,