Automatically early terminate search query based on index sorting (#24864)

This commit refactors the query phase in order to be able
to automatically detect queries that can be early terminated.
If the index sort matches the query sort, the top docs collection is early terminated
on each segment and the computing of the total number of hits that match the query is delegated to a simple TotalHitCountCollector.
This change also adds a new parameter to the search request called `track_total_hits`.
It indicates if the total number of hits that match the query should be tracked.
If false, queries sorted by the index sort will not try to compute this information and 
and will limit the collection to the first N documents per segment.
Aggregations are not impacted and will continue to see every document
even when the index sort matches the query sort and `track_total_hits` is false.

Relates #6720

2 files changed, 143 insertions, 17 deletions

diff --git a/rest-api-spec/src/main/resources/rest-api-spec/api/search.json b/rest-api-spec/src/main/resources/rest-api-spec/api/search.json
index dc5fda5743..0519a92380 100644
--- a/rest-api-spec/src/main/resources/rest-api-spec/api/search.json
+++ b/rest-api-spec/src/main/resources/rest-api-spec/api/search.json
@@ -147,6 +147,10 @@
           "type" : "boolean",
           "description": "Whether to calculate and return scores even if they are not used for sorting"
         },
+        "track_total_hits": {
+          "type" : "boolean",
+          "description": "Indicate if the number of documents that match the query should be tracked"
+        },
         "typed_keys": {
           "type" : "boolean",
           "description" : "Specify whether aggregation and suggester names should be prefixed by their respective types in the response"
diff --git a/rest-api-spec/src/main/resources/rest-api-spec/test/indices.sort/10_basic.yml b/rest-api-spec/src/main/resources/rest-api-spec/test/indices.sort/10_basic.yml
index 8119e837d6..664a788caa 100644
--- a/rest-api-spec/src/main/resources/rest-api-spec/test/indices.sort/10_basic.yml
+++ b/rest-api-spec/src/main/resources/rest-api-spec/test/indices.sort/10_basic.yml
@@ -11,7 +11,7 @@
         body:
           settings:
             number_of_shards: 1
-            number_of_replicas: 0
+            number_of_replicas: 1
             index.sort.field: rank
           mappings:
             test:
@@ -20,10 +20,6 @@
                   type:     integer
 
   - do:
-      cluster.health:
-        wait_for_status: green
-
-  - do:
       index:
         index: test
         type:  test
@@ -56,6 +52,105 @@
         index: test
 
   - do:
+      index:
+        index: test
+        type:  test
+        id:    "5"
+        body:  { "rank": 8 }
+
+  - do:
+      index:
+        index: test
+        type:  test
+        id:    "6"
+        body:  { "rank": 6 }
+
+  - do:
+      index:
+        index: test
+        type:  test
+        id:    "7"
+        body:  { "rank": 5 }
+
+  - do:
+      index:
+        index: test
+        type:  test
+        id:    "8"
+        body:  { "rank": 7 }
+
+  - do:
+      index:
+        index: test
+        type:  test
+        id:    "8"
+        body:  { "rank": 7 }
+
+  - do:
+      indices.refresh:
+        index: test
+
+  - do:
+      search:
+        index: test
+        type: test
+        body:
+          sort: ["rank"]
+          size: 1
+
+  - is_true: terminated_early
+  - match: {hits.total: 8 }
+  - length: {hits.hits: 1 }
+  - match: {hits.hits.0._id: "2" }
+
+  - do:
+      search:
+        index: test
+        type: test
+        body:
+          sort: ["rank"]
+          query: {"range": { "rank": { "from": 0 } } }
+          track_total_hits: false
+          size: 1
+
+  - match: {terminated_early: true}
+  - match: {hits.total: -1 }
+  - length: {hits.hits: 1 }
+  - match: {hits.hits.0._id: "2" }
+
+  - do:
+      search:
+        index: test
+        type: test
+        body:
+          sort: ["rank"]
+          size: 3
+
+  - is_true: terminated_early
+  - match: {hits.total: 8 }
+  - length: {hits.hits: 3 }
+  - match: {hits.hits.0._id: "2" }
+  - match: {hits.hits.1._id: "4" }
+  - match: {hits.hits.2._id: "3" }
+
+  - do:
+      search:
+        index: test
+        type: test
+        track_total_hits: false
+        body:
+          query: {"range": { "rank": { "from": 0 } } }
+          sort: ["rank"]
+          size: 3
+
+  - match: {terminated_early: true }
+  - match: {hits.total: -1 }
+  - length: {hits.hits: 3 }
+  - match: {hits.hits.0._id: "2" }
+  - match: {hits.hits.1._id: "4" }
+  - match: {hits.hits.2._id: "3" }
+
+  - do:
       indices.forcemerge:
         index: test
         max_num_segments: 1
@@ -65,23 +160,50 @@
         index: test
 
   - do:
-        indices.segments:
-            index: test
+      search:
+        index: test
+        type: test
+        body:
+          sort: _doc
+
+  - is_false: terminated_early
+  - match: {hits.total: 8 }
+  - length: {hits.hits: 8 }
+  - match: {hits.hits.0._id: "2" }
+  - match: {hits.hits.1._id: "4" }
+  - match: {hits.hits.2._id: "3" }
+  - match: {hits.hits.3._id: "1" }
+  - match: {hits.hits.4._id: "7" }
+  - match: {hits.hits.5._id: "6" }
+  - match: {hits.hits.6._id: "8" }
+  - match: {hits.hits.7._id: "5" }
+
+  - do:
+      search:
+        index: test
+        type: test
+        body:
+          sort: ["rank"]
+          query: {"range": { "rank": { "from": 0 } } }
+          track_total_hits: false
+          size: 3
 
-  - match:    { _shards.total: 1}
-  - length:   { indices.test.shards.0: 1}
-  - length:   { indices.test.shards.0.0.segments: 1}
+  - match: {terminated_early: true }
+  - match: {hits.total: -1 }
+  - length: {hits.hits: 3 }
+  - match: {hits.hits.0._id: "2" }
+  - match: {hits.hits.1._id: "4" }
+  - match: {hits.hits.2._id: "3" }
 
   - do:
+      catch:      /disabling \[track_total_hits\] is not allowed in a scroll context/
       search:
         index: test
         type: test
+        scroll: 1m
         body:
-          sort: _doc
+          sort: ["rank"]
+          query: {"range": { "rank": { "from": 0 } } }
+          track_total_hits: false
+          size: 3
 
-  - match:  {hits.total: 4 }
-  - length: {hits.hits: 4 }
-  - match:  {hits.hits.0._id: "2" }
-  - match:  {hits.hits.1._id: "4" }
-  - match:  {hits.hits.2._id: "3" }
-  - match:  {hits.hits.3._id: "1" }