fv-value-datafusion 0.3.0

The fv-value expression dialect as DataFusion expressions: exact translation for pushdown and vectorized evaluation, with a per-row UDF fallback.
Documentation
//! Geo calls over a GeoArrow point or WKB column, a column at a time. The literal side is read once
//! (a polygon, a volume, or a point to measure to), and each point is read straight from the
//! column: its coordinates, or its WKB in place. A row the dialect would not read as a plain point
//! (out of range, an altitude that is not a number, a WKB row that is another geometry) is handed
//! to the dialect, so its answer, or its error, is its own.

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

use std::sync::Arc;

use datafusion::arrow::array::{Array, ArrayRef, AsArray, BooleanArray, BooleanBuilder, Float64Array, Float64Builder};
use datafusion::arrow::buffer::{BooleanBuffer, ScalarBuffer};
use datafusion::arrow::datatypes::{DataType, Float64Type};
use datafusion::common::Column;
use datafusion::error::{DataFusionError, Result};
use datafusion::logical_expr::{
    ColumnarValue, Expr as DfExpr, ScalarFunctionArgs, ScalarUDF, ScalarUDFImpl, Signature, Volatility,
};
use fv_value::{BoundExpr, Containment, DistanceTo, Expr, PolygonTest, Value, VolumeTest};

use crate::convert::{wkb_point, wkb_polygons, Cells};

/// A GeoArrow point column's coordinates: x and y, and z when it has one. An `m` is not read.
struct Coords<'a> {
    x: &'a [f64],
    y: &'a [f64],
    z: Option<&'a [f64]>,
    /// Interleaved: the values per point, and the column's first point's offset into them.
    stride: usize,
    offset: usize,
}

impl<'a> Coords<'a> {
    fn of(array: &'a ArrayRef) -> Option<Self> {
        match array.data_type() {
            DataType::Struct(fields) => {
                let s = array.as_struct();
                let col = |name: &str| {
                    let k = fields.iter().position(|f| f.name() == name)?;
                    Some(&s.column(k).as_primitive::<Float64Type>().values()[..])
                };
                Some(Coords {
                    x: col("x")?,
                    y: col("y")?,
                    z: col("z"),
                    stride: 1,
                    offset: 0,
                })
            }
            DataType::FixedSizeList(child, n) => {
                let l = array.as_fixed_size_list();
                let values = &l.values().as_primitive::<Float64Type>().values()[..];
                let n = *n as usize;
                let has_z = n == 4 || (n == 3 && !child.name().ends_with('m'));
                Some(Coords {
                    x: values,
                    y: &values[1..],
                    z: has_z.then(|| &values[2..]),
                    stride: n,
                    offset: l.value_offset(0) as usize,
                })
            }
            _ => None,
        }
    }

    /// Point `i`: x, y, and z when the column has one.
    #[inline]
    fn at(&self, i: usize) -> (f64, f64, Option<f64>) {
        let k = self.offset + i * self.stride;
        (self.x[k], self.y[k], self.z.map(|z| z[k]))
    }
}

/// A point read from the column: x, y, and z when it has one.
type Pt = (f64, f64, Option<f64>);

/// What a call computes for each point of the column, its literal side read once.
#[derive(Debug)]
pub(crate) enum Kernel {
    /// `geoWithin` or `geoContains` (`interior`), or `geoIntersects`, against a literal polygon.
    Polygon { test: PolygonTest, interior: bool },
    /// `geoWithinVolume` against a literal footprint and band: at the call's altitude, else the
    /// row's own.
    Volume { test: VolumeTest, alt: Option<f64> },
    /// `distance3dM` to a literal point: from the row at the call's altitude, else its own, else
    /// the ground.
    Distance { to: DistanceTo, alt: Option<f64> },
    /// `geoContains` or `geoWithin` (`interior`), or `geoIntersects`, of a column of WKB polygons
    /// and a literal point: each row's polygon read in place and placed by the one exact rule.
    PolygonRows { point: geo3d::Geodetic, interior: bool },
}

