Repository navigation
[DISCUSSION] Extending Partitioning to Support More Variants #21992
Description
Activity
Great description. The exact use case at DataDog. We plan to use this a lot.
Reacted by Gene BordegarayI have added a draft PR #22002 which shows my vision for what partitioning can look like going forward and how this will apply to an optimization like dynamic filter routing. The API design was done by me but implementation details by AI and is not meant to be a mergeable PR. I provided a description of the API, would love any suggestions/ideas on this general approach.
I separated it into 4 commits to show the logical progression of the implementation:
- Adding Range partitioning variant that models what a custom partitioning trait would look like
- Introduce the general partitioning trait using this model and have range partitioning implement it
- Have file preserved partitioning use range partitioning rather than false advertising hash
- Route dynamic filters using partitioning compatibility and create partitioning-local filters when range partitioned
I think it would also help to decide sooner rather than later if we want a general partitioning trait, or if we are just going to hard code Range Partitioning. I think either could work.
If we are going to go with a trait, it might be good to declare that we eventually want to shoot to remove all special cases for hash partitioning 🤔
I think it would also help to decide sooner rather than later if we want a general partitioning trait, or if we are just going to hard code Range Partitioning. I think either could work.
I vote for a general partitioning trait
I'm not sure if it should be a trait or an eum. I generally prefer an explicit enum if the trait doesn't generalize well. E.g. if we can't point to an obvious 3rd use case for the trait that an external system could conceivably implement and where everything would work for them, I fear a trait is the wrong choice.
@NGA-TRAN could you share why you prefer a trait to an enum here? Maybe you know some additional partitioning strategies that are commonly used in the database world that I don't know of.
@adriangb : Can you provide an example of enum? If it covers our use cases, we are happy to go with it.
Currently, our range come from 2 columns (or 2 expressions). For example (time, int_val). So we can have these ranges:
- ( [2026.05.01 - 2026.05.07] , [1 - 100] )
- ( [2026.05.01 - 2026.05.07] , [101 - 200] )
- ...
- ( [2026.05.08 - 2026.05.15] , [1 - 500] )
- ( [2026.05.08 - 2026.05.15] , [501 - 1000] )
- ...
As long as they do not overlaps, they are considered as ranges. We can definitely map those into simple ranges or indexes and use those simple ones in DF instead.
I don't know that the enum is any different than the trait in terms of representation. I.e. if we can represent it as a trait we can represent it as an enum. The question is more if we want to hard code all of the handled cases or leave it open for users to add more down the road.
I'd defer to @gene-bordegaray as to what an enum version would look like but I think something like this:
pub enum Partitioning { RoundRobinBatch(usize), Hash { exprs: Vec<Arc<dyn PhysicalExpr>>, partition_count: usize, }, Range { exprs: Vec<Arc<dyn PhysicalExpr>>, partitions: Vec<RangePartition>, }, } pub struct RangePartition { /// One interval per `Range.exprs` entry. /// /// For exprs = [time, int_val], this can represent: /// time in [2026-05-01, 2026-05-07] /// AND int_val in [1, 100] pub bounds: Vec<RangeInterval>, } pub struct RangeInterval { pub lower: Option<RangeBound>, pub upper: Option<RangeBound>, } pub struct RangeBound { pub value: ScalarValue, pub inclusive: bool, }
Reacted by Gabriel and Andrew LambThe enum Gene proposed looks good. As long as there are PhysicalExpr, it will work
Range { exprs: Vec<Arc<dyn PhysicalExpr>>, partitions: Vec<RangePartition>, },
I am in favor of a general trait as the long-term goal of this work. I think allowing users to implement their own type of partitioning will make DF more powerful in production use cases as I am sure that there will be instances of partitioning that are not captured in
HashorRangepartitioning (just asHashdid not fully work for us). Off the top of my head something like aValuepartitioning would also be useful:p0: col in ('a', 'd') p1: col in ('b') p2: col in ('c')Because of this I think providing another extendible point for people (the trait) will be very high value even if worth the extra effort.
With this said I do think we can create mergeable commits by extending the enum now by supporting
Rangepartitioning as @adriangb has described but model it after what our trait will look like. We can treat the trait as the final goal but letRangehelp us define the requirements for that as we pseudo-implement what that trait will look like.If we are going to go with a trait, it might be good to declare that we eventually want to shoot to remove all special cases for hash partitioning 🤔
And along with this, yes I agree here that we should shoot to encapsulate all partitioning logic behind this trait and no special cases. The optimizer rules and other things should ask if two partitioning are compatible or satisfy one another, not just "is this Hash partitioned" 👍
I see this path as actually being more intuitive once done well.
Reacted by Nga Tran and Stu HoodI think that partitioning is likely to become relevant for us in the next few weeks, and our schedule should finally be clearing up to try and get some of our team involved with helping.
We're very likely to be doing either Range or N-dimensional partitioning. AFAICT though, Range is sufficient to represent N-dimensional partitioning (with a physical optimizer rule running before EnforceDistribution), because you can declare each table to be partitioned on the relevant 1-dimensional join key, as a subset of the N-dimensions.
So, in practice, it doesn't seem like it would be worth actually introducing knowledge of multi-dimensional ranges here: a Range type would be enough.
Reacted by Gene BordegarayWe spoke about this topic the other day in person when we were at the NYC meetup
I believe @gene-bordegaray 's usecase will be satisfied if we can represent range partitioning that is represented like
[expr]:[[ranges]]
For example, partitioning on
datewould be represented like[date]: [
[[2021-01-01, 2021-12-32]]
[[2022-01-01, 2022-12-32]],
...
]
partitioning on
date, citywould be represented like[date, city]: [
[[2021-01-01, 2021-12-32], [Allston, Boston]]
[[2021-01-01, 2021-12-32], [Boston, NYC]]
[2022-01-01, 2022-12-32], [Allston, Boston]]
[2022-01-01, 2022-12-32], [Boston, NYC]]
...
]
Some TBD details are:
- How to ensure the entire range is covered (e.g. what range in the above example handles 1970-01-01)?
In my experience, range partitioning is usually represented with only the partitioning points, which addresses the infinite end cap issue, and guarantees that everything is covered. Each point is exclusive for the range to the left side of the point and inclusive for the range to the right side of the point. So your example would be more like:
To create three ranges (infinitely small to
2021-01-01, between2021-01-01and2022-12-32, and2022-12-32to infinitely large)`[date]`: [ [2021-01-01] [2022-12-32], ... ]And the date + city example would be:
`[date, city]`: [ [2021-01-01, Allston], [2021-01-01, Boston], [2022-12-32, Allston], [2022-12-32, NYC], ... ](or something).
Reacted by Andrew Lamb, Nga Tran and Gene BordegarayTo keep everyone else in this thread up-to-date, we had some discussions this week regarding this topic and have come up with a concrete plan. We are going to start with adding a enum variant for
ExprPartitioning(name up for debate) rather than introducing a general trait immediately. @alamb described the concept and representation of this well, so I won't reexplain that here.For implementation, the first PR will be purely mechanical. This will add a
Expr(or similar) variant to the existing physicalPartitioningenum, along with the supporting types, but just throw "not implemented" at callsites. This will introduce the concept and give a good idea of the API methods we will need to represent partitioning well.This will then be followed up with implementing the partitioning features based on the callsites in follow-up PRs, with one of these beeing the dynamic filter routing.
The goal is still to model this in a way that can evolve into a general partitioning abstraction if needed.
I will make the mechanical PR soon and ping here 👍
Reacted by Nga Tran and Alessandro SolimandoReacted by Nga Tran and Stu Hood9 remaining items
- added a commit that references this issue
on May 29, 2026 - added a commit that references this issue
on Jun 5, 2026 - added a commit that references this issue
on Jun 10, 2026 - added a commit that references this issue
on Jun 11, 2026 - added a commit that references this issue
on Jun 23, 2026 Given #22395 maybe we should close this issue and track the work there
sounds good to me
I’d like to restart the partitioning side of this discussion separately from the dynamic-filter PRs and threads (see #21207 for more background)
The main issue seems to be that DataFusion cannot always represent the physical partitioning that some data sources actually have. In our case, range-partitioned data has had to claim
Partitioning::Hash, which lets us avoid repartitioning but makes later optimizer and dynamic-filter decisions brittle due to this false advertisement.Today we are in this scenario:
Those are not the same partitioning scheme.
The general goal should be that DataFusion should be able to describe physical partitioning truthfully, be able to compare two partitionings for compatibility, and use that information only when compatibility is proven.
This is well shown in dynamic filtering:
These are compatible as every partition X on the build side is compatible with partition X on the probe side. With this information, optimizations can safely use partition-local behavior:
A possible direction is to evolve Partitioning toward an extensible abstraction, such as a
PhysicalPartitioningtrait, and add range partitioning as the first use case. Longer term, built-ins like hash partitioning could move behind the same abstraction.This would give us a cleaner foundation for:
Does this direction seem interesting to others in the community nd any thoughts on this proposal?
cc: @NGA-TRAN @alamb @jayshrivastava @gabotechs @adriangb