# Why is ascending geo distance sorting faster than descending geo distance sorting **URL:** \ **Category:** Elasticsearch\ **Created:** [March 21, 2019, 2:17pm UTC](https://discuss.elastic.co/t/why-is-ascending-geo-distance-sorting-faster-than-descending-geo-distance-sorting/173328 "2019-03-21T14:17:57Z")\ **Posts on this page:** 8\ **Page:** 1
**Author:** ![gemo1011](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/gemo1011/32/45075_2.png) [@gemo1011](https://discuss.elastic.co/u/gemo1011)\ **Post date:** [March 21, 2019, 2:17pm UTC](https://discuss.elastic.co/t/why-is-ascending-geo-distance-sorting-faster-than-descending-geo-distance-sorting/173328/1 "2019-03-21T14:17:57Z")
I'm using Elasticsearch 6.6 and have an index (1 shard, 1 replica) with the geonames ([https://www.geonames.org/](https://www.geonames.org/)) dataset indexed (indexsize =1.3 gb, 11.8 mio geopoints). I was playing around a bit with the geo distance sorting query, sorting the whole index for some origin points. So after some testing I saw that sorting ascending is always faster than sorting descending. here is an example query: ``` POST /geonames/_search?request_cache=false { "size":1, "sort" : [ { "_geo_distance" : { "location" : [8, 49], "order" : "asc", "unit" : "m", "mode" : "min", "distance_type" : "arc", "ignore_unmapped": true } } ] } ``` Here is the answer for ascending sorting (with explain and profile True): ``` { "took" : 1374, "timed_out" : false, "_shards" : { "total" : 1, "successful" : 1, "skipped" : 0, "failed" : 0 }, "hits" : { "total" : 11858060, "max_score" : null, "hits" : [ { "_shard" : "[geonames][0]", "_node" : "qXTymyB9QLmxhPtGEtA_mA", "_index" : "geonames", "_type" : "doc", "_id" : "L781LmkBrQo0YN4qP48D", "_score" : null, "_source" : { "id" : "3034701", "name" : "Forêt de Wissembourg", "location" : { "lat" : "49.00924", "lon" : "8.01542" } }, "sort" : [ 1523.4121312414704 ], "_explanation" : { "value" : 1.0, "description" : "*:*", "details" : [] } } ] }, "profile" : { "shards" : [ { "id" : "[qXTymyB9QLmxhPtGEtA_mA][geonames][0]", "searches" : [ { "query" : [ { "type" : "MatchAllDocsQuery", "description" : "*:*", "time_in_nanos" : 265223567, "breakdown" : { "score" : 0, "build_scorer_count" : 54, "match_count" : 0, "create_weight" : 10209, "next_doc" : 253091268, "match" : 0, "create_weight_count" : 1, "next_doc_count" : 11858087, "score_count" : 0, "build_scorer" : 263948, "advance" : 0, "advance_count" : 0 } } ], "rewrite_time" : 1097, "collector" : [ { "name" : "CancellableCollector", "reason" : "search_cancelled", "time_in_nanos" : 1044167746, "children" : [ { "name" : "SimpleFieldCollector", "reason" : "search_top_hits", "time_in_nanos" : 508296683 } ] } ] } ], "aggregations" : [] } ] } } ``` and here for descending, just switched the parameter from asc to desc (also with profile and explain): ``` { "took" : 2226, "timed_out" : false, "_shards" : { "total" : 1, "successful" : 1, "skipped" : 0, "failed" : 0 }, "hits" : { "total" : 11858060, "max_score" : null, "hits" : [ { "_shard" : "[geonames][0]", "_node" : "qXTymyB9QLmxhPtGEtA_mA", "_index" : "geonames", "_type" : "doc", "_id" : "Mq80LmkBrQo0YN4q11bA", "_score" : null, "_source" : { "id" : "4036351", "name" : "Bollons Seamount", "location" : { "lat" : "-49.66667", "lon" : "-176.16667" } }, "sort" : [ 1.970427111052182E7 ], "_explanation" : { "value" : 1.0, "description" : "*:*", "details" : [] } } ] }, "profile" : { "shards" : [ { "id" : "[qXTymyB9QLmxhPtGEtA_mA][geonames][0]", "searches" : [ { "query" : [ { "type" : "MatchAllDocsQuery", "description" : "*:*", "time_in_nanos" : 268521404, "breakdown" : { "score" : 0, "build_scorer_count" : 54, "match_count" : 0, "create_weight" : 9333, "next_doc" : 256458664, "match" : 0, "create_weight_count" : 1, "next_doc_count" : 11858087, "score_count" : 0, "build_scorer" : 195265, "advance" : 0, "advance_count" : 0 } } ], "rewrite_time" : 1142, "collector" : [ { "name" : "CancellableCollector", "reason" : "search_cancelled", "time_in_nanos" : 1898324618, "children" : [ { "name" : "SimpleFieldCollector", "reason" : "search_top_hits", "time_in_nanos" : 1368306442 } ] } ] } ], "aggregations" : [] } ] } } ``` So my question is, why is it like this ? As I understood Es calculates the distance from the origin point to every other point and then sorts them. So why is the descending sorting so much slower ? ---
**Author:** ![Ignacio\_Vera](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/ignacio_vera/32/36674_2.png) [@Ignacio\_Vera](https://discuss.elastic.co/u/Ignacio_Vera)\ **Post date:** [March 21, 2019, 4:21pm UTC](https://discuss.elastic.co/t/why-is-ascending-geo-distance-sorting-faster-than-descending-geo-distance-sorting/173328/2 "2019-03-21T16:21:53Z")
In the case of sorting ascending it uses a specialise sorting algorithm/strategy (`LatLonDocValuesField.newDistanceSort`). When sorting descending it is doing what you said. > ---
**Author:** ![gemo1011](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/gemo1011/32/45075_2.png) [@gemo1011](https://discuss.elastic.co/u/gemo1011)\ **Post date:** [March 21, 2019, 6:42pm UTC](https://discuss.elastic.co/t/why-is-ascending-geo-distance-sorting-faster-than-descending-geo-distance-sorting/173328/3 "2019-03-21T18:42:28Z")
Thank you very much for your fast answer. The different sorting strategies explain the differences in the query time. So I'm trying to understand how the ascending sorting works. My Java knowledge isn't very good, so I only see that the `LatLonDocValuesField.newDistanceSort` returns a `LatLonPointSortField` that somehow calls `SortField` ? ---
**Author:** ![Ignacio\_Vera](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/ignacio_vera/32/36674_2.png) [@Ignacio\_Vera](https://discuss.elastic.co/u/Ignacio_Vera)\ **Post date:** [March 22, 2019, 6:30am UTC](https://discuss.elastic.co/t/why-is-ascending-geo-distance-sorting-faster-than-descending-geo-distance-sorting/173328/4 "2019-03-22T06:30:05Z")
`LatLonDocValuesField.newDistanceSort` is a primitive implemented at Lucene level: > The key of the algorithm is on `LatLonPointDistanceComparator`, the javadocs explain the strategy used. A bounding box from the min competitive distance is built and therefore we can reject points based on this bounding box instead of calculating the distance for every element which is expensive. > ---
**Author:** ![gemo1011](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/gemo1011/32/45075_2.png) [@gemo1011](https://discuss.elastic.co/u/gemo1011)\ **Post date:** [March 22, 2019, 9:45am UTC](https://discuss.elastic.co/t/why-is-ascending-geo-distance-sorting-faster-than-descending-geo-distance-sorting/173328/5 "2019-03-22T09:45:31Z")
The filtering of the points beforehand with a bbox for ascending search makes sense. But I don't understand how you get the min competitive distance for calculating the bounding box. So looking at my query there are 11858060 hits that should be ordered. How do you choose the distance for the bbox ? Looking at the code it seems like it using some kind of iterative bounding box creation and calculating the distances for the points in the bbox. So for me it looks like that it takes (randomly ?) some points from the hits, calculates a bbox for the min value of this points. If they are enough points for the output they get ordered by distance. If they are not enough a bigger bbox gets created. Until enough points are gathered, or a specific number of iterations was done: `if (setBottomCounter < 1024 || (setBottomCounter & 0x3F) == 0x3F)` Thank you for taking the time explaining this issue to me. ---
**Author:** ![Ignacio\_Vera](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/ignacio_vera/32/36674_2.png) [@Ignacio\_Vera](https://discuss.elastic.co/u/Ignacio_Vera)\ **Post date:** [March 22, 2019, 10:41am UTC](https://discuss.elastic.co/t/why-is-ascending-geo-distance-sorting-faster-than-descending-geo-distance-sorting/173328/6 "2019-03-22T10:41:06Z")
The process starts the same way when you calculate the distance for all hits on your query. You get those values from the `docValues` in your index that I believe they come in the order they were writing in the index. Not sure if `setBottom(int slot)` is called every time you have a min competitive document or it is sampled. In your case because your query has a `size=1`, every new document that has a distance lower than the current min competitive document will replace the previous one. At the beginning we create a new bounding box for each call to the method `setBottomCounter < 1024` and after that we start sampling `(setBottomCounter & 0x3F) == 0x3F`. ---
**Author:** ![gemo1011](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/gemo1011/32/45075_2.png) [@gemo1011](https://discuss.elastic.co/u/gemo1011)\ **Post date:** [March 22, 2019, 1:22pm UTC](https://discuss.elastic.co/t/why-is-ascending-geo-distance-sorting-faster-than-descending-geo-distance-sorting/173328/7 "2019-03-22T13:22:34Z")
Ok, I think I'm now roughly understanding the algorithm. Thank you again ---
**Author:** ![system](https://us1.discourse-cdn.com/elastic/original/3X/1/a/1ac57faf039f6b580b3f104ef42a2a89e41014de.png) [@system](https://discuss.elastic.co/u/system)\ **Post date:** [April 19, 2019, 1:22pm UTC](https://discuss.elastic.co/t/why-is-ascending-geo-distance-sorting-faster-than-descending-geo-distance-sorting/173328/8 "2019-04-19T13:22:38Z")
This topic was automatically closed 28 days after the last reply. New replies are no longer allowed.