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));
}
