Add AndCardinalPredicate and OrCardinalPredicate Before this change, IndexSource derived cardinality from predicate which implement HasCardinality. Since AndPredicate and OrPredicate does not return cardinality, IndexSource defaults to 10 when query comprises more than one predicate. Due to this behavior, AndSource chooses IndexSource almost always when query contains more than one index predicate. Add AndCardinalPredicate and OrCardinalPredicate which implement HasCardinality's getCardinality(). AndCardinalPredicate will return minimum of all the cardinalities of its children. OrCardinalPredicate will return sum of all the cardinalities of its children. Enhance index rewritter to return AndCardinalPredicate when there is at least one predicate which implements HasCardinality. Similarly, return OrCardinalPredicate when all the children implement HasCardinality. This helps AndSource to choose the right source more often. Unfortunately there are no operators which are datasources other than Index in the Core as of now. We at Qualcomm have a datasource operator in a plugin which takes a bug number and queries the bug tracker's DB for changes related to that bug number. Suppose this operator (say issue:123) returns around 15 changes. On a 3.4 test site against LUCENE which contains ~20K open changes, ~2.8M merged changes, the performance of, query "issue:123 status:open age:1d" before: 4.5s, 4.4s, 4.4s after: 0.29s, 0.26s, 0.23s query "issue:123 status:merged age:1d" before: 11m, 11m, 11m after: 0.23s, 0.20s, 0.25s Release-Notes: AndSource chooses right source more often Change-Id: Id79bea6f512c7673f3183f39a187debec7ce34f7

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/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/server/index/change/ChangeIndexRewriter.java b/java/com/google/gerrit/server/index/change/ChangeIndexRewriter.java
index bca620e..1f270b0 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;
@@ -276,7 +279,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);
   }
 
@@ -287,12 +290,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/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 bb15cb6..9b70159 100644
--- a/javatests/com/google/gerrit/index/query/PredicateTest.java
+++ b/javatests/com/google/gerrit/index/query/PredicateTest.java

@@ -43,6 +43,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 213c3e6..96fc0d1 100644
--- a/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java
+++ b/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java

@@ -27,6 +27,7 @@
 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.OrPredicate;
 import com.google.gerrit.index.query.Predicate;
@@ -156,7 +157,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 +167,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();
   }
 
@@ -262,6 +263,11 @@
     return new AndChangeSource(Arrays.asList(preds), IndexConfig.createDefault());
   }
 
+  @SafeVarargs
+  private static AndCardinalPredicate<ChangeData> andCardinal(Predicate<ChangeData>... preds) {
+    return new AndCardinalPredicate<>(Arrays.asList(preds));
+  }
+
   private Predicate<ChangeData> rewrite(Predicate<ChangeData> in) throws QueryParseException {
     return rewrite.rewrite(in, options(0, DEFAULT_MAX_QUERY_LIMIT));
   }