diff --git a/java/com/google/gerrit/index/query/AndCardinalPredicate.java b/java/com/google/gerrit/index/query/AndCardinalPredicate.java
new file mode 100644
index 0000000..cf0e8c3
--- /dev/null
+++ b/java/com/google/gerrit/index/query/AndCardinalPredicate.java
@@ -0,0 +1,48 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.index.query;
+
+import java.util.Collection;
+import java.util.Optional;
+
+public class AndCardinalPredicate<T> extends AndPredicate<T> implements HasCardinality {
+  private final int cardinality;
+
+  public AndCardinalPredicate(Collection<? extends Predicate<T>> that) {
+    super(that);
+    Optional<Predicate<T>> atLeastOneCardinalPredicate =
+        getChildren().stream().filter(p -> (p instanceof HasCardinality)).findAny();
+    if (!atLeastOneCardinalPredicate.isPresent()) {
+      throw new IllegalArgumentException("No HasCardinality Found");
+    }
+    int minCardinality = Integer.MAX_VALUE;
+    for (Predicate<T> child : getChildren()) {
+      if (child instanceof HasCardinality) {
+        minCardinality = Math.min(((HasCardinality) child).getCardinality(), minCardinality);
+      }
+    }
+    cardinality = minCardinality;
+  }
+
+  @Override
+  public Predicate<T> copy(Collection<? extends Predicate<T>> children) {
+    return new AndCardinalPredicate<>(children);
+  }
+
+  @Override
+  public int getCardinality() {
+    return cardinality;
+  }
+}
diff --git a/java/com/google/gerrit/index/query/DataSource.java b/java/com/google/gerrit/index/query/DataSource.java
index 262ed57..3b83478 100644
--- a/java/com/google/gerrit/index/query/DataSource.java
+++ b/java/com/google/gerrit/index/query/DataSource.java
@@ -14,10 +14,7 @@
 
 package com.google.gerrit.index.query;
 
