fv-streams-ops 0.3.0

Stateful streaming operators for FusionVault Streams: event-time tumbling and sliding windows with keyed incremental aggregation, session windows, stream joins, top-N and last-N, watermarks and snapshots. Pure and synchronous — no I/O, no runtime.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
//! LOOKUP JOIN — enrich a high-volume STREAM against a BOUNDED side TABLE (Nexmark q13).
//!
//! Unlike the interval [`StreamJoin`](crate::StreamJoin) (two streams, both buffered, watermark
//! eviction), a lookup join has one **stream** side that is stateless per row and one **table** side
//! held as a keyed **upsert map**: the table's latest row per join key. Each stream row is enriched
//! by looking up its join key and appending the table's (non-key) columns — a LEFT lookup: an
//! unmatched stream row keeps its columns with the table columns null, so enrichment never drops
//! stream data. Semantics are **processing-time**: a stream row enriches against the table's state at
//! the moment it is processed (Flink's *lookup join*; the event-time *temporal* join, versioned by
//! time, is a future extension). The table side is its own low-rate upsert stream (a compacted topic
//! or a file), so "rebuild the table when it changes" is just applying its upserts.
//!
//! Throughput: the table materialises to ONE dense Arrow batch (one row per key), rebuilt only when
//! the table changes; the hot stream path is a vectorised probe — key bytes via `arrow::row`, an
//! O(1) hash lookup per row, then a single `take` per table column (nulls for misses = the LEFT
//! join). No buffering of the stream, no watermark gating.
//!
//! Snapshots are framed Arrow IPC: a header (config fingerprint) and the dense table batch; the
//! key→row index is rebuilt on restore from the join-key column.

use std::collections::HashMap;
use std::sync::Arc;

use arrow::array::{Array, ArrayRef, RecordBatch, UInt32Array};
use arrow::compute::take;
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
use arrow::ipc::reader::StreamReader;
use arrow::ipc::writer::StreamWriter;
use arrow::row::{RowConverter, SortField};

pub const SNAPSHOT_VERSION: i64 = 1;

/// An event-time-free equi lookup join. Feed the table side with [`upsert_table`](Self::upsert_table)
/// and the stream side with [`enrich`](Self::enrich); the stream side returns the enriched batch.
pub struct LookupJoinBatch {
    join_key: String,
    /// Row converter over the join-key column (fixed by the first side seen). Both sides' join-key
    /// columns must share a comparable type.
    converter: Option<RowConverter>,
    /// join-key bytes → dense table row id.
    dense: HashMap<Vec<u8>, u32>,
    /// The table's NON-KEY columns, one row per key at its dense id — the materialised lookup table.
    /// `None` until the first table row defines the table schema.
    table: Option<RecordBatch>,
    /// The table's non-key output schema (the columns appended to each enriched stream row), fixed
    /// on the first table batch. `None` until then.
    table_schema: Option<SchemaRef>,
    /// Stream batches that arrived before the table schema was known — enriched and released once it
    /// is (keeps the output schema stable regardless of input ordering). Empty in the common case
    /// (a bounded table is loaded before the stream).
    pending_stream: Vec<RecordBatch>,
    /// The enriched output schema (stream columns + the table's non-key columns), fixed on the first
    /// enrich once both schemas are known.
    out_schema: Option<SchemaRef>,
}

impl LookupJoinBatch {
    pub fn new(join_key: impl Into<String>) -> Self {
        LookupJoinBatch {
            join_key: join_key.into(),
            converter: None,
            dense: HashMap::new(),
            table: None,
            table_schema: None,
            pending_stream: Vec::new(),
            out_schema: None,
        }
    }

    fn cfg_fingerprint(&self) -> String {
        format!("v{SNAPSHOT_VERSION};lookup;join_key={}", self.join_key)
    }

    /// Bytes the materialised table holds — for the broadcast-vs-shuffle size decision and memory.
    pub fn table_bytes(&self) -> usize {
        self.table.as_ref().map(|t| t.get_array_memory_size()).unwrap_or(0)
    }

    /// Distinct keys currently in the table.
    pub fn table_keys(&self) -> usize {
        self.dense.len()
    }

