Recently I've been playing with quite a big table (over 50mln rows),
and did some SELECT ... sum(...) WHERE ... GROUP BY ... queries.

The usual plan for these is to sort the entries according to GROUP BY
specification, then to run aggregates one by one. If the data to be
sorted is large enough, PostgreSQL has no other option than to spill
to disk, which well, Isn't the fastest...

Then I thought, why not skip the sorting, and do something like this,
say a table is:
kind tetx, sumkind text, cnt int, size int
foo, bar, 2, 10
blah, argh, 23, 3
foo, baz, 1, 20
blah, argh, 23, 3
and the query would be:
SELECT kind,subkind,sum(cnt),sum(size) FROM x GROUP BY kind,subkind;
Instead of sorting, we would create an empty temporary state variable tree,
looked up "foo, bar" in that tree -- if not found, enter there a new
initialized
state variables for sum(cnt) and sum(size).
looked up blah, argh -- create the state variables
looked up foo, baz -- create the state variables
looked up blah,argh -- update the state variables there.
And finally dump the whole tree as results of our query:
foo, bar, 2, 10
foo, baz, 1, 20
blah, argh, 46,6

Of course first thing you'll notice is that the "looking up" part will probably
eat all benefits from not spilling, and if group by columns have large
cardinality we'd have to spill anyway. But then I thought, maybe a hybrid
approach could be benefitial, and its' the resason I'm sending this message.

The hybrid approach means: sort as much as you can without spilling to
disk, then aggregate and store aggregate state variables in safe place
(like a "tree" above), get more tuples from the table, sort them, update
aggregate state variables, lather, rince, repeat.

This should avoid the need to spill to disk. The cost of such operation
depends on cardinality of GROUP BY part (and their correlation, doh),
so it might be wise to try this approach for promising data only.

I have yet almost no knowledge od PostgreSQL's internals, but I think
the idea is feasible therefore I post it here. If it's been proposed before,
forgive me.

Regards,
Dawid

---------------------------(end of broadcast)---------------------------
TIP 3: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

On Thu, Oct 12, 2006 at 09:52:11AM +0200, Dawid Kuroczko wrote:
> Recently I've been playing with quite a big table (over 50mln rows),
> and did some SELECT ... sum(...) WHERE ... GROUP BY ... queries.
>
> The usual plan for these is to sort the entries according to GROUP BY
> specification, then to run aggregates one by one. If the data to be
> sorted is large enough, PostgreSQL has no other option than to spill
> to disk, which well, Isn't the fastest...

<snip>

Sounds an awful lot like the HashAggregate nodetype which has existed
since at least 7.4. It has a hashtable of "keys" with attached
"states".

Hope this helps,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFFLhGGIB7bNG8LQkwRAo08AJ9DmkcGzT3o4ubj9hdoEi dAH4xexwCfUY+m
9sElIOoVy+GW8xypqvDeaoI=
=UYKG
-----END PGP SIGNATURE-----

Hi, Dawid,

Dawid Kuroczko wrote:

> The hybrid approach means: sort as much as you can without spilling to
> disk, then aggregate and store aggregate state variables in safe place
> (like a "tree" above), get more tuples from the table, sort them, update
> aggregate state variables, lather, rince, repeat.

For this to work, you need an additional function in the aggregate
definition, that allows to merge two states into one, for the "update
aggregate state variables" step.

Recently, there was some discussion that the Bizgres MPP people already
have such a function for merging states of different backend processes,
and that the query planner could benefit from such a function e. G. in
case of UNION or table partitioning.

Maybe we should come up with an exact definition of syntax and semantics
of this function, that satisfies all the needs of the three usecases above?

Thanks,
Markus

--
Markus Schaber | Logical Tracking&Tracing International AG
Dipl. Inf. | Software Development GIS

Fight against software patents in Europe! www.ffii.org
www.nosoftwarepatents.org


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFFMfxdyHQIGEs7eeARAyK7AKDuoUSjKkih/w5glxjIzdcSjkMBWgCeLJyo
Q8gweHMF16LK2XlnNfrzSF4=
=elX2
-----END PGP SIGNATURE-----