GSOC 2018:Sorting algorithms benchmark and implementation

From PostgreSQL wiki
Jump to: navigation, search

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

Todos

  • New hash table implementation