Improving avg performance for numeric

Hello

2013/3/16 Hadi Moshayedi <hadi@moshayedi.net>:

Revisiting:
/messages/by-id/45661BE7.4050205@paradise.net.nz

I think the reasons which the numeric average was slow were:
(1) Using Numeric for count, which is slower than int8 to increment,
(2) Constructing/deconstructing arrays at each transition step.

This is also discussed at:
http://www.citusdata.com/blog/53-postgres-performance-to-avg-or-to-sum-divided-by-count

So, I think we can improve the speed of numeric average by keeping the
transition state as an struct in the aggregate context, and just passing the
pointer to that struct from/to the aggregate transition function.

The attached patch uses this method.

I tested it using the data generated using:
CREATE TABLE avg_test AS SELECT (random() * 999)::decimal(5,2) as d FROM
generate_series(1, 10000000) s;

After applying this patch, run time of "SELECT avg(d) FROM avg_test;"
improves from 10.701 seconds to 5.204 seconds, which seems to be a huge
improvement.

I think we may also be able to use a similar method to improve performance
of some other numeric aggregates (like stddev). But I want to know your
feedback first.

Is this worth working on?

nice

+1

Regards

Pavel

Thanks,
-- Hadi

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

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

2013/3/16 Hadi Moshayedi <hadi@moshayedi.net>:

Revisiting:
/messages/by-id/45661BE7.4050205@paradise.net.nz

I think the reasons which the numeric average was slow were:
(1) Using Numeric for count, which is slower than int8 to increment,
(2) Constructing/deconstructing arrays at each transition step.

This is also discussed at:
http://www.citusdata.com/blog/53-postgres-performance-to-avg-or-to-sum-divided-by-count

So, I think we can improve the speed of numeric average by keeping the
transition state as an struct in the aggregate context, and just passing the
pointer to that struct from/to the aggregate transition function.

The attached patch uses this method.

I tested it using the data generated using:
CREATE TABLE avg_test AS SELECT (random() * 999)::decimal(5,2) as d FROM
generate_series(1, 10000000) s;

After applying this patch, run time of "SELECT avg(d) FROM avg_test;"
improves from 10.701 seconds to 5.204 seconds, which seems to be a huge
improvement.

I think we may also be able to use a similar method to improve performance
of some other numeric aggregates (like stddev). But I want to know your
feedback first.

Is this worth working on?

I checked this patch and it has a interesting speedup - and a price of
this methoud should not be limited to numeric type only

Pavel

Thanks,
-- Hadi

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

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

Hi Pavel,

Thanks a lot for your feedback.

I'll work more on this patch this week, and will send a more complete patch
later this week.

I'll also try to see how much is the speed up of this method for other
types.

Thanks,
-- Hadi

On Mon, Mar 18, 2013 at 10:36 AM, Pavel Stehule <pavel.stehule@gmail.com>wrote:

Hello

I played with sum(numeric) optimization

Now it is based on generic numeric_add function - this code is
relative old - now we can design aggregates with internal transition
buffers, and probably we can do this work more effective.

I just removed useles palloc/free operations and I got a 30% better
performance! My patch is ugly - because I used a generic add_var
function. Because Sum, Avg and almost all aggregates functions is
limited by speed of sum calculation I thing so we need a new numeric
routines optimized for calculation "sum", that use a only preallocated
buffers. A speed of numeric is more important now, because there are
more and more warehouses, where CPU is botleneck.

Regards

Pavel

2013/3/18 Hadi Moshayedi <hadi@moshayedi.net>:

Hello,

I updated the patch by taking ideas from your patch, and unifying the
transition struct and update function for different aggregates. The speed
of avg improved even more. It now has 60% better performance than the
current committed version.

This patch optimizes numeric/int8 sum, avg, stddev_pop, stddev_samp,
var_pop, var_samp.

I also noticed that this patch makes matview test fail. It seems that it
just changes the ordering of rows for queries like "SELECT * FROM tv;".
Does this seem like a bug in my patch, or should we add "ORDER BY" clauses
to this test to make it more deterministic?

I also agree with you that adding sum functions to use preallocated buffers
will make even more optimization. I'll try to see if I can find a simple
way to do this.

Thanks,
-- Hadi

On Mon, Mar 18, 2013 at 5:25 PM, Pavel Stehule <pavel.stehule@gmail.com>wrote:

Hadi Moshayedi <hadi@moshayedi.net> wrote:

I updated the patch by taking ideas from your patch, and unifying
the transition struct and update function for different
aggregates. The speed of avg improved even more. It now has 60%
better performance than the current committed version.

Outstanding!

I also noticed that this patch makes matview test fail. It seems
that it just changes the ordering of rows for queries like
"SELECT * FROM tv;". Does this seem like a bug in my patch, or
should we add "ORDER BY" clauses to this test to make it more
deterministic?

