Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-09-02 Thread Heikki Linnakangas

On 08/03/2016 08:47 PM, Andrey Borodin wrote:

1. Currenlty overflow is carried every  addition. I suggest that
it is possibe to do it only every (INT32_MAX - INT32_MAX / NBASE) /
(NBASE - 1) addition. Please note that with this overflow count it
will be neccesary to check whether two finishing carrings are
required.


I left it at (NBASE -1), but added a comment on that. I couldn't measure 
any performance difference between that and a larger interval, so it 
didn't seem worthwhile. The code wouldn't be much more complicated, but 
the math required to explain what the safe maximum is, would be :-).



2. Aggregates and numeric regression tests do not containt
any test case covering overflows. I recommend adding sum with numer 1
000 000 of 99 999 999 values. May be you will come up with more
clever overflow testing.


Hmm. Added a couple of simple SUM() queries to the regression tests, so 
that we have at least some test coverage of the overflows. But nothing 
very clever.


Looking closer, I don't think this implementation is actually dependent 
on NBASE being 1. So I removed the comment changes that suggested so.


I did some more minor comment fixes, and committed. Thanks for the review!

- Heikki



--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-08-03 Thread Andres Freund
On 2016-08-03 17:47:20 +, Andrey Borodin wrote:
> I suppose this proves performance impact of a patch. I don't think
> that sum calculation was a common bottleneck, but certainly patch will
> slightly improve performance of a very huge number of queries.

They commonly are in OLAP style workloads.


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-08-03 Thread Andrey Borodin

> 3 авг. 2016 г., в 22:47, Andrey Borodin  написал(а):
> 
> make installcheck-world:  tested, failed
> Implements feature:   tested, failed
> Spec compliant:   tested, failed
> Documentation:tested, failed
> 
> This is a review of a patch "Optimizing numeric SUM() aggregate" by Heikki 
> Linnakangas
Oh, I failed to use those checkboxes in web app. In my review please read 
"tested, failed" as "tested, passed". I'm sorry.

Best regards, Andrey Borodin.

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-08-03 Thread Andrey Borodin
The following review has been posted through the commitfest application:
make installcheck-world:  tested, failed
Implements feature:   tested, failed
Spec compliant:   tested, failed
Documentation:tested, failed

This is a review of a patch "Optimizing numeric SUM() aggregate" by Heikki 
Linnakangas
https://www.postgresql.org/message-id/flat/c0545351-a467-5b76-6d46-4840d1ea8...@iki.fi#c0545351-a467-5b76-6d46-4840d1ea8...@iki.fi
This review contains summarization of all my posts regarding this patch and a 
little bit of additional suggestions.

Contents & Purpose
==
This patch improves performance of aggregates computation by delaying numeric 
overflow carring between NBASE-digit arbitrary-length arithmetic. This is 
possible because 32-bit int is used for storage of every NBASE-digit, where 
NBASE is 1.
Patch changes file numeric.c only. Folder of numeric.c does not contain README. 
That is why all documentation of a patch is done in comments. I consider 
documentation sufficient.

Initial Run
===
Patch can be applied cleanly to current HEAD. Regression tests path before and 
after patch application.

Performance
===
I've tested patch with this query
CREATE TABLE avg_test AS SELECT (random() * 999)::decimal(5,2) as d FROM 
generate_series(1, 100) s;
SELECT avg(d) a , avg(d+0) s0 , avg(d+1) s1 , avg(d+2) s2, avg(d+3) s3 , 
avg(d+4) s4 , avg(d+5) s5, avg(d+6) s6 , avg(d+7) s7, avg(d+8) s8 , avg(d+9) s9 
FROM avg_test;

Test specs were: Ubuntu 14 LTS VM, dynamic RAM, hypervisor Windows
Server 2016, SSD disk, core i5-2500. Configuration: out of the box master make.

On 10 test runs timing of select statement: AVG 3739.8 ms, STD  435.4193
With patch applied (as is) : 3017.8 ms, STD 319.893

I suppose this proves performance impact of a patch. I don't think that sum 
calculation was a common bottleneck, but certainly patch will slightly improve 
performance of a very huge number of queries.