-public interface DataSource<T> {
-  /** Returns an estimate of the number of results from {@link #read()}. */
-  int getCardinality();
-
+public interface DataSource<T> extends HasCardinality {
   /** Returns read from the index and return the results. */
   ResultSet<T> read();
 
diff --git a/java/com/google/gerrit/index/query/HasCardinality.java b/java/com/google/gerrit/index/query/HasCardinality.java
new file mode 100644
index 0000000..140ba4b
--- /dev/null
+++ b/java/com/google/gerrit/index/query/HasCardinality.java
@@ -0,0 +1,20 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.index.query;
+
+public interface HasCardinality {
+  /** Returns an estimate of the number of results a source can return. */
+  int getCardinality();
+}
diff --git a/java/com/google/gerrit/index/query/OrCardinalPredicate.java b/java/com/google/gerrit/index/query/OrCardinalPredicate.java
new file mode 100644
index 0000000..9d7913a
--- /dev/null
+++ b/java/com/google/gerrit/index/query/OrCardinalPredicate.java
@@ -0,0 +1,48 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.index.query;
+
+import java.util.Collection;
+import java.util.Optional;
+
+public class OrCardinalPredicate<T> extends OrPredicate<T> implements HasCardinality {
+  private final int cardinality;
+
+  public OrCardinalPredicate(Collection<? extends Predicate<T>> that) {
+    super(that);
+    Optional<Predicate<T>> nonHasCardinality =
+        getChildren().stream().filter(p -> !(p instanceof HasCardinality)).findAny();
+    if (nonHasCardinality.isPresent()) {
+      throw new IllegalArgumentException("No HasCardinality: " + nonHasCardinality.get());
+    }
+    int aggregateCardinality = 0;
+    for (Predicate<T> p : getChildren()) {
+      if (p instanceof HasCardinality) {
+        aggregateCardinality += ((HasCardinality) p).getCardinality();
+      }
+    }
+    cardinality = aggregateCardinality;
+  }
+
+  @Override
+  public Predicate<T> copy(Collection<? extends Predicate<T>> children) {
+    return new OrCardinalPredicate<>(children);
+  }
+
+  @Override
+  public int getCardinality() {
+    return cardinality;
+  }
+}
diff --git a/java/com/google/gerrit/lucene/LuceneChangeIndex.java b/java/com/google/gerrit/lucene/LuceneChangeIndex.java
index d40dfb4..daa921c 100644
--- a/java/com/google/gerrit/lucene/LuceneChangeIndex.java
+++ b/java/com/google/gerrit/lucene/LuceneChangeIndex.java
@@ -44,6 +44,7 @@
 import com.google.gerrit.index.QueryOptions;
 import com.google.gerrit.index.Schema;
 import com.google.gerrit.index.query.FieldBundle;
+import com.google.gerrit.index.query.HasCardinality;
 import com.google.gerrit.index.query.Predicate;
 import com.google.gerrit.index.query.QueryParseException;
 import com.google.gerrit.index.query.ResultSet;
@@ -344,7 +345,10 @@
 
     @Override
     public int getCardinality() {
-      return 10; // TODO(dborowitz): estimate from Lucene?
+      if (predicate instanceof HasCardinality) {
+        return ((HasCardinality) predicate).getCardinality();
+      }
+      return 10;
     }
 
     @Override
diff --git a/java/com/google/gerrit/server/index/change/ChangeIndexRewriter.java b/java/com/google/gerrit/server/index/change/ChangeIndexRewriter.java
index e255196..8b75872 100644
--- a/java/com/google/gerrit/server/index/change/ChangeIndexRewriter.java
+++ b/java/com/google/gerrit/server/index/change/ChangeIndexRewriter.java
@@ -26,10 +26,13 @@
 import com.google.gerrit.index.IndexRewriter;
 import com.google.gerrit.index.QueryOptions;
 import com.google.gerrit.index.Schema;
+import com.google.gerrit.index.query.AndCardinalPredicate;
 import com.google.gerrit.index.query.AndPredicate;
+import com.google.gerrit.index.query.HasCardinality;
 import com.google.gerrit.index.query.IndexPredicate;
 import com.google.gerrit.index.query.LimitPredicate;
 import com.google.gerrit.index.query.NotPredicate;
+import com.google.gerrit.index.query.OrCardinalPredicate;
 import com.google.gerrit.index.query.OrPredicate;
 import com.google.gerrit.index.query.Predicate;
 import com.google.gerrit.index.query.QueryParseException;
@@ -260,7 +263,8 @@
       throws QueryParseException {
     if (isIndexed.cardinality() == 1) {
       int i = isIndexed.nextSetBit(0);
-      newChildren.add(0, new IndexedChangeQuery(index, newChildren.remove(i), opts));
+      Predicate<ChangeData> indexed = newChildren.remove(i);
+      newChildren.add(0, new IndexedChangeQuery(index, copy(indexed, indexed.getChildren()), opts));
       return copy(in, newChildren);
     }
 
@@ -278,7 +282,7 @@
         all.add(c);
       }
     }
-    all.add(0, new IndexedChangeQuery(index, in.copy(indexed), opts));
+    all.add(0, new IndexedChangeQuery(index, copy(in, indexed), opts));
     return copy(in, all);
   }
 
@@ -289,12 +293,22 @@
       if (atLeastOneChangeDataSource.isPresent()) {
         return new AndChangeSource(all, config);
       }
+      Optional<Predicate<ChangeData>> atLeastOneCardinalPredicate =
+          all.stream().filter(p -> (p instanceof HasCardinality)).findAny();
+      if (atLeastOneCardinalPredicate.isPresent()) {
+        return new AndCardinalPredicate<>(all);
+      }
     } else if (in instanceof OrPredicate) {
       Optional<Predicate<ChangeData>> nonChangeDataSource =
           all.stream().filter(p -> !(p instanceof ChangeDataSource)).findAny();
       if (!nonChangeDataSource.isPresent()) {
         return new OrSource(all);
       }
+      Optional<Predicate<ChangeData>> nonHasCardinality =
+          all.stream().filter(p -> !(p instanceof HasCardinality)).findAny();
+      if (!nonHasCardinality.isPresent()) {
+        return new OrCardinalPredicate<>(all);
+      }
     }
     return in.copy(all);
   }
