Introduce a SEARCH_AFTER index pagination type

Current Paginated interface only allows to restart a query from
a given offset. Update it to also allow restarting queries using
a searchAfter key. searchAfter can help with performance of queries
such as [1] where the visibility is being queried for an account
that cannot see most/all changes. [1] finishes in ~45 mins with
OFFSET and ~10 mins with SEARCH_AFTER when the site has around
1M abandoned changes.

Index config has been updated to add a paginationType entry with
OFFSET and SEARCH_AFTER as supported values. The default is set
to OFFSET to keep the current pagination type unchanged.

Gerrit's Lucene index implementation has been updated to support
this new pagination type with search-after[2]. Elasticsearch
index implementation has also been updated to paginate using
search-after[3] and can be further improved to use PIT[4]. Lucene
and Elasticsearch tests have been updated to run with both pagination
types. Also, Elasticsearch tests now use the official docker image
as it can handle running tests with multiple index config suites.

Note that, searchAfter will not impact using offsets in Gerrit
query APIs.

[1] gerrit query 'status:abandoned visibleto:guest'
[2] https://lucene.apache.org/core/6_6_5/core/org/apache/lucene/search/IndexSearcher.html#search-org.apache.lucene.search.Query-int-org.apache.lucene.search.Sort-boolean-boolean-
[3] https://www.elastic.co/guide/en/elasticsearch/reference/current/paginate-search-results.html#search-after
[4] https://www.elastic.co/guide/en/elasticsearch/reference/current/point-in-time-api.html

Release-Notes: Index searches now support search-after pagination
Change-Id: If3f8d914d5fd3f350c026cf099f08cf9a13f2195

32 files changed, 386 insertions, 55 deletions

diff --git a/Documentation/config-gerrit.txt b/Documentation/config-gerrit.txt
index 9dea08e838..121ac8fd8a 100644
--- a/Documentation/config-gerrit.txt
+++ b/Documentation/config-gerrit.txt
@@ -3117,6 +3117,25 @@ advantage of new search features without restarting the server.
 +
 Defaults to true.
 
+[[index.paginationType]]index.paginationType::
++
+The pagination type to use when index queries are repeated to
+obtain the next set of results. Supported values are:
++
+* `OFFSET`
++
+Index queries are repeated with a non-zero offset to obtain the
+next set of results.
++
+* `SEARCH_AFTER`
++
+Index queries are repeated using a search-after object. This type
+is supported for Lucene and ElasticSearch. Other index backends can
+provide their custom implementations for search-after. Note that,
+`SEARCH_AFTER` does not impact using offsets in Gerrit query APIs.
++
+Defaults to `OFFSET`.
+
 [[index.maxLimit]]index.maxLimit::
 +
 Maximum limit to allow for search queries. Requesting results above this
diff --git a/java/com/google/gerrit/elasticsearch/AbstractElasticIndex.java b/java/com/google/gerrit/elasticsearch/AbstractElasticIndex.java
index 6ed1a51715..e27f43f193 100644
--- a/java/com/google/gerrit/elasticsearch/AbstractElasticIndex.java
+++ b/java/com/google/gerrit/elasticsearch/AbstractElasticIndex.java
@@ -360,9 +360,12 @@ abstract class AbstractElasticIndex<K, V> implements Index<K, V> {
       SearchSourceBuilder searchSource =
           new SearchSourceBuilder(client.adapter())
               .query(qb)
-              .from(opts.start())
               .size(opts.limit())
               .fields(Lists.newArrayList(opts.fields()));
+      searchSource =
+          opts.searchAfter() != null
+              ? searchSource.searchAfter((JsonArray) opts.searchAfter()).trackTotalHits(false)
+              : searchSource.from(opts.start());
       search = getSearch(searchSource, sortArray);
     }
 
