Query Engine Architecture

The KQL query engine transforms queries into efficient execution plans.

Pipeline

KQL Query String
    ↓
Lexer (pest)
    ↓
Parser → AST
    ↓
Query Planner → Logical Plan
    ↓
Optimizer → Physical Plan
    ↓
Executor → Result Set

Components

1. Parser

Pest-based parser with complete operator precedence:

pub fn parse(input: &str) -> Result<Query> {
    let pairs = KQLParser::parse(Rule::query, input)?;
    // ... build AST
}

Supported Syntax:

• MATCH patterns: (a:Label {prop: value})
• Relationships: (a)-[r:TYPE]->(b)
• WHERE clauses: Complex boolean expressions
• ORDER BY: Multi-key sorting
• LIMIT/OFFSET: Pagination
• Aggregations: COUNT, SUM, AVG, MIN, MAX
• GROUP BY: Group contexts

2. Pattern Matcher

Matches graph patterns against the database:

impl PatternMatcher {
    pub fn match_pattern(&self, pattern: &Pattern) -> Vec<Binding> {
        // Find nodes matching label and properties
        // Traverse relationships
        // Return variable bindings
    }
}

3. Filter Executor

Evaluates WHERE clauses:

impl FilterExecutor {
    pub fn evaluate(&self, expr: &Expression, ctx: &Context) -> Result<Value> {
        match expr {
            Expression::And(left, right) => { /* ... */ },
            Expression::Or(left, right) => { /* ... */ },
            Expression::Comparison { op, left, right } => { /* ... */ },
            // ... more operators
        }
    }
}

4. Optimizer

Applies query optimization rules:

Rules:

• Filter Pushdown: Move filters closer to data source
• Limit Pushdown: Apply limits early
• Join Reordering: Optimize join order
• Index Selection: Choose best indices

impl Optimizer {
    pub fn optimize(&self, plan: LogicalPlan) -> PhysicalPlan {
        let mut plan = self.push_down_filters(plan);
        plan = self.push_down_limits(plan);
        plan = self.reorder_joins(plan);
        self.to_physical(plan)
    }
}

Example Execution

Query:

MATCH (f:File)-[:DEFINES]->(fn:Function)
WHERE fn.visibility = 'public'
RETURN f.path, fn.name
ORDER BY fn.name
LIMIT 10

Execution:

1. Match: Find all File nodes
2. Traverse: Follow DEFINES edges to Function nodes
3. Filter: Keep only public functions
4. Project: Extract f.path and fn.name
5. Sort: Order by fn.name
6. Limit: Take first 10 results

Performance

Operation	1000 nodes	10000 nodes
Pattern Match	<1 ms	<10 ms
Filter Evaluation	<0.1 ms	<1 ms
Sort	<0.5 ms	<5 ms

Next Steps

• KQL Syntax Reference
• Performance Tuning