[MDEV-4166] Hash based aggregation for large input, small output GROUP BY Created: 2013-02-12 Updated: 2013-09-29 Due: 2013-02-26 Resolved: 2013-09-29 |
|
| Status: | Closed |
| Project: | MariaDB Server |
| Component/s: | None |
| Fix Version/s: | None |
| Type: | Task | Priority: | Major |
| Reporter: | Mathew Johnston | Assignee: | Unassigned |
| Resolution: | Won't Fix | Votes: | 0 |
| Labels: | None | ||
| Description |
|
The current sort based GROUP BY implementation performs badly when source data is large (much larger than available RAM) and output is small. An alternative method, supported by Oracle, PostgreSQL, SQL Server, etc. is to use hash aggregation, as described here: http://blogs.msdn.com/b/craigfr/archive/2006/09/20/hash-aggregate.aspx Because the optimizer may not have sufficient stats to choose hash vs. sort aggregation, an optimization hint should be available for use in SELECT statements. |
| Comments |
| Comment by Igor Babaev [ 2013-02-12 ] |
|
Honestly I don't understand what you mean. |
| Comment by Mathew Johnston [ 2013-02-12 ] |
|
Hi Igor, The use of temporary tables is actually something I've had a hard time finding documentation on. While I'm at it - the behaviour of count(distinct X) seems to be undocumented too. In building the temporary table, is it creating a 'unique' HASH index on the grouped fields, and doing an INSERT INTO tmp ... ON DUPLICATE KEY UPDATE tmp_sum = tmp_sum+values(tmp_sum), etc? I.e. the temp table should only ever contain 1 row for each GROUP BY key? Anyway, the described algorithm (linked) uses an iterative approach, writing overflow to disk and merging it on subsequent passes. It means the algorithm doesn't have to fall back to filesort if the results don't fit in RAM. Thanks for your interest! |
| Comment by Sergei Golubchik [ 2013-09-29 ] |
|
MariaDB can never fall back to filesort. Optimizer decides up front whether to use temporary tables or filesort and it cannot change the decision later. When a temporary table in meory overflows, it is converted to on-disk temporary table (MyISAM or Aria) and it uses btree indexes instead of hash. |