use std::collections::HashMap;
use std::sync::Arc;
use arrow::array::{
Array, ArrayRef, BooleanArray, FixedSizeListArray, Float32Array, Float64Array, Int64Array,
PrimitiveArray, RecordBatch, Scalar, UInt32Array,
};
use arrow::compute::kernels::cmp;
use arrow::compute::{TakeOptions, and_kleene, filter_record_batch, take};
use arrow::datatypes::{ArrowPrimitiveType, DataType, Field, Float64Type, Int64Type, Schema};
use oxidelake_core::EngineError;
use oxidelake_core::params::{
AggregateFunction, AggregateSpec, Comparison, DistanceMetric, Literal, Predicate,
};
use rayon::prelude::*;
fn column(batch: &RecordBatch, index: usize) -> Result<&ArrayRef, EngineError> {
batch.columns().get(index).ok_or_else(|| {
EngineError::plan(format!(
"column index {index} out of range for a batch with {} columns",
batch.num_columns()
))
})
}
fn int64_column<'a>(
batch: &'a RecordBatch,
index: usize,
role: &str,
) -> Result<&'a Int64Array, EngineError> {
let col = column(batch, index)?;
col.as_any().downcast_ref::<Int64Array>().ok_or_else(|| {
EngineError::unsupported(
"cpu.int64_column",
format!(
"{role} column {index} has type {:?}; v1 supports Int64",
col.data_type()
),
)
})
}
const NEGATIVE_ZERO_BITS: u64 = (-0.0f64).to_bits();
fn positive_zero(v: f64) -> f64 {
if v.to_bits() == NEGATIVE_ZERO_BITS {
0.0
} else {
v
}
}
fn negative_zeros_as_positive(col: &ArrayRef) -> ArrayRef {
match col.as_any().downcast_ref::<Float64Array>() {
Some(values)
if values
.values()
.iter()
.any(|v| v.to_bits() == NEGATIVE_ZERO_BITS) =>
{
Arc::new(values.unary::<_, Float64Type>(positive_zero))
}
_ => Arc::clone(col),
}
}
pub fn evaluate_predicate(
batch: &RecordBatch,
predicate: &Predicate,
) -> Result<BooleanArray, EngineError> {
match predicate {
Predicate::Compare {
column: idx,
op,
literal,
} => {
let col = column(batch, *idx)?;
if *col.data_type() != literal.data_type() {
return Err(EngineError::unsupported(
"cpu.filter",
format!(
"column {idx} has type {:?} but the literal is {:?}",
col.data_type(),
literal.data_type()
),
));
}
let scalar: ArrayRef = match literal {
Literal::Int64(v) => Arc::new(Int64Array::from(vec![*v])),
Literal::Float64(v) => Arc::new(Float64Array::from(vec![positive_zero(*v)])),
};
let scalar = Scalar::new(scalar);
let col = &negative_zeros_as_positive(col);
let mask = match op {
Comparison::Eq => cmp::eq(col, &scalar),
Comparison::Lt => cmp::lt(col, &scalar),
Comparison::LtEq => cmp::lt_eq(col, &scalar),
Comparison::Gt => cmp::gt(col, &scalar),
Comparison::GtEq => cmp::gt_eq(col, &scalar),
}?;
Ok(mask)
}
Predicate::And(left, right) => {
let l = evaluate_predicate(batch, left)?;
let r = evaluate_predicate(batch, right)?;
Ok(and_kleene(&l, &r)?)
}
}
}
pub fn filter_project(
batch: &RecordBatch,
predicate: &Predicate,
projection: &[usize],
) -> Result<RecordBatch, EngineError> {
let mask = evaluate_predicate(batch, predicate)?;
let projected = batch.project(projection)?;
Ok(filter_record_batch(&projected, &mask)?)
}
#[derive(Default, Clone, Copy)]
struct KeyHasher(u64);
impl std::hash::Hasher for KeyHasher {
fn finish(&self) -> u64 {
let mut z = self.0;
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
fn write(&mut self, bytes: &[u8]) {
for chunk in bytes.chunks(8) {
let mut word = [0u8; 8];
word[..chunk.len()].copy_from_slice(chunk);
self.0 = self.0.rotate_left(5) ^ u64::from_le_bytes(word);
}
}
fn write_i64(&mut self, i: i64) {
self.0 = self.0.rotate_left(5) ^ (i as u64);
}
}
#[derive(Debug, Clone)]
pub struct JoinTable {
ranges: HashMap<i64, (u32, u32), std::hash::BuildHasherDefault<KeyHasher>>,
rows: Vec<u32>,
}
impl std::fmt::Debug for KeyHasher {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("KeyHasher")
}
}
impl JoinTable {
pub fn build(build: &RecordBatch, key: usize) -> Result<Self, EngineError> {
let keys = int64_column(build, key, "build join key")?;
let mut counts: HashMap<i64, u32, std::hash::BuildHasherDefault<KeyHasher>> =
HashMap::with_capacity_and_hasher(keys.len(), Default::default());
for key in keys.iter().flatten() {
*counts.entry(key).or_insert(0) += 1;
}
let mut ranges = HashMap::with_capacity_and_hasher(counts.len(), Default::default());
let mut next: u32 = 0;
for (key, count) in counts {
ranges.insert(key, (next, count));
next = next
.checked_add(count)
.ok_or_else(|| EngineError::execution("build side exceeds u32::MAX rows"))?;
}
let mut cursor: HashMap<i64, u32, std::hash::BuildHasherDefault<KeyHasher>> =
ranges.iter().map(|(k, (start, _))| (*k, *start)).collect();
let mut rows = vec![0u32; next as usize];
for (j, key) in keys.iter().enumerate() {
let Some(key) = key else { continue };
if let Some(slot) = cursor.get_mut(&key) {
rows[*slot as usize] = index_u32(j)?;
*slot += 1;
}
}
Ok(Self { ranges, rows })
}
pub fn matches(&self, key: i64) -> &[u32] {
match self.ranges.get(&key) {
Some(&(start, len)) => &self.rows[start as usize..(start + len) as usize],
None => &[],
}
}
fn run(&self, key: i64) -> Option<(u32, u32)> {
self.ranges.get(&key).copied()
}
pub fn runs(&self) -> impl Iterator<Item = (i64, u32, u32)> + '_ {
self.ranges
.iter()
.map(|(&key, &(start, count))| (key, start, count))
}
pub fn row_indices(&self) -> &[u32] {
&self.rows
}
pub fn distinct_keys(&self) -> usize {
self.ranges.len()
}
pub fn rows(&self) -> usize {
self.rows.len()
}
}
pub fn hash_join(
left: &RecordBatch,
right: &RecordBatch,
left_key: usize,
right_key: usize,
) -> Result<RecordBatch, EngineError> {
let table = JoinTable::build(right, right_key)?;
hash_join_probe(left, left_key, right, &table, None)
}
pub fn hash_join_probe(
left: &RecordBatch,
left_key: usize,
right: &RecordBatch,
table: &JoinTable,
projection: Option<&[usize]>,
) -> Result<RecordBatch, EngineError> {
let matches = JoinMatches::probe(left, left_key, table)?;
let rows = usize::try_from(matches.len())
.map_err(|_| EngineError::execution("join output exceeds usize::MAX rows"))?;
hash_join_gather(left, right, table, &matches, 0, rows, projection)
}
#[derive(Debug, Clone, Default)]
pub struct JoinMatches {
offsets: Vec<u64>,
starts: Vec<u32>,
}
impl JoinMatches {
pub fn probe(
left: &RecordBatch,
left_key: usize,
table: &JoinTable,
) -> Result<Self, EngineError> {
let keys = int64_column(left, left_key, "left join key")?;
index_u32(keys.len())?;
let mut offsets = Vec::with_capacity(keys.len() + 1);
let mut starts = Vec::with_capacity(keys.len());
let mut total = 0u64;
for key in keys.iter() {
offsets.push(total);
let (start, count) = key.and_then(|k| table.run(k)).unwrap_or((0, 0));
starts.push(start);
total += u64::from(count);
}
offsets.push(total);
Ok(Self { offsets, starts })
}
pub fn len(&self) -> u64 {
self.offsets.last().copied().unwrap_or(0)
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
pub fn probe_rows(&self) -> usize {
self.starts.len()
}
pub fn pairs(
&self,
table: &JoinTable,
first: u64,
rows: usize,
) -> Result<(UInt32Array, UInt32Array), EngineError> {
let end = u64::try_from(rows)
.ok()
.and_then(|r| first.checked_add(r))
.filter(|&end| end <= self.len())
.ok_or_else(|| {
EngineError::execution(format!(
"matches {first}..+{rows} are outside a probe with {} matches",
self.len()
))
})?;
let mut left = Vec::with_capacity(rows);
let mut right = Vec::with_capacity(rows);
let mut row = self
.offsets
.partition_point(|&offset| offset <= first)
.saturating_sub(1);
let mut at = first;
while at < end {
let (lo, hi) = (self.offsets[row], self.offsets[row + 1]);
let upto = hi.min(end);
if upto > at {
let start = self.starts[row] as usize;
let run = table
.rows
.get(start + (at - lo) as usize..start + (upto - lo) as usize)
.ok_or_else(|| {
EngineError::execution("join matches were probed against another table")
})?;
left.extend(std::iter::repeat_n(index_u32(row)?, run.len()));
right.extend_from_slice(run);
at = upto;
}
row += 1;
}
Ok((UInt32Array::from(left), UInt32Array::from(right)))
}
}
pub fn hash_join_gather(
left: &RecordBatch,
right: &RecordBatch,
table: &JoinTable,
matches: &JoinMatches,
first: u64,
rows: usize,
projection: Option<&[usize]>,
) -> Result<RecordBatch, EngineError> {
if matches.probe_rows() != left.num_rows() {
return Err(EngineError::execution(format!(
"join matches cover {} probe rows but the probe batch has {}",
matches.probe_rows(),
left.num_rows()
)));
}
let (left_idx, right_idx) = matches.pairs(table, first, rows)?;
let checked = Some(TakeOptions { check_bounds: true });
let all_fields: Vec<_> = left
.schema()
.fields()
.iter()
.chain(right.schema().fields().iter())
.cloned()
.collect();
let width = left.num_columns();
let selected: Vec<usize> = match projection {
Some(indices) => indices.to_vec(),
None => (0..all_fields.len()).collect(),
};
let mut fields = Vec::with_capacity(selected.len());
let mut columns = Vec::with_capacity(selected.len());
for &index in &selected {
let field = all_fields.get(index).ok_or_else(|| {
EngineError::plan(format!(
"join projection index {index} out of range for {} columns",
all_fields.len()
))
})?;
let array = if index < width {
take(left.column(index).as_ref(), &left_idx, checked.clone())?
} else {
take(
right.column(index - width).as_ref(),
&right_idx,
checked.clone(),
)?
};
fields.push(Arc::clone(field));
columns.push(array);
}
Ok(RecordBatch::try_new(
Arc::new(Schema::new(fields)),
columns,
)?)
}
fn index_u32(i: usize) -> Result<u32, EngineError> {
u32::try_from(i).map_err(|_| EngineError::execution("batch exceeds u32::MAX rows"))
}
#[derive(Debug)]
enum Accumulator {
Count(Vec<i64>),
SumI64(Vec<Option<i64>>),
SumF64(Vec<Option<f64>>),
MinI64(Vec<Option<i64>>),
MaxI64(Vec<Option<i64>>),
MinF64(Vec<Option<f64>>),
MaxF64(Vec<Option<f64>>),
}
fn primitive<'a, T: ArrowPrimitiveType>(
values: &'a ArrayRef,
what: &str,
) -> Result<&'a PrimitiveArray<T>, EngineError> {
values
.as_any()
.downcast_ref::<PrimitiveArray<T>>()
.ok_or_else(|| {
EngineError::execution(format!(
"{what} input has type {:?}, expected {:?}",
values.data_type(),
T::DATA_TYPE
))
})
}
fn fold<T: ArrowPrimitiveType>(
values: &PrimitiveArray<T>,
ids: &[usize],
slots: &mut [Option<T::Native>],
first: impl Fn(T::Native) -> T::Native,
next: impl Fn(T::Native, T::Native) -> T::Native,
) {
for (row, &g) in ids.iter().enumerate() {
if values.is_valid(row) {
let v = values.value(row);
slots[g] = Some(match slots[g] {
Some(held) => next(held, v),
None => first(v),
});
}
}
}
fn total_min(held: f64, v: f64) -> f64 {
if v.total_cmp(&held).is_lt() { v } else { held }
}
fn total_max(held: f64, v: f64) -> f64 {
if v.total_cmp(&held).is_gt() { v } else { held }
}
impl Accumulator {
fn new(func: AggregateFunction, input: &DataType, index: usize) -> Result<Self, EngineError> {
Ok(match (func, input) {
(AggregateFunction::Count, DataType::Int64 | DataType::Float64) => {
Self::Count(Vec::new())
}
(AggregateFunction::Sum, DataType::Int64) => Self::SumI64(Vec::new()),
(AggregateFunction::Sum, DataType::Float64) => Self::SumF64(Vec::new()),
(AggregateFunction::Min, DataType::Int64) => Self::MinI64(Vec::new()),
(AggregateFunction::Max, DataType::Int64) => Self::MaxI64(Vec::new()),
(AggregateFunction::Min, DataType::Float64) => Self::MinF64(Vec::new()),
(AggregateFunction::Max, DataType::Float64) => Self::MaxF64(Vec::new()),
(_, other) => {
return Err(EngineError::unsupported(
"cpu.aggregate",
format!(
"aggregate input column {index} has type {other:?}; v1 supports Int64 and Float64"
),
));
}
})
}
fn grow(&mut self, groups: usize) {
match self {
Self::Count(v) => v.resize(groups, 0),
Self::SumI64(v) | Self::MinI64(v) | Self::MaxI64(v) => v.resize(groups, None),
Self::SumF64(v) | Self::MinF64(v) | Self::MaxF64(v) => v.resize(groups, None),
}
}
fn update(&mut self, values: &ArrayRef, ids: &[usize]) -> Result<(), EngineError> {
match self {
Self::Count(counts) => {
for (row, &g) in ids.iter().enumerate() {
if values.is_valid(row) {
counts[g] += 1;
}
}
}
Self::SumI64(slots) => fold(
primitive::<Int64Type>(values, "SUM")?,
ids,
slots,
|v| v,
i64::wrapping_add,
),
Self::SumF64(slots) => fold(
primitive::<Float64Type>(values, "SUM")?,
ids,
slots,
|v| 0.0 + v,
|held, v| held + v,
),
Self::MinI64(slots) => fold(
primitive::<Int64Type>(values, "MIN")?,
ids,
slots,
|v| v,
i64::min,
),
Self::MaxI64(slots) => fold(
primitive::<Int64Type>(values, "MAX")?,
ids,
slots,
|v| v,
i64::max,
),
Self::MinF64(slots) => fold(
primitive::<Float64Type>(values, "MIN")?,
ids,
slots,
|v| v,
total_min,
),
Self::MaxF64(slots) => fold(
primitive::<Float64Type>(values, "MAX")?,
ids,
slots,
|v| v,
total_max,
),
}
Ok(())
}
fn merge(&mut self, partial: &ArrayRef, ids: &[usize]) -> Result<(), EngineError> {
if let Self::Count(counts) = self {
let partial = primitive::<Int64Type>(partial, "partial COUNT")?;
for (row, &g) in ids.iter().enumerate() {
if partial.is_valid(row) {
counts[g] = counts[g].wrapping_add(partial.value(row));
}
}
return Ok(());
}
self.update(partial, ids)
}
fn finish(&self, order: &[usize]) -> (DataType, ArrayRef) {
fn pick<T: Copy>(slots: &[T], order: &[usize]) -> Vec<T> {
order.iter().map(|&g| slots[g]).collect()
}
match self {
Self::Count(counts) => (
DataType::Int64,
Arc::new(Int64Array::from(pick(counts, order))),
),
Self::SumI64(slots) | Self::MinI64(slots) | Self::MaxI64(slots) => (
DataType::Int64,
Arc::new(Int64Array::from(pick(slots, order))),
),
Self::SumF64(slots) | Self::MinF64(slots) | Self::MaxF64(slots) => (
DataType::Float64,
Arc::new(Float64Array::from(pick(slots, order))),
),
}
}
}
#[derive(Debug)]
pub struct GroupedAggregator {
group_by: usize,
key_name: String,
inputs: Vec<usize>,
names: Vec<String>,
index: HashMap<i64, usize>,
null_group: Option<usize>,
keys: Vec<Option<i64>>,
accumulators: Vec<Accumulator>,
}
impl GroupedAggregator {
pub fn new(schema: &Schema, spec: &AggregateSpec) -> Result<Self, EngineError> {
let field = |index: usize| {
schema.fields().get(index).ok_or_else(|| {
EngineError::plan(format!(
"column index {index} out of range for a batch with {} columns",
schema.fields().len()
))
})
};
let key = field(spec.group_by)?;
if key.data_type() != &DataType::Int64 {
return Err(EngineError::unsupported(
"cpu.int64_column",
format!(
"group key column {} has type {:?}; v1 supports Int64",
spec.group_by,
key.data_type()
),
));
}
let mut accumulators = Vec::with_capacity(spec.aggregates.len());
let mut names = Vec::with_capacity(spec.aggregates.len());
for (func, index) in &spec.aggregates {
let input = field(*index)?;
accumulators.push(Accumulator::new(*func, input.data_type(), *index)?);
names.push(format!("{}({})", func.name(), input.name()));
}
Ok(Self {
group_by: spec.group_by,
key_name: key.name().clone(),
inputs: spec.aggregates.iter().map(|(_, index)| *index).collect(),
names,
index: HashMap::new(),
null_group: None,
keys: Vec::new(),
accumulators,
})
}
pub fn groups(&self) -> usize {
self.keys.len()
}
fn group_ids(&mut self, keys: &Int64Array) -> Vec<usize> {
let mut ids = Vec::with_capacity(keys.len());
for row in 0..keys.len() {
let next = self.keys.len();
let id = if keys.is_valid(row) {
let key = keys.value(row);
let groups = &mut self.keys;
*self.index.entry(key).or_insert_with(|| {
groups.push(Some(key));
next
})
} else if let Some(g) = self.null_group {
g
} else {
self.keys.push(None);
self.null_group = Some(next);
next
};
ids.push(id);
}
for accumulator in &mut self.accumulators {
accumulator.grow(self.keys.len());
}
ids
}
pub fn update(&mut self, batch: &RecordBatch) -> Result<(), EngineError> {
let keys = int64_column(batch, self.group_by, "group key")?;
let ids = self.group_ids(keys);
for (accumulator, &input) in self.accumulators.iter_mut().zip(&self.inputs) {
accumulator.update(column(batch, input)?, &ids)?;
}
Ok(())
}
pub fn merge(&mut self, partial: &RecordBatch) -> Result<(), EngineError> {
if partial.num_columns() != 1 + self.accumulators.len() {
return Err(EngineError::execution(format!(
"a partial aggregate has {} columns; this aggregation's output has {}",
partial.num_columns(),
1 + self.accumulators.len()
)));
}
let keys = int64_column(partial, 0, "partial group key")?;
let ids = self.group_ids(keys);
for (i, accumulator) in self.accumulators.iter_mut().enumerate() {
accumulator.merge(partial.column(1 + i), &ids)?;
}
Ok(())
}
pub fn finish(self) -> Result<RecordBatch, EngineError> {
let mut order: Vec<usize> = (0..self.keys.len()).collect();
order.sort_unstable_by_key(|&g| (self.keys[g].is_none(), self.keys[g]));
let mut fields = vec![Field::new(&self.key_name, DataType::Int64, true)];
let mut columns: Vec<ArrayRef> = vec![Arc::new(Int64Array::from(
order.iter().map(|&g| self.keys[g]).collect::<Vec<_>>(),
))];
for (accumulator, name) in self.accumulators.iter().zip(&self.names) {
let (data_type, array) = accumulator.finish(&order);
fields.push(Field::new(name, data_type, true));
columns.push(array);
}
Ok(RecordBatch::try_new(
Arc::new(Schema::new(fields)),
columns,
)?)
}
}
pub fn aggregate(batch: &RecordBatch, spec: &AggregateSpec) -> Result<RecordBatch, EngineError> {
let mut groups = GroupedAggregator::new(&batch.schema(), spec)?;
groups.update(batch)?;
groups.finish()
}
pub const fn total_order_key(x: f64) -> i64 {
let bits = x.to_bits() as i64;
bits ^ ((((bits >> 63) as u64) >> 1) as i64)
}
pub const fn from_total_order_key(key: i64) -> f64 {
f64::from_bits((key ^ ((((key >> 63) as u64) >> 1) as i64)) as u64)
}
pub fn vector_distance(
batch: &RecordBatch,
column_index: usize,
query: &[f32],
metric: DistanceMetric,
output_name: &str,
) -> Result<RecordBatch, EngineError> {
let col = column(batch, column_index)?;
let list = col
.as_any()
.downcast_ref::<FixedSizeListArray>()
.ok_or_else(|| {
EngineError::unsupported(
"cpu.vector_distance",
format!(
"column {column_index} has type {:?}; expected FixedSizeList<Float32>",
col.data_type()
),
)
})?;
let values = list
.values()
.as_any()
.downcast_ref::<Float32Array>()
.ok_or_else(|| {
EngineError::unsupported(
"cpu.vector_distance",
format!(
"vector element type is {:?}; expected Float32",
list.value_type()
),
)
})?;
let dim = usize::try_from(list.value_length())
.map_err(|_| EngineError::plan("negative list size"))?;
if query.len() != dim {
return Err(EngineError::plan(format!(
"query vector has {} dimensions but the column has {dim}",
query.len()
)));
}
let raw = values.values();
let distances: Vec<Option<f32>> = (0..batch.num_rows())
.into_par_iter()
.map(|row| {
if list.is_null(row) {
return None;
}
let start = usize::try_from(list.value_offset(row)).unwrap_or(0);
let v = &raw[start..start + dim];
Some(match metric {
DistanceMetric::L2 => l2(v, query),
DistanceMetric::Cosine => cosine(v, query),
})
})
.collect();
let mut fields: Vec<_> = batch.schema().fields().iter().cloned().collect();
fields.push(Arc::new(Field::new(output_name, DataType::Float32, true)));
let mut columns = batch.columns().to_vec();
columns.push(Arc::new(Float32Array::from(distances)));
Ok(RecordBatch::try_new(
Arc::new(Schema::new(fields)),
columns,
)?)
}
pub fn l2(a: &[f32], b: &[f32]) -> f32 {
a.iter()
.zip(b)
.map(|(x, y)| (x - y) * (x - y))
.sum::<f32>()
.sqrt()
}
pub fn cosine(a: &[f32], b: &[f32]) -> f32 {
let dot: f32 = a.iter().zip(b).map(|(x, y)| x * y).sum();
let na: f32 = a.iter().map(|x| x * x).sum::<f32>().sqrt();
let nb: f32 = b.iter().map(|y| y * y).sum::<f32>().sqrt();
if na == 0.0 || nb == 0.0 {
f32::NAN
} else {
1.0 - dot / (na * nb)
}
}
#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tests {
use arrow::array::{Array, StringArray};
use arrow::buffer::NullBuffer;
use arrow::datatypes::SchemaRef;
use super::*;
fn schema() -> SchemaRef {
Arc::new(Schema::new(vec![
Field::new("k", DataType::Int64, true),
Field::new("v", DataType::Float64, true),
Field::new("s", DataType::Utf8, true),
]))
}
fn batch() -> RecordBatch {
RecordBatch::try_new(
schema(),
vec![
Arc::new(Int64Array::from(vec![
Some(1),
Some(2),
None,
Some(2),
Some(5),
])),
Arc::new(Float64Array::from(vec![
Some(0.5),
None,
Some(2.5),
Some(3.5),
Some(-1.0),
])),
Arc::new(StringArray::from(vec![
Some("a"),
Some("b"),
Some("c"),
None,
Some("e"),
])),
],
)
.unwrap()
}
#[test]
fn filter_drops_null_predicates_and_projects() {
let pred = Predicate::and(
Predicate::compare(0, Comparison::GtEq, Literal::Int64(2)),
Predicate::compare(1, Comparison::Lt, Literal::Float64(4.0)),
);
let out = filter_project(&batch(), &pred, &[2, 0]).unwrap();
assert_eq!(out.num_columns(), 2);
assert_eq!(out.schema().field(0).name(), "s");
let ks = out.column(1).as_any().downcast_ref::<Int64Array>().unwrap();
assert_eq!(ks.values(), &[2, 5]);
}
#[test]
fn float_comparisons_order_as_datafusion_does() {
let values = [
f64::NAN,
-f64::NAN,
f64::INFINITY,
f64::NEG_INFINITY,
0.0,
-0.0,
4.0,
];
let batch = RecordBatch::try_new(
Arc::new(Schema::new(vec![Field::new("v", DataType::Float64, false)])),
vec![Arc::new(Float64Array::from(values.to_vec()))],
)
.unwrap();
let selected = |op, x| -> Vec<usize> {
let predicate = Predicate::compare(0, op, Literal::Float64(x));
let mask = evaluate_predicate(&batch, &predicate).unwrap();
(0..mask.len()).filter(|&row| mask.value(row)).collect()
};
assert_eq!(selected(Comparison::Gt, 4.0), [0, 2]);
assert_eq!(selected(Comparison::Lt, f64::NEG_INFINITY), [1]);
assert_eq!(selected(Comparison::Eq, f64::NAN), [0]);
assert_eq!(selected(Comparison::Eq, 0.0), [4, 5]);
assert_eq!(selected(Comparison::Eq, -0.0), [4, 5]);
assert_eq!(selected(Comparison::Lt, 0.0), [1, 3]);
assert_eq!(selected(Comparison::GtEq, -0.0), [0, 2, 4, 5, 6]);
}
#[test]
fn filter_type_mismatch_is_unsupported() {
let pred = Predicate::compare(1, Comparison::Eq, Literal::Int64(1));
assert!(
filter_project(&batch(), &pred, &[0])
.unwrap_err()
.is_unsupported()
);
}
#[test]
fn join_skips_null_keys_and_multiplies_matches() {
let right = RecordBatch::try_new(
Arc::new(Schema::new(vec![
Field::new("rk", DataType::Int64, true),
Field::new("name", DataType::Utf8, false),
])),
vec![
Arc::new(Int64Array::from(vec![Some(2), Some(2), None, Some(9)])),
Arc::new(StringArray::from(vec!["two-a", "two-b", "null", "nine"])),
],
)
.unwrap();
let out = hash_join(&batch(), &right, 0, 0).unwrap();
assert_eq!(out.num_columns(), 5);
assert_eq!(out.num_rows(), 4);
let names = out
.column(4)
.as_any()
.downcast_ref::<StringArray>()
.unwrap();
let mut got: Vec<&str> = names.iter().flatten().collect();
got.sort_unstable();
assert_eq!(got, vec!["two-a", "two-a", "two-b", "two-b"]);
}
#[test]
fn join_matches_gather_in_ranges_equal_one_gather() {
let right = RecordBatch::try_new(
Arc::new(Schema::new(vec![
Field::new("rk", DataType::Int64, true),
Field::new("name", DataType::Utf8, false),
])),
vec![
Arc::new(Int64Array::from(vec![
Some(2),
Some(2),
None,
Some(9),
Some(2),
Some(5),
])),
Arc::new(StringArray::from(vec![
"a", "b", "null", "nine", "c", "five",
])),
],
)
.unwrap();
let left = batch();
let table = JoinTable::build(&right, 0).unwrap();
let matches = JoinMatches::probe(&left, 0, &table).unwrap();
let whole = hash_join_probe(&left, 0, &right, &table, None).unwrap();
assert_eq!(matches.len(), 7);
assert_eq!(whole.num_rows(), 7);
let projection = [0, 1, 3, 4];
for chunk in 1..=8 {
let mut parts = Vec::new();
let mut first = 0;
while first < matches.len() {
let rows = chunk.min(usize::try_from(matches.len() - first).unwrap());
let part = hash_join_gather(
&left,
&right,
&table,
&matches,
first,
rows,
Some(&projection),
)
.unwrap();
assert_eq!(part.num_rows(), rows);
parts.push(part);
first += rows as u64;
}
let joined = arrow::compute::concat_batches(&parts[0].schema(), &parts).unwrap();
assert_eq!(joined, whole.project(&projection).unwrap(), "chunk {chunk}");
}
assert!(matches.pairs(&table, 7, 1).is_err());
assert!(matches.pairs(&table, 0, usize::MAX).is_err());
let other = JoinTable::build(&right.slice(0, 2), 0).unwrap();
assert!(hash_join_gather(&left, &right, &other, &matches, 0, 7, None).is_err());
assert!(hash_join_gather(&left.slice(0, 2), &right, &table, &matches, 0, 1, None).is_err());
}
#[test]
fn aggregate_groups_nulls_last_and_skips_null_values() {
let spec = AggregateSpec {
group_by: 0,
aggregates: vec![
(AggregateFunction::Sum, 1),
(AggregateFunction::Count, 1),
(AggregateFunction::Min, 1),
(AggregateFunction::Max, 0),
],
};
let out = aggregate(&batch(), &spec).unwrap();
let keys = out.column(0).as_any().downcast_ref::<Int64Array>().unwrap();
assert_eq!(
keys.iter().collect::<Vec<_>>(),
vec![Some(1), Some(2), Some(5), None]
);
let sums = out
.column(1)
.as_any()
.downcast_ref::<Float64Array>()
.unwrap();
assert_eq!(
sums.iter().collect::<Vec<_>>(),
vec![Some(0.5), Some(3.5), Some(-1.0), Some(2.5)]
);
let counts = out.column(2).as_any().downcast_ref::<Int64Array>().unwrap();
assert_eq!(counts.values(), &[1, 1, 1, 1]);
assert_eq!(out.schema().field(1).name(), "SUM(v)");
assert_eq!(out.schema().field(4).name(), "MAX(k)");
let maxk = out.column(4).as_any().downcast_ref::<Int64Array>().unwrap();
assert_eq!(
maxk.iter().collect::<Vec<_>>(),
vec![Some(1), Some(2), Some(5), None]
);
}
fn edge_batch(rows: &[(Option<i64>, Option<i64>, Option<f64>)]) -> RecordBatch {
let schema = Arc::new(Schema::new(vec![
Field::new("k", DataType::Int64, true),
Field::new("i", DataType::Int64, true),
Field::new("f", DataType::Float64, true),
]));
RecordBatch::try_new(
schema,
vec![
Arc::new(Int64Array::from(
rows.iter().map(|r| r.0).collect::<Vec<_>>(),
)),
Arc::new(Int64Array::from(
rows.iter().map(|r| r.1).collect::<Vec<_>>(),
)),
Arc::new(Float64Array::from(
rows.iter().map(|r| r.2).collect::<Vec<_>>(),
)),
],
)
.unwrap()
}
fn bits(batch: &RecordBatch) -> Vec<Vec<Option<u64>>> {
batch
.columns()
.iter()
.map(|c| {
if let Some(ints) = c.as_any().downcast_ref::<Int64Array>() {
ints.iter().map(|v| v.map(|v| v as u64)).collect()
} else {
let floats = c.as_any().downcast_ref::<Float64Array>().unwrap();
floats.iter().map(|v| v.map(f64::to_bits)).collect()
}
})
.collect()
}
#[test]
fn batch_by_batch_and_merged_partials_equal_one_pass() {
use AggregateFunction::{Count, Max, Min, Sum};
let nan = f64::NAN;
let rows = [
(Some(1), Some(i64::MAX - 1), Some(1.0)),
(Some(2), Some(5), Some(nan)),
(None, Some(i64::MAX), Some(-0.0)),
(Some(1), Some(i64::MAX - 1), Some(nan)),
(Some(3), None, None),
(Some(4), Some(i64::MIN), Some(-nan)),
(None, Some(i64::MAX), Some(0.0)),
(Some(1), Some(-3), Some(3.0)),
(Some(4), Some(7), Some(f64::NEG_INFINITY)),
(Some(2), Some(-1), Some(0.25)),
];
let spec = AggregateSpec {
group_by: 0,
aggregates: vec![
(Sum, 1),
(Count, 1),
(Min, 1),
(Max, 1),
(Sum, 2),
(Count, 2),
(Min, 2),
(Max, 2),
],
};
let whole = aggregate(&edge_batch(&rows), &spec).unwrap();
for split in 1..rows.len() {
let (a, b) = rows.split_at(split);
let (a, b) = (edge_batch(a), edge_batch(b));
let mut streamed = GroupedAggregator::new(&a.schema(), &spec).unwrap();
streamed.update(&a).unwrap();
streamed.update(&b).unwrap();
let mut merged = GroupedAggregator::new(&a.schema(), &spec).unwrap();
merged.merge(&aggregate(&b, &spec).unwrap()).unwrap();
merged.merge(&aggregate(&a, &spec).unwrap()).unwrap();
assert_eq!(
bits(&streamed.finish().unwrap()),
bits(&whole),
"update, split at {split}"
);
assert_eq!(
bits(&merged.finish().unwrap()),
bits(&whole),
"merge, split at {split}"
);
}
let sums = whole
.column(1)
.as_any()
.downcast_ref::<Int64Array>()
.unwrap();
assert_eq!(
sums.iter().collect::<Vec<_>>(),
vec![Some(-7), Some(4), None, Some(i64::MIN + 7), Some(-2)]
);
let float = |c: usize| bits(&whole)[c].clone();
assert_eq!(
float(7),
[Some(1.0), Some(0.25), None, Some(-nan), Some(-0.0)]
.map(|v| v.map(f64::to_bits))
.to_vec()
);
assert_eq!(
float(8),
[
Some(nan),
Some(nan),
None,
Some(f64::NEG_INFINITY),
Some(0.0)
]
.map(|v| v.map(f64::to_bits))
.to_vec()
);
}
#[test]
fn merging_a_mislaid_partial_is_an_error() {
let spec = AggregateSpec {
group_by: 0,
aggregates: vec![(AggregateFunction::Count, 1)],
};
let mut groups = GroupedAggregator::new(&schema(), &spec).unwrap();
assert!(groups.merge(&batch()).is_err());
assert_eq!(groups.groups(), 0);
}
#[test]
fn aggregate_over_empty_batch_has_no_groups() {
let empty = RecordBatch::new_empty(schema());
let spec = AggregateSpec {
group_by: 0,
aggregates: vec![(AggregateFunction::Count, 1)],
};
let out = aggregate(&empty, &spec).unwrap();
assert_eq!(out.num_rows(), 0);
assert_eq!(out.num_columns(), 2);
}
#[test]
fn total_order_keys_order_like_total_cmp_and_round_trip() {
let values = [
f64::from_bits(u64::MAX),
-f64::NAN,
f64::NEG_INFINITY,
f64::MIN,
-1.0,
-f64::from_bits(1),
-0.0,
0.0,
f64::from_bits(1),
f64::MIN_POSITIVE,
1.0,
f64::MAX,
f64::INFINITY,
f64::from_bits(0x7FF0_0000_0000_0001),
f64::NAN,
f64::from_bits(0x7FFF_FFFF_FFFF_FFFF),
];
for a in values {
assert_eq!(
from_total_order_key(total_order_key(a)).to_bits(),
a.to_bits()
);
for b in values {
assert_eq!(
total_order_key(a).cmp(&total_order_key(b)),
a.total_cmp(&b),
"{a:?} ({:#x}) vs {b:?} ({:#x})",
a.to_bits(),
b.to_bits()
);
}
}
assert_eq!(
from_total_order_key(i64::MAX).to_bits(),
0x7FFF_FFFF_FFFF_FFFF
);
assert_eq!(from_total_order_key(i64::MIN).to_bits(), u64::MAX);
}
#[test]
fn vector_distances() {
let field = Arc::new(Field::new("item", DataType::Float32, false));
let vectors = FixedSizeListArray::try_new(
field,
2,
Arc::new(Float32Array::from(vec![1.0, 0.0, 0.0, 1.0, 3.0, 4.0])),
Some(NullBuffer::from(vec![true, false, true])),
)
.unwrap();
let schema = Arc::new(Schema::new(vec![Field::new(
"vec",
vectors.data_type().clone(),
true,
)]));
let batch = RecordBatch::try_new(schema, vec![Arc::new(vectors)]).unwrap();
let out = vector_distance(&batch, 0, &[1.0, 0.0], DistanceMetric::L2, "d").unwrap();
let d = out
.column(1)
.as_any()
.downcast_ref::<Float32Array>()
.unwrap();
assert_eq!(
d.iter().collect::<Vec<_>>(),
vec![Some(0.0), None, Some(20f32.sqrt())]
);
let out = vector_distance(&batch, 0, &[1.0, 0.0], DistanceMetric::Cosine, "d").unwrap();
let d = out
.column(1)
.as_any()
.downcast_ref::<Float32Array>()
.unwrap();
assert!((d.value(0)).abs() < 1e-6);
assert!((d.value(2) - (1.0 - 3.0 / 5.0)).abs() < 1e-6);
assert!(vector_distance(&batch, 0, &[1.0], DistanceMetric::L2, "d").is_err());
assert!(cosine(&[0.0, 0.0], &[1.0, 0.0]).is_nan());
}
}