rudb_kernels/
compare.rs

1//! Comparing values, which is where SQL's three-valued logic actually lives.
2//!
3//! Six of the eight comparisons return null when either side is null, and the other two never do.
4//! That is not a detail: `WHERE a = b` drops a row where either is null and `WHERE a IS NOT
5//! DISTINCT FROM b` keeps the row where both are, and the binder produces the second one for `IS
6//! NULL` and for a `USING` join under some rewrites. One enum with the null rule attached to the
7//! variant is what stops that difference from being re-decided in every operator.
8//!
9//! The comparison enum here is this crate's own rather than `rudb_plan`'s, because the plan sits
10//! nine ranks above the kernels and a kernel that imports a plan type is a kernel that cannot be
11//! called from anywhere else. The executor maps one to the other, which is four lines it writes
12//! once.
13//!
14//! Float comparison is DuckDB's rather than IEEE's. Two NaNs are equal, NaN sorts above every
15//! number, and negative zero equals zero. IEEE says the first is false and that a NaN comparison is
16//! unordered, which would make `GROUP BY` over a column with a NaN in it produce a group nothing
17//! can ever find again and make a sort's result depend on the order the rows arrived in.
18
19use std::cmp::Ordering;
20
21use rudb_common::{Error, LogicalType, Result, Value};
22use rudb_vector::{Form, Vector};
23
24use crate::number::{approximate, integral};
25
26/// Which comparison.
27#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
28pub enum Comparison {
29    /// `=`, null if either side is null.
30    Equal,
31    /// `<>`, null if either side is null.
32    NotEqual,
33    /// `<`, null if either side is null.
34    Less,
35    /// `<=`, null if either side is null.
36    LessOrEqual,
37    /// `>`, null if either side is null.
38    Greater,
39    /// `>=`, null if either side is null.
40    GreaterOrEqual,
41    /// `IS DISTINCT FROM`, which is total and never null.
42    DistinctFrom,
43    /// `IS NOT DISTINCT FROM`, which is total and never null.
44    NotDistinctFrom,
45}
46
47impl Comparison {
48    /// Whether this comparison treats null as a value rather than as an absence.
49    #[must_use]
50    pub fn is_total(self) -> bool {
51        matches!(self, Self::DistinctFrom | Self::NotDistinctFrom)
52    }
53}
54
55/// Compares two vectors of the same length, producing a `BOOLEAN` vector.
56///
57/// # Errors
58///
59/// If the two sides are not the same length, or if the two types cannot be compared.
60pub fn compare(op: Comparison, left: &Vector, right: &Vector) -> Result<Vector> {
61    if left.len() != right.len() {
62        return Err(Error::internal(format!(
63            "a comparison of a {} row vector with a {} row one",
64            left.len(),
65            right.len()
66        )));
67    }
68    if left.form() == Form::Constant && right.form() == Form::Constant && !left.is_empty() {
69        let single = compare_values(op, &left.value_at(0), &right.value_at(0))?;
70        return Ok(Vector::constant(LogicalType::Boolean, single, left.len()));
71    }
72    let mut values = Vec::with_capacity(left.len());
73    for index in 0..left.len() {
74        values.push(compare_values(op, &left.value_at(index), &right.value_at(index))?);
75    }
76    Vector::from_values(LogicalType::Boolean, &values)
77}
78
79/// Compares two values, producing `TRUE`, `FALSE` or `NULL`.
80///
81/// # Errors
82///
83/// If the two types cannot be compared, which after binding means one of them is a nested type.
84pub fn compare_values(op: Comparison, left: &Value, right: &Value) -> Result<Value> {
85    if op.is_total() {
86        let same = match (left.is_null(), right.is_null()) {
87            (true, true) => true,
88            (true, false) | (false, true) => false,
89            (false, false) => order(left, right)? == Ordering::Equal,
90        };
91        return Ok(Value::Boolean(match op {
92            Comparison::NotDistinctFrom => same,
93            _ => !same,
94        }));
95    }
96    if left.is_null() || right.is_null() {
97        return Ok(Value::Null);
98    }
99    let ordering = order(left, right)?;
100    let held = match op {
101        Comparison::Equal => ordering == Ordering::Equal,
102        Comparison::NotEqual => ordering != Ordering::Equal,
103        Comparison::Less => ordering == Ordering::Less,
104        Comparison::LessOrEqual => ordering != Ordering::Greater,
105        Comparison::Greater => ordering == Ordering::Greater,
106        Comparison::GreaterOrEqual => ordering != Ordering::Less,
107        Comparison::DistinctFrom | Comparison::NotDistinctFrom => {
108            return Err(Error::internal("a total comparison reached the ordered path"));
109        }
110    };
111    Ok(Value::Boolean(held))
112}
113
114/// The order of two values, neither of which is null.
115///
116/// This is the one place the sort order of a type is written down. `ORDER BY`, `GROUP BY`, a merge
117/// join and a min or max aggregate all reach it, and a type that ordered differently in two of
118/// those would produce a query whose answer depends on which operator the optimizer picked.
119///
120/// # Errors
121///
122/// If either value is null, which is the caller's mistake rather than a comparison, or if the
123/// types have no order between them.
124pub fn order(left: &Value, right: &Value) -> Result<Ordering> {
125    match (left, right) {
126        (Value::Null, _) | (_, Value::Null) => {
127            Err(Error::internal("a null reached the ordering path"))
128        }
129        (Value::Boolean(a), Value::Boolean(b)) => Ok(a.cmp(b)),
130        (Value::Varchar(a), Value::Varchar(b)) => Ok(a.as_bytes().cmp(b.as_bytes())),
131        (Value::Blob(a), Value::Blob(b)) => Ok(a.cmp(b)),
132        (Value::Date(a), Value::Date(b)) => Ok(a.cmp(b)),
133        (Value::Time(a), Value::Time(b)) | (Value::Timestamp(a), Value::Timestamp(b)) => {
134            Ok(a.cmp(b))
135        }
136        (
137            Value::Interval { months: am, days: ad, micros: au },
138            Value::Interval { months: bm, days: bd, micros: bu },
139        ) => Ok((am, ad, au).cmp(&(bm, bd, bu))),
140        _ => numeric_order(left, right),
141    }
142}
143
144/// The order of two numbers, which is the case that has to work across representations.
145fn numeric_order(left: &Value, right: &Value) -> Result<Ordering> {
146    if let (Some(a), Some(b)) = (integral(left), integral(right)) {
147        return Ok(a.cmp(&b));
148    }
149    if let (
150        Value::Decimal { unscaled: a, scale: sa, .. },
151        Value::Decimal { unscaled: b, scale: sb, .. },
152    ) = (left, right)
153    {
154        if sa == sb {
155            return Ok(a.cmp(b));
156        }
157    }
158    match (approximate(left), approximate(right)) {
159        (Some(a), Some(b)) => Ok(float_order(a, b)),
160        _ => Err(Error::not_implemented(format!(
161            "comparing {} with {}",
162            left.logical_type(),
163            right.logical_type()
164        ))),
165    }
166}
167
168/// DuckDB's float order: NaN is equal to itself and above everything else, and zero has one place.
169fn float_order(left: f64, right: f64) -> Ordering {
170    if left == right {
171        return Ordering::Equal;
172    }
173    match (left.is_nan(), right.is_nan()) {
174        (true, true) => Ordering::Equal,
175        (true, false) => Ordering::Greater,
176        (false, true) => Ordering::Less,
177        (false, false) => left.partial_cmp(&right).unwrap_or(Ordering::Equal),
178    }
179}
180
181/// The order of two values with nulls in it, for a sort key.
182///
183/// A sort has to put nulls somewhere and SQL lets the query say where, so this takes the answer
184/// rather than deciding it.
185///
186/// # Errors
187///
188/// If the two types have no order between them.
189pub fn order_with_nulls(left: &Value, right: &Value, nulls_first: bool) -> Result<Ordering> {
190    match (left.is_null(), right.is_null()) {
191        (true, true) => Ok(Ordering::Equal),
192        (true, false) => Ok(if nulls_first { Ordering::Less } else { Ordering::Greater }),
193        (false, true) => Ok(if nulls_first { Ordering::Greater } else { Ordering::Less }),
194        (false, false) => order(left, right),
195    }
196}
197
198#[cfg(test)]
199mod tests {
200    use super::*;
201
202    fn compared(op: Comparison, left: Value, right: Value) -> Value {
203        compare_values(op, &left, &right).expect("these types compare")
204    }
205
206    #[test]
207    fn an_ordinary_comparison_is_null_when_either_side_is() {
208        assert_eq!(compared(Comparison::Equal, Value::Integer(1), Value::Null), Value::Null);
209        assert_eq!(compared(Comparison::Less, Value::Null, Value::Integer(1)), Value::Null);
210    }
211
212    #[test]
213    fn a_total_comparison_is_never_null() {
214        assert_eq!(
215            compared(Comparison::NotDistinctFrom, Value::Null, Value::Null),
216            Value::Boolean(true)
217        );
218        assert_eq!(
219            compared(Comparison::NotDistinctFrom, Value::Integer(1), Value::Null),
220            Value::Boolean(false)
221        );
222        assert_eq!(
223            compared(Comparison::DistinctFrom, Value::Integer(1), Value::Null),
224            Value::Boolean(true)
225        );
226    }
227
228    #[test]
229    fn a_string_compares_by_bytes() {
230        assert_eq!(
231            compared(Comparison::Less, Value::Varchar("a".into()), Value::Varchar("b".into())),
232            Value::Boolean(true)
233        );
234        assert_eq!(
235            compared(Comparison::Less, Value::Varchar("Z".into()), Value::Varchar("a".into())),
236            Value::Boolean(true)
237        );
238    }
239
240    /// The reason this crate does not use `f64::partial_cmp` directly. A NaN that compared
241    /// unordered would make a group by produce a group nothing can find again.
242    #[test]
243    fn two_nans_are_one_value_and_they_sort_above_the_numbers() {
244        assert_eq!(
245            compared(Comparison::Equal, Value::Double(f64::NAN), Value::Double(f64::NAN)),
246            Value::Boolean(true)
247        );
248        assert_eq!(
249            compared(Comparison::Greater, Value::Double(f64::NAN), Value::Double(1e300)),
250            Value::Boolean(true)
251        );
252    }
253
254    #[test]
255    fn zero_has_one_value_however_it_is_signed() {
256        assert_eq!(
257            compared(Comparison::Equal, Value::Double(0.0), Value::Double(-0.0)),
258            Value::Boolean(true)
259        );
260    }
261
262    #[test]
263    fn a_number_compares_the_same_however_it_is_stored() {
264        assert_eq!(
265            compared(Comparison::Equal, Value::Integer(3), Value::BigInt(3)),
266            Value::Boolean(true)
267        );
268        assert_eq!(
269            compared(Comparison::Less, Value::Integer(3), Value::Double(3.5)),
270            Value::Boolean(true)
271        );
272    }
273
274    #[test]
275    fn nulls_go_where_the_query_asked_for_them() {
276        assert_eq!(
277            order_with_nulls(&Value::Null, &Value::Integer(1), true).expect("orders"),
278            Ordering::Less
279        );
280        assert_eq!(
281            order_with_nulls(&Value::Null, &Value::Integer(1), false).expect("orders"),
282            Ordering::Greater
283        );
284    }
285
286    #[test]
287    fn two_constant_vectors_cost_one_comparison() {
288        let left = Vector::constant(LogicalType::Integer, Value::Integer(1), 512);
289        let right = Vector::constant(LogicalType::Integer, Value::Integer(2), 512);
290        let result = compare(Comparison::Less, &left, &right).expect("compares");
291        assert_eq!(result.form(), Form::Constant);
292        assert_eq!(result.value_at(500), Value::Boolean(true));
293    }
294
295    #[test]
296    fn a_comparison_of_two_vectors_is_one_answer_per_row() {
297        let left = Vector::from_values(
298            LogicalType::Integer,
299            &[Value::Integer(1), Value::Integer(5), Value::Null],
300        )
301        .expect("three rows");
302        let right = Vector::constant(LogicalType::Integer, Value::Integer(3), 3);
303        let result = compare(Comparison::Greater, &left, &right).expect("compares");
304        assert_eq!(result.value_at(0), Value::Boolean(false));
305        assert_eq!(result.value_at(1), Value::Boolean(true));
306        assert_eq!(result.value_at(2), Value::Null);
307    }
308
309    #[test]
310    fn two_vectors_of_different_lengths_are_caught() {
311        let left = Vector::constant(LogicalType::Integer, Value::Integer(1), 4);
312        let right = Vector::constant(LogicalType::Integer, Value::Integer(1), 5);
313        let error = compare(Comparison::Equal, &left, &right).expect_err("ragged");
314        assert!(error.message().contains("4 row vector"), "{error}");
315    }
316}
rudb_kernels/compare.rs

rudb_kernels/
compare.rs