I added some ORDER BY clauses.  That is probably a good thing
anyway for purposes of code coverage.  Does that fix it for you?

--
Kevin Grittner
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

2013/3/19 Kevin Grittner <kgrittn@ymail.com>:

Hadi Moshayedi <hadi@moshayedi.net> wrote:

I updated the patch by taking ideas from your patch, and unifying
the transition struct and update function for different
aggregates. The speed of avg improved even more. It now has 60%
better performance than the current committed version.

Outstanding!

I did some tests ala OLAP queries and I am thinking so ~ 40% speedup
for queries with AVG is realistic. Depends on other conditions.

But there are lot of situation when data are in shared buffers or file
system memory and then this patch can carry significant speedup - and
probably can be better if some better algorithm for sum two numeric
numbers in aggregate.

Regards

Pavel

I also noticed that this patch makes matview test fail. It seems
that it just changes the ordering of rows for queries like
"SELECT * FROM tv;". Does this seem like a bug in my patch, or
should we add "ORDER BY" clauses to this test to make it more
deterministic?

I added some ORDER BY clauses. That is probably a good thing
anyway for purposes of code coverage. Does that fix it for you?

--
Kevin Grittner
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

Kevin Grittner <kgrittn@ymail.com> writes:

Hadi Moshayedi <hadi@moshayedi.net> wrote:

I also noticed that this patch makes matview test fail. It seems
that it just changes the ordering of rows for queries like
"SELECT * FROM tv;". Does this seem like a bug in my patch, or
should we add "ORDER BY" clauses to this test to make it more
deterministic?

I added some ORDER BY clauses.� That is probably a good thing
anyway for purposes of code coverage.� Does that fix it for you?

Uh, what? Fooling around with the implementation of avg() should surely
not change any planning decisions.

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

I am not sure how this works, but I also changed numeric sum(), and the
views in question had a numeric sum() column. Can that have any impact?

I am going to dig deeper to see why this happens.

On Tue, Mar 19, 2013 at 6:25 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

[ please do not top-reply ]

Hadi Moshayedi <hadi@moshayedi.net> writes:

On Tue, Mar 19, 2013 at 6:25 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Uh, what? Fooling around with the implementation of avg() should surely
not change any planning decisions.

I am not sure how this works, but I also changed numeric sum(), and the
views in question had a numeric sum() column. Can that have any impact?

[ looks at patch... ] Oh, I see what's affecting the plan: you changed
the aggtranstypes to internal for a bunch of aggregates. That's not
very good, because right now the planner takes that to mean that the
aggregate could eat a lot of space. We don't want that to happen for
these aggregates, I think.

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

I wrote:

[ looks at patch... ] Oh, I see what's affecting the plan: you changed
the aggtranstypes to internal for a bunch of aggregates. That's not
very good, because right now the planner takes that to mean that the
aggregate could eat a lot of space. We don't want that to happen for
these aggregates, I think.

After thinking about that for awhile: if we pursue this type of
optimization, what would probably be appropriate is to add an aggregate
property (stored in pg_aggregate) that allows direct specification of
the size that the planner should assume for the aggregate's transition
value. We were getting away with a hardwired assumption of 8K for
"internal" because the existing aggregates that used that transtype all
had similar properties, but it was always really a band-aid not a proper
solution. A per-aggregate override could be useful in other cases too.

This was looking like 9.4 material already, but adding such a property
would definitely put it over the top of what we could think about
squeezing into 9.3, IMO.

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

Hello

2013/3/19 Tom Lane <tgl@sss.pgh.pa.us>:

I wrote:

[ looks at patch... ] Oh, I see what's affecting the plan: you changed
the aggtranstypes to internal for a bunch of aggregates. That's not
very good, because right now the planner takes that to mean that the
aggregate could eat a lot of space. We don't want that to happen for
these aggregates, I think.

After thinking about that for awhile: if we pursue this type of
optimization, what would probably be appropriate is to add an aggregate
property (stored in pg_aggregate) that allows direct specification of
the size that the planner should assume for the aggregate's transition
value. We were getting away with a hardwired assumption of 8K for
"internal" because the existing aggregates that used that transtype all
had similar properties, but it was always really a band-aid not a proper
solution. A per-aggregate override could be useful in other cases too.

This was looking like 9.4 material already, but adding such a property
would definitely put it over the top of what we could think about
squeezing into 9.3, IMO.

Postgres is not a "in memory" OLAP database, but lot of companies use
it for OLAP queries due pg comfortable usage. This feature can be very
interesting for these users - and can introduce interesting speedup
with relative low price.

Regards

Pavel

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

Hi Tom,

Tom Lane <tgl@sss.pgh.pa.us> wrote:

