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

I have thought a little further about my proposal to have inner B-Tree
pages store strxfrm() blobs [1]; my earlier conclusion was that this
could not be trusted when equality was indicated [2] due to the
"Hungarian problem" [3]. As I noted earlier, that actually doesn't
really matter, because we may have missed what's really so useful
about strxfrm() blobs: We *can* trust a non-zero result as a proxy for
what we would have gotten with a proper bttextcmp(), even if a
strcmp() only looks at the first byte of a blob for each of two text
strings being compared. Here is what the strxfrm() blob looks like for
some common English words when put through glibc's strxfrm() with the
en_US.UTF-8 collation (I wrote a wrapper function to do this and
output bytea a couple of years ago):

[local]/postgres=# select strxfrm_test('Yellow');
strxfrm_test
--------------------------------------------
\x241017171a220109090909090901100909090909
(1 row)

[local]/postgres=# select strxfrm_test('Red');
strxfrm_test
--------------------------
\x1d100f0109090901100909
(1 row)

[local]/postgres=# select strxfrm_test('Orange');
strxfrm_test
--------------------------------------------
\x1a1d0c1912100109090909090901100909090909
(1 row)

[local]/postgres=# select strxfrm_test('Green');
strxfrm_test
--------------------------------------
\x121d101019010909090909011009090909
(1 row)

[local]/postgres=# select strxfrm_test('White');
strxfrm_test
--------------------------------------
\x2213141f10010909090909011009090909
(1 row)

[local]/postgres=# select strxfrm_test('Black');
strxfrm_test
--------------------------------------
\x0d170c0e16010909090909011009090909
(1 row)

Obviously, all of these blobs, while much larger than the original
string still differ in their first byte. It's almost as if they're
intended to be truncated.

The API I envisage is a new support function 3 that operator class
authors may optionally provide. Within the support function a text
varlena argument is passed, or whatever the type that relates to the
opclass happens to be. It returns a Datum to the core system. That
datum is always what is actually passed to their sort support routine
(B-Tree support function number 2) iff a support function 3 is
provided (you must provide number 2 if you provide number 3, but not
vice-versa). In respect of support-function-3-providing opclasses, the
core system is entitled to take the sort support return value as a
proxy for what a proper support function 1 call would indicate iff the
sort support routine does not return 0 in respect of two
support-function-3 blobs (typically strxfrm() blobs truncated at 8
bytes for convenient storage as pass-by-value Datums). Otherwise, a
proper call to support function 1, with fully-formed text arguments is
required.

I see at least two compelling things we can do with these blobs:

1. Store them as pseudo-columns of inner B-Tree IndexTuples (not leaf
pages). Naturally, inner pages are very heterogeneous, so only having
8 bytes is very probably an excellent trade-off there. Typically 1-3%
of B-Tree pages are inner pages, so the bloat risk seems acceptable.

2. When building a SortTuple array within TupleSort, we can store far
more of these truncated blobs in memory than we can proper strings. if
SortTuple.datum1 (the first column to sort on among tuples being
sorted, which is currently stored in memory as an optimization) was
just an 8 byte truncated strxfrm() blob, and not a pointer to a text
string in memory, that would be pretty great for performance for
several reasons. So just as with B-Tree inner pages, for SortTuples
there can be a pseudo leading key - we need only compare additional
sort keys/heap_getattr() when we need a tie-breaker, when those 8
bytes aren't enough to reach a firm conclusion.

It doesn't just stop with strxfrm() blobs, though. Why couldn't we
create blobs that can be used as reliable proxies for numerics, that
are just integers? Sure, you need to reserve a bit to indicate an
inability to represent the original value, and possibly work out other
details like that, but the only negative thing you can say about that,
or indeed applying these techniques to any operator class is that it
might not help in certain worst cases (mostly contrived cases). Still,
the overhead of doing that bit of extra work is surely quite low
anyway - at worst, a extra few instructions wasted per comparison -
making these techniques likely quite profitable for the vast majority
of real-world applications.

Does anyone else want to pick this idea up and run with it? I don't
think I'll have time for it.

[1] http://www.postgresql.org/message-id/CAM3SWZTcXrdDZSpA11qZXiyo4_jtxwjaNdZpnY54yjzq7d64=A@mail.gmail.com

[2] http://www.postgresql.org/message-id/CAM3SWZS7wewrBmRGCi9_yCX49Ug6UgqN2xNGJG3Zq5v8LbDU4g@mail.gmail.com

[3] http://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=656beff59033ccc5261a615802e1a85da68e8fad

--
Peter Geoghegan

On Wed, Mar 26, 2014 at 8:08 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> The API I envisage is a new support function 3 that operator class
> authors may optionally provide.

I've built a prototype patch, attached, that extends SortSupport and
tuplesort to support "poor man's normalized keys". All the regression
tests pass, so while it's just a proof of concept, it is reasonably
well put together for one. The primary shortcoming of the prototype
(the main reason why I'm calling it a prototype rather than just a
patch) is that it isn't sufficiently generalized (i.e. it only works
for the cases currently covered by SortSupport - not B-Tree index
builds, or B-Tree scanKeys). There is no B-Tree support function
number 3 in the patch. I didn't spend too long on this.

I'm pretty happy with the results for in-memory sorting of text (my
development system uses 'en_US.UTF8', so please assume that any costs
involved are for runs that use that collation). With the dellstore2
sample database [1] restored to my local development instance, the
following example demonstrates just how much the technique can help
performance.

With master:

pg(at)hamster:~/sort-tests$ cat sort.sql
select * from (select * from customers order by firstname offset 100000) d;
pg(at)hamster:~/sort-tests$ pgbench -f sort.sql -n -T 100
transaction type: Custom query
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
duration: 100 s
number of transactions actually processed: 819
latency average: 122.100 ms
tps = 8.186197 (including connections establishing)
tps = 8.186522 (excluding connections establishing)

With patch applied (requires initdb for new text SortSupport pg_proc entry):

pg(at)hamster:~/sort-tests$ cat sort.sql
select * from (select * from customers order by firstname offset 100000) d;
pg(at)hamster:~/sort-tests$ pgbench -f sort.sql -n -T 100
transaction type: Custom query
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
duration: 100 s
number of transactions actually processed: 2525
latency average: 39.604 ms
tps = 25.241723 (including connections establishing)
tps = 25.242447 (excluding connections establishing)

It looks like this technique is very valuable indeed, at least in the
average or best case. We're not just benefiting from following the
advice of the standard, and using strxfrm() for sorting to amortize
the cost of the strxfrm() transformation that strcoll() must do
anyway. It stands to reason that there is also a lot of benefit from
sorting tightly-packed keys. Quicksort is cache oblivious, and having
it sort tightly-packed binary data, as opposed to going through all of
that deferencing and deserialization indirection is probably also very
helpful. A tool like Cachegrind might offer some additional insights,
but I haven't gone to the trouble of trying that out.

(By the way, my earlier recollection about how memory-frugal
MinimalTuple/memtuple building is within tuplesort was incorrect, so
there are no savings in memory to be had here).

As I mentioned, something like a SortSupport for numeric, with poor
man's normalized keys might also be compelling. I suggest we focus on
how this technique can be further generalized, though. This prototype
patch is derivative of Robert's abandoned SortSupport for text patch.
If he wanted to take this off my hands, I'd have no objections - I
don't think I'm going to have time to take this as far as I'd like.

[1] http://pgfoundry.org/forum/forum.php?forum_id=603
--
Peter Geoghegan

On 31 March 2014 06:51, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Wed, Mar 26, 2014 at 8:08 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>> The API I envisage is a new support function 3 that operator class
>> authors may optionally provide.
>
> I've built a prototype patch, attached, that extends SortSupport and
> tuplesort to support "poor man's normalized keys". All the regression
> tests pass, so while it's just a proof of concept, it is reasonably
> well put together for one. The primary shortcoming of the prototype
> (the main reason why I'm calling it a prototype rather than just a
> patch) is that it isn't sufficiently generalized (i.e. it only works
> for the cases currently covered by SortSupport - not B-Tree index
> builds, or B-Tree scanKeys). There is no B-Tree support function
> number 3 in the patch. I didn't spend too long on this.
>
> I'm pretty happy with the results for in-memory sorting of text (my
> development system uses 'en_US.UTF8', so please assume that any costs
> involved are for runs that use that collation). With the dellstore2
> sample database [1] restored to my local development instance, the
> following example demonstrates just how much the technique can help
> performance.
>
> With master:
>
> pg(at)hamster:~/sort-tests$ cat sort.sql
> select * from (select * from customers order by firstname offset 100000) d;
> pg(at)hamster:~/sort-tests$ pgbench -f sort.sql -n -T 100
> transaction type: Custom query
> scaling factor: 1
> query mode: simple
> number of clients: 1
> number of threads: 1
> duration: 100 s
> number of transactions actually processed: 819
> latency average: 122.100 ms
> tps = 8.186197 (including connections establishing)
> tps = 8.186522 (excluding connections establishing)
>
> With patch applied (requires initdb for new text SortSupport pg_proc entry):
>
> pg(at)hamster:~/sort-tests$ cat sort.sql
> select * from (select * from customers order by firstname offset 100000) d;
> pg(at)hamster:~/sort-tests$ pgbench -f sort.sql -n -T 100
> transaction type: Custom query
> scaling factor: 1
> query mode: simple
> number of clients: 1
> number of threads: 1
> duration: 100 s
> number of transactions actually processed: 2525
> latency average: 39.604 ms
> tps = 25.241723 (including connections establishing)
> tps = 25.242447 (excluding connections establishing)