diff --git a/java/com/google/gerrit/server/query/change/ChangeIndexCardinalPredicate.java b/java/com/google/gerrit/server/query/change/ChangeIndexCardinalPredicate.java
new file mode 100644
index 0000000..6540d80
--- /dev/null
+++ b/java/com/google/gerrit/server/query/change/ChangeIndexCardinalPredicate.java
@@ -0,0 +1,39 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.server.query.change;
+
+import com.google.gerrit.index.FieldDef;
+import com.google.gerrit.index.query.HasCardinality;
+
+public class ChangeIndexCardinalPredicate extends ChangeIndexPredicate implements HasCardinality {
+  protected final int cardinality;
+
+  protected ChangeIndexCardinalPredicate(
+      FieldDef<ChangeData, ?> def, String value, int cardinality) {
+    super(def, value);
+    this.cardinality = cardinality;
+  }
+
+  protected ChangeIndexCardinalPredicate(
+      FieldDef<ChangeData, ?> def, String name, String value, int cardinality) {
+    super(def, name, value);
+    this.cardinality = cardinality;
+  }
+
+  @Override
+  public int getCardinality() {
+    return cardinality;
+  }
+}
diff --git a/java/com/google/gerrit/server/query/change/ChangePredicates.java b/java/com/google/gerrit/server/query/change/ChangePredicates.java
index ce17b31..259239b 100644
--- a/java/com/google/gerrit/server/query/change/ChangePredicates.java
+++ b/java/com/google/gerrit/server/query/change/ChangePredicates.java
@@ -58,7 +58,7 @@
    * com.google.gerrit.entities.Change.Id}.
    */
   public static Predicate<ChangeData> revertOf(Change.Id revertOf) {
-    return new ChangeIndexPredicate(ChangeField.REVERT_OF, revertOf.toString());
+    return new ChangeIndexCardinalPredicate(ChangeField.REVERT_OF, revertOf.toString(), 1);
   }
 
   /**
@@ -84,7 +84,7 @@
   public static Predicate<ChangeData> draftBy(
       boolean computeFromAllUsersRepository, CommentsUtil commentsUtil, Account.Id id) {
     if (!computeFromAllUsersRepository) {
-      return new ChangeIndexPredicate(ChangeField.DRAFTBY, id.toString());
+      return new ChangeIndexCardinalPredicate(ChangeField.DRAFTBY, id.toString(), 20);
     }
     Set<Predicate<ChangeData>> changeIdPredicates =
         commentsUtil.getChangesWithDrafts(id).stream()
@@ -137,8 +137,8 @@
    * com.google.gerrit.entities.Change.Id}.
    */
   public static Predicate<ChangeData> id(Change.Id id) {
-    return new ChangeIndexPredicate(
-        ChangeField.LEGACY_ID, ChangeQueryBuilder.FIELD_CHANGE, id.toString());
+    return new ChangeIndexCardinalPredicate(
+        ChangeField.LEGACY_ID, ChangeQueryBuilder.FIELD_CHANGE, id.toString(), 1);
   }
 
   /**
@@ -146,8 +146,8 @@
    * com.google.gerrit.entities.Change.Id}.
    */
   public static Predicate<ChangeData> idStr(Change.Id id) {
-    return new ChangeIndexPredicate(
-        ChangeField.LEGACY_ID_STR, ChangeQueryBuilder.FIELD_CHANGE, id.toString());
+    return new ChangeIndexCardinalPredicate(
+        ChangeField.LEGACY_ID_STR, ChangeQueryBuilder.FIELD_CHANGE, id.toString(), 1);
   }
 
   /**
@@ -155,7 +155,7 @@
    * com.google.gerrit.entities.Account.Id}.
    */
   public static Predicate<ChangeData> owner(Account.Id id) {
-    return new ChangeIndexPredicate(ChangeField.OWNER, id.toString());
+    return new ChangeIndexCardinalPredicate(ChangeField.OWNER, id.toString(), 5000);
   }
 
   /**
@@ -189,12 +189,12 @@
    * com.google.gerrit.entities.Project.NameKey}.
    */
   public static Predicate<ChangeData> project(Project.NameKey id) {
-    return new ChangeIndexPredicate(ChangeField.PROJECT, id.get());
+    return new ChangeIndexCardinalPredicate(ChangeField.PROJECT, id.get(), 1_000_000);
   }
 
   /** Returns a predicate that matches changes targeted at the provided {@code refName}. */
   public static Predicate<ChangeData> ref(String refName) {
-    return new ChangeIndexPredicate(ChangeField.REF, refName);
+    return new ChangeIndexCardinalPredicate(ChangeField.REF, refName, 10_000);
   }
 
   /** Returns a predicate that matches changes in the provided {@code topic}. */
