hawdb_optimizer/
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    validate_graph(graph)?;
318    crate::relational_join_hypergraph::enumerate_inner_graph(graph, required_properties, config)
319}
320
321fn validate_graph(graph: &RelationalJoinGraph) -> Result<(), RelationalJoinEnumerationError> {
322    if graph.relations.is_empty() {
323        return Err(RelationalJoinEnumerationError::EmptyGraph);
324    }
325    let relation_bindings: BindingSet = graph
326        .relations
327        .iter()
328        .map(|relation| relation.binding)
329        .collect();
330    if relation_bindings.len() != graph.relations.len() {
331        let mut seen = BindingSet::new();
332        let duplicate = graph
333            .relations
334            .iter()
335            .map(|relation| relation.binding)
336            .find(|binding| !seen.insert(*binding))
337            .expect("binding count mismatch requires a duplicate");
338        return Err(RelationalJoinEnumerationError::DuplicateBinding(duplicate));
339    }
340    for relation in &graph.relations {
341        if !relation
342            .access_paths
343            .iter()
344            .any(RelationalJoinAccessPath::supports_base)
345        {
346            return Err(RelationalJoinEnumerationError::MissingBaseAccess(
347                relation.binding,
348            ));
349        }
350        for access in &relation.access_paths {
351            access.descriptor.validate().map_err(|reason| {
352                RelationalJoinEnumerationError::InvalidAccessPath {
353                    binding: relation.binding,
354                    reason,
355                }
356            })?;
357            access.validate_usage().map_err(|reason| {
358                RelationalJoinEnumerationError::InvalidAccessPath {
359                    binding: relation.binding,
360                    reason,
361                }
362            })?;
363            if access.required_bindings.contains(relation.binding) {
364                return Err(RelationalJoinEnumerationError::SelfDependentAccess(
365                    relation.binding,
366                ));
367            }
368            if let Some(binding) = access
369                .required_bindings
370                .iter()
371                .find(|binding| !relation_bindings.contains(*binding))
372            {
373                return Err(RelationalJoinEnumerationError::UnknownAccessBinding {
374                    relation: relation.binding,
375                    binding,
376                });
377            }
378            if let Some(binding) = access.required_bindings.iter().find(|binding| {
379                !graph.predicates.iter().any(|predicate| {
380                    predicate.bindings.contains(relation.binding)
381                        && predicate.bindings.contains(*binding)
382                })
383            }) {
384                return Err(RelationalJoinEnumerationError::AccessWithoutPredicate {
385                    relation: relation.binding,
386                    binding,
387                });
388            }
389        }
390    }
391
392    let mut predicate_ids = BTreeMap::new();
393    for predicate in &graph.predicates {
394        if predicate_ids.insert(predicate.id, ()).is_some() {
395            return Err(RelationalJoinEnumerationError::DuplicatePredicate(
396                predicate.id,
397            ));
398        }
399        if predicate.bindings.len() < 2 {
400            return Err(
401                RelationalJoinEnumerationError::PredicateHasFewerThanTwoBindings(predicate.id),
402            );
403        }
404        if let Some(binding) = predicate
405            .bindings
406            .iter()
407            .find(|binding| !relation_bindings.contains(*binding))
408        {
409            return Err(RelationalJoinEnumerationError::UnknownPredicateBinding {
410                predicate: predicate.id,
411                binding,
412            });
413        }
414    }
415    Ok(())
416}
417
418fn access_path_properties(descriptor: &RelationalAccessPathDescriptor) -> PhysicalProperties {
419    let ordering_start = descriptor.equality_prefix_len;
420    let ordering_end = ordering_start
421        .saturating_add(descriptor.order_prefix_len)
422        .min(descriptor.index_columns.len());
423    PhysicalProperties {
424        distribution: Distribution::Single,
425        ordering: descriptor.index_columns[ordering_start..ordering_end].to_vec(),
426        covering_fields: if descriptor.covering {
427            descriptor.index_columns.clone()
428        } else {
429            Vec::new()
430        },
431        scan_pruning: match descriptor.kind {
432            RelationalAccessPathKind::FullScan => ScanPruningSupport::None,
433            RelationalAccessPathKind::PrimaryKey | RelationalAccessPathKind::Index => {
434                ScanPruningSupport::Index
435            }
436        },
437        memory_budget: MemoryBudgetClass::Constant,
438        ..PhysicalProperties::default()
439    }
440}
441
442#[cfg(test)]
443mod tests {
444    use super::*;
445    use std::collections::BTreeSet;
446
447    const A: BindingId = BindingId::new(1);
448    const B: BindingId = BindingId::new(2);
449    const C: BindingId = BindingId::new(3);
450
451    fn descriptor(
452        name: &str,
453        kind: RelationalAccessPathKind,
454        rows: usize,
455        unique: bool,
456    ) -> RelationalAccessPathDescriptor {
457        let index_columns = if kind != RelationalAccessPathKind::FullScan {
458            vec!["id".to_string()]
459        } else {
460            Vec::new()
461        };
462        RelationalAccessPathDescriptor {
463            kind,
464            name: name.to_string(),
465            access_columns: index_columns.iter().cloned().collect::<BTreeSet<_>>(),
466            equality_prefix_len: index_columns.len(),
467            index_columns,
468            order_prefix_len: 0,
469            exclusive_range: false,
470            reverse_order: false,
471            unique_point: unique,
472            covering: false,
473            requires_row_fetch: kind == RelationalAccessPathKind::Index,
474            estimated_rows: rows,
475        }
476    }
477
478    fn scan(rows: usize) -> RelationalJoinAccessPath {
479        RelationalJoinAccessPath::base_and_probe(descriptor(
480            "__full_scan",
481            RelationalAccessPathKind::FullScan,
482            rows,
483            false,
484        ))
485    }
486
487    fn probe(name: &str, required: BindingId, rows: usize) -> RelationalJoinAccessPath {
488        RelationalJoinAccessPath::probe(
489            descriptor(name, RelationalAccessPathKind::Index, rows, rows == 1),
490            required.into(),
491        )
492    }
493
494    fn relation_with_probes(
495        binding: BindingId,
496        rows: usize,
497        probes: Vec<RelationalJoinAccessPath>,
498    ) -> RelationalJoinRelation {
499        let mut access_paths = vec![scan(rows)];
500        access_paths.extend(probes);
501        RelationalJoinRelation {
502            binding,
503            access_paths,
504        }
505    }
506
507    fn predicate(id: u32, bindings: impl Into<BindingSet>) -> RelationalJoinPredicate {
508        RelationalJoinPredicate {
509            id: RelationalJoinPredicateId::new(id),
510            bindings: bindings.into(),
511        }
512    }
513
514    #[test]
515    fn memo_enumeration_prefers_selective_outer_and_index_probes() {
516        let graph = RelationalJoinGraph {
517            relations: vec![
518                relation_with_probes(A, 1_000, vec![probe("a_by_b", B, 1)]),
519                relation_with_probes(B, 100, vec![probe("b_by_a", A, 100), probe("b_by_c", C, 1)]),
520                relation_with_probes(C, 1, vec![probe("c_by_b", B, 100)]),
521            ],
522            predicates: vec![predicate(1, [A, B]), predicate(2, [B, C])],
523        };
524
525        let result = enumerate_relational_inner_joins(
526            &graph,
527            &RequiredProperties::default(),
528            RelationalJoinEnumerationConfig::default(),
529        )
530        .unwrap();
531
532        assert_eq!(result.plan.binding_order(), [C, B, A]);
533        assert_eq!(
534            result.plan.cost(),
535            PlanCost {
536                estimated_rows: 1,
537                cost: 21
538            }
539        );
540        assert_eq!(
541            result.plan.steps[0].activated_predicates,
542            [RelationalJoinPredicateId::new(2)]
543        );
544        assert_eq!(
545            result.plan.steps[1].activated_predicates,
546            [RelationalJoinPredicateId::new(1)]
547        );
548        assert!(result.memo_groups >= 5);
549        assert!(result.memo_expressions > result.memo_groups);
550    }
551
552    #[test]
553    fn memo_group_contains_equivalent_join_rewrites() {
554        let graph = RelationalJoinGraph {
555            relations: vec![
556                relation_with_probes(A, 10, vec![probe("a_by_b", B, 1), probe("a_by_c", C, 1)]),
557                relation_with_probes(B, 10, vec![probe("b_by_a", A, 1), probe("b_by_c", C, 1)]),
558                relation_with_probes(C, 10, vec![probe("c_by_a", A, 1), probe("c_by_b", B, 1)]),
559            ],
560            predicates: vec![
561                predicate(1, [A, B]),
562                predicate(2, [B, C]),
563                predicate(3, [A, C]),
564            ],
565        };
566
567        let result = enumerate_relational_inner_joins(
568            &graph,
569            &RequiredProperties::default(),
570            RelationalJoinEnumerationConfig::default(),
571        )
572        .unwrap();
573
574        assert_eq!(result.memo_groups, 7);
575        assert_eq!(result.memo_expressions, 12);
576        assert_eq!(result.plan.binding_order(), [A, B, C]);
577    }
578
579    #[test]
580    fn required_ordering_is_part_of_the_best_plan_cache_key() {
581        let ordered = scan(100).with_properties(PhysicalProperties {
582            distribution: Distribution::Single,
583            ordering: vec!["created_at".to_string()],
584            memory_budget: MemoryBudgetClass::Constant,
585            ..PhysicalProperties::default()
586        });
587        let graph = RelationalJoinGraph {
588            relations: vec![
589                RelationalJoinRelation {
590                    binding: A,
591                    access_paths: vec![ordered, probe("a_by_b", B, 1)],
592                },
593                relation_with_probes(B, 1, vec![probe("b_by_a", A, 1)]),
594            ],
595            predicates: vec![predicate(1, [A, B])],
596        };
597        let required = RequiredProperties {
598            distribution: Distribution::Single,
599            ordering: vec!["created_at".to_string()],
600            ..RequiredProperties::default()
601        };
602
603        let result = enumerate_relational_inner_joins(
604            &graph,
605            &required,
606            RelationalJoinEnumerationConfig::default(),
607        )
608        .unwrap();
609
610        assert_eq!(result.plan.binding_order(), [A, B]);
611        assert_eq!(result.plan.properties.ordering, ["created_at".to_string()]);
612    }
613
614    #[test]
615    fn base_only_access_paths_are_not_costed_as_inner_probes() {
616        let selective_base = RelationalJoinAccessPath::base(descriptor(
617            "a_constant_filter",
618            RelationalAccessPathKind::Index,
619            5,
620            false,
621        ));
622        let graph = RelationalJoinGraph {
623            relations: vec![
624                RelationalJoinRelation {
625                    binding: A,
626                    access_paths: vec![scan(100), selective_base, probe("a_by_b", B, 100)],
627                },
628                relation_with_probes(B, 1, Vec::new()),
629            ],
630            predicates: vec![predicate(1, [A, B])],
631        };
632
633        let result = enumerate_relational_inner_joins(
634            &graph,
635            &RequiredProperties::default(),
636            RelationalJoinEnumerationConfig::default(),
637        )
638        .unwrap();
639
640        assert_eq!(result.plan.binding_order(), [A, B]);
641        assert_eq!(
642            result.plan.base_access_path.descriptor.name,
643            "a_constant_filter"
644        );
645        assert_eq!(
646            result.plan.cost(),
647            PlanCost {
648                estimated_rows: 5,
649                cost: 67
650            }
651        );
652    }
653
654    #[test]
655    fn disconnected_graph_does_not_return_a_partial_enumeration() {
656        let graph = RelationalJoinGraph {
657            relations: vec![
658                relation_with_probes(A, 10, Vec::new()),
659                relation_with_probes(B, 10, Vec::new()),
660            ],
661            predicates: Vec::new(),
662        };
663
664        assert_eq!(
665            enumerate_relational_inner_joins(
666                &graph,
667                &RequiredProperties::default(),
668                RelationalJoinEnumerationConfig::default(),
669            ),
670            Err(RelationalJoinEnumerationError::Disconnected)
671        );
672    }
673
674    #[test]
675    fn access_dependencies_require_a_matching_join_predicate() {
676        let graph = RelationalJoinGraph {
677            relations: vec![
678                relation_with_probes(A, 10, vec![probe("a_by_b", B, 1)]),
679                relation_with_probes(B, 10, Vec::new()),
680                relation_with_probes(C, 10, Vec::new()),
681            ],
682            predicates: vec![predicate(1, [A, C])],
683        };
684
685        assert_eq!(
686            enumerate_relational_inner_joins(
687                &graph,
688                &RequiredProperties::default(),
689                RelationalJoinEnumerationConfig::default(),
690            ),
691            Err(RelationalJoinEnumerationError::AccessWithoutPredicate {
692                relation: A,
693                binding: B,
694            })
695        );
696    }
697
698    #[test]
699    fn group_budget_rejects_the_next_actual_connected_group() {
700        let graph = RelationalJoinGraph {
701            relations: vec![
702                relation_with_probes(A, 10, Vec::new()),
703                relation_with_probes(B, 10, Vec::new()),
704                relation_with_probes(C, 10, Vec::new()),
705            ],
706            predicates: vec![predicate(1, [A, B]), predicate(2, [B, C])],
707        };
708
709        assert_eq!(
710            enumerate_relational_inner_joins(
711                &graph,
712                &RequiredProperties::default(),
713                RelationalJoinEnumerationConfig {
714                    max_groups: 5,
715                    max_expressions: 100,
716                },
717            ),
718            Err(RelationalJoinEnumerationError::GroupBudgetExceeded {
719                required_groups: 6,
720                max_groups: 5,
721            })
722        );
723    }
724}
hawdb_optimizer/relational_join.rs

hawdb_optimizer/
relational_join.rs
