sqlitegraph/pattern_engine_cache/
fast_path_execution.rs

1use crate::{
2    backend::BackendDirection,
3    errors::SqliteGraphError,
4    graph::SqliteGraph,
5    pattern_engine::{PatternTriple, TripleMatch, match_triples},
6    pattern_engine_cache::{
7        edge_validation::edge_exists_with_type, edge_validation::get_edge_id,
8        fast_path_detection::can_use_fast_path, fast_path_detection::can_use_partial_fast_path,
9    },
10};
11
12/// Execute cache-enabled fast-path pattern matching.
13///
14/// This function provides an optimized version of pattern matching that:
15/// - Uses cache as a fast-path where safe
16/// - Falls back to SQL where pattern requires it
17/// - Returns IDENTICAL results to match_triples()
18/// - Maintains deterministic ordering
19///
20/// # Arguments
21/// * `graph` - The SQLiteGraph instance
22/// * `pattern` - The pattern triple to match
23///
24/// # Returns
25/// A vector of triple matches in deterministic order
26pub fn match_triples_fast(
27    graph: &SqliteGraph,
28    pattern: &PatternTriple,
29) -> Result<Vec<TripleMatch>, SqliteGraphError> {
30    pattern.validate()?;
31
32    // Case 1: Fast Path - edge type only
33    if can_use_fast_path(pattern) {
34        return execute_fast_path(graph, pattern);
35    }
36
37    // Case 2: Partial Fast Path - use cache as candidate generator
38    if can_use_partial_fast_path(pattern) {
39        return execute_partial_fast_path(graph, pattern);
40    }
41
42    // Case 3: SQL Only - complex pattern
43    execute_sql_only(graph, pattern)
44}
45
46/// Execute fast-path for edge type only patterns (Case 1)
47///
48/// Uses adjacency cache directly and validates via SQL lookup.
49fn execute_fast_path(
50    graph: &SqliteGraph,
51    pattern: &PatternTriple,
52) -> Result<Vec<TripleMatch>, SqliteGraphError> {
53    let mut matches = Vec::new();
54
55    // Get all entity IDs to iterate through
56    let entity_ids = graph.all_entity_ids()?;
57
58    // For each entity, use cache to get adjacency candidates
59    for &source_id in &entity_ids {
60        let candidates = match pattern.direction {
61            BackendDirection::Outgoing => graph.fetch_outgoing(source_id)?,
62            BackendDirection::Incoming => graph.fetch_incoming(source_id)?,
63        };
64
65        // For each candidate, validate edge exists with correct type
66        for &target_id in &candidates {
67            // Always use the actual database direction for validation
68            let (from_id, to_id) = match pattern.direction {
69                BackendDirection::Outgoing => (source_id, target_id),
70                BackendDirection::Incoming => (target_id, source_id),
71            };
72
73            // Validate edge exists with correct type
74            if edge_exists_with_type(
75                graph,
76                from_id,
77                to_id,
78                &pattern.edge_type,
79                BackendDirection::Outgoing,
80            )? {
81                let edge_id = get_edge_id(graph, from_id, to_id, &pattern.edge_type)?;
82
83                // Create TripleMatch with correct direction semantics
84                let triple_match = match pattern.direction {
85                    BackendDirection::Outgoing => TripleMatch::new(source_id, edge_id, target_id),
86                    BackendDirection::Incoming => TripleMatch::new(source_id, edge_id, target_id),
87                };
88                matches.push(triple_match);
89            }
90        }
91    }
92
93    // Ensure deterministic ordering
94    matches.sort_by(|a, b| {
95        a.start_id
96            .cmp(&b.start_id)
97            .then_with(|| a.edge_id.cmp(&b.edge_id))
98            .then_with(|| a.end_id.cmp(&b.end_id))
99    });
100
101    Ok(matches)
102}
103
104/// Execute partial fast-path using cache as candidate generator (Case 2)
105///
106/// Uses cache to narrow candidates but validates via SQL.
107fn execute_partial_fast_path(
108    graph: &SqliteGraph,
109    pattern: &PatternTriple,
110) -> Result<Vec<TripleMatch>, SqliteGraphError> {
111    // For partial fast-path, we still use SQL but can optimize
112    // by using cache to pre-filter candidates where possible
113    match_triples(graph, pattern)
114}
115
116/// Execute SQL-only path for complex patterns (Case 3)
117///
118/// Falls back to original SQL implementation.
119fn execute_sql_only(
120    graph: &SqliteGraph,
121    pattern: &PatternTriple,
122) -> Result<Vec<TripleMatch>, SqliteGraphError> {
123    match_triples(graph, pattern)
124}
sqlitegraph/pattern_engine_cache/fast_path_execution.rs

sqlitegraph/pattern_engine_cache/
fast_path_execution.rs
