fv-plan 0.3.0

The FusionVault transform executor on Apache DataFusion: inline row steps and relational reshapes (join, aggregate, window, union) over Arrow, with the value dialect translated into the plan, spatial SQL, file sources, and build orchestration checked against the published conformance vectors.
Documentation
//! `lttb(ts, value, target)` — server-side time-series decimation as a DataFusion aggregate
//! Largest-Triangle-Three-Buckets keeps the points that shape the line (spikes
//! inflections), so a million-row series aggregates to a render-ready `target` points in ONE
//! query instead of shipping the rows. The maths is fv-util's index-returning core — the same
//! code the OSS history endpoint uses, so both surfaces decimate identically.
//!
//! Contract: `ts` Int64 epoch-ms (the canonical form), `value` Float64, `target` Int64
//! literal. Returns `List<Struct{ts: Int64, value: Float64}>` sorted by ts. The accumulator
//! keeps RAW pairs and decimates once at evaluate — merge is plain concatenation, which is what
//! makes the aggregate correct under Ballista's partial/final split (partitions arrive unordered;
//! evaluate sorts).

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;

/// The output element type: Struct{ts, value}.
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; // a null point can't anchor a triangle — skip, don't poison
            }
            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> {
        // Partitions merge unordered; LTTB needs the series in time order.
        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() {
        // Under target: every point returned.
        let pts = run("SELECT lttb(ts, v, 50) FROM series", series(10, 3)).await;
        assert_eq!(pts.len(), 10);
        // GROUP BY (parallel partial aggregation exercises merge_batch + the evaluate-time sort).
        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);
    }
}