1use thiserror::Error;
16
17#[derive(Debug, Error, Clone, PartialEq)]
18pub enum JoinGraphError {
19 #[error("join-order optimization requires at least one relation")]
20 EmptyGraph,
21 #[error("JoinGraph supports at most 64 relations; cannot add `{name}` at index {index}")]
22 TooManyRelations { name: String, index: usize },
23 #[error(
24 "join edge references relation index {index}, but the graph contains {relation_count} relations"
25 )]
26 UnknownRelation { index: usize, relation_count: usize },
27 #[error("relation `{name}` has invalid cardinality estimate {rows}; expected a finite non-negative value")]
28 InvalidCardinality { name: String, rows: f64 },
29 #[error(
30 "relation `{name}` has invalid access cost {cost}; expected a finite non-negative value"
31 )]
32 InvalidAccessCost { name: String, cost: f64 },
33 #[error("join selectivity must be finite and between 0 and 1, got {selectivity}")]
34 InvalidSelectivity { selectivity: f64 },
35 #[error("duplicate join relation alias `{alias}`")]
36 DuplicateAlias { alias: String },
37 #[error("join predicate references unknown relation alias `{alias}`")]
38 UnknownAlias { alias: String },
39 #[error("invalid join plan: {detail}")]
40 InvalidPlan { detail: String },
41}
42
43pub type JoinGraphResult<T> = Result<T, JoinGraphError>;
44
45#[derive(Debug, Clone, Copy)]
46pub struct JoinEdge {
47 pub left: u64,
49 pub right: u64,
51 pub selectivity: f64,
54}
55
56#[derive(Debug, Clone, Default)]
57pub struct JoinGraph {
58 pub(crate) relations: Vec<String>,
61 pub(crate) cardinalities: Vec<f64>,
63 pub(crate) access_costs: Vec<f64>,
65 pub(crate) edges: Vec<JoinEdge>,
68}
69
70impl JoinGraph {
71 pub fn new() -> Self {
72 Self::default()
73 }
74
75 pub fn add_relation(&mut self, name: impl Into<String>, rows: f64) -> JoinGraphResult<usize> {
76 self.add_relation_with_cost(name, rows, rows)
77 }
78
79 pub fn add_relation_with_cost(
80 &mut self,
81 name: impl Into<String>,
82 rows: f64,
83 access_cost: f64,
84 ) -> JoinGraphResult<usize> {
85 let idx = self.relations.len();
86 let name = Self::validate_relation(idx, name.into(), rows, access_cost)?;
87 self.relations.push(name);
88 self.cardinalities.push(rows);
89 self.access_costs.push(access_cost);
90 Ok(idx)
91 }
92
93 pub(crate) fn validate_relation(
94 index: usize,
95 name: String,
96 rows: f64,
97 access_cost: f64,
98 ) -> JoinGraphResult<String> {
99 if index >= 64 {
100 return Err(JoinGraphError::TooManyRelations { name, index });
101 }
102 if !rows.is_finite() || rows < 0.0 {
103 return Err(JoinGraphError::InvalidCardinality { name, rows });
104 }
105 if !access_cost.is_finite() || access_cost < 0.0 {
106 return Err(JoinGraphError::InvalidAccessCost {
107 name,
108 cost: access_cost,
109 });
110 }
111 Ok(name)
112 }
113
114 pub fn add_edge(
115 &mut self,
116 left_idx: usize,
117 right_idx: usize,
118 selectivity: f64,
119 ) -> JoinGraphResult<()> {
120 let edge = Self::validated_edge(self.relation_count(), left_idx, right_idx, selectivity)?;
121 self.edges.push(edge);
122 Ok(())
123 }
124
125 pub(crate) fn validated_edge(
126 relation_count: usize,
127 left_idx: usize,
128 right_idx: usize,
129 selectivity: f64,
130 ) -> JoinGraphResult<JoinEdge> {
131 for index in [left_idx, right_idx] {
132 if index >= relation_count {
133 return Err(JoinGraphError::UnknownRelation {
134 index,
135 relation_count,
136 });
137 }
138 }
139 if !selectivity.is_finite() || !(0.0..=1.0).contains(&selectivity) {
140 return Err(JoinGraphError::InvalidSelectivity { selectivity });
141 }
142 Ok(JoinEdge {
143 left: 1u64 << left_idx,
144 right: 1u64 << right_idx,
145 selectivity,
146 })
147 }
148
149 pub fn relation_count(&self) -> usize {
150 self.relations.len()
151 }
152
153 pub fn edges_between(&self, s1: u64, s2: u64) -> Vec<&JoinEdge> {
157 self.edges
158 .iter()
159 .filter(|e| {
160 let l_in_1 = e.left & s1 != 0;
161 let r_in_2 = e.right & s2 != 0;
162 let l_in_2 = e.left & s2 != 0;
163 let r_in_1 = e.right & s1 != 0;
164 (l_in_1 && r_in_2) || (l_in_2 && r_in_1)
165 })
166 .collect()
167 }
168
169 pub fn full_set(&self) -> u64 {
170 match self.relations.len() {
171 0 => 0,
172 64 => u64::MAX,
173 count => (1u64 << count) - 1,
174 }
175 }
176
177 pub fn neighbors(&self, node: usize) -> Vec<usize> {
180 if node >= self.relations.len() {
181 return Vec::new();
182 }
183 let mark = 1u64 << node;
184 let mut out: Vec<usize> = Vec::new();
185 let mut seen: u64 = 0;
186 for edge in &self.edges {
187 let other = if edge.left == mark {
188 edge.right
189 } else if edge.right == mark {
190 edge.left
191 } else {
192 continue;
193 };
194 if other == 0 {
195 continue;
196 }
197 let Ok(idx) = usize::try_from(other.trailing_zeros()) else {
199 continue;
200 };
201 if seen & (1u64 << idx) != 0 {
202 continue;
203 }
204 seen |= 1u64 << idx;
205 out.push(idx);
206 }
207 out.sort_unstable();
208 out
209 }
210}
211
212#[cfg(test)]
213mod tests {
214 use super::*;
215
216 #[test]
217 fn full_set_covers_every_relation() {
218 let mut g = JoinGraph::new();
219 for i in 0..3 {
220 g.add_relation(format!("t{i}"), 100.0).unwrap();
221 }
222 assert_eq!(g.full_set(), 0b111);
223 }
224
225 #[test]
226 fn edges_between_finds_predicates_across_partition() {
227 let mut g = JoinGraph::new();
228 let a = g.add_relation("a", 100.0).unwrap();
229 let b = g.add_relation("b", 100.0).unwrap();
230 let c = g.add_relation("c", 100.0).unwrap();
231 g.add_edge(a, b, 0.01).unwrap();
232 g.add_edge(b, c, 0.01).unwrap();
233 let s1 = 1u64 << a;
234 let s2 = (1u64 << b) | (1u64 << c);
235 let between = g.edges_between(s1, s2);
236 assert_eq!(between.len(), 1);
237 }
238
239 #[test]
240 fn capacity_and_edge_errors_are_returned_without_panicking() {
241 let mut graph = JoinGraph::new();
242 for index in 0..64 {
243 graph.add_relation(format!("t{index}"), 1.0).unwrap();
244 }
245 assert_eq!(graph.full_set(), u64::MAX);
246 assert!(matches!(
247 graph.add_relation("overflow", 1.0),
248 Err(JoinGraphError::TooManyRelations { index: 64, .. })
249 ));
250 assert!(matches!(
251 graph.add_edge(0, 64, 1.0),
252 Err(JoinGraphError::UnknownRelation { index: 64, .. })
253 ));
254 assert_eq!(graph.neighbors(64).len(), 0);
255 }
256
257 #[test]
258 fn rejects_non_finite_cost_inputs_before_enumeration() {
259 let mut graph = JoinGraph::new();
260 assert!(matches!(
261 graph.add_relation("bad", f64::NAN),
262 Err(JoinGraphError::InvalidCardinality { .. })
263 ));
264 assert!(matches!(
265 graph.add_relation_with_cost("bad_cost", 1.0, f64::INFINITY),
266 Err(JoinGraphError::InvalidAccessCost { .. })
267 ));
268 let left = graph.add_relation("left", 1.0).unwrap();
269 let right = graph.add_relation("right", 1.0).unwrap();
270 for selectivity in [f64::NAN, -0.1, 1.1] {
271 assert!(matches!(
272 graph.add_edge(left, right, selectivity),
273 Err(JoinGraphError::InvalidSelectivity { .. })
274 ));
275 }
276 }
277}