Skip to main content

qualia_core_db/sparql_library/
range_hash_join.rs

1//! Bounded range HashJoin. The smaller TripleScan is hashed into a
2//! caller-capped table; the larger side probes it. If the build side would
3//! exceed the table, the operator fails closed so the planner can keep
4//! NestedLoopJoin. No unbounded allocation.
5
6use super::range_join_select::Q42RangeJoinSelectPlan;
7use super::range_select_apply::{apply_select_wrappers, SelectWrapperState};
8use super::sparql_ast::{
9    BindingRow, ExpressionId, SparqlQueryContext, VariableId, MAX_BINDINGS, MAX_VARIABLES,
10};
11use super::sparql_executor::{
12    execute_range_triple_page_into, execute_range_volume_set_triple_page_into,
13    Q42RangeNestedLoopJoinPage, Q42RangeNestedLoopJoinPlan, Q42RangeSparqlCursor,
14    Q42RangeTriplePattern, Q42RangeVolumeSetSparqlCursor,
15};
16use super::sparql_planner::{ExecutionPlan, PhysicalOperatorType};
17use crate::NQuin;
18
19#[derive(Clone, Copy, Debug, Eq, PartialEq)]
20pub struct Q42RangeHashJoinSlot {
21    pub key: u64,
22    pub row: BindingRow,
23    pub occupied: bool,
24}
25
26impl Default for Q42RangeHashJoinSlot {
27    fn default() -> Self {
28        Self {
29            key: 0,
30            row: BindingRow::default(),
31            occupied: false,
32        }
33    }
34}
35
36#[derive(Clone, Copy, Debug, Eq, PartialEq)]
37pub struct Q42RangeHashJoinPlan {
38    pub left: Q42RangeTriplePattern,
39    pub right: Q42RangeTriplePattern,
40    pub join_var: VariableId,
41    pub projection: [VariableId; MAX_VARIABLES],
42    pub projection_count: u8,
43    pub filters: [ExpressionId; 8],
44    pub filter_count: u8,
45    pub limit: u64,
46    pub offset: u64,
47}
48
49impl Q42RangeHashJoinPlan {
50    /// Narrows to a join-select view.
51    pub fn as_join_select(&self) -> Q42RangeJoinSelectPlan {
52        Q42RangeJoinSelectPlan {
53            join: Q42RangeNestedLoopJoinPlan {
54                left: self.left,
55                right: self.right,
56            },
57            projection: self.projection,
58            projection_count: self.projection_count,
59            filters: self.filters,
60            filter_count: self.filter_count,
61            limit: self.limit,
62            offset: self.offset,
63        }
64    }
65
66    /// Lowers an `ExecutionPlan` into a hash-join plan.
67    pub fn from_execution_plan(plan: &ExecutionPlan) -> Result<Self, String> {
68        if plan.operator_count == 0 || plan.root_operator as usize >= plan.operator_count as usize {
69            return Err("range HashJoin requires a non-empty execution plan".into());
70        }
71        let mut operator = plan.root_operator;
72        let mut projection = [0; MAX_VARIABLES];
73        let mut projection_count = 0;
74        let mut filters = [0; 8];
75        let mut filter_count = 0usize;
76        let mut limit = u64::MAX;
77        let mut offset = 0;
78        loop {
79            match plan.operators[operator as usize].operator_type {
80                PhysicalOperatorType::Project {
81                    input,
82                    vars,
83                    var_count,
84                } => {
85                    if projection_count != 0 {
86                        return Err("range HashJoin does not support nested projections".into());
87                    }
88                    projection = vars;
89                    projection_count = var_count;
90                    operator = input;
91                }
92                PhysicalOperatorType::Limit {
93                    input,
94                    limit: configured,
95                    offset: configured_offset,
96                } => {
97                    if limit != u64::MAX || offset != 0 {
98                        return Err("range HashJoin does not support nested limits".into());
99                    }
100                    limit = configured;
101                    offset = configured_offset;
102                    operator = input;
103                }
104                PhysicalOperatorType::Filter { input, expression } => {
105                    if filter_count == filters.len() {
106                        return Err(
107                            "range HashJoin supports at most eight stacked FILTER operators".into(),
108                        );
109                    }
110                    filters[filter_count] = expression;
111                    filter_count += 1;
112                    operator = input;
113                }
114                PhysicalOperatorType::HashJoin {
115                    left,
116                    right,
117                    join_var,
118                }
119                | PhysicalOperatorType::NestedLoopJoin {
120                    left,
121                    right,
122                    join_var,
123                } => {
124                    return Ok(Self {
125                        left: triple_scan(plan, left)?,
126                        right: triple_scan(plan, right)?,
127                        join_var,
128                        projection,
129                        projection_count,
130                        filters,
131                        filter_count: filter_count as u8,
132                        limit,
133                        offset,
134                    });
135                }
136                _ => {
137                    return Err(
138                        "range HashJoin supports Project/Filter/Limit over HashJoin or NestedLoopJoin(TripleScan, TripleScan)"
139                            .into(),
140                    );
141                }
142            }
143        }
144    }
145}
146
147#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
148pub struct Q42RangeHashJoinState {
149    pub built: bool,
150    pub build_is_right: bool,
151    pub probe_scan: Q42RangeSparqlCursor,
152    pub probe_count: usize,
153    pub probe_index: usize,
154    pub probe_exhausted: bool,
155    pub match_offset: usize,
156    pub wrappers: SelectWrapperState,
157}
158
159#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
160pub struct Q42RangeVolumeSetHashJoinState {
161    pub built: bool,
162    pub build_is_right: bool,
163    pub probe_scan: Q42RangeVolumeSetSparqlCursor,
164    pub probe_count: usize,
165    pub probe_index: usize,
166    pub probe_exhausted: bool,
167    pub match_offset: usize,
168    pub wrappers: SelectWrapperState,
169}
170
171fn triple_scan(plan: &ExecutionPlan, operator: u16) -> Result<Q42RangeTriplePattern, String> {
172    let Some(entry) = plan.operators.get(operator as usize) else {
173        return Err("range HashJoin input operator is out of bounds".into());
174    };
175    match entry.operator_type {
176        PhysicalOperatorType::TripleScan {
177            subject,
178            predicate,
179            object,
180        } => Ok(Q42RangeTriplePattern {
181            subject,
182            predicate,
183            object,
184        }),
185        _ => Err("range HashJoin currently requires TripleScan inputs".into()),
186    }
187}
188
189fn cap_error(count: usize, cap: usize) -> String {
190    format!(
191        "range HashJoin build side ({count} rows) exceeds caller cap ({cap}); planner must keep NestedLoopJoin"
192    )
193}
194
195fn term_var(term: u64, ctx: &SparqlQueryContext) -> Option<VariableId> {
196    if (term as usize) < ctx.variable_count {
197        Some(term as VariableId)
198    } else {
199        None
200    }
201}
202
203fn pattern_vars(pattern: Q42RangeTriplePattern, ctx: &SparqlQueryContext) -> ([VariableId; 3], u8) {
204    let mut vars = [0; 3];
205    let mut count = 0u8;
206    for term in [pattern.subject, pattern.predicate, pattern.object] {
207        if let Some(var) = term_var(term, ctx) {
208            if !vars[..count as usize].contains(&var) {
209                vars[count as usize] = var;
210                count += 1;
211            }
212        }
213    }
214    (vars, count)
215}
216
217fn shared_join_vars(
218    left: Q42RangeTriplePattern,
219    right: Q42RangeTriplePattern,
220    ctx: &SparqlQueryContext,
221    join_var: VariableId,
222) -> ([VariableId; 3], u8) {
223    let (left_vars, left_n) = pattern_vars(left, ctx);
224    let (right_vars, right_n) = pattern_vars(right, ctx);
225    let mut shared = [0; 3];
226    let mut count = 0u8;
227    let left_slice = &left_vars[..left_n as usize];
228    let right_slice = &right_vars[..right_n as usize];
229    if left_slice.contains(&join_var) && right_slice.contains(&join_var) {
230        shared[0] = join_var;
231        count = 1;
232    }
233    for var in left_slice {
234        if right_slice.contains(var) && !shared[..count as usize].contains(var) && count < 3 {
235            shared[count as usize] = *var;
236            count += 1;
237        }
238    }
239    (shared, count)
240}
241
242fn join_key(row: &BindingRow, vars: &[VariableId]) -> u64 {
243    for var in vars {
244        if let Some(value) = row.get(*var) {
245            return value;
246        }
247    }
248    0
249}
250
251fn rows_compatible(left: &BindingRow, right: &BindingRow) -> bool {
252    for slot in 0..MAX_BINDINGS {
253        if let (Some(a), Some(b)) = (left.slots[slot], right.slots[slot]) {
254            if a != b {
255                return false;
256            }
257        }
258    }
259    true
260}
261
262fn merge_rows(left: &BindingRow, right: &BindingRow) -> BindingRow {
263    let mut joined = BindingRow::new();
264    for slot in 0..MAX_BINDINGS {
265        joined.slots[slot] = left.slots[slot].or(right.slots[slot]);
266    }
267    joined
268}
269
270fn insert_slot(
271    table: &mut [Q42RangeHashJoinSlot],
272    key: u64,
273    row: BindingRow,
274) -> Result<(), String> {
275    if table.is_empty() {
276        return Err(cap_error(1, 0));
277    }
278    let cap = table.len();
279    let start = (key as usize) % cap;
280    for step in 0..cap {
281        let slot = &mut table[(start + step) % cap];
282        if !slot.occupied {
283            slot.occupied = true;
284            slot.key = key;
285            slot.row = row;
286            return Ok(());
287        }
288    }
289    Err(cap_error(cap + 1, cap))
290}
291
292fn count_side<C, F>(
293    mut page_fn: F,
294    pattern: Q42RangeTriplePattern,
295    scratch: &mut [BindingRow],
296) -> Result<usize, String>
297where
298    C: Copy + Default,
299    F: FnMut(Q42RangeTriplePattern, C, &mut [BindingRow]) -> Result<(usize, Option<C>), String>,
300{
301    let mut cursor = C::default();
302    let mut total = 0usize;
303    loop {
304        let (count, next) = page_fn(pattern, cursor, scratch)?;
305        total = total.saturating_add(count);
306        match next {
307            Some(next_cursor) => cursor = next_cursor,
308            None => return Ok(total),
309        }
310    }
311}
312
313fn build_side<C, F>(
314    mut page_fn: F,
315    pattern: Q42RangeTriplePattern,
316    key_vars: &[VariableId],
317    table: &mut [Q42RangeHashJoinSlot],
318    scratch: &mut [BindingRow],
319) -> Result<usize, String>
320where
321    C: Copy + Default,
322    F: FnMut(Q42RangeTriplePattern, C, &mut [BindingRow]) -> Result<(usize, Option<C>), String>,
323{
324    let mut cursor = C::default();
325    let mut inserted = 0usize;
326    loop {
327        let (count, next) = page_fn(pattern, cursor, scratch)?;
328        for row in &scratch[..count] {
329            insert_slot(table, join_key(row, key_vars), *row)?;
330            inserted += 1;
331        }
332        match next {
333            Some(next_cursor) => cursor = next_cursor,
334            None => return Ok(inserted),
335        }
336    }
337}
338
339fn emit_matches(
340    table: &[Q42RangeHashJoinSlot],
341    probe: &BindingRow,
342    key_vars: &[VariableId],
343    match_offset: &mut usize,
344    out: &mut [BindingRow],
345) -> usize {
346    if table.is_empty() {
347        *match_offset = 0;
348        return 0;
349    }
350    let key = join_key(probe, key_vars);
351    let cap = table.len();
352    let start = (key as usize) % cap;
353    let mut returned = 0usize;
354    while *match_offset < cap && returned < out.len() {
355        let slot = &table[(start + *match_offset) % cap];
356        *match_offset += 1;
357        if !slot.occupied {
358            *match_offset = cap;
359            break;
360        }
361        if slot.key != key || !rows_compatible(probe, &slot.row) {
362            continue;
363        }
364        out[returned] = merge_rows(probe, &slot.row);
365        returned += 1;
366    }
367    returned
368}
369
370fn emit_matches_accel(
371    table: &[Q42RangeHashJoinSlot],
372    probes: &[BindingRow],
373    key_vars: &[VariableId],
374    out: &mut [BindingRow],
375) -> usize {
376    let mut build_keys = Vec::new();
377    let mut build_rows = Vec::new();
378    for slot in table {
379        if slot.occupied {
380            build_keys.push(slot.key);
381            build_rows.push(slot.row);
382        }
383    }
384    let probe_keys: Vec<u64> = probes.iter().map(|r| join_key(r, key_vars)).collect();
385    let mut pairs = vec![(0u32, 0u32); out.len()];
386    let joined = crate::query::graph_accel::hash_join_u64(&build_keys, &probe_keys, &mut pairs);
387    let mut n = 0usize;
388    for &(pi, bi) in &pairs[..joined.written] {
389        if n >= out.len() {
390            break;
391        }
392        let probe = &probes[pi as usize];
393        let built = &build_rows[bi as usize];
394        if !rows_compatible(probe, built) {
395            continue;
396        }
397        out[n] = merge_rows(probe, built);
398        n += 1;
399    }
400    n
401}
402
403/// Executes hash join into a caller page buffer on `S`.
404pub fn execute_range_hash_join_page_into<S: crate::q42_volume::Q42RangeSource>(
405    volume: &crate::q42_volume::Q42RangeVolume<S>,
406    plan: Q42RangeHashJoinPlan,
407    ctx: &SparqlQueryContext,
408    state: &mut Q42RangeHashJoinState,
409    table: &mut [Q42RangeHashJoinSlot],
410    compressed: &mut [u8],
411    decoded: &mut [u8],
412    quin_scratch: &mut [NQuin],
413    probe_rows: &mut [BindingRow],
414    join_out: &mut [BindingRow],
415    out: &mut [BindingRow],
416) -> Result<Q42RangeNestedLoopJoinPage, String> {
417    let mut page_fn =
418        |pattern: Q42RangeTriplePattern, cursor: Q42RangeSparqlCursor, rows: &mut [BindingRow]| {
419            execute_range_triple_page_into(
420                volume,
421                pattern.subject,
422                pattern.predicate,
423                pattern.object,
424                None,
425                ctx,
426                &BindingRow::default(),
427                cursor,
428                compressed,
429                decoded,
430                quin_scratch,
431                rows,
432            )
433            .map(|page| (page.returned, page.next_cursor))
434        };
435    if !state.built {
436        let left_n = count_side(&mut page_fn, plan.left, probe_rows)?;
437        let right_n = count_side(&mut page_fn, plan.right, probe_rows)?;
438        let build_is_right = right_n <= left_n;
439        let build_n = if build_is_right { right_n } else { left_n };
440        if build_n > table.len() {
441            return Err(cap_error(build_n, table.len()));
442        }
443        let build_pattern = if build_is_right {
444            plan.right
445        } else {
446            plan.left
447        };
448        let (key_vars, key_n) = shared_join_vars(plan.left, plan.right, ctx, plan.join_var);
449        build_side(
450            &mut page_fn,
451            build_pattern,
452            &key_vars[..key_n as usize],
453            table,
454            probe_rows,
455        )?;
456        state.built = true;
457        state.build_is_right = build_is_right;
458        state.probe_scan = Q42RangeSparqlCursor::default();
459        state.probe_exhausted = false;
460        state.probe_count = 0;
461        state.probe_index = 0;
462        state.match_offset = 0;
463    }
464    let probe_pattern = if state.build_is_right {
465        plan.left
466    } else {
467        plan.right
468    };
469    let mut returned = 0usize;
470    loop {
471        if returned == out.len() {
472            return Ok(Q42RangeNestedLoopJoinPage {
473                returned,
474                done: false,
475            });
476        }
477        if state.wrappers.emitted >= plan.limit {
478            return Ok(Q42RangeNestedLoopJoinPage {
479                returned,
480                done: true,
481            });
482        }
483        if state.probe_index >= state.probe_count {
484            if state.probe_exhausted {
485                return Ok(Q42RangeNestedLoopJoinPage {
486                    returned,
487                    done: true,
488                });
489            }
490            let (count, next) = page_fn(probe_pattern, state.probe_scan, probe_rows)?;
491            state.probe_count = count;
492            state.probe_index = 0;
493            state.match_offset = 0;
494            state.probe_scan = next.unwrap_or_default();
495            state.probe_exhausted = next.is_none();
496            if state.probe_count == 0 {
497                if state.probe_exhausted {
498                    return Ok(Q42RangeNestedLoopJoinPage {
499                        returned,
500                        done: true,
501                    });
502                }
503                continue;
504            }
505        }
506        let (key_vars, key_n) = shared_join_vars(plan.left, plan.right, ctx, plan.join_var);
507        if state.probe_index == 0
508            && state.match_offset == 0
509            && state.probe_count >= 32
510            && table.iter().filter(|s| s.occupied).count() >= 32
511        {
512            let produced = emit_matches_accel(
513                table,
514                &probe_rows[..state.probe_count],
515                &key_vars[..key_n as usize],
516                join_out,
517            );
518            state.probe_index = state.probe_count;
519            let applied = apply_select_wrappers(
520                ctx,
521                &plan.filters,
522                plan.filter_count,
523                plan.projection,
524                plan.projection_count,
525                plan.limit,
526                plan.offset,
527                &mut state.wrappers,
528                &join_out[..produced],
529                &mut out[returned..],
530            )?;
531            returned += applied.returned;
532            if applied.limit_reached || returned == out.len() {
533                return Ok(Q42RangeNestedLoopJoinPage {
534                    returned,
535                    done: applied.limit_reached,
536                });
537            }
538            continue;
539        }
540        let probe = probe_rows[state.probe_index];
541        let produced = emit_matches(
542            table,
543            &probe,
544            &key_vars[..key_n as usize],
545            &mut state.match_offset,
546            join_out,
547        );
548        let applied = apply_select_wrappers(
549            ctx,
550            &plan.filters,
551            plan.filter_count,
552            plan.projection,
553            plan.projection_count,
554            plan.limit,
555            plan.offset,
556            &mut state.wrappers,
557            &join_out[..produced],
558            &mut out[returned..],
559        )?;
560        returned += applied.returned;
561        if state.match_offset >= table.len() || table.is_empty() {
562            state.probe_index += 1;
563            state.match_offset = 0;
564        }
565        if applied.limit_reached {
566            return Ok(Q42RangeNestedLoopJoinPage {
567                returned,
568                done: true,
569            });
570        }
571        if returned == out.len() {
572            return Ok(Q42RangeNestedLoopJoinPage {
573                returned,
574                done: false,
575            });
576        }
577    }
578}
579
580/// Executes hash join across a volume set.
581pub fn execute_range_volume_set_hash_join_page_into<S: crate::q42_volume::Q42RangeSource>(
582    volumes: &crate::q42_volume::Q42RangeVolumeSet<S>,
583    plan: Q42RangeHashJoinPlan,
584    ctx: &SparqlQueryContext,
585    state: &mut Q42RangeVolumeSetHashJoinState,
586    table: &mut [Q42RangeHashJoinSlot],
587    compressed: &mut [u8],
588    decoded: &mut [u8],
589    quin_scratch: &mut [NQuin],
590    probe_rows: &mut [BindingRow],
591    join_out: &mut [BindingRow],
592    out: &mut [BindingRow],
593) -> Result<Q42RangeNestedLoopJoinPage, String> {
594    let mut page_fn = |pattern: Q42RangeTriplePattern,
595                       cursor: Q42RangeVolumeSetSparqlCursor,
596                       rows: &mut [BindingRow]| {
597        execute_range_volume_set_triple_page_into(
598            volumes,
599            pattern.subject,
600            pattern.predicate,
601            pattern.object,
602            None,
603            ctx,
604            &BindingRow::default(),
605            cursor,
606            compressed,
607            decoded,
608            quin_scratch,
609            rows,
610        )
611        .map(|page| (page.returned, page.next_cursor))
612    };
613    if !state.built {
614        let left_n = count_side(&mut page_fn, plan.left, probe_rows)?;
615        let right_n = count_side(&mut page_fn, plan.right, probe_rows)?;
616        let build_is_right = right_n <= left_n;
617        let build_n = if build_is_right { right_n } else { left_n };
618        if build_n > table.len() {
619            return Err(cap_error(build_n, table.len()));
620        }
621        let build_pattern = if build_is_right {
622            plan.right
623        } else {
624            plan.left
625        };
626        let (key_vars, key_n) = shared_join_vars(plan.left, plan.right, ctx, plan.join_var);
627        build_side(
628            &mut page_fn,
629            build_pattern,
630            &key_vars[..key_n as usize],
631            table,
632            probe_rows,
633        )?;
634        state.built = true;
635        state.build_is_right = build_is_right;
636        state.probe_scan = Q42RangeVolumeSetSparqlCursor::default();
637        state.probe_exhausted = false;
638        state.probe_count = 0;
639        state.probe_index = 0;
640        state.match_offset = 0;
641    }
642    let probe_pattern = if state.build_is_right {
643        plan.left
644    } else {
645        plan.right
646    };
647    let mut returned = 0usize;
648    loop {
649        if returned == out.len() {
650            return Ok(Q42RangeNestedLoopJoinPage {
651                returned,
652                done: false,
653            });
654        }
655        if state.wrappers.emitted >= plan.limit {
656            return Ok(Q42RangeNestedLoopJoinPage {
657                returned,
658                done: true,
659            });
660        }
661        if state.probe_index >= state.probe_count {
662            if state.probe_exhausted {
663                return Ok(Q42RangeNestedLoopJoinPage {
664                    returned,
665                    done: true,
666                });
667            }
668            let (count, next) = page_fn(probe_pattern, state.probe_scan, probe_rows)?;
669            state.probe_count = count;
670            state.probe_index = 0;
671            state.match_offset = 0;
672            state.probe_scan = next.unwrap_or_default();
673            state.probe_exhausted = next.is_none();
674            if state.probe_count == 0 {
675                if state.probe_exhausted {
676                    return Ok(Q42RangeNestedLoopJoinPage {
677                        returned,
678                        done: true,
679                    });
680                }
681                continue;
682            }
683        }
684        let (key_vars, key_n) = shared_join_vars(plan.left, plan.right, ctx, plan.join_var);
685        if state.probe_index == 0
686            && state.match_offset == 0
687            && state.probe_count >= 32
688            && table.iter().filter(|s| s.occupied).count() >= 32
689        {
690            let produced = emit_matches_accel(
691                table,
692                &probe_rows[..state.probe_count],
693                &key_vars[..key_n as usize],
694                join_out,
695            );
696            state.probe_index = state.probe_count;
697            let applied = apply_select_wrappers(
698                ctx,
699                &plan.filters,
700                plan.filter_count,
701                plan.projection,
702                plan.projection_count,
703                plan.limit,
704                plan.offset,
705                &mut state.wrappers,
706                &join_out[..produced],
707                &mut out[returned..],
708            )?;
709            returned += applied.returned;
710            if applied.limit_reached || returned == out.len() {
711                return Ok(Q42RangeNestedLoopJoinPage {
712                    returned,
713                    done: applied.limit_reached,
714                });
715            }
716            continue;
717        }
718        let probe = probe_rows[state.probe_index];
719        let produced = emit_matches(
720            table,
721            &probe,
722            &key_vars[..key_n as usize],
723            &mut state.match_offset,
724            join_out,
725        );
726        let applied = apply_select_wrappers(
727            ctx,
728            &plan.filters,
729            plan.filter_count,
730            plan.projection,
731            plan.projection_count,
732            plan.limit,
733            plan.offset,
734            &mut state.wrappers,
735            &join_out[..produced],
736            &mut out[returned..],
737        )?;
738        returned += applied.returned;
739        if state.match_offset >= table.len() || table.is_empty() {
740            state.probe_index += 1;
741            state.match_offset = 0;
742        }
743        if applied.limit_reached {
744            return Ok(Q42RangeNestedLoopJoinPage {
745                returned,
746                done: true,
747            });
748        }
749        if returned == out.len() {
750            return Ok(Q42RangeNestedLoopJoinPage {
751                returned,
752                done: false,
753            });
754        }
755    }
756}
757
758#[cfg(test)]
759mod tests {
760    use super::*;
761    use crate::q42_volume::{write_unified_volume, LocalFileRangeSource, Q42RangeVolume};
762
763    fn quin(s: u64, p: u64, o: u64) -> NQuin {
764        NQuin {
765            subject: s,
766            predicate: p,
767            object: o,
768            context: 0,
769            metadata: 0,
770            parity: 0,
771        }
772    }
773
774    fn test_volume(quins: &[NQuin]) -> (tempfile::TempDir, Q42RangeVolume<LocalFileRangeSource>) {
775        let dir = tempfile::TempDir::new().unwrap();
776        let path = dir.path().join("hash-join.q42");
777        let lo = quins.iter().map(|q| q.object).min().unwrap_or(0);
778        let hi = quins.iter().map(|q| q.object).max().unwrap_or(0);
779        write_unified_volume(
780            &path,
781            &std::collections::HashMap::new(),
782            &[(lo, hi)],
783            &[quins.to_vec()],
784        )
785        .unwrap();
786        let source = LocalFileRangeSource::open(&path).unwrap();
787        (dir, Q42RangeVolume::open(source).unwrap())
788    }
789
790    fn join_plan() -> Q42RangeHashJoinPlan {
791        Q42RangeHashJoinPlan {
792            left: Q42RangeTriplePattern {
793                subject: 0,
794                predicate: 20,
795                object: 1,
796            },
797            right: Q42RangeTriplePattern {
798                subject: 1,
799                predicate: 40,
800                object: 2,
801            },
802            join_var: 1,
803            projection: [0; MAX_VARIABLES],
804            projection_count: 0,
805            filters: [0; 8],
806            filter_count: 0,
807            limit: u64::MAX,
808            offset: 0,
809        }
810    }
811
812    #[test]
813    fn accepts_nested_loop_join_tree() {
814        let mut plan = ExecutionPlan::new();
815        let left = plan
816            .add_operator(
817                PhysicalOperatorType::TripleScan {
818                    subject: 0,
819                    predicate: 20,
820                    object: 1,
821                },
822                1,
823            )
824            .unwrap();
825        let right = plan
826            .add_operator(
827                PhysicalOperatorType::TripleScan {
828                    subject: 1,
829                    predicate: 40,
830                    object: 2,
831                },
832                1,
833            )
834            .unwrap();
835        plan.root_operator = plan
836            .add_operator(
837                PhysicalOperatorType::NestedLoopJoin {
838                    left,
839                    right,
840                    join_var: 1,
841                },
842                1,
843            )
844            .unwrap();
845        let compiled = Q42RangeHashJoinPlan::from_execution_plan(&plan).unwrap();
846        assert_eq!(compiled.join_var, 1);
847        assert_eq!(compiled.right.predicate, 40);
848    }
849
850    #[test]
851    fn hashes_smaller_side_and_joins() {
852        let left = quin(10, 20, 30);
853        let right = quin(30, 40, 50);
854        let extra = quin(31, 40, 51);
855        let (_dir, volume) = test_volume(&[left, right, extra]);
856        let mut ctx = SparqlQueryContext::new();
857        ctx.variable_count = 3;
858        let mut table = [Q42RangeHashJoinSlot::default(); 8];
859        let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
860        let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
861        let mut quins = [NQuin::default(); 4];
862        let mut probe_rows = [BindingRow::default(); 4];
863        let mut join_out = [BindingRow::default(); 4];
864        let mut out = [BindingRow::default(); 4];
865        let mut state = Q42RangeHashJoinState::default();
866        let page = execute_range_hash_join_page_into(
867            &volume,
868            join_plan(),
869            &ctx,
870            &mut state,
871            &mut table,
872            &mut compressed,
873            &mut decoded,
874            &mut quins,
875            &mut probe_rows,
876            &mut join_out,
877            &mut out,
878        )
879        .unwrap();
880        assert!(page.done);
881        assert_eq!(page.returned, 1);
882        assert_eq!(out[0].get(0), Some(10));
883        assert_eq!(out[0].get(1), Some(30));
884        assert_eq!(out[0].get(2), Some(50));
885        assert!(!state.build_is_right);
886    }
887
888    #[test]
889    fn cap_exceeded_tells_planner_to_keep_nested_loop() {
890        let left_a = quin(10, 20, 30);
891        let left_b = quin(11, 20, 32);
892        let right_a = quin(30, 40, 50);
893        let right_b = quin(32, 40, 51);
894        let (_dir, volume) = test_volume(&[left_a, left_b, right_a, right_b]);
895        let mut ctx = SparqlQueryContext::new();
896        ctx.variable_count = 3;
897        let mut table = [Q42RangeHashJoinSlot::default(); 1];
898        let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
899        let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
900        let mut quins = [NQuin::default(); 4];
901        let mut probe_rows = [BindingRow::default(); 4];
902        let mut join_out = [BindingRow::default(); 4];
903        let mut out = [BindingRow::default(); 4];
904        let mut state = Q42RangeHashJoinState::default();
905        let err = execute_range_hash_join_page_into(
906            &volume,
907            join_plan(),
908            &ctx,
909            &mut state,
910            &mut table,
911            &mut compressed,
912            &mut decoded,
913            &mut quins,
914            &mut probe_rows,
915            &mut join_out,
916            &mut out,
917        )
918        .unwrap_err();
919        assert!(
920            err.contains("planner must keep NestedLoopJoin"),
921            "unexpected error: {err}"
922        );
923        assert!(!state.built);
924    }
925
926    #[test]
927    fn empty_table_is_a_cap_error() {
928        let left = quin(10, 20, 30);
929        let right = quin(30, 40, 50);
930        let (_dir, volume) = test_volume(&[left, right]);
931        let mut ctx = SparqlQueryContext::new();
932        ctx.variable_count = 3;
933        let mut table = [];
934        let mut compressed = [0u8; crate::q42_volume::MAX_COMPRESSED_SUPERBLOCK_SIZE];
935        let mut decoded = [0u8; crate::q42_volume::SUPERBLOCK_SIZE];
936        let mut quins = [NQuin::default(); 2];
937        let mut probe_rows = [BindingRow::default(); 2];
938        let mut join_out = [BindingRow::default(); 2];
939        let mut out = [BindingRow::default(); 2];
940        let mut state = Q42RangeHashJoinState::default();
941        let err = execute_range_hash_join_page_into(
942            &volume,
943            join_plan(),
944            &ctx,
945            &mut state,
946            &mut table,
947            &mut compressed,
948            &mut decoded,
949            &mut quins,
950            &mut probe_rows,
951            &mut join_out,
952            &mut out,
953        )
954        .unwrap_err();
955        assert!(err.contains("NestedLoopJoin"));
956    }
957}