Learned sorting algorithm for Lucene

[josefschiefer27]

Description

I found this article about an interesting SIGMOD paper about a learned sorting algorithm which outperforms Radixsort by the factor 1.49. While the implementation doesn't look trivial, it might be an opportunity to significantly speed up the sorting in Lucene.

edit: There is an updated version (LearnedSort 2.0) which can deal better with duplicates.

cc: @jpountz @bruno-roustant

[jpountz]

This is certainly interesting and possibly applicable to Lucene as indexing involves a lot of sorting, but also looks complicated to integrate. Contributions are welcome. :)

[msokolov]

https://github.com/anikristo/LearnedSort/ is GPLv3 licensed

[bruno-roustant]

Thank you for creating this issue. This is indeed a subject I'm interested in, although currently I'm on another learned algorithm to search sorted keys. This learned sort would be the next step! Did you start some experimental implementation in Java?

[Frostfire25]

Hey, very interested in assisting with the implementation of this algorithm.

[josefschiefer27]

Here a link to the actual SIGMOD paper.