[ElasticSearch] Sort results by _doc when no order is specified

[cdegroc]

When no order() is specified in a Gremlin Traversal, ElasticSearch requests don't specify any sort criteria [1][2].

By sorting on the _doc field (ElasticSearch "index order"), we might be able to reduce queries latency, as suggested in ElasticSearch documentation:

• "Scroll requests have optimizations that make them faster when the sort order is _doc"
• "_doc has no real use-case besides being the most efficient sort order. So if you don’t care about the order in which documents are returned, then you should sort by _doc. This especially helps when scrolling",

I've run a simple benchmark locally (code here):

• Launch an ES container
• Create an index with 300 000 dummy vertices
• Send queries returning a specific number of vertices (1 000, 10 000, ...) repetitively, and record their time after a warm-up period
• Repeat with a sort on the _doc field this time

Results are as follows:

documents returned	mean ± stdev request time without any sort	mean/stdev request time with sort=_doc asc
1 000	402 ± 56	401 ± 37
10 000	4 305 ± 194	4 009 ± 192
20 000	10 727 ± 1 407	8 430 ± 996
50 000	41 615 ± 4 278	21 780 ± 1 199
100 000	117 459 ± 2 123	47 026 ± 2 764

I've run this benchmark several times and while the gain for queries returning 1 000 or 10 000 vertices varies, it is very consistent for queries returning 50 000 or 100 000 results.

If you can think of any flaw in the benchmark or can suggest a more robust way (libraries? datasets?) to run another benchmark, please let me know!

Related to this, if we always specified _doc as the last sort criteria for all requests (and not only for those that don't have a sort order), we could maybe make results order stable? (see this comment from @li-boxuan pointing out that sort is unstable)

I guess the same change could be applied to SolR but I haven't looked into it.

[li-boxuan]

Interesting thought! Two cents from me:

1. Using _doc won't help you make results order stable. See Provide a consistent order of mixed index results #2573
2. If you have some time, maybe you could also compare scroll with/without _doc order, to search_after. See Optimize ElasticSearch search queries to not always use Scroll API #1680. That being said, I am okay with small incremental optimizations.
3. I am not sure but I guess Elasticsearch by default returns results in descending order of matching score. Thus, changing the sorting order to something else might make some users not happy. We should make it optional.

[cdegroc]

Thanks for your feedback Boxuan.

1. Definitely makes sense now.
2. Got it. I'll comment on Optimize ElasticSearch search queries to not always use Scroll API #1680 if/when I have a first PR with search_after.
3. Sure, we can add a config flag for it. We could also change this behavior in the next major release (0.6)?

[li-boxuan]

Not sure if we can make it for 0.6.0, whose release deadline is May 1st.
Actually I am not sure about the 3rd point; it was just my hypothesis. We could validate it later :)