@@ -384,6 +387,7 @@ abstract class AbstractElasticIndex<K, V> implements Index<K, V> {
     private <T> ResultSet<T> readImpl(Function<JsonObject, T> mapper) {
       try {
         String uri = getURI(SEARCH);
+        JsonArray searchAfter = null;
         Response response =
             performRequest(HttpPost.METHOD_NAME, uri, search, Collections.emptyMap());
         StatusLine statusLine = response.getStatusLine();
@@ -394,13 +398,24 @@ abstract class AbstractElasticIndex<K, V> implements Index<K, V> {
           if (obj.get("hits") != null) {
             JsonArray json = obj.getAsJsonArray("hits");
             ImmutableList.Builder<T> results = ImmutableList.builderWithExpectedSize(json.size());
+            JsonObject hit = null;
             for (int i = 0; i < json.size(); i++) {
-              T mapperResult = mapper.apply(json.get(i).getAsJsonObject());
+              hit = json.get(i).getAsJsonObject();
+              T mapperResult = mapper.apply(hit);
               if (mapperResult != null) {
                 results.add(mapperResult);
               }
             }
-            return new ListResultSet<>(results.build());
+            if (hit != null && hit.get("sort") != null) {
+              searchAfter = hit.getAsJsonArray("sort");
+            }
+            JsonArray finalSearchAfter = searchAfter;
+            return new ListResultSet<T>(results.build()) {
+              @Override
+              public Object searchAfter() {
+                return finalSearchAfter;
+              }
+            };
           }
         } else {
           logger.atSevere().log(statusLine.getReasonPhrase());
diff --git a/java/com/google/gerrit/elasticsearch/builders/SearchAfterBuilder.java b/java/com/google/gerrit/elasticsearch/builders/SearchAfterBuilder.java
new file mode 100644
index 0000000000..095121704f
--- /dev/null
+++ b/java/com/google/gerrit/elasticsearch/builders/SearchAfterBuilder.java
@@ -0,0 +1,45 @@
+// Copyright (C) 2022 The Android Open Source Project, 2009-2015 Elasticsearch
+//
+// 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.elasticsearch.builders;
+
+import com.google.gson.JsonArray;
+import com.google.gson.JsonPrimitive;
+import java.io.IOException;
+
+/**
+ * A trimmed down and modified version of org.elasticsearch.search.searchafter.SearchAfterBuilder.
+ */
+public final class SearchAfterBuilder {
+  private JsonArray sortValues;
+
+  public SearchAfterBuilder(JsonArray sortValues) {
+    this.sortValues = sortValues;
+  }
+
+  public void innerToXContent(XContentBuilder builder) throws IOException {
+    builder.startArray("search_after");
+    for (int i = 0; i < sortValues.size(); i++) {
+      JsonPrimitive value = sortValues.get(i).getAsJsonPrimitive();
+      if (value.isNumber()) {
+        builder.value(value.getAsLong());
+      } else if (value.isBoolean()) {
+        builder.value(value.getAsBoolean());
+      } else {
+        builder.value(value.getAsString());
+      }
+    }
+    builder.endArray();
+  }
+}
diff --git a/java/com/google/gerrit/elasticsearch/builders/SearchSourceBuilder.java b/java/com/google/gerrit/elasticsearch/builders/SearchSourceBuilder.java
index 35cbea99b6..7e4ea93bdd 100644
--- a/java/com/google/gerrit/elasticsearch/builders/SearchSourceBuilder.java
+++ b/java/com/google/gerrit/elasticsearch/builders/SearchSourceBuilder.java
@@ -15,6 +15,7 @@
 package com.google.gerrit.elasticsearch.builders;
 
 import com.google.gerrit.elasticsearch.ElasticQueryAdapter;
+import com.google.gson.JsonArray;
 import java.io.IOException;
 import java.util.List;
 
@@ -28,10 +29,14 @@ public class SearchSourceBuilder {
 
   private QuerySourceBuilder querySourceBuilder;
 
+  private SearchAfterBuilder searchAfterBuilder;
+
   private int from = -1;
 
   private int size = -1;
 
+  private boolean trackTotalHits = true;
+
   private List<String> fieldNames;
 
   /** Constructs a new search source builder. */
@@ -53,12 +58,22 @@ public class SearchSourceBuilder {
     return this;
   }
 
+  public SearchSourceBuilder searchAfter(JsonArray sortValues) {
+    this.searchAfterBuilder = new SearchAfterBuilder(sortValues);
+    return this;
+  }
+
   /** The number of search hits to return. Defaults to <tt>10</tt>. */
   public SearchSourceBuilder size(int size) {
     this.size = size;
     return this;
   }
 
+  public SearchSourceBuilder trackTotalHits(boolean track) {
+    this.trackTotalHits = track;
+    return this;
+  }
+
   /**
    * Sets the fields to load and return as part of the search request. If none are specified, the
    * source of the document will be returned.
@@ -93,6 +108,10 @@ public class SearchSourceBuilder {
       builder.field("size", size);
     }
 
+    if (!trackTotalHits) {
+      builder.field("track_total_hits", false);
+    }
+
     if (querySourceBuilder != null) {
       querySourceBuilder.innerToXContent(builder);
     }
@@ -108,5 +127,9 @@ public class SearchSourceBuilder {
         builder.endArray();
       }
     }
+
+    if (searchAfterBuilder != null) {
+      searchAfterBuilder.innerToXContent(builder);
+    }
   }
 }
diff --git a/java/com/google/gerrit/elasticsearch/builders/XContentBuilder.java b/java/com/google/gerrit/elasticsearch/builders/XContentBuilder.java
index 9c44583e15..853596d15b 100644
--- a/java/com/google/gerrit/elasticsearch/builders/XContentBuilder.java
+++ b/java/com/google/gerrit/elasticsearch/builders/XContentBuilder.java
@@ -152,6 +152,8 @@ public final class XContentBuilder implements Closeable {
       generator.writeString((String) value);
     } else if (type == Integer.class) {
       generator.writeNumber(((Integer) value));
+    } else if (type == Long.class) {
+      generator.writeNumber(((Long) value));
     } else if (type == byte[].class) {
       generator.writeBinary((byte[]) value);
     } else if (value instanceof Date) {
diff --git a/java/com/google/gerrit/index/IndexConfig.java b/java/com/google/gerrit/index/IndexConfig.java
index 29b8ea657e..b1b019860c 100644
--- a/java/com/google/gerrit/index/IndexConfig.java
+++ b/java/com/google/gerrit/index/IndexConfig.java
@@ -41,6 +41,7 @@ public abstract class IndexConfig {
     setIfPresent(cfg, "maxPages", b::maxPages);
     setIfPresent(cfg, "maxTerms", b::maxTerms);
     setTypeOrDefault(cfg, b::type);
+    setPaginationTypeOrDefault(cfg, b::paginationType);
     return b;
   }
 
@@ -56,13 +57,19 @@ public abstract class IndexConfig {
     setter.accept(new IndexType(type).toString());
   }
 
+  private static void setPaginationTypeOrDefault(Config cfg, Consumer<PaginationType> setter) {
+    setter.accept(
+        cfg != null ? cfg.getEnum("index", null, "paginationType", PaginationType.OFFSET) : null);
+  }
+
   public static Builder builder() {
     return new AutoValue_IndexConfig.Builder()
         .maxLimit(Integer.MAX_VALUE)
         .maxPages(Integer.MAX_VALUE)
         .maxTerms(DEFAULT_MAX_TERMS)
         .type(IndexType.getDefault())
-        .separateChangeSubIndexes(false);
+        .separateChangeSubIndexes(false)
+        .paginationType(PaginationType.OFFSET);
   }
 
   @AutoValue.Builder
@@ -85,6 +92,8 @@ public abstract class IndexConfig {
 
     public abstract Builder separateChangeSubIndexes(boolean separate);
 
+    public abstract Builder paginationType(PaginationType type);
+
     abstract IndexConfig autoBuild();
 
     public IndexConfig build() {
@@ -124,4 +133,10 @@ public abstract class IndexConfig {
    * @return whether different subsets of changes may be stored in different physical sub-indexes.
    */
   public abstract boolean separateChangeSubIndexes();
+
+  /**
+   * @return pagination type to use when index queries are repeated to obtain the next set of
+   *     results.
+   */
+  public abstract PaginationType paginationType();
 }
diff --git a/java/com/google/gerrit/index/PaginationType.java b/java/com/google/gerrit/index/PaginationType.java
new file mode 100644
index 0000000000..e7e34fdc0a
--- /dev/null
+++ b/java/com/google/gerrit/index/PaginationType.java
@@ -0,0 +1,29 @@
+// 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;
+
+public enum PaginationType {
+  /** Index queries are restarted at a non-zero offset to obtain the next set of results */
+  OFFSET,
+
+  /**
+   * Index queries are restarted using a search-after object. Supported index backends can provide
+   * their custom implementations for search-after.
+   *
+   * <p>For example, Lucene implementation uses the last doc from the previous search as
+   * search-after object and uses the IndexSearcher.searchAfter API to get the next set of results.
+   */
+  SEARCH_AFTER
+}
diff --git a/java/com/google/gerrit/index/QueryOptions.java b/java/com/google/gerrit/index/QueryOptions.java
index 0401dab067..b4b73e6395 100644
--- a/java/com/google/gerrit/index/QueryOptions.java
+++ b/java/com/google/gerrit/index/QueryOptions.java
@@ -19,15 +19,25 @@ import static com.google.common.base.Preconditions.checkArgument;
 import com.google.auto.value.AutoValue;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.primitives.Ints;
+import com.google.gerrit.common.Nullable;
 import java.util.Set;
 import java.util.function.Function;
 
 @AutoValue
 public abstract class QueryOptions {
   public static QueryOptions create(IndexConfig config, int start, int limit, Set<String> fields) {
+    return create(config, start, null, limit, fields);
+  }
+
+  public static QueryOptions create(
+      IndexConfig config, int start, Object searchAfter, int limit, Set<String> fields) {
     checkArgument(start >= 0, "start must be nonnegative: %s", start);
     checkArgument(limit > 0, "limit must be positive: %s", limit);
-    return new AutoValue_QueryOptions(config, start, limit, ImmutableSet.copyOf(fields));
+    if (searchAfter != null) {
+      checkArgument(start == 0, "start must be 0 when searchAfter is specified: %s", start);
+    }
+    return new AutoValue_QueryOptions(
+        config, start, searchAfter, limit, ImmutableSet.copyOf(fields));
   }
 
   public QueryOptions convertForBackend() {
@@ -36,26 +46,35 @@ public abstract class QueryOptions {
     int backendLimit = config().maxLimit();
     int limit = Ints.saturatedCast((long) limit() + start());
     limit = Math.min(limit, backendLimit);
-    return create(config(), 0, limit, fields());
+    return create(config(), 0, null, limit, fields());
   }
 
   public abstract IndexConfig config();
 
   public abstract int start();
 
+  @Nullable
+  public abstract Object searchAfter();
+
   public abstract int limit();
 
   public abstract ImmutableSet<String> fields();
 
   public QueryOptions withLimit(int newLimit) {
-    return create(config(), start(), newLimit, fields());
+    return create(config(), start(), searchAfter(), newLimit, fields());
   }
 
   public QueryOptions withStart(int newStart) {
-    return create(config(), newStart, limit(), fields());
+    return create(config(), newStart, searchAfter(), limit(), fields());
+  }
+
+  public QueryOptions withSearchAfter(Object newSearchAfter) {
+    // Index search-after APIs don't use 'start', so set it to 0 to be safe. ElasticSearch for
+    // example, expects it to be 0 when using search-after APIs.
+    return create(config(), start(), newSearchAfter, limit(), fields()).withStart(0);
   }
 
   public QueryOptions filterFields(Function<QueryOptions, Set<String>> filter) {
-    return create(config(), start(), limit(), filter.apply(this));
+    return create(config(), start(), searchAfter(), limit(), filter.apply(this));
   }
 }
diff --git a/java/com/google/gerrit/index/query/AndSource.java b/java/com/google/gerrit/index/query/AndSource.java
index 538e11b783..ca1acf13b0 100644
--- a/java/com/google/gerrit/index/query/AndSource.java
+++ b/java/com/google/gerrit/index/query/AndSource.java
@@ -21,6 +21,8 @@ import com.google.common.collect.FluentIterable;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.gerrit.exceptions.StorageException;
+import com.google.gerrit.index.IndexConfig;
+import com.google.gerrit.index.PaginationType;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Comparator;
@@ -33,23 +35,30 @@ public class AndSource<T> extends AndPredicate<T>
   private final IsVisibleToPredicate<T> isVisibleToPredicate;
   private final int start;
   private final int cardinality;
+  private final IndexConfig indexConfig;
 
-  public AndSource(Collection<? extends Predicate<T>> that) {
-    this(that, null, 0);
+  public AndSource(Collection<? extends Predicate<T>> that, IndexConfig indexConfig) {
+    this(that, null, 0, indexConfig);
   }
 
-  public AndSource(Predicate<T> that, IsVisibleToPredicate<T> isVisibleToPredicate) {
-    this(that, isVisibleToPredicate, 0);
+  public AndSource(
+      Predicate<T> that, IsVisibleToPredicate<T> isVisibleToPredicate, IndexConfig indexConfig) {
+    this(that, isVisibleToPredicate, 0, indexConfig);
   }
 
-  public AndSource(Predicate<T> that, IsVisibleToPredicate<T> isVisibleToPredicate, int start) {
-    this(ImmutableList.of(that), isVisibleToPredicate, start);
+  public AndSource(
+      Predicate<T> that,
+      IsVisibleToPredicate<T> isVisibleToPredicate,
+      int start,
+      IndexConfig indexConfig) {
+    this(ImmutableList.of(that), isVisibleToPredicate, start, indexConfig);
   }
 
   public AndSource(
       Collection<? extends Predicate<T>> that,
       IsVisibleToPredicate<T> isVisibleToPredicate,
-      int start) {
+      int start,
+      IndexConfig indexConfig) {
     super(that);
     checkArgument(start >= 0, "negative start: %s", start);
     this.isVisibleToPredicate = isVisibleToPredicate;
@@ -71,6 +80,7 @@ public class AndSource<T> extends AndPredicate<T>
     }
     this.source = s;
     this.cardinality = c;
+    this.indexConfig = indexConfig;
   }
 
   @Override
@@ -105,10 +115,13 @@ public class AndSource<T> extends AndPredicate<T>
             //
             @SuppressWarnings("unchecked")
             Paginated<T> p = (Paginated<T>) source;
+            Object searchAfter = resultSet.searchAfter();
             while (skipped && r.size() < p.getOptions().limit() + start) {
               skipped = false;
-              ResultSet<T> next = p.restart(nextStart);
-
+              ResultSet<T> next =
+                  indexConfig.paginationType().equals(PaginationType.SEARCH_AFTER)
+                      ? p.restart(searchAfter)
+                      : p.restart(nextStart);
               for (T data : buffer(next)) {
                 if (match(data)) {
                   r.add(data);
@@ -117,6 +130,7 @@ public class AndSource<T> extends AndPredicate<T>
                 }
                 nextStart++;
               }
+              searchAfter = next.searchAfter();
             }
           }
 
diff --git a/java/com/google/gerrit/index/query/IndexedQuery.java b/java/com/google/gerrit/index/query/IndexedQuery.java
index d9e33ea2dc..ded0074cf7 100644
--- a/java/com/google/gerrit/index/query/IndexedQuery.java
+++ b/java/com/google/gerrit/index/query/IndexedQuery.java
@@ -89,17 +89,13 @@ public class IndexedQuery<I, T> extends Predicate<T> implements DataSource<T>, P
   @Override
   public ResultSet<T> restart(int start) {
     opts = opts.withStart(start);
-    try {
-      source = index.getSource(pred, opts);
-    } catch (QueryParseException e) {
-      // Don't need to show this exception to the user; the only thing that
-      // changed about pred was its start, and any other QPEs that might happen
-      // should have already thrown from the constructor.
-      throw new StorageException(e);
-    }
-    // Don't convert start to a limit, since the caller of this method (see
-    // AndSource) has calculated the actual number to skip.
-    return read();
+    return search();
+  }
+
+  @Override
+  public ResultSet<T> restart(Object searchAfter) {
+    opts = opts.withSearchAfter(searchAfter);
+    return search();
   }
 
   @Override
@@ -125,4 +121,18 @@ public class IndexedQuery<I, T> extends Predicate<T> implements DataSource<T>, P
   public String toString() {
     return MoreObjects.toStringHelper("index").add("p", pred).add("opts", opts).toString();
   }
+
+  private ResultSet<T> search() {
+    try {
+      source = index.getSource(pred, opts);
+    } catch (QueryParseException e) {
+      // Don't need to show this exception to the user; the only thing that
+      // changed about pred was its start, and any other QPEs that might happen
+      // should have already thrown from the constructor.
+      throw new StorageException(e);
+    }
+    // Don't convert start to a limit, since the caller of this method (see
+    // AndSource) has calculated the actual number to skip.
+    return read();
+  }
 }
diff --git a/java/com/google/gerrit/index/query/LazyResultSet.java b/java/com/google/gerrit/index/query/LazyResultSet.java
index f3fab5f5b5..a7d71f003a 100644
--- a/java/com/google/gerrit/index/query/LazyResultSet.java
+++ b/java/com/google/gerrit/index/query/LazyResultSet.java
@@ -53,4 +53,9 @@ public class LazyResultSet<T> implements ResultSet<T> {
 
   @Override
   public void close() {}
+
+  @Override
+  public Object searchAfter() {
+    return null;
+  }
 }
diff --git a/java/com/google/gerrit/index/query/ListResultSet.java b/java/com/google/gerrit/index/query/ListResultSet.java
index 9d7eadf393..f09fda0cd2 100644
--- a/java/com/google/gerrit/index/query/ListResultSet.java
+++ b/java/com/google/gerrit/index/query/ListResultSet.java
@@ -54,4 +54,9 @@ public class ListResultSet<T> implements ResultSet<T> {
   public void close() {
     results = null;
   }
+
+  @Override
+  public Object searchAfter() {
+    return null;
+  }
 }
diff --git a/java/com/google/gerrit/index/query/Paginated.java b/java/com/google/gerrit/index/query/Paginated.java
index e61dd53234..475bcfe4fd 100644
--- a/java/com/google/gerrit/index/query/Paginated.java
+++ b/java/com/google/gerrit/index/query/Paginated.java
@@ -20,4 +20,6 @@ public interface Paginated<T> {
   QueryOptions getOptions();
 
   ResultSet<T> restart(int start);
+
+  ResultSet<T> restart(Object searchAfter);
 }
diff --git a/java/com/google/gerrit/index/query/ResultSet.java b/java/com/google/gerrit/index/query/ResultSet.java
index 65fcd4593c..b4bd19e9a7 100644
--- a/java/com/google/gerrit/index/query/ResultSet.java
+++ b/java/com/google/gerrit/index/query/ResultSet.java
@@ -49,4 +49,6 @@ public interface ResultSet<T> extends Iterable<T> {
    * the iterator has finished.
    */
   void close();
+
+  Object searchAfter();
 }
diff --git a/java/com/google/gerrit/lucene/AbstractLuceneIndex.java b/java/com/google/gerrit/lucene/AbstractLuceneIndex.java
index 1e6ccac89a..f3ee73840c 100644
--- a/java/com/google/gerrit/lucene/AbstractLuceneIndex.java
+++ b/java/com/google/gerrit/lucene/AbstractLuceneIndex.java
@@ -535,20 +535,31 @@ public abstract class AbstractLuceneIndex<K, V> implements Index<K, V> {
 
     private <T> ResultSet<T> readImpl(Function<Document, T> mapper) {
       IndexSearcher searcher = null;
+      ScoreDoc scoreDoc = null;
       try {
         searcher = acquire();
         int realLimit = opts.start() + opts.limit();
-        TopFieldDocs docs = searcher.search(query, realLimit, sort);
+        TopFieldDocs docs =
+            opts.searchAfter() != null
+                ? searcher.searchAfter(
+                    (ScoreDoc) opts.searchAfter(), query, realLimit, sort, false, false)
+                : searcher.search(query, realLimit, sort);
         ImmutableList.Builder<T> b = ImmutableList.builderWithExpectedSize(docs.scoreDocs.length);
         for (int i = opts.start(); i < docs.scoreDocs.length; i++) {
-          ScoreDoc sd = docs.scoreDocs[i];
-          Document doc = searcher.doc(sd.doc, opts.fields());
+          scoreDoc = docs.scoreDocs[i];
+          Document doc = searcher.doc(scoreDoc.doc, opts.fields());
           T mapperResult = mapper.apply(doc);
           if (mapperResult != null) {
             b.add(mapperResult);
           }
         }
-        return new ListResultSet<>(b.build());
+        ScoreDoc searchAfter = scoreDoc;
+        return new ListResultSet<T>(b.build()) {
+          @Override
+          public Object searchAfter() {
+            return searchAfter;
+          }
+        };
       } catch (IOException e) {
         throw new StorageException(e);
       } finally {
diff --git a/java/com/google/gerrit/lucene/LuceneChangeIndex.java b/java/com/google/gerrit/lucene/LuceneChangeIndex.java
index b1141d9200..2e8d6a2de0 100644
--- a/java/com/google/gerrit/lucene/LuceneChangeIndex.java
+++ b/java/com/google/gerrit/lucene/LuceneChangeIndex.java
@@ -76,9 +76,12 @@ import java.io.IOException;
 import java.nio.file.Path;
 import java.sql.Timestamp;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collection;
+import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
 import java.util.concurrent.Callable;
 import java.util.concurrent.ExecutionException;
@@ -398,9 +401,9 @@ public class LuceneChangeIndex implements ChangeIndex {
       final Set<String> fields = IndexUtils.changeFields(opts, schema.useLegacyNumericFields());
       return new ChangeDataResults(
           executor.submit(
-              new Callable<List<Document>>() {
+              new Callable<Results>() {
                 @Override
-                public List<Document> call() throws IOException {
+                public Results call() throws IOException {
                   return doRead(fields);
                 }
 
@@ -415,8 +418,12 @@ public class LuceneChangeIndex implements ChangeIndex {
     @Override
     public ResultSet<FieldBundle> readRaw() {
       List<Document> documents;
+      Map<ChangeSubIndex, ScoreDoc> searchAfterBySubIndex;
+
       try {
-        documents = doRead(IndexUtils.changeFields(opts, schema.useLegacyNumericFields()));
+        Results r = doRead(IndexUtils.changeFields(opts, schema.useLegacyNumericFields()));
+        documents = r.docs;
+        searchAfterBySubIndex = r.searchAfterBySubIndex;
       } catch (IOException e) {
         throw new StorageException(e);
       }
@@ -437,11 +444,17 @@ public class LuceneChangeIndex implements ChangeIndex {
         public void close() {
           // Do nothing.
         }
+
+        @Override
+        public Object searchAfter() {
+          return searchAfterBySubIndex;
+        }
       };
     }
 
-    private List<Document> doRead(Set<String> fields) throws IOException {
+    private Results doRead(Set<String> fields) throws IOException {
       IndexSearcher[] searchers = new IndexSearcher[indexes.size()];
+      Map<ChangeSubIndex, ScoreDoc> searchAfterBySubIndex = new HashMap<>();
       try {
         int realLimit = opts.start() + opts.limit();
         if (Integer.MAX_VALUE - opts.limit() < opts.start()) {
@@ -449,8 +462,22 @@ public class LuceneChangeIndex implements ChangeIndex {
         }
         TopFieldDocs[] hits = new TopFieldDocs[indexes.size()];
         for (int i = 0; i < indexes.size(); i++) {
-          searchers[i] = indexes.get(i).acquire();
-          hits[i] = searchers[i].search(query, realLimit, sort);
+          ChangeSubIndex subIndex = indexes.get(i);
+          searchers[i] = subIndex.acquire();
+          if (opts.searchAfter() != null && opts.searchAfter() instanceof HashMap) {
+            hits[i] =
+                searchers[i].searchAfter(
+                    ((HashMap<ChangeSubIndex, ScoreDoc>) opts.searchAfter()).get(subIndex),
+                    query,
+                    realLimit,
+                    sort,
+                    /* doDocScores= */ false,
+                    /* doMaxScore= */ false);
+          } else {
+            hits[i] = searchers[i].search(query, realLimit, sort);
+          }
+          searchAfterBySubIndex.put(
+              subIndex, Iterables.getLast(Arrays.asList(hits[i].scoreDocs), null));
         }
         TopDocs docs = TopDocs.merge(sort, realLimit, hits);
 
@@ -459,7 +486,7 @@ public class LuceneChangeIndex implements ChangeIndex {
           ScoreDoc sd = docs.scoreDocs[i];
           result.add(searchers[sd.shardIndex].doc(sd.doc, fields));
         }
-        return result;
+        return new Results(result, searchAfterBySubIndex);
       } finally {
         for (int i = 0; i < indexes.size(); i++) {
           if (searchers[i] != null) {
@@ -474,11 +501,22 @@ public class LuceneChangeIndex implements ChangeIndex {
     }
   }
 
+  private static class Results {
+    List<Document> docs;
+    Map<ChangeSubIndex, ScoreDoc> searchAfterBySubIndex;
+
+    public Results(List<Document> docs, Map<ChangeSubIndex, ScoreDoc> searchAfterBySubIndex) {
+      this.docs = docs;
+      this.searchAfterBySubIndex = searchAfterBySubIndex;
+    }
+  }
+
   private class ChangeDataResults implements ResultSet<ChangeData> {
-    private final Future<List<Document>> future;
+    private final Future<Results> future;
     private final Set<String> fields;
+    private Map<ChangeSubIndex, ScoreDoc> searchAfterBySubIndex;
 
-    ChangeDataResults(Future<List<Document>> future, Set<String> fields) {
+    ChangeDataResults(Future<Results> future, Set<String> fields) {
       this.future = future;
       this.fields = fields;
     }
@@ -491,7 +529,9 @@ public class LuceneChangeIndex implements ChangeIndex {
     @Override
     public ImmutableList<ChangeData> toList() {
       try {
-        List<Document> docs = future.get();
+        Results r = future.get();
+        List<Document> docs = r.docs;
+        searchAfterBySubIndex = r.searchAfterBySubIndex;
         ImmutableList.Builder<ChangeData> result =
             ImmutableList.builderWithExpectedSize(docs.size());
         for (Document doc : docs) {
@@ -511,6 +551,11 @@ public class LuceneChangeIndex implements ChangeIndex {
     public void close() {
       future.cancel(false /* do not interrupt Lucene */);
     }
+
+    @Override
+    public Object searchAfter() {
+      return searchAfterBySubIndex;
+    }
   }
 
   private static ListMultimap<String, IndexableField> fields(Document doc, Set<String> fields) {
diff --git a/java/com/google/gerrit/server/index/change/ChangeIndexRewriter.java b/java/com/google/gerrit/server/index/change/ChangeIndexRewriter.java
index 63c52977a6..35d167a5ce 100644
--- a/java/com/google/gerrit/server/index/change/ChangeIndexRewriter.java
+++ b/java/com/google/gerrit/server/index/change/ChangeIndexRewriter.java
@@ -281,7 +281,7 @@ public class ChangeIndexRewriter implements IndexRewriter<ChangeData> {
 
   private Predicate<ChangeData> copy(Predicate<ChangeData> in, List<Predicate<ChangeData>> all) {
     if (in instanceof AndPredicate) {
-      return new AndChangeSource(all);
+      return new AndChangeSource(all, config);
     } else if (in instanceof OrPredicate) {
       return new OrSource(all);
     }
diff --git a/java/com/google/gerrit/server/index/change/IndexedChangeQuery.java b/java/com/google/gerrit/server/index/change/IndexedChangeQuery.java
index be5f803495..85017fbe76 100644
--- a/java/com/google/gerrit/server/index/change/IndexedChangeQuery.java
+++ b/java/com/google/gerrit/server/index/change/IndexedChangeQuery.java
@@ -110,6 +110,11 @@ public class IndexedChangeQuery extends IndexedQuery<Change.Id, ChangeData>
       public void close() {
         rs.close();
       }
+
+      @Override
+      public Object searchAfter() {
+        return rs.searchAfter();
+      }
     };
   }
 
diff --git a/java/com/google/gerrit/server/query/account/AccountQueryProcessor.java b/java/com/google/gerrit/server/query/account/AccountQueryProcessor.java
index e380ef13dd..9893d1a778 100644
--- a/java/com/google/gerrit/server/query/account/AccountQueryProcessor.java
+++ b/java/com/google/gerrit/server/query/account/AccountQueryProcessor.java
@@ -43,6 +43,7 @@ import com.google.inject.Provider;
 public class AccountQueryProcessor extends QueryProcessor<AccountState> {
   private final AccountControl.Factory accountControlFactory;
   private final Sequences sequences;
+  private final IndexConfig indexConfig;
 
   static {
     // It is assumed that basic rewrites do not touch visibleto predicates.
@@ -71,12 +72,13 @@ public class AccountQueryProcessor extends QueryProcessor<AccountState> {
         () -> limitsFactory.create(userProvider.get()).getQueryLimit());
     this.accountControlFactory = accountControlFactory;
     this.sequences = sequences;
+    this.indexConfig = indexConfig;
   }
 
   @Override
   protected Predicate<AccountState> enforceVisibility(Predicate<AccountState> pred) {
     return new AndSource<>(
-        pred, new AccountIsVisibleToPredicate(accountControlFactory.get()), start);
+        pred, new AccountIsVisibleToPredicate(accountControlFactory.get()), start, indexConfig);
   }
 
   @Override
diff --git a/java/com/google/gerrit/server/query/change/AndChangeSource.java b/java/com/google/gerrit/server/query/change/AndChangeSource.java
index 749204f3f1..98cada3d3a 100644
--- a/java/com/google/gerrit/server/query/change/AndChangeSource.java
+++ b/java/com/google/gerrit/server/query/change/AndChangeSource.java
@@ -14,6 +14,7 @@
 
 package com.google.gerrit.server.query.change;
 
+import com.google.gerrit.index.IndexConfig;
 import com.google.gerrit.index.query.AndSource;
 import com.google.gerrit.index.query.IsVisibleToPredicate;
 import com.google.gerrit.index.query.Predicate;
@@ -22,15 +23,16 @@ import java.util.List;
 
 public class AndChangeSource extends AndSource<ChangeData> implements ChangeDataSource {
 
-  public AndChangeSource(Collection<Predicate<ChangeData>> that) {
-    super(that);
+  public AndChangeSource(Collection<Predicate<ChangeData>> that, IndexConfig indexConfig) {
+    super(that, indexConfig);
   }
 
   public AndChangeSource(
       Predicate<ChangeData> that,
       IsVisibleToPredicate<ChangeData> isVisibleToPredicate,
-      int start) {
-    super(that, isVisibleToPredicate, start);
+      int start,
+      IndexConfig indexConfig) {
+    super(that, isVisibleToPredicate, start, indexConfig);
   }
 
   @Override
diff --git a/java/com/google/gerrit/server/query/change/ChangeQueryProcessor.java b/java/com/google/gerrit/server/query/change/ChangeQueryProcessor.java
index 7d02ecd688..28a961429e 100644
--- a/java/com/google/gerrit/server/query/change/ChangeQueryProcessor.java
+++ b/java/com/google/gerrit/server/query/change/ChangeQueryProcessor.java
@@ -63,6 +63,7 @@ public class ChangeQueryProcessor extends QueryProcessor<ChangeData>
   private final List<Extension<ChangePluginDefinedInfoFactory>>
       changePluginDefinedInfoFactoriesByPlugin = new ArrayList<>();
   private final Sequences sequences;
+  private final IndexConfig indexConfig;
 
   static {
     // It is assumed that basic rewrites do not touch visibleto predicates.
@@ -93,6 +94,7 @@ public class ChangeQueryProcessor extends QueryProcessor<ChangeData>
     this.userProvider = userProvider;
     this.changeIsVisibleToPredicateFactory = changeIsVisibleToPredicateFactory;
     this.sequences = sequences;
+    this.indexConfig = indexConfig;
 
     changePluginDefinedInfoFactories
         .entries()
@@ -135,7 +137,7 @@ public class ChangeQueryProcessor extends QueryProcessor<ChangeData>
   @Override
   protected Predicate<ChangeData> enforceVisibility(Predicate<ChangeData> pred) {
     return new AndChangeSource(
-        pred, changeIsVisibleToPredicateFactory.forUser(userProvider.get()), start);
+        pred, changeIsVisibleToPredicateFactory.forUser(userProvider.get()), start, indexConfig);
   }
 
   @Override
diff --git a/java/com/google/gerrit/server/query/group/GroupQueryProcessor.java b/java/com/google/gerrit/server/query/group/GroupQueryProcessor.java
index e5fb036521..c6683faa87 100644
--- a/java/com/google/gerrit/server/query/group/GroupQueryProcessor.java
+++ b/java/com/google/gerrit/server/query/group/GroupQueryProcessor.java
@@ -44,6 +44,7 @@ public class GroupQueryProcessor extends QueryProcessor<InternalGroup> {
   private final Provider<CurrentUser> userProvider;
   private final GroupControl.GenericFactory groupControlFactory;
   private final Sequences sequences;
+  private final IndexConfig indexConfig;
 
   static {
     // It is assumed that basic rewrites do not touch visibleto predicates.
@@ -73,12 +74,16 @@ public class GroupQueryProcessor extends QueryProcessor<InternalGroup> {
     this.userProvider = userProvider;
     this.groupControlFactory = groupControlFactory;
     this.sequences = sequences;
+    this.indexConfig = indexConfig;
   }
 
   @Override
   protected Predicate<InternalGroup> enforceVisibility(Predicate<InternalGroup> pred) {
     return new AndSource<>(
-        pred, new GroupIsVisibleToPredicate(groupControlFactory, userProvider.get()), start);
+        pred,
+        new GroupIsVisibleToPredicate(groupControlFactory, userProvider.get()),
+        start,
+        indexConfig);
   }
 
   @Override
diff --git a/java/com/google/gerrit/server/query/project/ProjectQueryProcessor.java b/java/com/google/gerrit/server/query/project/ProjectQueryProcessor.java
index 5465d6d42e..6dafa92289 100644
--- a/java/com/google/gerrit/server/query/project/ProjectQueryProcessor.java
+++ b/java/com/google/gerrit/server/query/project/ProjectQueryProcessor.java
@@ -46,6 +46,7 @@ public class ProjectQueryProcessor extends QueryProcessor<ProjectData> {
   private final PermissionBackend permissionBackend;
   private final Provider<CurrentUser> userProvider;
   private final ProjectCache projectCache;
+  private final IndexConfig indexConfig;
 
   static {
     // It is assumed that basic rewrites do not touch visibleto predicates.
@@ -75,12 +76,16 @@ public class ProjectQueryProcessor extends QueryProcessor<ProjectData> {
     this.permissionBackend = permissionBackend;
     this.userProvider = userProvider;
     this.projectCache = projectCache;
+    this.indexConfig = indexConfig;
   }
 
   @Override
   protected Predicate<ProjectData> enforceVisibility(Predicate<ProjectData> pred) {
     return new AndSource<>(
-        pred, new ProjectIsVisibleToPredicate(permissionBackend, userProvider.get()), start);
+        pred,
+        new ProjectIsVisibleToPredicate(permissionBackend, userProvider.get()),
+        start,
+        indexConfig);
   }
 
   @Override
diff --git a/javatests/com/google/gerrit/elasticsearch/ElasticContainer.java b/javatests/com/google/gerrit/elasticsearch/ElasticContainer.java
index b4fb1535f6..a2a84ed88d 100644
--- a/javatests/com/google/gerrit/elasticsearch/ElasticContainer.java
+++ b/javatests/com/google/gerrit/elasticsearch/ElasticContainer.java
@@ -40,7 +40,7 @@ public class ElasticContainer extends ElasticsearchContainer {
   private static String getImageName(ElasticVersion version) {
     switch (version) {
       case V7_16:
-        return "gerritforge/elasticsearch:7.16.2";
+        return "docker.elastic.co/elasticsearch/elasticsearch:7.16.2";
     }
     throw new IllegalStateException("No tests for version: " + version.name());
   }
diff --git a/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryAccountsTest.java b/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryAccountsTest.java
index 39517d5577..83d2c564e7 100644
--- a/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryAccountsTest.java
+++ b/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryAccountsTest.java
@@ -30,6 +30,13 @@ public class ElasticV7QueryAccountsTest extends AbstractQueryAccountsTest {
     return IndexConfig.createForElasticsearch();
   }
 
+  @ConfigSuite.Config
+  public static Config searchAfterPaginationType() {
+    Config config = defaultConfig();
+    config.setString("index", null, "paginationType", "SEARCH_AFTER");
+    return config;
+  }
+
   private static ElasticContainer container;
 
   @BeforeClass
diff --git a/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryChangesTest.java b/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryChangesTest.java
index 5d64d0a91f..30e731756d 100644
--- a/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryChangesTest.java
+++ b/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryChangesTest.java
@@ -39,6 +39,13 @@ public class ElasticV7QueryChangesTest extends AbstractQueryChangesTest {
     return IndexConfig.createForElasticsearch();
   }
 
+  @ConfigSuite.Config
+  public static Config searchAfterPaginationType() {
+    Config config = defaultConfig();
+    config.setString("index", null, "paginationType", "SEARCH_AFTER");
+    return config;
+  }
+
   private static ElasticContainer container;
   private static CloseableHttpAsyncClient client;
 
diff --git a/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryGroupsTest.java b/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryGroupsTest.java
index 645f889bc3..44518b97a9 100644
--- a/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryGroupsTest.java
+++ b/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryGroupsTest.java
@@ -30,6 +30,13 @@ public class ElasticV7QueryGroupsTest extends AbstractQueryGroupsTest {
     return IndexConfig.createForElasticsearch();
   }
 
+  @ConfigSuite.Config
+  public static Config searchAfterPaginationType() {
+    Config config = defaultConfig();
+    config.setString("index", null, "paginationType", "SEARCH_AFTER");
+    return config;
+  }
+
   private static ElasticContainer container;
 
   @BeforeClass
diff --git a/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryProjectsTest.java b/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryProjectsTest.java
index 8d7f5f8b6c..950443e6c3 100644
--- a/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryProjectsTest.java
+++ b/javatests/com/google/gerrit/elasticsearch/ElasticV7QueryProjectsTest.java
@@ -30,6 +30,13 @@ public class ElasticV7QueryProjectsTest extends AbstractQueryProjectsTest {
     return IndexConfig.createForElasticsearch();
   }
 
+  @ConfigSuite.Config
+  public static Config searchAfterPaginationType() {
+    Config config = defaultConfig();
+    config.setString("index", null, "paginationType", "SEARCH_AFTER");
+    return config;
+  }
+
   private static ElasticContainer container;
 
   @BeforeClass
diff --git a/javatests/com/google/gerrit/index/query/LazyDataSourceTest.java b/javatests/com/google/gerrit/index/query/LazyDataSourceTest.java
index 7064f648d4..4105a1d7f5 100644
--- a/javatests/com/google/gerrit/index/query/LazyDataSourceTest.java
+++ b/javatests/com/google/gerrit/index/query/LazyDataSourceTest.java
@@ -17,6 +17,7 @@ package com.google.gerrit.index.query;
 import static com.google.gerrit.testing.GerritJUnit.assertThrows;
 
 import com.google.common.collect.ImmutableList;
+import com.google.gerrit.index.IndexConfig;
 import com.google.gerrit.server.query.change.ChangeData;
 import com.google.gerrit.server.query.change.ChangeDataSource;
 import com.google.gerrit.server.query.change.OrSource;
@@ -88,11 +89,17 @@ public class LazyDataSourceTest {
     public void close() {
       // No-op
     }
+
+    @Override
+    public Object searchAfter() {
+      return null;
+    }
   }
 
   @Test
   public void andSourceIsLazy() {
-    AndSource<ChangeData> and = new AndSource<>(ImmutableList.of(new LazyPredicate()));
+    AndSource<ChangeData> and =
+        new AndSource<>(ImmutableList.of(new LazyPredicate()), IndexConfig.createDefault());
     ResultSet<ChangeData> resultSet = and.read();
     assertThrows(AssertionError.class, () -> resultSet.toList());
   }
diff --git a/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java b/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java
index e5b2ffb548..e2eaa1df3e 100644
--- a/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java
+++ b/javatests/com/google/gerrit/server/index/change/ChangeIndexRewriterTest.java
@@ -259,7 +259,7 @@ public class ChangeIndexRewriterTest {
 
   @SafeVarargs
   private static AndChangeSource andSource(Predicate<ChangeData>... preds) {
-    return new AndChangeSource(Arrays.asList(preds));
+    return new AndChangeSource(Arrays.asList(preds), IndexConfig.createDefault());
   }
 
   private Predicate<ChangeData> rewrite(Predicate<ChangeData> in) throws QueryParseException {
diff --git a/javatests/com/google/gerrit/server/query/change/LuceneQueryChangesLatestIndexVersionTest.java b/javatests/com/google/gerrit/server/query/change/LuceneQueryChangesLatestIndexVersionTest.java
index 52a9170fe1..45879433e6 100644
--- a/javatests/com/google/gerrit/server/query/change/LuceneQueryChangesLatestIndexVersionTest.java
+++ b/javatests/com/google/gerrit/server/query/change/LuceneQueryChangesLatestIndexVersionTest.java
@@ -23,4 +23,11 @@ public class LuceneQueryChangesLatestIndexVersionTest extends LuceneQueryChanges
   public static Config defaultConfig() {
     return IndexConfig.createForLucene();
   }
+
+  @ConfigSuite.Config
+  public static Config searchAfterPaginationType() {
+    Config config = defaultConfig();
+    config.setString("index", null, "paginationType", "SEARCH_AFTER");
+    return config;
+  }
 }
diff --git a/javatests/com/google/gerrit/server/query/change/LuceneQueryChangesPreviousIndexVersionTest.java b/javatests/com/google/gerrit/server/query/change/LuceneQueryChangesPreviousIndexVersionTest.java
index 62483fa0b7..178269730c 100644
--- a/javatests/com/google/gerrit/server/query/change/LuceneQueryChangesPreviousIndexVersionTest.java
+++ b/javatests/com/google/gerrit/server/query/change/LuceneQueryChangesPreviousIndexVersionTest.java
@@ -33,4 +33,11 @@ public class LuceneQueryChangesPreviousIndexVersionTest extends LuceneQueryChang
                 IndexConfig.createForLucene())
             .values());
   }
+
+  @ConfigSuite.Config
+  public static Config searchAfterPaginationType() {
+    Config config = againstPreviousIndexVersion();
+    config.setString("index", null, "paginationType", "SEARCH_AFTER");
+    return config;
+  }
 }