/// A geo call over a GeoArrow point or WKB column, a column at a time, with the dialect's answers.
#[derive(Debug)]
pub(crate) struct PointColumnUdf {
    name: String,
    kernel: Kernel,
    /// The call itself, bound to the column, for a row the dialect must answer.
    dialect: BoundExpr,
    signature: Signature,
}

/// Runs `$body` with `$bytes` reading row `i`'s WKB bytes, the column's binary type picked once for
/// the batch, so each row reads with no dispatch.
macro_rules! with_bytes {
    ($udf:expr, $array:expr, |$bytes:ident| $body:expr) => {
        match $array.data_type() {
            DataType::Binary => {
                let b = $array.as_binary::<i32>();
                let $bytes = |i: usize| b.value(i);
                $body
            }
            DataType::LargeBinary => {
                let b = $array.as_binary::<i64>();
                let $bytes = |i: usize| b.value(i);
                $body
            }
            DataType::BinaryView => {
                let b = $array.as_binary_view();
                let $bytes = |i: usize| b.value(i);
                $body
            }
            _ => Err(DataFusionError::Internal(format!(
                "{}: not a GeoArrow point or WKB column",
                $udf.name
            ))),
        }
    };
}

/// Runs `$body` with `$at` reading the column's point `i` (`None` for a row that is not a plain
/// point): its coordinates, or its WKB in place, the reader picked once for the batch.
macro_rules! with_points {
    ($udf:expr, $array:expr, |$at:ident| $body:expr) => {
        match Coords::of($array) {
            Some(c) => {
                let $at = |i: usize| Some(c.at(i));
                $body
            }
            None => with_bytes!($udf, $array, |bytes| {
                let $at = |i: usize| wkb_point(bytes(i));
                $body
            }),
        }
    };
}

impl PointColumnUdf {
    /// The UDF for `call` over `column`, computing `kernel`.
    pub(crate) fn new(call: &Expr, column: &str, kernel: Kernel) -> Self {
        let mut h = DefaultHasher::new();
        call.source().hash(&mut h);
        column.hash(&mut h);
        PointColumnUdf {
            name: format!("fv_geo_point_column_{:016x}", h.finish()),
            kernel,
            dialect: call.bind(&[column]),
            signature: Signature::any(1, Volatility::Immutable),
        }
    }

    /// The call expression: the UDF applied to the column.
    pub(crate) fn call_expr(self, column: &str) -> DfExpr {
        ScalarUDF::from(self).call(vec![DfExpr::Column(Column::from_name(column))])
    }

    /// Row `i`'s answer when the column call has none: null for a null row, else the dialect's own
    /// answer or error.
    fn dialect_row(&self, array: &ArrayRef, cells: Cells, i: usize) -> Result<Value> {
        if array.is_null(i) {
            return Ok(Value::Null);
        }
        self.dialect
            .eval(&[cells.value(i)])
            .map_err(|e| DataFusionError::Execution(format!("fv-value: {e}")))
    }

    /// The column's boolean answers, `get` answering row `i` (`None` hands the row to the
    /// dialect): one pass into the result's bits with the input's nulls kept, or, when a row must
    /// go to the dialect, the batch again row by row.
    fn bools(&self, array: &ArrayRef, cells: Cells, get: impl Fn(usize) -> Option<bool>) -> Result<BooleanArray> {
        let nulls = array.nulls();
        let mut handed_back = false;
        let bits = BooleanBuffer::collect_bool(array.len(), |i| {
            if nulls.is_some_and(|nb| nb.is_null(i)) {
                return false;
            }
            get(i).unwrap_or_else(|| {
                handed_back = true;
                false
            })
        });
        if !handed_back {
            return Ok(BooleanArray::new(bits, nulls.cloned()));
        }
        let mut out = BooleanBuilder::with_capacity(array.len());
        for i in 0..array.len() {
            match get(i).filter(|_| array.is_valid(i)) {
                Some(b) => out.append_value(b),
                None => match self.dialect_row(array, cells, i)? {
                    Value::Bool(b) => out.append_value(b),
                    Value::Null => out.append_null(),
                    other => return Err(expected("a boolean", &other)),
                },
            }
        }
        Ok(out.finish())
    }