    /// The comparable byte rows of `batch`'s join-key column (interning the converter on first use).
    /// A row missing the key column, or with a null key, yields `None` (it cannot match / be keyed).
    fn key_bytes(&mut self, batch: &RecordBatch) -> Vec<Option<Vec<u8>>> {
        let Some(col) = batch.column_by_name(&self.join_key) else {
            return vec![None; batch.num_rows()];
        };
        if self.converter.is_none() {
            let f = SortField::new(col.data_type().clone());
            self.converter = Some(RowConverter::new(vec![f]).expect("lookup key converter"));
        }
        let rows = self
            .converter
            .as_mut()
            .expect("converter")
            .convert_columns(std::slice::from_ref(col))
            .expect("convert join key");
        (0..batch.num_rows())
            .map(|i| {
                if col.is_null(i) {
                    None
                } else {
                    Some(rows.row(i).as_ref().to_vec())
                }
            })
            .collect()
    }

    /// The table's non-key column indexes for `batch` (everything but the join key), and the schema
    /// they form. Fixed by the first table batch.
    fn non_key_projection(&self, batch: &RecordBatch) -> (Vec<usize>, SchemaRef) {
        let schema = batch.schema();
        let idx: Vec<usize> = (0..batch.num_columns())
            .filter(|&i| schema.field(i).name() != &self.join_key)
            .collect();
        let fields: Vec<Field> = idx
            .iter()
            .map(|&i| {
                let f = schema.field(i);
                // nullable in the output: a stream row that finds no table row reads null here.
                Field::new(f.name(), f.data_type().clone(), true)
            })
            .collect();
        (idx, Arc::new(Schema::new(fields)))
    }

    /// Upsert the table side: apply each row as the latest value for its join key, then rematerialise
    /// the dense lookup table. Returns any buffered stream batches now enrichable (usually none — the
    /// first table batch releases stream rows that arrived before it).
    pub fn upsert_table(&mut self, batch: &RecordBatch) -> Vec<RecordBatch> {
        if batch.num_rows() == 0 {
            return Vec::new();
        }
        let keys = self.key_bytes(batch);
        let (proj, schema) = self.non_key_projection(batch);
        if self.table_schema.is_none() {
            self.table_schema = Some(Arc::clone(&schema));
        }
        let incoming = batch.project(&proj).expect("project table non-key columns");

        // Merge the incoming rows over the current dense table, keeping the LATEST row per key. Build
        // gather indices into a two-source interleave: source 0 = the current table, source 1 = the
        // incoming batch; a key present in `incoming` takes the incoming row.
        let current = self.table.clone();
        let n_current = self.dense.len();
        // dense id -> (source, row). Seed with the current table (source 0), then overlay incoming.
        let mut pos: Vec<(usize, usize)> = (0..n_current).map(|d| (0usize, d)).collect();
        for (r, k) in keys.iter().enumerate() {
            let Some(k) = k else { continue }; // a null-keyed table row cannot be looked up
            match self.dense.get(k).copied() {
                Some(d) => pos[d as usize] = (1, r),
                None => {
                    let d = self.dense.len() as u32;
                    self.dense.insert(k.clone(), d);
                    pos.push((1, r));
                }
            }
        }
        let out_schema = self.table_schema.clone().expect("set above");
        let sources: Vec<&RecordBatch> = match &current {
            Some(c) => vec![c, &incoming],
            None => {
                // no current table: every position must reference source 1 (incoming). (Seeded pos
                // had none from source 0 because n_current == 0.)
                vec![&incoming, &incoming]
            }
        };
        self.table = Some(interleave_rows(&out_schema, &sources, &pos));

        // Release any stream batches that were waiting for the table schema.
        if self.pending_stream.is_empty() {
            Vec::new()
        } else {
            let held = std::mem::take(&mut self.pending_stream);
            held.iter().map(|b| self.enrich_ready(b)).collect()
        }
    }

    /// Enrich one stream batch. Returns the enriched batch (stream columns + the table's non-key
    /// columns, null where a key has no table row), or `None` while the table schema is still unknown
    /// (the batch is buffered and released by the first [`upsert_table`](Self::upsert_table)).
    pub fn enrich(&mut self, batch: &RecordBatch) -> Option<RecordBatch> {
        if self.table_schema.is_none() {
            // the table hasn't defined its columns yet — hold the stream row so the output schema is
            // stable once it does. Rare: a bounded side input is normally loaded first.
            if batch.num_rows() > 0 {
                self.pending_stream.push(batch.clone());
            }
            return None;
        }
        Some(self.enrich_ready(batch))
    }

