Skip to main content

uqa_planner/
join_order.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Join-order optimization.
8//!
9//! Bridges DPccp join enumeration ([`crate::join_enumerator`]) and the
10//! row-oriented join algorithms in `uqa-joins`. The optimizer accepts
11//! a list of [`JoinRelation`] descriptors plus equijoin
12//! [`JoinPredicate`] descriptors, builds an internal [`JoinGraph`],
13//! runs DPccp, and materializes the chosen plan into a
14//! [`JoinOrderTree`] -- a tree of join descriptors the engine
15//! interprets to drive the actual row-tuple join algorithms.
16//!
17//! `JoinOrderTree` retains the executable physical strategy selected by the
18//! enumerator. Today relational equijoins are hash joins; the planner does not
19//! pretend that a pre-existing index join is available when the engine cannot
20//! execute one.
21
22use 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/// Invalid join inputs or failed admission while selecting their order.
36#[derive(Debug, thiserror::Error)]
37pub enum JoinOrderError {
38    #[error(transparent)]
39    Graph(#[from] JoinGraphError),
40    #[error(transparent)]
41    Production(#[from] ValueRetentionError),
42}
43
44/// Description of a base relation feeding a join-order search.
45#[derive(Debug, Clone)]
46pub struct JoinRelation {
47    pub alias: String,
48    pub cardinality: f64,
49    pub column_stats: ColumnStatistics,
50    /// Cost of producing this relation after local access predicates.
51    pub access_cost: f64,
52    /// Physical domain used by the relation-local access path.
53    pub paradigm: AccessParadigm,
54    /// Relation reference the engine resolves back to its backing
55    /// data (e.g. a table id or scan handle).
56    pub source_id: u64,
57}
58
59/// Selection observes existing relation metadata without requiring an owned alias or column map.
60#[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/// Equijoin predicate between two named relations.
80#[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/// Algorithm hint for an inner join.
108#[derive(Debug, Clone, Copy, PartialEq, Eq)]
109pub enum JoinAlgorithm {
110    Hash,
111}
112
113/// Equijoin condition.
114#[derive(Debug, Clone)]
115pub struct JoinCondition {
116    pub left_field: String,
117    pub right_field: String,
118}
119
120/// Output of the join order optimizer. The engine walks this tree to
121/// drive the actual row-tuple join algorithms.
122#[derive(Debug, Clone)]
123pub enum JoinOrderTree {
124    /// Base relation -- a single scan source.
125    Scan(JoinRelation),
126    /// Inner equijoin with the chosen algorithm.
127    Inner {
128        algorithm: JoinAlgorithm,
129        condition: JoinCondition,
130        left: Box<JoinOrderTree>,
131        right: Box<JoinOrderTree>,
132    },
133    /// Cross join -- no predicate connecting the two sides.
134    Cross {
135        left: Box<JoinOrderTree>,
136        right: Box<JoinOrderTree>,
137    },
138}
139
140/// Result of optimization: the chosen join tree plus the alias of the
141/// first non-empty relation (used as the engine's primary table
142/// context).
143#[derive(Debug, Clone)]
144pub struct JoinOrderResult {
145    pub tree: JoinOrderTree,
146    pub primary_alias: Option<String>,
147}
148
149/// Determines an optimal join ordering using DPccp.
150#[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    /// Find the optimal join order and build the operator tree.
166    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                // Preserve the existing last predicate for each relation pair.
189                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    /// Select an admitted join tree from borrowed metadata. Graph and search
204    /// scratch release before return; the output retains only its boxed nodes.
205    /// Relation statistics remain with their input owner and are never copied.
206    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                // Leaf: `relations` is a singleton bitmask of the
261                // source relation index.
262                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                // Orient condition fields: if the plan put the edge's
312                // RIGHT relation on the LEFT side, swap the fields so
313                // left_field corresponds to the actual left side.
314                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}