Pre-sort shards based on the max/min value of the primary sort field

[jimczi]

This change automatically pre-sort search shards on search requests that use a primary sort based on the value of a field. When possible, the can_match phase will extract the min/max (depending on the provided sort order) values of each shard and use it to pre-sort the shards prior to running the subsequent phases. This feature can be useful to ensure that shards that contain recent data are executed first so that intermediate merges have more chance to contain contiguous data (think of date_histogram for instance) but it could also be used in a follow up to early terminate sorted
top-hits queries that don't require the total hit count. The latter could significantly speed up the retrieval of the most/least recent documents from time-based indices.
I took two shortcuts here that require some discussions:

• I reused the can_match phase to add the required information for the shard sort. We could instead introduce a new phase but it make sense to me to use the existing phase to add more informations as long as the additional ops are lightweight.
• The shard sort is done automatically if the primary search sort is based on a field. However this sorting only makes sense if the range of values in each shard doesn't overlap (time-based indices sorted on timestamp for instance). We could add a new option to enable/disable this behavior or even add an additional shard_sort criteria but I also like the fact that users don't need to set any option to benefit from this feature.

Relates #49091

[elasticmachine]

Pinging @elastic/es-search (:Search/Search)

[jimczi]

@elasticmachine run elasticsearch-ci/1

[jpountz]

I left some comments but I like it. To your questions:
+1 to reusing can_match, this is better than introducing an additional phase
+1 to not requiring users to tune anything. I wonder whether we should return both the min and the max value so that we could check whether there is significant overlap or not on the coordinating node and optimize accordingly.

I think this logic might make wrong decisions when sorting on a date and some fields have the date mapped as date and other ones as date_nanos? I don't think it's a bug deal, we wouldn't return wrong results, I'm just checking my understanding.

[jimczi]

Thanks for looking @jpountz. I pushed another commit to address your review. The can_match phase now returns the minimum and the maximum value of the primary sort and we pick the sort value in the coordinator node depending on the provided order.

[jpountz]

The change looks good, Ieft some nit picks about type safety and usage of the comparator API.

[jimczi]

@elasticmachine run elasticsearch-ci/packaging-sample-matrix