    /// Enrich a stream batch once the table schema is known: a vectorised probe + one `take` per
    /// table column (null indices for misses = the LEFT join).
    fn enrich_ready(&mut self, batch: &RecordBatch) -> RecordBatch {
        let table_schema = self.table_schema.clone().expect("table schema known");
        let keys = self.key_bytes(batch);
        // dense id per stream row, null when the key is absent from the table.
        let mut idx = arrow::array::UInt32Builder::with_capacity(batch.num_rows());
        for k in &keys {
            match k.as_ref().and_then(|k| self.dense.get(k)) {
                Some(&d) => idx.append_value(d),
                None => idx.append_null(),
            }
        }
        let idx: UInt32Array = idx.finish();

        let mut cols: Vec<ArrayRef> = batch.columns().to_vec();
        let mut fields: Vec<Field> = batch.schema().fields().iter().map(|f| f.as_ref().clone()).collect();
        let have: std::collections::HashSet<String> =
            batch.schema().fields().iter().map(|f| f.name().to_string()).collect();
        let empty_table = self.table.is_none();
        for (j, f) in table_schema.fields().iter().enumerate() {
            // a table column whose name the stream already carries: the stream value wins (like the
            // interval join's left-then-right merge), so skip it.
            if have.contains(f.name()) {
                continue;
            }
            let gathered: ArrayRef = match &self.table {
                Some(t) if !empty_table => take(t.column(j), &idx, None).expect("take table column"),
                _ => arrow::array::new_null_array(f.data_type(), batch.num_rows()),
            };
            cols.push(gathered);
            fields.push(Field::new(f.name(), f.data_type().clone(), true));
        }
        let schema = Arc::new(Schema::new(fields));
        // pin the stable output schema on the first enrich.
        if self.out_schema.is_none() {
            self.out_schema = Some(Arc::clone(&schema));
        }
        RecordBatch::try_new(schema, cols).expect("enriched batch")
    }

    /// The materialised table as framed Arrow IPC (one frame: config header, then the dense table).
    pub fn snapshot(&mut self) -> Vec<u8> {
        let mut bytes = Vec::new();
        let table = self
            .table
            .clone()
            .unwrap_or_else(|| empty_batch(self.table_schema.clone()));
        let key_col = self.join_key.clone();
        // stash the join-key values alongside so the index rebuilds on restore. The table batch holds
        // only non-key columns, so we carry the keys in dense-id order as their own column.
        let keys_in_order = self.keys_in_dense_order();
        let schema = table.schema();
        let mut fields: Vec<Field> = schema.fields().iter().map(|f| f.as_ref().clone()).collect();
        fields.push(Field::new(format!("__fv_lookupkey_{key_col}"), DataType::Binary, true));
        let mut cols = table.columns().to_vec();
        cols.push(Arc::new(arrow::array::BinaryArray::from(
            keys_in_order.iter().map(|k| Some(k.as_slice())).collect::<Vec<_>>(),
        )));
        let schema = Arc::new(
            Schema::new(fields).with_metadata([("cfg".to_string(), self.cfg_fingerprint())].into_iter().collect()),
        );
        let batch = RecordBatch::try_new(Arc::clone(&schema), cols).expect("snapshot batch");
        let mut w = StreamWriter::try_new(&mut bytes, &schema).expect("writer");
        w.write(&batch).expect("write");
        w.finish().expect("finish");
        bytes
    }

