oxgraph_db/
query.rs

1//! Native `OxQL` and pinned Cypher-profile query execution.
2
3use oxgraph_graph::{
4    CanonicalElementIdentity, CanonicalRelationIdentity, EdgeSourceGraph, EdgeTargetGraph,
5    TopologyCounts,
6};
7use serde::{Deserialize, Serialize};
8
9use crate::{
10    DbError, ElementId, IncidenceRecord, ProjectionId, PropertyKeyId, PropertySubject,
11    PropertyValue, RelationId,
12    catalog::{ProjectionDefinition, PropertyFamily},
13    projection::GraphProjection,
14    state::DatabaseState,
15    traversal::{self, TraversalDirection, TraversalOptions},
16    value::parse_value_token,
17};
18
19/// Query frontend language.
20///
21/// # Performance
22///
23/// Copying and comparing are `O(1)`.
24#[derive(Clone, Copy, Debug, Deserialize, Eq, Hash, Ord, PartialEq, PartialOrd, Serialize)]
25pub enum QueryLanguage {
26    /// Native topology-first `OxQL` profile.
27    Oxql,
28    /// Pinned Cypher language profile over property-graph projections.
29    Cypher,
30}
31
32/// Prepared query plan.
33///
34/// # Performance
35///
36/// Cloning is `O(query length)`.
37#[derive(Clone, Debug, Eq, PartialEq)]
38pub struct PreparedQuery {
39    /// Source language.
40    language: QueryLanguage,
41    /// Original query text.
42    text: String,
43    /// Physical plan.
44    plan: QueryPlan,
45}
46
47impl PreparedQuery {
48    /// Parses and prepares one query string against current catalog metadata.
49    ///
50    /// # Errors
51    ///
52    /// Returns [`DbError::EmptyQuery`] or [`DbError::UnsupportedQuery`] when the
53    /// query is outside the supported profile.
54    ///
55    /// # Performance
56    ///
57    /// This function is `O(query length + catalog lookup cost)`.
58    pub(crate) fn prepare(
59        language: QueryLanguage,
60        query: &str,
61        state: &DatabaseState,
62    ) -> Result<Self, DbError> {
63        let trimmed = query.trim();
64        if trimmed.is_empty() {
65            return Err(DbError::EmptyQuery);
66        }
67        let logical = match language {
68            QueryLanguage::Oxql => parse_oxql(trimmed)?,
69            QueryLanguage::Cypher => parse_cypher(trimmed)?,
70        };
71        let plan = bind_and_lower(logical, state)?;
72        Ok(Self {
73            language,
74            text: trimmed.to_owned(),
75            plan,
76        })
77    }
78
79    /// Returns the query language.
80    ///
81    /// # Performance
82    ///
83    /// This method is `O(1)`.
84    #[must_use]
85    pub const fn language(&self) -> QueryLanguage {
86        self.language
87    }
88
89    /// Returns the source query text.
90    ///
91    /// # Performance
92    ///
93    /// This method is `O(1)`.
94    #[must_use]
95    pub fn text(&self) -> &str {
96        &self.text
97    }
98
99    /// Returns a stable physical explanation.
100    ///
101    /// # Performance
102    ///
103    /// This method is `O(plan size)`.
104    #[must_use]
105    pub fn explain(&self) -> String {
106        self.plan.explain()
107    }
108
109    /// Executes this prepared plan.
110    ///
111    /// # Errors
112    ///
113    /// Returns [`DbError`] when a referenced projection cannot be materialized.
114    ///
115    /// # Performance
116    ///
117    /// This method is `O(plan output + projection build cost when used)`.
118    pub(crate) fn execute(&self, state: &DatabaseState) -> Result<QueryResult, DbError> {
119        self.plan.execute(state)
120    }
121}
122
123/// Query result materialized for JSON, CLI, and embedded consumers.
124///
125/// # Performance
126///
127/// Iterating rows is `O(row count)`.
128#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
129pub struct QueryResult {
130    /// Materialized rows.
131    rows: Vec<QueryRow>,
132}
133
134impl QueryResult {
135    /// Creates a result from rows.
136    ///
137    /// # Performance
138    ///
139    /// This function is `O(1)` excluding row ownership transfer.
140    #[must_use]
141    pub(crate) const fn new(rows: Vec<QueryRow>) -> Self {
142        Self { rows }
143    }
144
145    /// Returns result rows.
146    ///
147    /// # Performance
148    ///
149    /// This method is `O(1)`.
150    #[must_use]
151    pub fn rows(&self) -> &[QueryRow] {
152        &self.rows
153    }
154}
155
156/// One query result row.
157///
158/// # Performance
159///
160/// Cloning is `O(value count + string/property bytes)`.
161#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
162pub struct QueryRow {
163    /// Values carried by the row.
164    pub values: Vec<QueryValue>,
165}
166
167impl QueryRow {
168    /// Creates a single-value row.
169    ///
170    /// # Performance
171    ///
172    /// This function is `O(1)` excluding value ownership transfer.
173    #[must_use]
174    pub(crate) fn single(value: QueryValue) -> Self {
175        Self {
176            values: vec![value],
177        }
178    }
179}
180
181/// Query value variants used by `OxQL` and the pinned Cypher profile.
182///
183/// # Performance
184///
185/// Cloning is `O(value bytes)`.
186#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
187pub enum QueryValue {
188    /// Canonical element id.
189    Element(ElementId),
190    /// Canonical relation id.
191    Relation(RelationId),
192    /// Canonical incidence record.
193    Incidence(IncidenceRecord),
194    /// Property subject.
195    Subject(PropertySubject),
196    /// Typed property value.
197    Property(PropertyValue),
198    /// Human-readable text value.
199    Text(String),
200    /// Projection id.
201    Projection(ProjectionId),
202}
203
204/// Private physical query plan.
205#[derive(Clone, Debug, Eq, PartialEq)]
206enum QueryPlan {
207    /// Scan all elements.
208    ElementScan,
209    /// Scan all relations.
210    RelationScan,
211    /// Scan all incidences.
212    IncidenceScan,
213    /// Scan elements with a label.
214    ElementLabelScan {
215        /// Label name for explanations.
216        label: String,
217        /// Label ID.
218        label_id: crate::LabelId,
219    },
220    /// Scan elements by property equality.
221    ElementPropertyEqual {
222        /// Property key name for explanations.
223        key: String,
224        /// Property key ID.
225        key_id: PropertyKeyId,
226        /// Required property value.
227        value: PropertyValue,
228    },
229    /// Scan relations by relation type.
230    RelationTypeScan {
231        /// Relation type name for explanations.
232        relation_type: String,
233        /// Relation type ID.
234        relation_type_id: crate::RelationTypeId,
235    },
236    /// Walk a graph projection.
237    GraphWalk {
238        /// Projection ID.
239        projection: ProjectionId,
240        /// Canonical starting element.
241        element: ElementId,
242        /// Traversal options.
243        options: TraversalOptions,
244    },
245    /// Cypher directed edge triple scan.
246    CypherDirectedTriples {
247        /// Graph projection ID.
248        projection: ProjectionId,
249    },
250    /// Catalog metadata scan.
251    CatalogScan,
252}
253
254impl QueryPlan {
255    /// Explains this physical plan.
256    fn explain(&self) -> String {
257        match self {
258            Self::ElementScan => "oxql scan elements".to_owned(),
259            Self::RelationScan => "oxql scan relations".to_owned(),
260            Self::IncidenceScan => "oxql scan incidences".to_owned(),
261            Self::ElementLabelScan { label, .. } => {
262                format!("oxql label index lookup elements label={label}")
263            }
264            Self::ElementPropertyEqual { key, value, .. } => {
265                format!("oxql property equality lookup elements {key}={value}")
266            }
267            Self::RelationTypeScan { relation_type, .. } => {
268                format!("oxql relation-type index lookup type={relation_type}")
269            }
270            Self::GraphWalk {
271                projection,
272                element,
273                options,
274            } => format!(
275                "oxql graph projection {projection} walk from {element} depth {} direction {:?} limit {}",
276                options.max_depth, options.direction, options.limit,
277            ),
278            Self::CypherDirectedTriples { projection } => {
279                format!("cypher directed triple scan projection={projection}")
280            }
281            Self::CatalogScan => "catalog metadata scan".to_owned(),
282        }
283    }
284
285    /// Executes this physical plan.
286    fn execute(&self, state: &DatabaseState) -> Result<QueryResult, DbError> {
287        match self {
288            Self::ElementScan => Ok(scan_elements(state)),
289            Self::RelationScan => Ok(scan_relations(state)),
290            Self::IncidenceScan => Ok(scan_incidences(state)),
291            Self::ElementLabelScan { label_id, .. } => {
292                Ok(scan_elements_with_label(state, *label_id))
293            }
294            Self::ElementPropertyEqual { key_id, value, .. } => {
295                scan_elements_with_property(state, *key_id, value)
296            }
297            Self::RelationTypeScan {
298                relation_type_id, ..
299            } => Ok(scan_relations_with_type(state, *relation_type_id)),
300            Self::GraphWalk {
301                projection,
302                element,
303                options,
304            } => execute_graph_walk(state, *projection, *element, *options),
305            Self::CypherDirectedTriples { projection } => {
306                execute_cypher_triples(state, *projection)
307            }
308            Self::CatalogScan => Ok(scan_catalog(state)),
309        }
310    }
311}
312
313/// Resolved logical operation emitted by parsing, before catalog binding.
314///
315/// The parsers ([`parse_oxql`], [`parse_cypher`]) are purely token/string
316/// driven and never touch the catalog; they produce one of these ops carrying
317/// raw names and literals. [`bind_and_lower`] then resolves names to catalog
318/// IDs, validates value families/types, and produces the physical
319/// [`QueryPlan`]. Cypher node and label scans lower onto the shared element ops
320/// rather than duplicating them.
321#[derive(Clone, Debug, Eq, PartialEq)]
322enum LogicalOp {
323    /// Scan all elements.
324    ElementScan,
325    /// Scan all relations.
326    RelationScan,
327    /// Scan all incidences.
328    IncidenceScan,
329    /// Scan catalog metadata.
330    CatalogScan,
331    /// Scan elements carrying a named label.
332    ElementLabelScan {
333        /// Unresolved label name.
334        label: String,
335    },
336    /// Scan relations of a named relation type.
337    RelationTypeScan {
338        /// Unresolved relation type name.
339        relation_type: String,
340    },
341    /// Scan elements whose named property equals a literal token.
342    ElementPropertyEqual {
343        /// Unresolved property key name.
344        key: String,
345        /// Unparsed property value token.
346        value: String,
347    },
348    /// Walk a named graph projection from a raw element-ID token.
349    GraphWalk {
350        /// Unresolved projection name.
351        projection: String,
352        /// Unparsed element-ID token.
353        element: String,
354        /// Parsed traversal options.
355        options: TraversalOptions,
356    },
357    /// Scan the first graph projection as directed source/relation/target triples.
358    CypherDirectedTriples,
359}
360
361/// Parses native `OxQL` into a logical operation without catalog access.
362fn parse_oxql(query: &str) -> Result<LogicalOp, DbError> {
363    let tokens = query.split_whitespace().collect::<Vec<_>>();
364    let upper = tokens
365        .iter()
366        .map(|token| token.to_ascii_uppercase())
367        .collect::<Vec<_>>();
368    match upper.as_slice() {
369        [command] if command == "CATALOG" => Ok(LogicalOp::CatalogScan),
370        [verb, family] if verb == "MATCH" && family == "ELEMENTS" => Ok(LogicalOp::ElementScan),
371        [verb, family] if verb == "MATCH" && family == "RELATIONS" => Ok(LogicalOp::RelationScan),
372        [verb, family] if verb == "MATCH" && family == "INCIDENCES" => Ok(LogicalOp::IncidenceScan),
373        [verb, family, has, object, _name]
374            if verb == "MATCH" && family == "ELEMENTS" && has == "HAS" && object == "LABEL" =>
375        {
376            Ok(LogicalOp::ElementLabelScan {
377                label: tokens[4].to_owned(),
378            })
379        }
380        [verb, family, r#type, _name]
381            if verb == "MATCH" && family == "RELATIONS" && r#type == "TYPE" =>
382        {
383            Ok(LogicalOp::RelationTypeScan {
384                relation_type: tokens[3].to_owned(),
385            })
386        }
387        [verb, family, r#where, _key, equals, _value]
388            if verb == "MATCH" && family == "ELEMENTS" && r#where == "WHERE" && equals == "=" =>
389        {
390            Ok(LogicalOp::ElementPropertyEqual {
391                key: tokens[3].to_owned(),
392                value: tokens[5].to_owned(),
393            })
394        }
395        [graph, _projection, neighbors, _element]
396            if graph == "GRAPH" && neighbors == "NEIGHBORS" =>
397        {
398            Ok(LogicalOp::GraphWalk {
399                projection: tokens[1].to_owned(),
400                element: tokens[3].to_owned(),
401                options: TraversalOptions::default(),
402            })
403        }
404        [
405            graph,
406            _projection,
407            walk,
408            from,
409            _element,
410            depth,
411            _max_depth,
412            ..,
413        ] if graph == "GRAPH" && walk == "WALK" && from == "FROM" && depth == "DEPTH" => {
414            parse_graph_walk(&tokens, &upper)
415        }
416        _tokens => Err(DbError::unsupported("unsupported OxQL profile query")),
417    }
418}
419
420/// Parses the pinned Cypher language profile into a logical operation.
421fn parse_cypher(query: &str) -> Result<LogicalOp, DbError> {
422    if query == "MATCH (n) RETURN n" {
423        return Ok(LogicalOp::ElementScan);
424    }
425    if query == "MATCH (n)-[r]->(m) RETURN n,r,m" {
426        return Ok(LogicalOp::CypherDirectedTriples);
427    }
428    if let Some(label) = query
429        .strip_prefix("MATCH (n:")
430        .and_then(|rest| rest.strip_suffix(") RETURN n"))
431    {
432        return Ok(LogicalOp::ElementLabelScan {
433            label: label.to_owned(),
434        });
435    }
436    Err(DbError::unsupported("unsupported Cypher profile query"))
437}
438
439/// Parses the optional `DIRECTION`/`LIMIT` clauses of an `OxQL` graph walk.
440fn parse_graph_walk(tokens: &[&str], upper: &[String]) -> Result<LogicalOp, DbError> {
441    let max_depth = tokens[6]
442        .parse::<usize>()
443        .map_err(|_error| DbError::unsupported("walk depth must be an integer"))?;
444    let mut options = TraversalOptions {
445        max_depth,
446        ..TraversalOptions::default()
447    };
448    let mut saw_direction = false;
449    let mut saw_limit = false;
450    let mut index = 7;
451    while index < tokens.len() {
452        let Some(value) = tokens.get(index + 1) else {
453            return Err(DbError::unsupported("walk option requires a value"));
454        };
455        match upper[index].as_str() {
456            "DIRECTION" if !saw_direction => {
457                options.direction = parse_walk_direction(&upper[index + 1])?;
458                saw_direction = true;
459            }
460            "DIRECTION" => return Err(DbError::unsupported("walk direction specified twice")),
461            "LIMIT" if !saw_limit => {
462                options.limit = value
463                    .parse::<usize>()
464                    .map_err(|_error| DbError::unsupported("walk limit must be an integer"))?;
465                saw_limit = true;
466            }
467            "LIMIT" => return Err(DbError::unsupported("walk limit specified twice")),
468            _option => return Err(DbError::unsupported("unsupported walk option")),
469        }
470        index += 2;
471    }
472    Ok(LogicalOp::GraphWalk {
473        projection: tokens[1].to_owned(),
474        element: tokens[4].to_owned(),
475        options,
476    })
477}
478
479/// Parses one `OxQL` graph walk direction.
480fn parse_walk_direction(direction: &str) -> Result<TraversalDirection, DbError> {
481    match direction {
482        "OUTGOING" => Ok(TraversalDirection::Outgoing),
483        "INCOMING" => Ok(TraversalDirection::Incoming),
484        "BOTH" => Ok(TraversalDirection::Both),
485        _direction => Err(DbError::unsupported(
486            "walk direction must be outgoing, incoming, or both",
487        )),
488    }
489}
490
491/// Binds a logical operation against the catalog and lowers it to a plan.
492///
493/// This is the single seam where names resolve to catalog IDs and where
494/// property literals are parsed and family/type-validated. Parsing above never
495/// touches the catalog; execution below never resolves names.
496fn bind_and_lower(op: LogicalOp, state: &DatabaseState) -> Result<QueryPlan, DbError> {
497    match op {
498        LogicalOp::ElementScan => Ok(QueryPlan::ElementScan),
499        LogicalOp::RelationScan => Ok(QueryPlan::RelationScan),
500        LogicalOp::IncidenceScan => Ok(QueryPlan::IncidenceScan),
501        LogicalOp::CatalogScan => Ok(QueryPlan::CatalogScan),
502        LogicalOp::ElementLabelScan { label } => {
503            let label_id = state
504                .catalog()
505                .label_id(&label)
506                .ok_or_else(|| DbError::unsupported(format!("unknown label {label}")))?;
507            Ok(QueryPlan::ElementLabelScan { label, label_id })
508        }
509        LogicalOp::RelationTypeScan { relation_type } => {
510            let relation_type_id = state
511                .catalog()
512                .relation_type_id(&relation_type)
513                .ok_or_else(|| {
514                    DbError::unsupported(format!("unknown relation type {relation_type}"))
515                })?;
516            Ok(QueryPlan::RelationTypeScan {
517                relation_type,
518                relation_type_id,
519            })
520        }
521        LogicalOp::ElementPropertyEqual { key, value } => {
522            let key_id = state
523                .catalog()
524                .property_key_id(&key)
525                .ok_or_else(|| DbError::unsupported(format!("unknown property key {key}")))?;
526            let value = parse_value_token(&value).map_err(DbError::unsupported)?;
527            state.validate_lookup_value_for_family(key_id, PropertyFamily::Element, &value)?;
528            Ok(QueryPlan::ElementPropertyEqual { key, key_id, value })
529        }
530        LogicalOp::GraphWalk {
531            projection,
532            element,
533            options,
534        } => lower_graph_walk(&projection, &element, options, state),
535        LogicalOp::CypherDirectedTriples => Ok(QueryPlan::CypherDirectedTriples {
536            projection: first_graph_projection(state)?,
537        }),
538    }
539}
540
541/// Resolves and validates an `OxQL` graph traversal into a physical walk.
542fn lower_graph_walk(
543    projection: &str,
544    element: &str,
545    options: TraversalOptions,
546    state: &DatabaseState,
547) -> Result<QueryPlan, DbError> {
548    let projection = state
549        .catalog()
550        .projection_id(projection)
551        .ok_or_else(|| DbError::unsupported(format!("unknown projection {projection}")))?;
552    let entry = state
553        .catalog()
554        .projection(projection)
555        .ok_or(DbError::UnknownProjection { id: projection })?;
556    if matches!(&entry.definition, ProjectionDefinition::Hypergraph(_)) {
557        return Err(DbError::invalid_projection("projection is not a graph"));
558    }
559    let raw = element
560        .parse::<u64>()
561        .map_err(|_error| DbError::unsupported("element id must be an integer"))?;
562    Ok(QueryPlan::GraphWalk {
563        projection,
564        element: ElementId::new(raw),
565        options,
566    })
567}
568
569/// Scans all elements.
570fn scan_elements(state: &DatabaseState) -> QueryResult {
571    QueryResult::new(
572        state
573            .elements()
574            .map(|record| QueryRow::single(QueryValue::Element(record.id)))
575            .collect(),
576    )
577}
578
579/// Scans all relations.
580fn scan_relations(state: &DatabaseState) -> QueryResult {
581    QueryResult::new(
582        state
583            .relations()
584            .map(|record| QueryRow::single(QueryValue::Relation(record.id)))
585            .collect(),
586    )
587}
588
589/// Scans all incidences.
590fn scan_incidences(state: &DatabaseState) -> QueryResult {
591    QueryResult::new(
592        state
593            .incidences()
594            .map(|record| QueryRow::single(QueryValue::Incidence(*record)))
595            .collect(),
596    )
597}
598
599/// Scans elements with one label.
600fn scan_elements_with_label(state: &DatabaseState, label_id: crate::LabelId) -> QueryResult {
601    QueryResult::new(
602        state
603            .elements_with_label(label_id)
604            .into_iter()
605            .map(|id| QueryRow::single(QueryValue::Element(id)))
606            .collect(),
607    )
608}
609
610/// Scans elements with a property value.
611fn scan_elements_with_property(
612    state: &DatabaseState,
613    key: PropertyKeyId,
614    value: &PropertyValue,
615) -> Result<QueryResult, DbError> {
616    Ok(QueryResult::new(
617        state
618            .typed_property_equal_for_family(key, PropertyFamily::Element, value)?
619            .into_iter()
620            .filter_map(|subject| match subject {
621                PropertySubject::Element(id) => Some(QueryRow::single(QueryValue::Element(id))),
622                PropertySubject::Relation(_) | PropertySubject::Incidence(_) => None,
623            })
624            .collect(),
625    ))
626}
627
628/// Scans relations with one relation type.
629fn scan_relations_with_type(
630    state: &DatabaseState,
631    relation_type: crate::RelationTypeId,
632) -> QueryResult {
633    QueryResult::new(
634        state
635            .relations_with_type(relation_type)
636            .into_iter()
637            .map(|id| QueryRow::single(QueryValue::Relation(id)))
638            .collect(),
639    )
640}
641
642/// Scans catalog entries.
643fn scan_catalog(state: &DatabaseState) -> QueryResult {
644    let rows = state
645        .catalog()
646        .projections()
647        .map(|entry| QueryRow {
648            values: vec![
649                QueryValue::Projection(entry.id),
650                QueryValue::Text(entry.definition.name().to_owned()),
651            ],
652        })
653        .collect();
654    QueryResult::new(rows)
655}
656
657/// Executes a graph walk.
658fn execute_graph_walk(
659    state: &DatabaseState,
660    projection: ProjectionId,
661    element: ElementId,
662    options: TraversalOptions,
663) -> Result<QueryResult, DbError> {
664    let graph = graph_projection(state, projection)?;
665    let traversal = traversal::traverse_graph_projection(&graph, &[element], options)?;
666    let rows = traversal
667        .rows()
668        .iter()
669        .map(|row| QueryRow::single(QueryValue::Element(row.element)))
670        .collect();
671    Ok(QueryResult::new(rows))
672}
673
674/// Executes the Cypher directed triple profile.
675fn execute_cypher_triples(
676    state: &DatabaseState,
677    projection: ProjectionId,
678) -> Result<QueryResult, DbError> {
679    let graph = graph_projection(state, projection)?;
680    let mut rows = Vec::with_capacity(graph.relation_count());
681    for index in 0..graph.relation_count() {
682        let edge = projection_relation(index)?;
683        rows.push(QueryRow {
684            values: vec![
685                QueryValue::Element(graph.canonical_element_id(graph.source(edge))),
686                QueryValue::Relation(graph.canonical_relation_id(edge)),
687                QueryValue::Element(graph.canonical_element_id(graph.target(edge))),
688            ],
689        });
690    }
691    Ok(QueryResult::new(rows))
692}
693
694/// Materializes a graph projection by ID.
695fn graph_projection(
696    state: &DatabaseState,
697    projection: ProjectionId,
698) -> Result<GraphProjection, DbError> {
699    let entry = state
700        .catalog()
701        .projection(projection)
702        .ok_or(DbError::UnknownProjection { id: projection })?;
703    match &entry.definition {
704        ProjectionDefinition::Graph(definition) => {
705            GraphProjection::from_state(state, definition.clone())
706        }
707        ProjectionDefinition::Hypergraph(_definition) => {
708            Err(DbError::invalid_projection("projection is not a graph"))
709        }
710    }
711}
712
713/// Finds the first graph projection in catalog order.
714fn first_graph_projection(state: &DatabaseState) -> Result<ProjectionId, DbError> {
715    state
716        .catalog()
717        .projections()
718        .find_map(|entry| match &entry.definition {
719            ProjectionDefinition::Graph(_definition) => Some(entry.id),
720            ProjectionDefinition::Hypergraph(_definition) => None,
721        })
722        .ok_or_else(|| DbError::unsupported("Cypher profile requires a graph projection"))
723}
724
725/// Builds a projection relation ID for query execution.
726fn projection_relation(index: usize) -> Result<crate::ProjectionRelationId, DbError> {
727    u32::try_from(index)
728        .map(crate::ProjectionRelationId::new)
729        .map_err(|_error| DbError::IdOverflow)
730}
oxgraph_db/query.rs

oxgraph_db/
query.rs
