Skip to content

Instantly share code, notes, and snippets.

@Strider-Alex

Strider-Alex/GSOC2018.md

Last active March 23, 2019 03:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Strider-Alex/253ff5b3bff8c48a6c98bdcd97ff4cbb to your computer and use it in GitHub Desktop.
Save Strider-Alex/253ff5b3bff8c48a6c98bdcd97ff4cbb to your computer and use it in GitHub Desktop.
Download ZIP
GSOC 2018: Sorting algorithms benchmark and implementation
Raw
GSOC2018.md

Introduction

The goal of this project is to improve the sorting routine in PostgreSQL.

Currently, PostgreSQL is using 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. A fast sorting algorithms with guaranteed O(nlogn) time complexity would be preferable.

This project compared several sorting algorithms and proposed a new sorting implementation.

Benefits to the PostgreSQL Community

  • Using a more optimized sorting algorithm brings a performance gain for many parts of PostgreSQL.
  • The benchmark could be used for further improvement of the sorting routine.

Proposal

Proposal archive

Wiki

PostgreSQL Wiki

Deliverables

Todos

  • New hash table implementation
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment