GSOC 2018:Sorting algorithms benchmark and implementation
This project tries to improve the current sorting routine used in PostgreSQL.
Originally, PostgreSQL is using the QuickSort implemented by J. L. Bentley and M. D. McIlroy in "Engineering a sort function" with some modifications. This sorting routine is very fast, yet may fall to O(n^2) time complexity in the worst case scenario. I am trying to find faster sorting algorithms with guaranteed O(nlogn) time complexity.
In this project, I have compared several sorting algorithms and proposed a new sorting implementation.
Benefits to the PostgreSQL Community
- Using a more optimized sorting algorithm could bring a performance gain for many parts of PostgreSQL.
- The benchmark could be used for further improvement of the sorting routine.
- Sorting routines and benchmark: https://github.com/Strider-Alex/PostgreSQLSorting
- Research results: https://github.com/Strider-Alex/postgres_sorting_benchmark
- Sorting patch (intro sort implemenation): https://github.com/Strider-Alex/GSoC-2018-archive/tree/master/patch
- Community discussion of the resulting algorithm: https://www.postgresql.org/message-id/flat/5b5f8149.1c69fb81.e06c6.d054%40mx.google.com#ce794227b4efef1ae44884386933734b
- New hash table implementation