|
1 | 1 | // SPDX-License-Identifier: Apache-2.0 |
2 | 2 | // SPDX-FileCopyrightText: Copyright the Vortex contributors |
3 | 3 |
|
| 4 | +use std::sync::Arc; |
| 5 | + |
4 | 6 | use vortex_array::dtype::DType; |
5 | 7 | use vortex_array::dtype::Nullability; |
6 | 8 | use vortex_array::expr::BoundExpression; |
| 9 | +use vortex_array::expr::BoundLambda; |
7 | 10 | 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; |
8 | 14 | use vortex_array::scalar_fn::fns::is_not_null::IsNotNull; |
9 | 15 | use vortex_array::scalar_fn::fns::is_null::IsNull; |
10 | 16 | 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; |
11 | 20 | use vortex_error::VortexResult; |
12 | 21 |
|
| 22 | +use crate::layouts::struct_::Item; |
| 23 | +use crate::layouts::struct_::step_into_struct_field; |
| 24 | + |
13 | 25 | /// The minimal set of list children an expression needs for evaluation. |
14 | 26 | /// |
15 | 27 | /// For example: |
@@ -47,6 +59,124 @@ pub(super) fn get_necessary_bound_list_children(expr: &BoundExpression) -> ListC |
47 | 59 | .unwrap_or(ListChildrenNeeded::Validity) |
48 | 60 | } |
49 | 61 |
|
| 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(), ¶m, 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 | + |
50 | 180 | fn is_bound_null_root(expr: &BoundExpression) -> bool { |
51 | 181 | (expr.as_scalar().is_some_and(|f| f.is::<IsNull>()) |
52 | 182 | || expr.as_scalar().is_some_and(|f| f.is::<IsNotNull>())) |
|
0 commit comments