Suggestions
===
1. Currenlty overflow is carried every  addition. I suggest that it is 
possibe to do it only every (INT32_MAX - INT32_MAX / NBASE) / (NBASE - 1) 
addition. Please note that with this overflow count it will be neccesary to 
check whether two finishing carrings are required.
2. Aggregates and numeric regression tests do not containt any test case 
covering overflows. I recommend adding sum with numer 1 000 000 of 99 999 999 
values. May be you will come up with more clever overflow testing.

Conclusion
==
This patch is important and thorough work, but I'd suggest to consider some 
polishing on two points listed above.

The new status of this patch is: Waiting on Author

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-07-29 Thread Andrew Borodin
I've tested patch with this query
https://gist.github.com/x4m/fee16ed1a55217528f036983d88771b4
Test specs were: Ubuntu 14 LTS VM, dynamic RAM, hypervisor Windows
Server 2016, SSD disk, core i5-2500. Configuration: out of the box
master make.

On 10 test runs timing of select statement: AVG 3739.8 ms, STD  435.4193
With patch applied (as is) : 3017.8 ms, STD 319.893

Increase of overflow const showed no statistically viable performance
improvement (though, I do not worth doing).

2016-07-27 17:32 GMT+05:00 Tom Lane :
> For that matter, spelling INT_MAX as 0x7FF is also not per project style.

Sure, 0x7FF was not for code but for metal arithmetics. I would
even add that INT_MAX is system-dependent and varies in different
specs. I'd suggest INT32_MAX.

Best regards, Andrey Borodin, Octonica & Ural Federal University.


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-07-27 Thread Tom Lane
Andrew Borodin  writes:
>> I don't think there is any reason for this new code to assume NBASE=1

> There is a comment on line 64 stating that value 1 is hardcoded
> somewhere else, any other value is not recommended and a bunch of code
> is left for historical reasons.

Doesn't matter: please use NBASE when you mean NBASE.  1 is just a
magic number, and therefore bad coding style.  For that matter, spelling
INT_MAX as 0x7FF is also not per project style.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-07-27 Thread Dean Rasheed
On 27 July 2016 at 10:17, Andrew Borodin  wrote:
>>   if (accum->maxdig > (INT_MAX - INT_MAX / NBASE) / (NBASE - 1))
> Woth noting that (INT_MAX - INT_MAX / NBASE) / (NBASE - 1) == INT_MAX
> / NBASE for any NBASE > 1

Interesting. I think it's clearer the way it is in mul_var() though,
because the intention is to avoid letting digits exceed INT_MAX -
INT_MAX/NBASE, so that there is no danger of overflow in the carry
propagation step. The long form makes that clearer (and is just as
efficient, since these expressions will be evaluated by the
preprocessor).

Regards,
Dean


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-07-27 Thread Dean Rasheed
On 27 July 2016 at 09:57, Dean Rasheed  wrote:
> it could be
> coded using something like
>
> accum->maxdig += NBASE - 1;
> if (accum->maxdig > (INT_MAX - INT_MAX / NBASE) / (NBASE - 1))
> Propagate carries...
>

Oops, that's not quite right because maxdig is actually epresents the
max possible value divided by NBASE-1 in mul_var(), so actually it
ought to have been accum->maxdig++ in the first line.

Regards,
Dean


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-07-27 Thread Andrew Borodin
>   if (accum->maxdig > (INT_MAX - INT_MAX / NBASE) / (NBASE - 1))
Woth noting that (INT_MAX - INT_MAX / NBASE) / (NBASE - 1) == INT_MAX
/ NBASE for any NBASE > 1
>I don't think there is any reason for this new code to assume NBASE=1
There is a comment on line 64 stating that value 1 is hardcoded
somewhere else, any other value is not recommended and a bunch of code
is left for historical reasons.

Best regards, Andrey Borodin, Octonica & Ural Federal University.