As another data point, I ran the same benchmark, but I don't appear to
yield the same positive result. An initdb was done for each rebuild,
my system uses en_GB.UTF-8 (if that's relevant) and I used your same
sort.sql...

With master:

thom(at)swift ~/Development $ pgbench -f sort.sql -n -T 100 ds2
transaction type: Custom query
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
duration: 100 s
number of transactions actually processed: 421479
latency average: 0.237 ms
tps = 4214.769601 (including connections establishing)
tps = 4214.906079 (excluding connections establishing)

With patch applied:

thom(at)swift ~/Development $ pgbench -f sort.sql -n -T 100 ds2
transaction type: Custom query
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
duration: 100 s
number of transactions actually processed: 412405
latency average: 0.242 ms
tps = 4124.047237 (including connections establishing)
tps = 4124.177437 (excluding connections establishing)

And with 4 runs (TPS):

Master: 4214.906079 / 4564.532623 / 4152.784608 / 4152.578297 (avg: 4271)
Patched: 4124.177437 / 3777.561869 / 3777.561869 / 2484.220475 (avg: 3481)

I'm not sure what's causing the huge variation. I ran 5 minute benchmarks too:

Master:

thom(at)swift ~/Development $ pgbench -f sort.sql -n -T 300 ds2
transaction type: Custom query
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
duration: 300 s
number of transactions actually processed: 1092221
latency average: 0.275 ms
tps = 3640.733002 (including connections establishing)
tps = 3640.784628 (excluding connections establishing)

Patched:

thom(at)swift ~/Development $ pgbench -f sort.sql -n -T 300 ds2
transaction type: Custom query
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
duration: 300 s
number of transactions actually processed: 1068239
latency average: 0.281 ms
tps = 3560.794946 (including connections establishing)
tps = 3560.835076 (excluding connections establishing)

And per-second results for the first 30 seconds:

Master:

progress: 1.0 s, 2128.8 tps, lat 0.464 ms stddev 0.084
progress: 2.0 s, 2138.9 tps, lat 0.464 ms stddev 0.015
progress: 3.0 s, 2655.6 tps, lat 0.374 ms stddev 0.151
progress: 4.0 s, 2214.0 tps, lat 0.448 ms stddev 0.080
progress: 5.0 s, 2171.1 tps, lat 0.457 ms stddev 0.071
progress: 6.0 s, 2131.6 tps, lat 0.466 ms stddev 0.035
progress: 7.0 s, 3811.2 tps, lat 0.260 ms stddev 0.177
progress: 8.0 s, 2139.6 tps, lat 0.464 ms stddev 0.017
progress: 9.0 s, 7989.7 tps, lat 0.124 ms stddev 0.091
progress: 10.0 s, 8509.7 tps, lat 0.117 ms stddev 0.062
progress: 11.0 s, 3131.3 tps, lat 0.317 ms stddev 0.177
progress: 12.0 s, 9362.1 tps, lat 0.106 ms stddev 0.006
progress: 13.0 s, 5831.0 tps, lat 0.170 ms stddev 0.137
progress: 14.0 s, 4949.3 tps, lat 0.201 ms stddev 0.156
progress: 15.0 s, 2136.9 tps, lat 0.464 ms stddev 0.028
progress: 16.0 s, 3918.3 tps, lat 0.253 ms stddev 0.177
progress: 17.0 s, 4102.7 tps, lat 0.242 ms stddev 0.122
progress: 18.0 s, 2997.6 tps, lat 0.331 ms stddev 0.151
progress: 19.0 s, 2139.1 tps, lat 0.464 ms stddev 0.034
progress: 20.0 s, 3189.5 tps, lat 0.311 ms stddev 0.173
progress: 21.0 s, 2120.7 tps, lat 0.468 ms stddev 0.030
progress: 22.0 s, 3197.7 tps, lat 0.311 ms stddev 0.182
progress: 23.0 s, 2115.3 tps, lat 0.469 ms stddev 0.034
progress: 24.0 s, 2129.0 tps, lat 0.466 ms stddev 0.031
progress: 25.0 s, 2190.7 tps, lat 0.453 ms stddev 0.106
progress: 26.0 s, 2118.6 tps, lat 0.468 ms stddev 0.031
progress: 27.0 s, 2136.8 tps, lat 0.464 ms stddev 0.018
progress: 28.0 s, 5160.7 tps, lat 0.193 ms stddev 0.156
progress: 29.0 s, 2312.5 tps, lat 0.429 ms stddev 0.107
progress: 30.0 s, 2145.9 tps, lat 0.463 ms stddev 0.038
progress: 31.0 s, 2107.6 tps, lat 0.471 ms stddev 0.071

Patched:

progress: 1.0 s, 2136.2 tps, lat 0.463 ms stddev 0.084
progress: 2.0 s, 2153.3 tps, lat 0.461 ms stddev 0.035
progress: 3.0 s, 2336.0 tps, lat 0.425 ms stddev 0.112
progress: 4.0 s, 2144.8 tps, lat 0.463 ms stddev 0.037
progress: 5.0 s, 2171.7 tps, lat 0.457 ms stddev 0.041
progress: 6.0 s, 2161.9 tps, lat 0.459 ms stddev 0.036
progress: 7.0 s, 2143.1 tps, lat 0.463 ms stddev 0.019
progress: 8.0 s, 2148.4 tps, lat 0.462 ms stddev 0.032
progress: 9.0 s, 2142.1 tps, lat 0.463 ms stddev 0.028
progress: 10.0 s, 2133.6 tps, lat 0.465 ms stddev 0.032
progress: 11.0 s, 2138.3 tps, lat 0.464 ms stddev 0.020
progress: 12.0 s, 2578.7 tps, lat 0.385 ms stddev 0.149
progress: 13.0 s, 2455.6 tps, lat 0.404 ms stddev 0.119
progress: 14.0 s, 2909.5 tps, lat 0.341 ms stddev 0.170
progress: 15.0 s, 2133.7 tps, lat 0.465 ms stddev 0.025
progress: 16.0 s, 2876.9 tps, lat 0.345 ms stddev 0.160
progress: 17.0 s, 2167.1 tps, lat 0.458 ms stddev 0.038
progress: 18.0 s, 3623.4 tps, lat 0.274 ms stddev 0.181
progress: 19.0 s, 2476.3 tps, lat 0.401 ms stddev 0.137
progress: 20.0 s, 2166.9 tps, lat 0.458 ms stddev 0.030
progress: 21.0 s, 3150.0 tps, lat 0.315 ms stddev 0.176
progress: 22.0 s, 2220.3 tps, lat 0.447 ms stddev 0.084
progress: 23.0 s, 2131.3 tps, lat 0.466 ms stddev 0.030
progress: 24.0 s, 2154.2 tps, lat 0.461 ms stddev 0.047
progress: 25.0 s, 2122.5 tps, lat 0.468 ms stddev 0.040
progress: 26.0 s, 2202.2 tps, lat 0.451 ms stddev 0.079
progress: 27.0 s, 2150.6 tps, lat 0.461 ms stddev 0.039
progress: 28.0 s, 2156.1 tps, lat 0.460 ms stddev 0.027
progress: 29.0 s, 2152.1 tps, lat 0.461 ms stddev 0.028
progress: 30.0 s, 2235.4 tps, lat 0.444 ms stddev 0.071

--
Thom

On 31 March 2014 11:32, Thom Brown <thom(at)linux(dot)com> wrote:
> On 31 March 2014 06:51, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>> On Wed, Mar 26, 2014 at 8:08 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>>> The API I envisage is a new support function 3 that operator class
>>> authors may optionally provide.
>>
>> I've built a prototype patch, attached, that extends SortSupport and
>> tuplesort to support "poor man's normalized keys". All the regression
>> tests pass, so while it's just a proof of concept, it is reasonably
>> well put together for one. The primary shortcoming of the prototype
>> (the main reason why I'm calling it a prototype rather than just a
>> patch) is that it isn't sufficiently generalized (i.e. it only works
>> for the cases currently covered by SortSupport - not B-Tree index
>> builds, or B-Tree scanKeys). There is no B-Tree support function
>> number 3 in the patch. I didn't spend too long on this.
>>
>> I'm pretty happy with the results for in-memory sorting of text (my
>> development system uses 'en_US.UTF8', so please assume that any costs
>> involved are for runs that use that collation). With the dellstore2
>> sample database [1] restored to my local development instance, the
>> following example demonstrates just how much the technique can help
>> performance.
>>
>> With master:
>>
>> pg(at)hamster:~/sort-tests$ cat sort.sql
>> select * from (select * from customers order by firstname offset 100000) d;
>> pg(at)hamster:~/sort-tests$ pgbench -f sort.sql -n -T 100
>> transaction type: Custom query
>> scaling factor: 1
>> query mode: simple
>> number of clients: 1
>> number of threads: 1
>> duration: 100 s
>> number of transactions actually processed: 819
>> latency average: 122.100 ms
>> tps = 8.186197 (including connections establishing)
>> tps = 8.186522 (excluding connections establishing)
>>
>> With patch applied (requires initdb for new text SortSupport pg_proc entry):
>>
>> pg(at)hamster:~/sort-tests$ cat sort.sql
>> select * from (select * from customers order by firstname offset 100000) d;
>> pg(at)hamster:~/sort-tests$ pgbench -f sort.sql -n -T 100
>> transaction type: Custom query
>> scaling factor: 1
>> query mode: simple
>> number of clients: 1
>> number of threads: 1
>> duration: 100 s
>> number of transactions actually processed: 2525
>> latency average: 39.604 ms
>> tps = 25.241723 (including connections establishing)
>> tps = 25.242447 (excluding connections establishing)
>
> As another data point, I ran the same benchmark, but I don't appear to
> yield the same positive result. An initdb was done for each rebuild,
> my system uses en_GB.UTF-8 (if that's relevant) and I used your same
> sort.sql...
>
> With master:
>
> thom(at)swift ~/Development $ pgbench -f sort.sql -n -T 100 ds2
> transaction type: Custom query
> scaling factor: 1
> query mode: simple
> number of clients: 1
> number of threads: 1
> duration: 100 s
> number of transactions actually processed: 421479
> latency average: 0.237 ms
> tps = 4214.769601 (including connections establishing)
> tps = 4214.906079 (excluding connections establishing)
>
> With patch applied:
>
> thom(at)swift ~/Development $ pgbench -f sort.sql -n -T 100 ds2
> transaction type: Custom query
> scaling factor: 1
> query mode: simple
> number of clients: 1
> number of threads: 1
> duration: 100 s
> number of transactions actually processed: 412405
> latency average: 0.242 ms
> tps = 4124.047237 (including connections establishing)
> tps = 4124.177437 (excluding connections establishing)
>
>
> And with 4 runs (TPS):
>
> Master: 4214.906079 / 4564.532623 / 4152.784608 / 4152.578297 (avg: 4271)
> Patched: 4124.177437 / 3777.561869 / 3777.561869 / 2484.220475 (avg: 3481)
>
> I'm not sure what's causing the huge variation. I ran 5 minute benchmarks too:
>
> Master:
>
> thom(at)swift ~/Development $ pgbench -f sort.sql -n -T 300 ds2
> transaction type: Custom query
> scaling factor: 1
> query mode: simple
> number of clients: 1
> number of threads: 1
> duration: 300 s
> number of transactions actually processed: 1092221
> latency average: 0.275 ms
> tps = 3640.733002 (including connections establishing)
> tps = 3640.784628 (excluding connections establishing)
>
>
> Patched:
>
> thom(at)swift ~/Development $ pgbench -f sort.sql -n -T 300 ds2
> transaction type: Custom query
> scaling factor: 1
> query mode: simple
> number of clients: 1
> number of threads: 1
> duration: 300 s
> number of transactions actually processed: 1068239
> latency average: 0.281 ms
> tps = 3560.794946 (including connections establishing)
> tps = 3560.835076 (excluding connections establishing)
>
>
>
> And per-second results for the first 30 seconds:
>
>
> Master:
>
> progress: 1.0 s, 2128.8 tps, lat 0.464 ms stddev 0.084
> progress: 2.0 s, 2138.9 tps, lat 0.464 ms stddev 0.015
> progress: 3.0 s, 2655.6 tps, lat 0.374 ms stddev 0.151
> progress: 4.0 s, 2214.0 tps, lat 0.448 ms stddev 0.080
> progress: 5.0 s, 2171.1 tps, lat 0.457 ms stddev 0.071
> progress: 6.0 s, 2131.6 tps, lat 0.466 ms stddev 0.035
> progress: 7.0 s, 3811.2 tps, lat 0.260 ms stddev 0.177
> progress: 8.0 s, 2139.6 tps, lat 0.464 ms stddev 0.017
> progress: 9.0 s, 7989.7 tps, lat 0.124 ms stddev 0.091
> progress: 10.0 s, 8509.7 tps, lat 0.117 ms stddev 0.062
> progress: 11.0 s, 3131.3 tps, lat 0.317 ms stddev 0.177
> progress: 12.0 s, 9362.1 tps, lat 0.106 ms stddev 0.006
> progress: 13.0 s, 5831.0 tps, lat 0.170 ms stddev 0.137
> progress: 14.0 s, 4949.3 tps, lat 0.201 ms stddev 0.156
> progress: 15.0 s, 2136.9 tps, lat 0.464 ms stddev 0.028
> progress: 16.0 s, 3918.3 tps, lat 0.253 ms stddev 0.177
> progress: 17.0 s, 4102.7 tps, lat 0.242 ms stddev 0.122
> progress: 18.0 s, 2997.6 tps, lat 0.331 ms stddev 0.151
> progress: 19.0 s, 2139.1 tps, lat 0.464 ms stddev 0.034
> progress: 20.0 s, 3189.5 tps, lat 0.311 ms stddev 0.173
> progress: 21.0 s, 2120.7 tps, lat 0.468 ms stddev 0.030
> progress: 22.0 s, 3197.7 tps, lat 0.311 ms stddev 0.182
> progress: 23.0 s, 2115.3 tps, lat 0.469 ms stddev 0.034
> progress: 24.0 s, 2129.0 tps, lat 0.466 ms stddev 0.031
> progress: 25.0 s, 2190.7 tps, lat 0.453 ms stddev 0.106
> progress: 26.0 s, 2118.6 tps, lat 0.468 ms stddev 0.031
> progress: 27.0 s, 2136.8 tps, lat 0.464 ms stddev 0.018
> progress: 28.0 s, 5160.7 tps, lat 0.193 ms stddev 0.156
> progress: 29.0 s, 2312.5 tps, lat 0.429 ms stddev 0.107
> progress: 30.0 s, 2145.9 tps, lat 0.463 ms stddev 0.038
> progress: 31.0 s, 2107.6 tps, lat 0.471 ms stddev 0.071
>
>
>
> Patched:
>
> progress: 1.0 s, 2136.2 tps, lat 0.463 ms stddev 0.084
> progress: 2.0 s, 2153.3 tps, lat 0.461 ms stddev 0.035
> progress: 3.0 s, 2336.0 tps, lat 0.425 ms stddev 0.112
> progress: 4.0 s, 2144.8 tps, lat 0.463 ms stddev 0.037
> progress: 5.0 s, 2171.7 tps, lat 0.457 ms stddev 0.041
> progress: 6.0 s, 2161.9 tps, lat 0.459 ms stddev 0.036
> progress: 7.0 s, 2143.1 tps, lat 0.463 ms stddev 0.019
> progress: 8.0 s, 2148.4 tps, lat 0.462 ms stddev 0.032
> progress: 9.0 s, 2142.1 tps, lat 0.463 ms stddev 0.028
> progress: 10.0 s, 2133.6 tps, lat 0.465 ms stddev 0.032
> progress: 11.0 s, 2138.3 tps, lat 0.464 ms stddev 0.020
> progress: 12.0 s, 2578.7 tps, lat 0.385 ms stddev 0.149
> progress: 13.0 s, 2455.6 tps, lat 0.404 ms stddev 0.119
> progress: 14.0 s, 2909.5 tps, lat 0.341 ms stddev 0.170
> progress: 15.0 s, 2133.7 tps, lat 0.465 ms stddev 0.025
> progress: 16.0 s, 2876.9 tps, lat 0.345 ms stddev 0.160
> progress: 17.0 s, 2167.1 tps, lat 0.458 ms stddev 0.038
> progress: 18.0 s, 3623.4 tps, lat 0.274 ms stddev 0.181
> progress: 19.0 s, 2476.3 tps, lat 0.401 ms stddev 0.137
> progress: 20.0 s, 2166.9 tps, lat 0.458 ms stddev 0.030
> progress: 21.0 s, 3150.0 tps, lat 0.315 ms stddev 0.176
> progress: 22.0 s, 2220.3 tps, lat 0.447 ms stddev 0.084
> progress: 23.0 s, 2131.3 tps, lat 0.466 ms stddev 0.030
> progress: 24.0 s, 2154.2 tps, lat 0.461 ms stddev 0.047
> progress: 25.0 s, 2122.5 tps, lat 0.468 ms stddev 0.040
> progress: 26.0 s, 2202.2 tps, lat 0.451 ms stddev 0.079
> progress: 27.0 s, 2150.6 tps, lat 0.461 ms stddev 0.039
> progress: 28.0 s, 2156.1 tps, lat 0.460 ms stddev 0.027
> progress: 29.0 s, 2152.1 tps, lat 0.461 ms stddev 0.028
> progress: 30.0 s, 2235.4 tps, lat 0.444 ms stddev 0.071

While this seems to indicate some kind or regression with the patch,
I've just realised that the data files weren't read in as the csv
files were in the wrong path, so that explains the very high tps.
*facepalm* So here are the *right* benchmarks:

Master:

thom(at)swift ~/Development $ pgbench -f sort.sql -n -T 100 ds2
transaction type: Custom query
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
duration: 100 s
number of transactions actually processed: 2093
latency average: 47.778 ms
tps = 20.920833 (including connections establishing)
tps = 20.921719 (excluding connections establishing)

(a repeat shows 20.737619)

With patch:

thom(at)swift ~/Development $ pgbench -f sort.sql -n -T 100 ds2
transaction type: Custom query
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
duration: 100 s
number of transactions actually processed: 6148
latency average: 16.265 ms
tps = 61.477152 (including connections establishing)
tps = 61.479736 (excluding connections establishing)

(a repeat shows 62.252024)

So clearly a 3-fold improvement in this case.
--
Thom

On 03/31/2014 08:51 AM, Peter Geoghegan wrote:
> + #ifdef HAVE_LOCALE_T
> + if (tss->locale)
> + strxfrm_l(pres, tss->buf1, Min(sizeof(Datum), len), tss->locale);
> + else
> + #endif
> + strxfrm(pres, tss->buf1, Min(sizeof(Datum), len));
> +
> + pres[Min(sizeof(Datum) - 1, len)] = '\0';

I'm afraid that trick isn't 100% reliable. The man page for strxrfm says:

> RETURN VALUE
> The strxfrm() function returns the number of bytes required to store
> the transformed string in dest excluding the terminating null byte
> ('\0'). If the value returned is n or more, the contents of dest are
> indeterminate.

Note the last sentence. To avoid the undefined behavior, you have to
pass a buffer that's large enough to hold the whole result, and then
truncate the result.

- Heikki

On Mon, Mar 31, 2014 at 8:08 AM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> Note the last sentence. To avoid the undefined behavior, you have to pass a
> buffer that's large enough to hold the whole result, and then truncate the
> result.

I was working off the glibc documentation, which says:

"The return value is the length of the entire transformed string. This
value is not affected by the value of size, but if it is greater or
equal than size, it means that the transformed string did not entirely
fit in the array to. In this case, only as much of the string as
actually fits was stored. To get the whole transformed string, call
strxfrm again with a bigger output array."

It looks like this may be a glibc-ism. I'm not sure whether or not
it's worth attempting to benefit from glibc's apparent additional
guarantees here. Obviously that is something that would have to be
judged by weighing any actual additional benefit. FWIW, I didn't
actually imagine that this was a trick I was exploiting. I wouldn't be
surprised if this wasn't very important in practice.

--
Peter Geoghegan

Peter Geoghegan <pg(at)heroku(dot)com> writes:
> On Mon, Mar 31, 2014 at 8:08 AM, Heikki Linnakangas
> <hlinnakangas(at)vmware(dot)com> wrote:
>> Note the last sentence. To avoid the undefined behavior, you have to pass a
>> buffer that's large enough to hold the whole result, and then truncate the
>> result.

> I was working off the glibc documentation, which says:

> "The return value is the length of the entire transformed string. This
> value is not affected by the value of size, but if it is greater or
> equal than size, it means that the transformed string did not entirely
> fit in the array to. In this case, only as much of the string as
> actually fits was stored. To get the whole transformed string, call
> strxfrm again with a bigger output array."

> It looks like this may be a glibc-ism.

Possibly worth noting is that on my RHEL6 and Fedora machines,
"man strxfrm" says the same thing as the POSIX spec. Likewise on OS X.
I don't think we can rely on what you suggest.

regards, tom lane

On Mon, Mar 31, 2014 at 1:30 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Possibly worth noting is that on my RHEL6 and Fedora machines,
> "man strxfrm" says the same thing as the POSIX spec. Likewise on OS X.
> I don't think we can rely on what you suggest.

Okay. Attached revision only trusts strxfrm() blobs (as far as that
goes) when the buffer passed to strxfrm() was sufficiently large that
the blob could fully fit. We're now managing two buffers as part of
the text sort support state (for leading poor man's keys, rather than
just for non-leading keys as before) - one for the original string (to
put in a NULL byte, since like strcoll(), strxfrm() expects that), and
the other to temporarily store the blob before memcpy()ing over to the
pass-by-value poor man's normalized key Datum. These are the same two
persistent sortsupport-state buffers used when sorting a non-leading
text key, where there is one for each string that needs to have a NULL
byte appended.

This appears to perform at least as well as the prior revision, and
possibly even appreciably better. I guess that glibc was internally
managing a buffer to do much the same thing, so perhaps we gain
something more from mostly avoiding that with a longer lived buffer.

Perhaps you could investigate the performance of this new revision too, Thom?

I'd really like to see this basic approach expanded to store pseudo
leading keys in internal B-Tree pages too, per my earlier proposals.
At the very least, B-Tree index builds should benefit from this. I
think I'm really only scratching the surface here, both in terms of
the number of places in the code where a poor man's normalized key
could usefully be exploited, as well as in terms of the number of
B-Tree operator classes that could be made to provide one.

--
Peter Geoghegan

On Mon, Mar 31, 2014 at 7:35 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> Okay. Attached revision only trusts strxfrm() blobs (as far as that
> goes) when the buffer passed to strxfrm() was sufficiently large that
> the blob could fully fit.

Attached revision has been further polished. I've added two additional
optimizations:

* Squeeze the last byte out of each Datum, so that on a 64-bit system,
the full 8 bytes are available to store strxfrm() blobs.

* Figure out when the strcoll() bttextfastcmp_locale() comparator is
called, if it was called because a poor man's comparison required it
(and *not* because it's the non-leading key in the traditional sense,
which implies there are no poorman's normalized keys in respect of
this attribute at all). This allows us to try and get away with a
straight memcmp if and when the lengths of the original text strings
match, on the assumption that when the initial poorman's comparison
didn't work out, and when the string lengths match, there is a very
good chance that both are equal, and on average it's a win to avoid
doing a strcoll() (along with the attendant copying around of buffers
for NULL-termination) entirely. Given that memcmp() is so much cheaper
than strcoll() anyway, this seems like a good trade-off.

--
Peter Geoghegan

On 3 April 2014 17:52, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Mon, Mar 31, 2014 at 7:35 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>> Okay. Attached revision only trusts strxfrm() blobs (as far as that
>> goes) when the buffer passed to strxfrm() was sufficiently large that
>> the blob could fully fit.
>
> Attached revision has been further polished. I've added two additional
> optimizations:
>
> * Squeeze the last byte out of each Datum, so that on a 64-bit system,
> the full 8 bytes are available to store strxfrm() blobs.
>
> * Figure out when the strcoll() bttextfastcmp_locale() comparator is
> called, if it was called because a poor man's comparison required it
> (and *not* because it's the non-leading key in the traditional sense,
> which implies there are no poorman's normalized keys in respect of
> this attribute at all). This allows us to try and get away with a
> straight memcmp if and when the lengths of the original text strings
> match, on the assumption that when the initial poorman's comparison
> didn't work out, and when the string lengths match, there is a very
> good chance that both are equal, and on average it's a win to avoid
> doing a strcoll() (along with the attendant copying around of buffers
> for NULL-termination) entirely. Given that memcmp() is so much cheaper
> than strcoll() anyway, this seems like a good trade-off.

I'm getting an error when building this:

In file included from printtup.c:23:0:
../../../../src/include/utils/memdebug.h:21:31: fatal error:
valgrind/memcheck.h: No such file or directory
compilation terminated.
gcc -O2 -Wall -Wmissing-prototypes -Wpointer-arith
-Wdeclaration-after-statement -Wendif-labels
-Wmissing-format-attribute -Wformat-security -fno-strict-aliasing
-fwrapv -fexcess-precision=standard -I../../../src/include
-D_GNU_SOURCE -c -o analyze.o analyze.c -MMD -MP -MF
.deps/analyze.Po
make[4]: *** [printtup.o] Error 1
make[4]: Leaving directory
`/home/thom/Development/postgresql/src/backend/access/common'
make[3]: *** [common-recursive] Error 2
make[3]: Leaving directory
`/home/thom/Development/postgresql/src/backend/access'
make[2]: *** [access-recursive] Error 2
make[2]: *** Waiting for unfinished jobs....

--
Thom

On Thu, Apr 3, 2014 at 1:23 PM, Thom Brown <thom(at)linux(dot)com> wrote:
> I'm getting an error when building this:

Sorry. I ran this through Valgrind, and forgot to reset where the
relevant macro is define'd before submission. Attached revision should
build without issue.

--
Peter Geoghegan

On 3 April 2014 19:05, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Thu, Apr 3, 2014 at 1:23 PM, Thom Brown <thom(at)linux(dot)com> wrote:
>> I'm getting an error when building this:
>
> Sorry. I ran this through Valgrind, and forgot to reset where the
> relevant macro is define'd before submission. Attached revision should
> build without issue.

Looking good:

-T 100 -n -f sort.sql

Master: 21.670467 / 21.718653 (avg: 21.69456)
Patch: 66.888756 / 66.888756 (avg: 66.888756)

308% increase in speed

-c 80 -j 80 -T 100 -n -f sort.sql

Master: 38.450082 / 37.440701 (avg: 37.9453915)
Patch: 153.321946 / 145.004726 (avg: 149.163336)

393% increase in speed

--
Thom

On Thu, Apr 3, 2014 at 3:19 PM, Thom Brown <thom(at)linux(dot)com> wrote:
> Master: 38.450082 / 37.440701 (avg: 37.9453915)
> Patch: 153.321946 / 145.004726 (avg: 149.163336)

I think that those are objectively very large reductions in a cost
that figures prominently in most workloads. Based solely on those
facts, but also on the fairly low complexity of the patch, it may be
worth considering committing this before 9.4 goes into feature freeze,
purely as something that just adds a SortSupport function for the
default text opclass, with more or less the same cases accelerated as
with the existing SortSupport-supplying-opclasses. There has been only
very modest expansions to the SortSupport and tuplesort code. I
haven't generalized this to work with other areas where a normalized
key could be put to good use, but I see no reason to block on that.

Obviously I've missed the final commitfest deadline by a wide berth. I
don't suggest this lightly, and it in no small part has a lot to do
with the patch being simple and easy to reason about. The patch could
almost (but not quite) be written as part of a third party text
operator class's sort support routine. I think that if an individual
committer were willing to commit this at their own discretion before
feature freeze, outside of the formal commitfest process, that would
not be an unreasonable thing in these particular, somewhat unusual
circumstances.

I defer entirely to the judgement of others here - this is not an
issue that I feel justified in expressing a strong opinion on, and in
fact I don't have such an opinion anyway. However, by actually looking
at the risks and the benefits here, I think everyone will at least
understand why I'd feel justified in broaching the topic. This is a
very simple idea, and a rather old one at that.

--
Peter Geoghegan

Peter Geoghegan <pg(at)heroku(dot)com> writes:
> I think that those are objectively very large reductions in a cost
> that figures prominently in most workloads. Based solely on those
> facts, but also on the fairly low complexity of the patch, it may be
> worth considering committing this before 9.4 goes into feature freeze,

Personally, I have paid no attention to this thread and have no intention
of doing so before feature freeze. There are three dozen patches at
https://commitfest.postgresql.org/action/commitfest_view?id=21
that have moral priority for consideration for 9.4. Not all of them are
going to get in, certainly, and I'm already feeling a lot of guilt about
the small amount of time I've been able to devote to reviewing/committing
patches this cycle. Spending time now on patches that didn't even exist
at the submission deadline feels quite unfair to me.

Perhaps I shouldn't lay my own guilt trip on other committers --- but
I think it would be a bad precedent to not deal with the existing patch
queue first.

regards, tom lane

On Thu, Apr 3, 2014 at 11:44 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Personally, I have paid no attention to this thread and have no intention
> of doing so before feature freeze.

Anything that you missed was likely musings on how to further
generalize SortSupport. The actual additions to SortSupport and
tuplesort proposed are rather small. A simple abstraction to allow for
semi-reliable normalized keys, and a text sort support function to use
it.

> Perhaps I shouldn't lay my own guilt trip on other committers --- but
> I think it would be a bad precedent to not deal with the existing patch
> queue first.

I think that that's a matter of personal priorities for committers. I
am not in a position to tell anyone what their priorities ought to be,
and giving extra attention to this patch may be unfair. It doesn't
have to be a zero-sum game, though. Attention from a committer to,
say, this patch does not necessarily have to come at the expense of
another, if for example this patch piques somebody's interest and
causes them to put extra work into it on top of what they'd already
planned to look at. Again, under these somewhat unusual circumstances,
that seems like something that some committer might be inclined to do,
without it being altogether unreasonable. Then again, perhaps not.

--
Peter Geoghegan

On Thu, Apr 03, 2014 at 11:44:46PM -0400, Tom Lane wrote:
> Peter Geoghegan <pg(at)heroku(dot)com> writes:
> > I think that those are objectively very large reductions in a cost
> > that figures prominently in most workloads. Based solely on those
> > facts, but also on the fairly low complexity of the patch, it may be
> > worth considering committing this before 9.4 goes into feature freeze,
>
> Personally, I have paid no attention to this thread and have no intention
> of doing so before feature freeze. There are three dozen patches at
> https://commitfest.postgresql.org/action/commitfest_view?id=21
> that have moral priority for consideration for 9.4. Not all of them are
> going to get in, certainly, and I'm already feeling a lot of guilt about
> the small amount of time I've been able to devote to reviewing/committing
> patches this cycle. Spending time now on patches that didn't even exist
> at the submission deadline feels quite unfair to me.
>
> Perhaps I shouldn't lay my own guilt trip on other committers --- but
> I think it would be a bad precedent to not deal with the existing patch
> queue first.

+1

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

On Fri, Apr 4, 2014 at 12:13 PM, Noah Misch <noah(at)leadboat(dot)com> wrote:
> On Thu, Apr 03, 2014 at 11:44:46PM -0400, Tom Lane wrote:
>> Peter Geoghegan <pg(at)heroku(dot)com> writes:
>> > I think that those are objectively very large reductions in a cost
>> > that figures prominently in most workloads. Based solely on those
>> > facts, but also on the fairly low complexity of the patch, it may be
>> > worth considering committing this before 9.4 goes into feature freeze,
>>
>> Personally, I have paid no attention to this thread and have no intention
>> of doing so before feature freeze. There are three dozen patches at
>> https://commitfest.postgresql.org/action/commitfest_view?id=21
>> that have moral priority for consideration for 9.4. Not all of them are
>> going to get in, certainly, and I'm already feeling a lot of guilt about
>> the small amount of time I've been able to devote to reviewing/committing
>> patches this cycle. Spending time now on patches that didn't even exist
>> at the submission deadline feels quite unfair to me.
>>
>> Perhaps I shouldn't lay my own guilt trip on other committers --- but
>> I think it would be a bad precedent to not deal with the existing patch
>> queue first.
>
> +1

+1

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

On Fri, Apr 4, 2014 at 12:15 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> >> Perhaps I shouldn't lay my own guilt trip on other committers --- but
> >> I think it would be a bad precedent to not deal with the existing patch
> >> queue first.
> >
> > +1
>
> +1

I don't think we have to promise a strict priority queue and preempt all
other development. But I agree loosely that processing patches that have
been around should be a higher priority.

I've been meaning to do more review for a while and just took a skim
through the queue. There are only a couple I feel I can contribute with so
I'm going to work on those and then if it's still before the feature freeze
I would like to go ahead with Peter's patch. I think it's generally a good
patch.

Two questions I have:

1) Would it make more sense to use a floating point instead of an integer?
I saw a need for a function like this when I was looking into doing GPU
sorts. But GPUs expect floating point values.

2) I would want to see a second data type, probably numeric, before
committing to be sure we had a reasonably generic api. But it's pretty
simply to do so.

--
greg

On Fri, Apr 4, 2014 at 5:29 PM, Greg Stark <stark(at)mit(dot)edu> wrote:
> Two questions I have:
>
> 1) Would it make more sense to use a floating point instead of an integer? I
> saw a need for a function like this when I was looking into doing GPU sorts.
> But GPUs expect floating point values.

In the context of this patch, I don't think you want to add
uncertainty to the != 0 or ==0 case (which is what FP would do).

On Fri, Apr 4, 2014 at 4:29 PM, Greg Stark <stark(at)mit(dot)edu> wrote:
> 1) Would it make more sense to use a floating point instead of an integer? I
> saw a need for a function like this when I was looking into doing GPU sorts.
> But GPUs expect floating point values.

