2017-01-10 14:53 GMT+05:00 Alexander Korotkov <a.korotkov@postgrespro.ru>:
> 1. What project ideas we have?
Hi!
I'd like to propose project on sorting algorithm research. I’m ready
to be a mentor on this project.
===Topic===
Sorting algorithms benchmark and implementation.
===Idea===
Currently the PostgreSQL uses Hoare’s Quicksort implementation based
on work of Bentley and McIlroy [1] from 1993, while there exist some
more novel algorithms [2], [3], and [4] which are actively used by
highly optimized code like Java and .NET. Probably, use of optimized
sorting algorithm could yield general system performance improvement.
Also, use of non-comparison based algorithms deserves attention and
benchmarking [5].
===Project details===
The project has four essential parts:
1. Implementation of benchmark for sorting. Making sure that
operations using sorting are represented proportionally to some
“average” use cases.
2. Selection of benchmark algorithms. Selection can be based,
for example, on scientific papers or community opinions.
3. Benchmark implementation of selected algorithms. Analysis of
results, picking of winner.
4. Industrial implementation for pg_qsort(), pg_qsort_args() and
gen_qsort_tuple.pl. Implemented patch is submitted to commitfest,
other patch is reviewed by the student.
[1] Bentley, Jon L., and M. Douglas McIlroy. "Engineering a sort
function." Software: Practice and Experience 23.11 (1993): 1249-1265.
[2] Musser, David R. "Introspective sorting and selection algorithms."
Softw., Pract. Exper. 27.8 (1997): 983-993.
[3] Auger, Nicolas, Cyril Nicaud, and Carine Pivoteau. "Merge
Strategies: from Merge Sort to TimSort." (2015).
[4] Beniwal, Sonal, and Deepti Grover. "Comparison of various sorting
algorithms: A review." International Journal of Emerging Research in
Management &Technology 2 (2013).
[5] Mcllroy, Peter M., Keith Bostic, and M. Douglas Mcllroy.
"Engineering radix sort." Computing systems 6.1 (1993): 5-27.
Best regards, Andrey Borodin.