2016-07-27 13:57 GMT+05:00 Dean Rasheed :
> On 27 July 2016 at 07:33, Andrew Borodin  wrote:
>>>I think we could do carry every 0x7FF / 1 accumulation, couldn't we?
>>
>> I feel that I have to elaborate a bit. Probably my calculations are wrong.
>>
>> Lets assume we already have accumulated INT_MAX of  digits in
>> previous-place accumulator. That's almost overflow, but that's not
>> overflow. Carring that accumulator to currents gives us INT_MAX/1
>> carried sum.
>> So in current-place accumulator we can accumulate: ( INT_MAX - INT_MAX
>> / 1 ) / , where  is max value dropped in current-place
>> accumulator on each addition.
>> That is INT_MAX *  /  or simply INT_MAX / 1.
>>
>> If we use unsigned 32-bit integer that is 429496. Which is 43 times
>> less frequent carring.
>>
>> As a bonus, we get rid of  const in the code (:
>>
>> Please correct me if I'm wrong.
>>
>
> This is basically the same problem that has already been solved in
> mul_var() and other places in numeric.c, so in this case it could be
> coded using something like
>
> accum->maxdig += NBASE - 1;
> if (accum->maxdig > (INT_MAX - INT_MAX / NBASE) / (NBASE - 1))
> Propagate carries...
>
> I agree that the new code should avoid explicitly referring to
> constants like , and I don't think there is any reason for this
> new code to assume NBASE=1.
>
> Regards,
> Dean


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-07-27 Thread Dean Rasheed
On 27 July 2016 at 07:33, Andrew Borodin  wrote:
>>I think we could do carry every 0x7FF / 1 accumulation, couldn't we?
>
> I feel that I have to elaborate a bit. Probably my calculations are wrong.
>
> Lets assume we already have accumulated INT_MAX of  digits in
> previous-place accumulator. That's almost overflow, but that's not
> overflow. Carring that accumulator to currents gives us INT_MAX/1
> carried sum.
> So in current-place accumulator we can accumulate: ( INT_MAX - INT_MAX
> / 1 ) / , where  is max value dropped in current-place
> accumulator on each addition.
> That is INT_MAX *  /  or simply INT_MAX / 1.
>
> If we use unsigned 32-bit integer that is 429496. Which is 43 times
> less frequent carring.
>
> As a bonus, we get rid of  const in the code (:
>
> Please correct me if I'm wrong.
>

This is basically the same problem that has already been solved in
mul_var() and other places in numeric.c, so in this case it could be
coded using something like

accum->maxdig += NBASE - 1;
if (accum->maxdig > (INT_MAX - INT_MAX / NBASE) / (NBASE - 1))
Propagate carries...

I agree that the new code should avoid explicitly referring to
constants like , and I don't think there is any reason for this
new code to assume NBASE=1.

Regards,
Dean


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-07-27 Thread Andrew Borodin
>I think we could do carry every 0x7FF / 1 accumulation, couldn't we?

I feel that I have to elaborate a bit. Probably my calculations are wrong.

Lets assume we already have accumulated INT_MAX of  digits in
previous-place accumulator. That's almost overflow, but that's not
overflow. Carring that accumulator to currents gives us INT_MAX/1
carried sum.
So in current-place accumulator we can accumulate: ( INT_MAX - INT_MAX
/ 1 ) / , where  is max value dropped in current-place
accumulator on each addition.
That is INT_MAX *  /  or simply INT_MAX / 1.

If we use unsigned 32-bit integer that is 429496. Which is 43 times
less frequent carring.

As a bonus, we get rid of  const in the code (:

Please correct me if I'm wrong.


Best regards, Andrey Borodin, Octonica & Ural Federal University.


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


Re: [HACKERS] Optimizing numeric SUM() aggregate

2016-07-26 Thread Andrew Borodin
Hi!

I like the idea and implementation, but I have one suggestion.
> Instead of propagating carry after each new value, it's done only every  
> values (or at the end).

I think we could do carry every 0x7FF / 1 accumulation, couldn't we?

Best regards, Andrey Borodin, Octonica & Ural Federal University.


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers


[HACKERS] Optimizing numeric SUM() aggregate

2016-07-25 Thread Heikki Linnakangas

Hi,

I spent some time profiling a simply query with a SUM() aggregate. We've 
made some big improvements in this area in recent years, but it seems 
there's still some room for improvement. A lot of CPU time is spent in 
the numeric add_var() and friends. Which isn't that surprising, I guess.


I came up with the attached patch that keeps the sum in a specialized 
accumulator, instead of a NumericVar. The specialized accumulator has a 
few tricks, compared to the status quo:


1. Uses 32-bit integers to represent each base-1 "digit". Instead of 
propagating carry after each new value, it's done only every  values 
(or at the end).


2. Accumulates positive and negative values separately. They positive 
and negative sums are added together only at the end. This avoids the 
overhead in add_var(), for figuring out which value is larger and 
determining the result sign at each step.


3. Only allocate a new buffer when it needs to be enlarged. add_abs() 
allocates a new one on every call.



These optimizations give a nice speedup for SUM(), and other aggregates 
like AVG() and STDDEV() that use the same agg state. For example, using 
the same test query that Hadi Moshayedi used on previous work on numeric 
aggregates 
(https://www.postgresql.org/message-id/CAK%3D1%3DWrmCkWc_xQXs_bpUyswCPr7O9zkLmm8Oa7_nT2vybvBEQ%40mail.gmail.com):


CREATE TABLE avg_test AS SELECT (random() * 999)::decimal(5,2) as d FROM
generate_series(1, 1000) s;

SELECT avg(d) FROM avg_test;

On my laptop, with max_parallel_workers_per_gather=0, this runs in about 
1.5 s without the patch, and 1.2 s with the patch.


- Heikki
From 1f9556d13ca05dae4092e2c4a8a0d7b444039726 Mon Sep 17 00:00:00 2001
From: Heikki Linnakangas 
Date: Mon, 25 Jul 2016 13:17:04 +0300
Subject: [PATCH 1/1] Speed up SUM calculation in numeric aggregates.

This introduces a numeric sum accumulator, which performs better than
repeatedly calling add_var(). The performance comes from using wider
digits and delaying carry propagation, and using separate sums for
positive and negative values, and avoiding a round of palloc/pfree on
every value. This speeds up SUM(), as well as other standard aggregates
like AVG() and STDDEV() that also calculate a sum internally.
---
 src/backend/utils/adt/numeric.c | 596 +---
 1 file changed, 492 insertions(+), 104 deletions(-)

diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c
index 2fbdfe0..746a4c6 100644
--- a/src/backend/utils/adt/numeric.c
+++ b/src/backend/utils/adt/numeric.c
@@ -65,7 +65,8 @@
  * and are no longer supported in any sense; no mechanism exists for the client
  * to discover the base, so every client supporting binary mode expects the
  * base-1 format.  If you plan to change this, also note the numeric
- * abbreviation code, which assumes NBASE=1.
+ * abbreviation code, and the numeric sum accum code, which both assume
+ * NBASE=1.
  * --
  */
 
@@ -302,6 +303,51 @@ typedef struct
 	hyperLogLogState abbr_card; /* cardinality estimator */
 } NumericSortSupport;
 
+
+/* --
+ * Fast sum accumulator.
+ *
+ * NumericSumAccum is used to implement SUM(), and other standard aggregates
+ * that track the sum of input values. It uses 32-bit integers to store the
+ * digits, instead of the normal 16-bit integers (with NBASE=1). This
+ * way, we can safely accumulate up to  values without propagating carry,
+ * before risking overflow any of the digits. Delaying carry propagation
+ * avoids a lot of overhead. 'num_uncarried' tracks how many values have been
+ * accumulated without propagating carry.
+ *
+ * Positive and negative values are accumulated separately, in 'pos_digits'
+ * 'neg_digits'. This is simpler and faster than deciding whether to add
+ * or subtract from the current value, for each new value (see sub_var()
+ * for the logic we avoid by doing this). Both buffers are of same size,
+ * and have the same weight and scale. In accum_sum_final(), the positive
+ * and negative sums are added together to produce the final result.
+ *
+ * When a new value has a larger ndigits or weight than the accumulator
+ * currently does, the ndigits and weight of the accumulator are enlarged
+ * to accommodate the new value. We normally have one zero digit reserved
+ * for carry propagation, and that is indicated by the 'have_carry_space'
+ * flag. When accum_sum_carry() uses up the reserved digit, it clears the
+ * 'have_carry_space' flag. The next call to accum_sum_add() will enlarge
+ * the buffer, to make room for the extra digit, and set the flag again.
+ *
+ * To initialize a new accumulator, simply reset all fields to zeros.
+ *
+ * The accumulator does not handle NaNs.
+ *
+ * --
+ */
+typedef struct NumericSumAccum
+{
+	int			ndigits;
+	int			weight;
+	int			dscale;
+	int			num_uncarried;
+	bool		have_carry_space;
+	int32	   *pos_digits;
+	int32	   *neg_digits;
+}