hawdb_optimizer_relational/
relational_planning.rs

1// Copyright 2026 Nowledge
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
15use crate::{
16    PlanCostBreakdown, RelationalJoinEnumerationConfig, RelationalJoinEnumerationError,
17    RelationalJoinRewriteError,
18};
19
20#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
21pub enum RelationalJoinPlanningDirective {
22    #[default]
23    Auto,
24    SyntaxOrder,
25}
26
27#[derive(Debug, Clone, Copy, PartialEq, Eq)]
28pub enum RelationalJoinPlanningStrategy {
29    SyntaxOrder,
30    InnerJoinMemo,
31    InnerLeftJoinRewriteMemo,
32    CsgCmpMemo,
33}
34
35impl RelationalJoinPlanningStrategy {
36    pub const fn as_str(self) -> &'static str {
37        match self {
38            Self::SyntaxOrder => "syntax_order",
39            Self::InnerJoinMemo => "inner_join_memo",
40            Self::InnerLeftJoinRewriteMemo => "inner_left_join_rewrite_memo",
41            Self::CsgCmpMemo => "csg_cmp_memo",
42        }
43    }
44}
45
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47pub enum RelationalJoinPlanningStatus {
48    NotEligible,
49    Selected,
50    Fallback,
51}
52
53impl RelationalJoinPlanningStatus {
54    pub const fn as_str(self) -> &'static str {
55        match self {
56            Self::NotEligible => "not_eligible",
57            Self::Selected => "selected",
58            Self::Fallback => "fallback",
59        }
60    }
61}
62
63#[derive(Debug, Clone, Copy, PartialEq, Eq)]
64pub enum RelationalJoinPlanningReason {
65    NoJoin,
66    UnsupportedJoinKind,
67    LockingSelect,
68    ExplicitSyntaxOrder,
69    UnresolvedColumns,
70    UnsupportedJoinPredicate,
71    UnavailableAccessBinding,
72    UnsupportedPostJoinFilter,
73    SpecializedJoinNotEnumerated,
74    GroupBudgetExceeded,
75    ExpressionBudgetExceeded,
76    DisconnectedGraph,
77    RequiredPropertiesUnsatisfied,
78    NoLegalPlan,
79    SyntaxFallback,
80    SyntaxOrderOptimal,
81    CostReordered,
82}
83
84impl RelationalJoinPlanningReason {
85    pub const fn as_str(self) -> &'static str {
86        match self {
87            Self::NoJoin => "no_join",
88            Self::UnsupportedJoinKind => "unsupported_join_kind",
89            Self::LockingSelect => "locking_select",
90            Self::ExplicitSyntaxOrder => "explicit_syntax_order",
91            Self::UnresolvedColumns => "unresolved_columns",
92            Self::UnsupportedJoinPredicate => "unsupported_join_predicate",
93            Self::UnavailableAccessBinding => "unavailable_access_binding",
94            Self::UnsupportedPostJoinFilter => "unsupported_post_join_filter",
95            Self::SpecializedJoinNotEnumerated => "specialized_join_not_enumerated",
96            Self::GroupBudgetExceeded => "group_budget_exceeded",
97            Self::ExpressionBudgetExceeded => "expression_budget_exceeded",
98            Self::DisconnectedGraph => "disconnected_graph",
99            Self::RequiredPropertiesUnsatisfied => "required_properties_unsatisfied",
100            Self::NoLegalPlan => "no_legal_plan",
101            Self::SyntaxFallback => "syntax_fallback",
102            Self::SyntaxOrderOptimal => "syntax_order_optimal",
103            Self::CostReordered => "cost_reordered",
104        }
105    }
106}
107
108#[derive(Debug, Clone, Copy, PartialEq, Eq)]
109pub enum RelationalJoinPlanningFallbackClass {
110    Budget,
111    Unsupported,
112}
113
114impl RelationalJoinPlanningFallbackClass {
115    pub const fn as_str(self) -> &'static str {
116        match self {
117            Self::Budget => "budget",
118            Self::Unsupported => "unsupported",
119        }
120    }
121}
122
123#[derive(Debug, Clone, Copy, PartialEq, Eq)]
124pub struct RelationalJoinPlanningBudget {
125    pub max_groups: usize,
126    pub max_expressions: usize,
127}
128
129impl From<RelationalJoinEnumerationConfig> for RelationalJoinPlanningBudget {
130    fn from(config: RelationalJoinEnumerationConfig) -> Self {
131        Self {
132            max_groups: config.max_groups,
133            max_expressions: config.max_expressions,
134        }
135    }
136}
137
138#[derive(Debug, Clone, Copy, PartialEq, Eq)]
139pub struct RelationalJoinPlanningCost {
140    pub estimated_rows: u64,
141    pub cost: u64,
142    pub cpu: u64,
143    pub random_io: u64,
144    pub sequential_io: u64,
145    pub output_rows: u64,
146}
147
148impl From<PlanCostBreakdown> for RelationalJoinPlanningCost {
149    fn from(cost: PlanCostBreakdown) -> Self {
150        Self {
151            estimated_rows: cost.estimated_rows,
152            cost: cost.cost,
153            cpu: cost.cpu,
154            random_io: cost.random_io,
155            sequential_io: cost.sequential_io,
156            output_rows: cost.output_rows,
157        }
158    }
159}
160
161#[derive(Debug, Clone, PartialEq, Eq)]
162pub struct RelationalJoinPlanningAttempt {
163    pub strategy: RelationalJoinPlanningStrategy,
164    pub status: RelationalJoinPlanningStatus,
165    pub reason: RelationalJoinPlanningReason,
166    pub fallback_class: Option<RelationalJoinPlanningFallbackClass>,
167    pub memo_groups: Option<usize>,
168    pub memo_expressions: Option<usize>,
169    pub cost: Option<RelationalJoinPlanningCost>,
170}
171
172impl RelationalJoinPlanningAttempt {
173    pub fn not_eligible(
174        strategy: RelationalJoinPlanningStrategy,
175        reason: RelationalJoinPlanningReason,
176    ) -> Self {
177        Self {
178            strategy,
179            status: RelationalJoinPlanningStatus::NotEligible,
180            reason,
181            fallback_class: None,
182            memo_groups: None,
183            memo_expressions: None,
184            cost: None,
185        }
186    }
187
188    pub fn selected(
189        strategy: RelationalJoinPlanningStrategy,
190        reordered: bool,
191        memo_groups: usize,
192        memo_expressions: usize,
193        cost: PlanCostBreakdown,
194    ) -> Self {
195        Self {
196            strategy,
197            status: RelationalJoinPlanningStatus::Selected,
198            reason: if reordered {
199                RelationalJoinPlanningReason::CostReordered
200            } else {
201                RelationalJoinPlanningReason::SyntaxOrderOptimal
202            },
203            fallback_class: None,
204            memo_groups: Some(memo_groups),
205            memo_expressions: Some(memo_expressions),
206            cost: Some(cost.into()),
207        }
208    }
209
210    pub fn syntax_fallback() -> Self {
211        Self {
212            strategy: RelationalJoinPlanningStrategy::SyntaxOrder,
213            status: RelationalJoinPlanningStatus::Selected,
214            reason: RelationalJoinPlanningReason::SyntaxFallback,
215            fallback_class: None,
216            memo_groups: None,
217            memo_expressions: None,
218            cost: None,
219        }
220    }
221
222    pub fn explicit_syntax_order() -> Self {
223        Self {
224            strategy: RelationalJoinPlanningStrategy::SyntaxOrder,
225            status: RelationalJoinPlanningStatus::Selected,
226            reason: RelationalJoinPlanningReason::ExplicitSyntaxOrder,
227            fallback_class: None,
228            memo_groups: None,
229            memo_expressions: None,
230            cost: None,
231        }
232    }
233
234    pub fn fallback_from_enumeration(
235        strategy: RelationalJoinPlanningStrategy,
236        error: &RelationalJoinEnumerationError,
237    ) -> Option<Self> {
238        let (reason, fallback_class, memo_groups, memo_expressions) = match error {
239            RelationalJoinEnumerationError::GroupBudgetExceeded {
240                required_groups, ..
241            } => (
242                RelationalJoinPlanningReason::GroupBudgetExceeded,
243                RelationalJoinPlanningFallbackClass::Budget,
244                Some(*required_groups),
245                None,
246            ),
247            RelationalJoinEnumerationError::ExpressionBudgetExceeded {
248                required_expressions,
249                ..
250            } => (
251                RelationalJoinPlanningReason::ExpressionBudgetExceeded,
252                RelationalJoinPlanningFallbackClass::Budget,
253                None,
254                Some(*required_expressions),
255            ),
256            RelationalJoinEnumerationError::Disconnected => (
257                RelationalJoinPlanningReason::DisconnectedGraph,
258                RelationalJoinPlanningFallbackClass::Unsupported,
259                None,
260                None,
261            ),
262            RelationalJoinEnumerationError::RequiredPropertiesUnsatisfied => (
263                RelationalJoinPlanningReason::RequiredPropertiesUnsatisfied,
264                RelationalJoinPlanningFallbackClass::Unsupported,
265                None,
266                None,
267            ),
268            RelationalJoinEnumerationError::EmptyGraph
269            | RelationalJoinEnumerationError::DuplicateBinding(_)
270            | RelationalJoinEnumerationError::DuplicatePredicate(_)
271            | RelationalJoinEnumerationError::PredicateHasFewerThanTwoBindings(_)
272            | RelationalJoinEnumerationError::UnknownPredicateBinding { .. }
273            | RelationalJoinEnumerationError::UnknownAccessBinding { .. }
274            | RelationalJoinEnumerationError::AccessWithoutPredicate { .. }
275            | RelationalJoinEnumerationError::SelfDependentAccess(_)
276            | RelationalJoinEnumerationError::MissingBaseAccess(_)
277            | RelationalJoinEnumerationError::InvalidAccessPath { .. } => return None,
278        };
279        Some(Self {
280            strategy,
281            status: RelationalJoinPlanningStatus::Fallback,
282            reason,
283            fallback_class: Some(fallback_class),
284            memo_groups,
285            memo_expressions,
286            cost: None,
287        })
288    }
289
290    pub fn fallback_from_rewrite(
291        strategy: RelationalJoinPlanningStrategy,
292        error: &RelationalJoinRewriteError,
293    ) -> Option<Self> {
294        match error {
295            RelationalJoinRewriteError::Enumeration(error) => {
296                Self::fallback_from_enumeration(strategy, error)
297            }
298            RelationalJoinRewriteError::NoLegalRewrite => Some(Self {
299                strategy,
300                status: RelationalJoinPlanningStatus::Fallback,
301                reason: RelationalJoinPlanningReason::NoLegalPlan,
302                fallback_class: Some(RelationalJoinPlanningFallbackClass::Unsupported),
303                memo_groups: None,
304                memo_expressions: None,
305                cost: None,
306            }),
307            RelationalJoinRewriteError::DuplicateTreeBinding(_)
308            | RelationalJoinRewriteError::DuplicateOperator(_)
309            | RelationalJoinRewriteError::PredicateOutsideOperatorSubtree { .. }
310            | RelationalJoinRewriteError::RelationSetMismatch
311            | RelationalJoinRewriteError::OperatorCountMismatch { .. } => None,
312        }
313    }
314}
315
316#[derive(Debug, Clone, PartialEq, Eq)]
317pub struct RelationalJoinPlanningOutcome {
318    pub strategy: RelationalJoinPlanningStrategy,
319    pub status: RelationalJoinPlanningStatus,
320    pub reason: RelationalJoinPlanningReason,
321    pub memo_groups: Option<usize>,
322    pub memo_expressions: Option<usize>,
323    pub budget: RelationalJoinPlanningBudget,
324    pub selected_order: Vec<String>,
325    pub cost: Option<RelationalJoinPlanningCost>,
326    pub attempts: Vec<RelationalJoinPlanningAttempt>,
327}
328
329impl RelationalJoinPlanningOutcome {
330    pub fn not_eligible(
331        reason: RelationalJoinPlanningReason,
332        selected_order: Vec<String>,
333        config: RelationalJoinEnumerationConfig,
334    ) -> Self {
335        Self::not_eligible_after_attempts(reason, selected_order, config, Vec::new())
336    }
337
338    pub fn not_eligible_after_attempts(
339        reason: RelationalJoinPlanningReason,
340        selected_order: Vec<String>,
341        config: RelationalJoinEnumerationConfig,
342        mut attempts: Vec<RelationalJoinPlanningAttempt>,
343    ) -> Self {
344        let attempt = RelationalJoinPlanningAttempt::not_eligible(
345            RelationalJoinPlanningStrategy::SyntaxOrder,
346            reason,
347        );
348        attempts.push(attempt);
349        Self {
350            strategy: RelationalJoinPlanningStrategy::SyntaxOrder,
351            status: RelationalJoinPlanningStatus::NotEligible,
352            reason,
353            memo_groups: None,
354            memo_expressions: None,
355            budget: config.into(),
356            selected_order,
357            cost: None,
358            attempts,
359        }
360    }
361
362    pub fn selected(
363        attempt: RelationalJoinPlanningAttempt,
364        selected_order: Vec<String>,
365        config: RelationalJoinEnumerationConfig,
366        mut attempts: Vec<RelationalJoinPlanningAttempt>,
367    ) -> Self {
368        debug_assert_eq!(attempt.status, RelationalJoinPlanningStatus::Selected);
369        debug_assert!(attempt.fallback_class.is_none());
370        let strategy = attempt.strategy;
371        let reason = attempt.reason;
372        let memo_groups = attempt.memo_groups;
373        let memo_expressions = attempt.memo_expressions;
374        let cost = attempt.cost;
375        attempts.push(attempt);
376        Self {
377            strategy,
378            status: RelationalJoinPlanningStatus::Selected,
379            reason,
380            memo_groups,
381            memo_expressions,
382            budget: config.into(),
383            selected_order,
384            cost,
385            attempts,
386        }
387    }
388
389    pub fn explicit_syntax_order(
390        selected_order: Vec<String>,
391        config: RelationalJoinEnumerationConfig,
392    ) -> Self {
393        let attempt = RelationalJoinPlanningAttempt::explicit_syntax_order();
394        Self {
395            strategy: attempt.strategy,
396            status: attempt.status,
397            reason: attempt.reason,
398            memo_groups: None,
399            memo_expressions: None,
400            budget: config.into(),
401            selected_order,
402            cost: None,
403            attempts: vec![attempt],
404        }
405    }
406
407    pub fn fallback_to_syntax(
408        mut attempts: Vec<RelationalJoinPlanningAttempt>,
409        selected_order: Vec<String>,
410        config: RelationalJoinEnumerationConfig,
411    ) -> Option<Self> {
412        let failed = attempts
413            .iter()
414            .rev()
415            .find(|attempt| attempt.status == RelationalJoinPlanningStatus::Fallback)
416            .cloned()?;
417        attempts.push(RelationalJoinPlanningAttempt::syntax_fallback());
418        Some(Self {
419            strategy: failed.strategy,
420            status: RelationalJoinPlanningStatus::Fallback,
421            reason: failed.reason,
422            memo_groups: failed.memo_groups,
423            memo_expressions: failed.memo_expressions,
424            budget: config.into(),
425            selected_order,
426            cost: None,
427            attempts,
428        })
429    }
430
431    pub fn join_order_reordered(&self) -> bool {
432        self.status == RelationalJoinPlanningStatus::Selected
433            && self.reason == RelationalJoinPlanningReason::CostReordered
434    }
435}
436
437#[cfg(test)]
438mod tests {
439    use super::*;
440
441    #[test]
442    fn planning_enums_expose_stable_diagnostic_names() {
443        assert_eq!(
444            RelationalJoinPlanningStrategy::InnerJoinMemo.as_str(),
445            "inner_join_memo"
446        );
447        assert_eq!(
448            RelationalJoinPlanningStrategy::CsgCmpMemo.as_str(),
449            "csg_cmp_memo"
450        );
451        assert_eq!(RelationalJoinPlanningStatus::Fallback.as_str(), "fallback");
452        assert_eq!(
453            RelationalJoinPlanningReason::ExpressionBudgetExceeded.as_str(),
454            "expression_budget_exceeded"
455        );
456        assert_eq!(
457            RelationalJoinPlanningReason::SpecializedJoinNotEnumerated.as_str(),
458            "specialized_join_not_enumerated"
459        );
460    }
461
462    #[test]
463    fn budget_failure_retains_required_and_configured_counts() {
464        let config = RelationalJoinEnumerationConfig {
465            max_groups: 8,
466            max_expressions: 16,
467        };
468        let attempt = RelationalJoinPlanningAttempt::fallback_from_enumeration(
469            RelationalJoinPlanningStrategy::InnerJoinMemo,
470            &RelationalJoinEnumerationError::ExpressionBudgetExceeded {
471                required_expressions: 17,
472                max_expressions: 16,
473            },
474        )
475        .expect("budget exhaustion is fallback eligible");
476        let outcome = RelationalJoinPlanningOutcome::fallback_to_syntax(
477            vec![attempt],
478            vec!["a".to_string(), "b".to_string()],
479            config,
480        )
481        .expect("budget exhaustion produces a syntax fallback outcome");
482
483        assert_eq!(outcome.status, RelationalJoinPlanningStatus::Fallback);
484        assert_eq!(outcome.memo_expressions, Some(17));
485        assert_eq!(outcome.budget.max_expressions, 16);
486        assert_eq!(outcome.attempts.len(), 2);
487        assert_eq!(
488            outcome.attempts[0].fallback_class,
489            Some(RelationalJoinPlanningFallbackClass::Budget)
490        );
491        assert_eq!(
492            outcome.attempts[1].strategy,
493            RelationalJoinPlanningStrategy::SyntaxOrder
494        );
495        assert!(!outcome.join_order_reordered());
496    }
497
498    #[test]
499    fn invalid_join_graph_is_not_fallback_eligible() {
500        let attempt = RelationalJoinPlanningAttempt::fallback_from_enumeration(
501            RelationalJoinPlanningStrategy::CsgCmpMemo,
502            &RelationalJoinEnumerationError::EmptyGraph,
503        );
504        assert!(attempt.is_none());
505
506        let rewrite = RelationalJoinPlanningAttempt::fallback_from_rewrite(
507            RelationalJoinPlanningStrategy::CsgCmpMemo,
508            &RelationalJoinRewriteError::RelationSetMismatch,
509        );
510        assert!(rewrite.is_none());
511    }
512}
hawdb_optimizer_relational/relational_planning.rs

hawdb_optimizer_relational/
relational_planning.rs
