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            range: None,
490            reverse_order: false,
491            unique_point: unique,
492            covering: false,
493            requires_row_fetch: kind == RelationalAccessPathKind::Index,
494            estimated_rows: rows,
495        }
496    }
497
498    fn scan(rows: usize) -> RelationalJoinAccessPath {
499        RelationalJoinAccessPath::base_and_probe(descriptor(
500            "__full_scan",
501            RelationalAccessPathKind::FullScan,
502            rows,
503            false,
504        ))
505    }
506
507    fn probe(name: &str, required: BindingId, rows: usize) -> RelationalJoinAccessPath {
508        RelationalJoinAccessPath::probe(
509            descriptor(name, RelationalAccessPathKind::Index, rows, rows == 1),
510            required.into(),
511        )
512    }
513
514    fn relation_with_probes(
515        binding: BindingId,
516        rows: usize,
517        probes: Vec<RelationalJoinAccessPath>,
518    ) -> RelationalJoinRelation {
519        let mut access_paths = vec![scan(rows)];
520        access_paths.extend(probes);
521        RelationalJoinRelation {
522            binding,
523            access_paths,
524        }
525    }
526
527    fn predicate(id: u32, bindings: impl Into<BindingSet>) -> RelationalJoinPredicate {
528        RelationalJoinPredicate {
529            id: RelationalJoinPredicateId::new(id),
530            bindings: bindings.into(),
531        }
532    }
533
534    #[test]
535    fn memo_enumeration_prefers_selective_outer_and_index_probes() {
536        let graph = RelationalJoinGraph {
537            relations: vec![
538                relation_with_probes(A, 1_000, vec![probe("a_by_b", B, 1)]),
539                relation_with_probes(B, 100, vec![probe("b_by_a", A, 100), probe("b_by_c", C, 1)]),
540                relation_with_probes(C, 1, vec![probe("c_by_b", B, 100)]),
541            ],
542            predicates: vec![predicate(1, [A, B]), predicate(2, [B, C])],
543        };
544
545        let result = enumerate_relational_inner_joins(
546            &graph,
547            &RequiredProperties::default(),
548            RelationalJoinEnumerationConfig::default(),
549        )
550        .unwrap();
551
552        assert_eq!(result.plan.binding_order(), [C, B, A]);
553        assert_eq!(
554            result.plan.cost(),
555            PlanCost {
556                estimated_rows: 1,
557                cost: 21
558            }
559        );
560        assert_eq!(
561            result.plan.steps[0].activated_predicates,
562            [RelationalJoinPredicateId::new(2)]
563        );
564        assert_eq!(
565            result.plan.steps[1].activated_predicates,
566            [RelationalJoinPredicateId::new(1)]
567        );
568        assert!(result.memo_groups >= 5);
569        assert!(result.memo_expressions > result.memo_groups);
570    }
571
572    #[test]
573    fn memo_group_contains_equivalent_join_rewrites() {
574        let graph = RelationalJoinGraph {
575            relations: vec![
576                relation_with_probes(A, 10, vec![probe("a_by_b", B, 1), probe("a_by_c", C, 1)]),
577                relation_with_probes(B, 10, vec![probe("b_by_a", A, 1), probe("b_by_c", C, 1)]),
578                relation_with_probes(C, 10, vec![probe("c_by_a", A, 1), probe("c_by_b", B, 1)]),
579            ],
580            predicates: vec![
581                predicate(1, [A, B]),
582                predicate(2, [B, C]),
583                predicate(3, [A, C]),
584            ],
585        };
586
587        let result = enumerate_relational_inner_joins(
588            &graph,
589            &RequiredProperties::default(),
590            RelationalJoinEnumerationConfig::default(),
591        )
592        .unwrap();
593
594        assert_eq!(result.memo_groups, 7);
595        assert_eq!(result.memo_expressions, 12);
596        assert_eq!(result.plan.binding_order(), [A, B, C]);
597    }
598
599    #[test]
600    fn required_ordering_is_part_of_the_best_plan_cache_key() {
601        let ordered = scan(100).with_properties(PhysicalProperties {
602            distribution: Distribution::Single,
603            ordering: vec!["created_at".to_string()],
604            memory_budget: MemoryBudgetClass::Constant,
605            ..PhysicalProperties::default()
606        });
607        let graph = RelationalJoinGraph {
608            relations: vec![
609                RelationalJoinRelation {
610                    binding: A,
611                    access_paths: vec![ordered, probe("a_by_b", B, 1)],
612                },
613                relation_with_probes(B, 1, vec![probe("b_by_a", A, 1)]),
614            ],
615            predicates: vec![predicate(1, [A, B])],
616        };
617        let required = RequiredProperties {
618            distribution: Distribution::Single,
619            ordering: vec!["created_at".to_string()],
620            ..RequiredProperties::default()
621        };
622
623        let result = enumerate_relational_inner_joins(
624            &graph,
625            &required,
626            RelationalJoinEnumerationConfig::default(),
627        )
628        .unwrap();
629
630        assert_eq!(result.plan.binding_order(), [A, B]);
631        assert_eq!(result.plan.properties.ordering, ["created_at".to_string()]);
632    }
633
634    #[test]
635    fn base_only_access_paths_are_not_costed_as_inner_probes() {
636        let selective_base = RelationalJoinAccessPath::base(descriptor(
637            "a_constant_filter",
638            RelationalAccessPathKind::Index,
639            5,
640            false,
641        ));
642        let graph = RelationalJoinGraph {
643            relations: vec![
644                RelationalJoinRelation {
645                    binding: A,
646                    access_paths: vec![scan(100), selective_base, probe("a_by_b", B, 100)],
647                },
648                relation_with_probes(B, 1, Vec::new()),
649            ],
650            predicates: vec![predicate(1, [A, B])],
651        };
652
653        let result = enumerate_relational_inner_joins(
654            &graph,
655            &RequiredProperties::default(),
656            RelationalJoinEnumerationConfig::default(),
657        )
658        .unwrap();
659
660        assert_eq!(result.plan.binding_order(), [A, B]);
661        assert_eq!(
662            result.plan.base_access_path.descriptor.name,
663            "a_constant_filter"
664        );
665        assert_eq!(
666            result.plan.cost(),
667            PlanCost {
668                estimated_rows: 5,
669                cost: 67
670            }
671        );
672    }
673
674    #[test]
675    fn disconnected_graph_does_not_return_a_partial_enumeration() {
676        let graph = RelationalJoinGraph {
677            relations: vec![
678                relation_with_probes(A, 10, Vec::new()),
679                relation_with_probes(B, 10, Vec::new()),
680            ],
681            predicates: Vec::new(),
682        };
683
684        assert_eq!(
685            enumerate_relational_inner_joins(
686                &graph,
687                &RequiredProperties::default(),
688                RelationalJoinEnumerationConfig::default(),
689            ),
690            Err(RelationalJoinEnumerationError::Disconnected)
691        );
692    }
693
694    #[test]
695    fn access_dependencies_require_a_matching_join_predicate() {
696        let graph = RelationalJoinGraph {
697            relations: vec![
698                relation_with_probes(A, 10, vec![probe("a_by_b", B, 1)]),
699                relation_with_probes(B, 10, Vec::new()),
700                relation_with_probes(C, 10, Vec::new()),
701            ],
702            predicates: vec![predicate(1, [A, C])],
703        };
704
705        assert_eq!(
706            enumerate_relational_inner_joins(
707                &graph,
708                &RequiredProperties::default(),
709                RelationalJoinEnumerationConfig::default(),
710            ),
711            Err(RelationalJoinEnumerationError::AccessWithoutPredicate {
712                relation: A,
713                binding: B,
714            })
715        );
716    }
717
718    #[test]
719    fn group_budget_rejects_the_next_actual_connected_group() {
720        let graph = RelationalJoinGraph {
721            relations: vec![
722                relation_with_probes(A, 10, Vec::new()),
723                relation_with_probes(B, 10, Vec::new()),
724                relation_with_probes(C, 10, Vec::new()),
725            ],
726            predicates: vec![predicate(1, [A, B]), predicate(2, [B, C])],
727        };
728
729        assert_eq!(
730            enumerate_relational_inner_joins(
731                &graph,
732                &RequiredProperties::default(),
733                RelationalJoinEnumerationConfig {
734                    max_groups: 5,
735                    max_expressions: 100,
736                },
737            ),
738            Err(RelationalJoinEnumerationError::GroupBudgetExceeded {
739                required_groups: 6,
740                max_groups: 5,
741            })
742        );
743    }
744}
hawdb_optimizer_relational/relational_join.rs

hawdb_optimizer_relational/
relational_join.rs
