Skip to content

Commit f73fe6e

Browse files
HarukiMoriartyconnortsui20
authored andcommitted
perf(spatial): keep length on native storage
Signed-off-by: Nemo Yu <[email protected]>
1 parent 3adca63 commit f73fe6e

1 file changed

Lines changed: 179 additions & 25 deletions

File tree

‎vortex-spatial/src/scalar_fn/length.rs‎

Lines changed: 179 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -3,28 +3,50 @@
33

44
//! `ST_Length`: planar (Euclidean) length of native lineal geometries.
55
6-
use geo::Euclidean;
7-
use geo::Length;
8-
use geo_types::Geometry;
96
use vortex_array::ArrayRef;
7+
use vortex_array::ExecutionCtx;
8+
use vortex_array::IntoArray;
9+
use vortex_array::arrays::ConstantArray;
10+
use vortex_array::arrays::ExtensionArray;
11+
use vortex_array::arrays::ListArray;
12+
use vortex_array::arrays::ListViewArray;
13+
use vortex_array::arrays::PrimitiveArray;
1014
use vortex_array::arrays::ScalarFnArray;
15+
use vortex_array::arrays::StructArray;
16+
use vortex_array::arrays::extension::ExtensionArrayExt;
17+
use vortex_array::arrays::list::ListArraySlotsExt;
18+
use vortex_array::arrays::listview::list_from_list_view;
19+
use vortex_array::builtins::ArrayBuiltins;
1120
use vortex_array::dtype::DType;
21+
use vortex_array::dtype::Nullability;
22+
use vortex_array::dtype::PType;
23+
use vortex_array::expr::Expression;
24+
use vortex_array::expr::union_child_validities;
25+
use vortex_array::scalar_fn::Arity;
26+
use vortex_array::scalar_fn::ChildName;
1227
use vortex_array::scalar_fn::EmptyOptions;
28+
use vortex_array::scalar_fn::ExecutionArgs;
1329
use vortex_array::scalar_fn::ScalarFnId;
30+
use vortex_array::scalar_fn::ScalarFnVTable;
1431
use vortex_array::scalar_fn::TypedScalarFnInstance;
15-
use vortex_array::scalar_fn::unstable::row::RowFn;
16-
use vortex_array::scalar_fn::unstable::row::RowVisitor;
32+
use vortex_array::validity::Validity;
33+
use vortex_buffer::Buffer;
1734
use vortex_error::VortexResult;
1835
use vortex_error::vortex_ensure;
36+
use vortex_error::vortex_err;
1937
use vortex_session::VortexSession;
2038
use vortex_session::registry::CachedId;
2139

2240
use crate::extension::LineString;
2341
use crate::extension::MultiLineString;
24-
use crate::scalar_fn::row::GeometryRow;
42+
use crate::extension::coordinate::ordinates;
43+
use crate::extension::flatten_row_offsets;
44+
use crate::scalar_fn::execute::Execution;
45+
use crate::scalar_fn::execute::Operand;
46+
use crate::scalar_fn::execute::dispatch_unary;
2547

