Skip to main content

uqa_execution/
projected_predicate.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Scalar predicates compiled against positional storage projections.
8
9use uqa_core::Value;
10use uqa_sql::ast::BinaryOp;
11use uqa_sql::expr::IntegerWidth;
12use uqa_sql::{SQLError, SQLParam};
13
14use crate::{RowSchema, ScalarExpr};
15
16mod compile;
17mod evaluate;
18
19/// A predicate whose column lookups are resolved once to projection slots.
20/// Unsupported expressions return `None` and continue through the canonical
21/// map-backed evaluator.
22pub struct ProjectedPredicate {
23    expression: ProjectedExpr,
24}
25
26pub(super) enum ProjectedIntPredicate {
27    Comparison {
28        field: usize,
29        op: BinaryOp,
30        literal: i64,
31        field_on_left: bool,
32    },
33    Between {
34        field: usize,
35        low: i64,
36        high: i64,
37    },
38}
39
40pub(super) enum ProjectedExpr {
41    Field(usize),
42    Literal(Value),
43    Binary {
44        op: BinaryOp,
45        lhs: Box<Self>,
46        rhs: Box<Self>,
47        integer_width: Option<IntegerWidth>,
48        real_arithmetic: bool,
49    },
50    UnaryMinus(Box<Self>),
51    IntFieldComparison {
52        field: usize,
53        op: BinaryOp,
54        literal: i64,
55        field_on_left: bool,
56    },
57    Not(Box<Self>),
58    And(Vec<Self>),
59    IntFieldConjunction(Vec<ProjectedIntPredicate>),
60    Or(Vec<Self>),
61    IsNull {
62        expression: Box<Self>,
63        negated: bool,
64    },
65    Between {
66        expression: Box<Self>,
67        low: Box<Self>,
68        high: Box<Self>,
69    },
70    IntFieldBetween {
71        field: usize,
72        low: i64,
73        high: i64,
74    },
75    InList {
76        expression: Box<Self>,
77        list: Vec<Self>,
78        negated: bool,
79    },
80    Like {
81        expression: Box<Self>,
82        pattern: uqa_sql::expr::CompiledLikePattern,
83    },
84    Cast {
85        expression: Box<Self>,
86        ty: String,
87    },
88}
89
90impl ProjectedPredicate {
91    pub fn compile(
92        expression: &ScalarExpr,
93        fields: &[String],
94        params: &[SQLParam],
95    ) -> Result<Option<Self>, SQLError> {
96        Self::compile_with_schema(expression, &RowSchema::new(fields.to_vec()), params)
97    }
98
99    /// Compile against structured SQL identities instead of interpreting punctuation in public labels as qualification metadata.
100    pub fn compile_with_schema(
101        expression: &ScalarExpr,
102        schema: &RowSchema,
103        params: &[SQLParam],
104    ) -> Result<Option<Self>, SQLError> {
105        let expression = uqa_sql::bind_type_introspection(expression.clone(), schema, params);
106        Self::compile_bound(&expression, schema, params)
107    }
108
109    pub(crate) fn compile_bound(
110        expression: &ScalarExpr,
111        schema: &RowSchema,
112        params: &[SQLParam],
113    ) -> Result<Option<Self>, SQLError> {
114        match compile::compile(expression, schema, params) {
115            Ok(expression) => Ok(expression.map(|expression| Self { expression })),
116            Err(SQLError::Unsupported(_)) => Ok(None),
117            Err(error) => Err(error),
118        }
119    }
120
121    #[inline]
122    pub fn keep(&self, values: &[&Value]) -> Result<bool, SQLError> {
123        evaluate::keep(&self.expression, values)
124    }
125
126    /// Evaluate against backend-owned values through a positional projection without constructing an intermediate reference array. A `usize::MAX` projection slot reads as SQL NULL.
127    #[inline]
128    pub fn keep_indexed(&self, values: &[Value], projection: &[usize]) -> Result<bool, SQLError> {
129        evaluate::keep_indexed(&self.expression, values, projection)
130    }
131
132    /// Evaluate directly against a composite physical row. Column names and
133    /// qualifiers were resolved to logical positions during compilation, so
134    /// the hot path neither builds a named row nor allocates a reference list.
135    #[inline]
136    pub fn keep_row(&self, row: &crate::PhysicalRowView<'_>) -> Result<bool, SQLError> {
137        evaluate::keep_row(&self.expression, row)
138    }
139}
140
141#[cfg(test)]
142mod tests {
143    use super::*;
144    use crate::RowSchemaExecution;
145    use crate::{eval_scalar, ScalarEvalContext};
146    use uqa_sql::ast::ColumnType;
147    use uqa_sql::expr::truthy;
148
149    #[test]
150    fn positional_predicate_preserves_null_and_short_circuit_semantics() {
151        let expression = ScalarExpr::And(vec![
152            ScalarExpr::Between {
153                expr: Box::new(ScalarExpr::Column("x".into())),
154                low: Box::new(ScalarExpr::Literal(Value::Int(2))),
155                high: Box::new(ScalarExpr::Literal(Value::Int(4))),
156            },
157            ScalarExpr::IsNull {
158                expr: Box::new(ScalarExpr::Column("y".into())),
159                negated: false,
160            },
161        ]);
162        let predicate = ProjectedPredicate::compile(&expression, &["x".into(), "y".into()], &[])
163            .unwrap()
164            .unwrap();
165        assert!(predicate.keep(&[&Value::Int(3), &Value::Null]).unwrap());
166        assert!(!predicate.keep(&[&Value::Int(5), &Value::Null]).unwrap());
167        assert!(!predicate.keep(&[&Value::Null, &Value::Null]).unwrap());
168
169        let stored = [Value::Null, Value::Int(3)];
170        assert!(predicate.keep_indexed(&stored, &[1, 0]).unwrap());
171        assert!(!predicate.keep_indexed(&stored, &[usize::MAX, 0]).unwrap());
172    }
173
174    #[test]
175    fn projected_q1_and_q6_predicates_match_the_canonical_evaluator() {
176        let fields = vec!["discount".into(), "quantity".into(), "ship_day".into()];
177        let q6 = ScalarExpr::And(vec![
178            ScalarExpr::Between {
179                expr: Box::new(ScalarExpr::Column("ship_day".into())),
180                low: Box::new(ScalarExpr::Param(1)),
181                high: Box::new(ScalarExpr::Literal(Value::Int(2_190))),
182            },
183            ScalarExpr::Between {
184                expr: Box::new(ScalarExpr::Column("discount".into())),
185                low: Box::new(ScalarExpr::Literal(Value::Int(2))),
186                high: Box::new(ScalarExpr::Literal(Value::Int(8))),
187            },
188            ScalarExpr::Binary {
189                op: BinaryOp::Greater,
190                lhs: Box::new(ScalarExpr::Literal(Value::Int(40))),
191                rhs: Box::new(ScalarExpr::Column("quantity".into())),
192            },
193        ]);
194        let params = vec![SQLParam::typed_scalar(
195            Value::Int(365),
196            ColumnType::SmallInteger,
197        )];
198        let predicate = ProjectedPredicate::compile(&q6, &fields, &params)
199            .unwrap()
200            .unwrap();
201        assert!(matches!(
202            &predicate.expression,
203            ProjectedExpr::IntFieldConjunction(items) if items.len() == 3
204        ));
205        let discounts = [Value::Null, Value::Int(1), Value::Int(2), Value::Int(8)];
206        let quantities = [
207            Value::Null,
208            Value::Int(39),
209            Value::Int(40),
210            Value::Float(39.5),
211        ];
212        let ship_days = [
213            Value::Null,
214            Value::Int(364),
215            Value::Int(365),
216            Value::Int(2_190),
217            Value::Int(2_191),
218        ];
219        for discount in &discounts {
220            for quantity in &quantities {
221                for ship_day in &ship_days {
222                    assert_projected_parity(
223                        &q6,
224                        &predicate,
225                        &fields,
226                        &[discount.clone(), quantity.clone(), ship_day.clone()],
227                        &params,
228                    );
229                }
230            }
231        }
232
233        let q1 = ScalarExpr::Binary {
234            op: BinaryOp::LessEqual,
235            lhs: Box::new(ScalarExpr::Column("ship_day".into())),
236            rhs: Box::new(ScalarExpr::Literal(Value::Int(2_449))),
237        };
238        let predicate = ProjectedPredicate::compile(&q1, &fields, &[])
239            .unwrap()
240            .unwrap();
241        for ship_day in [Value::Null, Value::Int(2_449), Value::Int(2_450)] {
242            assert_projected_parity(
243                &q1,
244                &predicate,
245                &fields,
246                &[Value::Int(0), Value::Int(0), ship_day],
247                &[],
248            );
249        }
250    }
251
252    #[test]
253    fn projected_integer_comparisons_match_every_canonical_operator_and_operand_order() {
254        let fields = vec!["value".into()];
255        for op in [
256            BinaryOp::Equal,
257            BinaryOp::NotEqual,
258            BinaryOp::Less,
259            BinaryOp::LessEqual,
260            BinaryOp::Greater,
261            BinaryOp::GreaterEqual,
262        ] {
263            for field_on_left in [true, false] {
264                let field = ScalarExpr::Column("value".into());
265                let literal = ScalarExpr::Literal(Value::Int(7));
266                let expression = ScalarExpr::Binary {
267                    op,
268                    lhs: Box::new(if field_on_left {
269                        field.clone()
270                    } else {
271                        literal.clone()
272                    }),
273                    rhs: Box::new(if field_on_left {
274                        literal.clone()
275                    } else {
276                        field.clone()
277                    }),
278                };
279                let predicate = ProjectedPredicate::compile(&expression, &fields, &[])
280                    .unwrap()
281                    .unwrap();
282                for value in [
283                    Value::Null,
284                    Value::Int(6),
285                    Value::Int(7),
286                    Value::Int(8),
287                    Value::Float(7.0),
288                ] {
289                    assert_projected_parity(&expression, &predicate, &fields, &[value], &[]);
290                }
291            }
292        }
293    }
294
295    #[test]
296    fn projected_like_predicates_match_the_canonical_evaluator() {
297        for (operator, pattern) in [
298            ("LIKE", "%"),
299            ("LIKE", "%green%"),
300            ("LIKE", "%special%requests%"),
301            ("LIKE", "a_c"),
302            ("ILIKE", "%GREEN%"),
303        ] {
304            let expression = parsed_expression(&format!("text {operator} '{pattern}'"));
305            let fields = vec!["text".into()];
306            let predicate = ProjectedPredicate::compile(&expression, &fields, &[])
307                .unwrap()
308                .unwrap();
309            for value in [
310                Value::Str("forest green part".into()),
311                Value::FixedChar("GREEN   ".into()),
312                Value::Str("a-c".into()),
313                Value::Str("special pending requests".into()),
314                Value::Null,
315            ] {
316                assert_projected_parity(&expression, &predicate, &fields, &[value], &[]);
317            }
318        }
319    }
320
321    #[test]
322    fn qualified_like_runs_directly_on_a_composite_physical_row() {
323        let expression = parsed_expression("o.comment NOT LIKE '%special%requests%'");
324        let left_schema =
325            crate::RowSchema::with_qualified_types("c", vec!["id".into()], vec![None]);
326        let right_schema =
327            crate::RowSchema::with_qualified_types("o", vec!["comment".into()], vec![None]);
328        let schema = crate::RowSchema::join(&left_schema, &right_schema, std::iter::empty());
329        let predicate = ProjectedPredicate::compile_with_schema(&expression, &schema, &[])
330            .unwrap()
331            .unwrap();
332
333        let accepted = crate::PhysicalRow::concat(
334            &crate::PhysicalRow::from_values(vec![Value::Int(1)]),
335            &crate::PhysicalRow::from_values(vec![Value::Str("ordinary order".into())]),
336        );
337        let rejected = crate::PhysicalRow::concat(
338            &crate::PhysicalRow::from_values(vec![Value::Int(1)]),
339            &crate::PhysicalRow::from_values(vec![Value::Str("special pending requests".into())]),
340        );
341        assert!(predicate.keep_row(&schema.view(&accepted)).unwrap());
342        assert!(!predicate.keep_row(&schema.view(&rejected)).unwrap());
343    }
344
345    fn parsed_expression(source: &str) -> ScalarExpr {
346        let uqa_sql::Statement::Select(mut query) = uqa_sql::compile(&format!("SELECT {source}"))
347            .unwrap()
348            .remove(0)
349        else {
350            panic!("scalar SELECT");
351        };
352        uqa_sql::plan::ExpressionPlan::lower(query.projections.remove(0).expr).scalar
353    }
354
355    #[test]
356    fn session_dependent_datetime_predicates_keep_the_invoking_evaluator() {
357        let schema = RowSchema::with_types(
358            ["d", "t", "z"].map(str::to_owned).to_vec(),
359            [
360                ColumnType::Date,
361                ColumnType::Timestamp,
362                ColumnType::TimestampTz,
363            ]
364            .map(Some)
365            .to_vec(),
366        );
367        for sql in [
368            "d = z",
369            "z < d",
370            "d BETWEEN z AND z",
371            "d IN (z)",
372            "d = ANY(ARRAY[TIMESTAMPTZ '2020-01-01+00'])",
373            "d <> ALL(ARRAY[TIMESTAMPTZ '2020-01-01+00'])",
374        ] {
375            assert!(
376                ProjectedPredicate::compile_with_schema(&parsed_expression(sql), &schema, &[])
377                    .unwrap()
378                    .is_none(),
379                "{sql}"
380            );
381        }
382        for sql in ["d = d", "d = t", "t = d"] {
383            assert!(
384                ProjectedPredicate::compile_with_schema(&parsed_expression(sql), &schema, &[])
385                    .unwrap()
386                    .is_some(),
387                "{sql}"
388            );
389        }
390    }
391
392    #[test]
393    fn session_dependent_cast_predicates_keep_the_invoking_evaluator() {
394        let schema = RowSchema::with_types(
395            ["d", "t", "z", "s", "n"].map(str::to_owned).to_vec(),
396            [
397                ColumnType::Date,
398                ColumnType::Timestamp,
399                ColumnType::TimestampTz,
400                ColumnType::Text,
401                ColumnType::Integer,
402            ]
403            .map(Some)
404            .to_vec(),
405        );
406        for sql in [
407            "d::timestamptz = z",
408            "t::timestamptz = z",
409            "z::timestamp = t",
410            "z::date = d",
411            "d::timestamp::timestamptz = z",
412            "d::text = s",
413            "s::date = d",
414            "s::timestamptz = z",
415        ] {
416            assert!(
417                ProjectedPredicate::compile_with_schema(&parsed_expression(sql), &schema, &[])
418                    .unwrap()
419                    .is_none(),
420                "{sql}"
421            );
422        }
423        for sql in ["d::timestamp = t", "n::bigint = n", "n::text = s"] {
424            assert!(
425                ProjectedPredicate::compile_with_schema(&parsed_expression(sql), &schema, &[])
426                    .unwrap()
427                    .is_some(),
428                "{sql}"
429            );
430        }
431        assert!(ProjectedPredicate::compile(
432            &parsed_expression("x::smallint = 1"),
433            &["x".into()],
434            &[],
435        )
436        .unwrap()
437        .is_none());
438    }
439
440    #[test]
441    fn projected_predicate_retains_analyzed_datetime_literals() {
442        let expression = ScalarExpr::Binary {
443            op: BinaryOp::Less,
444            lhs: Box::new(ScalarExpr::Column("day".into())),
445            rhs: Box::new(ScalarExpr::Cast {
446                implicit: false,
447                expr: Box::new(ScalarExpr::Literal(Value::Str("1995-03-15".into()))),
448                ty: "date".into(),
449            }),
450        };
451        // Text input still needs the invoking DateStyle. An analyzed temporal constant already owns its value and remains eligible for positional evaluation.
452        assert!(
453            ProjectedPredicate::compile(&expression, &["day".into()], &[])
454                .unwrap()
455                .is_none()
456        );
457        let ScalarExpr::Binary { op, lhs, .. } = expression else {
458            unreachable!();
459        };
460        let expression = ScalarExpr::Binary {
461            op,
462            lhs,
463            rhs: Box::new(ScalarExpr::TypedLiteral {
464                value: Value::Temporal(uqa_core::TemporalValue::Date { days: 9204 }),
465                ty: "date".into(),
466                bound_type: Some(ColumnType::Date),
467                collation_oid: None,
468                composite_source: None,
469                parameter_index: None,
470            }),
471        };
472        let predicate = ProjectedPredicate::compile(&expression, &["day".into()], &[])
473            .unwrap()
474            .unwrap();
475
476        let ProjectedExpr::Binary { rhs, .. } = &predicate.expression else {
477            panic!("expected a compiled comparison");
478        };
479        assert!(matches!(
480            rhs.as_ref(),
481            ProjectedExpr::Literal(Value::Temporal(_))
482        ));
483    }
484
485    #[test]
486    fn projected_predicate_preserves_unary_minus_integer_width() {
487        let expression = ScalarExpr::Binary {
488            op: BinaryOp::Equal,
489            lhs: Box::new(ScalarExpr::UnaryMinus(Box::new(ScalarExpr::Cast {
490                implicit: false,
491                expr: Box::new(ScalarExpr::Column("x".into())),
492                ty: "smallint".into(),
493            }))),
494            rhs: Box::new(ScalarExpr::Literal(Value::Int(-1))),
495        };
496        let schema = RowSchema::with_types(vec!["x".into()], vec![Some(ColumnType::Integer)]);
497        let predicate = ProjectedPredicate::compile_with_schema(&expression, &schema, &[])
498            .unwrap()
499            .unwrap();
500
501        assert!(predicate.keep(&[&Value::Int(1)]).unwrap());
502        let error = predicate
503            .keep(&[&Value::Int(i64::from(i16::MIN))])
504            .expect_err("negating smallint minimum must overflow");
505        assert_eq!(error.sqlstate(), Some("22003"));
506    }
507
508    fn assert_projected_parity(
509        expression: &ScalarExpr,
510        predicate: &ProjectedPredicate,
511        fields: &[String],
512        values: &[Value],
513        params: &[SQLParam],
514    ) {
515        let row = fields
516            .iter()
517            .cloned()
518            .zip(values.iter().cloned())
519            .collect::<uqa_sql::ResultRow>();
520        let expected = eval_scalar(expression, &ScalarEvalContext::new(Some(&row), params))
521            .map(|value| truthy(&value));
522        let references = values.iter().collect::<Vec<_>>();
523        let actual = predicate.keep(&references);
524        match (expected, actual) {
525            (Ok(expected), Ok(actual)) => assert_eq!(actual, expected, "row: {row:?}"),
526            (Err(expected), Err(actual)) => assert_eq!(actual.to_string(), expected.to_string()),
527            (expected, actual) => panic!("projected result {actual:?} != canonical {expected:?}"),
528        }
529    }
530
531    fn membership(dispatch: &str, operator: &str, elements: Vec<Value>, oid: u32) -> ScalarExpr {
532        ScalarExpr::Func {
533            name: dispatch.into(),
534            binding: Some(uqa_sql::ast::FunctionBinding {
535                object_id: None,
536                name: if dispatch == "__any_op" {
537                    "ANY operator"
538                } else {
539                    "ALL operator"
540                }
541                .into(),
542                argument_types: Vec::new(),
543                builtin: true,
544                dispatch: Some(if dispatch == "__any_op" {
545                    uqa_sql::ast::FunctionDispatch::AnyOperator
546                } else {
547                    uqa_sql::ast::FunctionDispatch::AllOperator
548                }),
549                invocation: None,
550                composite_field: None,
551                resolution_error: None,
552                input_collation: None,
553            }),
554            args: vec![
555                ScalarExpr::Column("mode".into()),
556                ScalarExpr::Literal(Value::Array(
557                    uqa_core::ArrayValue::try_new(elements)
558                        .unwrap()
559                        .with_element_type_oid(Some(oid)),
560                )),
561                ScalarExpr::Literal(Value::Str(operator.into())),
562            ],
563            distinct: false,
564            order_by: Vec::new(),
565            order_syntax: uqa_sql::ast::FunctionOrderSyntax::Legacy,
566            filter: None,
567        }
568    }
569
570    #[test]
571    fn literal_array_membership_matches_canonical_any_and_all() {
572        let modes = || {
573            vec![
574                Value::FixedChar("AIR".into()),
575                Value::FixedChar("AIR REG".into()),
576            ]
577        };
578        let with_null = || vec![Value::Int(1), Value::Null];
579        let mut typed = membership("__any_op", "=", modes(), 1042);
580        if let ScalarExpr::Func { args, .. } = &mut typed {
581            let ScalarExpr::Literal(value) = args[1].clone() else {
582                unreachable!("literal array")
583            };
584            args[1] = ScalarExpr::TypedLiteral {
585                value,
586                ty: "pg_catalog.\"bpchar\"[]".into(),
587                collation_oid: None,
588                composite_source: None,
589                bound_type: Some(ColumnType::Array(Box::new(ColumnType::Bpchar))),
590                parameter_index: None,
591            };
592        }
593        let cases = [
594            typed,
595            membership("__any_op", "=", modes(), 1042),
596            membership("__all_op", "<>", modes(), 1042),
597            membership("__any_op", "=", with_null(), 23),
598            membership("__all_op", "<>", with_null(), 23),
599        ];
600        let rows = [
601            Value::FixedChar("AIR".into()),
602            Value::FixedChar("MAIL".into()),
603            Value::Int(1),
604            Value::Int(2),
605            Value::Null,
606        ];
607        for expression in &cases {
608            let predicate = ProjectedPredicate::compile(expression, &["mode".into()], &[])
609                .unwrap()
610                .unwrap_or_else(|| panic!("{expression:?} compiles"));
611            for value in &rows {
612                if matches!(
613                    (value, &expression),
614                    (Value::Int(_), ScalarExpr::Func { args, .. })
615                        if matches!(&args[1], ScalarExpr::Literal(Value::Array(array))
616                            if array.element_type_oid() == Some(1042))
617                ) {
618                    continue;
619                }
620                let row = uqa_sql::ResultRow::from([("mode".into(), value.clone())]);
621                let canonical =
622                    eval_scalar(expression, &ScalarEvalContext::new(Some(&row), &[])).unwrap();
623                assert_eq!(
624                    predicate.keep(&[value]).unwrap(),
625                    truthy(&canonical),
626                    "{expression:?} with {value:?}"
627                );
628            }
629        }
630    }
631
632    #[test]
633    fn empty_ordered_or_user_typed_membership_keeps_the_canonical_evaluator() {
634        for expression in [
635            membership("__any_op", "=", Vec::new(), 23),
636            membership("__any_op", "<", vec![Value::Int(1)], 23),
637            membership("__all_op", "=", vec![Value::Int(1)], 23),
638            membership("__any_op", "=", vec![Value::Int(1)], 16_384),
639        ] {
640            assert!(
641                ProjectedPredicate::compile(&expression, &["mode".into()], &[])
642                    .unwrap()
643                    .is_none(),
644                "{expression:?}"
645            );
646        }
647    }
648}