1use super::range_select_apply::{apply_select_wrappers, SelectWrapperState};
8use super::sparql_ast::{BindingRow, SparqlQueryContext, VariableId, MAX_VARIABLES};
9use super::sparql_executor::{
10 execute_range_nested_loop_join_page_into, execute_range_volume_set_nested_loop_join_page_into,
11 Q42RangeNestedLoopJoinPage, Q42RangeNestedLoopJoinPlan, Q42RangeNestedLoopJoinState,
12 Q42RangeVolumeSetNestedLoopJoinState,
13};
14use super::sparql_planner::{ExecutionPlan, PhysicalOperatorType};
15use crate::NQuin;
16
17#[derive(Clone, Copy, Debug, Eq, PartialEq)]
19pub struct Q42RangeJoinSelectPlan {
20 pub join: Q42RangeNestedLoopJoinPlan,
21 pub projection: [VariableId; MAX_VARIABLES],
22 pub projection_count: u8,
23 pub filters: [super::sparql_ast::ExpressionId; 8],
24 pub filter_count: u8,
25 pub limit: u64,
26 pub offset: u64,
27}
28
29#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
30pub struct Q42RangeJoinSelectState {
31 pub join: Q42RangeNestedLoopJoinState,
32 pub wrappers: SelectWrapperState,
33}
34
35#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
36pub struct Q42RangeVolumeSetJoinSelectState {
37 pub join: Q42RangeVolumeSetNestedLoopJoinState,
38 pub wrappers: SelectWrapperState,
39}
40
41impl Q42RangeJoinSelectPlan {
42 pub fn from_execution_plan(plan: &ExecutionPlan) -> Result<Self, String> {
44 if plan.operator_count == 0 || plan.root_operator as usize >= plan.operator_count as usize {
45 return Err("range join-select requires a non-empty execution plan".to_string());
46 }
47 let mut operator = plan.root_operator;
48 let mut projection = [0; MAX_VARIABLES];
49 let mut projection_count = 0;
50 let mut filters = [0; 8];
51 let mut filter_count = 0usize;
52 let mut limit = u64::MAX;
53 let mut offset = 0;
54 loop {
55 match plan.operators[operator as usize].operator_type {
56 PhysicalOperatorType::Project {
57 input,
58 vars,
59 var_count,
60 } => {
61 if projection_count != 0 {
62 return Err("range join-select does not support nested projections".into());
63 }
64 projection = vars;
65 projection_count = var_count;
66 operator = input;
67 }
68 PhysicalOperatorType::Limit {
69 input,
70 limit: configured,
71 offset: configured_offset,
72 } => {
73 if limit != u64::MAX || offset != 0 {
74 return Err("range join-select does not support nested limits".into());
75 }
76 limit = configured;
77 offset = configured_offset;
78 operator = input;
79 }
80 PhysicalOperatorType::Filter { input, expression } => {
81 if filter_count == filters.len() {
82 return Err(
83 "range join-select supports at most eight stacked FILTER operators"
84 .into(),
85 );
86 }
87 filters[filter_count] = expression;
88 filter_count += 1;
89 operator = input;
90 }
91 PhysicalOperatorType::NestedLoopJoin { .. } => {
92 return Ok(Self {
93 join: Q42RangeNestedLoopJoinPlan::from_join_root(plan, operator)?,
94 projection,
95 projection_count,
96 filters,
97 filter_count: filter_count as u8,
98 limit,
99 offset,
100 });
101 }
102 PhysicalOperatorType::HashJoin { .. } => {
103 return Err(
104 "range join-select does not yet execute HashJoin; planner must emit NestedLoopJoin"
105 .into(),
106 );
107 }
108 _ => {
109 return Err(
110 "range join-select supports Project/Filter/Limit over NestedLoopJoin(Scan, Scan)"
111 .into(),
112 );
113 }
114 }
115 }
116 }
117}
118
119pub fn execute_range_join_select_page_into<S: crate::q42_volume::Q42RangeSource>(
121 volume: &crate::q42_volume::Q42RangeVolume<S>,
122 plan: Q42RangeJoinSelectPlan,
123 ctx: &SparqlQueryContext,
124 state: &mut Q42RangeJoinSelectState,
125 compressed: &mut [u8],
126 decoded: &mut [u8],
127 quin_scratch: &mut [NQuin],
128 left_rows: &mut [BindingRow],
129 right_rows: &mut [BindingRow],
130 join_out: &mut [BindingRow],
131 out: &mut [BindingRow],
132) -> Result<Q42RangeNestedLoopJoinPage, String> {
133 let mut returned = 0usize;
134 loop {
135 if returned == out.len() {
136 return Ok(Q42RangeNestedLoopJoinPage {
137 returned,
138 done: false,
139 });
140 }
141 if state.wrappers.emitted >= plan.limit {
142 return Ok(Q42RangeNestedLoopJoinPage {
143 returned,
144 done: true,
145 });
146 }
147 let page = execute_range_nested_loop_join_page_into(
148 volume,
149 plan.join,
150 ctx,
151 &mut state.join,
152 compressed,
153 decoded,
154 quin_scratch,
155 left_rows,
156 right_rows,
157 join_out,
158 )?;
159 let applied = apply_select_wrappers(
160 ctx,
161 &plan.filters,
162 plan.filter_count,
163 plan.projection,
164 plan.projection_count,
165 plan.limit,
166 plan.offset,
167 &mut state.wrappers,
168 &join_out[..page.returned],
169 &mut out[returned..],
170 )?;
171 returned += applied.returned;
172 if page.done {
173 return Ok(Q42RangeNestedLoopJoinPage {
174 returned,
175 done: true,
176 });
177 }
178 if applied.limit_reached {
179 return Ok(Q42RangeNestedLoopJoinPage {
180 returned,
181 done: true,
182 });
183 }
184 if applied.returned == 0 && !page.done {
185 continue;
186 }
187 if returned > 0 {
188 return Ok(Q42RangeNestedLoopJoinPage {
189 returned,
190 done: false,
191 });
192 }
193 }
194}
195
196pub fn execute_range_volume_set_join_select_page_into<S: crate::q42_volume::Q42RangeSource>(
198 volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
199 plan: Q42RangeJoinSelectPlan,
200 ctx: &SparqlQueryContext,
201 state: &mut Q42RangeVolumeSetJoinSelectState,
202 compressed: &mut [u8],
203 decoded: &mut [u8],
204 quin_scratch: &mut [NQuin],
205 left_rows: &mut [BindingRow],
206 right_rows: &mut [BindingRow],
207 join_out: &mut [BindingRow],
208 out: &mut [BindingRow],
209) -> Result<Q42RangeNestedLoopJoinPage, String> {
210 let mut returned = 0usize;
211 loop {
212 if returned == out.len() {
213 return Ok(Q42RangeNestedLoopJoinPage {
214 returned,
215 done: false,
216 });
217 }
218 if state.wrappers.emitted >= plan.limit {
219 return Ok(Q42RangeNestedLoopJoinPage {
220 returned,
221 done: true,
222 });
223 }
224 let page = execute_range_volume_set_nested_loop_join_page_into(
225 volumes,
226 plan.join,
227 ctx,
228 &mut state.join,
229 compressed,
230 decoded,
231 quin_scratch,
232 left_rows,
233 right_rows,
234 join_out,
235 )?;
236 let applied = apply_select_wrappers(
237 ctx,
238 &plan.filters,
239 plan.filter_count,
240 plan.projection,
241 plan.projection_count,
242 plan.limit,
243 plan.offset,
244 &mut state.wrappers,
245 &join_out[..page.returned],
246 &mut out[returned..],
247 )?;
248 returned += applied.returned;
249 if page.done || applied.limit_reached {
250 return Ok(Q42RangeNestedLoopJoinPage {
251 returned,
252 done: true,
253 });
254 }
255 if applied.returned == 0 {
256 continue;
257 }
258 if returned > 0 {
259 return Ok(Q42RangeNestedLoopJoinPage {
260 returned,
261 done: false,
262 });
263 }
264 }
265}
266
267#[cfg(test)]
268mod tests {
269 use super::*;
270 use crate::q42_volume::{LocalFileRangeSource, Q42RangeVolume};
271 use crate::sparql_planner::{ExecutionPlan, PhysicalOperatorType};
272
273 #[test]
274 fn peels_project_filter_limit_from_a_join_tree() {
275 let mut plan = ExecutionPlan::new();
276 let left = plan
277 .add_operator(
278 PhysicalOperatorType::TripleScan {
279 subject: 10,
280 predicate: 20,
281 object: 0,
282 },
283 1,
284 )
285 .unwrap();
286 let right = plan
287 .add_operator(
288 PhysicalOperatorType::TripleScan {
289 subject: 0,
290 predicate: 40,
291 object: 50,
292 },
293 1,
294 )
295 .unwrap();
296 let join = plan
297 .add_operator(
298 PhysicalOperatorType::NestedLoopJoin {
299 left,
300 right,
301 join_var: 0,
302 },
303 1,
304 )
305 .unwrap();
306 let limited = plan
307 .add_operator(
308 PhysicalOperatorType::Limit {
309 input: join,
310 limit: 1,
311 offset: 0,
312 },
313 1,
314 )
315 .unwrap();
316 let projected = plan
317 .add_operator(
318 PhysicalOperatorType::Project {
319 input: limited,
320 vars: {
321 let mut vars = [0; MAX_VARIABLES];
322 vars[0] = 0;
323 vars
324 },
325 var_count: 1,
326 },
327 1,
328 )
329 .unwrap();
330 plan.root_operator = projected;
331 let compiled = Q42RangeJoinSelectPlan::from_execution_plan(&plan).unwrap();
332 assert_eq!(compiled.limit, 1);
333 assert_eq!(compiled.projection_count, 1);
334 assert_eq!(compiled.join.left.subject, 10);
335 assert_eq!(compiled.join.right.object, 50);
336 }
337
338 #[test]
339 fn limit_stops_after_one_join_row() {
340 let dir = tempfile::TempDir::new().unwrap();
341 let path = dir.path().join("join-select.q42");
342 let left = NQuin {
343 subject: 10,
344 predicate: 20,
345 object: 30,
346 context: 0,
347 metadata: 0,
348 parity: 0,
349 };
350 let right = NQuin {
351 subject: 30,
352 predicate: 40,
353 object: 50,
354 context: 0,
355 metadata: 0,
356 parity: 0,
357 };
358 crate::q42_volume::write_unified_volume(
359 &path,
360 &std::collections::HashMap::new(),
361 &[(left.object, right.object)],
362 &[vec![left, right]],
363 )
364 .unwrap();
365 let source = LocalFileRangeSource::open(&path).unwrap();
366 let volume = Q42RangeVolume::open(source).unwrap();
367 let mut context = SparqlQueryContext::new();
368 context.variable_count = 1;
369 let plan = Q42RangeJoinSelectPlan {
370 join: Q42RangeNestedLoopJoinPlan {
371 left: super::super::sparql_executor::Q42RangeTriplePattern {
372 subject: left.subject,
373 predicate: left.predicate,
374 object: 0,
375 },
376 right: super::super::sparql_executor::Q42RangeTriplePattern {
377 subject: 0,
378 predicate: right.predicate,
379 object: right.object,
380 },
381 },
382 projection: {
383 let mut vars = [0; MAX_VARIABLES];
384 vars[0] = 0;
385 vars
386 },
387 projection_count: 1,
388 filters: [0; 8],
389 filter_count: 0,
390 limit: 1,
391 offset: 0,
392 };
393 let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
394 let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
395 let mut quins = [NQuin::default(); 1];
396 let mut left_rows = [BindingRow::default(); 1];
397 let mut right_rows = [BindingRow::default(); 1];
398 let mut join_out = [BindingRow::default(); 1];
399 let mut out = [BindingRow::default(); 1];
400 let mut state = Q42RangeJoinSelectState::default();
401 let page = execute_range_join_select_page_into(
402 &volume,
403 plan,
404 &context,
405 &mut state,
406 &mut compressed,
407 &mut decoded,
408 &mut quins,
409 &mut left_rows,
410 &mut right_rows,
411 &mut join_out,
412 &mut out,
413 )
414 .unwrap();
415 assert_eq!(page.returned, 1);
416 assert!(page.done);
417 assert_eq!(out[0].get(0), Some(right.subject));
418 }
419}