2648
/// Validate the native lineal operand accepted by `ST_Length`.
27-
fn validate_length_operand(dtypes: &[DType]) -> VortexResult<()> {
49+
fn validate_length_operands(dtypes: &[DType]) -> VortexResult<()> {
2850
vortex_ensure!(
2951
dtypes.len() == 1,
3052
"spatial: length requires exactly one lineal operand, got {}",
@@ -40,16 +62,89 @@ fn validate_length_operand(dtypes: &[DType]) -> VortexResult<()> {
4062
Ok(())
4163
}
4264

43-
fn euclidean_length(geometry: &Geometry<f64>) -> f64 {
44-
match geometry {
45-
Geometry::LineString(line) => Euclidean.length(line),
46-
Geometry::MultiLineString(lines) => Euclidean.length(lines),
47-
_ => unreachable!("length dispatch validated a native lineal geometry"),
65+
fn list_offsets(list: &ListArray, ctx: &mut ExecutionCtx) -> VortexResult<Vec<usize>> {
66+
list.offsets()
67+
.clone()
68+
.cast(DType::Primitive(PType::U64, Nullability::NonNullable))?
69+
.execute::<Buffer<u64>>(ctx)?
70+
.iter()
71+
.map(|&offset| {
72+
usize::try_from(offset).map_err(|_| vortex_err!("spatial: list offset exceeds usize"))
73+
})
74+
.collect()
75+
}
76+
77+
fn linestring_length(xs: &[f64], ys: &[f64]) -> f64 {
78+
xs.windows(2)
79+
.zip(ys.windows(2))
80+
.map(|(x, y)| (x[1] - x[0]).hypot(y[1] - y[0]))
81+
.fold(0.0, |length, segment| length + segment)
82+
}
83+
84+
fn linestring_lengths(storage: ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<Buffer<f64>> {
85+
let (row_offsets, coords) = flatten_row_offsets(storage, ctx)?;
86+
let xs = ordinates(&coords, "x", ctx)?;
87+
let ys = ordinates(&coords, "y", ctx)?;
88+
Ok(Buffer::from_iter(row_offsets.windows(2).map(|offsets| {
89+
linestring_length(&xs[offsets[0]..offsets[1]], &ys[offsets[0]..offsets[1]])
90+
})))
91+
}
92+
93+
fn multilinestring_lengths(storage: ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<Buffer<f64>> {
94+
let rows = list_from_list_view(storage.execute::<ListViewArray>(ctx)?, ctx)?;
95+
let row_offsets = list_offsets(&rows, ctx)?;
96+
let lines = list_from_list_view(rows.elements().clone().execute::<ListViewArray>(ctx)?, ctx)?;
97+
let line_offsets = list_offsets(&lines, ctx)?;
98+
let coords = lines.elements().clone().execute::<StructArray>(ctx)?;
99+
let xs = ordinates(&coords, "x", ctx)?;
100+
let ys = ordinates(&coords, "y", ctx)?;
101+
102+
Ok(Buffer::from_iter(row_offsets.windows(2).map(|row| {
103+
line_offsets[row[0]..=row[1]]
104+
.windows(2)
105+
.map(|line| linestring_length(&xs[line[0]..line[1]], &ys[line[0]..line[1]]))
106+
.fold(0.0, |length, line| length + line)
107+
})))
108+
}
109+
110+
/// Compute planar lengths directly over native lineal offsets and coordinate buffers.
111+
fn length_array(
112+
array: ArrayRef,
113+
validity: Validity,
114+
ctx: &mut ExecutionCtx,
115+
) -> VortexResult<ArrayRef> {
116+
let is_linestring = array
117+
.dtype()
118+
.as_extension_opt()
119+
.is_some_and(|extension| extension.is::<LineString>());
120+
let storage = array
121+
.execute::<ExtensionArray>(ctx)?
122+
.storage_array()
123+
.clone();
124+
let lengths = if is_linestring {
125+
linestring_lengths(storage, ctx)?
126+
} else {
127+
multilinestring_lengths(storage, ctx)?
128+
};
129+
Ok(PrimitiveArray::new(lengths, validity).into_array())
130+
}
131+
132+
/// Execute length after shared constant/column and null dispatch.
133+
fn execute_length(
134+
execution: Execution<1, Validity>,
135+
ctx: &mut ExecutionCtx,
136+
) -> VortexResult<ArrayRef> {
137+
match execution.operands {
138+
[Operand::Constant(line)] => {
139+
let validity = Validity::from(execution.nullability);
140+
let one = length_array(ConstantArray::new(line, 1).into_array(), validity, ctx)?;
141+
Ok(ConstantArray::new(one.execute_scalar(0, ctx)?, execution.len).into_array())
142+
}
143+
[Operand::Column(lines)] => length_array(lines, execution.valid, ctx),
48144
}
49145
}
50146

51-
/// Planar (Euclidean) `ST_Length` (no geodesic correction) of native `LineString` and
52-
/// `MultiLineString` geometries.
147+
/// Planar (Euclidean) `ST_Length` (no geodesic correction) of native lineal geometries.
53148
#[derive(Debug, Clone, Default, PartialEq, Eq, Hash)]
54149
pub struct SpatialLength;
55150

@@ -63,12 +158,9 @@ impl SpatialLength {
63158
}
64159
}
65160

66-
impl RowFn for SpatialLength {
161+
impl ScalarFnVTable for SpatialLength {
67162
type Options = EmptyOptions;
68163

69-
const ARG_NAMES: &'static [&'static str] = &["geometry"];
70-
const INFALLIBLE: bool = true;
71-
72164
fn id(&self) -> ScalarFnId {
73165
static ID: CachedId = CachedId::new("vortex.st.length");
74166
*ID
@@ -82,14 +174,51 @@ impl RowFn for SpatialLength {
82174
Ok(EmptyOptions)
83175
}
84176

85-
fn dispatch<V: RowVisitor>(
177+
fn arity(&self, _: &Self::Options) -> Arity {
178+
Arity::Exact(1)
179+
}
180+
181+
fn child_name(&self, _: &Self::Options, child_idx: usize) -> ChildName {
182+
match child_idx {
183+
0 => ChildName::from("geometry"),
184+
_ => unreachable!("length has exactly one child"),
185+
}
186+
}
187+
188+
fn return_dtype(&self, _: &Self::Options, dtypes: &[DType]) -> VortexResult<DType> {
189+
validate_length_operands(dtypes)?;
190+
Ok(DType::Primitive(PType::F64, dtypes[0].nullability()))
191+
}
192+
193+
fn execute(
194+
&self,
195+
_: &Self::Options,
196+
args: &dyn ExecutionArgs,
197+
ctx: &mut ExecutionCtx,
198+
) -> VortexResult<ArrayRef> {
199+
let array = args.get(0)?;
200+
dispatch_unary(
201+
&array,
202+
DType::Primitive(PType::F64, array.dtype().nullability()),
203+
execute_length,
204+
ctx,
205+
)
206+
}
207+
208+
fn validity(
86209
&self,
87-
_options: &Self::Options,
88-
args: &[DType],
89-
visitor: V,
90-
) -> VortexResult<V::VisitResult> {
91-
validate_length_operand(args)?;
92-
visitor.visit::<(GeometryRow,), f64>(|(geometry,)| euclidean_length(geometry))
210+
_: &Self::Options,
211+
expression: &Expression,
212+
) -> VortexResult<Option<Expression>> {
213+
union_child_validities(expression)
214+
}
215+
216+
fn is_strict(&self, _: &Self::Options) -> bool {
217+
true
218+
}
219+
220+
fn is_infallible(&self, _: &Self::Options) -> bool {
221+
true
93222
}
94223
}
95224

@@ -166,6 +295,31 @@ mod tests {
166295
Ok(())
167296
}
168297

298+
#[test]
299+
fn propagates_nullable_multilinestring_rows() -> VortexResult<()> {
300+
let session = vortex_array::array_session();
301+
let mut ctx = session.create_execution_ctx();
302+
let lines = MaskedArray::try_new(
303+
multilinestring_column(vec![
304+
vec![vec![(0.0, 0.0), (3.0, 4.0)]],
305+
vec![vec![(0.0, 0.0), (1.0, 1.0)]],
306+
vec![vec![(0.0, 0.0), (0.0, 5.0)]],
307+
])?,
308+
Validity::from_iter([true, false, true]),
309+
)?
310+
.into_array();
311+
312+
let expected = PrimitiveArray::new(
313+
vec![5.0, 0.0, 5.0],
314+
Validity::from_iter([true, false, true]),
315+
)
316+
.into_array();
317+
let lengths = SpatialLength::try_new(lines)?.into_array();
318+
319+
assert_arrays_eq!(lengths, expected, &mut ctx);
320+
Ok(())
321+
}
322+
169323
#[test]
170324
fn constant_is_computed_once_and_remains_constant() -> VortexResult<()> {
171325
let session = vortex_array::array_session();

0 commit comments

Comments
 (0)