Re: Small improvement to compactify_tuples

On Wed, Nov 8, 2017 at 10:33 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)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