Repository navigation
Open
Labels
PROPOSAL EPICA proposal being discussed that is not yet fully underwayA proposal being discussed that is not yet fully underwayenhancementNew feature or requestNew feature or request
Description
Design document: https://docs.google.com/document/d/1M4mmV7KA1LSj-D-WJA338B4ydlm-8A8D5OPuDE5_SD4/edit
This is a meta issue for improving cost calculations and cost-based optimizations in DataFusion. We already have some statistics collected (mainly from the table sources) and there are estimations for statistics by some of the execution plan nodes, and the overall idea is to improve these as well as possible CBOs.
Main Goals
- Have enough statistics to start nested join optimizations (Implement nested join optimization #3843). This involves being able to estimate the weight of a join side, and do global re-ordering between join sides to minimize the overall cost of parent joins by reducing the output as much as possible at the bottom levels.
- Provide a more reliable static analysis phase for physical execution operators (so that range based pruning/predicate pruning can leverage the existing infrastructure on their implementations)
- What else?
Work in Progress
- A framework for expression boundary analysis (and statistics) #3898
- Implement statistics estimation for
FilterExec#3845 - Determine the expression boundaries of an
ANDconjuction #4158 - Determine the expression boundaries of an OR conjuction #4159
- What else?
Planned
- Estimating join cardinalities when the underlying table does not have any statistics (Never fallback to cartesian product for join estimation when we know the min/max values for columns #3813 (comment)).
- What else?
Future
- Support for histograms, so better value distribution when working with cardinality estimations / filter selectivity. Currently, none of the providers we use can directly pass it to us, so we either have to take a peek at the data or only expose the API for other services (like ballista) which can actually collect it and pass to us.
P.S.: feel free to update the text directly or let me know (and I can update it myself)
Reacted by Daniël Heres, Andy Grove and Andrew Lamb
Metadata
Metadata
Assignees
Labels
PROPOSAL EPICA proposal being discussed that is not yet fully underwayA proposal being discussed that is not yet fully underwayenhancementNew feature or requestNew feature or request
Activity
isidentical commentedon Oct 22, 2022
@alamb @Dandandan @mingmwang I've created the meta/epic issue as we discussed
alamb commentedon Oct 25, 2022
I believe the next step is some sort of design document.
isidentical commentedon Oct 25, 2022
I'd be happy to start one, and if anyone is interested I can also give write access (shoot me your google emails at
isidentical@gmail.com).Dandandan commentedon Oct 25, 2022
Maybe you can share the doc publicly so anyone can do suggestions?
isidentical commentedon Oct 26, 2022
It should be publicly accessible now: https://docs.google.com/document/d/1M4mmV7KA1LSj-D-WJA338B4ydlm-8A8D5OPuDE5_SD4/ (also pinning this to the issue)
It is an overall discovery of the stuff we are doing right now and how they can actually help us in the future (as well as some possible points) but it is in a very early stage. I'd be thrilled to hear about what you are thinking as well as potentially other unexplored areas).
alamb commentedon Oct 26, 2022
I plan to review the doc carefully tomorrow ❤️
isidentical commentedon Oct 26, 2022
Thanks @alamb! I'll also try to talk a bit more about it with real-world examples in tomorrow's meeting from scratch (if we would have the time for that in this meetup, and if I can actually make it there), just in case if anyone else here is planning to attend.
[-][META] Improving cost calculations and cost based optimizations[/-][+]Epic: Improving cost calculations and cost based optimizations[/+][-]Epic: Improving cost calculations and cost based optimizations[/-][+][EPIC] Improving cost calculations and cost based optimizations[/+]alamb commentedon Sep 22, 2025
I filed a ticket to discuss a potentially more general approach to join ordering and access path selection