1use uqa_sql::ast::JoinKind;
10use uqa_sql::ResultRow;
11
12use super::{output_schema, HybridRowStore, MatchFlags, SpillState, DEFAULT_JOIN_WORK_MEM_BYTES};
13
14mod iteration;
15use crate::{
16 Batch, ExecError, ExecResult, PhysicalOperator, PhysicalRow, RowSchema, ScalarExpr,
17 SharedExpressionEvaluator,
18};
19
20pub struct NestedLoopJoin<'a> {
25 left: Box<dyn PhysicalOperator + 'a>,
26 right: Box<dyn PhysicalOperator + 'a>,
27 kind: JoinKind,
28 predicate: Option<crate::scalar::PreparedExpressions<ScalarExpr>>,
29 evaluator: SharedExpressionEvaluator<'a>,
30 left_nulls: PhysicalRow,
31 right_nulls: PhysicalRow,
32 schema: RowSchema,
33 work_mem_bytes: usize,
34 output: Option<crate::spill::SpillDrain>,
35 left_pending: crate::physical::demand::PendingRows,
36 right_pending: crate::physical::demand::PendingRows,
37 right_rows: Option<HybridRowStore>,
38 matched_right: Option<MatchFlags>,
39 current_left: Option<PhysicalRow>,
40 right_position: u64,
41 unmatched_position: u64,
42 matched_left: bool,
43 left_finished: bool,
44 right_state: RightInputState,
45 output_spilled: SpillState,
46 right_input_spilled: SpillState,
47}
48
49#[derive(Clone, Copy, Eq, PartialEq)]
50enum RightInputState {
51 Unopened,
52 Open,
53 Exhausted,
54}
55
56impl<'a> NestedLoopJoin<'a> {
57 pub fn new(
58 left: Box<dyn PhysicalOperator + 'a>,
59 right: Box<dyn PhysicalOperator + 'a>,
60 kind: JoinKind,
61 predicate: Option<ScalarExpr>,
62 evaluator: SharedExpressionEvaluator<'a>,
63 left_nulls: ResultRow,
64 right_nulls: ResultRow,
65 ) -> Self {
66 Self::new_with_work_mem(
67 left,
68 right,
69 kind,
70 predicate,
71 evaluator,
72 left_nulls,
73 right_nulls,
74 DEFAULT_JOIN_WORK_MEM_BYTES,
75 )
76 }
77
78 #[expect(
79 clippy::too_many_arguments,
80 reason = "keeps join keys and schema aligned"
81 )]
82 pub fn new_with_work_mem(
83 left: Box<dyn PhysicalOperator + 'a>,
84 right: Box<dyn PhysicalOperator + 'a>,
85 kind: JoinKind,
86 predicate: Option<ScalarExpr>,
87 evaluator: SharedExpressionEvaluator<'a>,
88 left_nulls: ResultRow,
89 right_nulls: ResultRow,
90 work_mem_bytes: usize,
91 ) -> Self {
92 let left = super::presence::input(left, matches!(kind, JoinKind::Right | JoinKind::Full));
93 let right = super::presence::input(right, matches!(kind, JoinKind::Left | JoinKind::Full));
94 let schema = output_schema(
95 left.row_schema(),
96 right.row_schema(),
97 &left_nulls,
98 &right_nulls,
99 );
100 let left_nulls = PhysicalRow::nulls(left.row_schema().physical_width());
101 let right_nulls = PhysicalRow::nulls(right.row_schema().physical_width());
102 Self {
103 left,
104 right,
105 kind,
106 predicate: predicate.map(crate::scalar::PreparedExpressions::scalar),
107 evaluator,
108 left_nulls,
109 right_nulls,
110 schema,
111 work_mem_bytes,
112 output: None,
113 left_pending: crate::physical::demand::PendingRows::default(),
114 right_pending: crate::physical::demand::PendingRows::default(),
115 right_rows: None,
116 matched_right: None,
117 current_left: None,
118 right_position: 0,
119 unmatched_position: 0,
120 matched_left: false,
121 left_finished: false,
122 right_state: RightInputState::Unopened,
123 output_spilled: SpillState::InMemory,
124 right_input_spilled: SpillState::InMemory,
125 }
126 }
127
128 pub fn output_has_spilled(&self) -> bool {
129 self.output_spilled.is_spilled()
130 }
131
132 pub fn right_input_has_spilled(&self) -> bool {
135 self.right_input_spilled.is_spilled()
136 }
137}
138
139impl PhysicalOperator for NestedLoopJoin<'_> {
140 fn row_schema(&self) -> &RowSchema {
141 &self.schema
142 }
143
144 fn open(&mut self) -> ExecResult<()> {
145 self.output = None;
146 self.output_spilled = SpillState::InMemory;
147 self.right_input_spilled = SpillState::InMemory;
148 self.left_pending.clear();
149 self.right_pending.clear();
150 self.current_left = None;
151 self.right_position = 0;
152 self.unmatched_position = 0;
153 self.matched_left = false;
154 self.left_finished = false;
155 self.right_state = RightInputState::Unopened;
156 self.right_rows = Some(HybridRowStore::new(
157 self.right.row_schema().clone(),
158 self.work_mem_bytes / 2,
159 ));
160 self.matched_right = matches!(self.kind, JoinKind::Right | JoinKind::Full)
161 .then(|| MatchFlags::new(0, "join"))
162 .transpose()?;
163 self.left.open()
164 }
165
166 fn next(&mut self) -> ExecResult<Option<Batch>> {
167 self.pull(crate::batch::DEFAULT_BATCH_SIZE, false)
168 }
169
170 fn next_with_demand(&mut self, rows: std::num::NonZeroUsize) -> ExecResult<Option<Batch>> {
171 self.pull(rows.get().min(crate::batch::DEFAULT_BATCH_SIZE), true)
172 }
173
174 fn close(&mut self) -> ExecResult<()> {
175 self.output = None;
176 self.current_left = None;
177 self.right_rows = None;
178 self.matched_right = None;
179 self.left_pending.clear();
180 self.right_pending.clear();
181 let left = self.left.close();
182 let right = if self.right_state == RightInputState::Open {
183 self.right.close()
184 } else {
185 Ok(())
186 };
187 self.right_state = RightInputState::Exhausted;
188 crate::physical::with_cleanup(left, right, "close right nested-loop join input")
189 }
190}