Recursive CTE Proposal

[Puchaczov]

Introducing Recursive CTEs to Musoq - Design Discussion

Overview

I'd like to discuss adding recursive Common Table Expression (CTE) support to Musoq. This would enable hierarchical queries and graph traversal scenarios while maintaining Musoq's SQL-like syntax and simplicity.

Proposed Syntax

Basic structure:

with recursive <name> [(<options>)] as (
    -- Anchor member
    <initial_query>
    
    union all
    
    -- Recursive member
    <recursive_query>
)

With configurable options:

maxdepth <number>        -- Maximum recursion depth

Example usage:

with recursive Hierarchy as (
    -- Anchor: Get root nodes
    select Id, ParentId, Name, 0 as Level 
    from #system.source()
    where ParentId is null
    
    union all
    
    -- Recursive: Get child nodes
    select child.Id, child.ParentId, child.Name, parent.Level + 1
    from #system.source() child
    inner join Hierarchy parent on child.ParentId = parent.Id
)
select 
    Level,
    Count(*) as NodesAtLevel,
    string_agg(Name, ', ') as Names
from Hierarchy
group by Level
having Count(*) > 1
order by Level

Key Design Decision: Data Source Awareness

The main architectural decision we need to make is whether data sources should be aware they're participating in a recursive query.

Option 1: Sources Unaware of Recursion

• Data sources operate as they do today
• All recursion handling happens in the query engine
• Simpler plugin development
• Consistent with current separation of concerns

Option 2: Recursion-Aware Sources

• Sources could implement caching strategies
• Better control over memory usage through chunking
• Potential for source-specific optimizations
• More complex plugin API

Discussion Points

1. Should data sources be aware of recursion? Why or why not?
2. What other options should be supported besides maxdepth?
3. How should we handle cycle detection?
4. Are there specific use cases we should consider in the design?
5. What performance characteristics are most important?

Initial Implementation Thoughts

I'm currently leaning towards keeping data sources unaware of recursion because:

• Maintains simple plugin interface
• Consistent with how other operations work
• Engine can optimize recursion globally
• Lower barrier to entry for plugin developers

However, I'm very interested in the community's thoughts on this approach.

Examples of Potential Use Cases

1. File System Traversal

   • Directory hierarchies
   • File dependency chains
   • Configuration inheritance

2. Git Analysis

   • Commit history traversal
   • Branch relationships
   • Merge history analysis

3. Code Analysis

   • Class inheritance chains
   • Dependency graphs
   • Call hierarchies

4. Organizational Data

   • Employee hierarchies
   • Department structures
   • Resource allocation trees

Next Steps

1. Gather community feedback on the design approach
2. Define detailed technical requirements
3. Create prototype implementation
4. Develop test cases

Questions for the Community

1. What scenarios would you use recursive CTEs for?
2. Do you see any issues with the proposed syntax?
3. What optimizations would be most valuable for your use cases?
4. How important is cycle detection for your scenarios?

Implementation Considerations

Key areas that will need attention:

graph TD
    A[Recursive CTE Feature] --> B[Parser Changes]
    A --> C[Query Engine Updates]
    A --> D[Memory Management]
    A --> E[Performance Optimization]
    
    B --> B1[Syntax Recognition]
    B --> B2[Validation Rules]
    
    C --> C1[Recursion Control]
    C --> C2[Result Streaming]
    
    D --> D1[Chunking]
    D --> D2[Caching]
    
    E --> E1[Early Termination]
    E --> E2[Parallel Processing]

Loading