Fix AndSource to run #match() of predicate whose cost is least

Change I0785952bf2cee, unintentionally introduced a bug where AndSource
no longer picks the predicate based on cost to run #match(). Fix this
issue by sorting the predicates based on cost & cardinality. Add a test
for this scenario. Also fix a test which depends on predicate order.

With a 3.4 test site which contains ~20k open changes, the performance
of query [1] where reviewerin is costlier than destination (3 samples):
  before: 336s, 366s, 402s
  after: 4s, 4s, 4s

[1] status:open reviewerin:ldap/example AND destination:name=foo

With this change, queries containing predicates with poorly defined
costs or cardinalities could perform worse now.

Release-Notes: queries with different and accurate predicate costs are always performant despite ordering
Change-Id: Ib2cb25329fddf9ff931a168fa8b5b9eff8d783c7

5 files changed, 87 insertions, 31 deletions

diff --git a/java/com/google/gerrit/index/query/AndPredicate.java b/java/com/google/gerrit/index/query/AndPredicate.java
index ae13fb3f8b..098bccbde6 100644
--- a/java/com/google/gerrit/index/query/AndPredicate.java
+++ b/java/com/google/gerrit/index/query/AndPredicate.java
@@ -15,15 +15,19 @@
 package com.google.gerrit.index.query;
 
 import static com.google.common.base.Preconditions.checkState;
+import static com.google.common.collect.ImmutableList.toImmutableList;
 
+import com.google.common.collect.ImmutableList;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.List;
 
 /** Requires all predicates to be true. */