There is no reason to assume that the normalized keys within the
memtuples array need to be compared as integers, floats, or anything
else. That's a matter for the opclass author. Right now, it happens to
be the case that some of our earlier aspirations for SortSupport, such
as alternative user-defined sorting algorithms are not supported. This
is presumably only because no one came up with a compelling
alternative (i.e. no one followed through with trying to figure out if
radix sort added much value). It wouldn't be very hard to make
SortSupport and tuplesort care about that, but that's a separate
issue.

> 2) I would want to see a second data type, probably numeric, before
> committing to be sure we had a reasonably generic api. But it's pretty
> simply to do so.

I could pretty easily write a numeric proof of concept. I don't think
it would prove anything about the interface, though - I've only had
tuplesort and SortSupport assume that normalized keys are generated as
tuples are initially copied over (where applicable), as well as what
to do when a non-reliable comparison returns 0 (where applicable).
That is surely the kernel of the general idea, and nothing more, so I
don't see that numeric support proves the suitability of the interface
(or at least the essential idea of the interface, as opposed to
exactly how the mechanism works in the proposed patch, where the
SortSupport struct is slightly extended to express this idea).

A large majority of new code is the new SortSupport routine for text.

--
Peter Geoghegan

On Fri, Apr 4, 2014 at 4:29 PM, Greg Stark <stark(at)mit(dot)edu> wrote:
> On Fri, Apr 4, 2014 at 12:15 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> >> Perhaps I shouldn't lay my own guilt trip on other committers --- but
>> >> I think it would be a bad precedent to not deal with the existing patch
>> >> queue first.
>> >
>> > +1
>>
>> +1
>
> I don't think we have to promise a strict priority queue and preempt all
> other development. But I agree loosely that processing patches that have
> been around should be a higher priority.
>
> I've been meaning to do more review for a while and just took a skim through
> the queue. There are only a couple I feel I can contribute with so I'm going
> to work on those and then if it's still before the feature freeze I would
> like to go ahead with Peter's patch. I think it's generally a good patch.

To be honest, I think that's just flat-out inappropriate. There were
over 100 patches in this CommitFest and there's not a single committed
patch that has your name on it even as a reviewer, let alone a
committer. When a committer says, hey, I'm going to commit XYZ, that
basically forces anybody who might have an objection to it to drop
what they're doing and object fast, before it's too late. In other
words, the people who just said that they are too busy reviewing
patches that were timely submitted and don't want to divert effort
from that to handle patches that weren't are going to have to do that
anyway, or lose their right to object. I think that's unfair. You're
essentially leveraging a commit bit that you haven't used in more than
three years to try to push a patch that was submitted months too late
to the head of the review queue - and, just to put icing on the cake,
it just so happens that you and the patch author work for the same
employer. I have no objection to people committing patches written by
others who work at the same company, but only if those patches have
gone through a full, fair, and public review, with ample opportunity
for other people to complain if they don't like it. That is obviously
not the case here.

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

* Robert Haas (robertmhaas(at)gmail(dot)com) wrote:
> On Fri, Apr 4, 2014 at 4:29 PM, Greg Stark <stark(at)mit(dot)edu> wrote:
> > I've been meaning to do more review for a while and just took a skim through
> > the queue. There are only a couple I feel I can contribute with so I'm going
> > to work on those and then if it's still before the feature freeze I would
> > like to go ahead with Peter's patch. I think it's generally a good patch.
>
> To be honest, I think that's just flat-out inappropriate. There were
> over 100 patches in this CommitFest and there's not a single committed
> patch that has your name on it even as a reviewer, let alone a
> committer.

I haven't got any either (except for my little one), which frustrates
me greatly. Not because I'm looking for credit on the time that I've
spent in discussions, doing reviews, and I could have sworn there was
some patch that I did commit, but because I've not been able to find
the larger chunks of time required to get the more complex patches in.

> When a committer says, hey, I'm going to commit XYZ, that
> basically forces anybody who might have an objection to it to drop
> what they're doing and object fast, before it's too late. In other
> words, the people who just said that they are too busy reviewing
> patches that were timely submitted and don't want to divert effort
> from that to handle patches that weren't are going to have to do that
> anyway, or lose their right to object.

I don't agree that this is the case. We do revert patches from time to
time, when necessary, and issues with this particular patch seem likely
to be found during testing, well in advance of any release, and it's
self contained enough to be reverted pretty easily. Perhaps it's not
fair to expect everyone to have realized that, but at least any
committer looking at it would, I believe, weigh those against it being a
late patch.

> I think that's unfair. You're
> essentially leveraging a commit bit that you haven't used in more than
> three years to try to push a patch that was submitted months too late
> to the head of the review queue - and, just to put icing on the cake,
> it just so happens that you and the patch author work for the same
> employer. I have no objection to people committing patches written by
> others who work at the same company, but only if those patches have
> gone through a full, fair, and public review, with ample opportunity
> for other people to complain if they don't like it. That is obviously
> not the case here.

As for this- it's disingenuous at best and outright accusatory at worst.
The reason for this discussion is entirely because of PGConf.NYC, imv,
where Peter brought this patch up with at least Greg, Magnus and I.
Also during PGConf.NYC, Greg was specifically asking me about patches
which were in the commitfest that could be reviewed, ideally without
having to go back through threads hundreds of messages long and dealing
with complex parts of the code. Sadly, as is often the case, the "easy"
ones get handled pretty quickly and the difficult ones get left behind.

One bad part of the commitfest, imv, is that when a "clearly good,
small" patch does manage to show up, we don't formally take any of that
into consideration when we are prioritizing patches. They end up being
informally prioritized and get in quickly at the beginning, but that
doesn't address the reality that those smaller patches likely would get
in without any kind of commitfest process and not letting them in
because of the commitfest process doesn't generally mean that the larger
patches are any more likely to get in- iow, it's not a zero-sum game.
We have quite a few "part-time" committers (or at least, committers who
have disproportionate amounts of time, or perhaps the difference is in
the size of the blocks of time which can be dedicated to PG) and saying
"no, you can't help unless you tackle the hard problems" doesn't
particularly move us forward.

All that said, I don't have any particularly good idea of how to "fix"
any of this- it's not fair to tell the committers who have more time (or
larger blocks of time, etc) "you must work the hard problems only"
either. I don't feel Greg's interest in this patch has anything to do
with his current employment and everything to do with the side-talks in
NYC, and to that point, I'm very tempted to go look at this patch myself
because it sounds like an exciting improvement with minimal effort.
Would I feel bad for doing so, with the CustomScan API and Updatable
Security Barrier Views patches still pending? Sure, but it's the
difference between finding an hour and finding 8. The hour will come
pretty easily (probably spent half that on this email..), while an
8-hour block, which would likely turn into more, is neigh-on impossible
til at least this weekend. And, no, 8x one-hour blocks would not be
worthwhile; I've tried that before.

Thanks,

Stephen

On Mon, Apr 7, 2014 at 1:01 PM, Stephen Frost <sfrost(at)snowman(dot)net> wrote:
> All that said, I don't have any particularly good idea of how to "fix"
> any of this- it's not fair to tell the committers who have more time (or
> larger blocks of time, etc) "you must work the hard problems only"
> either. I don't feel Greg's interest in this patch has anything to do
> with his current employment and everything to do with the side-talks in
> NYC, and to that point, I'm very tempted to go look at this patch myself
> because it sounds like an exciting improvement with minimal effort.
> Would I feel bad for doing so, with the CustomScan API and Updatable
> Security Barrier Views patches still pending? Sure, but it's the
> difference between finding an hour and finding 8. The hour will come
> pretty easily (probably spent half that on this email..), while an
> 8-hour block, which would likely turn into more, is neigh-on impossible
> til at least this weekend. And, no, 8x one-hour blocks would not be
> worthwhile; I've tried that before.

If it's only going to take you an hour to address this patch (or 8 to
address those other ones) then you spend a heck of a lot less time on
review for a patch of a given complexity level than I do. I agree
that it's desirable to slip things in, from time to time, when they're
uncontroversial and obviously meritorious, but I'm not completely
convinced that this is such a case. As an utterly trivial point, I
find the naming to be less than ideal: "poorman" is not a term I want
to enshrine in our code. That's not very descriptive of what the
patch is actually doing even if you know what the idiom means, and
people whose first language - many of whom do significant work on our
code - may not.

Now the point is not that that's a serious flaw in and of itself. The
point is that these kinds of issues deserve to be discussed and agreed
on, and the process should be structured in a way that permits that.
And that discussion will require the time not only of the people who
find this patch more interesting than any other, but also of the
people who just said that they're busy with other things right now,
unless those people want to forfeit their right to an opinion.
Experience has shown that it's a whole lot easier for anyone here to
get a patch changed before it's committed than after it's committed,
so I don't buy your argument that the timing there doesn't matter.

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

On Mon, Apr 7, 2014 at 10:23 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> As an utterly trivial point, I
> find the naming to be less than ideal: "poorman" is not a term I want
> to enshrine in our code. That's not very descriptive of what the
> patch is actually doing even if you know what the idiom means, and
> people whose first language - many of whom do significant work on our
> code - may not.

I didn't come up with the idea, or the name.

--
Peter Geoghegan

On 2014-04-07 10:29:53 -0700, Peter Geoghegan wrote:
> On Mon, Apr 7, 2014 at 10:23 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> > As an utterly trivial point, I
> > find the naming to be less than ideal: "poorman" is not a term I want
> > to enshrine in our code. That's not very descriptive of what the
> > patch is actually doing even if you know what the idiom means, and
> > people whose first language - many of whom do significant work on our
> > code - may not.
>
> I didn't come up with the idea, or the name.

Doesn't mean it needs to be enshrined everywhere. I don't think Robert's
against putting it in some comments.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Mon, Apr 7, 2014 at 10:42 AM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> I didn't come up with the idea, or the name.
>
> Doesn't mean it needs to be enshrined everywhere. I don't think Robert's
> against putting it in some comments.

That seems reasonable. If someone wants to call what I have here
semi-reliable normalized keys, for example, I have no objection
whatsoever. In fact, I think that's probably a good idea.

--
Peter Geoghegan

On Mon, Apr 7, 2014 at 1:23 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> As an utterly trivial point, I
> find the naming to be less than ideal: "poorman" is not a term I want
> to enshrine in our code. That's not very descriptive of what the
> patch is actually doing even if you know what the idiom means, and
> people whose first language - many of whom do significant work on our
> code - may not.

To throw out one more point that I think is problematic, Peter's
original email on this thread gives a bunch of examples of strxfrm()
normalization that all different in the first few bytes - but so do
the underlying strings. I *think* (but don't have time to check right
now) that on my MacOS X box, strxfrm() spits out 3 bytes of header
junk and then 8 bytes per character in the input string - so comparing
the first 8 bytes of the strxfrm()'d representation would amount to
comparing part of the first byte. If for any reason the first byte is
the same (or similar enough) on many of the input strings, then this
will probably work out to be slower rather than faster. Even if other
platforms are more space-efficient (and I think at least some of them
are), I think it's unlikely that this optimization will ever pay off
for strings that don't differ in the first 8 bytes. And there are
many cases where that could be true a large percentage of the time
throughout the input, e.g. YYYY-MM-DD HH:MM:SS timestamps stored as
text. It seems like that the patch pessimizes those cases, though of
course there's no way to know without testing.

Now it *may well be* that after doing some research and performance
testing we will conclude that either no commonly-used platforms show
any regressions or that the regressions that do occur are discountable
in view of the benefits to more common cases to the benefits. I just
don't think mid-April is the right time to start those discussions
with the goal of a 9.4 commit; and I also don't think committing
without having those discussions is very prudent.

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

On 2014-04-07 13:01:52 -0400, Stephen Frost wrote:
> I haven't got any either (except for my little one), which frustrates
> me greatly. Not because I'm looking for credit on the time that I've
> spent in discussions, doing reviews, and I could have sworn there was
> some patch that I did commit, but because I've not been able to find
> the larger chunks of time required to get the more complex patches in.

I am a bit confused. To my eyes there's been a huge number of actually
trivial patches in this commitfest? Even now, there's some:

* Bugfix for timeout in LDAP connection parameter resolution
* Problem with displaying "wide" tables in psql
* Enable CREATE FOREIGN TABLE (... LIKE ... )
* Add min, max, and stdev execute statement time in pg_stat_statement
* variant of regclass etc.
* vacuumdb: Add option --analyze-in-stages

Are all small patches that don't need major changes before getting committed.

That's after three months. And after a high number of smaller patches
committed by Tom on Friday.

> > When a committer says, hey, I'm going to commit XYZ, that
> > basically forces anybody who might have an objection to it to drop
> > what they're doing and object fast, before it's too late. In other
> > words, the people who just said that they are too busy reviewing
> > patches that were timely submitted and don't want to divert effort
> > from that to handle patches that weren't are going to have to do that
> > anyway, or lose their right to object.
>
> I don't agree that this is the case. We do revert patches from time to
> time, when necessary, and issues with this particular patch seem likely
> to be found during testing, well in advance of any release, and it's
> self contained enough to be reverted pretty easily.

Given the trackrecord with testing the project seems to have with
testing, I don't have much faith in that claim. But even if, it'll only
get you testing on 2-3 platforms, without noticing portability issues.

I think it'd be a different discussion if this where CF-1 or so. But
we're nearly *2* months after the the *end* of the last CF.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

* Robert Haas (robertmhaas(at)gmail(dot)com) wrote:
> If it's only going to take you an hour to address this patch (or 8 to
> address those other ones) then you spend a heck of a lot less time on
> review for a patch of a given complexity level than I do.

Eh, I don't really time it and I'm probably completely off in reality,
it's more of a relative "feeling" thing wrt how long it'd take. I was
also thinking about it from a 'initial review and provide feedback'
standpoint, actually getting to a point of committing something
certainly takes much longer, but I can also kick off tests and do
individual testing in those smaller time blocks. Reading the code and
understanding it, writing up the feedback email, etc, is what requires
the larger single block. Perhaps I can work on improving that for
myself and maybe find a way to do it in smaller chunks, but that hasn't
happened in the however-many-years, and there's the whole 'old dog, new
tricks' issue.

> I agree
> that it's desirable to slip things in, from time to time, when they're
> uncontroversial and obviously meritorious, but I'm not completely
> convinced that this is such a case. As an utterly trivial point, I
> find the naming to be less than ideal: "poorman" is not a term I want
> to enshrine in our code. That's not very descriptive of what the
> patch is actually doing even if you know what the idiom means, and
> people whose first language - many of whom do significant work on our
> code - may not.

Fair enough.

> Now the point is not that that's a serious flaw in and of itself. The
> point is that these kinds of issues deserve to be discussed and agreed
> on, and the process should be structured in a way that permits that.

The issue on it being called "poorman"? That doesn't exactly strike me
as needing a particularly long discussion, nor that it would be
difficult to change later. I agree that there may be other issues, and
it'd be great to get buy-in from everyone before anything goes in, but
there's really zero hope of that being a reality.

> And that discussion will require the time not only of the people who
> find this patch more interesting than any other, but also of the
> people who just said that they're busy with other things right now,
> unless those people want to forfeit their right to an opinion.

I certainly hope that no committer feels that they forfeit their right
to an opinion about a piece of code because they didn't object to it
before it was committed. My experience is that committed code gets
reviewed and concerns are raised, at which point it's usually on the
original committer to go back and fix it; which I'm certainly glad for.

> Experience has shown that it's a whole lot easier for anyone here to
> get a patch changed before it's committed than after it's committed,
> so I don't buy your argument that the timing there doesn't matter.

Once code has been released and there are external dependencies on it,
that's obviously an issue. Ahead of that, I feel like the issue is
really more one of interest- everyone is very interested when code is
about to go in, but once it's in, for whatever reason, the interest
becomes much less to review and comment on it. I feel like that's a
very long-standing issue as it relates to our 'beta' period because
doing code review just simply isn't fun and the motivation is reduced
once it's been committed.

That makes me wonder about having "beta" review-fests (in fact, I feel
like that may have been proposed before...), where commits are assigned
out to be reviewed by someone other than the committer/author/original
reviewer, as a way to motivate individuals to go review what has gone
in before we get to release. That might help us ensure that more of the
committed code *gets* another review before release and reduce the
issues we have post-release. Just a thought.

Thanks,

Stephen

* Andres Freund (andres(at)2ndquadrant(dot)com) wrote:
> On 2014-04-07 13:01:52 -0400, Stephen Frost wrote:
> > I haven't got any either (except for my little one), which frustrates
> > me greatly. Not because I'm looking for credit on the time that I've
> > spent in discussions, doing reviews, and I could have sworn there was
> > some patch that I did commit, but because I've not been able to find
> > the larger chunks of time required to get the more complex patches in.
>
> I am a bit confused. To my eyes there's been a huge number of actually
> trivial patches in this commitfest? Even now, there's some:
>
> * Bugfix for timeout in LDAP connection parameter resolution

I can take a look at that (if no one else wants to speak up about it).

> * Problem with displaying "wide" tables in psql

That's not without controvery, as I understand it, but I admit that I
haven't been following it terribly closely.

> * Enable CREATE FOREIGN TABLE (... LIKE ... )

This has definitely got issues which are not trival, see Tom's recent
email on the subject..

> * Add min, max, and stdev execute statement time in pg_stat_statement

This was also quite controversal. If we've finally settled on this as
being acceptable then perhaps it can get in pretty easily.

> * variant of regclass etc.

This was recently being discussed also.

> * vacuumdb: Add option --analyze-in-stages

Haven't looked at this at all.

> Are all small patches that don't need major changes before getting committed.

That strikes me as optimistic. I do plan to go do another pass through
the commitfest patches before looking at other things (as Greg also said
he would do); thanks for bringing up the ones you feel are more
managable- it'll help me focus on them.

> Given the trackrecord with testing the project seems to have with
> testing, I don't have much faith in that claim. But even if, it'll only
> get you testing on 2-3 platforms, without noticing portability issues.

This would be another case where it'd be nice if we could give people
access to the buildfarm w/o having to actually commit something.

> I think it'd be a different discussion if this where CF-1 or so. But
> we're nearly *2* months after the the *end* of the last CF.

There wouldn't be any discussion if it was CF-1 as I doubt anyone would
object to it going in (or at least not as strongly..), even if it was
submitted after CF-1 was supposed to be over with remaining patches.
It's the threat of getting punted to the next release that really makes
the difference here, imv.

Thanks,

Stephen

On Mon, Apr 7, 2014 at 1:58 PM, Stephen Frost <sfrost(at)snowman(dot)net> wrote:
> * Robert Haas (robertmhaas(at)gmail(dot)com) wrote:
>> If it's only going to take you an hour to address this patch (or 8 to
>> address those other ones) then you spend a heck of a lot less time on
>> review for a patch of a given complexity level than I do.
>
> Eh, I don't really time it and I'm probably completely off in reality,
> it's more of a relative "feeling" thing wrt how long it'd take. I was
> also thinking about it from a 'initial review and provide feedback'
> standpoint, actually getting to a point of committing something
> certainly takes much longer, but I can also kick off tests and do
> individual testing in those smaller time blocks. Reading the code and
> understanding it, writing up the feedback email, etc, is what requires
> the larger single block. Perhaps I can work on improving that for
> myself and maybe find a way to do it in smaller chunks, but that hasn't
> happened in the however-many-years, and there's the whole 'old dog, new
> tricks' issue.

It takes me a big block of time, too, at least for the initial review.

> The issue on it being called "poorman"? That doesn't exactly strike me
> as needing a particularly long discussion, nor that it would be
> difficult to change later. I agree that there may be other issues, and
> it'd be great to get buy-in from everyone before anything goes in, but
> there's really zero hope of that being a reality.

Really? I think there have been just about zero patches that have
gone in in the last (ugh) three months that have had significant
unaddressed objections from anyone at the time they were committed.
There has certainly been an enormous amount of work by a whole lot of
people to address objections that have been raised, and generally that
has gone well. I will not pretend that every patch that has gone in
is completely well-liked by everyone and I am sure that is not the
case. Nevertheless I think we've done pretty well. Now the people
whose stuff has not got in - and may not get in - may well feel that
their stuff got short shrift, and I'm not going to deny that there's a
problem there. But breaking from our usual procedure for this patch
is just adding to that unfairness, not making anything better.

>> And that discussion will require the time not only of the people who
>> find this patch more interesting than any other, but also of the
>> people who just said that they're busy with other things right now,
>> unless those people want to forfeit their right to an opinion.
>
> I certainly hope that no committer feels that they forfeit their right
> to an opinion about a piece of code because they didn't object to it
> before it was committed. My experience is that committed code gets
> reviewed and concerns are raised, at which point it's usually on the
> original committer to go back and fix it; which I'm certainly glad for.

Sure, people can object to anything whenever they like. But it
becomes an uphill battle once it goes in, unless the breakage is
rather flagrant.

Regardless, if this patch had had multiple, detailed reviews finding
lots of issues that were then addressed, I'd probably be keeping my
trap shut and hoping for the best. But it hasn't. Any patch of this
size is going to have nitpicky stuff that needs to be addressed, if
nothing else, and points requiring some modicum of public discussion,
and there hasn't been any of that. That suggests to me that it just
hasn't been thoroughly reviewed yet, at least not in public, and that
should happen long before anyone talks about picking it up for commit.
If this patch had been timely submitted and I'd picked it up right
away, I would have expected at least three weeks to elapse between the
time my first review was posted and the time all the details were
nailed down, even assuming no more serious problems were found, and
starting that ball rolling now means looking forward to a commit
around the end of April assuming things go great. That seems way too
late to me; IMHO, we should already be mostly in mop-up mode now
(hence my recent DSM patch cleanup patch, which no one has commented
on...).

And I think it's likely that, in fact, we'll find cases where this
regresses performance rather badly, for reasons sketched in an email I
posted a bit ago.

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

