Re: PoC: Grouped base relation

On 17 January 2017 at 16:30, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
> Let's instead use an example similar to what Antonin mentioned in the
> initial post - two tables, with two columns each.
>
> CREATE TABLE t1 (a INT, b INT);
> CREATE TABLE t2 (c INT, d INT);
>
> And let's assume each table has 100.000 rows, but only 100 groups in the
> first column, with 1000 rows per group. Something like
>
> INSERT INTO t1
> SELECT mod(i,100), i FROM generate_series(1, 1e5) s(i);
>
> INSERT INTO t2
> SELECT mod(i,100), i FROM generate_series(1, 1e5) s(i);
>
> And let's assume this query
>
> SELECT t1.a, count(t2.d) FROM t1 JOIN t2 ON (t1.a = t2.c)
> GROUP BY t1.a;
>
> On master, EXPLAIN (COSTS OFF, TIMING OFF, ANALYZE) looks like this:
>
> QUERY PLAN
> -----------------------------------------------------------------
> HashAggregate (actual rows=100 loops=1)
> Group Key: t1.a
> -> Hash Join (actual rows=100000000 loops=1)
> Hash Cond: (t2.c = t1.a)
> -> Seq Scan on t2 (actual rows=100000 loops=1)
> -> Hash (actual rows=100000 loops=1)
> Buckets: 131072 Batches: 2 Memory Usage: 2716kB
> -> Seq Scan on t1 (actual rows=100000 loops=1)
> Planning time: 0.167 ms
> Execution time: 17005.300 ms
> (10 rows)
>
> while with the patch it looks like this
>
> QUERY PLAN
> ---------------------------------------------------------------------
> Finalize HashAggregate (actual rows=100 loops=1)
> Group Key: t1.a
> -> Hash Join (actual rows=100 loops=1)
> Hash Cond: (t1.a = t2.c)
> -> Partial HashAggregate (actual rows=100 loops=1)
> Group Key: t1.a
> -> Seq Scan on t1 (actual rows=100000 loops=1)
> -> Hash (actual rows=100 loops=1)
> Buckets: 1024 Batches: 1 Memory Usage: 14kB
> -> Partial HashAggregate (actual rows=100 loops=1)
> Group Key: t2.c
> -> Seq Scan on t2 (actual rows=100000 loops=1)
> Planning time: 0.105 ms
> Execution time: 31.609 ms
> (14 rows)
>
> This of course happens because with the patch we run the transition function
> 200k-times (on each side of the join) and aggtransmultifn on the 100 rows
> produced by the join, while on master the join produces 10.000.000 rows
> (which already takes much more time), and then have to run the transition
> function on all those rows.
>
> The performance difference is pretty obvious, I guess.

An exceptional improvement.

For the combine aggregate example of this query, since no patch exists
yet, we could simply mock what the planner would do by rewriting the
query. I'll use SUM() in-place of the combinefn for COUNT():

explain analyze SELECT t1.a, sum(t2.d) FROM t1 join (SELECT c,count(d)
d from t2 group by c) t2 on t1.a = t2.c group by t1.a;

this seems to be 100,000 aggtransfn calls (for t2), then 100,000
aggcombinefn calls (for t1) (total = 200,000), where as the patch
would perform 100,000 aggtransfn calls (for t2), then 100,000
aggtransfn calls (for t1), then 100 aggtransmultifn calls (total =
200,100)

Is my maths ok?

> I don't quite see how the patch could use aggcombinefn without sacrificing a
> lot of the benefits. Sure, it's possible to run the aggcombinefn in a loop
> (with number of iterations determined by the group size on the other side of
> the join), but that sounds pretty expensive and eliminates the reduction of
> transition function calls. The join cardinality would still be reduced,
> though.

I'd be interested in seeing the run time of my example query above. I
can't quite see a reason for it to be slower, but please let me know.

> I do have other question about the patch, however. It seems to rely on the
> fact that the grouping and joins both reference the same columns. I wonder
> how uncommon such queries are.
>
> To give a reasonable example, imagine the typical start schema, which is
> pretty standard for large analytical databases. A dimension table is
> "products" and the fact table is "sales", and the schema might look like
> this:
>
> CREATE TABLE products (
> id SERIAL PRIMARY KEY,
> name TEXT,
> category_id INT,
> producer_id INT
> );
>
> CREATE TABLE sales (
> product_id REFERENCES products (id),
> nitems INT,
> price NUMERIC
> );
>
> A typical query then looks like this:
>
> SELECT category_id, SUM(nitems), SUM(price)
> FROM products p JOIN sales s ON (p.id = s.product_id)
> GROUP BY p.category_id;
>
> which obviously uses different columns for the grouping and join, and so the
> patch won't help with that. Of course, a query grouping by product_id would
> allow the patch to work
>
> SELECT category_id, SUM(nitems), SUM(price)
> FROM products p JOIN sales s ON (p.id = s.product_id)
> GROUP BY p.product_id;
>
> Another thing is that in my experience most queries do joins on foreign keys
> (so the PK side is unique by definition), so the benefit on practical
> examples is likely much smaller.
>
> But I guess my main question is if there are actual examples of queries the
> patch is trying to improve, or whether the general benefit is allowing
> parallel plans for queries where it would not be possible otherwise.

Using the combine function technique the planner could have performed
this query the same as if the query had been written as:

SELECT p.category_id, SUM(sum_nitems), SUM(sum_price) FROM products p
JOIN (SELECT product_id,SUM(nitems) sum_nitems,SUM(price) sum_price
FROM sales GROUP BY product_id) s ON p.product_id = s.product_id GROUP
BY p.category_id;

The outer SUM() would be the combine function for SUM() in the
finalize aggregate node.

Why's that less efficient?

I don't deny that there's cases that this multiple aggregate function
won't be able to optimise better than the combine function, but I'm
just not that convinced yet it'll be worth the trouble when combine
functions, which are already in core could do most of what would be
useful with a fraction of the code.

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