-public class AndPredicate<T> extends Predicate<T> implements Matchable<T> {
+public class AndPredicate<T> extends Predicate<T>
+    implements Matchable<T>, Comparator<Predicate<T>> {
   private final List<Predicate<T>> children;
   private final int cost;
 
@@ -35,7 +39,7 @@ public class AndPredicate<T> extends Predicate<T> implements Matchable<T> {
   protected AndPredicate(Collection<? extends Predicate<T>> that) {
     List<Predicate<T>> t = new ArrayList<>(that.size());
     int c = 0;
-    for (Predicate<T> p : that) {
+    for (Predicate<T> p : sort(that)) {
       if (getClass() == p.getClass()) {
         for (Predicate<T> gp : p.getChildren()) {
           t.add(gp);
@@ -114,6 +118,28 @@ public class AndPredicate<T> extends Predicate<T> implements Matchable<T> {
         && getChildren().equals(((Predicate<?>) other).getChildren());
   }
 
+  private ImmutableList<Predicate<T>> sort(Collection<? extends Predicate<T>> that) {
+    return that.stream().sorted(this).collect(toImmutableList());
+  }
+
+  @Override
+  public int compare(Predicate<T> a, Predicate<T> b) {
+    int ai = a instanceof DataSource ? 0 : 1;
+    int bi = b instanceof DataSource ? 0 : 1;
+    int cmp = ai - bi;
+
+    if (cmp == 0) {
+      cmp = a.estimateCost() - b.estimateCost();
+    }
+
+    if (cmp == 0 && a instanceof DataSource && b instanceof DataSource) {
+      DataSource<?> as = (DataSource<?>) a;
+      DataSource<?> bs = (DataSource<?>) b;
+      cmp = as.getCardinality() - bs.getCardinality();
+    }
+    return cmp;
+  }
+
   @Override
   public String toString() {
     final StringBuilder r = new StringBuilder();
diff --git a/java/com/google/gerrit/index/query/AndSource.java b/java/com/google/gerrit/index/query/AndSource.java
index de24df05da..75fbb74adc 100644
--- a/java/com/google/gerrit/index/query/AndSource.java
+++ b/java/com/google/gerrit/index/query/AndSource.java
@@ -15,7 +15,6 @@
 package com.google.gerrit.index.query;
 
 import static com.google.common.base.Preconditions.checkArgument;
-import static com.google.common.collect.ImmutableList.toImmutableList;
 
 import com.google.common.collect.FluentIterable;
 import com.google.common.collect.ImmutableList;
@@ -27,11 +26,9 @@ import com.google.gerrit.index.PaginationType;
 import com.google.gerrit.index.QueryOptions;
 import java.util.ArrayList;
 import java.util.Collection;
-import java.util.Comparator;
 import java.util.List;
 
-public class AndSource<T> extends AndPredicate<T>
-    implements DataSource<T>, Comparator<Predicate<T>> {
+public class AndSource<T> extends AndPredicate<T> implements DataSource<T> {
   protected final DataSource<T> source;
 
   private final IsVisibleToPredicate<T> isVisibleToPredicate;
@@ -69,7 +66,7 @@ public class AndSource<T> extends AndPredicate<T>
     int c = Integer.MAX_VALUE;
     DataSource<T> s = null;
     int minCost = Integer.MAX_VALUE;
-    for (Predicate<T> p : sort(getChildren())) {
+    for (Predicate<T> p : getChildren()) {
       if (p instanceof DataSource) {
         c = Math.min(c, ((DataSource<?>) p).getCardinality());
 
@@ -184,28 +181,6 @@ public class AndSource<T> extends AndPredicate<T>
     return cardinality;
   }
 
-  private ImmutableList<Predicate<T>> sort(Collection<? extends Predicate<T>> that) {
-    return that.stream().sorted(this).collect(toImmutableList());
-  }
-
-  @Override
-  public int compare(Predicate<T> a, Predicate<T> b) {
-    int ai = a instanceof DataSource ? 0 : 1;
-    int bi = b instanceof DataSource ? 0 : 1;
-    int cmp = ai - bi;
-
-    if (cmp == 0) {
-      cmp = a.estimateCost() - b.estimateCost();
-    }
-
-    if (cmp == 0 && a instanceof DataSource && b instanceof DataSource) {
-      DataSource<?> as = (DataSource<?>) a;
-      DataSource<?> bs = (DataSource<?>) b;
-      cmp = as.getCardinality() - bs.getCardinality();
-    }
-    return cmp;
-  }
-
   @SuppressWarnings("unchecked")
   private DataSource<T> toDataSource(Predicate<T> pred) {
     return (DataSource<T>) pred;
diff --git a/javatests/com/google/gerrit/index/query/AndSourceTest.java b/javatests/com/google/gerrit/index/query/AndSourceTest.java
new file mode 100644
index 0000000000..3ae48fb756
--- /dev/null
+++ b/javatests/com/google/gerrit/index/query/AndSourceTest.java
@@ -0,0 +1,33 @@
+// 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 org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.google.common.collect.Lists;
+import org.junit.Test;
+
+public class AndSourceTest extends PredicateTest {
+  @Test
+  public void ensureLowerCostPredicateRunsFirst() {
+    TestMatchablePredicate p1 = new TestMatchablePredicate("predicate1", "foo", 10);
+    TestMatchablePredicate p2 = new TestMatchablePredicate("predicate2", "foo", 1);
+    AndSource<String> andSource = new AndSource<>(Lists.newArrayList(p1, p2), null);
+    andSource.match("bar");
+    assertFalse(p1.ranMatch);
+    assertTrue(p2.ranMatch);
+  }
+}
diff --git a/javatests/com/google/gerrit/index/query/PredicateTest.java b/javatests/com/google/gerrit/index/query/PredicateTest.java
index 3ec7f1362d..e10d7749bb 100644
--- a/javatests/com/google/gerrit/index/query/PredicateTest.java
+++ b/javatests/com/google/gerrit/index/query/PredicateTest.java
@@ -18,7 +18,29 @@ import org.junit.Ignore;
 
 @Ignore
 public abstract class PredicateTest {
-  protected static final class TestPredicate extends OperatorPredicate<String> {
+  protected static final class TestMatchablePredicate extends TestPredicate
+      implements Matchable<String> {
+    protected int cost;
+    protected boolean ranMatch = false;
+
+    protected TestMatchablePredicate(String name, String value, int cost) {
+      super(name, value);
+      this.cost = cost;
+    }
+
+    @Override
+    public boolean match(String object) {
+      ranMatch = true;
+      return false;
+    }
+
+    @Override
+    public int getCost() {
+      return cost;
+    }
+  }
+
+  protected static class TestPredicate extends OperatorPredicate<String> {
     protected TestPredicate(String name, String value) {
       super(name, value);
     }
diff --git a/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java b/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java
index e2eaa1df3e..4acedd17e7 100644
--- a/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java
+++ b/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java
@@ -186,7 +186,7 @@ public class ChangeIndexRewriterTest {
     Predicate<ChangeData> out = rewrite(in, options(0, 5));
     assertThat(out.getClass()).isEqualTo(AndChangeSource.class);
     assertThat(out.getChildren())
-        .containsExactly(query(in.getChild(1), 5), parse("limit:5"), parse("limit:5"))
+        .containsExactly(query(parse("file:a"), 5), parse("limit:5"), parse("limit:5"))
         .inOrder();
   }