perf: Replace in-memory cycle detection with database-native recursive CTE

[dean0x]

Overview

Replace the current in-memory graph-based cycle detection with a more scalable, database-native approach using a recursive Common Table Expression (CTE). This avoids loading all dependencies into application memory.

Current Implementation

Location: src/implementations/dependency-repository.ts:154 + src/services/handlers/dependency-handler.ts:80-88

The current approach loads ALL dependencies into memory for cycle detection:

// Build graph from all dependencies (synchronous)
const allDepsRows = this.findAllStmt.all() as Record<string, any>[];
const allDeps = allDepsRows.map(row => this.rowToDependency(row));
graph = new DependencyGraph(allDeps);

Problem

• Loads entire dependency graph into memory on every addDependency call
• Doesn't scale to large graphs (10K+ tasks with complex dependencies)
• O(V + E) memory usage where V = tasks, E = dependencies

Proposed Solution

Use SQLite recursive CTE for cycle detection:

wouldCreateCycleInDB(taskId, dependsOnTaskId) {
  const query = `
    WITH RECURSIVE dependency_path(task) AS (
      SELECT ?
      UNION ALL
      SELECT T.depends_on_task_id FROM task_dependencies T, dependency_path P
      WHERE T.task_id = P.task
    )
    SELECT 1 FROM dependency_path WHERE task = ?;
  `;
  const result = this.db.prepare(query).get(dependsOnTaskId, taskId);
  return !!result;
}

Benefits

• O(1) memory usage - query runs entirely in SQLite
• Better scalability for large graphs
• Leverages database indexes for performance
• Eliminates need for in-memory DependencyGraph during insertion

Trade-offs

• Removes graph caching optimization (but cache is invalidated on every insert anyway)
• Slightly more complex SQL (but standard recursive CTE pattern)
• Requires benchmarking to validate performance improvement

Implementation Plan

1. Add wouldCreateCycleInDB() method to SQLiteDependencyRepository
2. Replace in-memory cycle detection in addDependency() transaction
3. Update tests to verify cycle detection still works correctly
4. Benchmark performance vs current implementation
5. Remove DependencyGraph usage from DependencyRepository (can still be used by handlers for topological sort)

References

• Identified in PR feat: Task Dependencies v0.3.0 - Post-Review Fixes #9 review by qodo-merge-for-open-source
• Related: SQLite Recursive CTEs

Target

v0.3.1 - Performance Optimizations

[dean0x]

Closing as won't-fix - addressed differently in v0.3.1

The performance concern this issue raised has been addressed through a different approach in v0.3.1:

What v0.3.1 implemented instead:

1. Transitive Query Memoization (src/core/dependency-graph.ts:29-33)

   • getAllDependencies() and getAllDependents() results are now cached
   • Cache invalidates only on mutations
   • 90%+ improvement for repeated queries

2. Batch Dependency Resolution (Issue [v0.3.1] Batch Dependency Resolution for 10× Performance #10)

   • Multiple dependencies resolved in single transaction
   • 10x speedup for tasks with many dependencies

3. Deep Copy Fix (Issue CRITICAL: Shallow copy in wouldCreateCycle() corrupts dependency graph #28)

   • Fixed critical bug where shallow copy corrupted the graph
   • Now uses proper deep copy for safe cycle detection

Why not pursue recursive CTE:

1. Working solution exists - In-memory approach is correct and performant
2. Premature optimization - No evidence of actual performance issues at current scale
3. Complexity tradeoff - CTE approach would require rewrite for marginal gains
4. Caching wins - Memoization already addresses the "repeated work" concern

If you're hitting actual performance issues with large dependency graphs, please open a new issue with specific metrics.