Skip to content

Commit fd43ebd

Browse files
feat: support bound expressions in partitioning (#9157)
This is done before using `BoundExpression` in layouts due a lock of partitioning causing a perf regression ## Summary - add identity-keyed traversal, annotation, and labeling support for `BoundExpression` - add `partition_bound` / `partition_bound_annotations` and a bound partition result - keep partition roots and child expressions bound so downstream callers preserve shared tree identity - use `ExactBoundExpr` for bound analysis maps so lazy schema dtypes are not structurally hashed Signed-off-by: Joe Isaacs <[email protected]>
1 parent 876996f commit fd43ebd

6 files changed

Lines changed: 798 additions & 38 deletions

File tree

‎vortex-array/src/expr/analysis/annotation.rs‎

Lines changed: 140 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,10 @@ use vortex_error::VortexResult;
88
use vortex_utils::aliases::hash_map::HashMap;
99
use vortex_utils::aliases::hash_set::HashSet;
1010

11+
use crate::expr::BoundExpression;
12+
use crate::expr::ExactBoundExpr;
1113
use crate::expr::Expression;
14+
use crate::expr::traversal::Node;
1215
use crate::expr::traversal::NodeExt;
1316
use crate::expr::traversal::NodeVisitor;
1417
use crate::expr::traversal::TraversalOrder;
@@ -17,28 +20,38 @@ pub trait Annotation: Clone + Hash + Eq {}
1720

1821
impl<A> Annotation for A where A: Clone + Hash + Eq {}
1922

20-
pub trait AnnotationFn: Fn(&Expression) -> Vec<Self::Annotation> {
23+
pub trait AnnotationFn<N = Expression>: Fn(&N) -> Vec<Self::Annotation> {
2124
type Annotation: Annotation;
2225
}
2326

24-
impl<A, F> AnnotationFn for F
27+
impl<N, A, F> AnnotationFn<N> for F
2528
where
2629
A: Annotation,
27-
F: Fn(&Expression) -> Vec<A>,
30+
F: Fn(&N) -> Vec<A>,
2831
{
2932
type Annotation = A;
3033
}
3134

32-
pub type Annotations<'a, A> = HashMap<&'a Expression, HashSet<A>>;
35+
pub type Annotations<'a, A, N = Expression> = HashMap<&'a N, HashSet<A>>;
36+
37+
/// Annotations keyed by bound-tree identity.
38+
///
39+
/// Identity keys avoid structurally hashing every node's dtype. That matters when a bound root
40+
/// carries a lazy schema whose structural hash would deserialize every field.
41+
pub type BoundAnnotations<A> = HashMap<ExactBoundExpr, HashSet<A>>;
3342

3443
/// Walk the expression tree and annotate each expression with zero or more annotations.
3544
///
3645
/// Returns a map of each expression to all annotations that any of its descendent (child)
3746
/// expressions are annotated with.
38-
pub fn descendent_annotations<A: AnnotationFn>(
39-
expr: &Expression,
47+
pub fn descendent_annotations<'a, N, A>(
48+
expr: &'a N,
4049
annotate: A,
41-
) -> Annotations<'_, A::Annotation> {
50+
) -> Annotations<'a, A::Annotation, N>
51+
where
52+
N: Node + Eq + Hash,
53+
A: AnnotationFn<N>,
54+
{
4255
let mut visitor = AnnotationVisitor {
4356
annotations: Default::default(),
4457
annotate,
@@ -53,10 +66,11 @@ pub fn descendent_annotations<A: AnnotationFn>(
5366
///
5467
/// Returns a map of each expression to all annotations. Annotations of
5568
/// children are not propagated to parents.
56-
pub fn direct_annotations<A: AnnotationFn>(
57-
expr: &Expression,
58-
annotate: A,
59-
) -> Annotations<'_, A::Annotation> {
69+
pub fn direct_annotations<'a, N, A>(expr: &'a N, annotate: A) -> Annotations<'a, A::Annotation, N>
70+
where
71+
N: Node + Eq + Hash,
72+
A: AnnotationFn<N>,
73+
{
6074
let mut visitor = AnnotationVisitor {
6175
annotations: Default::default(),
6276
annotate,
@@ -66,14 +80,66 @@ pub fn direct_annotations<A: AnnotationFn>(
6680
visitor.annotations
6781
}
6882

69-
struct AnnotationVisitor<'a, A: AnnotationFn> {
70-
annotations: Annotations<'a, A::Annotation>,
83+
/// Annotate a bound expression and propagate each annotation to its ancestors.
84+
///
85+
/// Unlike [`descendent_annotations`], this uses [`ExactBoundExpr`] keys to preserve the cheap
86+
/// identity semantics of an already-bound tree.
87+
pub fn descendent_bound_annotations<A>(
88+
expr: &BoundExpression,
89+
annotate: A,
90+
) -> BoundAnnotations<A::Annotation>
91+
where
92+
A: AnnotationFn<BoundExpression>,
93+
{
94+
bound_annotations(expr, annotate, true)
95+
}
96+
97+
/// Annotate each bound-expression node without propagating annotations to its ancestors.
98+
///
99+
/// The returned map uses [`ExactBoundExpr`] keys so lookups do not structurally hash node dtypes.
100+
pub fn direct_bound_annotations<A>(
101+
expr: &BoundExpression,
102+
annotate: A,
103+
) -> BoundAnnotations<A::Annotation>
104+
where
105+
A: AnnotationFn<BoundExpression>,
106+
{
107+
bound_annotations(expr, annotate, false)
108+
}
109+
110+
fn bound_annotations<A>(
111+
expr: &BoundExpression,
112+
annotate: A,
113+
propagate_up: bool,
114+
) -> BoundAnnotations<A::Annotation>
115+
where
116+
A: AnnotationFn<BoundExpression>,
117+
{
118+
let mut visitor = BoundAnnotationVisitor {
119+
annotations: Default::default(),
120+
annotate,
121+
propagate_up,
122+
};
123+
expr.accept(&mut visitor).vortex_expect("Infallible");
124+
visitor.annotations
125+
}
126+
127+
struct AnnotationVisitor<'a, N, A>
128+
where
129+
N: Node + Eq + Hash,
130+
A: AnnotationFn<N>,
131+
{
132+
annotations: Annotations<'a, A::Annotation, N>,
71133
annotate: A,
72134
propagate_up: bool,
73135
}
74136

75-
impl<'a, A: AnnotationFn> NodeVisitor<'a> for AnnotationVisitor<'a, A> {
76-
type NodeTy = Expression;
137+
impl<'a, N, A> NodeVisitor<'a> for AnnotationVisitor<'a, N, A>
138+
where
139+
N: Node + Eq + Hash,
140+
A: AnnotationFn<N>,
141+
{
142+
type NodeTy = N;
77143

78144
fn visit_down(&mut self, node: &'a Self::NodeTy) -> VortexResult<TraversalOrder> {
79145
let annotations = (self.annotate)(node);
@@ -89,20 +155,74 @@ impl<'a, A: AnnotationFn> NodeVisitor<'a> for AnnotationVisitor<'a, A> {
89155
}
90156
}
91157

92-
fn visit_up(&mut self, node: &'a Expression) -> VortexResult<TraversalOrder> {
158+
fn visit_up(&mut self, node: &'a N) -> VortexResult<TraversalOrder> {
93159
if !self.propagate_up {
94160
return Ok(TraversalOrder::Continue);
95161
}
162+
let child_annotations = node.iter_children(|children| {
163+
children
164+
.filter_map(|child| self.annotations.get(child).cloned())
165+
.collect::<Vec<_>>()
166+
});
167+
168+
let annotations = self.annotations.entry(node).or_default();
169+
child_annotations
170+
.into_iter()
171+
.for_each(|ps| annotations.extend(ps.iter().cloned()));
172+
173+
Ok(TraversalOrder::Continue)
174+
}
175+
}
176+
177+
struct BoundAnnotationVisitor<A>
178+
where
179+
A: AnnotationFn<BoundExpression>,
180+
{
181+
annotations: BoundAnnotations<A::Annotation>,
182+
annotate: A,
183+
propagate_up: bool,
184+
}
185+
186+
impl<'a, A> NodeVisitor<'a> for BoundAnnotationVisitor<A>
187+
where
188+
A: AnnotationFn<BoundExpression>,
189+
{
190+
type NodeTy = BoundExpression;
191+
192+
fn visit_down(&mut self, node: &'a Self::NodeTy) -> VortexResult<TraversalOrder> {
193+
let annotations = (self.annotate)(node);
194+
if annotations.is_empty() {
195+
return Ok(TraversalOrder::Continue);
196+
}
197+
198+
self.annotations
199+
.entry(ExactBoundExpr(node.clone()))
200+
.or_default()
201+
.extend(annotations);
202+
Ok(TraversalOrder::Skip)
203+
}
204+
205+
fn visit_up(&mut self, node: &'a Self::NodeTy) -> VortexResult<TraversalOrder> {
206+
if !self.propagate_up {
207+
return Ok(TraversalOrder::Continue);
208+
}
209+
96210
let child_annotations = node
97211
.children()
98212
.iter()
99-
.filter_map(|c| self.annotations.get(c).cloned())
213+
.filter_map(|child| {
214+
self.annotations
215+
.get(&ExactBoundExpr(child.clone()))
216+
.cloned()
217+
})
100218
.collect::<Vec<_>>();
101-
102-
let annotations = self.annotations.entry(node).or_default();
219+
let annotations = self
220+
.annotations
221+
.entry(ExactBoundExpr(node.clone()))
222+
.or_default();
103223
child_annotations
104224
.into_iter()
105-
.for_each(|ps| annotations.extend(ps.iter().cloned()));
225+
.for_each(|child| annotations.extend(child));
106226

107227
Ok(TraversalOrder::Continue)
108228
}

‎vortex-array/src/expr/analysis/immediate_access.rs‎

Lines changed: 29 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@ use vortex_utils::aliases::hash_set::HashSet;
66

77
use crate::dtype::FieldName;
88
use crate::dtype::StructFields;
9+
use crate::expr::BoundExpression;
910
use crate::expr::Expression;
1011
use crate::expr::analysis::AnnotationFn;
1112
use crate::expr::analysis::Annotations;
@@ -43,7 +44,7 @@ pub type FieldAccesses<'a> = Annotations<'a, FieldName>;
4344
/// - The full expression has free fields `{a, d}` (not `b`, only top-level fields are tracked).
4445
pub fn make_free_field_annotator(
4546
scope: &StructFields,
46-
) -> impl AnnotationFn<Annotation = FieldName> {
47+
) -> impl AnnotationFn<Expression, Annotation = FieldName> {
4748
move |expr: &Expression| {
4849
if let Some(selection) = expr.as_opt::<Select>() {
4950
if expr.child(0).is::<Root>() {
@@ -65,6 +66,33 @@ pub fn make_free_field_annotator(
6566
}
6667
}
6768

69+
/// Returns the free top-level fields for bound expression nodes.
70+
pub fn make_bound_free_field_annotator(
71+
scope: &StructFields,
72+
) -> impl AnnotationFn<BoundExpression, Annotation = FieldName> {
73+
move |expr: &BoundExpression| {
74+
let Some(scalar_fn) = expr.as_scalar() else {
75+
return scope.names().iter().cloned().collect();
76+
};
77+
78+
if let Some(selection) = scalar_fn.as_opt::<Select>() {
79+
if expr.children()[0].is_root() {
80+
return selection
81+
.normalize_to_included_fields(scope.names())
82+
.vortex_expect("Select fields must be valid for scope")
83+
.into_iter()
84+
.collect();
85+
}
86+
} else if let Some(field_name) = scalar_fn.as_opt::<GetItem>()
87+
&& expr.children()[0].is_root()
88+
{
89+
return vec![field_name.clone()];
90+
}
91+
92+
vec![]
93+
}
94+
}
95+
6896
/// For all subexpressions in an expression, find the fields that are accessed directly from the
6997
/// scope, but not any fields in those fields
7098
/// e.g. scope = {a: {b: .., c: ..}, d: ..}, expr = root().a.b + root().d accesses {a,d} (not b).

0 commit comments

Comments
 (0)