use arrow::datatypes::TimeUnit;
use rustc_hash::{FxHashMap as HashMap, FxHashSet as HashSet};
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum FieldType {
String,
Int64,
Float64,
Boolean,
Dictionary,
Date32,
Timestamp(TimeUnit, Option<Box<str>>),
Decimal128(u8),
}
impl std::str::FromStr for FieldType {
type Err = ();
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
"string" => Ok(FieldType::String),
"int64" => Ok(FieldType::Int64),
"float64" => Ok(FieldType::Float64),
"bool" | "boolean" => Ok(FieldType::Boolean),
"dictionary" => Ok(FieldType::Dictionary),
"date32" => Ok(FieldType::Date32),
s if s.starts_with("timestamp") => parse_timestamp_spec(s).ok_or(()),
"decimal128" => Ok(FieldType::Decimal128(18)),
s if s.starts_with("decimal128(") => {
let scale = s
.trim_start_matches("decimal128(")
.trim_end_matches(')')
.parse::<u8>()
.map_err(|_| ())?;
Ok(FieldType::Decimal128(scale))
}
_ => Err(()),
}
}
}
fn parse_timestamp_spec(s: &str) -> Option<FieldType> {
let rest = s.strip_prefix("timestamp")?;
if rest.is_empty() {
return Some(FieldType::Timestamp(TimeUnit::Microsecond, None));
}
let inner = rest.strip_prefix('[')?.strip_suffix(']')?;
let (unit_str, format) = match inner.split_once(',') {
Some((unit, opt)) => {
let fmt = opt.strip_prefix("format=")?;
if fmt.is_empty() {
return None;
}
(unit, Some(fmt))
}
None => {
if let Some(fmt) = inner.strip_prefix("format=") {
if fmt.is_empty() {
return None;
}
("us", Some(fmt))
} else {
(inner, None)
}
}
};
let unit = match unit_str {
"" | "us" | "µs" => TimeUnit::Microsecond,
"s" => TimeUnit::Second,
"ms" => TimeUnit::Millisecond,
"ns" => TimeUnit::Nanosecond,
_ => return None,
};
let format: Option<Box<str>> =
format.and_then(|f| if f.is_empty() { None } else { Some(f.into()) });
Some(FieldType::Timestamp(unit, format))
}
#[derive(Clone, Default)]
pub struct ExecutionPlan {
pub field_map: HashMap<String, String>,
pub drop_fields: HashSet<String>,
pub field_types: HashMap<String, FieldType>,
pub dictionary_columns: HashSet<String>,
pub filter: Option<FilterPredicate>,
pub schema_order: Vec<String>,
pub auto_dict: bool,
pub dict_threshold: Option<f64>,
pub dict_max_size: Option<usize>,
pub strict_types: bool,
pub max_split_chunks: Option<usize>,
pub observer: Option<std::sync::Arc<dyn crate::RowObserver>>,
}
impl std::fmt::Debug for ExecutionPlan {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("ExecutionPlan")
.field("field_map", &self.field_map)
.field("drop_fields", &self.drop_fields)
.field("field_types", &self.field_types)
.field("dictionary_columns", &self.dictionary_columns)
.field("filter", &self.filter)
.field("schema_order", &self.schema_order)
.field("auto_dict", &self.auto_dict)
.field("dict_threshold", &self.dict_threshold)
.field("dict_max_size", &self.dict_max_size)
.field("strict_types", &self.strict_types)
.field("max_split_chunks", &self.max_split_chunks)
.field("observer", &self.observer.is_some())
.finish()
}
}
impl ExecutionPlan {
pub fn new() -> Self {
Self::default()
}
pub fn rename(mut self, raw: impl Into<String>, output: impl Into<String>) -> Self {
self.field_map.insert(raw.into(), output.into());
self
}
pub fn drop(mut self, field: impl Into<String>) -> Self {
self.drop_fields.insert(field.into());
self
}
pub fn drop_many<I, S>(mut self, fields: I) -> Self
where
I: IntoIterator<Item = S>,
S: Into<String>,
{
self.drop_fields.extend(fields.into_iter().map(Into::into));
self
}
pub fn type_as(mut self, field: impl Into<String>, field_type: FieldType) -> Self {
self.field_types.insert(field.into(), field_type);
self
}
pub fn dictionary(mut self, field: impl Into<String>) -> Self {
self.dictionary_columns.insert(field.into());
self
}
pub fn filter_eq(mut self, field: impl Into<String>, value: impl Into<String>) -> Self {
self.filter = Some(FilterPredicate::Equal {
field: field.into(),
value: value.into(),
});
self
}
pub fn filter_ne(mut self, field: impl Into<String>, value: impl Into<String>) -> Self {
self.filter = Some(FilterPredicate::NotEqual {
field: field.into(),
value: value.into(),
});
self
}
pub fn filter_compare(
mut self,
field_a: impl Into<String>,
op: CompareOp,
field_b: impl Into<String>,
) -> Self {
self.filter = Some(FilterPredicate::Compare {
field_a: field_a.into(),
op,
field_b: field_b.into(),
});
self
}
pub fn schema_order<I, S>(mut self, order: I) -> Self
where
I: IntoIterator<Item = S>,
S: Into<String>,
{
self.schema_order = order.into_iter().map(Into::into).collect();
self
}
pub fn with_auto_dict(mut self, yes: bool) -> Self {
self.auto_dict = yes;
self
}
pub fn with_dict_threshold(mut self, threshold: f64) -> Self {
self.dict_threshold = Some(threshold);
self
}
pub fn with_dict_max_size(mut self, max_size: usize) -> Self {
self.dict_max_size = Some(max_size);
self
}
pub fn with_strict_types(mut self, yes: bool) -> Self {
self.strict_types = yes;
self
}
pub fn with_max_split_chunks(mut self, cap: usize) -> Self {
self.max_split_chunks = Some(cap);
self
}
pub fn with_observer(mut self, observer: std::sync::Arc<dyn crate::RowObserver>) -> Self {
self.observer = Some(observer);
self
}
pub fn column_type(&self, name: &str) -> FieldType {
if let Some(ft) = self.field_types.get(name) {
return ft.clone();
}
if self.dictionary_columns.contains(name) {
return FieldType::Dictionary;
}
FieldType::String
}
pub fn resolve_field<'a>(&'a self, raw: &'a str) -> Option<&'a str> {
let resolved = self.field_map.get(raw).map_or(raw, |s| s.as_str());
if self.drop_fields.contains(resolved) {
return None;
}
if !self.schema_order.is_empty()
&& !self.schema_order.iter().any(|n| n == resolved)
&& !self.filter_references(resolved)
{
return None;
}
Some(resolved)
}
fn filter_references(&self, resolved: &str) -> bool {
fn matches(pred: &FilterPredicate, plan: &ExecutionPlan, resolved: &str) -> bool {
fn ren<'x>(plan: &'x ExecutionPlan, f: &'x String) -> &'x str {
plan.field_map.get(f).map_or(f.as_str(), |s| s.as_str())
}
match pred {
FilterPredicate::Equal { field, .. }
| FilterPredicate::NotEqual { field, .. }
| FilterPredicate::CompareLiteral { field, .. }
| FilterPredicate::StartsWith { field, .. }
| FilterPredicate::EndsWith { field, .. }
| FilterPredicate::In { field, .. }
| FilterPredicate::NotIn { field, .. }
| FilterPredicate::NotField { field, .. }
| FilterPredicate::ArithmeticCompare { field, .. }
| FilterPredicate::Strip { field, .. }
| FilterPredicate::Lower { field, .. }
| FilterPredicate::Upper { field, .. }
| FilterPredicate::Replace { field, .. }
| FilterPredicate::Length { field, .. }
| FilterPredicate::Contains { field, .. }
| FilterPredicate::IsNull { field, .. }
| FilterPredicate::IsType { field, .. }
| FilterPredicate::Regex { field, .. } => ren(plan, field) == resolved,
FilterPredicate::Always(_) => false,
FilterPredicate::Compare {
field_a, field_b, ..
} => ren(plan, field_a) == resolved || ren(plan, field_b) == resolved,
FilterPredicate::And(a, b) | FilterPredicate::Or(a, b) => {
matches(a, plan, resolved) || matches(b, plan, resolved)
}
FilterPredicate::Not(inner) => matches(inner, plan, resolved),
}
}
self.filter
.as_ref()
.is_some_and(|f| matches(f, self, resolved))
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum CompareOp {
Gt,
Lt,
Ge,
Le,
Eq,
Ne,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum ArithOp {
Add,
Sub,
Mul,
Div,
}
impl std::str::FromStr for ArithOp {
type Err = ();
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
"+" | "add" => Ok(ArithOp::Add),
"-" | "sub" => Ok(ArithOp::Sub),
"*" | "mul" => Ok(ArithOp::Mul),
"/" | "div" => Ok(ArithOp::Div),
_ => Err(()),
}
}
}
impl std::str::FromStr for CompareOp {
type Err = ();
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
">" | "gt" => Ok(CompareOp::Gt),
"<" | "lt" => Ok(CompareOp::Lt),
">=" | "ge" => Ok(CompareOp::Ge),
"<=" | "le" => Ok(CompareOp::Le),
"==" | "eq" => Ok(CompareOp::Eq),
"!=" | "ne" => Ok(CompareOp::Ne),
_ => Err(()),
}
}
}
#[derive(Clone, Debug, PartialEq)]
pub enum FilterPredicate {
NotEqual { field: String, value: String },
Equal { field: String, value: String },
Compare {
field_a: String,
op: CompareOp,
field_b: String,
},
CompareLiteral {
field: String,
op: CompareOp,
value: String,
},
StartsWith { field: String, value: String },
EndsWith { field: String, value: String },
In { field: String, values: Vec<String> },
NotIn { field: String, values: Vec<String> },
Always(bool),
NotField { field: String },
ArithmeticCompare {
field: String,
arith_op: ArithOp,
arith_value: f64,
cmp_op: CompareOp,
cmp_value: String,
},
Strip {
field: String,
op: CompareOp,
value: String,
},
Lower {
field: String,
op: CompareOp,
value: String,
},
Upper {
field: String,
op: CompareOp,
value: String,
},
Replace {
field: String,
old: String,
new: String,
op: CompareOp,
value: String,
},
Length {
field: String,
op: CompareOp,
value: String,
},
Contains { field: String, value: String },
IsNull { field: String },
IsType {
field: String,
field_type: FieldType,
},
Regex { field: String, re: RegexSpec },
And(Box<FilterPredicate>, Box<FilterPredicate>),
Or(Box<FilterPredicate>, Box<FilterPredicate>),
Not(Box<FilterPredicate>),
}
#[derive(Clone)]
pub struct RegexSpec {
pub pattern: String,
pub compiled: regex::Regex,
}
impl RegexSpec {
pub fn new(pattern: impl Into<String>) -> std::result::Result<Self, regex::Error> {
let pattern = pattern.into();
let compiled = regex::Regex::new(&pattern)?;
Ok(Self { pattern, compiled })
}
}
impl std::fmt::Debug for RegexSpec {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("RegexSpec")
.field("pattern", &self.pattern)
.finish()
}
}
impl PartialEq for RegexSpec {
fn eq(&self, other: &Self) -> bool {
self.pattern == other.pattern
}
}
impl FilterPredicate {
pub fn all(a: FilterPredicate, b: FilterPredicate) -> Self {
FilterPredicate::And(Box::new(a), Box::new(b))
}
pub fn any(a: FilterPredicate, b: FilterPredicate) -> Self {
FilterPredicate::Or(Box::new(a), Box::new(b))
}
#[allow(clippy::should_implement_trait)]
pub fn not(inner: FilterPredicate) -> Self {
FilterPredicate::Not(Box::new(inner))
}
}
impl FilterPredicate {
pub(crate) fn check(
&self,
columns: &[crate::columnar::ColumnBuilder],
field_index: &HashMap<String, usize>,
row_index: usize,
plan: &ExecutionPlan,
) -> bool {
match self {
FilterPredicate::NotEqual { field, value } => {
let actual = get_value(columns, field_index, field, plan, row_index);
actual.as_deref() != Some(value.as_str())
}
FilterPredicate::Equal { field, value } => {
let actual = get_value(columns, field_index, field, plan, row_index);
actual.as_deref() == Some(value.as_str())
}
FilterPredicate::Compare {
field_a,
op,
field_b,
} => {
let va = get_column(columns, field_index, resolve(field_a, plan))
.and_then(|b| b.get_typed_value(row_index));
let vb = get_column(columns, field_index, resolve(field_b, plan))
.and_then(|b| b.get_typed_value(row_index));
match (va, vb) {
(Some(a), Some(b)) => compare_typed(&a, *op, &b),
_ => false,
}
}
FilterPredicate::CompareLiteral { field, op, value } => {
let va = get_column(columns, field_index, resolve(field, plan))
.and_then(|b| b.get_typed_value(row_index));
if let Some(a) = va {
if let Some(b) = typed_from_literal(&a, value) {
return compare_typed(&a, *op, &b);
}
}
false
}
FilterPredicate::StartsWith { field, value } => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => s.starts_with(value.as_str()),
None => false,
}
}
FilterPredicate::EndsWith { field, value } => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => s.ends_with(value.as_str()),
None => false,
}
}
FilterPredicate::In { field, values } => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => values.contains(&s),
None => false,
}
}
FilterPredicate::NotIn { field, values } => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => !values.contains(&s),
None => true,
}
}
FilterPredicate::Always(keep) => *keep,
FilterPredicate::NotField { field } => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => s.is_empty(),
None => true,
}
}
FilterPredicate::ArithmeticCompare {
field,
arith_op,
arith_value,
cmp_op,
cmp_value,
} => {
let actual = get_column(columns, field_index, resolve(field, plan))
.and_then(|b| b.get_typed_value(row_index));
if let Some(a) = actual {
let field_f64 = match &a {
crate::columnar::TypedValue::Int64(v) => *v as f64,
crate::columnar::TypedValue::Float64(v) => *v,
crate::columnar::TypedValue::Str(s) => s.parse::<f64>().unwrap_or(0.0),
_ => return false,
};
let result = match arith_op {
ArithOp::Add => field_f64 + arith_value,
ArithOp::Sub => field_f64 - arith_value,
ArithOp::Mul => field_f64 * arith_value,
ArithOp::Div => field_f64 / arith_value,
};
let cmp_f64 = cmp_value.parse::<f64>().unwrap_or(0.0);
return apply_op(*cmp_op, result.partial_cmp(&cmp_f64));
}
false
}
FilterPredicate::Strip { field, op, value } => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => {
let transformed = s.trim().to_string();
apply_op(*op, transformed.as_str().partial_cmp(value.as_str()))
}
None => false,
}
}
FilterPredicate::Lower { field, op, value } => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => {
let transformed = s.to_lowercase();
apply_op(*op, transformed.as_str().partial_cmp(value.as_str()))
}
None => false,
}
}
FilterPredicate::Upper { field, op, value } => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => {
let transformed = s.to_uppercase();
apply_op(*op, transformed.as_str().partial_cmp(value.as_str()))
}
None => false,
}
}
FilterPredicate::Replace {
field,
old,
new,
op,
value,
} => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => {
let transformed = s.replace(old.as_str(), new.as_str());
apply_op(*op, transformed.as_str().partial_cmp(value.as_str()))
}
None => false,
}
}
FilterPredicate::Length { field, op, value } => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => {
let len = s.len() as f64;
let cmp_val = value.parse::<f64>().unwrap_or(0.0);
apply_op(*op, len.partial_cmp(&cmp_val))
}
None => false,
}
}
FilterPredicate::Contains { field, value } => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => s.contains(value.as_str()),
None => false,
}
}
FilterPredicate::IsNull { field } => {
let actual = get_value(columns, field_index, field, plan, row_index);
actual.is_none()
}
FilterPredicate::Regex { field, re } => {
let actual = get_value(columns, field_index, field, plan, row_index);
match actual {
Some(s) => re.compiled.is_match(s.as_ref()),
None => false,
}
}
FilterPredicate::IsType { field, field_type } => {
let resolved = resolve(field, plan);
let col = get_column(columns, field_index, resolved);
match col {
None => false,
Some(c) => c.is_type_at(row_index, field_type),
}
}
FilterPredicate::And(a, b) => {
let (first, second) =
if pred_ordinal(a, field_index, plan) <= pred_ordinal(b, field_index, plan) {
(a.as_ref(), b.as_ref())
} else {
(b.as_ref(), a.as_ref())
};
first.check(columns, field_index, row_index, plan)
&& second.check(columns, field_index, row_index, plan)
}
FilterPredicate::Or(a, b) => {
let (first, second) =
if pred_ordinal(a, field_index, plan) <= pred_ordinal(b, field_index, plan) {
(a.as_ref(), b.as_ref())
} else {
(b.as_ref(), a.as_ref())
};
first.check(columns, field_index, row_index, plan)
|| second.check(columns, field_index, row_index, plan)
}
FilterPredicate::Not(inner) => !inner.check(columns, field_index, row_index, plan),
}
}
}
fn resolve<'a>(field: &'a str, plan: &'a ExecutionPlan) -> &'a str {
plan.field_map.get(field).map_or(field, |s| s.as_str())
}
fn get_column<'a>(
columns: &'a [crate::columnar::ColumnBuilder],
field_index: &HashMap<String, usize>,
name: &str,
) -> Option<&'a crate::columnar::ColumnBuilder> {
field_index.get(name).map(|&i| &columns[i])
}
fn get_value(
columns: &[crate::columnar::ColumnBuilder],
field_index: &HashMap<String, usize>,
field: &str,
plan: &ExecutionPlan,
row_index: usize,
) -> Option<String> {
let col = get_column(columns, field_index, resolve(field, plan))?;
if let Some(s) = col.get_filter_view(row_index) {
return Some(s.to_owned());
}
col.get_filter_value(row_index)
}
fn compare_typed(
a: &crate::columnar::TypedValue<'_>,
op: CompareOp,
b: &crate::columnar::TypedValue<'_>,
) -> bool {
use crate::columnar::TypedValue as T;
let num_pair: Option<(f64, f64)> = match (a, b) {
(T::Int64(x), T::Int64(y)) => Some((*x as f64, *y as f64)),
(T::Float64(x), T::Float64(y)) => Some((*x, *y)),
(T::Int64(x), T::Float64(y)) | (T::Float64(y), T::Int64(x)) => Some((*x as f64, *y)),
_ => None,
};
if let Some((x, y)) = num_pair {
return apply_op(op, x.partial_cmp(&y));
}
match (a, b) {
(T::Str(x), T::Str(y)) => apply_op(op, x.cmp(y).into()),
(T::Bool(x), T::Bool(y)) => apply_op(op, x.cmp(y).into()),
(T::Date32(x), T::Date32(y)) => apply_op(op, x.cmp(y).into()),
(T::Timestamp(x), T::Timestamp(y)) => apply_op(op, x.cmp(y).into()),
_ => false,
}
}
fn apply_op(op: CompareOp, ord: Option<std::cmp::Ordering>) -> bool {
use std::cmp::Ordering::*;
let Some(ord) = ord else { return false };
match op {
CompareOp::Gt => ord == Greater,
CompareOp::Lt => ord == Less,
CompareOp::Ge => ord != Less,
CompareOp::Le => ord != Greater,
CompareOp::Eq => ord == Equal,
CompareOp::Ne => ord != Equal,
}
}
fn typed_from_literal<'a>(
sample: &crate::columnar::TypedValue<'a>,
literal: &'a str,
) -> Option<crate::columnar::TypedValue<'a>> {
use crate::columnar::TypedValue as T;
match sample {
T::Str(_) => Some(T::Str(literal)),
T::Int64(_) => literal.parse::<i64>().ok().map(T::Int64),
T::Float64(_) => literal.parse::<f64>().ok().map(T::Float64),
T::Bool(_) => match literal {
"true" | "True" | "TRUE" => Some(T::Bool(true)),
"false" | "False" | "FALSE" => Some(T::Bool(false)),
_ => None,
},
T::Date32(_) => literal.parse::<i32>().ok().map(T::Date32),
T::Timestamp(_) => literal.parse::<i64>().ok().map(T::Timestamp),
}
}
fn pred_ordinal(
pred: &FilterPredicate,
field_index: &HashMap<String, usize>,
plan: &ExecutionPlan,
) -> usize {
match pred {
FilterPredicate::Equal { field, .. }
| FilterPredicate::NotEqual { field, .. }
| FilterPredicate::CompareLiteral { field, .. }
| FilterPredicate::StartsWith { field, .. }
| FilterPredicate::EndsWith { field, .. }
| FilterPredicate::In { field, .. }
| FilterPredicate::NotIn { field, .. }
| FilterPredicate::NotField { field, .. }
| FilterPredicate::ArithmeticCompare { field, .. }
| FilterPredicate::Strip { field, .. }
| FilterPredicate::Lower { field, .. }
| FilterPredicate::Upper { field, .. }
| FilterPredicate::Replace { field, .. }
| FilterPredicate::Length { field, .. }
| FilterPredicate::Contains { field, .. }
| FilterPredicate::IsNull { field, .. }
| FilterPredicate::IsType { field, .. }
| FilterPredicate::Regex { field, .. } => field_index
.get(resolve(field, plan))
.copied()
.unwrap_or(usize::MAX),
FilterPredicate::Always(_) => usize::MAX,
FilterPredicate::Compare {
field_a, field_b, ..
} => {
let a = field_index
.get(resolve(field_a, plan))
.copied()
.unwrap_or(usize::MAX);
let b = field_index
.get(resolve(field_b, plan))
.copied()
.unwrap_or(usize::MAX);
a.min(b)
}
FilterPredicate::And(a, b) | FilterPredicate::Or(a, b) => {
pred_ordinal(a, field_index, plan).min(pred_ordinal(b, field_index, plan))
}
FilterPredicate::Not(inner) => pred_ordinal(inner, field_index, plan),
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_timestamp_spec_plain() {
assert_eq!(
"timestamp".parse::<FieldType>(),
Ok(FieldType::Timestamp(TimeUnit::Microsecond, None))
);
assert_eq!(
"timestamp[ns]".parse::<FieldType>(),
Ok(FieldType::Timestamp(TimeUnit::Nanosecond, None))
);
}
#[test]
fn test_timestamp_spec_format() {
assert_eq!(
"timestamp[ms,format=%Y%m%d %H:%M]".parse::<FieldType>(),
Ok(FieldType::Timestamp(
TimeUnit::Millisecond,
Some("%Y%m%d %H:%M".into())
))
);
assert_eq!(
"timestamp[format=%d/%m/%Y]".parse::<FieldType>(),
Ok(FieldType::Timestamp(
TimeUnit::Microsecond,
Some("%d/%m/%Y".into())
))
);
assert_eq!("timestamp[fortnights]".parse::<FieldType>(), Err(()));
assert_eq!("timestamp[us,color=red]".parse::<FieldType>(), Err(()));
assert_eq!("timestamp[us,format=]".parse::<FieldType>(), Err(()));
}
}