Re: B-Tree support function number 3 (strxfrm() optimization)

On Thu, Jun 5, 2014 at 8:37 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> * A configure AC_TRY_RUN tests the suitability of the system strxfrm()
> implementation for the purposes of this optimization. There can be no
> "header bytes" (people at pgCon reported redundant bytes on the Mac
> OSX implementation at pgCon, to my great surprise), ...

I'm attaching a small test program demonstrating the Mac behavior.
Here's some sample output:

[rhaas ~]$ ./strxfrm en_US "" a aa ab abc abcd abcde peter Geoghegan _ %
"" -> ""
"a" -> "001S0000001S"
"aa" -> "001S001S0000001S001S"
"ab" -> "001S001T0000001S001T"
"abc" -> "001S001T001U0000001S001T001U"
"abcd" -> "001S001T001U001V0000001S001T001U001V"
"abcde" -> "001S001T001U001V001W0000001S001T001U001V001W"
"peter" -> "001b001W001f001W001d0000001b001W001f001W001d"
"Geoghegan" -> "0019001W001a001Y001Z001W001Y001S001`00000019001W001a001Y001Z001W001Y001S001`"
"_" -> "001Q0000001Q"
"%" -> "000W0000000W"

It appears that any string starting with the letter "a" will create
output that begins with 001S00 and the seventh character always
appears to be 0 or 1:

[rhaas ~]$ ./strxfrm en_US ab ac ad ae af a% a0 "a "
"ab" -> "001S001T0000001S001T"
"ac" -> "001S001U0000001S001U"
"ad" -> "001S001V0000001S001V"
"ae" -> "001S001W0000001S001W"
"af" -> "001S001X0000001S001X"
"a%" -> "001S000W0000001S000W"
"a0" -> "001S000b0000001S000b"
"a " -> "001S000R0000001S000R"

Also, the total number of bytes produced is apparently 8N+4, where N
is the length of the input string. On a Linux system I tested, the
output included non-printable characters, so I adapted the test
program to print the results in hex. Attaching that version, too.
Here, the length was 3N+2, except for 0-length strings which produce a
0-length result:

[rhaas(at)hydra ~]$ ./strxfrm-binary en_US "" a aa ab abc abcd abcde
peter Geoghegan _ %
"" -> (0 bytes)
"a" -> 0c01020102 (5 bytes)
"aa" -> 0c0c010202010202 (8 bytes)
"ab" -> 0c0d010202010202 (8 bytes)
"abc" -> 0c0d0e0102020201020202 (11 bytes)
"abcd" -> 0c0d0e0f01020202020102020202 (14 bytes)
"abcde" -> 0c0d0e0f10010202020202010202020202 (17 bytes)
"peter" -> 1b101f101d010202020202010202020202 (17 bytes)
"Geoghegan" -> 12101a121310120c190102020202020202020201040202020202020202
(29 bytes)
"_" -> 0101010112 (5 bytes)
"%" -> 0101010139 (5 bytes)
[rhaas(at)hydra ~]$ ./strxfrm-binary en_US ab ac ad ae af a% a0 "a "
"ab" -> 0c0d010202010202 (8 bytes)
"ac" -> 0c0e010202010202 (8 bytes)
"ad" -> 0c0f010202010202 (8 bytes)
"ae" -> 0c10010202010202 (8 bytes)
"af" -> 0c11010202010202 (8 bytes)
"a%" -> 0c01020102010239 (8 bytes)
"a0" -> 0c02010202010202 (8 bytes)
"a " -> 0c01020102010211 (8 bytes)

Even though each input bytes is generating 3 output bytes, it's not
generating a group of output bytes for each input byte as appears to
be happening on MacOS X. If it were doing that, then truncating the
blob to 8 bytes would only compare the first 2-3 bytes of the input
string. In fact we do better. If we change even the 8th letter in
the string to some other letter, the 8th output byte changes:

[rhaas(at)hydra ~]$ ./strxfrm-binary en_US aaaaaaaa aaaaaaab
"aaaaaaaa" -> 0c0c0c0c0c0c0c0c010202020202020202010202020202020202 (26 bytes)
"aaaaaaab" -> 0c0c0c0c0c0c0c0d010202020202020202010202020202020202 (26 bytes)

If we change the capitalization of the eighth byte, then the change
happens further out:

[rhaas(at)hydra ~]$ ./strxfrm-binary en_US aaaaaaaa aaaaaaaA
"aaaaaaaa" -> 0c0c0c0c0c0c0c0c010202020202020202010202020202020202 (26 bytes)
"aaaaaaaA" -> 0c0c0c0c0c0c0c0c010202020202020202010202020202020204 (26 bytes)

Still, it's fair to say that on this Linux system, the first 8 bytes
capture a significant portion of the entropy of the first 8 bytes of
the string, whereas on MacOS X you only get entropy from the first 2
bytes of the string. It would be interesting to see results from
other platforms people might care about also.

> The cost of adding all of these ameliorating measures appears to be
> very low. We're so bottlenecked on memory bandwidth that the
> fixed-size overhead of maintaining poor man cardinality, and the extra
> cycles from hashing n keys for the benefit of HyperLogLog just don't
> seem to matter next to the big savings for n log n comparisons. The
> best case performance is seemingly just as good as before (about a
> 200% improvement in transaction throughput for one client, but closer
> to a 250% improvement with many clients and/or expensive collations),
> while the worst case is much much better.

I haven't looked at the patch yet, but this sounds promising.

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