* Robert Haas (robertmhaas(at)gmail(dot)com) wrote:
> To throw out one more point that I think is problematic, Peter's
> original email on this thread gives a bunch of examples of strxfrm()
> normalization that all different in the first few bytes - but so do
> the underlying strings. I *think* (but don't have time to check right
> now) that on my MacOS X box, strxfrm() spits out 3 bytes of header
> junk and then 8 bytes per character in the input string - so comparing
> the first 8 bytes of the strxfrm()'d representation would amount to
> comparing part of the first byte. If for any reason the first byte is
> the same (or similar enough) on many of the input strings, then this
> will probably work out to be slower rather than faster. Even if other
> platforms are more space-efficient (and I think at least some of them
> are), I think it's unlikely that this optimization will ever pay off
> for strings that don't differ in the first 8 bytes. And there are
> many cases where that could be true a large percentage of the time
> throughout the input, e.g. YYYY-MM-DD HH:MM:SS timestamps stored as
> text. It seems like that the patch pessimizes those cases, though of
> course there's no way to know without testing.

Portability and performance concerns were exactly what worried me as
well. It was my hope/understanding that this was a clear win which was
vetted by other large projects across multiple platforms. If that's
actually in doubt and it isn't a clear win then I agree that we can't be
trying to squeeze it in at this late date.

> Now it *may well be* that after doing some research and performance
> testing we will conclude that either no commonly-used platforms show
> any regressions or that the regressions that do occur are discountable
> in view of the benefits to more common cases to the benefits. I just
> don't think mid-April is the right time to start those discussions
> with the goal of a 9.4 commit; and I also don't think committing
> without having those discussions is very prudent.

I agree with this in concept- but I'd be willing to spend a bit of time
researching it, given that it's from a well known and respected author
who I trust has done much of this research already.

Thanks,

Stephen

On 2014-04-07 14:12:09 -0400, Stephen Frost wrote:
> I can take a look at that (if no one else wants to speak up about it).
>
> > * Problem with displaying "wide" tables in psql
>
> That's not without controvery, as I understand it, but I admit that I
> haven't been following it terribly closely.

There didn't seem to be any conflicts here? I am talking about
http://archives.postgresql.org/message-id/CAJTaR32A1_d0DqP25T4%3DLwE3RpmhNf3oY%3Dr0-ksejepfPv6O%3Dw%40mail.gmail.com

> > * Enable CREATE FOREIGN TABLE (... LIKE ... )
>
> This has definitely got issues which are not trival, see Tom's recent
> email on the subject..

Yea. Besides others, he confirmed my comments. The issue there was
basically that I didn't like something, others disagreed. Still needed a
committers input.

> > * Add min, max, and stdev execute statement time in pg_stat_statement
>
> This was also quite controversal. If we've finally settled on this as
> being acceptable then perhaps it can get in pretty easily.

The minimal variant (just stddev) didn't seem to be all that
controversial.

> > I think it'd be a different discussion if this where CF-1 or so. But
> > we're nearly *2* months after the the *end* of the last CF.
>
> There wouldn't be any discussion if it was CF-1 as I doubt anyone would
> object to it going in (or at least not as strongly..), even if it was
> submitted after CF-1 was supposed to be over with remaining patches.
> It's the threat of getting punted to the next release that really makes
> the difference here, imv.

I can understand that for feature patches which your company/client
needs, but for a localized performance improvement? Unconvinced.

And sorry, if the "threat of getting punted to the next release" plays
a significant role in here, the patch *needs* to be punted. The only
reason I can see at this point is "ah, trivial enough, let's just do
this now".

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Mon, Apr 7, 2014 at 10:47 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> To throw out one more point that I think is problematic, Peter's
> original email on this thread gives a bunch of examples of strxfrm()
> normalization that all different in the first few bytes - but so do
> the underlying strings. I *think* (but don't have time to check right
> now) that on my MacOS X box, strxfrm() spits out 3 bytes of header
> junk and then 8 bytes per character in the input string - so comparing
> the first 8 bytes of the strxfrm()'d representation would amount to
> comparing part of the first byte. If for any reason the first byte is
> the same (or similar enough) on many of the input strings, then this
> will probably work out to be slower rather than faster. Even if other
> platforms are more space-efficient (and I think at least some of them
> are), I think it's unlikely that this optimization will ever pay off
> for strings that don't differ in the first 8 bytes.

Why would any platform have header bytes in the resulting binary
strings? That doesn't make any sense. Are you sure you aren't thinking
of the homogeneous trailing bytes that you can also see in my example?

The only case that this patch could possibly regress is where there
are strings that differ beyond about the first 8 bytes, but are not
identical (we chance a memcmp() == 0 before doing a full strcoll()
when tie-breaking on the semi-reliable initial comparison). We still
always avoid fmgr-overhead (and shim overhead, which I've measured),
as in your original patch - you put that at adding 7% at the time,
which is likely to make up for otherwise-regressed cases. There is
nothing at all contrived about my test-case.

You have to have an awfully large number of significantly similar but
not identical strings in order to possibly lose out. Even if you have
such a case, and the fmgr-trampoline-elision doesn't make up for it
(doesn't make up for having to do a separate heapattr lookup on the
minimal tuple, and optimization not too relevant for pass by reference
types), which is quite a stretch, it seems likely that you have other
cases that do benefit, which in aggregate makes up for it. The
benefits I've shown, on the first test case I picked are absolutely
enormous.

Now, let's assume that I'm wrong about all this, and that in fact
there is a plausible case where all of those tricks don't work out,
and someone has a complaint about a regression. What are we going to
do about that? Not accelerate text sorting by at least a factor of 3
for the benefit of some very narrow use-case? That's the only measure
I can see that you could take to not regress that case.

--
Peter Geoghegan

On Mon, Apr 7, 2014 at 2:12 PM, Stephen Frost <sfrost(at)snowman(dot)net> wrote:
>> I think it'd be a different discussion if this where CF-1 or so. But
>> we're nearly *2* months after the the *end* of the last CF.
>
> There wouldn't be any discussion if it was CF-1 as I doubt anyone would
> object to it going in (or at least not as strongly..), even if it was
> submitted after CF-1 was supposed to be over with remaining patches.
> It's the threat of getting punted to the next release that really makes
> the difference here, imv.

The point is that if this had been submitted for CF-1, CF-2, CF-3, or
CF-4, and I had concerns about it (which I do), then I would have
budgeted time to record those concerns so that they could be discussed
and, if necessary, addressed. Since it wasn't, I assumed I didn't
need to worry about studying the patch, figuring out which of my
concerns were actually legitimate, searching for other areas of
potential concern, and putting together a nice write-up until June -
and maybe not even then, because at that point other people might also
be studying the patch and might cover those areas in sufficient detail
as to obviate my own concerns.

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

Stephen Frost wrote:
> * Andres Freund (andres(at)2ndquadrant(dot)com) wrote:

> > I think it'd be a different discussion if this where CF-1 or so. But
> > we're nearly *2* months after the the *end* of the last CF.
>
> There wouldn't be any discussion if it was CF-1 as I doubt anyone would
> object to it going in (or at least not as strongly..), even if it was
> submitted after CF-1 was supposed to be over with remaining patches.
> It's the threat of getting punted to the next release that really makes
> the difference here, imv.

That's why we have this rule that CF4 should only receive patches that
were already reviewed in previous commitfests. I, too, find the
fast-tracking of this patch completely outside of the CF process to be
distasteful. We summarily reject much smaller patches at the end of
each cycle process, even when the gain is as obvious as is claimed to
be for this patch.

TBH I don't see why we're even discussing this.

--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

* Robert Haas (robertmhaas(at)gmail(dot)com) wrote:
> On Mon, Apr 7, 2014 at 1:58 PM, Stephen Frost <sfrost(at)snowman(dot)net> wrote:
> > The issue on it being called "poorman"? That doesn't exactly strike me
> > as needing a particularly long discussion, nor that it would be
> > difficult to change later. I agree that there may be other issues, and
> > it'd be great to get buy-in from everyone before anything goes in, but
> > there's really zero hope of that being a reality.
>
> Really? I think there have been just about zero patches that have
> gone in in the last (ugh) three months that have had significant
> unaddressed objections from anyone at the time they were committed.

That implies that everyone has been reviewing everything, which is
certainly not entirely the case.. If that's happening then I'm not sure
I understand the point of the commitfest, and feel I must be falling
down on the job here. Certainly there are patches which have been
picked up by committers and committed that I've not reviewed. I also
didn't object, but if I find issue with them in the future, I'd
certainly bring them up, even post-commit.

> There has certainly been an enormous amount of work by a whole lot of
> people to address objections that have been raised, and generally that
> has gone well. I will not pretend that every patch that has gone in
> is completely well-liked by everyone and I am sure that is not the
> case. Nevertheless I think we've done pretty well. Now the people
> whose stuff has not got in - and may not get in - may well feel that
> their stuff got short shrift, and I'm not going to deny that there's a
> problem there. But breaking from our usual procedure for this patch
> is just adding to that unfairness, not making anything better.

This goes back to the point which I was trying to make earlier-
prioritization. Small+clearly-good patches should be prioritized
higher, but identifying those is no small matter. Of course, we would
need to address the starvation risk when it comes to larger patches,
which I've got no answer for.

> Regardless, if this patch had had multiple, detailed reviews finding
> lots of issues that were then addressed, I'd probably be keeping my
> trap shut and hoping for the best. But it hasn't. Any patch of this
> size is going to have nitpicky stuff that needs to be addressed, if
> nothing else, and points requiring some modicum of public discussion,
> and there hasn't been any of that. That suggests to me that it just
> hasn't been thoroughly reviewed yet, at least not in public, and that
> should happen long before anyone talks about picking it up for commit.

Perhaps my memory is foggy, but I recall at least some amount of
discussion and review of this, along with fixes going in, over the past
couple of weeks. More may be needed, of course, but if so, I'd expect
any committer looking at it would realize that and bounce it at this
point, given the feature freeze deadline which is like next week..

> If this patch had been timely submitted and I'd picked it up right
> away, I would have expected at least three weeks to elapse between the
> time my first review was posted and the time all the details were
> nailed down, even assuming no more serious problems were found, and
> starting that ball rolling now means looking forward to a commit
> around the end of April assuming things go great. That seems way too
> late to me; IMHO, we should already be mostly in mop-up mode now
> (hence my recent DSM patch cleanup patch, which no one has commented
> on...).

I agree with this.

> And I think it's likely that, in fact, we'll find cases where this
> regresses performance rather badly, for reasons sketched in an email I
> posted a bit ago.

I've not researched it enough myself to say.

Thanks,

Stephen

* Alvaro Herrera (alvherre(at)2ndquadrant(dot)com) wrote:
> That's why we have this rule that CF4 should only receive patches that
> were already reviewed in previous commitfests.

I, at least, always understood that rule to be 'large' patches, which
this didn't strike me as.

> I, too, find the
> fast-tracking of this patch completely outside of the CF process to be
> distasteful. We summarily reject much smaller patches at the end of
> each cycle process, even when the gain is as obvious as is claimed to
> be for this patch.

In the past, we've also committed large patches which were submitted for
the first time to CF-4.

> TBH I don't see why we're even discussing this.

Think I'm about done, personally. I can't comment more without actually
looking at it and doing some research on it myself and I don't know that
I'll be able to do that any time soon, as I told Peter when he asked me
about it in NYC. That said, for my part, I don't like telling Greg that
he either has to review something else which was submitted but that he's
got no interest in (or which would take much longer), or not do
anything.

Thanks,

Stephen

On 2014-04-07 14:35:23 -0400, Stephen Frost wrote:
> That said, for my part, I don't like telling Greg that
> he either has to review something else which was submitted but that he's
> got no interest in (or which would take much longer), or not do
> anything.

Reviewing and committing are two very different shoes imo. This
discussion wasn't about it getting reviewed before the next CF, but
about committing it into 9.4.

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Mon, Apr 7, 2014 at 2:19 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Mon, Apr 7, 2014 at 10:47 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> To throw out one more point that I think is problematic, Peter's
>> original email on this thread gives a bunch of examples of strxfrm()
>> normalization that all different in the first few bytes - but so do
>> the underlying strings. I *think* (but don't have time to check right
>> now) that on my MacOS X box, strxfrm() spits out 3 bytes of header
>> junk and then 8 bytes per character in the input string - so comparing
>> the first 8 bytes of the strxfrm()'d representation would amount to
>> comparing part of the first byte. If for any reason the first byte is
>> the same (or similar enough) on many of the input strings, then this
>> will probably work out to be slower rather than faster. Even if other
>> platforms are more space-efficient (and I think at least some of them
>> are), I think it's unlikely that this optimization will ever pay off
>> for strings that don't differ in the first 8 bytes.
>
> Why would any platform have header bytes in the resulting binary
> strings? That doesn't make any sense. Are you sure you aren't thinking
> of the homogeneous trailing bytes that you can also see in my example?

No, I'm not sure of that at all. I haven't looked at this topic in a
while, but I'm happy to budget some to time to do so - for the June
CommitFest.

> The only case that this patch could possibly regress is where there
> are strings that differ beyond about the first 8 bytes, but are not
> identical (we chance a memcmp() == 0 before doing a full strcoll()
> when tie-breaking on the semi-reliable initial comparison). We still
> always avoid fmgr-overhead (and shim overhead, which I've measured),
> as in your original patch - you put that at adding 7% at the time,
> which is likely to make up for otherwise-regressed cases. There is
> nothing at all contrived about my test-case.

It's not a question of whether your test case is contrived. Your test
case can be (and likely is) extremely realistic and still not account
for other cases when the patch regresses performance. If I understand
correctly, and I may not because I wasn't planning to spend time on
this patch until the next CommitFest, the patch basically uses the
bytes available in datum1 to cache what you refer to as a normalized
or poor man's sort key which, it is hoped, will break most ties.
However, on any workload where it fails to break ties, you're going to
incur the additional overheads of (1) comparing the poor-man's sort
key, (2) memcmping the strings (based on what you just said), and then
(3) digging the correct datum back out of the tuple. I note that
somebody thought #3 was important enough to be worth creating datum1
for in the first place, so I don't think it can or should be assumed
that undoing that optimization in certain cases will turn out to be
cheap enough not to matter.

In short, I don't see any evidence that you've made an attempt to
construct a worst-case scenario for this patch, and that's a basic
part of performance testing. I had to endure having Andres beat the
snot out of me over cases where the MVCC snapshot patch regressed
performance, and as painful as that was, it led to a better patch. If
I'd committed the first thing that did well on my own tests, which
*did* include attempts (much less successful than Andres's) to find
regressions, we'd be significantly worse off today than we are.

> You have to have an awfully large number of significantly similar but
> not identical strings in order to possibly lose out. Even if you have
> such a case, and the fmgr-trampoline-elision doesn't make up for it
> (doesn't make up for having to do a separate heapattr lookup on the
> minimal tuple, and optimization not too relevant for pass by reference
> types), which is quite a stretch, it seems likely that you have other
> cases that do benefit, which in aggregate makes up for it. The
> benefits I've shown, on the first test case I picked are absolutely
> enormous.

Testing the cases where your patch wins and hand-waving that the
losses won't be that bad in other cases - without actually testing -
is not the right methodology.

And I think it would be quite a large error to assume that tables
never contain large numbers of similar but not identical strings. I
bet there are many people who have just that. That's also quite an
inaccurate depiction of the cases where this will regress things; a
bunch of strings that share the first few characters might not be
similar in any normal human sense of that term, while still slipping
through the proposed sieve. In your OP, a six-byte string blew up
until 20 bytes after being strxfrm()'d, which means that you're only
comparing the first 2-3 bytes. On a platform where Datums are only 4
bytes, you're only comparing the first 1-2 bytes. Arguing that nobody
anywhere has a table where not even the first character or two are
identical across most or all of the strings in the column is
ridiculous.

> Now, let's assume that I'm wrong about all this, and that in fact
> there is a plausible case where all of those tricks don't work out,
> and someone has a complaint about a regression. What are we going to
> do about that? Not accelerate text sorting by at least a factor of 3
> for the benefit of some very narrow use-case? That's the only measure
> I can see that you could take to not regress that case.

The appropriate time to have a discussion about whether the patch wins
by a large enough margin in enough use cases to justify possible
regressions in cases where it loses is after we have made a real
effort to characterize the winning and losing cases, mitigate the
losing cases as far as possible, and benchmarked the results. I think
it's far from a given even that your patch will win in more cases than
it loses, or that the regressions when it loses will be small. That,
of course, has yet to be proven, but so does the contrary.

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

On Mon, Apr 7, 2014 at 2:35 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> On 2014-04-07 14:35:23 -0400, Stephen Frost wrote:
>> That said, for my part, I don't like telling Greg that
>> he either has to review something else which was submitted but that he's
>> got no interest in (or which would take much longer), or not do
>> anything.
>
> Reviewing and committing are two very different shoes imo. This
> discussion wasn't about it getting reviewed before the next CF, but
> about committing it into 9.4.

Yes. I did not object to this patch being posted in the midst of
trying to nail down this release, and I certainly do not object to
Greg, or Stephen, or anyone else reviewing it. My note was
specifically prompted not by someone say they intended to *review* the
patch, but that they intended to *commit* it when it hasn't even
really been reviewed yet. There are patches that are trivial enough
that it's fine for someone to commit them without a public review
first, but this isn't remotely close to being in that category. If
nothing else, the fact that it extends the definition of the btree
opclass is sufficient reason to merit a public review.

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

* Andres Freund (andres(at)2ndquadrant(dot)com) wrote:
> On 2014-04-07 14:35:23 -0400, Stephen Frost wrote:
> > That said, for my part, I don't like telling Greg that
> > he either has to review something else which was submitted but that he's
> > got no interest in (or which would take much longer), or not do
> > anything.
>
> Reviewing and committing are two very different shoes imo. This
> discussion wasn't about it getting reviewed before the next CF, but
> about committing it into 9.4.

I'm not entirely sure why. No one is giving grief to the people
bringing up new things which are clearly for 9.5 at this point, yet we
have a ton of patches that still need to be reviewed. I don't think
that we don't want to tell individuals who are volunteering how to
spend their time, but what we're saying is that they can do anything
except actually commit stuff, because we must have ordering to what
gets committed; an ordering which hasn't really got any prioritization
to it based on the patch itself but entirely depends on when it was
submitted.

Thanks,

Stephen

On Mon, Apr 7, 2014 at 11:37 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> You're
> essentially leveraging a commit bit that you haven't used in more than
> three years to try to push a patch that was submitted months too late

I'm not leveraging anything any I'm not going to push something unless
people are on board. That's *why* I sent that message. And I started
the email by saying I was going to go work on patches from the
commitfest first.

--
greg

On Mon, Apr 7, 2014 at 11:59 AM, Stephen Frost <sfrost(at)snowman(dot)net> wrote:
> * Robert Haas (robertmhaas(at)gmail(dot)com) wrote:
>> There are patches that are trivial enough
>> that it's fine for someone to commit them without a public review
>> first, but this isn't remotely close to being in that category. If
>> nothing else, the fact that it extends the definition of the btree
>> opclass is sufficient reason to merit a public review.
>
> hrmpf. You have a good point about that- I admit that I didn't consider
> that as much as I should have.

Actually, contrary to the original subject of this thread, that isn't
the case. I have not added a support function 3, which I ultimately
concluded was a bad idea. This is all sort support.

--
Peter Geoghegan

* Robert Haas (robertmhaas(at)gmail(dot)com) wrote:
> There are patches that are trivial enough
> that it's fine for someone to commit them without a public review
> first, but this isn't remotely close to being in that category. If
> nothing else, the fact that it extends the definition of the btree
> opclass is sufficient reason to merit a public review.

hrmpf. You have a good point about that- I admit that I didn't consider
that as much as I should have.

Thanks,

Stephen

On Mon, Apr 7, 2014 at 11:56 AM, Greg Stark <stark(at)mit(dot)edu> wrote:
> On Mon, Apr 7, 2014 at 11:37 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> You're
>> essentially leveraging a commit bit that you haven't used in more than
>> three years to try to push a patch that was submitted months too late
>
>
> I'm not leveraging anything any I'm not going to push something unless
> people are on board. That's *why* I sent that message. And I started
> the email by saying I was going to go work on patches from the
> commitfest first.

Exactly.

I was of the opinion, as some familiar with the subject matter, that
this rose to the level of deserving special consideration. I'm glad
that there does seem to be a general recognition that such a category
exists. Given the reservations of Robert and others, this isn't going
to happen for 9.4. It was never going to happen under a cloud of
controversy. I only broached the idea.

Special consideration is not something I ask for lightly. I must admit
that it's hard to see things as I do if you aren't as familiar with
the problem. I happen to think that this is the wrong decision, but
I'll leave it at that.

I'm sure that whatever we come up with for 9.5 will be a lot better
than what I have here, because it will probably be generalized to
other important cases.

--
Peter Geoghegan

On Mon, Apr 7, 2014 at 2:56 PM, Greg Stark <stark(at)mit(dot)edu> wrote:
> On Mon, Apr 7, 2014 at 11:37 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> You're
>> essentially leveraging a commit bit that you haven't used in more than
>> three years to try to push a patch that was submitted months too late
>
> I'm not leveraging anything any I'm not going to push something unless
> people are on board. That's *why* I sent that message. And I started
> the email by saying I was going to go work on patches from the
> commitfest first.

I said that a lot more harshly than I should have, and I impugned you
unfairly. Sorry.

I'm going to try again:

I don't doubt that your desire to move this patch forward is motivated
by anything under than the best of possible motivations. However,
whether you intend it or not, trying to move this patch toward a 9.4
commit, or even trying to get people to express an opinion on whether
this is suitable for a 9.4 commit, is inevitably going to cause senior
reviewers who think they might have concerns about it to need to spend
time on it. Inevitably, that time will come at the expense of patches
that were timely submitted, and that is unfair to the people who
submitted those patches.

Of course, if you want to review this patch now, I'm 100% OK with
that. If you want to review other pending patches, for 9.4 or 9.5, I
think that's great, too. But if there's talk of committing this
patch, I think that seems both quite a bit too late (relative to the
timing of CF4) and quite a bit too early (relative to the amount of
review and testing done thus far).

Thanks,

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

* Peter Geoghegan (pg(at)heroku(dot)com) wrote:
> Actually, contrary to the original subject of this thread, that isn't
> the case. I have not added a support function 3, which I ultimately
> concluded was a bad idea. This is all sort support.

Well, as apparently no one is objecting to Greg reviewing it, I'd
suggest he do that and actually articulate his feelings on the patch
post-review and exactly what it is changing and if he feels it needs
public comment, rather than all this speculation by folks who aren't
looking at the patch.

In other words, in hindsight, Greg was rather premature with his
suggestion that he might commit it and rather than suggesting such, he
should have just said he was going to review it and then come back with
a detailed email argueing the case for it to go in.

I don't particularly fault Greg for that, but perhaps some of this could
be avoided in the future.

Thanks,

Stephen

Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> I am a bit confused. To my eyes there's been a huge number of actually
> trivial patches in this commitfest? Even now, there's some:

> * Bugfix for timeout in LDAP connection parameter resolution
> * Problem with displaying "wide" tables in psql
> * Enable CREATE FOREIGN TABLE (... LIKE ... )
> * Add min, max, and stdev execute statement time in pg_stat_statement
> * variant of regclass etc.
> * vacuumdb: Add option --analyze-in-stages

> Are all small patches that don't need major changes before getting committed.

FWIW, I think the reason most of those aren't in is that there's not
consensus that it's a feature we want. Triviality of the patch itself
doesn't make it easier to get past that. (Indeed, when a feature patch
is actually trivial, that usually suggests to me that it's not been
thought through fully ...)

The LDAP one requires both LDAP and Windows expertise, which means the
pool of qualified committers for it is pretty durn small. I think
Magnus promised to deal with it, though.

> I think it'd be a different discussion if this where CF-1 or so. But
> we're nearly *2* months after the the *end* of the last CF.

Yeah. At this point the default decision has to be to reject (or
more accurately, punt to 9.5). I think we can still get a few of
these in and meet the mid-April target date, but many of them will
not make it.

regards, tom lane

On Mon, Apr 7, 2014 at 11:47 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> It's not a question of whether your test case is contrived. Your test
> case can be (and likely is) extremely realistic and still not account
> for other cases when the patch regresses performance. If I understand
> correctly, and I may not because I wasn't planning to spend time on
> this patch until the next CommitFest, the patch basically uses the
> bytes available in datum1 to cache what you refer to as a normalized
> or poor man's sort key which, it is hoped, will break most ties.
> However, on any workload where it fails to break ties, you're going to
> incur the additional overheads of (1) comparing the poor-man's sort
> key, (2) memcmping the strings (based on what you just said), and then
> (3) digging the correct datum back out of the tuple. I note that
> somebody thought #3 was important enough to be worth creating datum1
> for in the first place, so I don't think it can or should be assumed
> that undoing that optimization in certain cases will turn out to be
> cheap enough not to matter.

The much earlier datum1 optimization is mostly compelling for
pass-by-value types, for reasons that prominently involve
cache/locality considerations. That's probably why this patch is so
compelling - it makes those advantages apply to pass-by-reference
types too.

> Testing the cases where your patch wins and hand-waving that the
> losses won't be that bad in other cases - without actually testing -
> is not the right methodology.

Okay. Here is a worst-case, with the pgbench script the same as my
original test-case, but with much almost maximally unsympathetic data
to sort:

[local]/postgres=# update customers set firstname =
'padding-padding-padding-padding' || firstname;
UPDATE 20000

Master:

pg(at)hamster:~/sort-tests$ pgbench -f sort.sql -n -T 100
transaction type: Custom query
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
duration: 100 s
number of transactions actually processed: 323
latency average: 309.598 ms
tps = 3.227745 (including connections establishing)
tps = 3.227784 (excluding connections establishing)

Patch:

pg(at)hamster:~/sort-tests$ pgbench -f sort.sql -n -T 100
transaction type: Custom query
scaling factor: 1
query mode: simple
number of clients: 1
number of threads: 1
duration: 100 s
number of transactions actually processed: 307
latency average: 325.733 ms
tps = 3.066256 (including connections establishing)
tps = 3.066313 (excluding connections establishing)

That seems like a pretty modest regression for a case where 100% of
what I've done goes to waste. If something that I'd done worked out
10% of the time, we'd still be well ahead.

--
Peter Geoghegan

On Mon, Apr 7, 2014 at 4:35 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> The much earlier datum1 optimization is mostly compelling for
> pass-by-value types, for reasons that prominently involve
> cache/locality considerations.

I agree.

> That's probably why this patch is so
> compelling - it makes those advantages apply to pass-by-reference
> types too.

Well, whether the patch is compelling is actually precisely what we
need to figure out. I feel like you're asserting your hoped-for
conclusion prematurely.

>> Testing the cases where your patch wins and hand-waving that the
>> losses won't be that bad in other cases - without actually testing -
>> is not the right methodology.
>
> Okay. Here is a worst-case, with the pgbench script the same as my
> original test-case, but with much almost maximally unsympathetic data
> to sort:
>
> [local]/postgres=# update customers set firstname =
> 'padding-padding-padding-padding' || firstname;
> UPDATE 20000
>
> Master:
>
> pg(at)hamster:~/sort-tests$ pgbench -f sort.sql -n -T 100
> transaction type: Custom query
> scaling factor: 1
> query mode: simple
> number of clients: 1
> number of threads: 1
> duration: 100 s
> number of transactions actually processed: 323
> latency average: 309.598 ms
> tps = 3.227745 (including connections establishing)
> tps = 3.227784 (excluding connections establishing)
>
> Patch:
>
> pg(at)hamster:~/sort-tests$ pgbench -f sort.sql -n -T 100
> transaction type: Custom query
> scaling factor: 1
> query mode: simple
> number of clients: 1
> number of threads: 1
> duration: 100 s
> number of transactions actually processed: 307
> latency average: 325.733 ms
> tps = 3.066256 (including connections establishing)
> tps = 3.066313 (excluding connections establishing)
>
> That seems like a pretty modest regression for a case where 100% of
> what I've done goes to waste. If something that I'd done worked out
> 10% of the time, we'd still be well ahead.

Now that is definitely interesting, and it does seem to demonstrate
that the worst case for this patch might not be as bad as I had feared
- it's about a 5% regression: not great, but perhaps tolerable. It's
not actually a worse case unless firstname is a fair ways into a tuple
with lots of variable-length columns before it, because part of what
the datum1 thing saves you is the cost of repeatedly walking through
the tuple's column list.

But I still think that a lot more could be done - and I'd challenge
you (or others) to do it - to look for cases where this might be a
pessimization. I get that the patch has an upside, but nearly every
patch that anybody proposes does, and the author usually points out
those cases quite prominently, as you have, and right so. But what
makes for a much more compelling submission is when the author *also*
tries really hard to break the patch, and hopefully fails. I agree
that the test result shown above is good news for this patch's future
prospects, but I *don't* agree that it nails the door shut. What
about other locales? Other operating systems? Other versions of
libc? Longer strings? Wider tuples? Systems where datums are only
32-bits? Sure, you can leave those things to the reviewer and/or
committer to worry about, but that's not the way to expedite the
patch's trip into the tree.

I have to admit, I didn't really view the original postings on this
topic to be anything more than, hey, we've got something promising
here, it's worth more study. That's part of why I was so taken aback
by Greg's email. There's certainly good potential here, but I think
there's quite a bit left of work left to do before you can declare
victory...

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

On Mon, Apr 7, 2014 at 3:49 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> Now that is definitely interesting, and it does seem to demonstrate
> that the worst case for this patch might not be as bad as I had feared
> - it's about a 5% regression: not great, but perhaps tolerable. It's
> not actually a worse case unless firstname is a fair ways into a tuple
> with lots of variable-length columns before it, because part of what
> the datum1 thing saves you is the cost of repeatedly walking through
> the tuple's column list.

I only use strxfrm() when the leading key is text. Otherwise, it's
pretty much just what your original sort support for text patch from
2012 does, and we don't bother with anything other than fmgr-elision.
The only thing that stops the above test case being perfectly pessimal
is that we don't always chance a memcmp(), due to some comparisons
realizing that len1 != len2. Also, exactly one comparison actually
benefits from that same "chance a memcmp()" trick in practice (there
is one duplicate). But it really is vanishingly close to perfectly
pessimal on my dev system, or that is at least my sincere belief.

I think that we're going to find ourselves with more and more cases
where to risk wasting lots of compute bandwidth to save a little
memory bandwidth is, counter-intuitively, a useful optimization. My
opportunistic memcmp() is probably an example of this. I'm aware of
others. This is perhaps a contributing factor to how inexpensive it is
to waste all the effort that goes into strxfrm() and so on. Having
said that, this is an idea from the 1960s, which might explain
something about the name of the technique.

> But I still think that a lot more could be done - and I'd challenge
> you (or others) to do it - to look for cases where this might be a
> pessimization. I get that the patch has an upside, but nearly every
> patch that anybody proposes does, and the author usually points out
> those cases quite prominently, as you have, and right so. But what
> makes for a much more compelling submission is when the author *also*
> tries really hard to break the patch, and hopefully fails. I agree
> that the test result shown above is good news for this patch's future
> prospects, but I *don't* agree that it nails the door shut. What
> about other locales? Other operating systems? Other versions of
> libc? Longer strings? Wider tuples? Systems where datums are only
> 32-bits? Sure, you can leave those things to the reviewer and/or
> committer to worry about, but that's not the way to expedite the
> patch's trip into the tree.

I don't think that 32-bit systems are all that high a priority for
performance work. Cellphones will come out with 64-bit processors this
year. Even still, it's hard to reason about how much difference that
will make, except to say that the worst case cannot be that bad. As
for other locales, it only gets better for this patch, because I
believe en_US.UTF-8 is one of the cheapest to compare locales (which
is to say, requires fewest passes). If you come up with some test case
with complicated collation rules (I'm thinking of hu_HU, Hungarian),
it surely makes the patch look much better. Having said that, I still
don't do anything special with the C locale (just provide a
non-fmgr-accessed comparator), which should probably be fixed, on the
grounds that sorting using the C locale is probably now more expensive
than with the en_US.UTF-8 collation.

> I have to admit, I didn't really view the original postings on this
> topic to be anything more than, hey, we've got something promising
> here, it's worth more study. That's part of why I was so taken aback
> by Greg's email. There's certainly good potential here, but I think
> there's quite a bit left of work left to do before you can declare
> victory...

I think that Greg's choice of words was a little imprudent, but must
be viewed in the context of an offline discussion during the hall
track of pgConf NYC. Clearly Greg wasn't about to go off and
unilaterally commit this. FWIW, I think I put him off the idea a few
hours after he made those remarks, without intending for what I'd said
to have that specific effect (or the opposite effect).

--
Peter Geoghegan

On 04/07/2014 11:35 PM, Peter Geoghegan wrote:
> Okay. Here is a worst-case, with the pgbench script the same as my
> original test-case, but with much almost maximally unsympathetic data
> to sort:
>
> [local]/postgres=# update customers set firstname =
> 'padding-padding-padding-padding' || firstname;

Hmm. I would expect the worst case to be where the strxfrm is not
helping because all the entries have the same prefix, but the actual key
is as short and cheap-to-compare as possible. So the padding should be
as short as possible. Also, we have a fast path for pre-sorted input,
which reduces the number of comparisons performed; that will make the
strxfrm overhead more significant.

I'm getting about 2x slowdown on this test case:

create table sorttest (t text);
insert into sorttest select 'foobarfo' || (g) || repeat('a', 75) from
generate_series(10000, 30000) g;

explain analyze select * from sorttest order by t;

Now, you can argue that that's acceptable because it's such a special
case, but if we're looking for the worst-case..

(BTW, IMHO it's way too late to do this for 9.4)

- Heikki

On 04/07/2014 09:19 PM, Peter Geoghegan wrote:
> The only case that this patch could possibly regress is where there
> are strings that differ beyond about the first 8 bytes, but are not
> identical (we chance a memcmp() == 0 before doing a full strcoll()
> when tie-breaking on the semi-reliable initial comparison). We still
> always avoid fmgr-overhead (and shim overhead, which I've measured),
> as in your original patch - you put that at adding 7% at the time,
> which is likely to make up for otherwise-regressed cases. There is
> nothing at all contrived about my test-case.

Did I understand correctly that this patch actually does two things:

1. Avoid fmgr and shim overhead
2. Use strxfrm to produce a pseudo-leading key that's cheaper to compare.

In that case, these changes need to be analyzed separately. You don't
get to "make up" for the losses by the second part by the gains from the
first part. We could commit just the first part (for 9.5!), and that has
to be the baseline for the second part.

This is very promising stuff, but it's not a slam-dunk win. I'd suggest
adding these to the next commitfest, as two separate patches.

- Heikki

On Mon, Apr 7, 2014 at 7:32 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> I think that Greg's choice of words was a little imprudent, but must
> be viewed in the context of an offline discussion during the hall
> track of pgConf NYC. Clearly Greg wasn't about to go off and
> unilaterally commit this. FWIW, I think I put him off the idea a few
> hours after he made those remarks, without intending for what I'd said
> to have that specific effect (or the opposite effect).

It was somewhere between your two interpretations. I intend to review
everything I can from the commitfest and then this patch and if this
patch is ready for commit before feature freeze I was saying I would
go ahead and commit it. That would only happen if there was a pretty
solid consensus that the my review was good and the patch was good of
course.

The point of the commit fest is to ensure that all patches get
attention. That's why I would only look at this after I've reviewed
anything else from the commitfest that I feel up to reviewing. But if
I have indeed done so there's no point in not taking other patches as
well up to feature freeze. I don't have any intention of lowering our
review standards of course.

So let's table this discussion until the hypothetical case of me doing
lots of reviews *and* reviewing this patch *and* that review being
positive and decisive enough to commit after one review cycle.

--
greg

t
On Tue, Apr 8, 2014 at 3:12 AM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> 1. Avoid fmgr and shim overhead
> 2. Use strxfrm to produce a pseudo-leading key that's cheaper to compare.
>
> In that case, these changes need to be analyzed separately. You don't get to
> "make up" for the losses by the second part by the gains from the first
> part. We could commit just the first part (for 9.5!), and that has to be the
> baseline for the second part.

Yes, that's right. Robert already submitted a patch that only did 1)
almost 2 years ago. That should have been committed at the time, but
wasn't. At the time, the improvement was put at about 7% by Robert. It
would be odd to submit the same patch that Robert withdrew already.

Why shouldn't 2) be credited with the same benefits as 1) ? It's not
as if the fact that the strxfrm() trick uses SortSupport is a
contrivance. I cannot reasonably submit the two separately, unless the
second in a cumulative patch. By far the largest improvements come
from 2), while 1) doesn't regress anything.

--
Peter Geoghegan

On 04/08/2014 08:02 PM, Peter Geoghegan wrote:
> On Tue, Apr 8, 2014 at 3:12 AM, Heikki Linnakangas
> <hlinnakangas(at)vmware(dot)com> wrote:
>> 1. Avoid fmgr and shim overhead
>> 2. Use strxfrm to produce a pseudo-leading key that's cheaper to compare.
>>
>> In that case, these changes need to be analyzed separately. You don't get to
>> "make up" for the losses by the second part by the gains from the first
>> part. We could commit just the first part (for 9.5!), and that has to be the
>> baseline for the second part.
>
> Yes, that's right. Robert already submitted a patch that only did 1)
> almost 2 years ago. That should have been committed at the time, but
> wasn't. At the time, the improvement was put at about 7% by Robert. It
> would be odd to submit the same patch that Robert withdrew already.
>
> Why shouldn't 2) be credited with the same benefits as 1) ? It's not
> as if the fact that the strxfrm() trick uses SortSupport is a
> contrivance. I cannot reasonably submit the two separately, unless the
> second in a cumulative patch.

Sure, submit the second as a cumulative patch.

> By far the largest improvements come
> from 2), while 1) doesn't regress anything.

