ruvector-dag 2.0.6

Directed Acyclic Graph (DAG) structures for query plan optimization with neural learning
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

//! Integration tests for MinCut optimization

use ruvector_dag::*;

#[test]
fn test_mincut_engine_basic() {
    let mut dag = QueryDag::new();

    // Create a simple query plan: SeqScan -> Filter -> Sort
    let scan = dag.add_node(OperatorNode::seq_scan(0, "users").with_estimates(1000.0, 100.0));
    let filter = dag.add_node(OperatorNode::filter(0, "age > 18").with_estimates(500.0, 50.0));
    let sort =
        dag.add_node(OperatorNode::sort(0, vec!["name".to_string()]).with_estimates(500.0, 150.0));

    dag.add_edge(scan, filter).unwrap();
    dag.add_edge(filter, sort).unwrap();

    // Build min-cut engine
    let mut engine = DagMinCutEngine::new(MinCutConfig::default());
    engine.build_from_dag(&dag);

    assert_eq!(dag.node_count(), 3);
}

#[test]
fn test_bottleneck_analysis() {
    let mut dag = QueryDag::new();

    // Create a query plan with a potential bottleneck
    let scan = dag.add_node(
        OperatorNode::seq_scan(0, "users").with_estimates(10000.0, 1000.0), // High cost
    );
    let filter = dag.add_node(
        OperatorNode::filter(0, "active = true").with_estimates(5000.0, 10.0), // Low cost
    );

    dag.add_edge(scan, filter).unwrap();

    // Compute criticality
    let mut engine = DagMinCutEngine::new(MinCutConfig::default());
    engine.build_from_dag(&dag);
    let criticality = engine.compute_criticality(&dag);

    // Analyze bottlenecks
    let analysis = BottleneckAnalysis::analyze(&dag, &criticality);

    assert!(analysis.total_cost > 0.0);
    assert!(analysis.critical_path_cost > 0.0);
}

#[test]
fn test_redundancy_suggestions() {
    let mut dag = QueryDag::new();

    let scan = dag
        .add_node(OperatorNode::hnsw_scan(0, "embeddings_idx", 100).with_estimates(1000.0, 200.0));

    // Create a high-criticality bottleneck
    let bottleneck = Bottleneck {
        node_id: scan,
        score: 0.8,
        impact_estimate: 160.0,
        suggested_action: "Test".to_string(),
    };

    let suggestions = RedundancySuggestion::generate(&dag, &[bottleneck]);

    assert_eq!(suggestions.len(), 1);
    assert!(matches!(
        suggestions[0].strategy,
        RedundancyStrategy::Prefetch
    ));
}

#[test]
fn test_local_kcut_computation() {
    let mut dag = QueryDag::new();

    // Create a simple chain
    let n0 = dag.add_node(OperatorNode::seq_scan(0, "t0").with_estimates(100.0, 10.0));
    let n1 = dag.add_node(OperatorNode::filter(0, "f1").with_estimates(50.0, 20.0));
    let n2 = dag.add_node(OperatorNode::sort(0, vec!["c1".to_string()]).with_estimates(50.0, 30.0));

    dag.add_edge(n0, n1).unwrap();
    dag.add_edge(n1, n2).unwrap();

    let mut engine = DagMinCutEngine::new(MinCutConfig {
        epsilon: 0.1,
        local_search_depth: 5,
        cache_cuts: true,
    });

    engine.build_from_dag(&dag);
    let result = engine.compute_mincut(n0, n2);

    // Should find some cut
    assert!(result.cut_value >= 0.0);
}

#[test]
fn test_dynamic_edge_update() {
    let mut dag = QueryDag::new();

    let n0 = dag.add_node(OperatorNode::seq_scan(0, "t0").with_estimates(100.0, 10.0));
    let n1 = dag.add_node(OperatorNode::filter(0, "f1").with_estimates(50.0, 20.0));
    let n2 = dag.add_node(OperatorNode::sort(0, vec!["c1".to_string()]).with_estimates(50.0, 30.0));

    dag.add_edge(n0, n1).unwrap();
    dag.add_edge(n1, n2).unwrap();

    let mut engine = DagMinCutEngine::new(MinCutConfig::default());
    engine.build_from_dag(&dag);

    // Test dynamic update - O(n^0.12) amortized
    engine.update_edge(n0, n1, 15.0);

    // Cache should be invalidated
    let result = engine.compute_mincut(n0, n2);
    assert!(result.cut_value >= 0.0);
}

#[test]
fn test_mincut_config() {
    let config = MinCutConfig {
        epsilon: 0.05,
        local_search_depth: 10,
        cache_cuts: false,
    };

    assert_eq!(config.epsilon, 0.05);
    assert_eq!(config.local_search_depth, 10);
    assert!(!config.cache_cuts);
}