diff --git a/src/main/java/com/google/devtools/build/lib/query2/RdepsBoundedVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/RdepsBoundedVisitor.java
index b631ba6..1728977 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/RdepsBoundedVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/RdepsBoundedVisitor.java
@@ -85,7 +85,8 @@
       this.depth = depth;
       this.universe = universe;
       this.depAndRdepAtDepthUniquifier =
-          new UniquifierImpl<>(depAndRdepAtDepth -> depAndRdepAtDepth);
+          new UniquifierImpl<>(
+              depAndRdepAtDepth -> depAndRdepAtDepth, env.getQueryEvaluationParallelismLevel());
       this.validRdepMinDepthUniquifier = env.createMinDepthSkyKeyUniquifier();
       this.callback = callback;
       this.packageSemaphore = packageSemaphore;
diff --git a/src/main/java/com/google/devtools/build/lib/query2/RdepsUnboundedVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/RdepsUnboundedVisitor.java
index 5ff265a..c85043e 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/RdepsUnboundedVisitor.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/RdepsUnboundedVisitor.java
@@ -94,7 +94,8 @@
         MultisetSemaphore<PackageIdentifier> packageSemaphore) {
       this.env = env;
       this.unfilteredUniverse = unfilteredUniverse;
-      this.depAndRdepUniquifier = new UniquifierImpl<>(depAndRdep -> depAndRdep);
+      this.depAndRdepUniquifier =
+          new UniquifierImpl<>(depAndRdep -> depAndRdep, env.getQueryEvaluationParallelismLevel());
       this.validRdepUniquifier = env.createSkyKeyUniquifier();
       this.callback = callback;
       this.packageSemaphore = packageSemaphore;
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 b26cc88..5c168958 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
@@ -661,7 +661,7 @@
   @ThreadSafe
   @Override
   public NonExceptionalUniquifier<Target> createUniquifier() {
-    return new UniquifierImpl<>(TargetKeyExtractor.INSTANCE);
+    return new UniquifierImpl<>(TargetKeyExtractor.INSTANCE, queryEvaluationParallelismLevel);
   }
 
   @ThreadSafe
@@ -679,7 +679,7 @@
 
   @ThreadSafe
   public Uniquifier<SkyKey> createSkyKeyUniquifier() {
-    return new UniquifierImpl<>(SkyKeyKeyExtractor.INSTANCE);
+    return new UniquifierImpl<>(SkyKeyKeyExtractor.INSTANCE, queryEvaluationParallelismLevel);
   }
 
   private ImmutableSet<PathFragment> getBlacklistedExcludes(TargetPatternKey targetPatternKey)
@@ -821,6 +821,10 @@
     return new FakeLoadTarget(label, pkg);
   }
 
+  int getQueryEvaluationParallelismLevel() {
+    return queryEvaluationParallelismLevel;
+  }
+
   @ThreadSafe
   @Override
   public TargetAccessor<Target> getAccessor() {
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java
index fe072b6..32843e9 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryUtil.java
@@ -264,8 +264,19 @@
     private final Set<K> alreadySeen;
 
     public UniquifierImpl(KeyExtractor<T, K> extractor) {
+      this(extractor, /*queryEvaluationParallelismLevel=*/ 1);
+    }
+
+    public UniquifierImpl(KeyExtractor<T, K> extractor, int queryEvaluationParallelismLevel) {
       this.extractor = extractor;
-      this.alreadySeen = Collections.newSetFromMap(new ConcurrentHashMap<>());
+      this.alreadySeen =
+          Collections.newSetFromMap(
+              // Note that ConcurrentHashMap sadly only uses these 3 parameters as an *initial*
+              // sizing hint.
+              new ConcurrentHashMap<>(
+                  /*initialCapacity=*/ 16,
+                  /*loadFactor=*/ 0.75f,
+                  /*concurrencyLevel=*/ queryEvaluationParallelismLevel));
     }
 
     @Override