Right. But 1) is the baseline we need to evaluate 2) against.

- Heikki

On Tue, Apr 8, 2014 at 10:10 AM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> Right. But 1) is the baseline we need to evaluate 2) against.

I don't agree with that. Surely we're concerned with not regressing
cases that people actually care about, which in practical terms means
the changes of a single release. While I guess I'm fine with
structuring the patch like that, I don't think it's fair that the
strxfrm() stuff doesn't get credit for not regressing those cases so
badly just because they're only ameliorated by the fmgr-eliding stuff.
While I'm concerned about worst case performance myself, I don't want
to worry about Machiavelli rather than Murphy. What collation did you
use for your test-case?

The fmgr-eliding stuff is only really valuable in that it ameliorates
the not-so-bad regressions, and is integral to the strxfrm() stuff.
Let's not lose sight of the fact that (if we take TPC style benchmarks
as representative) the majority of text sorts can be made at least 3
times faster.

--
Peter Geoghegan

On Tue, Apr 8, 2014 at 3:10 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Tue, Apr 8, 2014 at 10:10 AM, Heikki Linnakangas
> <hlinnakangas(at)vmware(dot)com> wrote:
>> Right. But 1) is the baseline we need to evaluate 2) against.
>
> I don't agree with that. Surely we're concerned with not regressing
> cases that people actually care about, which in practical terms means
> the changes of a single release.

No, we're concerned about ending up with the best possible
performance. That could mean applying the fmgr-elision but not the
other part. Whether the other part is beneficial is based on how it
compares to the performance post-fmgr-elision.

As an oversimplified example, suppose someone were to propose two
patches, one that makes PostgreSQL ten times as fast and the other of
which slows it down by a factor of five. If someone merges those two
things into a single combined patch, we would surely be foolish to
apply the whole thing. The right thing would be to separate them out
and apply only the first one. Every change has to stand on its own
two feet.

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

On Tue, Apr 8, 2014 at 12:31 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> No, we're concerned about ending up with the best possible
> performance. That could mean applying the fmgr-elision but not the
> other part. Whether the other part is beneficial is based on how it
> compares to the performance post-fmgr-elision.

I agree with everything you say here, but I'm puzzled only because
it's overwhelmingly obvious that the strxfrm() stuff is where the
value is. You can dispute whether or not I should have made various
tweaks, and you probably should, but the basic value of that idea is
very much in evidence already. You yourself put the improvements of
fmgr-elision alone at ~7% back in 2012 [1]. At the time, Noah said
that he didn't think it was worth bothering with that patch for what
he considered to be a small gain, a view which I did not share at the
time.

What I have here looks like it speeds things up a little over 200% (so
a little over 300% of the original throughput) with a single client
for many representative cases. That's a massive difference, to the
point that I don't see a lot of sense in considering fmgr-elision
alone separately.

[1] http://www.postgresql.org/message-id/CA+Tgmoa8by24gd+YbuPX=5gSGmN0w5sGiPzWwq7_8iS26vL5CQ@mail.gmail.com
--
Peter Geoghegan

Peter Geoghegan wrote:

> What I have here looks like it speeds things up a little over 200% (so
> a little over 300% of the original throughput) with a single client
> for many representative cases. That's a massive difference, to the
> point that I don't see a lot of sense in considering fmgr-elision
> alone separately.

I think the point here is what matters is that that gain from the
strxfrm part of the patch is large, regardless of what the baseline is
(right?). If there's a small loss in an uncommon worst case, that's
probably acceptable, as long as the worst case is uncommon and the loss
is small. But if the loss is large, or the case is not uncommon, then a
fix for the regression is going to be a necessity.

You seem to be assuming that a fix for whatever regression is found is
going to be impossible to find.

--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Tue, Apr 8, 2014 at 2:48 PM, Alvaro Herrera <alvherre(at)2ndquadrant(dot)com> wrote:
> I think the point here is what matters is that that gain from the
> strxfrm part of the patch is large, regardless of what the baseline is
> (right?). If there's a small loss in an uncommon worst case, that's
> probably acceptable, as long as the worst case is uncommon and the loss
> is small. But if the loss is large, or the case is not uncommon, then a
> fix for the regression is going to be a necessity.

That all seems reasonable. I just don't understand why you'd want to
break out the fmgr-elision part, given that that was already discussed
at length two years ago.

> You seem to be assuming that a fix for whatever regression is found is
> going to be impossible to find.

I think that a fix that is actually worth it on balance will be
elusive. Heikki's worst case is extremely narrow. I think he'd
acknowledge that himself. I've already fixed some plausible
regressions. For example, the opportunistic early "len1 == l3n2 &&
memcmp() == 0?" test covers the common case where two leading keys are
equal. I think we're very much into chasing diminishing returns past
this point. I think that my figure of a 5% regression is much more
realistic, even though it is itself quite unlikely.

I think that the greater point is that we don't want to take worrying
about worst case performance to extremes. Calling Heikki's 50%
regression the worst case is almost unfair, since it involves very
carefully crafted input. You could probably also carefully craft input
that made our quicksort implementation itself go quadratic, a behavior
not necessarily exhibited by an inferior implementation for the same
input. Yes, let's consider a pathological worst case, but lets put it
in the context of being one end of a spectrum of behaviors, on the
extreme fringes. In reality, only a tiny number of individual sort
operations will experience any kind of regression at all. In simple
terms, I'd be very surprised if anyone complained about a regression
at all. If anyone does, it's almost certainly not going to be a 50%
regression. There is a reason why many other systems have
representative workloads that they target (i.e. a variety of tpc
benchmarks). I think that a tyranny of the majority is a bad thing
myself, but I'm concerned that we sometimes take that too far.

