GSOC 2018:Sorting algorithms benchmark and implementation

Introduction

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.

Proposal

Proposal archive: https://github.com/Strider-Alex/GSoC-2018-archive/blob/master/proposal_gsoc2018.pdf

Deliverables

• 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

Todos

• New hash table implementation