Reorder triples in a chain by selectivity. Uses a greedy approach: 1. Score each unplaced triple by: label selectivity * bound-variable bonus. 2. Place the lowest-cost triple next. 3. Mark its output variables as bound. 4. Repeat until all triples are placed.
(chain: &mut PatternChain, csr: &CsrIndex)
| 44 | /// 3. Mark its output variables as bound. |
| 45 | /// 4. Repeat until all triples are placed. |
| 46 | fn optimize_chain(chain: &mut PatternChain, csr: &CsrIndex) { |
| 47 | let n = chain.triples.len(); |
| 48 | if n <= 1 { |
| 49 | return; // Nothing to reorder. |
| 50 | } |
| 51 | |
| 52 | let mut placed: Vec<PatternTriple> = Vec::with_capacity(n); |
| 53 | let mut remaining: Vec<PatternTriple> = chain.triples.drain(..).collect(); |
| 54 | let mut bound_vars: std::collections::HashSet<String> = std::collections::HashSet::new(); |
| 55 | |
| 56 | for _ in 0..n { |
| 57 | // Score each remaining triple. |
| 58 | let mut best_idx = 0; |
| 59 | let mut best_cost = f64::INFINITY; |
| 60 | |
| 61 | for (idx, triple) in remaining.iter().enumerate() { |
| 62 | let cost = score_triple(triple, csr, &bound_vars); |
| 63 | if cost < best_cost { |
| 64 | best_cost = cost; |
| 65 | best_idx = idx; |
| 66 | } |
| 67 | } |
| 68 | |
| 69 | // Place the best triple. |
| 70 | let triple = remaining.swap_remove(best_idx); |
| 71 | |
| 72 | // Mark variables as bound. |
| 73 | if let Some(ref name) = triple.src.name { |
| 74 | bound_vars.insert(name.clone()); |
| 75 | } |
| 76 | if let Some(ref name) = triple.dst.name { |
| 77 | bound_vars.insert(name.clone()); |
| 78 | } |
| 79 | if let Some(ref name) = triple.edge.name { |
| 80 | bound_vars.insert(name.clone()); |
| 81 | } |
| 82 | |
| 83 | placed.push(triple); |
| 84 | } |
| 85 | |
| 86 | chain.triples = placed; |
| 87 | } |
| 88 | |
| 89 | /// Score a triple for join ordering. Lower = more selective = better. |
| 90 | /// |