apache / apache/datafusion

Improve Sort Based Optimizations

Aperta
#8,064 0 commenti 3 reazioni 0 assegnatari Vedi su GitHub
enhancement
Lingua principale
Rust
Stelle
9.3k
Fork
2.4k
Merge medio
3g 11h
PR unite (30g)
360

Descrizione

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

In the existing code base we have two different methods to keep track of equivalences in the `Arc`.
Which are `equivalence_properties` and `ordering_equivalence_properties`.

As a background `EquivalenceProperties` keeps track of equivalent columns such as `a=b=c`, `e=f`.
`OrderingEquivalenceProperties` alternative orderings that table satisfies. such `[a ASC, b ASC]`, and `[c ASC, d ASC]`.
`OrderingEquivalenceProperties` keeps track of constant expressions also (e.g expression that are known to have a constant value. This can arise after filter, join, etc.).

Inherently, this information is coupled, as an example
Assume that
- existing table satisfies following orderings `[a ASC, b ASC]` and `[c ASC, d ASC]`.
- table have equivalent columns `a=e`.
- It is known that `f` is constant.

If an operator requires ordering at its input `[e ASC, f ASC, b ASC]`. During the analysis for whether this requirement is satisfied by existing ordering, we need to consider all orderings, equivalences, and constants at the same time.

Following naive algorithm can be followed for this analysis (Please note that algorithm in this PR is more elaborate.)
- Remove constant expressions from the requirement (This converts requirement `[e ASC, f ASC, b ASC]` to `[e ASC, b ASC]`)
- Rewrite requirement such that it uses only representative expression for each distinct equivalent group (This converts requirement `[e ASC, b ASC]` to `[a ASC, b ASC]`).
- Apply same procedures above each of the orderings inside the `OrderingEquivalences` (This converts ordering `[a ASC, b ASC]` to `[a ASC, b ASC]` and `[c ASC, d ASC]` to `[c ASC, d ASC]` no change ).
- Check whether normalized requirement `[a ASC, b ASC]` is satisfied by any of normalized orderings `[a ASC, b ASC]`, `[c ASC, d ASC]`.

As can be seen from the example above. Keeping track of these information separately, is a bit cumbersome.

Also for the user implementing new functionality is a bit hard, and existing APIs are a bit involved also. Such as `ordering_satisfy`, `requirements_compatible`, etc.

I think it is better to unify these information in a single `struct` so that
- We can expose better, and more friendly `API`s from struct.
- Move utils, functions, to method calls
- Keep the invariants in the state (not relying on correct arguments).
- All of the implementations, algorithms resides in a single place, and logic is not scatterred in different files.

TASKS
- [x] Add Unification of these classes. Completed in [#8006](https://github.com/apache/arrow-datafusion/pull/8006)
- [x] https://github.com/apache/arrow-datafusion/pull/8033
- [x] https://github.com/apache/arrow-datafusion/issues/8043
- [x] Preserve all of the valid orderings during merge, see [#8169](https://github.com/apache/arrow-datafusion/pull/8169).
- [x] Add support for complex expression ordering analysis. We should be able to understand `date_bin(ts)` is ordered given `ts` is ordered. See [#8484](https://github.com/apache/arrow-datafusion/pull/8484).
- [ ] https://github.com/apache/arrow-datafusion/issues/8120 to maybe help avoid issues for others upgrading
- [x] https://github.com/apache/arrow-datafusion/pull/8034

### Describe the solution you'd like

_No response_

### Describe alternatives you've considered

_No response_

### Additional context

_No response_

Guida per i contributori

Apri la guida per i contributori

Direzione di ricerca

Inizia esaminando l’attività rimanente non ancora contrassegnata come completata nell’issue #8120 e il lavoro di unificazione completato a cui si fa riferimento nelle PR #8006, #8033, #8169, #8484 e #8034. Traccia come viene utilizzato lo stato unificato di equivalenza e ordinamento, quindi definisci il completamento come la risoluzione del problema rimanente relativo all’upgrade senza perdere il comportamento di ordinamento valido.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Valutazione

Stack tecnologico
rust
Ambito
backend, performance
Tipo di issue
Refactoring
Difficoltà
5/5
Tempo stimato
Più di una settimana
Stato di attività
Ferma
Chiarezza
Da chiarire
Idoneità per principianti
25/100

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.