radixdb_executor/
join_graph.rs

1// Copyright 2026 RadixDB Contributors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Bound logical relation graph for a SELECT table expression.
16//!
17//! The parser intentionally preserves SQL text as a binary `JoinSource` tree.
18//! Physical planning must not confuse that syntax tree with an execution
19//! order. This graph assigns stable relation identities, records the complete
20//! relation set on both sides of every edge, and makes outer/derived barriers
21//! explicit before any source is opened.
22
23use std::sync::Arc;
24
25use radixdb_sql::ast::Expression;
26
27#[derive(Debug, Clone, Copy, PartialEq, Eq)]
28pub enum LogicalRelationKind {
29    Table,
30    Derived,
31    Cte,
32    Values,
33    Function,
34    Opaque,
35}
36
37#[derive(Debug, Clone, PartialEq, Eq)]
38pub struct LogicalRelation {
39    pub ordinal: usize,
40    pub visible_name: Option<String>,
41    pub kind: LogicalRelationKind,
42}
43
44#[derive(Debug, Clone, Copy, PartialEq, Eq)]
45pub enum JoinReorderBarrier {
46    ReorderableInner,
47    Cross,
48    Left,
49    Right,
50    Full,
51    NaturalOrUsing,
52    Other,
53}
54
55impl JoinReorderBarrier {
56    pub const fn permits_inner_reorder(self) -> bool {
57        matches!(self, Self::ReorderableInner)
58    }
59}
60
61#[derive(Debug, Clone, PartialEq, Eq)]
62pub struct LogicalJoinEdge {
63    pub ordinal: usize,
64    pub left_relations: Arc<[usize]>,
65    pub right_relations: Arc<[usize]>,
66    pub barrier: JoinReorderBarrier,
67}
68
69#[derive(Debug, Clone, PartialEq, Eq)]
70pub struct LogicalJoinGraph {
71    pub relations: Arc<[LogicalRelation]>,
72    pub edges: Arc<[LogicalJoinEdge]>,
73}
74
75impl LogicalJoinGraph {
76    pub fn bind(table_expression: &Expression) -> Option<Self> {
77        if !matches!(table_expression, Expression::JoinSource(_)) {
78            return None;
79        }
80        let mut builder = LogicalJoinGraphBuilder::default();
81        builder.bind_subtree(table_expression);
82        Some(Self {
83            relations: Arc::from(builder.relations),
84            edges: Arc::from(builder.edges),
85        })
86    }
87
88    pub fn reorderable_edge_count(&self) -> usize {
89        self.edges
90            .iter()
91            .filter(|edge| edge.barrier.permits_inner_reorder())
92            .count()
93    }
94}
95
96#[derive(Default)]
97struct LogicalJoinGraphBuilder {
98    relations: Vec<LogicalRelation>,
99    edges: Vec<LogicalJoinEdge>,
100}
101
102impl LogicalJoinGraphBuilder {
103    fn bind_subtree(&mut self, expression: &Expression) -> Vec<usize> {
104        if let Expression::JoinSource(join) = expression {
105            let left_relations = self.bind_subtree(&join.left);
106            let right_relations = self.bind_subtree(&join.right);
107            self.edges.push(LogicalJoinEdge {
108                ordinal: self.edges.len(),
109                left_relations: Arc::from(left_relations.clone()),
110                right_relations: Arc::from(right_relations.clone()),
111                barrier: classify_barrier(join),
112            });
113            let mut relations = left_relations;
114            relations.extend(right_relations);
115            relations
116        } else {
117            let ordinal = self.relations.len();
118            let (visible_name, kind) = classify_relation(expression);
119            self.relations.push(LogicalRelation {
120                ordinal,
121                visible_name,
122                kind,
123            });
124            vec![ordinal]
125        }
126    }
127}
128
129fn classify_barrier(join: &radixdb_sql::ast::JoinTableSource) -> JoinReorderBarrier {
130    if !join.using_columns.is_empty() || join.join_type.to_uppercase().contains("NATURAL") {
131        return JoinReorderBarrier::NaturalOrUsing;
132    }
133    match join.join_type.trim().to_uppercase().as_str() {
134        "INNER" if join.condition.is_some() => JoinReorderBarrier::ReorderableInner,
135        "CROSS" => JoinReorderBarrier::Cross,
136        "LEFT" | "LEFT OUTER" => JoinReorderBarrier::Left,
137        "RIGHT" | "RIGHT OUTER" => JoinReorderBarrier::Right,
138        "FULL" | "FULL OUTER" => JoinReorderBarrier::Full,
139        _ => JoinReorderBarrier::Other,
140    }
141}
142
143fn classify_relation(expression: &Expression) -> (Option<String>, LogicalRelationKind) {
144    match expression {
145        Expression::TableSource(source) => (
146            Some(
147                source
148                    .alias
149                    .as_ref()
150                    .unwrap_or(&source.name)
151                    .value_lower()
152                    .to_string(),
153            ),
154            LogicalRelationKind::Table,
155        ),
156        Expression::SubquerySource(source) => (
157            source
158                .alias
159                .as_ref()
160                .map(|alias| alias.value_lower().to_string()),
161            LogicalRelationKind::Derived,
162        ),
163        Expression::CteReference(source) => (
164            Some(
165                source
166                    .alias
167                    .as_ref()
168                    .unwrap_or(&source.name)
169                    .value_lower()
170                    .to_string(),
171            ),
172            LogicalRelationKind::Cte,
173        ),
174        Expression::ValuesSource(source) => (
175            source
176                .alias
177                .as_ref()
178                .map(|alias| alias.value_lower().to_string()),
179            LogicalRelationKind::Values,
180        ),
181        Expression::FunctionTableSource(source) => (
182            Some(
183                source
184                    .alias
185                    .as_ref()
186                    .unwrap_or(&source.function)
187                    .value_lower()
188                    .to_string(),
189            ),
190            LogicalRelationKind::Function,
191        ),
192        Expression::Aliased(source) => (
193            Some(source.alias.value_lower().to_string()),
194            LogicalRelationKind::Derived,
195        ),
196        _ => (None, LogicalRelationKind::Opaque),
197    }
198}
199
200#[cfg(test)]
201mod tests {
202    use super::*;
203    use radixdb_sql::Statement;
204
205    fn graph(sql: &str) -> LogicalJoinGraph {
206        let mut statements = radixdb_sql::parse_sql(sql).unwrap();
207        let Statement::Select(statement) = statements.remove(0) else {
208            panic!("expected SELECT")
209        };
210        LogicalJoinGraph::bind(statement.table_expr.as_deref().unwrap()).unwrap()
211    }
212
213    #[test]
214    fn relation_sets_and_outer_barriers_are_explicit() {
215        let graph = graph(
216            "SELECT a.id FROM a \
217             INNER JOIN b ON b.a_id = a.id \
218             LEFT JOIN (SELECT id FROM c) c1 ON c1.id = b.c_id \
219             INNER JOIN d ON d.id = a.d_id",
220        );
221
222        assert_eq!(graph.relations.len(), 4);
223        assert_eq!(graph.relations[0].visible_name.as_deref(), Some("a"));
224        assert_eq!(graph.relations[2].visible_name.as_deref(), Some("c1"));
225        assert_eq!(graph.relations[2].kind, LogicalRelationKind::Derived);
226        assert_eq!(graph.edges.len(), 3);
227        assert_eq!(graph.edges[0].left_relations.as_ref(), &[0]);
228        assert_eq!(graph.edges[0].right_relations.as_ref(), &[1]);
229        assert_eq!(graph.edges[0].barrier, JoinReorderBarrier::ReorderableInner);
230        assert_eq!(graph.edges[1].left_relations.as_ref(), &[0, 1]);
231        assert_eq!(graph.edges[1].right_relations.as_ref(), &[2]);
232        assert_eq!(graph.edges[1].barrier, JoinReorderBarrier::Left);
233        assert_eq!(graph.edges[2].left_relations.as_ref(), &[0, 1, 2]);
234        assert_eq!(graph.edges[2].right_relations.as_ref(), &[3]);
235        assert_eq!(graph.reorderable_edge_count(), 2);
236    }
237
238    #[test]
239    fn using_and_cross_edges_are_not_silently_reorderable() {
240        let graph = graph("SELECT * FROM a JOIN b USING (id) CROSS JOIN c");
241        assert_eq!(graph.edges[0].barrier, JoinReorderBarrier::NaturalOrUsing);
242        assert_eq!(graph.edges[1].barrier, JoinReorderBarrier::Cross);
243        assert_eq!(graph.reorderable_edge_count(), 0);
244    }
245}
radixdb_executor/join_graph.rs

radixdb_executor/
join_graph.rs