@@ -287,7 +287,7 @@
 
   /** Returns a predicate that matches changes with the provided {@code trackingId}. */
   public static Predicate<ChangeData> trackingId(String trackingId) {
-    return new ChangeIndexPredicate(ChangeField.TR, trackingId);
+    return new ChangeIndexCardinalPredicate(ChangeField.TR, trackingId, 5);
   }
 
   /** Returns a predicate that matches changes authored by the provided {@code exactAuthor}. */
@@ -319,7 +319,7 @@
 
   /** Returns a predicate that matches changes whose ID starts with the provided {@code id}. */
   public static Predicate<ChangeData> idPrefix(String id) {
-    return new ChangeIndexPredicate(ChangeField.ID, id);
+    return new ChangeIndexCardinalPredicate(ChangeField.ID, id, 5);
   }
 
   /**
@@ -336,9 +336,9 @@
    */
   public static Predicate<ChangeData> commitPrefix(String commitId) {
     if (commitId.length() == ObjectIds.STR_LEN) {
-      return new ChangeIndexPredicate(ChangeField.EXACT_COMMIT, commitId);
+      return new ChangeIndexCardinalPredicate(ChangeField.EXACT_COMMIT, commitId, 5);
     }
-    return new ChangeIndexPredicate(ChangeField.COMMIT, commitId);
+    return new ChangeIndexCardinalPredicate(ChangeField.COMMIT, commitId, 5);
   }
 
   /**
diff --git a/java/com/google/gerrit/server/query/change/ChangeStatusPredicate.java b/java/com/google/gerrit/server/query/change/ChangeStatusPredicate.java
index 9aff0c5..66c136f 100644
--- a/java/com/google/gerrit/server/query/change/ChangeStatusPredicate.java
+++ b/java/com/google/gerrit/server/query/change/ChangeStatusPredicate.java
@@ -20,6 +20,7 @@
 import com.google.gerrit.common.Nullable;
 import com.google.gerrit.entities.Change;
 import com.google.gerrit.entities.Change.Status;
+import com.google.gerrit.index.query.HasCardinality;
 import com.google.gerrit.index.query.Predicate;
 import com.google.gerrit.index.query.QueryParseException;
 import com.google.gerrit.server.index.change.ChangeField;
@@ -39,7 +40,7 @@
  *
  * <p>Status names are looked up by prefix case-insensitively.
  */