I wonder, why did Heikki not add more padding to the end of the
strings in his example, in order to give strxfrm() more wasted work?
Didn't he want to make his worst case even worse? Or was is to control
for TOASTing noise?

--
Peter Geoghegan

On Thu, Apr 3, 2014 at 12:19 PM, Thom Brown <thom(at)linux(dot)com> wrote:
> Looking good:
>
> -T 100 -n -f sort.sql
>
> Master: 21.670467 / 21.718653 (avg: 21.69456)
> Patch: 66.888756 / 66.888756 (avg: 66.888756)

These were almost exactly the same figures as I saw on my machine.
However, when compiling with certain additional flags -- with
CFLAGS="-O3 -march=native" -- I was able to squeeze more out of this.
My machine has a recent Intel CPU, "Intel(R) Core(TM) i7-3520M". With
these build settings the benchmark then averages about 75.5 tps across
multiple runs, which I'd call a fair additional improvement. I tried
this because I was specifically interested in the results of a memcmp
implementation that uses SIMD. I believe that these flags make
gcc/glibc use a memcmp implementation that takes advantage of SSE
where supported (and various subsequent extensions). Although I didn't
go to the trouble of verifying all this by going through the
disassembly, or instrumenting the code in any way, that is my best
guess as to what actually helped. I don't know how any of that might
be applied to improve matters in the real world, which is why I
haven't dived into this further, but it's worth being aware of.

--
Peter Geoghegan

On Tue, Apr 8, 2014 at 2:57 AM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> Hmm. I would expect the worst case to be where the strxfrm is not helping
> because all the entries have the same prefix, but the actual key is as short
> and cheap-to-compare as possible. So the padding should be as short as
> possible. Also, we have a fast path for pre-sorted input, which reduces the
> number of comparisons performed; that will make the strxfrm overhead more
> significant.
>
> I'm getting about 2x slowdown on this test case:
>
> create table sorttest (t text);
> insert into sorttest select 'foobarfo' || (g) || repeat('a', 75) from
> generate_series(10000, 30000) g;

One thing that isn't all that obvious about this worst case is that
it's in general very qsort() friendly, and therefore the startup costs
(copying) totally dominates. Actually, you're not even sorting -
you're verifying that the tuples are already exactly in order (a
questionable optimization we apply at every level). Consider:

postgres=# select correlation from pg_stats where tablename =
'sorttest' and attname = 't';
correlation
-------------
1
(1 row)

So you only have to do n - 1 comparisons, never n log n. This is a
very skewed test. There is no reason to think that strcoll() is better
than strxfrm() + strcmp() if the first difference is earlier. That's
the main reason why what I called a worse case is much more
representative than this, even if we assume that it's very common for
people to sort strings that don't differ in the first 8 bytes and yet
are not identical.

I took a look at fixing your worst case all the same, despite becoming
discouraged during discussion at pgCon. I thought about it for a
while, and realized that the problems are probably solvable. Even
still, I would like to emphasize that this is a family of techniques
for B-Tree operator classes. Sorting heap tuples is not the only use
case, and it's probably not even the most interesting one, yet all the
criticisms are largely confined to sorting alone. This is because
wasted cycles on a poor man's comparison are not too problematic if
the only additional work is a few CPU instructions for comparison (and
not the entire transformation, which happens when that cost can be
amortized over a huge length of time). I'm thinking of inner pages in
B-Trees here. I've looked at heap tuple sorting first because the
sortsupport infrastructure happens to be available, making it the best
proving ground. That's the only reason.

Anyway, major steps against worst case performance in the attached
revision include:

* 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), and with ASCII
code points you get the full benefit of being able to store the
leading 8 code points in the poorman's key (we also insist that
sizeof(Datum) == 8 to apply the poor man's optimization). It might be
that this restricts the optimization to 64-bit Linux entirely, where
glibc is almost universally used. If that's true, I consider it to be
a acceptable given that the majority of Postgres systems use this
family of platforms in practice. Even still, the fact that every
implementation doesn't meet my standard came as a big surprise to me,
and so I hope that the problem is limited to Mac OSX. I'm slightly
concerned that all BSD systems are affected by this issue, but even if
that was true not covering those cases would be acceptable in my view.
*Maybe* we could come up with a scheme for stripping those header
bytes if someone feels very strongly about it, and we judge it to be
worth it to get our hands dirty in that way (we could even dynamically
verify the header bytes always matched, and bail if our assumption was
somehow undermined at little cost on those platforms).

* The dominant additional cost in Heikki's worst case is wasted
strxfrm() transformations (or maybe just the memcpy() overhead
required to NULL terminate text for strxfrm() processing). When
copying over heap tuples into the memtuples array, we instrument the
costs and weigh them against the likely eventual benefits using
heuristic rules. We may choose to abort the transformation process
early if it doesn't look promising. This process includes maintaining
the mean query length so far (which is taken as a proxy for
transformation costs), as well as maintaining the approximate
cardinality of the set of already generated poor man's keys using the
HyperLogLog algorithm [1].

This almost completely fixes the worst case performance Heikki
complained of. With smaller strings you might get my implementation to
show worse regressions than what you'll see for your worst case by
placing careful traps for the heuristics that now appear within
bttext_abort(), but I suspect not by terribly much. These are still
fairly implausible cases.

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. As the HyperLogLog paper [2]
says:

"In practice, the HYPERLOGLOG program is quite efficient: like the
standard LOGLOG of [10] or MINCOUNT of [16], its running time is
dominated by the computation of the hash function, so that it is only
three to four times slower than a plain scan of the data (e.g., by the
Unix command “wc -l”, which merely counts end-of-lines)."

(Since we're doing all that copying, and everything else anyway, and
only hashing the first 8 bytes, the ratio for us is more compelling
still, before we even begin the sort).

I'm not entirely sure that the fact that I now pass down outer plan
estimated plan rows in the case of ExecSort(), to hint to the
bttext_abort() heuristics so it has a "sense of proportion" about
costs is the right thing. It's a difficult problem to judge, so I've
left that in despite some misgivings. In any case, I think that this
revision isn't too far from the best of both worlds. I do have some
concerns that I don't have things well balanced within bttext_abort(),
but it's a start. It's hard to exactly characterize the break even
point here, particularly given that we only know about cardinality and
string length, and not distribution. Let's not lose sight of the fact
that in the real world the large majority of sorts will be on the
right side of that break even point, though. This is all about
ameliorating infrequent worst cases.

Because of the new strxfrm()-quality AC_TRY_RUN configure test, you'll
need to "autoreconf" and so on to get the patch working. I didn't
include changes to the "configure" file generated by these changes in
the patch itself.

I use "en_US.UTF8" for the purposes of all benchmark figures here. I
attach some interesting numbers for a variety of cases
(poorman-performance.txt). Worse case performance is considered.

I've been using a table of 3,17,102 cities of the world to look at
average and best case performance. Overview:

postgres=# select count(*), country from cities group by country order
by 1 desc limit 15;
count | country
-------+--------------------------
66408 | India
35845 | France
29926 | United States of America
13154 | Turkey
11210 | Mexico
11028 | Germany
9352 | Tanzania
8118 | Spain
8109 | Italy
7680 | Burkina Faso
6066 | Czech Republic
6043 | Iran
5777 | Slovenia
5584 | Brazil
5115 | Philippines
(15 rows)

These city names are all Latin characters with accents and other
diacritics. For example:

postgres=# select * from cities where country = 'Sweden' limit 5;
country | province | city | one | two | three | four
---------+----------+---------------+--------+--------+--------+--------
Sweden | Blekinge | Backaryd | [null] | [null] | [null] | [null]
Sweden | Blekinge | Bräkne-Hoby | [null] | [null] | [null] | [null]
Sweden | Blekinge | Brömsebro | [null] | [null] | [null] | [null]
Sweden | Blekinge | Drottningskär | [null] | [null] | [null] | [null]
Sweden | Blekinge | Eringsboda | [null] | [null] | [null] | [null]
(5 rows)

You can download a plain format dump of this database here:
http://postgres-benchmarks.s3-website-us-east-1.amazonaws.com/data/cities.dump

I also attach some DEBUG1 output that shows the accuracy of
HyperLogLog estimation (of poor man's normalized key cardinality) for
the cases tested (poorman-debug-hll-cardinality.txt). It's very
accurate given the low, fixed memory overhead chosen.

[1] https://en.wikipedia.org/wiki/HyperLogLog

[2] http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
--
Peter Geoghegan

On Thu, Jun 5, 2014 at 5:37 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> Even still, the fact that every
> implementation doesn't meet my standard came as a big surprise to me,
> and so I hope that the problem is limited to Mac OSX. I'm slightly
> concerned that all BSD systems are affected by this issue

I tried out my test program with FreeBSD 9.2-RC2. I linked my program
to the system libc. I explicitly set the collation to "en_US.UTF-8". I
can't see any header bytes, and that implementation meets the standard
my configure test looks for generally, so I guess this was only ever
an issue peculiar to Mac OS X (or the collations it ships with?).

I probably should have mentioned before that Windows is still broken
(I don't plan on optimizing Windows at all due to complexity around
the UTF-8 hacks on that platform, but right now the sortsupport
routine just returns NULL, which is not acceptable).

--
Peter Geoghegan

On Thu, Jun 5, 2014 at 5:37 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> One thing that isn't all that obvious about this worst case is that
> it's in general very qsort() friendly, and therefore the startup costs
> (copying) totally dominates. Actually, you're not even sorting -
> you're verifying that the tuples are already exactly in order (a
> questionable optimization we apply at every level).

Kevin mentioned something about the Wisconsin courts having columns
that all began with "The State of Wisconsin Vs." in the dev meeting in
Ottawa. I thought that this was an interesting case, because it is
representative of reality, which is crucially important to consider
here. I decided to simulate it. In my original test database:

postgres=# create table wisconsin(casen text);
CREATE TABLE
postgres=# insert into wisconsin select 'The State of Wisconsin Vs. '
|| city from cities;
INSERT 0 317102

sort-wisconsin.sql: select * from (select * from wisconsin order by
casen offset 1000000) d;

Master:

pgbench -M prepared -f sort-wisconsin.sql -T 300 -n
transaction type: Custom query
scaling factor: 1
query mode: prepared
number of clients: 1
number of threads: 1
duration: 300 s
number of transactions actually processed: 55
latency average: 5454.545 ms
tps = 0.181191 (including connections establishing)
tps = 0.181191 (excluding connections establishing)

Patch (most recent revision, with ameliorations, HyperLogLog, etc):

pgbench -M prepared -f sort-wisconsin.sql -T 300 -n

transaction type: Custom query
scaling factor: 1
query mode: prepared
number of clients: 1
number of threads: 1
duration: 300 s
number of transactions actually processed: 55
latency average: 5454.545 ms
tps = 0.182593 (including connections establishing)
tps = 0.182594 (excluding connections establishing)

