Re: Review [was Re: MD5 aggregate]

On 21 June 2013 21:04, David Fetter <david@fetter.org> wrote:
> On Fri, Jun 21, 2013 at 10:48:35AM -0700, David Fetter wrote:
>> On Mon, Jun 17, 2013 at 11:34:52AM +0100, Dean Rasheed wrote:
>> > On 15 June 2013 10:22, Dean Rasheed <dean.a.rasheed@gmail.com> wrote:
>> > > There seem to be 2 separate directions that this could go, which
>> > > really meet different requirements:
>> > >
>> > > 1). Produce an unordered sum for SQL to compare 2 tables regardless of
>> > > the order in which they are scanned. A possible approach to this might
>> > > be something like an aggregate
>> > >
>> > > md5_total(text/bytea) returns text
>> > >
>> > > that returns the sum of the md5 values of each input value, treating
>> > > each md5 value as an unsigned 128-bit integer, and then producing the
>> > > hexadecimal representation of the final sum. This should out-perform a
>> > > solution based on numeric addition, and in typical cases, the result
>> > > wouldn't be much longer than a regular md5 sum, and so would be easy
>> > > to eyeball for differences.
>> > >
>> >
>> > I've been playing around with the idea of an aggregate that computes
>> > the sum of the md5 hashes of each of its inputs, which I've called
>> > md5_total() for now, although I'm not particularly wedded to that
>> > name. Comparing it with md5_agg() on a 100M row table (see attached
>> > test script) produces interesting results:
>> >
>> > SELECT md5_agg(foo.*::text)
>> >   FROM (SELECT * FROM foo ORDER BY id) foo;
>> >
>> >  50bc42127fb9b028c9708248f835ed8f
>> >
>> > Time: 92960.021 ms
>> >
>> > SELECT md5_total(foo.*::text) FROM foo;
>> >
>> >  02faea7fafee4d253fc94cfae031afc43c03479c
>> >
>> > Time: 96190.343 ms
>> >
>> > Unlike md5_agg(), it is no longer a true MD5 sum (for one thing, its
>> > result is longer) but it seems like it would be very useful for
>> > quickly comparing data in SQL, since its value is not dependent on the
>> > row-order making it easier to use and better performing if there is no
>> > usable index for ordering.
>> >
>> > Note, however, that if there is an index that can be used for
>> > ordering, the performance is not necessarily better than md5_agg(), as
>> > this example shows. There is a small additional overhead per row for
>> > initialising the MD5 sums, and adding the results to the total, but I
>> > think the biggest factor is that md5_total() is processing more data.
>> > The reason is that MD5 works on 64-byte blocks, so the total amount of
>> > data going through the core MD5 algorithm is each row's size is
>> > rounded up to a multiple of 64. In this simple case it ends up
>> > processing around 1.5 times as much data:
>> >
>> > SELECT sum(length(foo.*::text)) AS md5_agg,
>> >        sum(((length(foo.*::text)+63)/64)*64) AS md5_total FROM foo;
>> >
>> >   md5_agg   |  md5_total
>> > ------------+-------------
>> >  8103815438 | 12799909248
>> >
>> > although of course that overhead won't be as large on wider tables,
>> > and even in this case the overall performance is still on a par with
>> > md5_agg().
>> >
>> > ISTM that both aggregates are potentially useful in different
>> > situations. I would probably typically use md5_total() because of its
>> > simplicity/order-independence and consistent performance, but
>> > md5_agg() might also be useful when comparing with external data.
>> >
>> > Regards,
>> > Dean
>
>> Performance review (skills needed: ability to time performance)
>>
>>     Does the patch slow down simple tests?
>>
>>         Yes.  For an MD5 checksum of some random data, here are
>>         results from master:
>>
>>             shackle@postgres:5493=# WITH t1 AS (SELECT string_agg(chr(floor(255*random()+1)::int),'') AS a FROM
generate_series(1,10000)),
>>             postgres-# t2 AS (SELECT a FROM t1 CROSS JOIN generate_series(1,10000))
>>             postgres-# select md5(a::text) FROM t2;
>>             shackle@postgres:5493=# \timing
>>             Timing is on.
>>             shackle@postgres:5493=# \g
>>             Time: 955.393 ms
>>             shackle@postgres:5493=# \g
>>             Time: 950.909 ms
>>             shackle@postgres:5493=# \g
>>             Time: 947.955 ms
>>             shackle@postgres:5493=# \g
>>             Time: 946.193 ms
>>             shackle@postgres:5493=# \g
>>             Time: 950.591 ms
>>             shackle@postgres:5493=# \g
>>             Time: 952.346 ms
>>             shackle@postgres:5493=# \g
>>             Time: 948.623 ms
>>             shackle@postgres:5493=# \g
>>             Time: 939.819 ms
>>
>>         and here from master + the patch:
>>
>>             WITH t1 AS (SELECT string_agg(chr(floor(255*random()+1)::int),'') AS a FROM generate_series(1,10000)),
>>             t2 AS (SELECT a FROM t1 CROSS JOIN generate_series(1,10000))
>>             select md5(a::text) FROM t2;
>>             Time: 1129.178 ms
>>             shackle@postgres:5494=# \g
>>             Time: 1134.013 ms
>>             shackle@postgres:5494=# \g
>>             Time: 1124.387 ms
>>             shackle@postgres:5494=# \g
>>             Time: 1119.733 ms
>>             shackle@postgres:5494=# \g
>>             Time: 1104.906 ms
>>             shackle@postgres:5494=# \g
>>             Time: 1137.055 ms
>>             shackle@postgres:5494=# \g
>>             Time: 1128.977 ms
>>             shackle@postgres:5494=# \g
>>             Time: 1143.619 ms
>>
>>             Avg, StddevPopulation without patch: 948.97 ms, 4.353 ms
>>             Avg, StddevPopulation with patch: 1127.73 ms, 11.06 ms
>
> The above was with -O0.  Please find below with vanilla ./configure (-O2):
>
> Master:
> shackle@postgres:5493=# WITH t1 AS (SELECT
> string_agg(chr(floor(255*random()+1)::int),'') AS a FROM
> generate_series(1,10000)),
> t2 AS (SELECT a FROM t1 CROSS JOIN generate_series(1,10000))
> select md5(a::text) FROM t2;
> Time: 469.101 ms
> shackle@postgres:5493=# \g
> Time: 464.122 ms
> shackle@postgres:5493=# \g
> Time: 461.411 ms
> shackle@postgres:5493=# \g
> Time: 458.222 ms
> shackle@postgres:5493=# \g
> Time: 463.616 ms
> shackle@postgres:5493=# \g
> Time: 463.983 ms
> shackle@postgres:5493=# \g
> Time: 453.770 ms
> shackle@postgres:5493=# \g
> Time: 456.729 ms
>
> MD5:
> WITH t1 AS (SELECT string_agg(chr(floor(255*random()+1)::int),'') AS a
> FROM generate_series(1,10000)),
> t2 AS (SELECT a FROM t1 CROSS JOIN generate_series(1,10000))
> select md5(a::text) FROM t2;
> Time: 436.862 ms
> shackle@postgres:5494=# \t
> Showing only tuples.
> shackle@postgres:5494=# \t
> Tuples only is off.
> shackle@postgres:5494=# \g
> Time: 438.686 ms
> shackle@postgres:5494=# \g
> Time: 443.789 ms
> shackle@postgres:5494=# \g
> Time: 452.522 ms
> shackle@postgres:5494=# \g
> Time: 447.824 ms
> shackle@postgres:5494=# \g
> Time: 448.547 ms
> shackle@postgres:5494=# \g
> Time: 446.901 ms
> shackle@postgres:5494=# \g
> Time: 448.537 ms
>
> Average, stddev population for master: 461.36925, 4.5883631545
> Average, stddev population for md5:    445.4585,  4.9892286729
>
> so slightly faster on MD5, as expected.
>
> Cheers,
> David.

Thanks for the review and testing!

Regards,
Dean