apache / apache/datafusion

Improve Aggregate with Limit

Open
#13,729 1 comment 3 reactions 0 assignees View on GitHub
enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.