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;
pub struct LookupJoinBatch {
join_key: String,
converter: Option<RowConverter>,
dense: HashMap<Vec<u8>, u32>,
table: Option<RecordBatch>,
table_schema: Option<SchemaRef>,
pending_stream: Vec<RecordBatch>,
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)
}
pub fn table_bytes(&self) -> usize {
self.table
.as_ref()
.map(|t| t.get_array_memory_size())
.unwrap_or(0)
}
pub fn table_keys(&self) -> usize {
self.dense.len()
}
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()
}
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);
Field::new(f.name(), f.data_type().clone(), true)
})
.collect();
(idx, Arc::new(Schema::new(fields)))
}
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");
let current = self.table.clone();
let n_current = self.dense.len();
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 }; 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 ¤t {
Some(c) => vec![c, &incoming],
None => {
vec![&incoming, &incoming]
}
};
self.table = Some(interleave_rows(&out_schema, &sources, &pos));
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()
}
}
pub fn enrich(&mut self, batch: &RecordBatch) -> Option<RecordBatch> {
if self.table_schema.is_none() {
if batch.num_rows() > 0 {
self.pending_stream.push(batch.clone());
}
return None;
}
Some(self.enrich_ready(batch))
}
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);
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() {
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));
if self.out_schema.is_none() {
self.out_schema = Some(Arc::clone(&schema));
}
RecordBatch::try_new(schema, cols).expect("enriched batch")
}
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();
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
}
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(())
}
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
}
}
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};
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()
}
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"
);
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")])); 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");
assert!(lj.enrich(&stream(&[(1, 10.0), (9, 90.0)])).is_none());
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() {
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])), 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")])); 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());
}
}