hawdb_optimizer_relational/
relational_join.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
15//! Relational inner-join graph contracts and validation.
16
17use crate::{
18    Distribution, MemoryBudgetClass, PhysicalProperties, PlanCost, PlanCostBreakdown,
19    RelationalAccessPathDescriptor, RelationalAccessPathKind, RequiredProperties,
20    ScanPruningSupport,
21};
22use hawdb_expression::{BindingId, BindingSet};
23use std::{collections::BTreeMap, error::Error, fmt};
24
25#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
26pub struct RelationalJoinPredicateId(u32);
27
28impl RelationalJoinPredicateId {
29    pub const fn new(value: u32) -> Self {
30        Self(value)
31    }
32
33    pub const fn get(self) -> u32 {
34        self.0
35    }
36}
37
38#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct RelationalJoinAccessPath {
40    pub descriptor: RelationalAccessPathDescriptor,
41    pub required_bindings: BindingSet,
42    pub properties: PhysicalProperties,
43    pub applicability: RelationalJoinAccessApplicability,
44}
45
46#[derive(Debug, Clone, Copy, PartialEq, Eq)]
47pub enum RelationalJoinAccessApplicability {
48    Base,
49    Probe,
50    BaseAndProbe,
51}
52
53impl RelationalJoinAccessPath {
54    pub fn base(descriptor: RelationalAccessPathDescriptor) -> Self {
55        Self::new(
56            descriptor,
57            BindingSet::new(),
58            RelationalJoinAccessApplicability::Base,
59        )
60    }
61
62    pub fn probe(
63        descriptor: RelationalAccessPathDescriptor,
64        required_bindings: BindingSet,
65    ) -> Self {
66        Self::new(
67            descriptor,
68            required_bindings,
69            RelationalJoinAccessApplicability::Probe,
70        )
71    }
72
73    pub fn base_and_probe(descriptor: RelationalAccessPathDescriptor) -> Self {
74        Self::new(
75            descriptor,
76            BindingSet::new(),
77            RelationalJoinAccessApplicability::BaseAndProbe,
78        )
79    }
80
81    fn new(
82        descriptor: RelationalAccessPathDescriptor,
83        required_bindings: BindingSet,
84        applicability: RelationalJoinAccessApplicability,
85    ) -> Self {
86        let properties = access_path_properties(&descriptor);
87        Self {
88            descriptor,
89            required_bindings,
90            properties,
91            applicability,
92        }
93    }
94
95    pub fn with_properties(mut self, properties: PhysicalProperties) -> Self {
96        self.properties = properties;
97        self
98    }
99
100    pub(crate) fn supports_base(&self) -> bool {
101        matches!(
102            self.applicability,
103            RelationalJoinAccessApplicability::Base
104                | RelationalJoinAccessApplicability::BaseAndProbe
105        )
106    }
107
108    pub(crate) fn supports_probe(&self) -> bool {
109        matches!(
110            self.applicability,
111            RelationalJoinAccessApplicability::Probe
112                | RelationalJoinAccessApplicability::BaseAndProbe
113        )
114    }
115
116    pub(crate) fn validate_usage(&self) -> Result<(), &'static str> {
117        match self.applicability {
118            RelationalJoinAccessApplicability::Base
119            | RelationalJoinAccessApplicability::BaseAndProbe
120                if !self.required_bindings.is_empty() =>
121            {
122                Err("base access path cannot require another binding")
123            }
124            RelationalJoinAccessApplicability::Probe if self.required_bindings.is_empty() => {
125                Err("probe access path must require another binding")
126            }
127            _ => Ok(()),
128        }
129    }
130}
131
132#[derive(Debug, Clone, PartialEq, Eq)]
133pub struct RelationalJoinRelation {
134    pub binding: BindingId,
135    pub access_paths: Vec<RelationalJoinAccessPath>,
136}
137
138#[derive(Debug, Clone, PartialEq, Eq)]
139pub struct RelationalJoinPredicate {
140    pub id: RelationalJoinPredicateId,
141    pub bindings: BindingSet,
142}
143
144#[derive(Debug, Clone, PartialEq, Eq)]
145pub struct RelationalJoinGraph {
146    pub relations: Vec<RelationalJoinRelation>,
147    pub predicates: Vec<RelationalJoinPredicate>,
148}
149
150#[derive(Debug, Clone, Copy, PartialEq, Eq)]
151pub struct RelationalJoinEnumerationConfig {
152    pub max_groups: usize,
153    pub max_expressions: usize,
154}
155
156impl Default for RelationalJoinEnumerationConfig {
157    fn default() -> Self {
158        Self {
159            max_groups: 4_095,
160            max_expressions: 32_768,
161        }
162    }
163}
164
165#[derive(Debug, Clone, PartialEq, Eq)]
166pub struct RelationalJoinStep {
167    pub binding: BindingId,
168    pub access_path: RelationalJoinAccessPath,
169    pub activated_predicates: Vec<RelationalJoinPredicateId>,
170}
171
172#[derive(Debug, Clone, PartialEq, Eq)]
173pub struct RelationalJoinPlan {
174    pub base_binding: BindingId,
175    pub base_access_path: RelationalJoinAccessPath,
176    pub steps: Vec<RelationalJoinStep>,
177    pub cost_breakdown: PlanCostBreakdown,
178    pub properties: PhysicalProperties,
179}
180
181impl RelationalJoinPlan {
182    pub fn cost(&self) -> PlanCost {
183        self.cost_breakdown.as_plan_cost()
184    }
185
186    pub fn binding_order(&self) -> Vec<BindingId> {
187        std::iter::once(self.base_binding)
188            .chain(self.steps.iter().map(|step| step.binding))
189            .collect()
190    }
191}
192
193#[derive(Debug, Clone, PartialEq, Eq)]
194pub struct RelationalInnerJoinEnumeration {
195    pub plan: RelationalJoinPlan,
196    pub memo_groups: usize,
197    pub memo_expressions: usize,
198}
199
200#[derive(Debug, Clone, PartialEq, Eq)]
201pub enum RelationalJoinEnumerationError {
202    EmptyGraph,
203    DuplicateBinding(BindingId),
204    DuplicatePredicate(RelationalJoinPredicateId),
205    PredicateHasFewerThanTwoBindings(RelationalJoinPredicateId),
206    UnknownPredicateBinding {
207        predicate: RelationalJoinPredicateId,
208        binding: BindingId,
209    },
210    UnknownAccessBinding {
211        relation: BindingId,
212        binding: BindingId,
213    },
214    AccessWithoutPredicate {
215        relation: BindingId,
216        binding: BindingId,
217    },
218    SelfDependentAccess(BindingId),
219    MissingBaseAccess(BindingId),
220    InvalidAccessPath {
221        binding: BindingId,
222        reason: &'static str,
223    },
224    GroupBudgetExceeded {
225        required_groups: usize,
226        max_groups: usize,
227    },
228    ExpressionBudgetExceeded {
229        required_expressions: usize,
230        max_expressions: usize,
231    },
232    Disconnected,
233    RequiredPropertiesUnsatisfied,
234}
235
236impl fmt::Display for RelationalJoinEnumerationError {
237    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
238        match self {
239            Self::EmptyGraph => write!(formatter, "relational join graph is empty"),
240            Self::DuplicateBinding(binding) => {
241                write!(formatter, "duplicate relational binding {}", binding.get())
242            }
243            Self::DuplicatePredicate(predicate) => {
244                write!(formatter, "duplicate relational predicate {}", predicate.get())
245            }
246            Self::PredicateHasFewerThanTwoBindings(predicate) => write!(
247                formatter,
248                "relational join predicate {} references fewer than two bindings",
249                predicate.get()
250            ),
251            Self::UnknownPredicateBinding { predicate, binding } => write!(
252                formatter,
253                "relational join predicate {} references unknown binding {}",
254                predicate.get(),
255                binding.get()
256            ),
257            Self::UnknownAccessBinding { relation, binding } => write!(
258                formatter,
259                "relational binding {} access path requires unknown binding {}",
260                relation.get(),
261                binding.get()
262            ),
263            Self::AccessWithoutPredicate { relation, binding } => write!(
264                formatter,
265                "relational binding {} access path depends on binding {} without a connecting predicate",
266                relation.get(),
267                binding.get()
268            ),
269            Self::SelfDependentAccess(binding) => write!(
270                formatter,
271                "relational binding {} access path depends on itself",
272                binding.get()
273            ),
274            Self::MissingBaseAccess(binding) => write!(
275                formatter,
276                "relational binding {} has no unbound access path",
277                binding.get()
278            ),
279            Self::InvalidAccessPath { binding, reason } => write!(
280                formatter,
281                "relational binding {} has an invalid access path: {reason}",
282                binding.get()
283            ),
284            Self::GroupBudgetExceeded {
285                required_groups,
286                max_groups,
287            } => write!(
288                formatter,
289                "relational join enumeration requires {required_groups} groups, exceeding max_groups {max_groups}"
290            ),
291            Self::ExpressionBudgetExceeded {
292                required_expressions,
293                max_expressions,
294            } => write!(
295                formatter,
296                "relational join enumeration requires at least {required_expressions} expressions, exceeding max_expressions {max_expressions}"
297            ),
298            Self::Disconnected => write!(
299                formatter,
300                "relational join graph has no connected left-deep enumeration"
301            ),
302            Self::RequiredPropertiesUnsatisfied => write!(
303                formatter,
304                "no relational join order satisfies the required physical properties"
305            ),
306        }
307    }
308}
309
310impl Error for RelationalJoinEnumerationError {}
311
312pub fn enumerate_relational_inner_joins(
313    graph: &RelationalJoinGraph,
314    required_properties: &RequiredProperties,
315    config: RelationalJoinEnumerationConfig,
316) -> Result<RelationalInnerJoinEnumeration, RelationalJoinEnumerationError> {
317    enumerate_relational_inner_joins_with_cost_contexts(
318        graph,
319        required_properties,
320        config,
321        &crate::RelationalJoinCostContexts::default(),
322    )
323}
324
325pub fn enumerate_relational_inner_joins_with_cost_contexts(
326    graph: &RelationalJoinGraph,
327    required_properties: &RequiredProperties,
328    config: RelationalJoinEnumerationConfig,
329    cost_contexts: &crate::RelationalJoinCostContexts,
330) -> Result<RelationalInnerJoinEnumeration, RelationalJoinEnumerationError> {
331    validate_graph(graph)?;
332    crate::relational_join_hypergraph::enumerate_inner_graph(
333        graph,
334        required_properties,
335        config,
336        cost_contexts,
337    )
338}
339
340fn validate_graph(graph: &RelationalJoinGraph) -> Result<(), RelationalJoinEnumerationError> {
341    if graph.relations.is_empty() {
342        return Err(RelationalJoinEnumerationError::EmptyGraph);
343    }
344    let relation_bindings: BindingSet = graph
345        .relations
346        .iter()
347        .map(|relation| relation.binding)
348        .collect();
349    if relation_bindings.len() != graph.relations.len() {
350        let mut seen = BindingSet::new();
351        let duplicate = graph
352            .relations
353            .iter()
354            .map(|relation| relation.binding)
355            .find(|binding| !seen.insert(*binding))
356            .expect("binding count mismatch requires a duplicate");
357        return Err(RelationalJoinEnumerationError::DuplicateBinding(duplicate));
358    }
359    for relation in &graph.relations {
360        if !relation
361            .access_paths
362            .iter()
363            .any(RelationalJoinAccessPath::supports_base)
364        {
365            return Err(RelationalJoinEnumerationError::MissingBaseAccess(
366                relation.binding,
367            ));
368        }
369        for access in &relation.access_paths {
370            access.descriptor.validate().map_err(|reason| {
371                RelationalJoinEnumerationError::InvalidAccessPath {
372                    binding: relation.binding,
373                    reason,
374                }
375            })?;
376            access.validate_usage().map_err(|reason| {
377                RelationalJoinEnumerationError::InvalidAccessPath {
378                    binding: relation.binding,
379                    reason,
380                }
381            })?;
382            if access.required_bindings.contains(relation.binding) {
383                return Err(RelationalJoinEnumerationError::SelfDependentAccess(
384                    relation.binding,
385                ));
386            }
387            if let Some(binding) = access
388                .required_bindings
389                .iter()
390                .find(|binding| !relation_bindings.contains(*binding))
391            {
392                return Err(RelationalJoinEnumerationError::UnknownAccessBinding {
393                    relation: relation.binding,
394                    binding,
395                });
396            }
397            if let Some(binding) = access.required_bindings.iter().find(|binding| {
398                !graph.predicates.iter().any(|predicate| {
399                    predicate.bindings.contains(relation.binding)
400                        && predicate.bindings.contains(*binding)
401                })
402            }) {
403                return Err(RelationalJoinEnumerationError::AccessWithoutPredicate {
404                    relation: relation.binding,
405                    binding,
406                });
407            }
408        }
409    }
410
411    let mut predicate_ids = BTreeMap::new();
412    for predicate in &graph.predicates {
413        if predicate_ids.insert(predicate.id, ()).is_some() {
414            return Err(RelationalJoinEnumerationError::DuplicatePredicate(
415                predicate.id,
416            ));
417        }
418        if predicate.bindings.len() < 2 {
419            return Err(
420                RelationalJoinEnumerationError::PredicateHasFewerThanTwoBindings(predicate.id),
421            );
422        }
423        if let Some(binding) = predicate
424            .bindings
425            .iter()
426            .find(|binding| !relation_bindings.contains(*binding))
427        {
428            return Err(RelationalJoinEnumerationError::UnknownPredicateBinding {
429                predicate: predicate.id,
430                binding,
431            });
432        }
433    }
434    Ok(())
435}
436
437fn access_path_properties(descriptor: &RelationalAccessPathDescriptor) -> PhysicalProperties {
438    let ordering_start = descriptor.equality_prefix_len;
439    let ordering_end = ordering_start
440        .saturating_add(descriptor.order_prefix_len)
441        .min(descriptor.index_columns.len());
442    PhysicalProperties {
443        distribution: Distribution::Single,
444        ordering: descriptor.index_columns[ordering_start..ordering_end].to_vec(),
445        covering_fields: if descriptor.covering {
446            descriptor.index_columns.clone()
447        } else {
448            Vec::new()
449        },
450        scan_pruning: match descriptor.kind {
451            RelationalAccessPathKind::FullScan => ScanPruningSupport::None,
452            RelationalAccessPathKind::PrimaryKey | RelationalAccessPathKind::Index => {
453                ScanPruningSupport::Index
454            }
455        },
456        memory_budget: MemoryBudgetClass::Constant,
457        ..PhysicalProperties::default()
458    }
459}
460
461#[cfg(test)]
462mod tests {
463    use super::*;
464    use std::collections::BTreeSet;
465
466    const A: BindingId = BindingId::new(1);
467    const B: BindingId = BindingId::new(2);
468    const C: BindingId = BindingId::new(3);
469
470    fn descriptor(
471        name: &str,
472        kind: RelationalAccessPathKind,
473        rows: usize,
474        unique: bool,
475    ) -> RelationalAccessPathDescriptor {
476        let index_columns = if kind != RelationalAccessPathKind::FullScan {
477            vec!["id".to_string()]
478        } else {
479            Vec::new()
480        };
481        RelationalAccessPathDescriptor {
482            kind,
483            name: name.to_string(),
484            access_columns: index_columns.iter().cloned().collect::<BTreeSet<_>>(),
485            equality_prefix_len: index_columns.len(),
486            index_columns,
487            order_prefix_len: 0,
488            exclusive_range: false,
489            reverse_order: false,
490            unique_point: unique,
491            covering: false,
492            requires_row_fetch: kind == RelationalAccessPathKind::Index,
493            estimated_rows: rows,
494        }
495    }
496
497    fn scan(rows: usize) -> RelationalJoinAccessPath {
498        RelationalJoinAccessPath::base_and_probe(descriptor(
499            "__full_scan",
500            RelationalAccessPathKind::FullScan,
501            rows,
502            false,
503        ))
504    }
505
506    fn probe(name: &str, required: BindingId, rows: usize) -> RelationalJoinAccessPath {
507        RelationalJoinAccessPath::probe(
508            descriptor(name, RelationalAccessPathKind::Index, rows, rows == 1),
509            required.into(),
510        )
511    }
512
513    fn relation_with_probes(
514        binding: BindingId,
515        rows: usize,
516        probes: Vec<RelationalJoinAccessPath>,
517    ) -> RelationalJoinRelation {
518        let mut access_paths = vec![scan(rows)];
519        access_paths.extend(probes);
520        RelationalJoinRelation {
521            binding,
522            access_paths,
523        }
524    }
525
526    fn predicate(id: u32, bindings: impl Into<BindingSet>) -> RelationalJoinPredicate {
527        RelationalJoinPredicate {
528            id: RelationalJoinPredicateId::new(id),
529            bindings: bindings.into(),
530        }
531    }
532
533    #[test]
534    fn memo_enumeration_prefers_selective_outer_and_index_probes() {
535        let graph = RelationalJoinGraph {
536            relations: vec![
537                relation_with_probes(A, 1_000, vec![probe("a_by_b", B, 1)]),
538                relation_with_probes(B, 100, vec![probe("b_by_a", A, 100), probe("b_by_c", C, 1)]),
539                relation_with_probes(C, 1, vec![probe("c_by_b", B, 100)]),
540            ],
541            predicates: vec![predicate(1, [A, B]), predicate(2, [B, C])],
542        };
543
544        let result = enumerate_relational_inner_joins(
545            &graph,
546            &RequiredProperties::default(),
547            RelationalJoinEnumerationConfig::default(),
548        )
549        .unwrap();
550
551        assert_eq!(result.plan.binding_order(), [C, B, A]);
552        assert_eq!(
553            result.plan.cost(),
554            PlanCost {
555                estimated_rows: 1,
556                cost: 21
557            }
558        );
559        assert_eq!(
560            result.plan.steps[0].activated_predicates,
561            [RelationalJoinPredicateId::new(2)]
562        );
563        assert_eq!(
564            result.plan.steps[1].activated_predicates,
565            [RelationalJoinPredicateId::new(1)]
566        );
567        assert!(result.memo_groups >= 5);
568        assert!(result.memo_expressions > result.memo_groups);
569    }
570
571    #[test]
572    fn memo_group_contains_equivalent_join_rewrites() {
573        let graph = RelationalJoinGraph {
574            relations: vec![
575                relation_with_probes(A, 10, vec![probe("a_by_b", B, 1), probe("a_by_c", C, 1)]),
576                relation_with_probes(B, 10, vec![probe("b_by_a", A, 1), probe("b_by_c", C, 1)]),
577                relation_with_probes(C, 10, vec![probe("c_by_a", A, 1), probe("c_by_b", B, 1)]),
578            ],
579            predicates: vec![
580                predicate(1, [A, B]),
581                predicate(2, [B, C]),
582                predicate(3, [A, C]),
583            ],
584        };
585
586        let result = enumerate_relational_inner_joins(
587            &graph,
588            &RequiredProperties::default(),
589            RelationalJoinEnumerationConfig::default(),
590        )
591        .unwrap();
592
593        assert_eq!(result.memo_groups, 7);
594        assert_eq!(result.memo_expressions, 12);
595        assert_eq!(result.plan.binding_order(), [A, B, C]);
596    }
597
598    #[test]
599    fn required_ordering_is_part_of_the_best_plan_cache_key() {
600        let ordered = scan(100).with_properties(PhysicalProperties {
601            distribution: Distribution::Single,
602            ordering: vec!["created_at".to_string()],
603            memory_budget: MemoryBudgetClass::Constant,
604            ..PhysicalProperties::default()
605        });
606        let graph = RelationalJoinGraph {
607            relations: vec![
608                RelationalJoinRelation {
609                    binding: A,
610                    access_paths: vec![ordered, probe("a_by_b", B, 1)],
611                },
612                relation_with_probes(B, 1, vec![probe("b_by_a", A, 1)]),
613            ],
614            predicates: vec![predicate(1, [A, B])],
615        };
616        let required = RequiredProperties {
617            distribution: Distribution::Single,
618            ordering: vec!["created_at".to_string()],
619            ..RequiredProperties::default()
620        };
621
622        let result = enumerate_relational_inner_joins(
623            &graph,
624            &required,
625            RelationalJoinEnumerationConfig::default(),
626        )
627        .unwrap();
628
629        assert_eq!(result.plan.binding_order(), [A, B]);
630        assert_eq!(result.plan.properties.ordering, ["created_at".to_string()]);
631    }
632
633    #[test]
634    fn base_only_access_paths_are_not_costed_as_inner_probes() {
635        let selective_base = RelationalJoinAccessPath::base(descriptor(
636            "a_constant_filter",
637            RelationalAccessPathKind::Index,
638            5,
639            false,
640        ));
641        let graph = RelationalJoinGraph {
642            relations: vec![
643                RelationalJoinRelation {
644                    binding: A,
645                    access_paths: vec![scan(100), selective_base, probe("a_by_b", B, 100)],
646                },
647                relation_with_probes(B, 1, Vec::new()),
648            ],
649            predicates: vec![predicate(1, [A, B])],
650        };
651
652        let result = enumerate_relational_inner_joins(
653            &graph,
654            &RequiredProperties::default(),
655            RelationalJoinEnumerationConfig::default(),
656        )
657        .unwrap();
658
659        assert_eq!(result.plan.binding_order(), [A, B]);
660        assert_eq!(
661            result.plan.base_access_path.descriptor.name,
662            "a_constant_filter"
663        );
664        assert_eq!(
665            result.plan.cost(),
666            PlanCost {
667                estimated_rows: 5,
668                cost: 67
669            }
670        );
671    }
672
673    #[test]
674    fn disconnected_graph_does_not_return_a_partial_enumeration() {
675        let graph = RelationalJoinGraph {
676            relations: vec![
677                relation_with_probes(A, 10, Vec::new()),
678                relation_with_probes(B, 10, Vec::new()),
679            ],
680            predicates: Vec::new(),
681        };
682
683        assert_eq!(
684            enumerate_relational_inner_joins(
685                &graph,
686                &RequiredProperties::default(),
687                RelationalJoinEnumerationConfig::default(),
688            ),
689            Err(RelationalJoinEnumerationError::Disconnected)
690        );
691    }
692
693    #[test]
694    fn access_dependencies_require_a_matching_join_predicate() {
695        let graph = RelationalJoinGraph {
696            relations: vec![
697                relation_with_probes(A, 10, vec![probe("a_by_b", B, 1)]),
698                relation_with_probes(B, 10, Vec::new()),
699                relation_with_probes(C, 10, Vec::new()),
700            ],
701            predicates: vec![predicate(1, [A, C])],
702        };
703
704        assert_eq!(
705            enumerate_relational_inner_joins(
706                &graph,
707                &RequiredProperties::default(),
708                RelationalJoinEnumerationConfig::default(),
709            ),
710            Err(RelationalJoinEnumerationError::AccessWithoutPredicate {
711                relation: A,
712                binding: B,
713            })
714        );
715    }
716
717    #[test]
718    fn group_budget_rejects_the_next_actual_connected_group() {
719        let graph = RelationalJoinGraph {
720            relations: vec![
721                relation_with_probes(A, 10, Vec::new()),
722                relation_with_probes(B, 10, Vec::new()),
723                relation_with_probes(C, 10, Vec::new()),
724            ],
725            predicates: vec![predicate(1, [A, B]), predicate(2, [B, C])],
726        };
727
728        assert_eq!(
729            enumerate_relational_inner_joins(
730                &graph,
731                &RequiredProperties::default(),
732                RelationalJoinEnumerationConfig {
733                    max_groups: 5,
734                    max_expressions: 100,
735                },
736            ),
737            Err(RelationalJoinEnumerationError::GroupBudgetExceeded {
738                required_groups: 6,
739                max_groups: 5,
740            })
741        );
742    }
743}
hawdb_optimizer_relational/relational_join.rs

hawdb_optimizer_relational/
relational_join.rs
