1use super::range_select_apply::{apply_select_wrappers, SelectWrapperState};
8use super::sparql_ast::{BindingRow, ExpressionId, SparqlQueryContext, VariableId, MAX_VARIABLES};
9use super::sparql_executor::{
10 execute_range_triple_page_into, execute_range_volume_set_triple_page_into,
11 Q42RangeNestedLoopJoinPage, Q42RangeSparqlCursor, Q42RangeTriplePattern,
12 Q42RangeVolumeSetSparqlCursor,
13};
14use super::sparql_filter::{EvalResult, ExpressionEvaluator};
15use super::sparql_planner::{ExecutionPlan, PhysicalOperatorType};
16use crate::NQuin;
17
18#[derive(Clone, Copy, Debug, Eq, PartialEq)]
19pub struct Q42RangeBindPlan {
20 pub input: Q42RangeTriplePattern,
21 pub var: VariableId,
22 pub expression: ExpressionId,
23 pub projection: [VariableId; MAX_VARIABLES],
24 pub projection_count: u8,
25 pub filters: [ExpressionId; 8],
26 pub filter_count: u8,
27 pub limit: u64,
28 pub offset: u64,
29}
30
31#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
32pub struct Q42RangeBindState {
33 pub scan: Q42RangeSparqlCursor,
34 pub exhausted: bool,
35 pub wrappers: SelectWrapperState,
36}
37
38#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
39pub struct Q42RangeVolumeSetBindState {
40 pub scan: Q42RangeVolumeSetSparqlCursor,
41 pub exhausted: bool,
42 pub wrappers: SelectWrapperState,
43}
44
45impl Q42RangeBindPlan {
46 pub fn from_execution_plan(plan: &ExecutionPlan) -> Result<Self, String> {
48 if plan.operator_count == 0 || plan.root_operator as usize >= plan.operator_count as usize {
49 return Err("range BIND requires a non-empty execution plan".into());
50 }
51 let mut operator = plan.root_operator;
52 let mut projection = [0; MAX_VARIABLES];
53 let mut projection_count = 0;
54 let mut filters = [0; 8];
55 let mut filter_count = 0usize;
56 let mut limit = u64::MAX;
57 let mut offset = 0;
58 loop {
59 match plan.operators[operator as usize].operator_type {
60 PhysicalOperatorType::Project {
61 input,
62 vars,
63 var_count,
64 } => {
65 if projection_count != 0 {
66 return Err("range BIND does not support nested projections".into());
67 }
68 projection = vars;
69 projection_count = var_count;
70 operator = input;
71 }
72 PhysicalOperatorType::Limit {
73 input,
74 limit: configured,
75 offset: configured_offset,
76 } => {
77 if limit != u64::MAX || offset != 0 {
78 return Err("range BIND does not support nested limits".into());
79 }
80 limit = configured;
81 offset = configured_offset;
82 operator = input;
83 }
84 PhysicalOperatorType::Filter { input, expression } => {
85 if filter_count == filters.len() {
86 return Err(
87 "range BIND supports at most eight stacked FILTER operators".into()
88 );
89 }
90 filters[filter_count] = expression;
91 filter_count += 1;
92 operator = input;
93 }
94 PhysicalOperatorType::Bind {
95 input,
96 var,
97 expression,
98 } => {
99 return Ok(Self {
100 input: triple_scan(plan, input)?,
101 var,
102 expression,
103 projection,
104 projection_count,
105 filters,
106 filter_count: filter_count as u8,
107 limit,
108 offset,
109 });
110 }
111 _ => {
112 return Err(
113 "range BIND supports Project/Filter/Limit over Bind(TripleScan)".into(),
114 );
115 }
116 }
117 }
118 }
119}
120
121fn triple_scan(plan: &ExecutionPlan, operator: u16) -> Result<Q42RangeTriplePattern, String> {
122 let Some(entry) = plan.operators.get(operator as usize) else {
123 return Err("range BIND input operator is out of bounds".into());
124 };
125 match entry.operator_type {
126 PhysicalOperatorType::TripleScan {
127 subject,
128 predicate,
129 object,
130 } => Ok(Q42RangeTriplePattern {
131 subject,
132 predicate,
133 object,
134 }),
135 _ => Err("range BIND currently requires a TripleScan input".into()),
136 }
137}
138
139pub fn apply_bind(
141 ctx: &SparqlQueryContext,
142 var: VariableId,
143 expression: ExpressionId,
144 row: &mut BindingRow,
145) {
146 match ExpressionEvaluator::evaluate(expression, ctx, row) {
147 Ok(EvalResult::Numeric(n)) | Ok(EvalResult::Iri(n)) | Ok(EvalResult::String(n)) => {
148 row.set(var, n);
149 }
150 Ok(EvalResult::Boolean(b)) => row.set(var, b as u64),
151 Ok(EvalResult::Float(f)) => row.set(var, f.to_bits()),
152 Err(_) => {}
153 }
154}
155
156pub fn execute_range_bind_page_into<S: crate::q42_volume::Q42RangeSource>(
158 volume: &crate::q42_volume::Q42RangeVolume<S>,
159 plan: Q42RangeBindPlan,
160 ctx: &SparqlQueryContext,
161 state: &mut Q42RangeBindState,
162 compressed: &mut [u8],
163 decoded: &mut [u8],
164 quin_scratch: &mut [NQuin],
165 raw: &mut [BindingRow],
166 out: &mut [BindingRow],
167) -> Result<Q42RangeNestedLoopJoinPage, String> {
168 let mut returned = 0usize;
169 loop {
170 if returned == out.len() {
171 return Ok(Q42RangeNestedLoopJoinPage {
172 returned,
173 done: false,
174 });
175 }
176 if state.wrappers.emitted >= plan.limit || state.exhausted {
177 return Ok(Q42RangeNestedLoopJoinPage {
178 returned,
179 done: true,
180 });
181 }
182 let page = execute_range_triple_page_into(
183 volume,
184 plan.input.subject,
185 plan.input.predicate,
186 plan.input.object,
187 None,
188 ctx,
189 &BindingRow::default(),
190 state.scan,
191 compressed,
192 decoded,
193 quin_scratch,
194 raw,
195 )?;
196 state.scan = page.next_cursor.unwrap_or_default();
197 state.exhausted = page.next_cursor.is_none();
198 for row in &mut raw[..page.returned] {
199 apply_bind(ctx, plan.var, plan.expression, row);
200 }
201 let applied = apply_select_wrappers(
202 ctx,
203 &plan.filters,
204 plan.filter_count,
205 plan.projection,
206 plan.projection_count,
207 plan.limit,
208 plan.offset,
209 &mut state.wrappers,
210 &raw[..page.returned],
211 &mut out[returned..],
212 )?;
213 returned += applied.returned;
214 if state.exhausted || applied.limit_reached {
215 return Ok(Q42RangeNestedLoopJoinPage {
216 returned,
217 done: true,
218 });
219 }
220 if applied.returned == 0 {
221 continue;
222 }
223 if returned > 0 {
224 return Ok(Q42RangeNestedLoopJoinPage {
225 returned,
226 done: false,
227 });
228 }
229 }
230}
231
232pub fn execute_range_volume_set_bind_page_into<S: crate::q42_volume::Q42RangeSource>(
234 volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
235 plan: Q42RangeBindPlan,
236 ctx: &SparqlQueryContext,
237 state: &mut Q42RangeVolumeSetBindState,
238 compressed: &mut [u8],
239 decoded: &mut [u8],
240 quin_scratch: &mut [NQuin],
241 raw: &mut [BindingRow],
242 out: &mut [BindingRow],
243) -> Result<Q42RangeNestedLoopJoinPage, String> {
244 let mut returned = 0usize;
245 loop {
246 if returned == out.len() {
247 return Ok(Q42RangeNestedLoopJoinPage {
248 returned,
249 done: false,
250 });
251 }
252 if state.wrappers.emitted >= plan.limit || state.exhausted {
253 return Ok(Q42RangeNestedLoopJoinPage {
254 returned,
255 done: true,
256 });
257 }
258 let page = execute_range_volume_set_triple_page_into(
259 volumes,
260 plan.input.subject,
261 plan.input.predicate,
262 plan.input.object,
263 None,
264 ctx,
265 &BindingRow::default(),
266 state.scan,
267 compressed,
268 decoded,
269 quin_scratch,
270 raw,
271 )?;
272 state.scan = page.next_cursor.unwrap_or_default();
273 state.exhausted = page.next_cursor.is_none();
274 for row in &mut raw[..page.returned] {
275 apply_bind(ctx, plan.var, plan.expression, row);
276 }
277 let applied = apply_select_wrappers(
278 ctx,
279 &plan.filters,
280 plan.filter_count,
281 plan.projection,
282 plan.projection_count,
283 plan.limit,
284 plan.offset,
285 &mut state.wrappers,
286 &raw[..page.returned],
287 &mut out[returned..],
288 )?;
289 returned += applied.returned;
290 if state.exhausted || applied.limit_reached {
291 return Ok(Q42RangeNestedLoopJoinPage {
292 returned,
293 done: true,
294 });
295 }
296 if applied.returned == 0 {
297 continue;
298 }
299 if returned > 0 {
300 return Ok(Q42RangeNestedLoopJoinPage {
301 returned,
302 done: false,
303 });
304 }
305 }
306}
307
308#[cfg(test)]
309mod tests {
310 use super::*;
311 use crate::q42_volume::{write_unified_volume, LocalFileRangeSource, Q42RangeVolume};
312 use crate::sparql_ast::Expression;
313
314 fn quin(s: u64, p: u64, o: u64) -> NQuin {
315 NQuin {
316 subject: s,
317 predicate: p,
318 object: o,
319 context: 0,
320 metadata: 0,
321 parity: 0,
322 }
323 }
324
325 fn test_volume(quins: &[NQuin]) -> (tempfile::TempDir, Q42RangeVolume<LocalFileRangeSource>) {
326 let dir = tempfile::TempDir::new().unwrap();
327 let path = dir.path().join("bind.q42");
328 let lo = quins.iter().map(|q| q.object).min().unwrap_or(0);
329 let hi = quins.iter().map(|q| q.object).max().unwrap_or(0);
330 write_unified_volume(
331 &path,
332 &std::collections::HashMap::new(),
333 &[(lo, hi)],
334 &[quins.to_vec()],
335 )
336 .unwrap();
337 let source = LocalFileRangeSource::open(&path).unwrap();
338 (dir, Q42RangeVolume::open(source).unwrap())
339 }
340
341 #[test]
342 fn peels_project_from_bind_tree() {
343 let mut plan = ExecutionPlan::new();
344 let scan = plan
345 .add_operator(
346 PhysicalOperatorType::TripleScan {
347 subject: 0,
348 predicate: 20,
349 object: 1,
350 },
351 1,
352 )
353 .unwrap();
354 let bind = plan
355 .add_operator(
356 PhysicalOperatorType::Bind {
357 input: scan,
358 var: 2,
359 expression: 0,
360 },
361 1,
362 )
363 .unwrap();
364 let mut vars = [0; MAX_VARIABLES];
365 vars[0] = 2;
366 plan.root_operator = plan
367 .add_operator(
368 PhysicalOperatorType::Project {
369 input: bind,
370 vars,
371 var_count: 1,
372 },
373 1,
374 )
375 .unwrap();
376 let compiled = Q42RangeBindPlan::from_execution_plan(&plan).unwrap();
377 assert_eq!(compiled.var, 2);
378 assert_eq!(compiled.input.predicate, 20);
379 assert_eq!(compiled.projection_count, 1);
380 }
381
382 #[test]
383 fn bind_literal_extends_every_row() {
384 let row = quin(10, 20, 30);
385 let (_dir, volume) = test_volume(&[row]);
386 let mut ctx = SparqlQueryContext::new();
387 ctx.variable_count = 3;
388 let expr = ctx.alloc_expression(Expression::Literal(42)).unwrap();
389 let plan = Q42RangeBindPlan {
390 input: Q42RangeTriplePattern {
391 subject: 0,
392 predicate: 20,
393 object: 1,
394 },
395 var: 2,
396 expression: expr,
397 projection: [0; MAX_VARIABLES],
398 projection_count: 0,
399 filters: [0; 8],
400 filter_count: 0,
401 limit: u64::MAX,
402 offset: 0,
403 };
404 let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
405 let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
406 let mut quins = [NQuin::default(); 2];
407 let mut raw = [BindingRow::default(); 2];
408 let mut out = [BindingRow::default(); 2];
409 let mut state = Q42RangeBindState::default();
410 let page = execute_range_bind_page_into(
411 &volume,
412 plan,
413 &ctx,
414 &mut state,
415 &mut compressed,
416 &mut decoded,
417 &mut quins,
418 &mut raw,
419 &mut out,
420 )
421 .unwrap();
422 assert!(page.done);
423 assert_eq!(page.returned, 1);
424 assert_eq!(out[0].get(0), Some(10));
425 assert_eq!(out[0].get(1), Some(30));
426 assert_eq!(out[0].get(2), Some(42));
427 }
428
429 #[test]
430 fn bind_error_leaves_variable_unbound() {
431 let row = quin(10, 20, 30);
432 let (_dir, volume) = test_volume(&[row]);
433 let mut ctx = SparqlQueryContext::new();
434 ctx.variable_count = 3;
435 let plan = Q42RangeBindPlan {
436 input: Q42RangeTriplePattern {
437 subject: 0,
438 predicate: 20,
439 object: 1,
440 },
441 var: 2,
442 expression: 200,
443 projection: [0; MAX_VARIABLES],
444 projection_count: 0,
445 filters: [0; 8],
446 filter_count: 0,
447 limit: u64::MAX,
448 offset: 0,
449 };
450 let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
451 let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
452 let mut quins = [NQuin::default(); 2];
453 let mut raw = [BindingRow::default(); 2];
454 let mut out = [BindingRow::default(); 2];
455 let mut state = Q42RangeBindState::default();
456 let page = execute_range_bind_page_into(
457 &volume,
458 plan,
459 &ctx,
460 &mut state,
461 &mut compressed,
462 &mut decoded,
463 &mut quins,
464 &mut raw,
465 &mut out,
466 )
467 .unwrap();
468 assert_eq!(page.returned, 1);
469 assert_eq!(out[0].get(0), Some(10));
470 assert_eq!(out[0].get(2), None);
471 }
472}