use std::collections::{BTreeMap, HashMap, HashSet};
use std::sync::Arc;
use arrow::array::{Array, ArrayRef, BinaryArray, BooleanArray, Float64Array, Int64Array, RecordBatch, UInt32Array};
use arrow::compute::{cast, take};
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
use arrow::ipc::reader::StreamReader;
use arrow::ipc::writer::StreamWriter;
use arrow::row::{OwnedRow, RowConverter, SortField};
use datafusion::functions_aggregate::average::avg_udaf;
use datafusion::functions_aggregate::bit_and_or_xor::{bit_and_udaf, bit_or_udaf, bit_xor_udaf};
use datafusion::functions_aggregate::bool_and_or::{bool_and_udaf, bool_or_udaf};
use datafusion::functions_aggregate::count::count_udaf;
use datafusion::functions_aggregate::min_max::{max_udaf, min_udaf};
use datafusion::functions_aggregate::stddev::{stddev_pop_udaf, stddev_udaf};
use datafusion::functions_aggregate::sum::sum_udaf;
use datafusion::functions_aggregate::variance::{var_pop_udaf, var_samp_udaf};
use datafusion::logical_expr::function::AccumulatorArgs;
use datafusion::logical_expr::{AggregateUDF, EmitTo, GroupsAccumulator};
use datafusion::physical_expr::expressions::col;
use datafusion::physical_expr::PhysicalExpr;
use crate::watermark::Watermark;
use crate::{Agg, AggOp, Trigger, WindowKind};
pub trait BatchOperator {
fn expect_partitions(&mut self, partitions: &[i32], now_ms: i64);
fn push_batch(&mut self, partition: i32, batch: &RecordBatch, event_ms: &[i64]) -> usize;
fn advance(&mut self, now_ms: i64) -> Option<RecordBatch>;
fn advance_to(&mut self, watermark_ms: i64) -> Option<RecordBatch>;
fn flush(&mut self) -> Option<RecordBatch>;
fn output_schema(&self) -> SchemaRef;
fn snapshot(&mut self) -> Vec<u8>;
fn load_snapshot(&mut self, bytes: &[u8]) -> Result<(), String>;
}
pub const SNAPSHOT_VERSION: i64 = 4; pub const WINDOW_START: &str = "windowStart";
pub const WINDOW_END: &str = "windowEnd";
enum AggKind {
Df {
udaf: Arc<AggregateUDF>,
input: DataType,
skip: bool,
},
Distinct,
}
struct AggPlan {
op: AggOp,
column: String,
alias: String,
kind: AggKind,
out: DataType,
}
type DistinctSets = Vec<HashMap<Vec<u8>, ()>>;
struct Pane {
accs: Vec<Box<dyn GroupsAccumulator>>,
distinct: Vec<Option<DistinctSets>>,
to_global: Vec<u32>,
local: HashMap<u32, u32>,
dirty: HashSet<u32>,
}
pub struct WindowAggBatch {
kind: WindowKind,
group_by: Vec<String>,
aggs: Vec<Agg>,
plans: Vec<AggPlan>,
converter: Option<RowConverter>,
key_ids: HashMap<Vec<u8>, u32>,
keys: Vec<OwnedRow>,
key_types: Vec<DataType>,
panes: BTreeMap<i64, Pane>,
wm: Watermark,
fired_through: i64,
late_dropped: u64,
input_schema: Option<SchemaRef>,
trigger: Trigger,
rows_since_early: u64,
last_early_ms: i64,
}
impl WindowAggBatch {
pub fn tumbling(size_ms: i64, allowed_lateness_ms: i64, group_by: Vec<String>, aggs: Vec<Agg>) -> Self {
Self::new(WindowKind::Tumbling { size_ms }, allowed_lateness_ms, group_by, aggs)
}
pub fn sliding(
size_ms: i64,
slide_ms: i64,
allowed_lateness_ms: i64,
group_by: Vec<String>,
aggs: Vec<Agg>,
) -> Self {
Self::new(
WindowKind::Sliding { size_ms, slide_ms },
allowed_lateness_ms,
group_by,
aggs,
)
}
fn new(kind: WindowKind, allowed_lateness_ms: i64, group_by: Vec<String>, aggs: Vec<Agg>) -> Self {
WindowAggBatch {
kind,
group_by,
aggs,
plans: Vec::new(),
converter: None,
key_ids: HashMap::new(),
keys: Vec::new(),
key_types: Vec::new(),
panes: BTreeMap::new(),
wm: Watermark::new(allowed_lateness_ms),
fired_through: i64::MIN,
late_dropped: 0,
input_schema: None,
trigger: Trigger::OnWatermark,
rows_since_early: 0,
last_early_ms: i64::MIN,
}
}
pub fn with_idle_timeout(mut self, idle_timeout_ms: i64) -> Self {
self.wm = self.wm.with_idle_timeout(idle_timeout_ms);
self
}
pub fn with_trigger(mut self, trigger: Trigger) -> Self {
self.trigger = trigger;
self
}
pub fn watermark(&self, now_ms: i64) -> i64 {
self.wm.current(now_ms)
}
pub fn late_dropped(&self) -> u64 {
self.late_dropped
}
pub fn open_panes(&self) -> usize {
self.panes.len()
}
pub fn state_bytes(&self) -> usize {
let panes: usize = self
.panes
.values()
.map(|p| p.accs.iter().map(|a| a.size()).sum::<usize>() + p.to_global.len())
.sum();
let interning: usize = self.keys.iter().map(|r| r.as_ref().len()).sum::<usize>() + self.key_ids.len() * 24; panes + interning
}
fn cfg_fingerprint(&self) -> String {
format!(
"v3;kind={:?};group_by={:?};aggs={:?};{}{}",
self.kind,
self.group_by,
self.aggs,
self.wm.cfg_fingerprint(),
self.trigger.fingerprint(),
)
}
fn plan_for(&mut self, schema: &SchemaRef) -> Result<(), String> {
let mut plans = Vec::with_capacity(self.aggs.len());
for a in &self.aggs {
let input = schema
.field_with_name(&a.column)
.map(|f| f.data_type().clone())
.unwrap_or(DataType::Null);
let numeric = matches!(
input,
DataType::Float64
| DataType::Float32
| DataType::Int64
| DataType::Int32
| DataType::Int16
| DataType::Int8
| DataType::UInt64
| DataType::UInt32
| DataType::UInt16
| DataType::UInt8
);
let (kind, out) = match a.op {
AggOp::Count => (
AggKind::Df {
udaf: count_udaf(),
input: DataType::Int64,
skip: false,
},
DataType::Float64,
),
AggOp::CountDistinct => (AggKind::Distinct, DataType::Float64),
AggOp::Sum | AggOp::Avg | AggOp::Min | AggOp::Max => {
let udaf = match a.op {
AggOp::Sum => sum_udaf(),
AggOp::Avg => avg_udaf(),
AggOp::Min => min_udaf(),
_ => max_udaf(),
};
(
AggKind::Df {
udaf,
input: DataType::Float64,
skip: !numeric,
},
DataType::Float64,
)
}
AggOp::VarPop | AggOp::VarSamp | AggOp::StddevPop | AggOp::StddevSamp => {
let udaf = match a.op {
AggOp::VarPop => var_pop_udaf(),
AggOp::VarSamp => var_samp_udaf(),
AggOp::StddevPop => stddev_pop_udaf(),
_ => stddev_udaf(),
};
(
AggKind::Df {
udaf,
input: DataType::Float64,
skip: !numeric,
},
DataType::Float64,
)
}
AggOp::BoolAnd | AggOp::BoolOr => (
AggKind::Df {
udaf: if a.op == AggOp::BoolAnd {
bool_and_udaf()
} else {
bool_or_udaf()
},
input: DataType::Boolean,
skip: input != DataType::Boolean,
},
DataType::Boolean,
),
AggOp::BitAnd | AggOp::BitOr | AggOp::BitXor => (
AggKind::Df {
udaf: match a.op {
AggOp::BitAnd => bit_and_udaf(),
AggOp::BitOr => bit_or_udaf(),
_ => bit_xor_udaf(),
},
input: DataType::Int64,
skip: !numeric,
},
DataType::Float64,
),
};
plans.push(AggPlan {
op: a.op,
column: a.column.clone(),
alias: a.alias.clone(),
kind,
out,
});
}
self.plans = plans;
let types: Vec<DataType> = self
.group_by
.iter()
.map(|g| {
schema
.field_with_name(g)
.map(|f| f.data_type().clone())
.unwrap_or(DataType::Null)
})
.collect();
self.converter = Some(
RowConverter::new(types.iter().map(|t| SortField::new(t.clone())).collect()).map_err(|e| e.to_string())?,
);
self.key_types = types;
self.input_schema = Some(Arc::clone(schema));
Ok(())
}
fn new_pane(&self) -> Pane {
let accs = self
.plans
.iter()
.map(|p| match &p.kind {
AggKind::Df { udaf, input, .. } => create_acc(udaf, input),
AggKind::Distinct => create_acc(&count_udaf(), &DataType::Int64), })
.collect();
let distinct = self
.plans
.iter()
.map(|p| match p.kind {
AggKind::Distinct => Some(Vec::new()),
_ => None,
})
.collect();
Pane {
accs,
distinct,
to_global: Vec::new(),
local: HashMap::new(),
dirty: HashSet::new(),
}
}
fn intern_keys(&mut self, batch: &RecordBatch) -> Vec<u32> {
if self.group_by.is_empty() {
return vec![0; batch.num_rows()];
}
let cols: Vec<ArrayRef> = self
.group_by
.iter()
.map(|g| match batch.column_by_name(g) {
Some(c) => Arc::clone(c),
None => arrow::array::new_null_array(&DataType::Null, batch.num_rows()),
})
.collect();
let rows = self
.converter
.as_mut()
.expect("planned")
.convert_columns(&cols)
.expect("group columns convert");
let mut ids = Vec::with_capacity(batch.num_rows());
for i in 0..batch.num_rows() {
let r = rows.row(i);
let bytes: &[u8] = r.as_ref();
let id = match self.key_ids.get(bytes) {
Some(&id) => id,
None => {
let id = self.keys.len() as u32;
self.key_ids.insert(bytes.to_vec(), id);
self.keys.push(r.owned());
id
}
};
ids.push(id);
}
ids
}
fn agg_input(&self, plan: &AggPlan, batch: &RecordBatch, idx: &UInt32Array, event_ms: &[i64]) -> ArrayRef {
let n = idx.len();
let AggKind::Df { input, skip, .. } = &plan.kind else {
unreachable!("distinct handled separately")
};
if plan.op == AggOp::Count {
let ones: Int64Array = idx
.values()
.iter()
.map(|&i| event_ms[i as usize])
.collect::<Vec<_>>()
.into();
return Arc::new(ones);
}
let colv = if *skip {
None
} else {
batch.column_by_name(&plan.column)
};
let Some(colv) = colv else {
return arrow::array::new_null_array(input, n);
};
let taken = take(colv.as_ref(), idx, None).expect("take");
match input {
DataType::Int64 => {
let f = cast(&taken, &DataType::Float64).expect("cast");
let f = f.as_any().downcast_ref::<Float64Array>().expect("f64");
let ints: Int64Array = (0..n)
.map(|i| {
if f.is_null(i) || f.value(i).fract() != 0.0 {
None
} else {
Some(f.value(i) as i64)
}
})
.collect();
Arc::new(ints)
}
t => cast(&taken, t).expect("cast"),
}
}
fn fire(&mut self, ready: impl Fn(i64, i64) -> bool, set_fired_through: Option<i64>) -> Option<RecordBatch> {
let size = self.kind.size();
let starts: Vec<i64> = self.panes.keys().filter(|s| ready(**s, size)).copied().collect();
if let Some(wm) = set_fired_through {
self.fired_through = self.fired_through.max(wm);
}
if starts.is_empty() {
return None;
}
let out_schema = self.output_schema();
let mut batches = Vec::with_capacity(starts.len());
for start in starts {
let mut pane = self.panes.remove(&start).expect("present");
let ids = self.sorted_ids(&pane); if let Some(b) = self.emit_pane(start, &mut pane, &ids, true, &out_schema) {
batches.push(b);
}
}
if batches.is_empty() {
return None;
}
Some(arrow::compute::concat_batches(&out_schema, &batches).expect("concat fired"))
}
fn fire_open(&mut self) -> Option<RecordBatch> {
let out_schema = self.output_schema();
let starts: Vec<i64> = self.panes.keys().copied().collect();
let mut batches = Vec::new();
for start in starts {
let mut pane = self.panes.remove(&start).expect("present");
let ids = self.sorted_dirty_ids(&pane);
if let Some(b) = self.emit_pane(start, &mut pane, &ids, false, &out_schema) {
batches.push(b);
}
pane.dirty.clear();
self.panes.insert(start, pane); }
if batches.is_empty() {
return None;
}
Some(arrow::compute::concat_batches(&out_schema, &batches).expect("concat early"))
}
fn emit_pane(
&self,
start: i64,
pane: &mut Pane,
ids: &[u32],
destructive: bool,
out_schema: &SchemaRef,
) -> Option<RecordBatch> {
if ids.is_empty() {
return None;
}
let size = self.kind.size();
let n = ids.len();
let idx = UInt32Array::from(ids.to_vec());
let mut cols: Vec<ArrayRef> = Vec::with_capacity(2 + self.group_by.len() + self.plans.len());
cols.push(Arc::new(Int64Array::from(vec![start; n])));
cols.push(Arc::new(Int64Array::from(vec![start + size; n])));
if !self.group_by.is_empty() {
let rows: Vec<_> = ids
.iter()
.map(|i| self.keys[pane.to_global[*i as usize] as usize].row())
.collect();
let key_cols = self
.converter
.as_ref()
.expect("planned")
.convert_rows(rows)
.expect("rows convert back");
cols.extend(key_cols);
}
for (pi, plan) in self.plans.iter().enumerate() {
let arr: ArrayRef = match &plan.kind {
AggKind::Distinct => {
let sets = pane.distinct[pi].as_ref().expect("distinct sets");
let counts: Float64Array = ids
.iter()
.map(|i| sets.get(*i as usize).map(|s| s.len() as f64).unwrap_or(0.0))
.collect::<Vec<_>>()
.into();
Arc::new(counts)
}
AggKind::Df { .. } => {
let all = if destructive {
pane.accs[pi].evaluate(EmitTo::All).expect("evaluate")
} else {
self.eval_open(pane, pi)
};
let picked = if all.len() >= pane.to_global.len() {
take(all.as_ref(), &idx, None).expect("take")
} else {
arrow::array::new_null_array(all.data_type(), n)
};
finalize(plan, picked)
}
};
cols.push(arr);
}
Some(RecordBatch::try_new(Arc::clone(out_schema), cols).expect("fired batch"))
}
fn eval_open(&self, pane: &mut Pane, pi: usize) -> ArrayRef {
let n = pane.to_global.len();
let state = pane.accs[pi].state(EmitTo::All).expect("state"); let idx: Vec<usize> = (0..n).collect();
let restored: Vec<ArrayRef> = state.iter().map(|a| a.slice(0, n.min(a.len()))).collect();
let ok = !restored.is_empty() && restored[0].len() == n;
if ok {
pane.accs[pi].merge_batch(&restored, &idx, None, n).expect("re-merge live");
}
let mut scratch = match &self.plans[pi].kind {
AggKind::Df { udaf, input, .. } => create_acc(udaf, input),
AggKind::Distinct => unreachable!("eval_open is only called for Df aggregates"),
};
if ok {
scratch.merge_batch(&restored, &idx, None, n).expect("scratch merge");
}
scratch.evaluate(EmitTo::All).expect("evaluate")
}
fn sorted_ids(&self, pane: &Pane) -> Vec<u32> {
let mut ids: Vec<u32> = (0..pane.to_global.len() as u32).collect();
self.sort_by_key_row(&mut ids, pane);
ids
}
fn sorted_dirty_ids(&self, pane: &Pane) -> Vec<u32> {
let mut ids: Vec<u32> = pane.dirty.iter().copied().collect();
self.sort_by_key_row(&mut ids, pane);
ids
}
fn sort_by_key_row(&self, ids: &mut [u32], pane: &Pane) {
if !self.group_by.is_empty() {
ids.sort_by(|a, b| {
self.keys[pane.to_global[*a as usize] as usize]
.row()
.cmp(&self.keys[pane.to_global[*b as usize] as usize].row())
});
}
}
fn with_early(&mut self, closed: Option<RecordBatch>, now_ms: Option<i64>) -> Option<RecordBatch> {
if !self.early_due(now_ms) {
return closed;
}
match (closed, self.fire_open()) {
(None, early) => early,
(closed, None) => closed,
(Some(c), Some(e)) => {
let schema = c.schema();
Some(arrow::compute::concat_batches(&schema, &[c, e]).expect("concat closed+early"))
}
}
}
fn early_due(&mut self, now_ms: Option<i64>) -> bool {
match self.trigger {
Trigger::OnWatermark => false,
Trigger::EveryRows(n) => {
if n > 0 && self.rows_since_early >= n {
self.rows_since_early = 0;
true
} else {
false
}
}
Trigger::EveryMs(ms) => match now_ms {
Some(t) if ms > 0 => {
if self.last_early_ms == i64::MIN {
self.last_early_ms = t; false
} else if t - self.last_early_ms >= ms {
self.last_early_ms = t;
true
} else {
false
}
}
_ => false,
},
}
}
}
fn finalize(plan: &AggPlan, arr: ArrayRef) -> ArrayRef {
match plan.op {
AggOp::Sum | AggOp::Avg | AggOp::Count => {
let f = cast(&arr, &DataType::Float64).expect("cast");
let f = f.as_any().downcast_ref::<Float64Array>().expect("f64");
Arc::new(Float64Array::from(
(0..f.len())
.map(|i| if f.is_null(i) { 0.0 } else { f.value(i) })
.collect::<Vec<_>>(),
))
}
AggOp::BoolAnd | AggOp::BoolOr => arr,
_ => cast(&arr, &plan.out).expect("cast"),
}
}
fn create_acc(udaf: &AggregateUDF, input: &DataType) -> Box<dyn GroupsAccumulator> {
let dt = input.clone();
let schema = Schema::new(vec![Field::new("v", dt.clone(), true)]);
let expr: Arc<dyn PhysicalExpr> = col("v", &schema).expect("col");
let exprs = [expr];
let field: Arc<Field> = Arc::new(Field::new("v", dt.clone(), true));
let expr_fields = [field];
let return_field = Arc::new(Field::new("out", udaf.return_type(&[dt]).expect("return type"), true));
let args = AccumulatorArgs {
return_field,
schema: &schema,
ignore_nulls: false,
order_bys: &[],
is_reversed: false,
name: udaf.name(),
is_distinct: false,
exprs: &exprs,
expr_fields: &expr_fields,
};
udaf.create_groups_accumulator(args).expect("groups accumulator")
}
impl BatchOperator for WindowAggBatch {
fn expect_partitions(&mut self, partitions: &[i32], now_ms: i64) {
self.wm.expect(partitions, now_ms);
}
fn push_batch(&mut self, partition: i32, batch: &RecordBatch, event_ms: &[i64]) -> usize {
if batch.num_rows() == 0 {
return 0;
}
if self.trigger.early_fires() {
self.rows_since_early += batch.num_rows() as u64;
}
if self.converter.is_none() {
self.plan_for(&batch.schema())
.expect("aggregates plan against the schema");
}
for &t in event_ms {
self.wm.observe(partition, t);
}
let size = self.kind.size();
let ids = self.intern_keys(batch);
let mut by_pane: BTreeMap<i64, Vec<u32>> = BTreeMap::new();
let mut late = 0usize;
for (i, &t) in event_ms.iter().enumerate() {
let mut added = false;
for start in self.kind.starts_for(t) {
if start + size <= self.fired_through {
continue;
}
added = true;
by_pane.entry(start).or_default().push(i as u32);
}
if !added {
late += 1;
}
}
self.late_dropped += late as u64;
for (start, rows) in by_pane {
if !self.panes.contains_key(&start) {
let p = self.new_pane();
self.panes.insert(start, p);
}
let idx = UInt32Array::from(rows.clone());
let group_indices: Vec<usize> = rows.iter().map(|r| ids[*r as usize] as usize).collect();
let inputs: Vec<Option<ArrayRef>> = self
.plans
.iter()
.map(|plan| match &plan.kind {
AggKind::Df { .. } => Some(self.agg_input(plan, batch, &idx, event_ms)),
AggKind::Distinct => None,
})
.collect();
let pane = self.panes.get_mut(&start).expect("inserted");
let local_indices: Vec<usize> = group_indices
.iter()
.map(|&g| {
let g = g as u32;
match pane.local.get(&g) {
Some(&l) => l as usize,
None => {
let l = pane.to_global.len();
pane.local.insert(g, l as u32);
pane.to_global.push(g);
l
}
}
})
.collect();
let n_local = pane.to_global.len();
for (pi, plan) in self.plans.iter().enumerate() {
match &plan.kind {
AggKind::Distinct => {
let Some(colv) = batch.column_by_name(&plan.column) else {
continue;
};
let taken = take(colv.as_ref(), &idx, None).expect("take");
let sets = pane.distinct[pi].as_mut().expect("sets");
if sets.len() < n_local {
sets.resize_with(n_local, HashMap::new);
}
let conv = RowConverter::new(vec![SortField::new(taken.data_type().clone())]).expect("conv");
let vrows = conv.convert_columns(&[Arc::clone(&taken)]).expect("convert");
for (r, l) in local_indices.iter().enumerate() {
if taken.is_null(r) {
continue;
}
sets[*l].insert(vrows.row(r).as_ref().to_vec(), ());
}
}
AggKind::Df { .. } => {
let values = inputs[pi].clone().expect("input computed");
pane.accs[pi]
.update_batch(&[values], &local_indices, None, n_local)
.expect("update_batch");
}
}
}
if self.trigger.early_fires() {
for &l in &local_indices {
pane.dirty.insert(l as u32);
}
}
}
late
}
fn advance(&mut self, now_ms: i64) -> Option<RecordBatch> {
self.wm.tick(now_ms);
let wm = self.wm.current(now_ms);
let closed = if wm == i64::MIN {
None
} else {
self.fire(|start, size| start + size <= wm, Some(wm))
};
self.with_early(closed, Some(now_ms))
}
fn advance_to(&mut self, watermark_ms: i64) -> Option<RecordBatch> {
let wm = self.wm.after_lateness(watermark_ms);
let closed = if wm == i64::MIN {
None
} else {
self.fire(|start, size| start + size <= wm, Some(wm))
};
self.with_early(closed, None)
}
fn flush(&mut self) -> Option<RecordBatch> {
self.fired_through = i64::MAX;
self.fire(|_, _| true, None)
}
fn output_schema(&self) -> SchemaRef {
let mut fields = vec![
Field::new(WINDOW_START, DataType::Int64, false),
Field::new(WINDOW_END, DataType::Int64, false),
];
for (g, t) in self.group_by.iter().zip(self.key_types.iter()) {
fields.push(Field::new(g, t.clone(), true));
}
for p in &self.plans {
fields.push(Field::new(&p.alias, p.out.clone(), true));
}
Arc::new(Schema::new(fields))
}
fn snapshot(&mut self) -> Vec<u8> {
let mut bytes = Vec::new();
let frame = |bytes: &mut Vec<u8>, stream: Vec<u8>| {
bytes.extend_from_slice(&(stream.len() as u32).to_le_bytes());
bytes.extend_from_slice(&stream);
};
{
let mut header_bytes = Vec::new();
let owned: Vec<Vec<u8>> = self.keys.iter().map(|k| k.row().as_ref().to_vec()).collect();
let keys = BinaryArray::from(owned.iter().map(|v| v.as_slice()).collect::<Vec<&[u8]>>());
let header_schema = Arc::new(
Schema::new(vec![Field::new("key", DataType::Binary, true)]).with_metadata(
[
("v".to_string(), SNAPSHOT_VERSION.to_string()),
("cfg".to_string(), self.cfg_fingerprint()),
("fired_through".to_string(), self.fired_through.to_string()),
("late_dropped".to_string(), self.late_dropped.to_string()),
("wm".to_string(), self.wm.state_to_json().to_string()),
("panes".to_string(), self.panes.len().to_string()),
]
.into_iter()
.collect(),
),
);
let header = RecordBatch::try_new(Arc::clone(&header_schema), vec![Arc::new(keys)]).expect("header");
let mut w = StreamWriter::try_new(&mut header_bytes, &header_schema).expect("writer");
w.write(&header).expect("write header");
w.finish().expect("finish");
drop(w);
frame(&mut bytes, header_bytes);
}
{
let schema = self.input_schema.clone().unwrap_or_else(|| Arc::new(Schema::empty()));
let mut schema_bytes = Vec::new();
let mut w = StreamWriter::try_new(&mut schema_bytes, &schema).expect("writer");
w.finish().expect("finish");
drop(w);
frame(&mut bytes, schema_bytes);
}
for (start, pane) in self.panes.iter_mut() {
let to_global: UInt32Array = pane.to_global.clone().into();
let n = pane.to_global.len();
let mut fields = vec![Field::new("to_global", DataType::UInt32, true)];
let mut cols: Vec<ArrayRef> = vec![Arc::new(to_global)];
for (pi, plan) in self.plans.iter().enumerate() {
match &plan.kind {
AggKind::Distinct => {
let sets = pane.distinct[pi].as_ref().expect("sets");
let mut groups: Vec<u32> = Vec::new();
let mut vals: Vec<Vec<u8>> = Vec::new();
for (g, s) in sets.iter().enumerate() {
for v in s.keys() {
groups.push(g as u32);
vals.push(v.clone());
}
}
let owned: Vec<Vec<u8>> = groups
.iter()
.zip(vals.iter())
.map(|(g, v)| {
let mut b = g.to_le_bytes().to_vec();
b.extend_from_slice(v);
b
})
.collect();
let enc = BinaryArray::from(owned.iter().map(|v| v.as_slice()).collect::<Vec<&[u8]>>());
let padded = pad_to(Arc::new(enc), n.max(groups.len()));
fields.push(Field::new(format!("d{pi}"), DataType::Binary, true));
cols.push(padded);
}
AggKind::Df { .. } => {
let state = pane.accs[pi].state(EmitTo::All).expect("state");
let all: Vec<usize> = (0..n).collect();
let restored: Vec<ArrayRef> = state.iter().map(|a| a.slice(0, n.min(a.len()))).collect();
if !restored.is_empty() && restored[0].len() == n {
pane.accs[pi].merge_batch(&restored, &all, None, n).expect("re-merge");
}
for (si, s) in state.iter().enumerate() {
fields.push(Field::new(format!("a{pi}_{si}"), s.data_type().clone(), true));
cols.push(pad_to(Arc::clone(s), n));
}
}
}
}
let len = cols.iter().map(|c| c.len()).max().unwrap_or(0);
let cols: Vec<ArrayRef> = cols.into_iter().map(|c| pad_to(c, len)).collect();
let schema = Arc::new(
Schema::new(fields).with_metadata([("start".to_string(), start.to_string())].into_iter().collect()),
);
let b = RecordBatch::try_new(Arc::clone(&schema), cols).expect("pane batch");
let mut pane_bytes = Vec::new();
let mut w = StreamWriter::try_new(&mut pane_bytes, &schema).expect("writer");
w.write(&b).expect("write pane");
w.finish().expect("finish");
drop(w);
frame(&mut bytes, pane_bytes);
}
bytes
}
fn load_snapshot(&mut self, bytes: &[u8]) -> Result<(), String> {
let mut frames: Vec<&[u8]> = Vec::new();
let mut pos = 0usize;
while pos + 4 <= bytes.len() {
let len = u32::from_le_bytes(bytes[pos..pos + 4].try_into().map_err(|_| "snapshot: frame")?) as usize;
pos += 4;
if pos + len > bytes.len() {
return Err("snapshot: truncated frame".into());
}
frames.push(&bytes[pos..pos + len]);
pos += len;
}
let mut frames = frames.into_iter();
let header_bytes = frames.next().ok_or("snapshot: empty")?;
let mut r = StreamReader::try_new(header_bytes, None).map_err(|e| format!("snapshot: {e}"))?;
let header = r.next().ok_or("snapshot: empty")?.map_err(|e| e.to_string())?;
let md = header.schema().metadata().clone();
let v: i64 = md
.get("v")
.and_then(|s| s.parse().ok())
.ok_or("snapshot: missing version")?;
if v != SNAPSHOT_VERSION {
return Err(format!("snapshot: version {v} != supported {SNAPSHOT_VERSION}"));
}
let cfg = md.get("cfg").cloned().unwrap_or_default();
if cfg != self.cfg_fingerprint() {
return Err("snapshot: config mismatch (window kind/size, group_by, aggs or lateness differ)".into());
}
self.fired_through = md.get("fired_through").and_then(|s| s.parse().ok()).unwrap_or(i64::MIN);
self.late_dropped = md.get("late_dropped").and_then(|s| s.parse().ok()).unwrap_or(0);
if let Some(w) = md.get("wm") {
let j: serde_json::Value = serde_json::from_str(w).map_err(|e| e.to_string())?;
self.wm.load_state(&j)?;
}
let n_panes: usize = md.get("panes").and_then(|s| s.parse().ok()).unwrap_or(0);
let keys = header
.column(0)
.as_any()
.downcast_ref::<BinaryArray>()
.ok_or("snapshot: keys")?;
let schema_bytes = frames.next().ok_or("snapshot: schema frame missing")?;
let sr = StreamReader::try_new(schema_bytes, None).map_err(|e| format!("snapshot schema: {e}"))?;
let input_schema = sr.schema();
if self.converter.is_none() {
if input_schema.fields().is_empty() {
return Ok(());
}
self.plan_for(&input_schema)?;
}
let converter = self.converter.as_ref().expect("planned above");
self.key_ids.clear();
self.keys.clear();
let parser = converter.parser();
for i in 0..keys.len() {
let b = keys.value(i).to_vec();
let row = parser.parse(&b).owned();
self.key_ids.insert(b, i as u32);
self.keys.push(row);
}
drop(r);
self.panes.clear();
for _ in 0..n_panes {
let pane_bytes = frames.next().ok_or("snapshot: pane frame missing")?;
let mut pr = StreamReader::try_new(pane_bytes, None).map_err(|e| format!("snapshot pane: {e}"))?;
let b = pr.next().ok_or("snapshot: pane missing")?.map_err(|e| e.to_string())?;
let start: i64 = b
.schema()
.metadata()
.get("start")
.and_then(|s| s.parse().ok())
.ok_or("snapshot: pane start")?;
let tg = b
.column(0)
.as_any()
.downcast_ref::<UInt32Array>()
.ok_or("snapshot: to_global")?;
let mut pane = self.new_pane();
for i in 0..tg.len() {
if tg.is_valid(i) {
let g = tg.value(i);
pane.local.insert(g, pane.to_global.len() as u32);
pane.to_global.push(g);
}
}
let n = pane.to_global.len();
let all: Vec<usize> = (0..n).collect();
for (pi, plan) in self.plans.iter().enumerate() {
match &plan.kind {
AggKind::Distinct => {
let colv = b.column_by_name(&format!("d{pi}")).ok_or("snapshot: distinct column")?;
let enc = colv
.as_any()
.downcast_ref::<BinaryArray>()
.ok_or("snapshot: distinct bytes")?;
let sets = pane.distinct[pi].as_mut().expect("sets");
sets.resize_with(n, HashMap::new);
for i in 0..enc.len() {
if enc.is_null(i) {
continue;
}
let v = enc.value(i);
let g =
u32::from_le_bytes(v[..4].try_into().map_err(|_| "snapshot: distinct group")?) as usize;
sets[g].insert(v[4..].to_vec(), ());
}
}
AggKind::Df { .. } => {
let state: Vec<ArrayRef> = b
.schema()
.fields()
.iter()
.enumerate()
.filter(|(_, f)| f.name().starts_with(&format!("a{pi}_")))
.map(|(i, _)| b.column(i).slice(0, n))
.collect();
if !state.is_empty() && n > 0 {
pane.accs[pi]
.merge_batch(&state, &all, None, n)
.map_err(|e| format!("snapshot: merge: {e}"))?;
}
}
}
}
self.panes.insert(start, pane);
}
if self.trigger.early_fires() {
self.rows_since_early = 0;
self.last_early_ms = i64::MIN;
for pane in self.panes.values_mut() {
pane.dirty = (0..pane.to_global.len() as u32).collect();
}
}
Ok(())
}
}
impl crate::WindowOperator for WindowAggBatch {
fn state_bytes(&self) -> usize {
WindowAggBatch::state_bytes(self)
}
fn open_windows(&self) -> usize {
self.open_panes()
}
fn expect_partitions(&mut self, partitions: &[i32], now_ms: i64) {
BatchOperator::expect_partitions(self, partitions, now_ms);
}
fn push(&mut self, partition: i32, event_ms: i64, row: &[(String, fv_value::Value)]) -> bool {
let schema = match &self.input_schema {
Some(s) => Arc::clone(s),
None => Arc::new(Schema::new(
row.iter()
.map(|(k, v)| Field::new(k, value_type(v), true))
.collect::<Vec<_>>(),
)),
};
let cols: Vec<ArrayRef> = schema
.fields()
.iter()
.map(|f| {
let v = row.iter().find(|(k, _)| k == f.name()).map(|(_, v)| v);
value_array(v, f.data_type())
})
.collect();
let b = RecordBatch::try_new(schema, cols).expect("one-row batch");
BatchOperator::push_batch(self, partition, &b, &[event_ms]) == 0
}
fn push_batch(&mut self, partition: i32, batch: &RecordBatch, event_ms: &[i64]) -> Option<usize> {
Some(BatchOperator::push_batch(self, partition, batch, event_ms))
}
fn advance_batch(&mut self, now_ms: i64) -> Option<Option<RecordBatch>> {
Some(BatchOperator::advance(self, now_ms))
}
fn advance_batch_to(&mut self, watermark_ms: i64) -> Option<Option<RecordBatch>> {
Some(BatchOperator::advance_to(self, watermark_ms))
}
fn flush_batch(&mut self) -> Option<Option<RecordBatch>> {
Some(BatchOperator::flush(self))
}
fn advance(&mut self, now_ms: i64) -> Vec<crate::WindowRow> {
BatchOperator::advance(self, now_ms)
.map(|b| self.batch_to_window_rows(&b))
.unwrap_or_default()
}
fn advance_to(&mut self, watermark_ms: i64) -> Vec<crate::WindowRow> {
BatchOperator::advance_to(self, watermark_ms)
.map(|b| self.batch_to_window_rows(&b))
.unwrap_or_default()
}
fn flush(&mut self) -> Vec<crate::WindowRow> {
BatchOperator::flush(self)
.map(|b| self.batch_to_window_rows(&b))
.unwrap_or_default()
}
fn snapshot(&mut self) -> Vec<u8> {
BatchOperator::snapshot(self)
}
fn load_snapshot(&mut self, bytes: &[u8]) -> Result<(), String> {
BatchOperator::load_snapshot(self, bytes)
}
}
impl WindowAggBatch {
fn batch_to_window_rows(&self, b: &RecordBatch) -> Vec<crate::WindowRow> {
let start = b.column(0).as_any().downcast_ref::<Int64Array>().expect("windowStart");
let end = b.column(1).as_any().downcast_ref::<Int64Array>().expect("windowEnd");
let ng = self.group_by.len();
(0..b.num_rows())
.map(|i| crate::WindowRow {
window_start: start.value(i),
window_end: end.value(i),
key: (0..ng).map(|g| cell_value(b.column(2 + g), i)).collect(),
aggs: self
.plans
.iter()
.enumerate()
.map(|(pi, p)| (p.alias.clone(), cell_value(b.column(2 + ng + pi), i)))
.collect(),
})
.collect()
}
}
fn value_type(v: &fv_value::Value) -> DataType {
match v {
fv_value::Value::Num(_) => DataType::Float64,
fv_value::Value::Str(_) => DataType::Utf8,
fv_value::Value::Bool(_) => DataType::Boolean,
_ => DataType::Null,
}
}
fn value_array(v: Option<&fv_value::Value>, t: &DataType) -> ArrayRef {
match (t, v) {
(DataType::Float64, Some(fv_value::Value::Num(n))) => Arc::new(Float64Array::from(vec![*n])),
(DataType::Int64, Some(fv_value::Value::Num(n))) => Arc::new(Int64Array::from(vec![*n as i64])),
(DataType::Utf8, Some(fv_value::Value::Str(s))) => Arc::new(arrow::array::StringArray::from(vec![s.as_str()])),
(DataType::Boolean, Some(fv_value::Value::Bool(b))) => Arc::new(BooleanArray::from(vec![*b])),
_ => arrow::array::new_null_array(t, 1),
}
}
fn cell_value(a: &ArrayRef, i: usize) -> fv_value::Value {
if a.is_null(i) {
return fv_value::Value::Null;
}
match a.data_type() {
DataType::Float64 => fv_value::Value::Num(a.as_any().downcast_ref::<Float64Array>().unwrap().value(i)),
DataType::Int64 => fv_value::Value::Num(a.as_any().downcast_ref::<Int64Array>().unwrap().value(i) as f64),
DataType::Utf8 => fv_value::Value::Str(
a.as_any()
.downcast_ref::<arrow::array::StringArray>()
.unwrap()
.value(i)
.to_string(),
),
DataType::Boolean => fv_value::Value::Bool(a.as_any().downcast_ref::<BooleanArray>().unwrap().value(i)),
_ => fv_value::Value::Null,
}
}
fn pad_to(a: ArrayRef, n: usize) -> ArrayRef {
if a.len() >= n {
return a;
}
let nulls = arrow::array::new_null_array(a.data_type(), n - a.len());
arrow::compute::concat(&[a.as_ref(), nulls.as_ref()]).expect("pad")
}
#[cfg(test)]
mod tests {
use super::*;
use arrow::array::StringArray;
fn batch(rows: &[(&str, f64, i64)]) -> (RecordBatch, Vec<i64>) {
let schema = Arc::new(Schema::new(vec![
Field::new("k", DataType::Utf8, true),
Field::new("v", DataType::Float64, true),
Field::new("ts", DataType::Int64, true),
]));
let k: StringArray = rows.iter().map(|r| r.0).collect::<Vec<_>>().into();
let v: Float64Array = rows.iter().map(|r| r.1).collect::<Vec<_>>().into();
let ts: Int64Array = rows.iter().map(|r| r.2).collect::<Vec<_>>().into();
let b = RecordBatch::try_new(schema, vec![Arc::new(k), Arc::new(v), Arc::new(ts)]).unwrap();
let t = rows.iter().map(|r| r.2).collect();
(b, t)
}
fn aggs() -> Vec<Agg> {
vec![
Agg::count("n"),
Agg::of(AggOp::Sum, "v", "s"),
Agg::of(AggOp::Avg, "v", "a"),
Agg::of(AggOp::Min, "v", "mn"),
Agg::of(AggOp::Max, "v", "mx"),
]
}
fn f64s(b: &RecordBatch, name: &str) -> Vec<f64> {
let a = b.column_by_name(name).unwrap();
let a = a.as_any().downcast_ref::<Float64Array>().unwrap();
(0..a.len()).map(|i| a.value(i)).collect()
}
fn i64s(b: &RecordBatch, name: &str) -> Vec<i64> {
let a = b.column_by_name(name).unwrap();
let a = a.as_any().downcast_ref::<Int64Array>().unwrap();
(0..a.len()).map(|i| a.value(i)).collect()
}
fn strs(b: &RecordBatch, name: &str) -> Vec<String> {
let a = b.column_by_name(name).unwrap();
let a = a.as_any().downcast_ref::<StringArray>().unwrap();
(0..a.len()).map(|i| a.value(i).to_string()).collect()
}
#[test]
fn tumbling_windows_fire_on_the_watermark_with_exact_aggregates() {
let mut op = WindowAggBatch::tumbling(1000, 0, vec!["k".into()], aggs());
op.expect_partitions(&[0], 0);
let (b, t) = batch(&[("a", 1.0, 100), ("b", 5.0, 200), ("a", 3.0, 900), ("a", 10.0, 1500)]);
assert_eq!(op.push_batch(0, &b, &t), 0);
assert_eq!(op.open_panes(), 2);
let fired = op.advance(0).unwrap();
assert_eq!(fired.num_rows(), 2);
assert_eq!(strs(&fired, "k"), vec!["a", "b"]);
assert_eq!(f64s(&fired, "n"), vec![2.0, 1.0]);
assert_eq!(f64s(&fired, "s"), vec![4.0, 5.0]);
assert_eq!(f64s(&fired, "a"), vec![2.0, 5.0]);
assert_eq!(f64s(&fired, "mn"), vec![1.0, 5.0]);
assert_eq!(f64s(&fired, "mx"), vec![3.0, 5.0]);
assert_eq!(i64s(&fired, WINDOW_END), vec![1000, 1000]);
assert_eq!(op.open_panes(), 1);
let rest = op.flush().unwrap();
assert_eq!(f64s(&rest, "s"), vec![10.0]);
}
#[test]
fn advance_to_fires_by_the_delivered_watermark_less_lateness_never_by_the_rows() {
let mut op = WindowAggBatch::tumbling(1000, 500, vec!["k".into()], vec![Agg::count("n")]);
op.expect_partitions(&[0], 0);
let (b, t) = batch(&[("a", 1.0, 100), ("b", 1.0, 9_900)]);
assert_eq!(op.push_batch(0, &b, &t), 0);
assert!(
BatchOperator::advance_to(&mut op, 1_400).is_none(),
"1400 − 500 < 1000: holds"
);
assert!(
BatchOperator::advance_to(&mut op, i64::MIN).is_none(),
"no time at all: holds"
);
let fired = BatchOperator::advance_to(&mut op, 1_500).unwrap();
assert_eq!(strs(&fired, "k"), vec!["a"]);
assert_eq!(i64s(&fired, WINDOW_END), vec![1000]);
let (late, t) = batch(&[("c", 1.0, 200)]);
assert_eq!(op.push_batch(0, &late, &t), 1);
assert_eq!(op.late_dropped(), 1);
let rest = BatchOperator::advance_to(&mut op, 20_000).unwrap();
assert_eq!(strs(&rest, "k"), vec!["b"]);
}
#[test]
fn a_distinct_set_larger_than_the_key_count_snapshots_and_restores() {
let mut op = WindowAggBatch::tumbling(1000, 0, vec![], vec![Agg::of(AggOp::CountDistinct, "k", "d")]);
op.expect_partitions(&[0], 0);
let (b, t) = batch(&[("a", 1.0, 100), ("b", 1.0, 200), ("c", 1.0, 300), ("a", 1.0, 400)]);
assert_eq!(op.push_batch(0, &b, &t), 0);
let snap = op.snapshot();
let mut restored = WindowAggBatch::tumbling(1000, 0, vec![], vec![Agg::of(AggOp::CountDistinct, "k", "d")]);
restored.expect_partitions(&[0], 0);
restored.load_snapshot(&snap).unwrap();
let (b2, t2) = batch(&[("d", 1.0, 1500)]);
restored.push_batch(0, &b2, &t2);
let fired = BatchOperator::advance(&mut restored, 0).unwrap();
assert_eq!(f64s(&fired, "d"), vec![3.0], "a, b, c — the restored set counts three");
op.push_batch(0, &b2, &t2);
let fired = BatchOperator::advance(&mut op, 0).unwrap();
assert_eq!(f64s(&fired, "d"), vec![3.0]);
}
#[test]
fn sliding_windows_land_an_event_in_every_overlapping_pane() {
let mut op = WindowAggBatch::sliding(1000, 500, 0, vec![], vec![Agg::count("n")]);
op.expect_partitions(&[0], 0);
let (b, t) = batch(&[("x", 1.0, 700)]);
op.push_batch(0, &b, &t);
assert_eq!(op.open_panes(), 2, "starts 500 and 0");
let out = op.flush().unwrap();
assert_eq!(i64s(&out, WINDOW_START), vec![0, 500]);
assert_eq!(f64s(&out, "n"), vec![1.0, 1.0]);
}
#[test]
fn late_events_are_dropped_and_counted_after_the_pane_fired() {
let mut op = WindowAggBatch::tumbling(1000, 0, vec!["k".into()], vec![Agg::count("n")]);
op.expect_partitions(&[0], 0);
let (b, t) = batch(&[("a", 1.0, 100), ("a", 1.0, 2500)]);
op.push_batch(0, &b, &t);
assert!(op.advance(0).is_some()); let (late, tl) = batch(&[("a", 1.0, 150)]);
assert_eq!(op.push_batch(0, &late, &tl), 1);
assert_eq!(op.late_dropped(), 1);
}
#[test]
fn allowed_lateness_holds_the_pane_open() {
let mut op = WindowAggBatch::tumbling(1000, 500, vec![], vec![Agg::count("n")]);
op.expect_partitions(&[0], 0);
let (b, t) = batch(&[("a", 1.0, 100), ("a", 1.0, 1200)]);
op.push_batch(0, &b, &t);
assert!(op.advance(0).is_none(), "watermark 700 < end 1000");
let (b2, t2) = batch(&[("a", 1.0, 1600)]);
op.push_batch(0, &b2, &t2);
let fired = op.advance(0).unwrap();
assert_eq!(f64s(&fired, "n"), vec![1.0]);
}
#[test]
fn a_lagging_partition_holds_firing() {
let mut op = WindowAggBatch::tumbling(1000, 0, vec![], vec![Agg::count("n")]);
op.expect_partitions(&[0, 1], 0);
let (b, t) = batch(&[("a", 1.0, 5000)]);
op.push_batch(0, &b, &t);
assert!(op.advance(0).is_none(), "partition 1 has not reported");
let (b1, t1) = batch(&[("a", 1.0, 2500)]);
op.push_batch(1, &b1, &t1);
assert!(op.advance(0).is_none());
let (b2, t2) = batch(&[("a", 1.0, 6500)]);
op.push_batch(1, &b2, &t2);
let fired = op.advance(0).unwrap();
assert_eq!(i64s(&fired, WINDOW_START), vec![2000]);
assert_eq!(i64s(&op.flush().unwrap(), WINDOW_START), vec![5000, 6000]);
}
#[test]
fn the_whole_op_family_matches_the_row_operator_rules() {
let schema = Arc::new(Schema::new(vec![
Field::new("v", DataType::Float64, true),
Field::new("b", DataType::Boolean, true),
Field::new("s", DataType::Utf8, true),
]));
let v: Float64Array = vec![Some(2.0), Some(4.0), None, Some(2.5)].into();
let bb: BooleanArray = vec![Some(true), Some(false), None, Some(true)].into();
let s: StringArray = vec!["x", "y", "x", "x"].into();
let b = RecordBatch::try_new(schema, vec![Arc::new(v), Arc::new(bb), Arc::new(s)]).unwrap();
let aggs = vec![
Agg::count("n"),
Agg::of(AggOp::CountDistinct, "s", "ds"),
Agg::of(AggOp::Sum, "v", "sum"),
Agg::of(AggOp::Min, "s", "min_s"), Agg::of(AggOp::VarSamp, "v", "vs"),
Agg::of(AggOp::StddevPop, "v", "sp"),
Agg::of(AggOp::BoolAnd, "b", "ba"),
Agg::of(AggOp::BoolOr, "b", "bo"),
Agg::of(AggOp::BitOr, "v", "bor"), ];
let mut op = WindowAggBatch::tumbling(1000, 0, vec![], aggs);
op.expect_partitions(&[0], 0);
op.push_batch(0, &b, &[1, 2, 3, 4]);
let out = op.flush().unwrap();
assert_eq!(f64s(&out, "n"), vec![4.0]);
assert_eq!(f64s(&out, "ds"), vec![2.0]);
assert_eq!(f64s(&out, "sum"), vec![8.5]);
assert!(out.column_by_name("min_s").unwrap().is_null(0));
let vs = f64s(&out, "vs")[0];
assert!((vs - 1.0833333333).abs() < 1e-6, "var_samp of 2,4,2.5 = {vs}");
let sp = f64s(&out, "sp")[0];
assert!((sp - 0.8498365855).abs() < 1e-6, "stddev_pop = {sp}");
let ba = out.column_by_name("ba").unwrap();
let ba = ba.as_any().downcast_ref::<BooleanArray>().unwrap();
assert!(!ba.value(0));
let bo = out.column_by_name("bo").unwrap();
assert!(bo.as_any().downcast_ref::<BooleanArray>().unwrap().value(0));
assert_eq!(f64s(&out, "bor"), vec![6.0]);
}
#[test]
fn snapshot_restore_fires_identically_to_the_uninterrupted_run() {
let (b1, t1) = batch(&[("a", 1.0, 100), ("b", 2.0, 300), ("a", 3.0, 1100)]);
let (b2, t2) = batch(&[("a", 4.0, 1200), ("c", 5.0, 2500)]);
let run = |restore: bool| -> Vec<(f64, String, f64)> {
let mut op = WindowAggBatch::tumbling(1000, 0, vec!["k".into()], aggs());
op.expect_partitions(&[0], 0);
op.push_batch(0, &b1, &t1);
let mut op = if restore {
let snap = op.snapshot();
let mut fresh = WindowAggBatch::tumbling(1000, 0, vec!["k".into()], aggs());
fresh.expect_partitions(&[0], 0);
fresh.load_snapshot(&snap).unwrap();
fresh
} else {
op
};
op.push_batch(0, &b2, &t2);
let mut out = Vec::new();
for fired in [op.advance(0), op.flush()].into_iter().flatten() {
let starts = i64s(&fired, WINDOW_START);
let ks = strs(&fired, "k");
let sums = f64s(&fired, "s");
for i in 0..fired.num_rows() {
out.push((starts[i] as f64, ks[i].clone(), sums[i]));
}
}
out
};
let plain = run(false);
let restored = run(true);
assert_eq!(plain, restored);
assert_eq!(plain.len(), 4);
}
#[test]
fn snapshot_refuses_a_config_mismatch() {
let (b1, t1) = batch(&[("a", 1.0, 100)]);
let mut op = WindowAggBatch::tumbling(1000, 0, vec!["k".into()], aggs());
op.push_batch(0, &b1, &t1);
let snap = op.snapshot();
let mut other = WindowAggBatch::tumbling(2000, 0, vec!["k".into()], aggs());
assert!(other.load_snapshot(&snap).is_err());
}
#[test]
fn on_watermark_trigger_matches_the_default_exactly() {
let feed = |op: &mut WindowAggBatch| {
op.expect_partitions(&[0], 0);
let (b, t) = batch(&[("a", 1.0, 100), ("b", 1.0, 200), ("a", 1.0, 900)]);
op.push_batch(0, &b, &t);
BatchOperator::advance_to(&mut *op, 1000).unwrap()
};
let mut explicit = WindowAggBatch::tumbling(1000, 0, vec!["k".into()], vec![Agg::count("n")])
.with_trigger(Trigger::OnWatermark);
let mut plain = WindowAggBatch::tumbling(1000, 0, vec!["k".into()], vec![Agg::count("n")]);
let e = feed(&mut explicit);
let p = feed(&mut plain);
assert_eq!(strs(&e, "k"), strs(&p, "k"));
assert_eq!(f64s(&e, "n"), f64s(&p, "n"));
assert_eq!(f64s(&e, "n"), vec![2.0, 1.0]);
assert_eq!(explicit.cfg_fingerprint(), plain.cfg_fingerprint());
}
#[test]
fn every_rows_early_fires_are_partial_and_converge_to_the_exact_close() {
let mut op = WindowAggBatch::tumbling(1000, 0, vec!["k".into()], vec![Agg::count("n")])
.with_trigger(Trigger::EveryRows(2));
op.expect_partitions(&[0], 0);
let (b, t) = batch(&[("a", 1.0, 100), ("b", 1.0, 200)]);
op.push_batch(0, &b, &t);
let early1 = BatchOperator::advance_to(&mut op, 500).expect("early fire");
assert_eq!(strs(&early1, "k"), vec!["a", "b"]);
assert_eq!(f64s(&early1, "n"), vec![1.0, 1.0]);
assert_eq!(i64s(&early1, WINDOW_END), vec![1000, 1000]);
assert_eq!(op.open_panes(), 1, "an early fire does NOT evict the window");
let (b, t) = batch(&[("a", 1.0, 300), ("a", 1.0, 400)]);
op.push_batch(0, &b, &t);
let early2 = BatchOperator::advance_to(&mut op, 500).expect("early fire");
assert_eq!(strs(&early2, "k"), vec!["a"], "only the dirty group re-emits");
assert_eq!(f64s(&early2, "n"), vec![3.0]);
let close = BatchOperator::advance_to(&mut op, 1000).expect("close");
assert_eq!(strs(&close, "k"), vec!["a", "b"]);
assert_eq!(f64s(&close, "n"), vec![3.0, 1.0], "exact at close: a=3, b=1");
}
#[test]
fn early_firing_is_non_destructive_the_close_equals_the_plain_run() {
let feed = |op: &mut WindowAggBatch| {
op.expect_partitions(&[0], 0);
for chunk in [
&[("a", 2.0, 100), ("b", 5.0, 150)][..],
&[("a", 4.0, 200), ("a", 6.0, 300)][..],
&[("b", 1.0, 400)][..],
] {
let (bb, tt) = batch(chunk);
op.push_batch(0, &bb, &tt);
let _ = BatchOperator::advance_to(&mut *op, 500); }
BatchOperator::advance_to(&mut *op, 1000).expect("close")
};
let mut early = WindowAggBatch::tumbling(1000, 0, vec!["k".into()], aggs())
.with_trigger(Trigger::EveryRows(1));
let mut plain = WindowAggBatch::tumbling(1000, 0, vec!["k".into()], aggs());
let e = feed(&mut early);
let p = feed(&mut plain);
assert_eq!(strs(&e, "k"), strs(&p, "k"));
for col in ["n", "s", "a", "mn", "mx"] {
assert_eq!(f64s(&e, col), f64s(&p, col), "column {col}: early firing corrupted the accumulator");
}
assert_eq!(f64s(&e, "n"), vec![3.0, 2.0]);
assert_eq!(f64s(&e, "mx"), vec![6.0, 5.0]);
}
#[test]
fn every_rows_replays_identically() {
let run = || {
let mut op = WindowAggBatch::tumbling(1000, 0, vec!["k".into()], vec![Agg::count("n"), Agg::of(AggOp::Sum, "v", "s")])
.with_trigger(Trigger::EveryRows(2));
op.expect_partitions(&[0], 0);
let mut seq: Vec<(Vec<String>, Vec<f64>)> = Vec::new();
for chunk in [&[("a", 1.0, 100), ("b", 2.0, 150)][..], &[("a", 3.0, 200), ("c", 4.0, 250)][..]] {
let (bb, tt) = batch(chunk);
op.push_batch(0, &bb, &tt);
if let Some(f) = BatchOperator::advance_to(&mut op, 500) {
seq.push((strs(&f, "k"), f64s(&f, "s")));
}
}
if let Some(f) = BatchOperator::advance_to(&mut op, 1000) {
seq.push((strs(&f, "k"), f64s(&f, "s")));
}
seq
};
assert_eq!(run(), run(), "same input → identical early-fire + close emission sequence");
}
#[test]
fn a_restore_resyncs_every_open_group_as_dirty() {
let mk = || {
WindowAggBatch::tumbling(1000, 0, vec!["k".into()], vec![Agg::count("n")])
.with_trigger(Trigger::EveryRows(1))
};
let mut op = mk();
op.expect_partitions(&[0], 0);
let (b, t) = batch(&[("a", 1.0, 100), ("b", 1.0, 200)]);
op.push_batch(0, &b, &t);
let _ = BatchOperator::advance_to(&mut op, 500); let snap = op.snapshot();
let mut restored = mk();
restored.expect_partitions(&[0], 0);
restored.load_snapshot(&snap).unwrap();
let (b2, t2) = batch(&[("c", 1.0, 300)]);
restored.push_batch(0, &b2, &t2);
let early = BatchOperator::advance_to(&mut restored, 500).expect("early fire");
assert_eq!(strs(&early, "k"), vec!["a", "b", "c"]);
assert_eq!(f64s(&early, "n"), vec![1.0, 1.0, 1.0]);
}
#[test]
#[ignore]
fn zz_emission_volume_vs_trigger() {
let (g, u, b): (usize, usize, usize) = (2_000, 20, 500);
let mk_batch = |ks: &[String], ts: i64| -> (RecordBatch, Vec<i64>) {
let schema = Arc::new(Schema::new(vec![
Field::new("k", DataType::Utf8, true),
Field::new("v", DataType::Float64, true),
Field::new("ts", DataType::Int64, true),
]));
let karr: StringArray = ks.iter().map(|s| s.as_str()).collect::<Vec<_>>().into();
let varr: Float64Array = ks.iter().map(|_| 1.0).collect::<Vec<_>>().into();
let tarr: Int64Array = ks.iter().map(|_| ts).collect::<Vec<_>>().into();
let bb = RecordBatch::try_new(schema, vec![Arc::new(karr), Arc::new(varr), Arc::new(tarr)]).unwrap();
(bb, vec![ts; ks.len()])
};
let keys: Vec<String> = (0..g).map(|i| format!("k{i:06}")).collect();
eprintln!("EMISSION VOLUME — {g} groups × {u} updates = {} input rows, one open window:", g * u);
for trig in [None, Some(1_000u64), Some(5_000), Some(20_000)] {
let mut op = WindowAggBatch::tumbling(1_000_000, 0, vec!["k".into()], vec![Agg::count("n"), Agg::of(AggOp::Sum, "v", "s")]);
if let Some(n) = trig {
op = op.with_trigger(Trigger::EveryRows(n));
}
op.expect_partitions(&[0], 0);
let mut early_rows = 0usize;
let mut ts = 0i64;
for _ in 0..u {
let mut i = 0;
while i < g {
let end = (i + b).min(g);
let (bb, tt) = mk_batch(&keys[i..end], ts);
op.push_batch(0, &bb, &tt);
if let Some(f) = BatchOperator::advance_to(&mut op, ts) {
early_rows += f.num_rows();
}
ts += 1;
i = end;
}
}
let resident = op.state_bytes();
let close_rows = op.flush().map(|f| f.num_rows()).unwrap_or(0);
let label = trig.map(|n| format!("everyRows({n})")).unwrap_or_else(|| "onWatermark".into());
eprintln!(
" {label:>16}: early={early_rows:>7} close={close_rows} total={:>7} ({:.1}× the {g}-row close) resident_state={resident} bytes",
early_rows + close_rows,
(early_rows + close_rows) as f64 / g as f64,
);
}
}
#[test]
#[ignore]
fn zz_load_snapshot_scaling() {
use std::time::Instant;
for &m in &[100_000usize, 400_000] {
let mk = || WindowAggBatch::sliding(10_000, 800, 5_000_000, vec!["k".into()], vec![Agg::count("n")]);
let mut op = mk();
op.expect_partitions(&[0], 0);
let keys: Vec<String> = (0..m).map(|i| format!("auction-{i}")).collect();
let ks: StringArray = keys.iter().map(|s| s.as_str()).collect::<Vec<_>>().into();
let vs: Float64Array = (0..m).map(|_| 1.0).collect::<Vec<_>>().into();
let ts: Int64Array = (0..m).map(|_| 5000i64).collect::<Vec<_>>().into();
let schema = Arc::new(Schema::new(vec![
Field::new("k", DataType::Utf8, true),
Field::new("v", DataType::Float64, true),
Field::new("ts", DataType::Int64, true),
]));
let b = RecordBatch::try_new(schema, vec![Arc::new(ks), Arc::new(vs), Arc::new(ts)]).unwrap();
let t = vec![5000i64; m];
op.push_batch(0, &b, &t);
let t_snap = Instant::now();
let snap = op.snapshot();
let snap_ms = t_snap.elapsed().as_millis();
let mut fresh = mk();
fresh.expect_partitions(&[0], 0);
let t_load = Instant::now();
fresh.load_snapshot(&snap).unwrap();
let load_ms = t_load.elapsed().as_millis();
eprintln!(
"SCALING m={m} keys, {} panes, snap {} MB in {snap_ms} ms, load {load_ms} ms",
fresh.panes.len(),
snap.len() / 1_000_000,
);
}
}
}