    /// The column's numbers, as [`bools`](Self::bools) answers them.
    fn numbers(&self, array: &ArrayRef, cells: Cells, get: impl Fn(usize) -> Option<f64>) -> Result<Float64Array> {
        let nulls = array.nulls();
        let mut handed_back = false;
        let values: ScalarBuffer<f64> = (0..array.len())
            .map(|i| {
                if nulls.is_some_and(|nb| nb.is_null(i)) {
                    return 0.0;
                }
                get(i).unwrap_or_else(|| {
                    handed_back = true;
                    0.0
                })
            })
            .collect();
        if !handed_back {
            return Ok(Float64Array::new(values, nulls.cloned()));
        }
        let mut out = Float64Builder::with_capacity(array.len());
        for i in 0..array.len() {
            match get(i).filter(|_| array.is_valid(i)) {
                Some(v) => out.append_value(v),
                None => match self.dialect_row(array, cells, i)? {
                    Value::Num(v) => out.append_value(v),
                    Value::Null => out.append_null(),
                    other => return Err(expected("a number", &other)),
                },
            }
        }
        Ok(out.finish())
    }
}

/// Whether a point's altitude, if it has one, is a number the dialect reads.
#[inline]
fn finite_z(p: &Pt) -> bool {
    p.2.is_none_or(f64::is_finite)
}

fn expected(what: &str, got: &Value) -> DataFusionError {
    DataFusionError::Execution(format!("fv-value: expected {what}, got {}", got.type_name()))
}

// The kernels and `BoundExpr` are not `Hash`/`Eq`; identity is the name, which hashes the source.
impl PartialEq for PointColumnUdf {
    fn eq(&self, o: &Self) -> bool {
        self.name == o.name
    }
}
impl Eq for PointColumnUdf {}
impl Hash for PointColumnUdf {
    fn hash<H: Hasher>(&self, h: &mut H) {
        self.name.hash(h);
    }
}

impl ScalarUDFImpl for PointColumnUdf {
    fn name(&self) -> &str {
        &self.name
    }
    fn signature(&self) -> &Signature {
        &self.signature
    }
    fn return_type(&self, _: &[DataType]) -> Result<DataType> {
        Ok(match self.kernel {
            Kernel::Distance { .. } => DataType::Float64,
            _ => DataType::Boolean,
        })
    }
    fn invoke_with_args(&self, args: ScalarFunctionArgs) -> Result<ColumnarValue> {
        let array = args.args[0].clone().into_array(args.number_rows)?;
        let cells = Cells::of_field(&args.arg_fields[0], &array)?;
        // within and contains take a point's interior; intersects anything but outside
        let take = |interior: bool, c: Containment| {
            if interior {
                c == Containment::Inside
            } else {
                c != Containment::Outside
            }
        };
        let out: ArrayRef = match &self.kernel {
            Kernel::Polygon { test, interior } => {
                let answer = |(x, y, _): Pt| Some(take(*interior, test.containment(x, y)?));
                Arc::new(with_points!(self, &array, |at| self
                    .bools(&array, cells, |i| at(i).filter(finite_z).and_then(answer)))?)
            }
            Kernel::Volume { test, alt } => {
                let answer = |(x, y, z): Pt| test.within(x, y, alt.or(z)?);
                Arc::new(with_points!(self, &array, |at| self
                    .bools(&array, cells, |i| at(i).filter(finite_z).and_then(answer)))?)
            }
            Kernel::Distance { to, alt } => {
                let answer = |(x, y, z): Pt| to.metres(x, y, alt.or(z).unwrap_or(0.0));
                Arc::new(with_points!(self, &array, |at| self
                    .numbers(&array, cells, |i| at(i).filter(finite_z).and_then(answer)))?)
            }
            Kernel::PolygonRows { point, interior } => {
                let answer = |ps| take(*interior, geo3d::multi_polygon_containment(ps, *point));
                Arc::new(with_bytes!(self, &array, |bytes| self
                    .bools(&array, cells, |i| { wkb_polygons(bytes(i)).map(answer) }))?)
            }
        };
        Ok(ColumnarValue::Array(out))
    }
}