Improve Aggregate with Limit
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Is your feature request related to a problem or challenge?
Currently datafusion supports topk_aggregation(#7192 ), and I've noticed two potential areas for optimization:
1. `topk_aggregation` only supports ordering by aggregations (order by agg), but doesn't support ordering by columns
2. `topk_aggregation` cannot be used in cases where there is no `order by` clause
### Describe the solution you'd like
1. For the first one, I think we can directly use the current priority queue solution
2. For the second one:
The following query which without an `ORDER BY` clause is a non-deterministic query where returning aggregate results for any 10 keys is valid. Therefore, the simplest optimization method is to make the aggregate operation work in an ordered manner.
```sql
SELECT "UserID", MIN("AdvEngineID") FROM hits GROUP BY "UserID" order by MIN("AdvEngineID") LIMIT 10;
```
When using ORDER BY, it runs faster
```bash
> SELECT "UserID", MIN("AdvEngineID") FROM hits GROUP BY "UserID" order by MIN("AdvEngineID") LIMIT 10;
+---------------------+-----------------------+
| UserID | min(hits.AdvEngineID) |
+---------------------+-----------------------+
| 8265925904823819813 | 0 |
| 4187744066815097140 | 0 |
| 7970073217952173230 | 0 |
| 1427747163043990597 | 0 |
| 844431718317972727 | 0 |
| 5777095312382298493 | 0 |
| 1726996514541263413 | 0 |
| 9126602271142633613 | 0 |
| 137961262398427389 | 0 |
| 1015195936484711824 | 0 |
+---------------------+-----------------------+
10 row(s) fetched.
Elapsed 0.389 seconds.
> SELECT "UserID", MIN("AdvEngineID") FROM hits GROUP BY "UserID" LIMIT 10;
+--------------------+-----------------------+
| UserID | min(hits.AdvEngineID) |
+--------------------+-----------------------+
| 572919489234519776 | 0 |
| 573305205053433738 | 0 |
| 573316808606264402 | 0 |
| 573764012887855352 | 0 |
| 573878311420505425 | 0 |
| 574390391777319344 | 0 |
| 574747808491966822 | 0 |
| 574822330152391359 | 0 |
| 574882842092706724 | 0 |
| 576132580282803970 | 0 |
+--------------------+-----------------------+
10 row(s) fetched.
Elapsed 0.632 seconds.
```
### Describe alternatives you've considered
_No response_
### Additional context
Just found that the `TopKAggregation` only support group by one column, I'm confused.
https://github.com/apache/datafusion/blob/0f5634ec3de8cae77804aae883b655db38da4648/datafusion/physical-optimizer/src/topk_aggregation.rs#L57
Contributor guide
Research direction
Start with datafusion/physical-optimizer/src/topk_aggregation.rs at the linked TopKAggregation implementation, then compare the two SQL examples in the issue. Determine how aggregate-with-LIMIT should behave with ORDER BY, without ORDER BY, ordering by columns, and multiple GROUP BY columns; done means the requested cases are supported without changing valid nondeterministic results.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust, sql
- Domain
- databases, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100