    /// Restore the table (and rebuild the key index) from a [`snapshot`](Self::snapshot).
    pub fn load_snapshot(&mut self, bytes: &[u8]) -> Result<(), String> {
        let mut r = StreamReader::try_new(bytes, None).map_err(|e| format!("lookup snapshot: {e}"))?;
        let b = r.next().ok_or("lookup snapshot: empty")?.map_err(|e| e.to_string())?;
        let cfg = b.schema().metadata().get("cfg").cloned().unwrap_or_default();
        if cfg != self.cfg_fingerprint() {
            return Err("lookup snapshot: config mismatch (join key differs)".into());
        }
        let keycol = format!("__fv_lookupkey_{}", self.join_key);
        let ki = b
            .schema()
            .index_of(&keycol)
            .map_err(|_| "lookup snapshot: missing key column")?;
        let keys = b
            .column(ki)
            .as_any()
            .downcast_ref::<arrow::array::BinaryArray>()
            .ok_or("lookup snapshot: key column type")?;
        let data_idx: Vec<usize> = (0..b.num_columns()).filter(|i| *i != ki).collect();
        let table = b.project(&data_idx).map_err(|e| e.to_string())?;
        self.dense.clear();
        for i in 0..keys.len() {
            if keys.is_valid(i) {
                self.dense.insert(keys.value(i).to_vec(), i as u32);
            }
        }
        self.table_schema = Some(table.schema());
        self.table = if table.num_rows() == 0 && self.dense.is_empty() {
            None
        } else {
            Some(table)
        };
        Ok(())
    }

    /// The join-key bytes in dense-id order (index space) — for the snapshot.
    fn keys_in_dense_order(&self) -> Vec<Vec<u8>> {
        let mut out = vec![Vec::new(); self.dense.len()];
        for (k, &d) in &self.dense {
            out[d as usize] = k.clone();
        }
        out
    }
}

/// Gather rows from several source batches (same schema) into one, `pos[d] = (source, row)`.
fn interleave_rows(schema: &SchemaRef, sources: &[&RecordBatch], pos: &[(usize, usize)]) -> RecordBatch {
    if pos.is_empty() {
        return empty_batch(Some(Arc::clone(schema)));
    }
    let ncols = schema.fields().len();
    let cols: Vec<ArrayRef> = (0..ncols)
        .map(|c| {
            let arrays: Vec<&dyn Array> = sources.iter().map(|s| s.column(c).as_ref()).collect();
            arrow::compute::interleave(&arrays, pos).expect("interleave table")
        })
        .collect();
    RecordBatch::try_new(Arc::clone(schema), cols).expect("materialise table")
}

fn empty_batch(schema: Option<SchemaRef>) -> RecordBatch {
    let schema = schema.unwrap_or_else(|| Arc::new(Schema::empty()));
    RecordBatch::new_empty(schema)
}

#[cfg(test)]
mod tests {
    use super::*;
    use arrow::array::{Float64Array, Int64Array, StringArray};

    // a stream side: (join key, price).
    fn stream(rows: &[(i64, f64)]) -> RecordBatch {
        let schema = Arc::new(Schema::new(vec![
            Field::new("key", DataType::Int64, true),
            Field::new("price", DataType::Float64, true),
        ]));
        let k: Int64Array = rows.iter().map(|r| r.0).collect::<Vec<_>>().into();
        let p: Float64Array = rows.iter().map(|r| r.1).collect::<Vec<_>>().into();
        RecordBatch::try_new(schema, vec![Arc::new(k), Arc::new(p)]).unwrap()
    }

    // a table side: (join key, value).
    fn table(rows: &[(i64, &str)]) -> RecordBatch {
        let schema = Arc::new(Schema::new(vec![
            Field::new("key", DataType::Int64, true),
            Field::new("value", DataType::Utf8, true),
        ]));
        let k: Int64Array = rows.iter().map(|r| r.0).collect::<Vec<_>>().into();
        let v: StringArray = rows.iter().map(|r| r.1).collect::<Vec<_>>().into();
        RecordBatch::try_new(schema, vec![Arc::new(k), Arc::new(v)]).unwrap()
    }

    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 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 vals(b: &RecordBatch, name: &str) -> Vec<Option<String>> {
        let a = b.column_by_name(name).unwrap();
        let a = a.as_any().downcast_ref::<StringArray>().unwrap();
        (0..a.len())
            .map(|i| {
                if a.is_null(i) {
                    None
                } else {
                    Some(a.value(i).to_string())
                }
            })
            .collect()
    }