-public final class ChangeStatusPredicate extends ChangeIndexPredicate {
+public final class ChangeStatusPredicate extends ChangeIndexPredicate implements HasCardinality {
   private static final String INVALID_STATUS = "__invalid__";
   static final Predicate<ChangeData> NONE = new ChangeStatusPredicate(null);
 
@@ -139,4 +140,19 @@
   public String toString() {
     return getOperator() + ":" + getValue();
   }
+
+  @Override
+  public int getCardinality() {
+    if (getStatus() == null) {
+      return 0;
+    }
+    switch (getStatus()) {
+      case MERGED:
+        return 50_000;
+      case ABANDONED:
+        return 50_000;
+      default:
+        return 2000;
+    }
+  }
 }
diff --git a/java/com/google/gerrit/server/query/change/ReviewerPredicate.java b/java/com/google/gerrit/server/query/change/ReviewerPredicate.java
index 142e956..57f5213 100644
--- a/java/com/google/gerrit/server/query/change/ReviewerPredicate.java
+++ b/java/com/google/gerrit/server/query/change/ReviewerPredicate.java
@@ -17,11 +17,12 @@
 import static com.google.common.base.Preconditions.checkArgument;
 
 import com.google.gerrit.entities.Account;
+import com.google.gerrit.index.query.HasCardinality;
 import com.google.gerrit.index.query.Predicate;
 import com.google.gerrit.server.index.change.ChangeField;
 import com.google.gerrit.server.notedb.ReviewerStateInternal;
 
-public class ReviewerPredicate extends ChangeIndexPredicate {
+public class ReviewerPredicate extends ChangeIndexPredicate implements HasCardinality {
   protected static Predicate<ChangeData> forState(Account.Id id, ReviewerStateInternal state) {
     checkArgument(state != ReviewerStateInternal.REMOVED, "can't query by removed reviewer");
     return new ReviewerPredicate(state, id);
@@ -52,4 +53,9 @@
   public boolean match(ChangeData cd) {
     return cd.reviewers().asTable().get(state, id) != null;
   }
+
+  @Override
+  public int getCardinality() {
+    return 5000;
+  }
 }
diff --git a/java/com/google/gerrit/server/query/change/StarPredicate.java b/java/com/google/gerrit/server/query/change/StarPredicate.java
index 4a8fe43..548ab29 100644
--- a/java/com/google/gerrit/server/query/change/StarPredicate.java
+++ b/java/com/google/gerrit/server/query/change/StarPredicate.java
@@ -15,10 +15,11 @@
 package com.google.gerrit.server.query.change;
 
 import com.google.gerrit.entities.Account;
+import com.google.gerrit.index.query.HasCardinality;
 import com.google.gerrit.server.StarredChangesUtil;
 import com.google.gerrit.server.index.change.ChangeField;
 
-public class StarPredicate extends ChangeIndexPredicate {
+public class StarPredicate extends ChangeIndexPredicate implements HasCardinality {
   protected final Account.Id accountId;
   protected final String label;
 
@@ -34,6 +35,11 @@
   }
 
   @Override
+  public int getCardinality() {
+    return 10;
+  }
+
+  @Override
   public String toString() {
     return ChangeQueryBuilder.FIELD_STAR + ":" + label;
   }
diff --git a/java/com/google/gerrit/server/restapi/change/CherryPickChange.java b/java/com/google/gerrit/server/restapi/change/CherryPickChange.java
index cb08c11..6a25095 100644
--- a/java/com/google/gerrit/server/restapi/change/CherryPickChange.java
+++ b/java/com/google/gerrit/server/restapi/change/CherryPickChange.java
@@ -515,8 +515,10 @@
                     ins.getPatchSetId(), sourceBranch, sourceCommit, cherryPickCommit)
                 : "Uploaded patch set 1.") // For revert commits, the message should not include
         // cherry-pick information.
-        .setTopic(topic)
-        .setCherryPickOf(sourcePatchSetId);
+        .setTopic(topic);
+    if (revertOf == null) {
+      ins.setCherryPickOf(sourcePatchSetId);
+    }
     if (input.keepReviewers && sourceChange != null) {
       ReviewerSet reviewerSet =
           approvalsUtil.getReviewers(changeNotesFactory.createChecked(sourceChange));
diff --git a/java/com/google/gerrit/server/restapi/change/RevertSubmission.java b/java/com/google/gerrit/server/restapi/change/RevertSubmission.java
index 8f29d82..4e5027b 100644
--- a/java/com/google/gerrit/server/restapi/change/RevertSubmission.java
+++ b/java/com/google/gerrit/server/restapi/change/RevertSubmission.java
@@ -306,7 +306,7 @@
       if (cherryPickInput.base.equals(changeNotes.getCurrentPatchSet().commitId().getName())) {
         // This is the code in case this is the first revert of this project + branch, and the
         // revert would be on top of the change being reverted.
-        craeteNormalRevert(revertInput, changeNotes, timestamp);
+        createNormalRevert(revertInput, changeNotes, timestamp);
       } else {
         createCherryPickedRevert(revertInput, project, changeNotes, timestamp);
       }
@@ -345,7 +345,7 @@
     }
   }
 
-  private void craeteNormalRevert(
+  private void createNormalRevert(
       RevertInput revertInput, ChangeNotes changeNotes, Instant timestamp)
       throws IOException, RestApiException, UpdateException, ConfigInvalidException {
 
diff --git a/javatests/com/google/gerrit/acceptance/api/change/RevertIT.java b/javatests/com/google/gerrit/acceptance/api/change/RevertIT.java
index e00a137..407d04e 100644
--- a/javatests/com/google/gerrit/acceptance/api/change/RevertIT.java
+++ b/javatests/com/google/gerrit/acceptance/api/change/RevertIT.java
@@ -1082,8 +1082,10 @@
         .isEqualTo(sha1FirstRevert);
     assertThat(revertChanges.get(0).get().revertOf)
         .isEqualTo(secondResult.getChange().change().getChangeId());
+    assertThat(revertChanges.get(0).get().cherryPickOfChange).isNull();
     assertThat(revertChanges.get(1).get().revertOf)
         .isEqualTo(firstResult.getChange().change().getChangeId());
+    assertThat(revertChanges.get(0).get().cherryPickOfChange).isNull();
     assertThat(revertChanges.get(0).current().files().get("b.txt").linesDeleted).isEqualTo(1);
     assertThat(revertChanges.get(1).current().files().get("a.txt").linesDeleted).isEqualTo(1);
 
diff --git a/javatests/com/google/gerrit/index/query/AndCardinalPredicateTest.java b/javatests/com/google/gerrit/index/query/AndCardinalPredicateTest.java
new file mode 100644
index 0000000..f2d4e03
--- /dev/null
+++ b/javatests/com/google/gerrit/index/query/AndCardinalPredicateTest.java
@@ -0,0 +1,36 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.index.query;
+
+import static com.google.common.truth.Truth.assertThat;
+import static com.google.gerrit.testing.GerritJUnit.assertThrows;
+
+import com.google.common.collect.Lists;
+import com.google.gerrit.server.query.change.ChangeData;
+import org.junit.Test;
+
+public class AndCardinalPredicateTest extends PredicateTest {
+  @Test
+  public void ensureAtLeastOneChildHasCardinality() {
+    TestMatchablePredicate<ChangeData> p1 = new TestMatchablePredicate<>("predicate1", "foo", 1);
+    TestMatchablePredicate<ChangeData> p2 = new TestMatchablePredicate<>("predicate2", "foo", 1);
+
+    IllegalArgumentException thrown =
+        assertThrows(
+            IllegalArgumentException.class,
+            () -> new AndCardinalPredicate<>(Lists.newArrayList(p1, p2)));
+    assertThat(thrown).hasMessageThat().contains("No HasCardinality Found");
+  }
+}
diff --git a/javatests/com/google/gerrit/index/query/OrCardinalPredicateTest.java b/javatests/com/google/gerrit/index/query/OrCardinalPredicateTest.java
new file mode 100644
index 0000000..5f7d048
--- /dev/null
+++ b/javatests/com/google/gerrit/index/query/OrCardinalPredicateTest.java
@@ -0,0 +1,36 @@
+// Copyright (C) 2022 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gerrit.index.query;
+
+import static com.google.common.truth.Truth.assertThat;
+import static com.google.gerrit.testing.GerritJUnit.assertThrows;
+
+import com.google.common.collect.Lists;
+import com.google.gerrit.server.query.change.ChangeData;
+import org.junit.Test;
+
+public class OrCardinalPredicateTest extends PredicateTest {
+  @Test
+  public void ensureAllChildrenAreHasCardinal() {
+    TestMatchablePredicate<ChangeData> p1 = new TestCardinalPredicate<>("predicate1", "foo", 10);
+    TestMatchablePredicate<ChangeData> p2 = new TestMatchablePredicate<>("predicate2", "foo", 1);
+
+    IllegalArgumentException thrown =
+        assertThrows(
+            IllegalArgumentException.class,
+            () -> new OrCardinalPredicate<>(Lists.newArrayList(p1, p2)));
+    assertThat(thrown).hasMessageThat().contains("No HasCardinality");
+  }
+}
diff --git a/javatests/com/google/gerrit/index/query/PredicateTest.java b/javatests/com/google/gerrit/index/query/PredicateTest.java
index b8e0fbb..d789201 100644
--- a/javatests/com/google/gerrit/index/query/PredicateTest.java
+++ b/javatests/com/google/gerrit/index/query/PredicateTest.java
@@ -44,6 +44,18 @@
     }
   }
 
+  protected static class TestCardinalPredicate<T> extends TestMatchablePredicate<T>
+      implements HasCardinality {
+    protected TestCardinalPredicate(String name, String value, int cost) {
+      super(name, value, cost);
+    }
+
+    @Override
+    public int getCardinality() {
+      return 1;
+    }
+  }
+
   protected static class TestMatchablePredicate<T> extends TestPredicate<T>
       implements Matchable<T> {
     protected int cost;
diff --git a/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java b/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java
index cd3958d..bcd0add 100644
--- a/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java
+++ b/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java
@@ -16,6 +16,7 @@
 
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.gerrit.common.data.GlobalCapability.DEFAULT_MAX_QUERY_LIMIT;
+import static com.google.gerrit.entities.Change.Status.ABANDONED;
 import static com.google.gerrit.entities.Change.Status.MERGED;
 import static com.google.gerrit.entities.Change.Status.NEW;
 import static com.google.gerrit.index.query.Predicate.and;
@@ -27,7 +28,9 @@
 import com.google.gerrit.entities.Change;
 import com.google.gerrit.index.IndexConfig;
 import com.google.gerrit.index.QueryOptions;
+import com.google.gerrit.index.query.AndCardinalPredicate;
 import com.google.gerrit.index.query.AndPredicate;
+import com.google.gerrit.index.query.OrCardinalPredicate;
 import com.google.gerrit.index.query.OrPredicate;
 import com.google.gerrit.index.query.Predicate;
 import com.google.gerrit.index.query.QueryParseException;
@@ -71,7 +74,12 @@
     assertThat(AndChangeSource.class).isSameInstanceAs(out.getClass());
     assertThat(out.getChildren())
         .containsExactly(
-            query(Predicate.or(ChangeStatusPredicate.open(), ChangeStatusPredicate.closed())), in)
+            query(
+                orCardinal(
+                    ChangeStatusPredicate.forStatus(NEW),
+                    ChangeStatusPredicate.forStatus(MERGED),
+                    ChangeStatusPredicate.forStatus(ABANDONED))),
+            in)
         .inOrder();
   }
 