After thinking about that for awhile: if we pursue this type of
optimization, what would probably be appropriate is to add an aggregate
property (stored in pg_aggregate) that allows direct specification of
the size that the planner should assume for the aggregate's transition
value. We were getting away with a hardwired assumption of 8K for
"internal" because the existing aggregates that used that transtype all
had similar properties, but it was always really a band-aid not a proper
solution. A per-aggregate override could be useful in other cases too.

Cool.

I created a patch which adds an aggregate property to pg_aggregate, so
the transition space is can be overridden. This patch doesn't contain
the numeric optimizations. It uses "0" (meaning not-set) for all
existing aggregates.

I manual-tested it a bit, by changing this value for aggregates and
observing the changes in plan. I also updated some docs and pg_dump.

Does this look like something along the lines of what you meant?

Thanks,
-- Hadi

Hello

2013/3/20 Hadi Moshayedi <hadi@moshayedi.net>:

Hi Tom,

Tom Lane <tgl@sss.pgh.pa.us> wrote:

After thinking about that for awhile: if we pursue this type of
optimization, what would probably be appropriate is to add an aggregate
property (stored in pg_aggregate) that allows direct specification of
the size that the planner should assume for the aggregate's transition
value. We were getting away with a hardwired assumption of 8K for
"internal" because the existing aggregates that used that transtype all
had similar properties, but it was always really a band-aid not a proper
solution. A per-aggregate override could be useful in other cases too.

Cool.

I created a patch which adds an aggregate property to pg_aggregate, so
the transition space is can be overridden. This patch doesn't contain
the numeric optimizations. It uses "0" (meaning not-set) for all
existing aggregates.

I manual-tested it a bit, by changing this value for aggregates and
observing the changes in plan. I also updated some docs and pg_dump.

Does this look like something along the lines of what you meant?

please, can you subscribe your patch to next commitfest?

I tested this patch, and it increase performance about 20% what is
interesting. More - it allows more comfortable custom aggregates for
custom types with better hash agg support.

Regards

Pavel

Thanks,
-- Hadi

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

I am attaching the updated the patch, which also fixes a bug which
caused one of the regression tests failed.

I'll subscribe this patch to the commitfest in the next hour.

Can you please review the patch?

Thanks,
-- Hadi

2013/7/8 Hadi Moshayedi <hadi@moshayedi.net>:

I am attaching the updated the patch, which also fixes a bug which
caused one of the regression tests failed.

I'll subscribe this patch to the commitfest in the next hour.

Can you please review the patch?

sure, :)

Pavel

Thanks,
-- Hadi

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

Hello

I am testing your code, and It increase speed of sum about 24% faster
then original implementation.

But I am surprise of AVG speed - it should have same speed like sum in
new implementation, but it is 2x slower, than sum - what signalize
some strange and there is used wrong transition function

I am sending fixed version

postgres=# create table bubu(a int, b float, c numeric);
CREATE TABLE
postgres=# insert into bubu select i, i+1, i+1.122 from
generate_series(1,1000000) g(i);
INSERT 0 1000000

After fixing a speed of sum and avg for numeric is similar

postgres=# select avg(c) from bubu;
avg
---------------------
500001.622000000000
(1 row)

Time: 228.483 ms
postgres=# select sum(c) from bubu;
sum
------------------
500001622000.000
(1 row)

Time: 222.791 ms

Regards

Pavel

2013/7/8 Hadi Moshayedi <hadi@moshayedi.net>:

On 07/07/2013 09:14 PM, Hadi Moshayedi wrote:

I am attaching the updated the patch, which also fixes a bug which
caused one of the regression tests failed.

I'll subscribe this patch to the commitfest in the next hour.

Can you please review the patch?

I'm afraid that, since this patch wasn't included anywhere near the
first week of the CommitFest, I can't possibly include it in the June
commitfest now. Accordingly, I have moved it to the September
commitfest. Hopefully someone can look at it before then.

Sorry for missing this in my "patch sweep" at the beginning of the CF.
Searching email for patches is, at best, inexact.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

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

Hello

2013/7/8 Josh Berkus <josh@agliodbs.com>:

On 07/07/2013 09:14 PM, Hadi Moshayedi wrote:

I am attaching the updated the patch, which also fixes a bug which
caused one of the regression tests failed.

I'll subscribe this patch to the commitfest in the next hour.

Can you please review the patch?

I'm afraid that, since this patch wasn't included anywhere near the
first week of the CommitFest, I can't possibly include it in the June
commitfest now. Accordingly, I have moved it to the September
commitfest. Hopefully someone can look at it before then.

Sorry for missing this in my "patch sweep" at the beginning of the CF.
Searching email for patches is, at best, inexact.

sure, it should be in September CF. It is relative simple patch
without global impacts. But I like it, it increase speed for
sum(numeric) about 25% and avg(numeric) about 50%

Regards

Pavel

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

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