Skip to main content

qualia_core_db/query/graph_accel/
join.rs

1//! Sort-merge join on `u64` keys. GPU radix on large sides, CPU merge always
2//! (merge is sequential). Fail-closed: if `out` fills, `truncated` is true.
3
4use super::cpu::{merge_sorted_pairs, radix_sort_u64_indices, sort_merge_join_u64};
5use super::path::{AccelPath, AccelPolicy, GPU_JOIN_MIN};
6use super::sort::sort_u64_indices;
7
8#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub struct JoinOutcome {
10    pub path: AccelPath,
11    pub written: usize,
12    pub truncated: bool,
13}
14
15/// Join `probe` to `build` on equal keys. Writes `(probe_idx, build_idx)`.
16pub fn hash_join_u64(build: &[u64], probe: &[u64], out: &mut [(u32, u32)]) -> JoinOutcome {
17    if build.is_empty() || probe.is_empty() || out.is_empty() {
18        return JoinOutcome {
19            path: AccelPath::Cpu,
20            written: 0,
21            truncated: false,
22        };
23    }
24    let policy = AccelPolicy::from_env();
25    let large = build.len() >= GPU_JOIN_MIN && probe.len() >= GPU_JOIN_MIN;
26    if policy != AccelPolicy::CpuOnly && large {
27        let mut b_idx: Vec<u32> = (0..build.len() as u32).collect();
28        let mut p_idx: Vec<u32> = (0..probe.len() as u32).collect();
29        let sb = sort_u64_indices(build, &mut b_idx);
30        let sp = sort_u64_indices(probe, &mut p_idx);
31        let written = merge_sorted_pairs(build, probe, &b_idx, &p_idx, out);
32        let path = if sb.path == AccelPath::Gpu || sp.path == AccelPath::Gpu {
33            AccelPath::Gpu
34        } else {
35            AccelPath::Cpu
36        };
37        return JoinOutcome {
38            path,
39            written,
40            // Full output buffer: more pairs may exist. Fail closed — caller enlarges.
41            truncated: written == out.len(),
42        };
43    }
44    let written = sort_merge_join_u64(build, probe, out);
45    JoinOutcome {
46        path: AccelPath::Cpu,
47        written,
48        truncated: written == out.len(),
49    }
50}
51
52/// CPU-only oracle (tests).
53pub fn hash_join_u64_cpu(build: &[u64], probe: &[u64], out: &mut [(u32, u32)]) -> usize {
54    let mut b_idx: Vec<u32> = (0..build.len() as u32).collect();
55    let mut p_idx: Vec<u32> = (0..probe.len() as u32).collect();
56    radix_sort_u64_indices(build, &mut b_idx);
57    radix_sort_u64_indices(probe, &mut p_idx);
58    merge_sorted_pairs(build, probe, &b_idx, &p_idx, out)
59}