    #[test]
    fn enrich_appends_the_matching_table_row_left_join() {
        let mut lj = LookupJoinBatch::new("key");
        lj.upsert_table(&table(&[(1, "a"), (2, "b")]));
        let e = lj.enrich(&stream(&[(1, 10.0), (2, 20.0), (3, 30.0)])).unwrap();
        assert_eq!(i64s(&e, "key"), vec![1, 2, 3]);
        assert_eq!(f64s(&e, "price"), vec![10.0, 20.0, 30.0], "stream columns pass through");
        assert_eq!(
            vals(&e, "value"),
            vec![Some("a".into()), Some("b".into()), None],
            "LEFT: a miss (key 3) keeps the row with a null table column"
        );
        // the table is not consumed — a second stream batch enriches identically (no eviction).
        let e2 = lj.enrich(&stream(&[(2, 99.0)])).unwrap();
        assert_eq!(vals(&e2, "value"), vec![Some("b".into())]);
    }

    #[test]
    fn a_table_upsert_keeps_the_latest_value_per_key() {
        let mut lj = LookupJoinBatch::new("key");
        lj.upsert_table(&table(&[(1, "a"), (2, "b")]));
        lj.upsert_table(&table(&[(1, "a2"), (3, "c")])); // key 1 updated, key 3 added
        assert_eq!(lj.table_keys(), 3);
        let e = lj.enrich(&stream(&[(1, 1.0), (2, 2.0), (3, 3.0)])).unwrap();
        assert_eq!(
            vals(&e, "value"),
            vec![Some("a2".into()), Some("b".into()), Some("c".into())],
            "the latest row wins for key 1; key 2 unchanged; key 3 newly present"
        );
    }

    #[test]
    fn a_stream_batch_before_the_table_is_buffered_then_released() {
        let mut lj = LookupJoinBatch::new("key");
        // no table yet → the stream row is held so the output schema stays stable.
        assert!(lj.enrich(&stream(&[(1, 10.0), (9, 90.0)])).is_none());
        // the first table batch defines the schema AND releases the buffered stream, enriched.
        let released = lj.upsert_table(&table(&[(1, "a")]));
        assert_eq!(released.len(), 1);
        assert_eq!(vals(&released[0], "value"), vec![Some("a".into()), None]);
    }

    #[test]
    fn a_table_column_sharing_a_stream_name_keeps_the_stream_value() {
        // table carries a `price` column too — the stream's value must win (left-preferred merge).
        let schema = Arc::new(Schema::new(vec![
            Field::new("key", DataType::Int64, true),
            Field::new("price", DataType::Float64, true),
            Field::new("value", DataType::Utf8, true),
        ]));
        let tb = RecordBatch::try_new(
            schema,
            vec![
                Arc::new(Int64Array::from(vec![1i64])),
                Arc::new(Float64Array::from(vec![-1.0])), // the table's price (must be ignored)
                Arc::new(StringArray::from(vec!["a"])),
            ],
        )
        .unwrap();
        let mut lj = LookupJoinBatch::new("key");
        lj.upsert_table(&tb);
        let e = lj.enrich(&stream(&[(1, 10.0)])).unwrap();
        assert_eq!(
            f64s(&e, "price"),
            vec![10.0],
            "the stream's price, not the table's -1.0"
        );
        assert_eq!(vals(&e, "value"), vec![Some("a".into())]);
        assert_eq!(e.num_columns(), 3, "key, price, value — no duplicate price column");
    }

    #[test]
    fn snapshot_restore_preserves_the_table_and_the_index() {
        let mut lj = LookupJoinBatch::new("key");
        lj.upsert_table(&table(&[(1, "a"), (2, "b")]));
        lj.upsert_table(&table(&[(2, "b2")])); // an update, so the dense/pos path is exercised
        let snap = lj.snapshot();
        let mut restored = LookupJoinBatch::new("key");
        restored.load_snapshot(&snap).unwrap();
        assert_eq!(restored.table_keys(), 2);
        let e = restored.enrich(&stream(&[(1, 1.0), (2, 2.0), (5, 5.0)])).unwrap();
        assert_eq!(vals(&e, "value"), vec![Some("a".into()), Some("b2".into()), None]);
    }

    #[test]
    fn a_snapshot_refuses_a_different_join_key() {
        let mut lj = LookupJoinBatch::new("key");
        lj.upsert_table(&table(&[(1, "a")]));
        let snap = lj.snapshot();
        let mut other = LookupJoinBatch::new("other");
        assert!(other.load_snapshot(&snap).is_err());
    }
}