hawdb_sql/pgq/
lowering.rs

1// Copyright 2026 Nowledge
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::collections::{BTreeMap, BTreeSet};
16use std::fmt;
17
18use hawdb_core::{RelationshipDirection, Value};
19use hawdb_plan_cypher::{ComparisonOp, LogicalPlan, Predicate, Projection, ProjectionExpression};
20use hawdb_sql_syntax::{BinaryOperatorSyntax, GraphEdgeDirection, Span, UnaryOperatorSyntax};
21
22use super::{
23    BoundPgqExpression, BoundPgqExpressionKind, BoundPgqGraphTable, BoundPgqLiteral,
24    BoundPgqPathPrimary, BoundPgqVariable, PgqSlotId,
25};
26
27pub type PgqLoweringParameters = BTreeMap<u32, Value>;
28
29#[derive(Debug, Clone, Copy, PartialEq, Eq)]
30pub enum PgqLoweringErrorCode {
31    InvalidBoundPlan,
32    UnsupportedPath,
33    UnsupportedLabels,
34    UnsupportedExpression,
35    MissingParameter,
36}
37
38#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct PgqLoweringError {
40    pub code: PgqLoweringErrorCode,
41    pub span: Span,
42    pub message: String,
43}
44
45impl PgqLoweringError {
46    fn new(code: PgqLoweringErrorCode, span: Span, message: impl Into<String>) -> Self {
47        Self {
48            code,
49            span,
50            message: message.into(),
51        }
52    }
53}
54
55impl fmt::Display for PgqLoweringError {
56    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
57        write!(
58            formatter,
59            "SQL/PGQ lowering error {:?} at bytes {}..{}: {}",
60            self.code, self.span.start, self.span.end, self.message
61        )
62    }
63}
64
65impl std::error::Error for PgqLoweringError {}
66
67/// Lowers the qualified executable SQL/PGQ subset into HawDB's shared graph
68/// logical operators.
69///
70/// Shapes without an equivalent shared operator fail here. Syntax nodes never
71/// enter the optimizer or executor, and this path never renders Cypher text.
72pub fn lower_bound_pgq_graph_table(
73    table: &BoundPgqGraphTable,
74    parameters: &PgqLoweringParameters,
75) -> Result<LogicalPlan, PgqLoweringError> {
76    let path = match table.pattern.paths.as_slice() {
77        [path] => path,
78        _ => {
79            return Err(PgqLoweringError::new(
80                PgqLoweringErrorCode::InvalidBoundPlan,
81                table.span,
82                "the executable GRAPH_TABLE subset requires exactly one bound path",
83            ));
84        }
85    };
86    let slots = SlotBindings::new(&table.variables)?;
87    let mut factors = path.factors.iter();
88    let first = factors.next().ok_or_else(|| {
89        PgqLoweringError::new(
90            PgqLoweringErrorCode::InvalidBoundPlan,
91            table.span,
92            "the bound graph path is empty",
93        )
94    })?;
95    if first.quantifier.is_some() {
96        return Err(PgqLoweringError::new(
97            PgqLoweringErrorCode::UnsupportedPath,
98            slots.span(primary_slot(&first.primary)),
99            "vertex quantifiers are not executable in the shared graph plan",
100        ));
101    }
102    let BoundPgqPathPrimary::Vertex {
103        slot: first_slot,
104        predicate: first_predicate,
105    } = &first.primary
106    else {
107        return Err(PgqLoweringError::new(
108            PgqLoweringErrorCode::InvalidBoundPlan,
109            slots.span(primary_slot(&first.primary)),
110            "a bound graph path must start with a vertex",
111        ));
112    };
113
114    let first_variable = slots.variable(*first_slot)?;
115    let mut path_slots = BTreeSet::from([*first_slot]);
116    let mut current_name = slots.name(*first_slot)?.to_string();
117    let mut current_label = executable_label(first_variable)?;
118    let mut plan = LogicalPlan::NodeScan {
119        variable: current_name.clone(),
120        label: current_label.clone(),
121    };
122    if let Some(predicate) = first_predicate {
123        plan = filter_plan(plan, lower_predicate(predicate, &slots, parameters)?);
124    }
125
126    while let Some(edge_factor) = factors.next() {
127        let Some(target_factor) = factors.next() else {
128            return Err(PgqLoweringError::new(
129                PgqLoweringErrorCode::InvalidBoundPlan,
130                table.span,
131                "a bound edge is missing its target vertex",
132            ));
133        };
134        if edge_factor
135            .quantifier
136            .as_ref()
137            .is_some_and(|range| range.min != 1 || range.max != 1)
138        {
139            return Err(PgqLoweringError::new(
140                PgqLoweringErrorCode::UnsupportedPath,
141                slots.span(primary_slot(&edge_factor.primary)),
142                "quantified paths require SQL/PGQ walk-semantics qualification",
143            ));
144        }
145        if target_factor.quantifier.is_some() {
146            return Err(PgqLoweringError::new(
147                PgqLoweringErrorCode::UnsupportedPath,
148                slots.span(primary_slot(&target_factor.primary)),
149                "vertex quantifiers are not executable in the shared graph plan",
150            ));
151        }
152        let BoundPgqPathPrimary::Edge {
153            slot: edge_slot,
154            direction,
155            predicate: edge_predicate,
156        } = &edge_factor.primary
157        else {
158            return Err(PgqLoweringError::new(
159                PgqLoweringErrorCode::InvalidBoundPlan,
160                slots.span(primary_slot(&edge_factor.primary)),
161                "bound graph paths must alternate vertex and edge factors",
162            ));
163        };
164        let BoundPgqPathPrimary::Vertex {
165            slot: target_slot,
166            predicate: target_predicate,
167        } = &target_factor.primary
168        else {
169            return Err(PgqLoweringError::new(
170                PgqLoweringErrorCode::UnsupportedPath,
171                slots.span(primary_slot(&target_factor.primary)),
172                "parenthesized paths are not executable in the shared graph plan",
173            ));
174        };
175
176        let edge = slots.variable(*edge_slot)?;
177        let target = slots.variable(*target_slot)?;
178        for slot in [*edge_slot, *target_slot] {
179            if !path_slots.insert(slot) {
180                return Err(PgqLoweringError::new(
181                    PgqLoweringErrorCode::UnsupportedPath,
182                    slots.span(slot),
183                    "reused graph variables require an explicit identity constraint in the shared graph plan",
184                ));
185            }
186        }
187        let target_name = slots.name(*target_slot)?.to_string();
188        let target_label = executable_label(target)?;
189        plan = LogicalPlan::Expand {
190            source_variable: current_name,
191            source_label: current_label,
192            rel_variable: Some(slots.name(*edge_slot)?.to_string()),
193            rel_type: executable_label(edge)?,
194            rel_properties: BTreeMap::new(),
195            direction: lower_direction(*direction),
196            target_variable: target_name.clone(),
197            target_label: target_label.clone(),
198            min_hops: 1,
199            max_hops: 1,
200            optional: false,
201            input: Box::new(plan),
202        };
203        let mut predicates = Vec::new();
204        if let Some(predicate) = edge_predicate {
205            predicates.push(lower_predicate(predicate, &slots, parameters)?);
206        }
207        if let Some(predicate) = target_predicate {
208            predicates.push(lower_predicate(predicate, &slots, parameters)?);
209        }
210        if !predicates.is_empty() {
211            plan = filter_plan(plan, and_predicates(predicates));
212        }
213        current_name = target_name;
214        current_label = target_label;
215    }
216
217    if let Some(predicate) = &table.pattern.predicate {
218        plan = filter_plan(plan, lower_predicate(predicate, &slots, parameters)?);
219    }
220    let items = table
221        .columns
222        .iter()
223        .map(|column| {
224            Ok(Projection {
225                expression: lower_projection(&column.expression, &slots, parameters)?,
226                name: column.name.clone(),
227            })
228        })
229        .collect::<Result<Vec<_>, PgqLoweringError>>()?;
230    Ok(LogicalPlan::Project {
231        items,
232        input: Box::new(plan),
233    })
234}
235
236struct SlotBindings<'a> {
237    variables: BTreeMap<PgqSlotId, &'a BoundPgqVariable>,
238    names: BTreeMap<PgqSlotId, String>,
239}
240
241impl<'a> SlotBindings<'a> {
242    fn new(variables: &'a [BoundPgqVariable]) -> Result<Self, PgqLoweringError> {
243        let mut by_slot = BTreeMap::new();
244        let mut used_names = variables
245            .iter()
246            .filter_map(|variable| variable.name.clone())
247            .collect::<BTreeSet<_>>();
248        let mut names = BTreeMap::new();
249        for variable in variables {
250            if by_slot.insert(variable.slot, variable).is_some() {
251                return Err(PgqLoweringError::new(
252                    PgqLoweringErrorCode::InvalidBoundPlan,
253                    variable.span,
254                    format!("duplicate bound graph slot {}", variable.slot.0),
255                ));
256            }
257            let name = variable.name.clone().unwrap_or_else(|| {
258                unique_internal_name(
259                    format!("__hawdb_pgq_slot_{}", variable.slot.0),
260                    &mut used_names,
261                )
262            });
263            names.insert(variable.slot, name);
264        }
265        Ok(Self {
266            variables: by_slot,
267            names,
268        })
269    }
270
271    fn variable(&self, slot: PgqSlotId) -> Result<&'a BoundPgqVariable, PgqLoweringError> {
272        self.variables.get(&slot).copied().ok_or_else(|| {
273            PgqLoweringError::new(
274                PgqLoweringErrorCode::InvalidBoundPlan,
275                Span::new(0, 0),
276                format!("bound graph slot {} is missing", slot.0),
277            )
278        })
279    }
280
281    fn name(&self, slot: PgqSlotId) -> Result<&str, PgqLoweringError> {
282        self.names.get(&slot).map(String::as_str).ok_or_else(|| {
283            PgqLoweringError::new(
284                PgqLoweringErrorCode::InvalidBoundPlan,
285                self.span(slot),
286                format!("bound graph slot {} has no logical variable", slot.0),
287            )
288        })
289    }
290
291    fn span(&self, slot: PgqSlotId) -> Span {
292        self.variables
293            .get(&slot)
294            .map_or(Span::new(0, 0), |variable| variable.span)
295    }
296}
297
298fn unique_internal_name(base: String, used_names: &mut BTreeSet<String>) -> String {
299    if used_names.insert(base.clone()) {
300        return base;
301    }
302    let mut suffix = 1u32;
303    loop {
304        let candidate = format!("{base}_{suffix}");
305        if used_names.insert(candidate.clone()) {
306            return candidate;
307        }
308        suffix = suffix.saturating_add(1);
309    }
310}
311
312fn primary_slot(primary: &BoundPgqPathPrimary) -> PgqSlotId {
313    match primary {
314        BoundPgqPathPrimary::Vertex { slot, .. } | BoundPgqPathPrimary::Edge { slot, .. } => *slot,
315        BoundPgqPathPrimary::Parenthesized { path, .. } => path
316            .factors
317            .first()
318            .map_or(PgqSlotId(u32::MAX), |factor| primary_slot(&factor.primary)),
319    }
320}
321
322fn executable_label(variable: &BoundPgqVariable) -> Result<String, PgqLoweringError> {
323    match variable.labels.as_slice() {
324        [] => Ok(String::new()),
325        [label] => Ok(label.clone()),
326        labels => Err(PgqLoweringError::new(
327            PgqLoweringErrorCode::UnsupportedLabels,
328            variable.span,
329            format!(
330                "the shared graph scan supports one exact label per element, found {} labels",
331                labels.len()
332            ),
333        )),
334    }
335}
336
337fn lower_direction(direction: GraphEdgeDirection) -> RelationshipDirection {
338    match direction {
339        GraphEdgeDirection::Left => RelationshipDirection::Incoming,
340        GraphEdgeDirection::Right => RelationshipDirection::Outgoing,
341        GraphEdgeDirection::Any => RelationshipDirection::Undirected,
342    }
343}
344
345fn filter_plan(input: LogicalPlan, predicate: Predicate) -> LogicalPlan {
346    LogicalPlan::Filter {
347        predicate,
348        input: Box::new(input),
349    }
350}
351
352fn and_predicates(mut predicates: Vec<Predicate>) -> Predicate {
353    if predicates.len() == 1 {
354        predicates.pop().expect("one predicate remains")
355    } else {
356        Predicate::And(predicates)
357    }
358}
359
360fn lower_predicate(
361    expression: &BoundPgqExpression,
362    slots: &SlotBindings<'_>,
363    parameters: &PgqLoweringParameters,
364) -> Result<Predicate, PgqLoweringError> {
365    match &expression.kind {
366        BoundPgqExpressionKind::Literal(BoundPgqLiteral::Boolean(value)) => {
367            Ok(Predicate::ConstantBool(*value))
368        }
369        BoundPgqExpressionKind::Parameter(position) => {
370            match parameter(parameters, *position, expression.span)? {
371                Value::Bool(value) => Ok(Predicate::ConstantBool(value)),
372                value => Err(unsupported_expression(
373                    expression.span,
374                    format!("boolean predicate parameter ${position} resolved to {value:?}"),
375                )),
376            }
377        }
378        BoundPgqExpressionKind::Property { slot, property } => Ok(Predicate::PropertyEq {
379            variable: slots.name(*slot)?.to_string(),
380            property: property.clone(),
381            value: Value::Bool(true),
382        }),
383        BoundPgqExpressionKind::Unary {
384            operator: UnaryOperatorSyntax::Not,
385            expression,
386        } => Ok(Predicate::Not(Box::new(lower_predicate(
387            expression, slots, parameters,
388        )?))),
389        BoundPgqExpressionKind::Binary {
390            left,
391            operator: BinaryOperatorSyntax::And,
392            right,
393        } => Ok(Predicate::And(vec![
394            lower_predicate(left, slots, parameters)?,
395            lower_predicate(right, slots, parameters)?,
396        ])),
397        BoundPgqExpressionKind::Binary {
398            left,
399            operator: BinaryOperatorSyntax::Or,
400            right,
401        } => Ok(Predicate::Or(vec![
402            lower_predicate(left, slots, parameters)?,
403            lower_predicate(right, slots, parameters)?,
404        ])),
405        BoundPgqExpressionKind::Binary {
406            left,
407            operator,
408            right,
409        } if is_comparison(*operator) => {
410            lower_comparison(left, *operator, right, slots, parameters)
411        }
412        BoundPgqExpressionKind::IsNull {
413            expression: inner,
414            negated,
415        } => {
416            let BoundPgqExpressionKind::Property { slot, property } = &inner.kind else {
417                return Err(unsupported_expression(
418                    expression.span,
419                    "IS NULL currently requires a graph property",
420                ));
421            };
422            if *negated {
423                Ok(Predicate::PropertyIsNotNull {
424                    variable: slots.name(*slot)?.to_string(),
425                    property: property.clone(),
426                })
427            } else {
428                Ok(Predicate::PropertyIsNull {
429                    variable: slots.name(*slot)?.to_string(),
430                    property: property.clone(),
431                })
432            }
433        }
434        BoundPgqExpressionKind::InList {
435            expression: inner,
436            values,
437            negated,
438        } => {
439            let BoundPgqExpressionKind::Property { slot, property } = &inner.kind else {
440                return Err(unsupported_expression(
441                    expression.span,
442                    "IN currently requires a graph property on the left",
443                ));
444            };
445            let values = values
446                .iter()
447                .map(|value| lower_constant(value, parameters))
448                .collect::<Result<Vec<_>, _>>()?;
449            let predicate = Predicate::PropertyIn {
450                variable: slots.name(*slot)?.to_string(),
451                property: property.clone(),
452                values,
453            };
454            if *negated {
455                Ok(Predicate::Not(Box::new(predicate)))
456            } else {
457                Ok(predicate)
458            }
459        }
460        BoundPgqExpressionKind::Between {
461            expression: inner,
462            low,
463            high,
464            negated,
465        } => {
466            let predicate = Predicate::And(vec![
467                lower_comparison(
468                    inner,
469                    BinaryOperatorSyntax::GreaterOrEqual,
470                    low,
471                    slots,
472                    parameters,
473                )?,
474                lower_comparison(
475                    inner,
476                    BinaryOperatorSyntax::LessOrEqual,
477                    high,
478                    slots,
479                    parameters,
480                )?,
481            ]);
482            if *negated {
483                Ok(Predicate::Not(Box::new(predicate)))
484            } else {
485                Ok(predicate)
486            }
487        }
488        _ => Err(unsupported_expression(
489            expression.span,
490            "expression has no equivalent shared graph predicate",
491        )),
492    }
493}
494
495fn lower_comparison(
496    left: &BoundPgqExpression,
497    operator: BinaryOperatorSyntax,
498    right: &BoundPgqExpression,
499    slots: &SlotBindings<'_>,
500    parameters: &PgqLoweringParameters,
501) -> Result<Predicate, PgqLoweringError> {
502    let comparison_span = Span::new(left.span.start, right.span.end);
503    let left = lower_projection(left, slots, parameters)?;
504    let right = lower_projection(right, slots, parameters)?;
505    Ok(match operator {
506        BinaryOperatorSyntax::Equal => Predicate::ExpressionEq {
507            expression: left,
508            value: right,
509        },
510        BinaryOperatorSyntax::NotEqual => Predicate::ExpressionNotEq {
511            expression: left,
512            value: right,
513        },
514        BinaryOperatorSyntax::Less => Predicate::ExpressionCompare {
515            expression: left,
516            op: ComparisonOp::Lt,
517            value: right,
518        },
519        BinaryOperatorSyntax::LessOrEqual => Predicate::ExpressionCompare {
520            expression: left,
521            op: ComparisonOp::Lte,
522            value: right,
523        },
524        BinaryOperatorSyntax::Greater => Predicate::ExpressionCompare {
525            expression: left,
526            op: ComparisonOp::Gt,
527            value: right,
528        },
529        BinaryOperatorSyntax::GreaterOrEqual => Predicate::ExpressionCompare {
530            expression: left,
531            op: ComparisonOp::Gte,
532            value: right,
533        },
534        _ => {
535            return Err(unsupported_expression(
536                comparison_span,
537                "non-comparison operator reached comparison lowering",
538            ));
539        }
540    })
541}
542
543fn lower_projection(
544    expression: &BoundPgqExpression,
545    slots: &SlotBindings<'_>,
546    parameters: &PgqLoweringParameters,
547) -> Result<ProjectionExpression, PgqLoweringError> {
548    match &expression.kind {
549        BoundPgqExpressionKind::Variable(slot) => Ok(ProjectionExpression::Variable {
550            variable: slots.name(*slot)?.to_string(),
551        }),
552        BoundPgqExpressionKind::Property { slot, property } => Ok(ProjectionExpression::Property {
553            variable: slots.name(*slot)?.to_string(),
554            property: property.clone(),
555        }),
556        BoundPgqExpressionKind::Parameter(position) => Ok(ProjectionExpression::Literal(
557            parameter(parameters, *position, expression.span)?,
558        )),
559        BoundPgqExpressionKind::Literal(_) => Ok(ProjectionExpression::Literal(lower_constant(
560            expression, parameters,
561        )?)),
562        BoundPgqExpressionKind::Unary {
563            operator: UnaryOperatorSyntax::Plus,
564            expression,
565        } => lower_projection(expression, slots, parameters),
566        BoundPgqExpressionKind::Unary {
567            operator: UnaryOperatorSyntax::Minus,
568            expression: inner,
569        } => match lower_constant(inner, parameters)? {
570            Value::Int(value) => value
571                .checked_neg()
572                .map(Value::Int)
573                .map(ProjectionExpression::Literal)
574                .ok_or_else(|| {
575                    unsupported_expression(expression.span, "integer negation overflows")
576                }),
577            Value::Float(value) => Ok(ProjectionExpression::Literal(Value::Float(-value))),
578            _ => Err(unsupported_expression(
579                expression.span,
580                "unary minus currently requires a numeric constant",
581            )),
582        },
583        BoundPgqExpressionKind::Function {
584            name,
585            arguments,
586            distinct: false,
587        } if name
588            .last()
589            .is_some_and(|name| name.eq_ignore_ascii_case("lower"))
590            && arguments.len() == 1 =>
591        {
592            Ok(ProjectionExpression::Lower(Box::new(lower_projection(
593                &arguments[0],
594                slots,
595                parameters,
596            )?)))
597        }
598        _ => Err(unsupported_expression(
599            expression.span,
600            "expression has no equivalent shared graph projection",
601        )),
602    }
603}
604
605fn lower_constant(
606    expression: &BoundPgqExpression,
607    parameters: &PgqLoweringParameters,
608) -> Result<Value, PgqLoweringError> {
609    match &expression.kind {
610        BoundPgqExpressionKind::Parameter(position) => {
611            parameter(parameters, *position, expression.span)
612        }
613        BoundPgqExpressionKind::Literal(literal) => Ok(match literal {
614            BoundPgqLiteral::Null => Value::Null,
615            BoundPgqLiteral::Boolean(value) => Value::Bool(*value),
616            BoundPgqLiteral::Int64(value) => Value::Int(*value),
617            BoundPgqLiteral::Float64(value) => Value::Float(*value),
618            BoundPgqLiteral::String(value) => Value::String(value.clone()),
619            BoundPgqLiteral::TypedString { value, .. } => Value::String(value.clone()),
620        }),
621        _ => Err(unsupported_expression(
622            expression.span,
623            "a constant literal or bound parameter is required",
624        )),
625    }
626}
627
628fn parameter(
629    parameters: &PgqLoweringParameters,
630    position: u32,
631    span: Span,
632) -> Result<Value, PgqLoweringError> {
633    parameters.get(&position).cloned().ok_or_else(|| {
634        PgqLoweringError::new(
635            PgqLoweringErrorCode::MissingParameter,
636            span,
637            format!("PostgreSQL parameter ${position} is not bound"),
638        )
639    })
640}
641
642fn is_comparison(operator: BinaryOperatorSyntax) -> bool {
643    matches!(
644        operator,
645        BinaryOperatorSyntax::Equal
646            | BinaryOperatorSyntax::NotEqual
647            | BinaryOperatorSyntax::Less
648            | BinaryOperatorSyntax::LessOrEqual
649            | BinaryOperatorSyntax::Greater
650            | BinaryOperatorSyntax::GreaterOrEqual
651    )
652}
653
654fn unsupported_expression(span: Span, message: impl Into<String>) -> PgqLoweringError {
655    PgqLoweringError::new(PgqLoweringErrorCode::UnsupportedExpression, span, message)
656}
657
658#[cfg(test)]
659mod tests;
hawdb_sql/pgq/lowering.rs

hawdb_sql/pgq/
lowering.rs
