use std::sync::Arc;
use datafusion::arrow::array::{Array, ArrayRef, Float64Array, Int64Array, ListArray, StructArray};
use datafusion::arrow::buffer::OffsetBuffer;
use datafusion::arrow::datatypes::{DataType, Field, Fields};
use datafusion::common::{exec_err, Result, ScalarValue};
use datafusion::logical_expr::function::{AccumulatorArgs, StateFieldsArgs};
use datafusion::logical_expr::{Accumulator, AggregateUDF, AggregateUDFImpl, Signature, Volatility};
use downsampling::lttb_indices;
fn point_fields() -> Fields {
Fields::from(vec![
Field::new("ts", DataType::Int64, true),
Field::new("value", DataType::Float64, true),
])
}
fn return_type() -> DataType {
DataType::List(Arc::new(Field::new("item", DataType::Struct(point_fields()), true)))
}
#[derive(Debug, PartialEq, Eq, Hash)]
pub struct Lttb {
signature: Signature,
}
impl Default for Lttb {
fn default() -> Self {
Self {
signature: Signature::exact(
vec![DataType::Int64, DataType::Float64, DataType::Int64],
Volatility::Immutable,
),
}
}
}
impl AggregateUDFImpl for Lttb {
fn name(&self) -> &str {
"lttb"
}
fn signature(&self) -> &Signature {
&self.signature
}
fn return_type(&self, _args: &[DataType]) -> Result<DataType> {
Ok(return_type())
}
fn accumulator(&self, _args: AccumulatorArgs) -> Result<Box<dyn Accumulator>> {
Ok(Box::new(LttbAccumulator::default()))
}
fn state_fields(&self, args: StateFieldsArgs) -> Result<Vec<Arc<Field>>> {
Ok(vec![
Arc::new(Field::new(
format!("{}_ts", args.name),
DataType::List(Arc::new(Field::new("item", DataType::Int64, true))),
true,
)),
Arc::new(Field::new(
format!("{}_vals", args.name),
DataType::List(Arc::new(Field::new("item", DataType::Float64, true))),
true,
)),
Arc::new(Field::new(format!("{}_target", args.name), DataType::Int64, true)),
])
}
}
pub fn lttb_udaf() -> AggregateUDF {
AggregateUDF::from(Lttb::default())
}
#[derive(Debug, Default)]
struct LttbAccumulator {
ts: Vec<i64>,
vals: Vec<f64>,
target: Option<i64>,
}
impl Accumulator for LttbAccumulator {
fn update_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
let (Some(ts), Some(vals)) = (
values[0].as_any().downcast_ref::<Int64Array>(),
values[1].as_any().downcast_ref::<Float64Array>(),
) else {
return exec_err!("lttb expects (ts Int64, value Float64, target Int64)");
};
let Some(tgt) = values[2].as_any().downcast_ref::<Int64Array>() else {
return exec_err!("lttb target must be an Int64 literal");
};
if self.target.is_none() && !tgt.is_empty() && tgt.null_count() < tgt.len() {
self.target = Some(tgt.value(0));
}
for i in 0..ts.len() {
if ts.is_null(i) || vals.is_null(i) {
continue; }
self.ts.push(ts.value(i));
self.vals.push(vals.value(i));
}
Ok(())
}
fn merge_batch(&mut self, states: &[ArrayRef]) -> Result<()> {
let (Some(ts_l), Some(vals_l), Some(tgt)) = (
states[0].as_any().downcast_ref::<ListArray>(),
states[1].as_any().downcast_ref::<ListArray>(),
states[2].as_any().downcast_ref::<Int64Array>(),
) else {
return exec_err!("lttb merge received an unexpected state shape");
};
for row in 0..ts_l.len() {
if ts_l.is_null(row) {
continue;
}
let (t, v) = (ts_l.value(row), vals_l.value(row));
let (Some(t), Some(v)) = (
t.as_any().downcast_ref::<Int64Array>(),
v.as_any().downcast_ref::<Float64Array>(),
) else {
return exec_err!("lttb merge received an unexpected state shape");
};
for i in 0..t.len() {
self.ts.push(t.value(i));
self.vals.push(v.value(i));
}
if self.target.is_none() && !tgt.is_null(row) {
self.target = Some(tgt.value(row));
}
}
Ok(())
}
fn state(&mut self) -> Result<Vec<ScalarValue>> {
Ok(vec![
ScalarValue::List(ScalarValue::new_list_nullable(
&self.ts.iter().map(|t| ScalarValue::Int64(Some(*t))).collect::<Vec<_>>(),
&DataType::Int64,
)),
ScalarValue::List(ScalarValue::new_list_nullable(
&self
.vals
.iter()
.map(|v| ScalarValue::Float64(Some(*v)))
.collect::<Vec<_>>(),
&DataType::Float64,
)),
ScalarValue::Int64(self.target),
])
}
fn evaluate(&mut self) -> Result<ScalarValue> {
let mut order: Vec<usize> = (0..self.ts.len()).collect();
order.sort_by_key(|&i| self.ts[i]);
let ts: Vec<i64> = order.iter().map(|&i| self.ts[i]).collect();
let vals: Vec<f64> = order.iter().map(|&i| self.vals[i]).collect();
let target = usize::try_from(self.target.unwrap_or(0)).unwrap_or(0).max(2);
let keep = lttb_indices(&ts, &vals, target);
let (ts_out, vals_out): (Vec<i64>, Vec<f64>) = keep.iter().map(|&i| (ts[i], vals[i])).unzip();
let n = ts_out.len();
let points = StructArray::new(
point_fields(),
vec![
Arc::new(Int64Array::from(ts_out)) as ArrayRef,
Arc::new(Float64Array::from(vals_out)) as ArrayRef,
],
None,
);
let list = ListArray::new(
Arc::new(Field::new("item", DataType::Struct(point_fields()), true)),
OffsetBuffer::new(vec![0, n as i32].into()),
Arc::new(points),
None,
);
Ok(ScalarValue::List(Arc::new(list)))
}
fn size(&self) -> usize {
size_of_val(self) + self.ts.capacity() * 8 + self.vals.capacity() * 8
}
}
#[cfg(test)]
mod tests {
use super::*;
use datafusion::arrow::array::RecordBatch;
use datafusion::arrow::datatypes::Schema;
use datafusion::prelude::SessionContext;
async fn run(sql: &str, batch: RecordBatch) -> Vec<(i64, f64)> {
let ctx = SessionContext::new();
ctx.register_udaf(lttb_udaf());
ctx.register_batch("series", batch).unwrap();
let out = ctx.sql(sql).await.unwrap().collect().await.unwrap();
let col = out[0].column(0);
let list = col.as_any().downcast_ref::<ListArray>().unwrap().value(0);
let s = list.as_any().downcast_ref::<StructArray>().unwrap().clone();
let t = s.column(0).as_any().downcast_ref::<Int64Array>().unwrap();
let v = s.column(1).as_any().downcast_ref::<Float64Array>().unwrap();
(0..t.len()).map(|i| (t.value(i), v.value(i))).collect()
}
fn series(n: i64, spike_at: i64) -> RecordBatch {
let schema = Arc::new(Schema::new(vec![
Field::new("ts", DataType::Int64, false),
Field::new("v", DataType::Float64, false),
]));
let ts: Vec<i64> = (0..n).collect();
let v: Vec<f64> = (0..n)
.map(|i| if i == spike_at { 100.0 } else { (i as f64 * 0.01).sin() })
.collect();
RecordBatch::try_new(
schema,
vec![Arc::new(Int64Array::from(ts)), Arc::new(Float64Array::from(v))],
)
.unwrap()
}
#[tokio::test]
async fn lttb_downsamples_to_target_and_keeps_the_spike() {
let pts = run("SELECT lttb(ts, v, 50) FROM series", series(5000, 3123)).await;
assert_eq!(pts.len(), 50);
assert!(
pts.iter().any(|(t, v)| *t == 3123 && *v == 100.0),
"the spike must survive decimation"
);
assert!(pts.windows(2).all(|w| w[0].0 < w[1].0), "output is time-ordered");
assert_eq!(pts.first().unwrap().0, 0);
assert_eq!(pts.last().unwrap().0, 4999);
}
#[tokio::test]
async fn lttb_passes_short_series_through_and_survives_group_by() {
let pts = run("SELECT lttb(ts, v, 50) FROM series", series(10, 3)).await;
assert_eq!(pts.len(), 10);
let ctx = SessionContext::new();
ctx.register_udaf(lttb_udaf());
ctx.register_batch("series", series(4000, 1111)).unwrap();
let out = ctx
.sql("SELECT ts % 2 AS g, lttb(ts, v, 20) FROM series GROUP BY g ORDER BY g")
.await
.unwrap()
.collect()
.await
.unwrap();
let rows: usize = out.iter().map(|b| b.num_rows()).sum();
assert_eq!(rows, 2);
}
}