On Wed, Nov 8, 2017 at 10:33 AM, Tom Lane <t...@sss.pgh.pa.us> wrote: > I do not think there is any change here that can be proven to always be a > win. Certainly the original patch, which proposes to replace an O(n log n) > sort algorithm with an O(n^2) one, should not be thought to be that. > The question to focus on is what's the average case, and I'm not sure how > to decide what the average case is. But more than two test scenarios > would be a good start.
I appreciate the difficulties here; I'm just urging caution. Let's not change things just to clear this patch off our plate. Just to throw a random idea out here, we currently have gen_qsort_tuple.pl producing qsort_tuple() and qsort_ssup(). Maybe it could be modified to also produce a specialized qsort_itemids(). That might be noticeably faster that our general-purpose qsort() for the reasons mentioned in the comments in gen_qsort_tuple.pl, viz: # The major effects are (1) inlining simple tuple comparators is much faster # than jumping through a function pointer and (2) swap and vecswap operations # specialized to the particular data type of interest (in this case, SortTuple) # are faster than the generic routines. I don't remember any more just how much faster qsort_tuple() and qsort_ssup() are than plain qsort(), but it was significant enough to convince me to commit 337b6f5ecf05b21b5e997986884d097d60e4e3d0... -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers