Skip to content

Commit ec1d74b

Browse files
mhk197robert3005
authored andcommitted
push list_transform lambda bodies into list layout element reads
Signed-off-by: Matt Katz <[email protected]>
1 parent 34f556e commit ec1d74b

4 files changed

Lines changed: 451 additions & 40 deletions

File tree

‎vortex-layout/src/layouts/list/expr.rs‎

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,27 @@
11
// SPDX-License-Identifier: Apache-2.0
22
// SPDX-FileCopyrightText: Copyright the Vortex contributors
33

4+
use std::sync::Arc;
5+
46
use vortex_array::dtype::DType;
57
use vortex_array::dtype::Nullability;
68
use vortex_array::expr::BoundExpression;
9+
use vortex_array::expr::BoundLambda;
710
use vortex_array::expr::bound::not;
11+
use vortex_array::expr::traversal::NodeExt;
12+
use vortex_array::expr::traversal::Transformed;
13+
use vortex_array::expr::traversal::TraversalOrder;
814
use vortex_array::scalar_fn::fns::is_not_null::IsNotNull;
915
use vortex_array::scalar_fn::fns::is_null::IsNull;
1016
use vortex_array::scalar_fn::fns::list_length::ListLength;
17+
use vortex_array::scalar_fn::fns::list_transform::ListTransform;
18+
use vortex_array::scalar_fn::fns::list_transform::ListTransformOptions;
19+
use vortex_error::VortexExpect;
1120
use vortex_error::VortexResult;
1221

22+
use crate::layouts::struct_::Item;
23+
use crate::layouts::struct_::step_into_struct_field;
24+
1325
/// The minimal set of list children an expression needs for evaluation.
1426
///
1527
/// For example:
@@ -47,6 +59,124 @@ pub(super) fn get_necessary_bound_list_children(expr: &BoundExpression) -> ListC
4759
.unwrap_or(ListChildrenNeeded::Validity)
4860
}
4961

62+
/// How a read of the list splits between its elements reader and the lists built over what that
63+
/// reader returns.
64+
pub(super) struct ElementsSplit {
65+
/// Evaluated by the elements reader, once per element.
66+
pub(super) elements: BoundExpression,
67+
/// The expression over the lists.
68+
pub(super) outer: BoundExpression,
69+
/// Whether nothing in `elements` can fail. A fallible one must not see the elements of null
70+
/// lists, which can hold anything.
71+
pub(super) infallible: bool,
72+
}
73+
74+
impl ElementsSplit {
75+
/// Read whole elements and evaluate `expr` over the list.
76+
pub(super) fn whole_elements(element_dtype: &DType, expr: &BoundExpression) -> Self {
77+
Self {
78+
elements: BoundExpression::new_root(element_dtype.clone()),
79+
outer: expr.clone(),
80+
infallible: true,
81+
}
82+
}
83+
}
84+
85+
/// Split an expression that reads the list only through one `list_transform($, λ)` into what the
86+
/// elements reader evaluates and the expression over the lists of its values.
87+
///
88+
/// The elements reader evaluates λ's body, so it reads only the element fields the body uses.
89+
/// The body is bound over its inputs, `{x: element}`, and stepping into `x` puts it over the
90+
/// elements. Several distinct lambdas, or the list also read whole (anything but its validity and
91+
/// lengths), read whole elements.
92+
pub(super) fn split_list_transform(expr: &BoundExpression) -> VortexResult<Option<ElementsSplit>> {
93+
let mut lambdas = Vec::new();
94+
let mut whole = ListChildrenNeeded::Validity;
95+
let mut list_dtype = None;
96+
collect_list_uses(expr, &mut lambdas, &mut whole, &mut list_dtype);
97+
let Some(DType::List(_, nullability)) = list_dtype else {
98+
return Ok(None);
99+
};
100+
let [lambda] = lambdas.as_slice() else {
101+
return Ok(None);
102+
};
103+
if whole == ListChildrenNeeded::All {
104+
return Ok(None);
105+
}
106+
107+
let param = Item::Field(lambda.params().names()[0].clone());
108+
let element = lambda
109+
.params()
110+
.field_by_index(0)
111+
.vortex_expect("list_transform's lambda takes the element");
112+
let elements = step_into_struct_field(lambda.body().clone(), &param, element)?;
113+
let lists = BoundExpression::new_root(DType::List(
114+
Arc::new(elements.dtype().clone()),
115+
nullability,
116+
));
117+
118+
// Every `list_transform($, λ)` is this lambda, and any other `$` is under `is_null` or
119+
// `list_length`, which the lists of λ's values answer alike.
120+
let outer = expr
121+
.clone()
122+
.transform_down(|node| {
123+
Ok(if list_transform_lambda(&node).is_some() || node.is_root() {
124+
Transformed {
125+
value: lists.clone(),
126+
changed: true,
127+
order: TraversalOrder::Skip,
128+
}
129+
} else {
130+
Transformed::no(node)
131+
})
132+
})?
133+
.into_inner();
134+
135+
Ok(Some(ElementsSplit {
136+
elements,
137+
outer,
138+
infallible: lambda.is_infallible(),
139+
}))
140+
}
141+
142+
/// The bound lambda of a `list_transform($, λ)` node.
143+
fn list_transform_lambda(node: &BoundExpression) -> Option<&BoundLambda> {
144+
match node.as_opt::<ListTransform>() {
145+
Some(ListTransformOptions::Bound(lambda)) if node.child(0).is_root() => Some(lambda),
146+
_ => None,
147+
}
148+
}
149+
150+
/// Collect the distinct lambdas of `list_transform($, λ)` nodes and what the rest of the
151+
/// expression needs of the list. `list_dtype` is set once a lambda is found.
152+
fn collect_list_uses(
153+
expr: &BoundExpression,
154+
lambdas: &mut Vec<BoundLambda>,
155+
whole: &mut ListChildrenNeeded,
156+
list_dtype: &mut Option<DType>,
157+
) {
158+
if let Some(lambda) = list_transform_lambda(expr) {
159+
if !lambdas.contains(lambda) {
160+
lambdas.push(lambda.clone());
161+
}
162+
*list_dtype = Some(expr.child(0).dtype().clone());
163+
return;
164+
}
165+
let needs = if is_bound_null_root(expr) {
166+
ListChildrenNeeded::Validity
167+
} else if is_bound_list_length_root(expr) {
168+
ListChildrenNeeded::OffsetsAndValidity
169+
} else if expr.is_root() {
170+
ListChildrenNeeded::All
171+
} else {
172+
for child in expr.children() {
173+
collect_list_uses(child, lambdas, whole, list_dtype);
174+
}
175+
return;
176+
};
177+
*whole = (*whole).max(needs);
178+
}
179+
50180
fn is_bound_null_root(expr: &BoundExpression) -> bool {
51181
(expr.as_scalar().is_some_and(|f| f.is::<IsNull>())
52182
|| expr.as_scalar().is_some_and(|f| f.is::<IsNotNull>()))

0 commit comments

Comments
 (0)