sortsupport for text - Mailing list pgsql-hackers

I decided to investigate the possible virtues of allowing "text" to
use the sortsupport infrastructure, since strings are something people
often want to sort.  I generated 100,000 random alphanumeric strings,
each 30 characters in length, and loaded them into a single-column
table, froze it, ran SELECT SUM(1) FROM tablename on it until it was
fully cached, and then repeatedly quicksorted the table contents using
my default locale (en_US.UTF8).  I repeated this test a number of
times, removing and recreating the data directory via initdb each
time.  The test was performed on my home desktop, which is running
Fedora 14 (yeah, I know I should reinstall) and equipped with an AMD
Athlon 5000 Dual-Core Processor.  Here's the exact test query:

SELECT SUM(1) FROM (SELECT * FROM randomtext ORDER BY t) x;

On unpatched master, this takes about 416 ms (plus or minus a few).
With the attached patch, it takes about 389 ms (plus or minus a very
few), a speedup of about 7%.

I repeated the experiment using the C locale, like this:

SELECT SUM(1) FROM (SELECT * FROM randomtext ORDER BY t COLLATE "C") x;

Here, it takes about 202 ms with the patch, and about 231 ms on
unpatched master, a savings of about 13%.

I also tried on a larger data set of 5 million strings, with a heap
sort using work_mem=256MB.  Unfortunately, there was so much noise
there that it was hard to get any useful measurements: the exact same
code base, using the exact same test script (that started with an
initdb) could perform quite differently on consecutive runs, perhaps
because the choice of blocks chosen to contain the database itself
affected the efficiency of reading and writing temporary files.  I
think it may be faster, and the results on the smaller data set argue
that it should be faster, but I was unable to gather reproducible
numbers.  I did observe the following oprofile results on a run on
this larger data set, on master:

12789    28.2686  libc-2.13.so             strcoll_l
6802     15.0350  postgres                 text_cmp
5081     11.2310  postgres                 comparetup_heap
3510      7.7584  postgres                 comparison_shim
2892      6.3924  postgres                 lc_collate_is_c
2722      6.0167  no-vmlinux               /no-vmlinux
2596      5.7382  postgres                 varstr_cmp
2517      5.5635  libc-2.13.so             __strlen_sse2
2515      5.5591  libc-2.13.so             __memcpy_sse2
968       2.1397  postgres                 tuplesort_heap_siftup
710       1.5694  postgres                 bttextcmp
664       1.4677  postgres                 pg_detoast_datum_packed

Clearly, a lot of that is unnecessary.  Doing lc_collate_is_c for
every tuple is a complete waste; as is translating the collation OID
to collate_t; this patch arranges to do those things just once per
sort.  The comparison_shim is also a waste.  Considering all that, I
had hoped for more like a 15-20% gain from this approach, but it
didn't happen, I suppose because some of the instructions saved just
resulted in more processor stalls.  All the same, I'm inclined to
think it's still worth doing.

I didn't attempt to handle the weirdness that is UTF-8 on Windows,
since I don't develop on Windows.  I thought when I wrote this code
that I could just leave the comparator uninitialized and let the
caller default to the shim implementation if the sort-support function
didn't do anything.  But I see now that
PrepareSortSupportFromOrderingOp() feels that it's entitled to assume
that the sort-support function will always fill in a comparator.
Either that assumption needs to be changed, or the corresponding
Windows code needs to be written, or the sort support function needs
to call PrepareSortSupportComparisonShim() in this case.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company