1use std::collections::BTreeMap;
23use uqa_core::{
24 memory::{Produced, ProductionControl},
25 ValueRetentionError,
26};
27
28use crate::cardinality::{AccessParadigm, ColumnStatistics};
29use crate::cost_model::{CostEstimator, OperatorKind};
30use crate::join_enumerator::JoinPlan;
31use crate::join_graph::{JoinGraph, JoinGraphError, JoinGraphResult};
32
33mod selection;
34
35#[derive(Debug, thiserror::Error)]
37pub enum JoinOrderError {
38 #[error(transparent)]
39 Graph(#[from] JoinGraphError),
40 #[error(transparent)]
41 Production(#[from] ValueRetentionError),
42}
43
44#[derive(Debug, Clone)]
46pub struct JoinRelation {
47 pub alias: String,
48 pub cardinality: f64,
49 pub column_stats: ColumnStatistics,
50 pub access_cost: f64,
52 pub paradigm: AccessParadigm,
54 pub source_id: u64,
57}
58
59#[derive(Clone, Copy)]
61pub(crate) struct JoinRelationRef<'a> {
62 pub alias: &'a str,
63 pub cardinality: f64,
64 pub column_stats: &'a ColumnStatistics,
65 pub access_cost: f64,
66}
67
68impl JoinRelation {
69 fn as_join_relation(&self) -> JoinRelationRef<'_> {
70 JoinRelationRef {
71 alias: &self.alias,
72 cardinality: self.cardinality,
73 column_stats: &self.column_stats,
74 access_cost: self.access_cost,
75 }
76 }
77}
78
79#[derive(Debug, Clone)]
81pub struct JoinPredicate {
82 pub left_alias: String,
83 pub right_alias: String,
84 pub left_field: String,
85 pub right_field: String,
86}
87
88#[derive(Debug, Clone, Copy)]
89pub(crate) struct JoinPredicateRef<'a> {
90 pub left_alias: &'a str,
91 pub right_alias: &'a str,
92 pub left_field: &'a str,
93 pub right_field: &'a str,
94}
95
96impl JoinPredicate {
97 fn as_join_predicate(&self) -> JoinPredicateRef<'_> {
98 JoinPredicateRef {
99 left_alias: &self.left_alias,
100 right_alias: &self.right_alias,
101 left_field: &self.left_field,
102 right_field: &self.right_field,
103 }
104 }
105}
106
107#[derive(Debug, Clone, Copy, PartialEq, Eq)]
109pub enum JoinAlgorithm {
110 Hash,
111}
112
113#[derive(Debug, Clone)]
115pub struct JoinCondition {
116 pub left_field: String,
117 pub right_field: String,
118}
119
120#[derive(Debug, Clone)]
123pub enum JoinOrderTree {
124 Scan(JoinRelation),
126 Inner {
128 algorithm: JoinAlgorithm,
129 condition: JoinCondition,
130 left: Box<JoinOrderTree>,
131 right: Box<JoinOrderTree>,
132 },
133 Cross {
135 left: Box<JoinOrderTree>,
136 right: Box<JoinOrderTree>,
137 },
138}
139
140#[derive(Debug, Clone)]
144pub struct JoinOrderResult {
145 pub tree: JoinOrderTree,
146 pub primary_alias: Option<String>,
147}
148
149#[derive(Debug, Clone, Default)]
151pub struct JoinOrderOptimizer {
152 pub cost_estimator: CostEstimator,
153}
154
155impl JoinOrderOptimizer {
156 pub fn new() -> Self {
157 Self::default()
158 }
159
160 pub fn with_cost_estimator(mut self, est: CostEstimator) -> Self {
161 self.cost_estimator = est;
162 self
163 }
164
165 pub fn optimize(
167 &self,
168 relations: Vec<JoinRelation>,
169 predicates: Vec<JoinPredicate>,
170 ) -> JoinGraphResult<JoinOrderResult> {
171 let selection::Selection { plan, aliases } = match self.select(
172 relations.iter().map(JoinRelation::as_join_relation),
173 predicates.iter().map(JoinPredicate::as_join_predicate),
174 &ProductionControl::uncontrolled(),
175 ) {
176 Ok(selection) => selection,
177 Err(JoinOrderError::Graph(error)) => return Err(error),
178 Err(JoinOrderError::Production(error)) => {
179 panic!("uncontrolled join-order allocation failed: {error}");
180 }
181 };
182 let primary_alias = relations.first().map(|relation| relation.alias.clone());
183 let mut predicate_lookup = BTreeMap::new();
184 if relations.len() > 1 {
185 for predicate in predicates {
186 let left = aliases.index(&predicate.left_alias)?;
187 let right = aliases.index(&predicate.right_alias)?;
188 predicate_lookup.insert((left.min(right), left.max(right)), predicate);
190 }
191 }
192 let mut sources: [Option<JoinRelation>; 64] = std::array::from_fn(|_| None);
193 for (index, relation) in relations.into_iter().enumerate() {
194 sources[index] = Some(relation);
195 }
196 let tree = Self::materialize_plan(&plan, &mut sources, &mut predicate_lookup)?;
197 Ok(JoinOrderResult {
198 tree,
199 primary_alias,
200 })
201 }
202
203 pub fn select_with_control(
207 &self,
208 relations: &[JoinRelation],
209 predicates: &[JoinPredicate],
210 control: &ProductionControl<'_>,
211 ) -> Result<Produced<JoinPlan>, JoinOrderError> {
212 self.select_relations_with_control(
213 relations.iter().map(JoinRelation::as_join_relation),
214 predicates.iter().map(JoinPredicate::as_join_predicate),
215 control,
216 )
217 }
218
219 pub(crate) fn select_relations_with_control<'a, 'p>(
220 &self,
221 relations: impl ExactSizeIterator<Item = JoinRelationRef<'a>> + Clone,
222 predicates: impl Iterator<Item = JoinPredicateRef<'p>>,
223 control: &ProductionControl<'_>,
224 ) -> Result<Produced<JoinPlan>, JoinOrderError> {
225 self.select(relations, predicates, control)
226 .map(|selection| selection.plan)
227 }
228
229 fn estimate_predicate_selectivity<'a>(
230 relations: impl ExactSizeIterator<Item = JoinRelationRef<'a>> + Clone,
231 left_idx: usize,
232 right_idx: usize,
233 left_field: &str,
234 right_field: &str,
235 ) -> f64 {
236 let l_distinct = relations
237 .clone()
238 .nth(left_idx)
239 .and_then(|r| r.column_stats.get(left_field))
240 .map(|s| s.distinct_count.max(1));
241 let r_distinct = relations
242 .clone()
243 .nth(right_idx)
244 .and_then(|r| r.column_stats.get(right_field))
245 .map(|s| s.distinct_count.max(1));
246 match (l_distinct, r_distinct) {
247 (Some(left), Some(right)) => 1.0 / left.max(right) as f64,
248 (Some(distinct), None) | (None, Some(distinct)) => 1.0 / distinct as f64,
249 (None, None) => crate::CardinalityEstimator::new().default_selectivity,
250 }
251 }
252
253 fn materialize_plan(
254 plan: &JoinPlan,
255 relations: &mut [Option<JoinRelation>],
256 predicates: &mut BTreeMap<(usize, usize), JoinPredicate>,
257 ) -> JoinGraphResult<JoinOrderTree> {
258 match (&plan.left, &plan.right) {
259 (None, None) => {
260 let idx = usize::try_from(plan.relations.trailing_zeros()).map_err(|_| {
263 crate::join_graph::JoinGraphError::InvalidPlan {
264 detail: "join leaf index exceeds usize".into(),
265 }
266 })?;
267 relations
268 .get_mut(idx)
269 .and_then(Option::take)
270 .map(JoinOrderTree::Scan)
271 .ok_or_else(|| crate::join_graph::JoinGraphError::InvalidPlan {
272 detail: format!("leaf references relation index {idx}"),
273 })
274 }
275 (Some(left), Some(right)) => {
276 let l_tree = Self::materialize_plan(left, relations, predicates)?;
277 let r_tree = Self::materialize_plan(right, relations, predicates)?;
278 let l_set = left.relations;
279 let Some(edge) = plan.join_edge else {
280 return Ok(JoinOrderTree::Cross {
281 left: Box::new(l_tree),
282 right: Box::new(r_tree),
283 });
284 };
285
286 let edge_left_bit = usize::try_from(edge.left.trailing_zeros()).map_err(|_| {
287 crate::join_graph::JoinGraphError::InvalidPlan {
288 detail: "left join edge index exceeds usize".into(),
289 }
290 })?;
291 let edge_right_bit =
292 usize::try_from(edge.right.trailing_zeros()).map_err(|_| {
293 crate::join_graph::JoinGraphError::InvalidPlan {
294 detail: "right join edge index exceeds usize".into(),
295 }
296 })?;
297 let left_in_l = (l_set & (1u64 << edge_left_bit)) != 0;
298 let right_in_l = (l_set & (1u64 << edge_right_bit)) != 0;
299 let key = (
300 edge_left_bit.min(edge_right_bit),
301 edge_left_bit.max(edge_right_bit),
302 );
303 let Some(pred) = predicates.remove(&key) else {
304 return Err(crate::join_graph::JoinGraphError::InvalidPlan {
305 detail: format!(
306 "join edge between relation indices {edge_left_bit} and {edge_right_bit} has no predicate"
307 ),
308 });
309 };
310
311 let condition = if !left_in_l && right_in_l {
315 JoinCondition {
316 left_field: pred.right_field,
317 right_field: pred.left_field,
318 }
319 } else {
320 JoinCondition {
321 left_field: pred.left_field,
322 right_field: pred.right_field,
323 }
324 };
325
326 let algorithm = match plan.kind {
327 Some(OperatorKind::HashJoinInner) => JoinAlgorithm::Hash,
328 Some(kind) => {
329 return Err(crate::join_graph::JoinGraphError::InvalidPlan {
330 detail: format!(
331 "DPccp selected non-executable equijoin strategy {kind:?}"
332 ),
333 });
334 }
335 None => {
336 return Err(crate::join_graph::JoinGraphError::InvalidPlan {
337 detail: "DPccp equijoin node has no physical strategy".into(),
338 });
339 }
340 };
341
342 Ok(JoinOrderTree::Inner {
343 algorithm,
344 condition,
345 left: Box::new(l_tree),
346 right: Box::new(r_tree),
347 })
348 }
349 (Some(_), None) | (None, Some(_)) => {
350 Err(crate::join_graph::JoinGraphError::InvalidPlan {
351 detail: "join node contains exactly one child".into(),
352 })
353 }
354 }
355 }
356}
357
358#[cfg(test)]
359mod tests {
360 use super::*;
361 use crate::ColumnStats;
362 use uqa_core::Value;
363
364 mod memory;
365
366 fn rel(alias: &str, card: f64, src: u64) -> JoinRelation {
367 JoinRelation {
368 alias: alias.into(),
369 cardinality: card,
370 column_stats: ColumnStatistics::default(),
371 access_cost: card,
372 paradigm: AccessParadigm::Relational,
373 source_id: src,
374 }
375 }
376
377 fn rel_with_stats(alias: &str, card: f64, src: u64, field: &str, ndv: u64) -> JoinRelation {
378 let mut cs = BTreeMap::new();
379 cs.insert(
380 field.to_string(),
381 ColumnStats {
382 distinct_count: ndv,
383 row_count: card as u64,
384 ..Default::default()
385 },
386 );
387 JoinRelation {
388 alias: alias.into(),
389 cardinality: card,
390 column_stats: cs.into(),
391 access_cost: card,
392 paradigm: AccessParadigm::Relational,
393 source_id: src,
394 }
395 }
396
397 fn assert_hash_join_tree(tree: &JoinOrderTree) {
398 match tree {
399 JoinOrderTree::Inner {
400 algorithm,
401 left,
402 right,
403 ..
404 } => {
405 assert_eq!(*algorithm, JoinAlgorithm::Hash);
406 assert_hash_join_tree(left);
407 assert_hash_join_tree(right);
408 }
409 JoinOrderTree::Cross { left, right } => {
410 assert_hash_join_tree(left);
411 assert_hash_join_tree(right);
412 }
413 JoinOrderTree::Scan(_) => {}
414 }
415 }
416
417 #[test]
418 fn single_relation_returns_scan() {
419 let opt = JoinOrderOptimizer::new();
420 let result = opt.optimize(vec![rel("a", 100.0, 1)], vec![]).unwrap();
421 assert!(matches!(result.tree, JoinOrderTree::Scan(_)));
422 assert_eq!(result.primary_alias.as_deref(), Some("a"));
423 }
424
425 #[test]
426 fn three_chain_uses_executable_hash_strategies() {
427 let opt = JoinOrderOptimizer::new();
428 let result = opt
429 .optimize(
430 vec![
431 rel_with_stats("small", 10.0, 1, "id", 10),
432 rel_with_stats("mid", 10_000.0, 2, "small_id", 10_000),
433 rel_with_stats("big", 1_000_000.0, 3, "mid_id", 1_000_000),
434 ],
435 vec![
436 JoinPredicate {
437 left_alias: "small".into(),
438 right_alias: "mid".into(),
439 left_field: "id".into(),
440 right_field: "small_id".into(),
441 },
442 JoinPredicate {
443 left_alias: "mid".into(),
444 right_alias: "big".into(),
445 left_field: "id".into(),
446 right_field: "mid_id".into(),
447 },
448 ],
449 )
450 .unwrap();
451 assert_hash_join_tree(&result.tree);
452 assert_eq!(result.primary_alias.as_deref(), Some("small"));
453 }
454
455 #[test]
456 fn cross_join_when_no_predicate() {
457 let opt = JoinOrderOptimizer::new();
458 let result = opt
459 .optimize(vec![rel("a", 50.0, 1), rel("b", 50.0, 2)], vec![])
460 .unwrap();
461 match result.tree {
462 JoinOrderTree::Inner { .. } => panic!("expected cross join, got inner"),
463 JoinOrderTree::Scan(_) => panic!("expected cross join, got scan"),
464 JoinOrderTree::Cross { .. } => {}
465 }
466 }
467
468 #[test]
469 fn predicate_selectivity_uses_max_distinct() {
470 let relations = [
471 rel_with_stats("a", 1000.0, 1, "x", 100),
472 rel_with_stats("b", 1000.0, 2, "y", 50),
473 ];
474 let s = JoinOrderOptimizer::estimate_predicate_selectivity(
475 relations.iter().map(JoinRelation::as_join_relation),
476 0,
477 1,
478 "x",
479 "y",
480 );
481 assert!((s - 0.01).abs() < 1e-9);
482 let _ = Value::Int(0);
483 }
484
485 #[test]
486 fn predicate_selectivity_uses_the_configured_fallback_without_statistics() {
487 let relations = [rel("a", 1000.0, 1), rel("b", 1000.0, 2)];
488 let selectivity = JoinOrderOptimizer::estimate_predicate_selectivity(
489 relations.iter().map(JoinRelation::as_join_relation),
490 0,
491 1,
492 "x",
493 "y",
494 );
495 assert_eq!(
496 selectivity,
497 crate::CardinalityEstimator::new().default_selectivity
498 );
499 }
500
501 #[test]
502 fn invalid_join_inputs_are_reported_instead_of_silently_rewritten() {
503 let optimizer = JoinOrderOptimizer::new();
504 assert!(matches!(
505 optimizer.optimize(Vec::new(), Vec::new()),
506 Err(crate::join_graph::JoinGraphError::EmptyGraph)
507 ));
508 assert!(matches!(
509 optimizer.optimize(vec![rel("a", 1.0, 1), rel("a", 2.0, 2)], Vec::new()),
510 Err(crate::join_graph::JoinGraphError::DuplicateAlias { .. })
511 ));
512 assert!(matches!(
513 optimizer.optimize(
514 vec![rel("a", 1.0, 1), rel("b", 2.0, 2)],
515 vec![JoinPredicate {
516 left_alias: "a".into(),
517 right_alias: "missing".into(),
518 left_field: "id".into(),
519 right_field: "id".into(),
520 }],
521 ),
522 Err(crate::join_graph::JoinGraphError::UnknownAlias { .. })
523 ));
524 assert!(matches!(
525 optimizer.optimize(vec![rel("bad", f64::NAN, 1)], Vec::new()),
526 Err(crate::join_graph::JoinGraphError::InvalidCardinality { .. })
527 ));
528 }
529}