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