Skip to main content

uqa_planner/
join_graph.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Join graph: nodes are individual relations (a single table or a
8//! materialised CTE / subquery output), edges are equijoin predicates.
9//! The DPccp enumerator walks this graph to pick a join order.
10//!
11//! The graph is dense by design (`u64` bitmask side sets) so DP cache
12//! lookups can use bitmasks directly. With 64 relations max this
13//! suffices for every shape the UQA SQL compiler can build.
14
15use 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    /// Bitmask of relations on the left side of the equijoin.
48    pub left: u64,
49    /// Bitmask of relations on the right side of the equijoin.
50    pub right: u64,
51    /// Selectivity of the join predicate (1 / max(distinct_left,
52    /// distinct_right) for an equijoin).
53    pub selectivity: f64,
54}
55
56#[derive(Debug, Clone, Default)]
57pub struct JoinGraph {
58    /// Relation labels in declaration order. The bit index of a
59    /// relation is its position in this vector.
60    pub(crate) relations: Vec<String>,
61    /// Per-relation row count estimate.
62    pub(crate) cardinalities: Vec<f64>,
63    /// Cost of producing each base relation after its local access predicates.
64    pub(crate) access_costs: Vec<f64>,
65    /// Connecting edges in predicate order. Costing preserves that order
66    /// when multiplying selectivities and selecting the first crossing edge.
67    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    /// All edges connecting a left subset to a right subset of the
154    /// graph. An edge is "between" `(s1, s2)` when one endpoint is in
155    /// `s1` and the other is in `s2`.
156    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    /// Indices of every relation directly connected to `node` by any edge.
178    /// Each call walks the edge list once: `O(|edges|)`.
179    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            // `other` is a singleton bitmask of the other side.
198            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}