sortsupport for text

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