@@ -88,7 +96,12 @@
     assertThat(AndChangeSource.class).isSameInstanceAs(out.getClass());
     assertThat(out.getChildren())
         .containsExactly(
-            query(Predicate.or(ChangeStatusPredicate.open(), ChangeStatusPredicate.closed())), in)
+            query(
+                orCardinal(
+                    ChangeStatusPredicate.forStatus(NEW),
+                    ChangeStatusPredicate.forStatus(MERGED),
+                    ChangeStatusPredicate.forStatus(ABANDONED))),
+            in)
         .inOrder();
   }
 
@@ -156,7 +169,7 @@
     Predicate<ChangeData> out = rewrite(in);
     assertThat(AndChangeSource.class).isSameInstanceAs(out.getClass());
     assertThat(out.getChildren())
-        .containsExactly(query(and(parse("status:new"), parse("file:a"))), parse("bar:p"))
+        .containsExactly(query(andCardinal(parse("status:new"), parse("file:a"))), parse("bar:p"))
         .inOrder();
   }
 
@@ -166,7 +179,7 @@
     Predicate<ChangeData> out = rewrite(in);
     assertThat(out.getClass()).isEqualTo(AndChangeSource.class);
     assertThat(out.getChildren())
-        .containsExactly(query(and(parse("status:new"), parse("file:a"))), parse("bar:p"))
+        .containsExactly(query(andCardinal(parse("status:new"), parse("file:a"))), parse("bar:p"))
         .inOrder();
   }
 
@@ -260,6 +273,16 @@
     return new AndChangeSource(Arrays.asList(preds), IndexConfig.createDefault());
   }
 
+  @SafeVarargs
+  private static AndCardinalPredicate<ChangeData> andCardinal(Predicate<ChangeData>... preds) {
+    return new AndCardinalPredicate<>(Arrays.asList(preds));
+  }
+
+  @SafeVarargs
+  private static OrCardinalPredicate<ChangeData> orCardinal(Predicate<ChangeData>... preds) {
+    return new OrCardinalPredicate<>(Arrays.asList(preds));
+  }
+
   private Predicate<ChangeData> rewrite(Predicate<ChangeData> in) throws QueryParseException {
     return rewrite.rewrite(in, options(0, DEFAULT_MAX_QUERY_LIMIT));
   }