2017-01-10 14:53 GMT+05:00 Alexander Korotkov <a.korot...@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. -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers