apache / apache/datafusion

Decorrelate scalar subqueries with more complex filter expressions

Offen
#14,554 15 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen
enhancement
Vorherrschende Sprache
Rust
Sterne
9.3k
Forks
2.4k
Ø Merge
3 T. 11 Std.
Gemergte PRs (30 T.)
360

Beschreibung

### Is your feature request related to a problem or challenge?

Datafusion already support decorrelating simple scalar subqueries in this PR: https://github.com/apache/datafusion/pull/6457

This follow the first approach in [TUM paper](https://btw-2015.informatik.uni-hamburg.de/res/proceedings/Hauptband/Wiss/Neumann-Unnesting_Arbitrary_Querie.pdf) (simple unnesting), and allow decorrelating [this simple query](https://github.com/apache/datafusion/blob/873d4178ab3c98ca6f78ef553c8e33e12dd342fb/datafusion/core/tests/sqllogictests/test_files/subquery.slt#L797)

```
explain select t1.t1_int from t1 where (select count(*) from t2 where t1.t1_id = t2.t2_id) < t1.t1_int
```
However, if we add an `or` condition this subquery
```
explain select t1.t1_int from t1 where (select count(*) from t2 where t1.t1_id = t2.t2_id or t1.t1_name=t2.t2_name) < t1.t1_int
```

Datafusion cannot decorrelate it
```
+--------------+----------------------------------------------------------------------------------------+
| plan_type | plan |
+--------------+----------------------------------------------------------------------------------------+
| logical_plan | Projection: t1.t1_int |
| | Filter: () < CAST(t1.t1_int AS Int64) |
| | Subquery: |
| | Projection: count(*) |
| | Aggregate: groupBy=[[]], aggr=[[count(Int64(1)) AS count(*)]] |
| | Filter: outer_ref(t1.t1_id) = t2.t2_id OR outer_ref(t1.t1_name) = t2.t2_name |
| | TableScan: t2 |
| | TableScan: t1 projection=[t1_id, t1_name, t1_int] |
+--------------+----------------------------------------------------------------------------------------+
```

### Describe the solution you'd like

Support decorrelating this query following the second method mentioned in the paper

### Describe alternatives you've considered

_No response_

### Additional context

General framework for decorrelation maybe discussed here https://github.com/apache/datafusion/issues/5492

But the steps needed to make this work is followed

Allow decorrelation for this type of filter exprs in this code: https://github.com/apache/datafusion/blob/813220d54f08c5203ad79bfb066ca638abe208ed/datafusion/optimizer/src/decorrelate.rs#L162

Add more logic to handle complex query decorrelation:
- Build domain/magic relation
- Rewrite the subquery to join inner table (table of the subquery) with domain/magic relation using its complex filter expression (i.e `t2.t2_id = domain.t1_id OR t2.t2_name = domain.t1_name`)
- Rewrite aggregation to group by the additional columns mentioned in the domain/magic relation
- Join the outer relation with the newly built aggregation

For example the above mentioned query may be rewritten like
```
explain select t1.t1_int from t1,
(
select count(*) as count_all, domain.t1_id as t1_id, domain.t1_name as t1_name from (
select distinct t1_id, t1_name from t1
) as domain join t2 where t2.t2_id = domain.t1_id or t2.t2_name=domain.t1_name
group by domain.t1_id, domain.t1_name
) as pulled_up
where t1.t1_id=pulled_up.t1_id and pulled_up.count_all < t1.t1_int
```

Logical plan may look like
```
| logical_plan | Projection: t1.t1_int |
| | Inner Join: t1.t1_id = pulled_up.t1_id Filter: pulled_up.count_all < CAST(t1.t1_int AS Int64) |
| | TableScan: t1 projection=[t1_id, t1_int] |
| | SubqueryAlias: pulled_up |
| | Projection: count(*) AS count_all, domain.t1_id |
| | Aggregate: groupBy=[[domain.t1_id, domain.t1_name]], aggr=[[count(Int64(1)) AS count(*)]] |
| | Projection: domain.t1_id, domain.t1_name |
| | Inner Join: Filter: t2.t2_id = domain.t1_id OR t2.t2_name = domain.t1_name |
| | SubqueryAlias: domain |
| | Aggregate: groupBy=[[t1.t1_id, t1.t1_name]], aggr=[[]] |
| | TableScan: t1 projection=[t1_id, t1_name] |
| | TableScan: t2 projection=[t2_id, t2_name]
```

Beitragsleitfaden

Beitragsleitfaden öffnen

Rechercherichtung

Beginne in datafusion/optimizer/src/decorrelate.rs bei der Behandlung von Filterausdrücken in Zeile 162 und überprüfe anschließend den bestehenden Fall für scalar-subquery sowie das subquery-Beispiel in datafusion/core/tests/sqllogictests/test_files/subquery.slt bei Zeile 797. Implementiere die im Issue beschriebenen Schritte für domain/magic-relation, Join, Gruppierung und Aggregation, führe den relevanten sqllogictest aus und bestätige, dass die komplexe OR-filter-Abfrage decorrelated wird.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Bewertung

Tech-Stack
rust, sql
Bereich
databases
Issue-Typ
Feature
Schwierigkeit
5/5
Geschätzter Aufwand
Über eine Woche
Aktivitätsstatus
Veraltet
Klarheit
Größtenteils klar
Anfängerfreundlichkeit
35/100

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.