Earlier patch (no ameliorations for Heikki's case):

pgbench -M prepared -f sort-wisconsin.sql -T 300 -n

transaction type: Custom query
scaling factor: 1
query mode: prepared
number of clients: 1
number of threads: 1
duration: 300 s
number of transactions actually processed: 54
latency average: 5555.556 ms
tps = 0.176914 (including connections establishing)
tps = 0.176915 (excluding connections establishing)

With my most recent revision, the ameliorating measures are effective
enough that with the sortsupport shim and fmgr trampoline avoided, we
still come out ahead even for this case. Great. But you may be
surprised that the regression is so small in the case of the patch
without any ameliorating measures (the original patch). That's because
the data isn't *perfectly* logically/physically correlated here, as in
Heikki's worst case. So, the 317,102 wasted strxfrm() calls are
relatively inexpensive. Consider how cost_sort() models the cost of a
sort when an in memory quicksort is anticipated:

/* We'll use plain quicksort on all the input tuples */
startup_cost += comparison_cost * tuples * LOG2(tuples);

In the case of this quicksort, the planner guesses there'll be "317102
* LOG2(317102)" comparisons -- about 5,794,908 comparisons, which
implies over 10 times as many strcoll() calls as wasted strxfrm()
calls. The cost of those strxfrm() calls begins to look insignificant
before n gets too big (at n = 100, it's 100 wasted strxfrm() calls to
about 664 strcoll() calls). Unless, of course, you have a "bubble sort
best case" where everything is already completely in order, in which
case there'll be a 1:1 ratio between wasted strxfrm() calls and
strcoll() calls. This optimization was something that we added to our
qsort(). It doesn't appear in the original NetBSD implementation, and
it doesn't appear in the Bentley/McIlroy paper, and it doesn't appear
anywhere else that I'm aware of. I'm not the only person to regard it
with suspicion - Tom has in the past expressed doubts about that too
[1]. Also, note that no sorting algorithm can do better than O(n log
n) in the average case - that's the information-theoretical lower
bound on the average-case speed of any comparison-based sorting
algorithm.

To be clear: I'm certainly not saying that we shouldn't fix Heikki's
worst case, and indeed I believe I have, but we should also put this
worst case in perspective.

By the way, I just realized that I failed to fully remove client
overhead (I should have put an extra 0 on the end of my offset for the
city.sql query), which added noise to the "city"/"country"/"province"
tests. Revised figures are as follows (these are better than before):

Master:
======

pgbench -M prepared -f sort-city.sql -T 300 -n

transaction type: Custom query
scaling factor: 1
query mode: prepared
number of clients: 1
number of threads: 1
duration: 300 s
number of transactions actually processed: 278
latency average: 1079.137 ms
tps = 0.924358 (including connections establishing)
tps = 0.924362 (excluding connections establishing)

Patch:
=====

pgbench -M prepared -f sort-city.sql -T 300 -n

transaction type: Custom query
scaling factor: 1
query mode: prepared
number of clients: 1
number of threads: 1
duration: 300 s
number of transactions actually processed: 1046
latency average: 286.807 ms
tps = 3.486089 (including connections establishing)
tps = 3.486104 (excluding connections establishing)

Master:
======

pgbench -M prepared -j 4 -c 4 -f sort-city.sql -T 300 -n

transaction type: Custom query
scaling factor: 1
query mode: prepared
number of clients: 4
number of threads: 4
duration: 300 s
number of transactions actually processed: 387
latency average: 3100.775 ms
tps = 1.278062 (including connections establishing)
tps = 1.278076 (excluding connections establishing)

Patch:
=====

pgbench -M prepared -j 4 -c 4 -f sort-city.sql -T 300 -n

transaction type: Custom query
scaling factor: 1
query mode: prepared
number of clients: 4
number of threads: 4
duration: 300 s
number of transactions actually processed: 1670
latency average: 718.563 ms
tps = 5.557700 (including connections establishing)
tps = 5.557754 (excluding connections establishing)

BTW, if you want to measure any of this independently, I suggest
making sure that power management settings don't ruin things. I advise
setting CPU governor to "performance" for each core on Linux, for
example.

[1] http://www.postgresql.org/message-id/18033.1361789032@sss.pgh.pa.us
--
Peter Geoghegan

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

On Thu, Jun 12, 2014 at 1:25 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>
> 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"

...

> [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.

If you knew mac's output character set with some certainty, you could
compress it rather efficiently by applying a tabulated decode back
into non-printable bytes. Say, like base64 decoding (the set appears
to be a subset of base64, but it's hard to be sure).

Ie,
x = strxfrm(s)
xz = hex(tab[x[0]] + 64*tab[x[1]] + 64^2*tab[x[2]] ... etc)

This can be made rather efficient. But the first step is defining with
some certainty the output character set.

Thanks for looking into this.

On Thu, Jun 12, 2014 at 9:25 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> 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.

Right. It was a little bit incautious of me to say that we had the
full benefit of 8 bytes of storage with "en_US.UTF-8", since that is
only true of lower case characters (I think that FreeBSD can play
tricks with this. Sometimes, it will give you the benefit of 8 bytes
of entropy for an 8 byte string, with only non-differentiating
trailing bytes, so that the first 8 bytes of "Aaaaaaaa" are distinct
from the first eight bytes of "aaaaaaaa", while any trailing bytes are
non-distinct for both). In any case it's pretty clear that a goal of
the glibc implementation is to concentrate as much entropy as possible
into the first part of the string, and that's the important point.
This makes perfect sense, and is why I was so incredulous about the
Mac behavior. After all, the Open Group's strcoll() documentation
says:

"The strxfrm() and strcmp() functions should be used for sorting large lists."

Sorting text is hardly an infrequent requirement -- it's almost the
entire reason for having strxfrm() in the standard. You're always
going to want to have each strcmp() find differences as early as
possible.

--
Peter Geoghegan

Peter Geoghegan <pg(at)heroku(dot)com> writes:
> ... In any case it's pretty clear that a goal of
> the glibc implementation is to concentrate as much entropy as possible
> into the first part of the string, and that's the important point.
> This makes perfect sense, and is why I was so incredulous about the
> Mac behavior.

I think this may be another facet of something we were already aware of,
which is that the UTF8 locales on OS X pretty much suck. It's fairly
clear that Apple has put no effort into achieving more than minimal
standards compliance for those. Sorting doesn't work as expected in
those locales, for example.

Still, that's reality, and any proposal to rely on strxfrm is going to
have to deal with it :-(

regards, tom lane

On Thu, Jun 12, 2014 at 2:09 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> Right. It was a little bit incautious of me to say that we had the
> full benefit of 8 bytes of storage with "en_US.UTF-8", since that is
> only true of lower case characters (I think that FreeBSD can play
> tricks with this. Sometimes, it will give you the benefit of 8 bytes
> of entropy for an 8 byte string, with only non-differentiating
> trailing bytes, so that the first 8 bytes of "Aaaaaaaa" are distinct
> from the first eight bytes of "aaaaaaaa", while any trailing bytes are
> non-distinct for both). In any case it's pretty clear that a goal of
> the glibc implementation is to concentrate as much entropy as possible
> into the first part of the string, and that's the important point.

I thought about using an order-preserving compression technique like
Hu Tucker [1] in order to get additional benefit from those 8 bytes.
Even my apparently sympathetic cities example isn't all that
sympathetic, since the number of distinct normalized keys is only
about 75% of the total number of cities (while a strcmp()-only
reliable tie-breaker isn't expected to be useful for the remaining
25%). Here is the improvement I see when I setup things so that there
is a 1:1 correspondence between city rows and distinct normalized
keys:

postgres=# with cc as
(select count(*), array_agg(ctid) ct,
substring(strxfrm_test(city)::text from 0 for 19 ) blob from cities
group by 3 having count(*) > 1 order by 1),
ff as
(
select unnest(ct[2:400]) u, blob from cc
)
delete from cities using ff where cities.ctid = ff.u;

postgres=# vacuum full cities ;
VACUUM

Afterwards:

postgres=# select count(*) from (select distinct
substring(strxfrm_test(city)::text from 0 for 19) from cities) i;
count
--------
243782
(1 row)

postgres=# select count(*) from cities;
count
--------
243782
(1 row)

$ cat sort-city.sql
select * from (select * from cities order by city offset 1000000) d;

Patch results
==========

pgbench -M prepared -f sort-city.sql -T 300 -n

transaction type: Custom query
scaling factor: 1
query mode: prepared
number of clients: 1
number of threads: 1
duration: 300 s
number of transactions actually processed: 1734
latency average: 173.010 ms
tps = 5.778545 (including connections establishing)
tps = 5.778572 (excluding connections establishing)

pgbench -M prepared -j 4 -c 4 -f sort-city.sql -T 300 -n

transaction type: Custom query
scaling factor: 1
query mode: prepared
number of clients: 4
number of threads: 4
duration: 300 s
number of transactions actually processed: 2916
latency average: 411.523 ms
tps = 9.706683 (including connections establishing)
tps = 9.706776 (excluding connections establishing)

Master results
==========

pgbench -M prepared -f sort-city.sql -T 300 -n

transaction type: Custom query
scaling factor: 1
query mode: prepared
number of clients: 1
number of threads: 1
duration: 300 s
number of transactions actually processed: 390
latency average: 769.231 ms
tps = 1.297545 (including connections establishing)
tps = 1.297551 (excluding connections establishing)

pgbench -M prepared -j 4 -c 4 -f sort-city.sql -T 300 -n

transaction type: Custom query
scaling factor: 1
query mode: prepared
number of clients: 4
number of threads: 4
duration: 300 s
number of transactions actually processed: 535
latency average: 2242.991 ms
tps = 1.777005 (including connections establishing)
tps = 1.777024 (excluding connections establishing)

So that seems like a considerable further improvement that would be
nice to see more frequently. I don't know that it's worth it to go to
the trouble of compressing given the existing ameliorating measures
(HyperLogLog, etc), at least if using compression is motivated by
worst case performance. There is some research on making this work for
this kind of thing specifically [2].

My concern is that it won't be worth it to do the extra work,
particularly given that I already have 8 bytes to work with. Supposing
I only had 4 bytes to work with (as researchers writing [2] may have
only had in 1994), that would leave me with a relatively small number
of distinct normalized keys in many representative cases. For example,
I'd have a mere 40,665 distinct normalized keys in the case of my
"cities" database, rather than 243,782 (out of a set of 317,102 rows)
for 8 bytes of storage. But if I double that to 16 bytes (which might
be taken as a proxy for what a good compression scheme could get me),
I only get a modest improvement - 273,795 distinct keys. To be fair,
that's in no small part because there are only 275,330 distinct city
names overall (and so most dups get away with a cheap memcmp() on
their tie-breaker), but this is a reasonably organic, representative
dataset.

Now, it's really hard to judge something like that, and I don't
imagine that this analysis is all that scientific. I am inclined to
think that we're better off just aborting if the optimization doesn't
work out while copying, and forgetting about order preserving
compression. Let us not lose sight of the fact that strxfrm() calls
are not that expensive relative to the cost of the sort in almost all
cases.

[1] http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/jstor_514.pdf

[2] http://www.hpl.hp.com/techreports/Compaq-DEC/CRL-94-3.pdf
--
Peter Geoghegan

On Mon, Jul 14, 2014 at 2:53 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> My concern is that it won't be worth it to do the extra work,
> particularly given that I already have 8 bytes to work with. Supposing
> I only had 4 bytes to work with (as researchers writing [2] may have
> only had in 1994), that would leave me with a relatively small number
> of distinct normalized keys in many representative cases. For example,
> I'd have a mere 40,665 distinct normalized keys in the case of my
> "cities" database, rather than 243,782 (out of a set of 317,102 rows)
> for 8 bytes of storage. But if I double that to 16 bytes (which might
> be taken as a proxy for what a good compression scheme could get me),
> I only get a modest improvement - 273,795 distinct keys. To be fair,
> that's in no small part because there are only 275,330 distinct city
> names overall (and so most dups get away with a cheap memcmp() on
> their tie-breaker), but this is a reasonably organic, representative
> dataset.

Are those numbers measured on MAC's strxfrm?

That was the one with suboptimal entropy on the first 8 bytes.

On Mon, Jul 14, 2014 at 11:03 AM, Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
> Are those numbers measured on MAC's strxfrm?
>
> That was the one with suboptimal entropy on the first 8 bytes.

No, they're from a Linux system which uses glibc 2.19. The
optimization will simply be not used on implementations that don't
meet a certain standard (see my AC_TRY_RUN test program). I'm
reasonably confident that that test program will pass on most systems.
Just not Mac OSX. The optimization is never used on Windows and 32-bit
systems for other reasons.

--
Peter Geoghegan

On Thu, Jun 12, 2014 at 2:09 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> Thanks for looking into this.

Is anyone going to look at this?

I attach a new revision. The only real change to the code is that I
fixed an open item concerning what to do on WIN32 with UTF-8, where
the UTF-16 hacks that we do there cannot be worked around to make the
optimization still work, and yet we're still obligated to set up a
sort support state since there is a cataloged sort support function
(unfortunately I wasn't able to test it on Windows since I no longer
own a Windows machine, but it should be fine). I set up a comparison
shim within varlena.c for that case only. This is a kludge, but I
decided that it was better than preparing the sort support
infrastructure to not get a sane sort support state from all opclasses
just because of some platform-specific issue. I think that's justified
by the fact that it's very unlikely to happen again. text is a
datatype that is unusually tied to the operating system. This does
necessitate having the sort support struct record which sort operator
was originally used to lookup the sort support function, but it seems
reasonable to store that in all instances.

What may be of more interest to reviewers is the revised AC_TRY_RUN
test program that "configure" consults. While the code is unchanged,
there is now a detailed rationale for why it's reasonable to expect
that a significant amount of entropy will be concentrated in the first
8 bytes of a strxfrm() blob, with reference to how those algorithms
are more or less required to behave by the Unicode consortium. The
basic reason is that the algorithm for building binary sort keys
(described by a Unicode standard [1] defining the behavior of Unicode
collation algorithms, and implemented by strxfrm()) specifically works
by storing primary level, secondary level and tertiary level weights
in turn in the returned blob. There may be additional levels, too. As
the standard says:

"""
The primary level (L1) is for the basic sorting of the text, and the
non-primary levels (L2..Ln) are for adjusting string weights for other
linguistic elements in the writing system that are important to users
in ordering, but less important than the order of the basic sorting.
"""

Robert pointed out a case where varying character case of an English
word did not alter the primary level bytes (and thus the poor man's
normalized key was the same). He acknowledged that most of the entropy
of the first 8 bytes of the string went into the first 8 bytes of the
blob/key. This can actually be very useful to the optimization in some
cases. In particular, with most Latin alphabets you'll see the same
pattern when diacritics are used. This means that even though the
original string has (say) an accented character that would take 2
bytes to store in UTF-8, the weight in the primary level is the same
as an equivalent unaccented character (and so only takes one byte to
store at that level, with differences only in subsequent levels).
Whole strxfrm() blobs are the same length regardless of how many
accents appear in otherwise equivalent original Latin string, and you
get exactly the same high concentrations of entropy in the first 8
bytes in pretty much all Latin alphabets (the *absence* of diacritics
is stored in later weight levels too, even with the "en_US.UTF-8"
collation). As the standard says:

"""
By default, the algorithm makes use of three fully-customizable
levels. For the Latin script, these levels correspond roughly to:

alphabetic ordering
diacritic ordering
case ordering.

A final level may be used for tie-breaking between strings not
otherwise distinguished.
"""

In practice a huge majority of comparisons are expected to be resolved
at the primary weight level (in the case of a straight-up sort of
complete, all-unique strxfrm() blobs), which at least in the case of
glibc appear to require (at most) as many bytes to store as an
original UTF-8 string did. Performance of a sort using a
strcoll()-based collation could be *faster* than the "C" location with
this patch if there were plenty of Latin characters with diacritics.
The diacritics would effectively be removed from the poor man's
normalized key representations, and would only be considered when a
tie-breaker is required.

[1] http://www.unicode.org/reports/tr10/
--
Peter Geoghegan

On Sun, Jul 27, 2014 at 8:00 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> What may be of more interest to reviewers is the revised AC_TRY_RUN
> test program that "configure" consults.

I haven't looked yet. Can you describe what exactly the AC_TRY_RUN is
testing for?

If it's just whether the system supports strxfrm or UTF-8 at all that
might be ok. If it's detailed behaviour of the locales then that's a
problem since that could vary the platform the code is eventually run
on on compared to the one it's built on.

--
greg

On Sun, Jul 27, 2014 at 8:23 AM, Greg Stark <stark(at)mit(dot)edu> wrote:
> I haven't looked yet. Can you describe what exactly the AC_TRY_RUN is
> testing for?

It's more or less testing for a primary weight level (i.e. the first
part of the blob) that is no larger than the original characters of
the string, and has no "header bytes" or other redundancies. It also
matches secondary and subsequently weight levels to ensure that they
match, since the two stings tested have identical case, use of
diacritics, etc (they're both lowercase ASCII-safe strings). I don't
set a locale, but that shouldn't matter. I have good reason to believe
that many strxfrm() implementations behave this way, based on the
Unicode standard, and some investigation. Still, that is something
that can be more formally verified as long as we're not trusting of
strxfrm() generally rather than just discriminating against Mac OS X
specifically. I think that the Mac OS X implementation is an anomaly
(I haven't really looked into why), and the FreeBSD one just isn't
very good. But even the FreeBSD one appears to append primary weights
(only) to the blob it returns, and so is essentially the same for my
purposes [1].

[1] http://lists.freebsd.org/pipermail/freebsd-current/2003-April/001273.html
--
Peter Geoghegan

On Sun, Jul 27, 2014 at 12:34 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> It's more or less testing for a primary weight level (i.e. the first
> part of the blob) that is no larger than the original characters of
> the string, and has no "header bytes" or other redundancies. It also
> matches secondary and subsequently weight levels to ensure that they
> match, since the two stings tested have identical case, use of
> diacritics, etc (they're both lowercase ASCII-safe strings). I don't
> set a locale, but that shouldn't matter.

Actually, come to think of it that might not quite be true. Consider
this output from Robert's strxfrm test program:

pg(at)hamster:~/code$ ./strxfrm hu_HU.utf8 potyty
"potyty" -> 2826303001090909090109090909 (14 bytes)
pg(at)hamster:~/code$ ./strxfrm hu_HU.utf8 potyta
"potyta" -> 2826302e0c010909090909010909090909 (17 bytes)

This is a very esoteric Hungarian collation rule [1], which at one
point we found we had to plaster over within varstr_cmp() to prevent
indexes giving wrong answers [2]. It turns out that with this
collation, strcoll("potyty", "potty") == 0. The point specifically is
that in principle, collations can alter the number of weights that
appear in the primary level of the blob. This might imply that the
number of primary level bytes for the ASCII-safe string "abcdefgh"
might not equal those of "ijklmnop" for some collation, because of the
application of some similar esoteric rule. In principle, collations
are at liberty to make that happen, even though this hardly ever
occurs in practice (we first heard about it in 2005, although the
Unicode algorithm standard warns of this), and even though any of the
cases where it does occur it probably happens to not affect my little
AC_TRY_RUN program. Even still, I'm not comfortable with the
deficiency of the program. I don't want my optimization to
accidentally not apply just because some hypothetical collation where
this is true was used when Postgres was built. It probably couldn't
happen, but I must admit guaranteeing that it can't is a mess.
I suppose I could fix this by no longer assuming that the number of
bytes that appear in the primary level are fixed at n for n original
ASCII code point strings. I think that in theory even that could
break, though, because we have no principled way of parsing out
different weight levels (the Unicode standard has some ideas about how
given strxfrm()'s "no NULL bytes in blob" restriction, but that's
clearly implementation defined).

Given that Mac OS X is the only platform that appears to have this
header byte problem at all, I think we'd be better off specifically
disabling it on Mac OS X. I was very surprised to learn of the problem
on Mac OS X. Clearly it's going against the grain by having the
problem.

[1] http://www.postgresql.org/message-id/43A16BB7.7030606@mage.hu
[2] http://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=656beff59033ccc5261a615802e1a85da68e8fad
--
Peter Geoghegan

On Mon, Jul 28, 2014 at 4:41 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> Actually, come to think of it that might not quite be true.

Another issue is that we might just happen to use the "C" locale when
the AC_TRY_RUN program is invoked, which probably doesn't exhibit the
broken behavior of Mac OS X, since at least with glibc on Linux that
leaves you with a blob exactly matching the original string. Then
again, who knows? The Mac OS X behavior seems totally arbitrary to me.
If I had to guess I'd say it has something to do with their providing
an open standard shim to a UTF-16 based proprietary API.

--
Peter Geoghegan

On 28 Jul 2014, at 4:57 PM, Peter Geoghegan wrote:
> [....] Then
> again, who knows? The Mac OS X behavior seems totally arbitrary to me.
> If I had to guess I'd say it has something to do with their providing
> an open standard shim to a UTF-16 based proprietary API.

A quick glance at OSX's strxfrm() suggests they're using an implementation of strxfrm() from FreeBSD. You can find the source here:

http://www.opensource.apple.com/source/Libc/Libc-997.90.3/string/FreeBSD/strxfrm.c

(and a really quick glance at the contents of libc on OSX 10.9 reinforces this--- I don't see any calls into their CoreFoundation unicode string APIs.)

On Mon, Jul 28, 2014 at 5:14 PM, Wim Lewis <wiml(at)omnigroup(dot)com> wrote:
> A quick glance at OSX's strxfrm() suggests they're using an implementation of strxfrm() from FreeBSD. You can find the source here:
>
> http://www.opensource.apple.com/source/Libc/Libc-997.90.3/string/FreeBSD/strxfrm.c
>
> (and a really quick glance at the contents of libc on OSX 10.9 reinforces this--- I don't see any calls into their CoreFoundation unicode string APIs.)

Something isn't quite accounted for, then. The FreeBSD behavior is to
append the primary weights only. That makes their returned blobs
smaller than those you'll see on Linux, but also appears to imply that
their implementation is substandard (The PostgreSQL port uses ICU on
FreeBSD for a reason, I suppose). But FreeBSD did not add extra,
redundant "header bytes" right in the primary level when I tested it,
but I'm told Mac OS X does. I guess it could be that the collations
shipped differ, but I can't think why that would be. It does seem
peculiar that the Mac OS X blobs are always printable, whereas that
isn't the case with Glibc (the only restriction like that is that
there are no NULL bytes), and the Unicode algorithm standard
specifically says that that's okay.

--
Peter Geoghegan

On Sun, Jul 27, 2014 at 12:00 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> I attach a new revision.

I think that I may have missed a trick here.

It turns out that it isn't expensive to also hash original text
values, to track their cardinality using HyperLogLog - it's hardly
measurable when done at an opportune point just after strxfrm()
expansion. I was already tracking the cardinality of poor man's
normalized keys using HyperLogLog. If I track the cardinality of both
sets (original values and normalized keys), I can compare the two when
evaluating if normalization should be aborted. This is by far the most
important consideration.

This causes the optimization to be applied when sorting millions of
tuples with only a tiny number of distinct values (like, 4 or 5),
without making bad cases that we fail to abort in a timely manner any
more likely. This is still significantly profitable - over 90% faster
in one test, because the optimistic memcmp() still allows us to avoid
any strcoll() calls. It looks about the same as using the "C"
collation. Not quite the huge boost we can see, but still well
worthwhile.

In general it seems well principled to have the "should I abort
normalization?" algorithm mostly weigh how effective a proxy for full
key cardinality normalized key cardinality is. If it is a good proxy
then nothing else matters. If it's not a very good proxy, that can
only be because there are many differences beyond the first 8 bytes.
Only then will we weigh the total number of distinct normalized keys,
and as the effectiveness of normalized key cardinality as a proxy for
overall cardinality falls, our requirements for the overall number of
distinct normalized keys shoots up rapidly.

--
Peter Geoghegan

On 28 Jul 2014, at 5:23 PM, Peter Geoghegan wrote:
> On Mon, Jul 28, 2014 at 5:14 PM, Wim Lewis <wiml(at)omnigroup(dot)com> wrote:
>> A quick glance at OSX's strxfrm() suggests they're using an implementation of strxfrm() from FreeBSD. You can find the source here:
>>
>> http://www.opensource.apple.com/source/Libc/Libc-997.90.3/string/FreeBSD/strxfrm.c
>>
>> (and a really quick glance at the contents of libc on OSX 10.9 reinforces this--- I don't see any calls into their CoreFoundation unicode string APIs.)
>
> Something isn't quite accounted for, then. The FreeBSD behavior is to
> append the primary weights only. That makes their returned blobs
> smaller than those you'll see on Linux, but also appears to imply that
> their implementation is substandard (The PostgreSQL port uses ICU on
> FreeBSD for a reason, I suppose). But FreeBSD did not add extra,
> redundant "header bytes" right in the primary level when I tested it,
> but I'm told Mac OS X does.

I don't think OSX actually does. From a look at the source and a simple test program, OSX's strxfrm represents its output as a series of 24-bit weights, each one encoded into four bytes. Multiple "levels" of weights are separated by a weight of 0 (which is encoded as the four bytes "0000").

Robert Haas' message in this thread on 7 April is the first mention of a header, but his examples from 12 June don't really demonstrate a header--- they're completely consistent with the description above and the published source code.

OSX's strxfrm output is very space-inefficient, especially for Latin text, where none of the weights seem to be greater than 2^12, meaning that half of the bytes in any output are always going to be 0x30. (Testing with, e.g., Hangul characters I find some weights that use more of the space.) But as far as I can tell it's not completely crazy. :)

What this means is that on OSX, comparing the first 8 bytes of strxfrm output will end up comparing the primary weights of the first two characters in the original string. Which is the same conclusion Robert Haas came to earlier, modulo the "header bytes" interpretation.

On Sun, Jul 27, 2014 at 3:00 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Thu, Jun 12, 2014 at 2:09 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>> Thanks for looking into this.
>
> Is anyone going to look at this?

I'm concerned by the licensing information in hyperloglog.c, which reads:

+ * Portions Copyright (c) 2014, PostgreSQL Global Development Group
+ *
+ * Based on Hideaki Ohno's C++ implementation.

There is no commentary whatever on the license applicable to that
code. It appears to be the MIT license:

https://github.com/hideo55/cpp-HyperLogLog

I don't think we should commit anything that's not clearly under the
PostgreSQL license.

Heikki previously made quite firmly the point that you shouldn't blend
the addition of sortsupport logic in general with the poor man's key
optimization in particular; they should be separate patches. He's
right.

Some other concerns:

1. As I think I mentioned before, I think the term "poor man's key" is
just terrible. It conveys, at least to me, no useful information
about what is really being done. If you called it, say,
"strxfrm-prefix comparison", it would be only a few more letters but a
whole lot more informative to future readers of the code.

2. The need to modify analyze.c and nodeMergeAppend.c to disable this
optimization seems odd, and the comments are uninformative, saying
only that it "isn't feasible", but not why. If it were only analyze.c
I might expect that it required some kind of transaction state that
isn't present there, but that doesn't explain the merge-append case.

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

On Wed, Jul 30, 2014 at 10:52 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> I don't think we should commit anything that's not clearly under the
> PostgreSQL license.

I thought that we were comfortable with using MIT licensed code. But,
come to think of it I don't know what our exact policy is. Wikipedia
says "The Simplified BSD license used by FreeBSD is essentially
identical[citation needed][discuss] to the MIT License, as it contains
neither an advertising clause, nor a prohibition on promotional use of
the copyright holder's name". There are plenty of suitably licensed
hyperLogLog implementations in any case, and many are similar. Some
direction here would be useful, since I'm not an expert on licensing.

> Heikki previously made quite firmly the point that you shouldn't blend
> the addition of sortsupport logic in general with the poor man's key
> optimization in particular; they should be separate patches. He's
> right.

Ordinarily, I'd agree with this. But the fact is that there was an
extensive discussion of that patch. We both know quite a lot about it,
because you wrote it and I reviewed it [1]. What more is there to
learn about it? It's not very controversial. It provides a text sort
support routine that consistently wins by removing avoidable overhead.
For the strcoll() case, you put the improvement at 7%. It clearly
cannot regress anything. It's easy to reason about. It's a fine patch.
We had a silly disagreement about it, but I would almost have been
willing to commit it there and then (although Windows was still broken
with that patch, something I've only just fixed, AFAIK).

This patch may cause regressions. They may not be that bad, but they
need to be characterized and avoided. It can also make many
representative cases more than 3 times faster (an improvement in
excess of 200%). Even low cardinality cases (e.g sorting a list of
cities in the world with more than a thousand inhabitants by country)
can be up to 150% faster. That's a very strong improvement, and the
lack of this kind of facility surely accounts for why other systems
are said to sort text so much more efficiently than Postgres
(something we discussed privately years ago). But, regressions are
bad. Plus, I freely admit that this whole idea is ugly as sin. That's
the only thing to discuss, AFAICT. We know that the best case
performance is almost entirely attributable to the normalized key
stuff.

> Some other concerns:
>
> 1. As I think I mentioned before, I think the term "poor man's key" is
> just terrible. It conveys, at least to me, no useful information
> about what is really being done. If you called it, say,
> "strxfrm-prefix comparison", it would be only a few more letters but a
> whole lot more informative to future readers of the code.

I don't have a problem with changing the name. But the name that you
propose is all about text. This patch is intended to add an extensible
infrastructure (a new part of sort support), plus one client of that
more complete extensible infrastructure (sort support for text). I
think there's a good chance that it could work well for another type
too, like numeric, if we could come up with a good system for encoding
numeric normalized keys, and if we can similarly get over the fact
that there is going to be a minority of cases that won't be helped at
all. That's a whole other discussion, though, and text is clearly the
really compelling case.

Do you have another suggestion?

> 2. The need to modify analyze.c and nodeMergeAppend.c to disable this
> optimization seems odd, and the comments are uninformative, saying
> only that it "isn't feasible", but not why. If it were only analyze.c
> I might expect that it required some kind of transaction state that
> isn't present there, but that doesn't explain the merge-append case.

The reason is that there is no convenient way to inject a conversion
routine. A binary heap is calling heap_compare_slots(), which is where
comparisons occur, so it isn't really sorting at all. It would be
ugly, and probably even counter-productive to do normalization just in
time, as tuples are pulled up. In general I assume that it's only
useful to do a full normalization pass before sorting (preferably at a
convenient juncture like copytup_heap()). Note that we still elide the
fmgr trampoline, so only the additional normalization optimization
fails to apply.

I should add that there is one other case where we arbitrarily don't
use the additional optimization that doesn't actually make any sense.
Within nodeAgg.c, "We use a plain Datum sorter when there's a single
input column; otherwise sort the full tuple". And thus, the
optimization may not be used there more or less by accident.
tuplesort_putdatum() needs to be taught about the new optimization
too, I think.

I feel it should be possible for both the Datum and Heap sort cases to
use the new optimization (since they can always use sort support)
wherever they can afford to make that normalization pass (they usually
can, since copytup* is usually passed through). Eventually, I think
we'll want to extend sort support to work with btree index builds.

Please don't review the abort logic until I finish producing a new
revision. It won't be long. I've come up with something appreciably
better [2].

[1] http://www.postgresql.org/message-id/CA+Tgmoa8by24gd+YbuPX=5gSGmN0w5sGiPzWwq7_8iS26vL5CQ@mail.gmail.com

[2] http://www.postgresql.org/message-id/CAM3SWZRYkTbOtVsun2R1j95XR5GnrvM+Zbvz+RxHLq0CLz41hA@mail.gmail.com
--
Peter Geoghegan

On Wed, Jul 30, 2014 at 3:04 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> I don't have a problem with changing the name. But the name that you
> propose is all about text. This patch is intended to add an extensible
> infrastructure (a new part of sort support), plus one client of that
> more complete extensible infrastructure (sort support for text). I
> think there's a good chance that it could work well for another type
> too, like numeric, if we could come up with a good system for encoding
> numeric normalized keys, and if we can similarly get over the fact
> that there is going to be a minority of cases that won't be helped at
> all. That's a whole other discussion, though, and text is clearly the
> really compelling case.
>
> Do you have another suggestion?

How about "proxy sort keys"? It's suggestive of a format that can be
relied on to faithfully represent the original key. But, like any
proxy, it's a substitute, and by definition a substitute is never as
authoritative as the original value. As such, the original value may
need to be consulted when the proxy sort key doesn't have enough
information to give a conclusive answer, which hopefully doesn't
happen often. Like any good proxy, proxy sort keys know enough to know
when they cannot faithfully represent what the original value would
say. In practice proxy sort keys are almost always themselves
pass-by-value, while serving to proxy a pass by reference type, but
this isn't a formal requirement. Encoding strategies don't necessarily
have anything to do with strxfrm(). That's just how text's default
opclass happens to do it.

--
Peter Geoghegan

On Wed, Jul 30, 2014 at 3:04 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> I feel it should be possible for both the Datum and Heap sort cases to
> use the new optimization (since they can always use sort support)
> wherever they can afford to make that normalization pass (they usually
> can, since copytup* is usually passed through). Eventually, I think
> we'll want to extend sort support to work with btree index builds.

Actually, scratch that; I think it should be possible to have things
like aggregates with a single ORDER BY expression use the
normalization optimization where available (a slightly less specific
statement than the above). I do not in fact think we should make this
work for tuplesort_begin_datum(). The single column case ORDER BY
aggregate happens to use a datum representation within tuplesort,
whereas the multi input column case uses heap tuples (and
tuplesort_begin_heap(), etc).

What I mean is that I think the best way to accomplish what we really
want here is probably to make the single column case artificially do
the same thing as the multi-column case where we know there is a sort
support routine with normalization support. That has to be a superior
approach to jury-rigging tuplesort to differentiate between normalized
keys and an original representation where tuplesort_getdatum() is
consulted. It's a bit ugly that datum sorts will then support sort
support, but only when this new infrastructure is unused. I see no
better way.

Now, to figure out a reasonable way to have nodeAgg.c ask "does this
sort operator have a real sort support function that happens to use
the new normalization capability?" before calling either
tuplesort_begin_heap() or tuplesort_begin_datum()...

--
Peter Geoghegan

On Wed, Jul 30, 2014 at 7:17 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Wed, Jul 30, 2014 at 3:04 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>> I don't have a problem with changing the name. But the name that you
>> propose is all about text. This patch is intended to add an extensible
>> infrastructure (a new part of sort support), plus one client of that
>> more complete extensible infrastructure (sort support for text). I
>> think there's a good chance that it could work well for another type
>> too, like numeric, if we could come up with a good system for encoding
>> numeric normalized keys, and if we can similarly get over the fact
>> that there is going to be a minority of cases that won't be helped at
>> all. That's a whole other discussion, though, and text is clearly the
>> really compelling case.
>>
>> Do you have another suggestion?
>
> How about "proxy sort keys"? It's suggestive of a format that can be
> relied on to faithfully represent the original key. But, like any
> proxy, it's a substitute, and by definition a substitute is never as
> authoritative as the original value. As such, the original value may
> need to be consulted when the proxy sort key doesn't have enough
> information to give a conclusive answer, which hopefully doesn't
> happen often. Like any good proxy, proxy sort keys know enough to know
> when they cannot faithfully represent what the original value would
> say. In practice proxy sort keys are almost always themselves
> pass-by-value, while serving to proxy a pass by reference type, but
> this isn't a formal requirement. Encoding strategies don't necessarily
> have anything to do with strxfrm(). That's just how text's default
> opclass happens to do it.

I certainly like that better than poor-man; but proxy, to me, fails to
convey inexactness. Perhaps we can work that idea in somehow. Or
maybe "pre"-something, to indicate that we do this before comparing
the regular key, in the hopes of not needing to.

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

On Thu, Jul 31, 2014 at 11:41 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> I certainly like that better than poor-man; but proxy, to me, fails to
> convey inexactness. Perhaps we can work that idea in somehow. Or
> maybe "pre"-something, to indicate that we do this before comparing
> the regular key, in the hopes of not needing to.

Well, these normalized keys are sometimes sufficient to give correct
answers, or are sufficient to determine that that isn't possible with
just their representation. That is pretty exact.

How about "delegate key"? That's a similar term to proxy key, but is
more strongly suggestive of the idea that these keys are in some sense
inferior to original keys.
--
Peter Geoghegan

On Thu, Jul 31, 2014 at 9:41 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> I certainly like that better than poor-man; but proxy, to me, fails to
> convey inexactness.

Maybe "abbreviated", "abridged", "minified"?

Regards,
Marti

On Thu, Jul 31, 2014 at 3:14 PM, Marti Raudsepp <marti(at)juffo(dot)org> wrote:
> On Thu, Jul 31, 2014 at 9:41 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> I certainly like that better than poor-man; but proxy, to me, fails to
>> convey inexactness.
>
> Maybe "abbreviated", "abridged", "minified"?

Yeah, something like that would work for me. I like abbreviated; that
seems very descriptive.

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

On Thu, Jul 31, 2014 at 8:14 PM, Marti Raudsepp <marti(at)juffo(dot)org> wrote:
> On Thu, Jul 31, 2014 at 9:41 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> I certainly like that better than poor-man; but proxy, to me, fails to
>> convey inexactness.
>
> Maybe "abbreviated", "abridged", "minified"?

Surrogate?

Let the bike shedding begin!

--
greg

On Thu, Jul 31, 2014 at 12:52 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> Maybe "abbreviated", "abridged", "minified"?
>
> Yeah, something like that would work for me. I like abbreviated; that
> seems very descriptive.

Abbreviated it is.

--
Peter Geoghegan

On Thu, Jul 31, 2014 at 1:12 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> Abbreviated it is.

Attached revision uses new terminology. I have abandoned configure
tests entirely, preferring to explicitly discriminate against Mac OS X
(Darwin) as a platform with a known odd locale implementation, just
like pg_get_encoding_from_locale() does. Since Robert did not give a
reason for discussing the basic fmgr-elision patch despite having
already discussed it a couple of years ago, I have not split the patch
into two (if I did, the first patch would be virtually identical to
Robert's 2012 patch). I hope that's okay. I am willing to revisit this
question if Robert feels that something is uncertain about the costs
and benefits of a basic fmgr-eliding sort support for text.

There are still some open items:

* I have left the licensing question unresolved. There is plenty we
can do about this, and if necessary we can ask the original author to
changed his license from the MIT license to the PostgreSQL license.
AFAICT, the BSD license is *more* restrictive than the MIT license,
and the PostgreSQL license is identical. The wording is almost
identical. I don't see the concern. If the PostgreSQL license had the
“non-endorsement clause” of the New BSD license, or alternatively if
the MIT license had a similar clause that the PostgreSQL licensed
lacked, that would be a substantive and appreciable difference. That
isn't the case.

* I have not made aggregates use the optimization where they currently
accidentally don't due to using datum tuplesort. I can artificially
force them to use heap tuplesort where that's likely to help [1].
Let's defer this question until we have an abort algorithm that seems
reasonable. There is a FIXME item.

Improvements in full:

* New terminology ("Abbreviated keys").

* Better explanations for why we don't use the additional optimization
of abbreviated keys where we're using sort support, in analyze.c and
nodeMergeAppend.c.

* Better handling of NULLs.

* Never use the optimization with bounded heap sorts.

* Better abort strategy, that centers on the idea of measuring full
key cardinality, and abbreviated key cardinality, and weighing how
good a proxy the former is for the latter. This is heavily weighed
when deciding if we should abort normalization as tuples are copied.
Exact details are explained within bttext_abort(). As already
mentioned, this can allow us to use the optimization when we're
sorting a million tuples with only five distinct values. This will
still win decisively, but it's obviously impossible to make work while
only considering abbreviated key cardinality. Determining cardinality
of both abbreviated keys and full keys appears to have very low
overhead, and is exactly what we ought to care about, so that's what
we do. While there is still some magic to the algorithm's inputs, my
sense is that I'm much closer to characterizing the break-even point
than before.

I also attach a second patch, which adds additional debug
instrumentation, and is intended to be applied on top of the real
patch to help with review. Run Postgres with DEBUG1 output when it's
applied. With the patch applied, the setting backslash_quote also
controls whether or not the optimization is used. So with the debug
instrumentation patch applied:

"backslash_quote = on" - use optimization, but never abort

"backslash_quote = off" - Never use optimization - set up shim (just
like the win32 UTF-8 case). Equivalent to master's behavior.

"backslash_quote = safe_encoding" - Use optimization, but actually
abort if it doesn't work out, the behavior that is always seen without
instrumentation. This is useful for testing the overhead of
considering the optimization in cases where it didn't work out (i.e.
it's useful to compare this with "backslash_quote = off").

I've found it useful to experiment with real-world data with the
optimization dynamically enabled and disabled.

Thoughts?

[1] http://www.postgresql.org/message-id/CAM3SWZSf0Ftxy8QHGAKJh=S80vD2SBx83zkEzuJyZ6R=pTy5xA@mail.gmail.com
--
Peter Geoghegan

On Fri, Aug 01, 2014 at 04:00:11PM -0700, Peter Geoghegan wrote:
> Since Robert did not give a
> reason for discussing the basic fmgr-elision patch despite having
> already discussed it a couple of years ago, I have not split the patch
> into two (if I did, the first patch would be virtually identical to
> Robert's 2012 patch). I hope that's okay. I am willing to revisit this
> question if Robert feels that something is uncertain about the costs
> and benefits of a basic fmgr-eliding sort support for text.

Robert, Heikki and maybe Alvaro requested and/or explained this split back in
April. The fact that the would-be first patch was discussed and rejected in
the past does not counter that request. (I voted against Robert's 2012 patch.
My opposition was mild even then, and the patch now being a stepping stone to
a more-compelling benefit certainly tips the scale.) Given that the effect of
that decision is a moderate procedural change only, even if the request were
wrong, why continue debating it?

> There are still some open items:
>
> * I have left the licensing question unresolved. There is plenty we
> can do about this, and if necessary we can ask the original author to
> changed his license from the MIT license to the PostgreSQL license.
> AFAICT, the BSD license is *more* restrictive than the MIT license,
> and the PostgreSQL license is identical. The wording is almost
> identical. I don't see the concern. If the PostgreSQL license had the
> non-endorsement clause of the New BSD license, or alternatively if
> the MIT license had a similar clause that the PostgreSQL licensed
> lacked, that would be a substantive and appreciable difference. That
> isn't the case.

It's fine to incorporate MIT-licensed code; we have many cases of copying
more-liberally-licensed code into our tree. However, it's important to have
long-term clarity on the upstream license terms. This is insufficient:

> + /*-------------------------------------------------------------------------
> + *
> + * hyperloglog.c
> + * HyperLogLog cardinality estimator
> + *
> + * Portions Copyright (c) 2014, PostgreSQL Global Development Group
> + *
> + * Based on Hideaki Ohno's C++ implementation. This is probably not ideally
> + * suited to estimating the cardinality of very large sets; in particular, we

Usually, the foreign file had a copyright/license notice, and we prepend the
PostgreSQL notice. See src/port/fls.c for a trivial example.

Thanks,
nm

--
Noah Misch
EnterpriseDB http://www.enterprisedb.com

On Fri, Aug 1, 2014 at 8:57 PM, Noah Misch <noah(at)leadboat(dot)com> wrote:
> Robert, Heikki and maybe Alvaro requested and/or explained this split back in
> April. The fact that the would-be first patch was discussed and rejected in
> the past does not counter that request. (I voted against Robert's 2012 patch.
> My opposition was mild even then, and the patch now being a stepping stone to
> a more-compelling benefit certainly tips the scale.) Given that the effect of
> that decision is a moderate procedural change only, even if the request were
> wrong, why continue debating it?

Heikki asked for it, and Robert repeated the request in the past few
days. I am not debating it. I merely don't understand the nature of
the request. I think it's virtually a foregone conclusion that there
should be fmgr elision for text, with very few decisions to be made on
the details of how that would work. The rest of what I have here is
trickier, and is something that must be discussed. Even the
improvement of ~7% that fmgr-elision offers is valuable for such a
common operation.

I don't want to dredge up the details of the 2012 thread, but since
you mention it the fact that the patch was not committed centered on a
silly disagreement on a very fine point, and nothing more. It was
*not* rejected, and my sense at the time was that it was very close to
being committed. I was fairly confident that everyone understood
things around the 2012 patch that way, and I sought clarity on that
point. It's a totally non-surprising and easy to reason about patch.
Clearly at least one person had some reservations about the basic idea
at the time, and it was worth asking what the concern was before
splitting the patch. It is easy to split the patch, but easier still
to answer my question.

> It's fine to incorporate MIT-licensed code; we have many cases of copying
> more-liberally-licensed code into our tree. However, it's important to have
> long-term clarity on the upstream license terms. This is insufficient:
>
>> + /*-------------------------------------------------------------------------
>> + *
>> + * hyperloglog.c
>> + * HyperLogLog cardinality estimator
>> + *
>> + * Portions Copyright (c) 2014, PostgreSQL Global Development Group
>> + *
>> + * Based on Hideaki Ohno's C++ implementation. This is probably not ideally
>> + * suited to estimating the cardinality of very large sets; in particular, we
>
> Usually, the foreign file had a copyright/license notice, and we prepend the
> PostgreSQL notice. See src/port/fls.c for a trivial example.

I will be more careful about this in the future.

--
Peter Geoghegan

On 08/02/2014 08:16 AM, Peter Geoghegan wrote:
> On Fri, Aug 1, 2014 at 8:57 PM, Noah Misch <noah(at)leadboat(dot)com> wrote:
>> Robert, Heikki and maybe Alvaro requested and/or explained this split back in
>> April. The fact that the would-be first patch was discussed and rejected in
>> the past does not counter that request. (I voted against Robert's 2012 patch.
>> My opposition was mild even then, and the patch now being a stepping stone to
>> a more-compelling benefit certainly tips the scale.) Given that the effect of
>> that decision is a moderate procedural change only, even if the request were
>> wrong, why continue debating it?
>
> Heikki asked for it, and Robert repeated the request in the past few
> days. I am not debating it.

Great, I'll wait for the patch.

> I merely don't understand the nature of the request.

Do you mean:

a) you don't understand what the patch should look like? or
b) you don't understand why it's been requested?

If a), I admit I don't remember the details of this patch or patches
very well either, but looking back at the archives here:
http://www.postgresql.org/message-id/CAM3SWZQVnuomFBWNHOyRQ8t+nVJp+3=e58jvvx_A9Y04QmHzrA@mail.gmail.com,
I think you had a pretty solid idea of how the split should look like.
So, please do that, i.e. post the patch that Robert did 2 years ago that
gave the 7% speedup, rebased over master. I don't recall the details of
that patch, so please explain briefly what it does, as if it was
submitted for the first time.

If b), see Noah's reply above. Hate to be blunt, but the nature of the
request is that you're not going to get anywhere with further debate,
without splitting the patch.

> I don't want to dredge up the details of the 2012 thread, but since
> you mention it the fact that the patch was not committed centered on a
> silly disagreement on a very fine point, and nothing more. It was
> *not* rejected, and my sense at the time was that it was very close to
> being committed. I was fairly confident that everyone understood
> things around the 2012 patch that way, and I sought clarity on that
> point. It's a totally non-surprising and easy to reason about patch.
> Clearly at least one person had some reservations about the basic idea
> at the time, and it was worth asking what the concern was before
> splitting the patch. It is easy to split the patch, but easier still
> to answer my question.

I didn't understand what that question is. Please just post the split
patches.
- Heikki

On Sat, Aug 2, 2014 at 1:15 AM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> Great, I'll wait for the patch.

I'll post something over the weekend.

> Do you mean:
>
> a) you don't understand what the patch should look like? or
> b) you don't understand why it's been requested?
>
> If a), I admit I don't remember the details of this patch or patches very
> well either, but looking back at the archives here:
> http://www.postgresql.org/message-id/CAM3SWZQVnuomFBWNHOyRQ8t+nVJp+3=e58jvvx_A9Y04QmHzrA@mail.gmail.com,
> I think you had a pretty solid idea of how the split should look like. So,
> please do that, i.e. post the patch that Robert did 2 years ago that gave
> the 7% speedup, rebased over master. I don't recall the details of that
> patch, so please explain briefly what it does, as if it was submitted for
> the first time.

Robert's 2012 patch just elides the fmgr overhead, like any sort
support routine, so you just go through a function pointer and not a
function pointer to a shim function with a fmgr call. It ends up
having the sort support routine do a dew things once that might
otherwise have to take place once per comparison. It's more or less a
basic sort support routine, and nothing more.

My question is: What is the reason for splitting the patch? Is it that
you or Robert don't agree with my assessment of the 2012 patch, and
you think there might be some subtlety to it that I'm not aware of? Do
you just want to do this incrementally because it's easier to digest
that way? This is a pertinent question. You said something about
understanding where the benefits come from here, which is fair, but my
point was that I actually do understand that the benefits clearly
mostly come from the new abbreviated key idea. As the author of the
2012 patch, I imagine that Robert must be pretty confident that's the
case too, but I don't want to presume that.

As I said, I don't have a problem with breaking out the patch. I am
not trying to artificially link the two. It just isn't obvious to me
that you're aware that most of the benefit, and indeed all of the
potential for regressions clearly comes from this abbreviated key
idea. So sure, we can break out the patch and commit the first part
fairly easily, almost entirely on the basis of 2012 discussion. What
you may have missed here is that the 2012 patch wasn't committed for
reasons entirely unrelated to the merit of the idea. If we were to
commit essentially the same 2012 patch, that is a very straightforward
matter, and is only a small fraction of our work here. The 2012 patch
really should have been committed in 2012.

--
Peter Geoghegan

On Sat, Aug 2, 2014 at 2:45 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> I'll post something over the weekend.

Attached is a cumulative pair of patches generated using
git-format-patch. I refer anyone who wants to know how the two parts
fit together to the commit messages of each patch. In passing, I have
added a reference to the MIT License as outlined by Noah.

--
Peter Geoghegan

Consider the "cities" table I've played around with throughout the
development of this patch:

postgres=# select tablename, attname, n_distinct, correlation from
pg_stats where attname in ('country', 'province', 'city');
tablename | attname | n_distinct | correlation
-----------+----------+------------+-------------
cities | city | -0.666628 | -0.0169657
cities | province | 1958 | 0.0776529
cities | country | 206 | 1
(3 rows)

Consider this query:

select * from (select * from cities order by country, province, city
offset 1000000) i;

With master, this consistently takes about 6.4 seconds on my laptop.
With the patch I posted most recently, it takes about 3.5 seconds. But
if I change this code:

+ if (ssup->position == sortKeyTiebreak && len1 == len2)
+ {

To this:

+ if (len1 == len2)
+ {

Then my patch takes about 1.3 seconds to execute the query, since now
we're always optimistic about the prospect of getting away with a
cheap memcmp() when the lengths match, avoiding copying and strcoll()
overhead entirely. "province" has a relatively low number of distinct
values - about 1,958, in a table of 317,102 cities - so clearly that
optimism is justified in this instance.

This does seem to suggest that there is something to be said for being
optimistic about yielding equality not just when performing a leading
attribute abbreviated key tie-breaker. Maybe the executor could pass a
per-attribute n_distinct hint to tuplesort, which would pass that on
to our sortsupport routine. Of course, if there was a low cardinality
attribute with text strings all of equal length, and/or if there
wasn't a correlation between "country" and "province" a lot of the
time those opportunistic memcmp()s could go to waste. But that might
be just fine, especially if we only did this for moderately short
strings (say less than 64 bytes). I don't have a good sense of the
costs yet, but the hashing that HyperLogLog requires in my patch
appears to be almost free, since it occurs at a time when we're
already bottlenecked on memory bandwidth, and is performed on memory
that needed to be manipulated at that juncture anyway. It wouldn't
surprise me if this general optimism about a simple memcmp() working
out had a very acceptable worst case. It might even be practically
free to be totally wrong about equality being likely, and if we have
nothing to lose and everything to gain, clearly we should proceed. I'm
aware of cases where it makes probabilistic sense to waste compute
bandwidth to gain memory bandwidth. It's something I've seen crop up a
number of times in various papers.

--
Peter Geoghegan

On Sat, Aug 2, 2014 at 6:58 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> On Sat, Aug 2, 2014 at 2:45 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>> I'll post something over the weekend.
>
> Attached is a cumulative pair of patches generated using
> git-format-patch. I refer anyone who wants to know how the two parts
> fit together to the commit messages of each patch. In passing, I have
> added a reference to the MIT License as outlined by Noah.

OK, I have taken a look at patch 1. You write:

+ * As a general principle, operator classes with a cataloged sort support
+ * function are expected to provide sane sort support state, including a
+ * function pointer comparator. Rather than revising that principle, just
+ * setup a shim for the WIN32 UTF-8 and non-"C" collation special case here.

...but I'm wondering what underlies that decision. I would
understand the decision to go that way if it simplified things
elsewhere, but in fact it seems that's what underlies the addition of
ssup_operator to SortSupportData, which in turn requires a number of
changes elsewhere. The upshot of those changes is that it makes it
possible to write bttext_inject_shim, but AFAICS that's just
recapitulating what get_sort_function_for_ordering_op and
PrepareSortSupportFromOrderingOp are already doing. Any material
change to either of those functions will have to be reflected in
bttext_inject_shim; and if some opclass other than text wants to
provide a sortsupport shim that supplies a comparator only sometimes,
it will need its own copy of the logic.

So I think it's better to just change the sortsupport contract so that
filling in the comparator is optional. Patch for that attached.
Objections?

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

On Tue, Aug 5, 2014 at 12:03 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> ...but I'm wondering what underlies that decision. I would
> understand the decision to go that way if it simplified things
> elsewhere, but in fact it seems that's what underlies the addition of
> ssup_operator to SortSupportData, which in turn requires a number of
> changes elsewhere.

The changes aren't too invasive. There is exactly one place where it
isn't a trivial matter of storing the operator that was already
available:

+ /* Original operator must be provided */
+ clause->ssup.ssup_operator = get_opfamily_member(opfamily,
+
op_lefttype,
+
op_righttype,
+
opstrategy);

> So I think it's better to just change the sortsupport contract so that
> filling in the comparator is optional. Patch for that attached.
> Objections?

I'd have preferred to maintain the obligation for some sane
sortsupport state to be provided. It's not as if I feel too strongly
about it, though.

You attached "git diff --stat" output, and not an actual patch. Please re-send.

--
Peter Geoghegan