Query Execution Plan (QEP)

Summary

A Query Execution Plan (QEP) is represented as a tree of operators. Each operator performs a specific task (e.g., pattern matching, filtering, projection) and produces a result set that feeds into its parent operator.

Overview of Query Execution Plan

1. Tree Structure:

• The QEP is a tree where:
  • Leaf nodes represent data sources (e.g., Holon retrieval or RelationshipMap traversal).
  • Intermediate nodes perform operations (e.g., filtering, joins).
  • Root node represents the final output operator (e.g., RETURN in OpenCypher).

2. Execution:

• The query is executed via a post-order traversal of the tree:
  • Start at the leaves.
  • Compute intermediate results by combining results from child nodes.
  • Finish at the root to produce the final output.

3. Operator Types:

• Operators encapsulate logic for graph query operations such as pattern matching, projection, filtering, aggregation, and joins.

Operand Design

The follow data structures comprise the operands used specifically for query execution:

• Graph -- Represents the entire database or a derived or filtered subset of it.
• Path -- Represents a sequence of connected Holons and relationships for traversal queries.

Separating the operand types simplifies the conceptual model while enabling flexibility in operator behavior. To handle both Graph and Path operands seamlessly, operators can rely on a unified Operand trait that abstracts the underlying type.

The following data structures are also leveraged as operands:

• Holon -- Represents a node (entity) in the graph.
• HolonReference -- Abstract reference to a Holon, supporting lazy loading and encapsulated resolution.
• RelationshipMap -- Organizes relationships between Holons by type.
• HolonCollection -- Encapsulates related Holons for a specific relationship.

Graph

The Graph operand is a fundamental component in any graph query or algebraic framework, and it plays a central role in query execution, data representation, and manipulation. The Graph operand serves as both the data structure for storing graph data a unified representation that operators like MATCH, FILTER, and PROJECT can act upon.

The Graph operand acts as the primary input for query execution. It abstracts the details of storage, indexing, and lazy loading (e.g., via HolonCache), allowing higher-level query logic to focus on semantics without concerning itself with low-level access patterns.

Initially, the Graph operand represents the entire database (HolonSpace). Operations transform the Graph operand into intermediate states. The final result of the query is derived from the Graph operand. For example, in RETURN n.name, the projected name property values are extracted from the intermediate Graph operand.

Definition:

#[derive(Debug, Clone)]
pub struct Graph {
    pub holons: BTreeMap<HolonId, Holon>, // Nodes (can include virtual Holons)
    pub is_subgraph: bool,                // Indicates if this is a subgraph
    // pub virtual_relationships: Option<BTreeMap<RelationshipName, Vec<(HolonId, HolonId)>>>, // Optional virtual edges
    // pub computed_properties: Option<BTreeMap<HolonId, PropertyMap>>, // Temporary properties for Holons
}

NOTE: virtual_relationships and computed_properties will be added to the definition once a clearer sense of their proper representation emerges.

Path

The Path operand represents a sequence of Holons connected by relationships. It’s used for traversal and path-based queries.

Definition:

#[derive(Debug, Clone)]
pub struct Path {
    pub grouped_nodes: Vec<(RelationshipName, HolonCollection>, // Relationship type and target Holons
    pub weight: Option<f64>, // Optional weight for traversal computations
}

Operator Design