#![cfg_attr(not(feature = "cuda"), allow(dead_code))]
use oxidelake_core::EngineError;
use crate::cpu::kernels::JoinTable;
const MAX_CAPACITY: usize = 1 << 31;
pub(crate) fn slot_hash(key: i64, capacity: u32) -> u32 {
let mut h = key as u64;
h ^= h >> 33;
h = h.wrapping_mul(0xff51_afd7_ed55_8ccd);
h ^= h >> 33;
h = h.wrapping_mul(0xc4ce_b9fe_1a85_ec53);
h ^= h >> 33;
(h & u64::from(capacity.wrapping_sub(1))) as u32
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct JoinSlots {
pub(crate) capacity: u32,
pub(crate) keys: Vec<i64>,
pub(crate) starts: Vec<u32>,
pub(crate) counts: Vec<u32>,
distinct: usize,
}
impl JoinSlots {
pub(crate) fn build(table: &JoinTable, build_rows: usize) -> Result<Self, EngineError> {
let rows = table.row_indices();
if let Some(&bad) = rows.iter().find(|&&r| r as usize >= build_rows) {
return Err(EngineError::execution(format!(
"join table row {bad} is out of range for a {build_rows}-row build side"
)));
}
let distinct = table.distinct_keys();
let capacity = distinct
.saturating_mul(2)
.max(16)
.checked_next_power_of_two()
.filter(|&c| c <= MAX_CAPACITY)
.and_then(|c| u32::try_from(c).ok())
.ok_or_else(|| {
EngineError::unsupported(
"device.join_table",
format!("{distinct} distinct join keys exceed the device index"),
)
})?;
let slots = capacity as usize;
let mut keys = vec![0i64; slots];
let mut starts = vec![0u32; slots];
let mut counts = vec![0u32; slots];
for (key, start, count) in table.runs() {
let end = start as usize + count as usize;
if count == 0 || end > rows.len() {
return Err(EngineError::execution(format!(
"join table run {start}+{count} for key {key} is outside its {} rows",
rows.len()
)));
}
let mut slot = slot_hash(key, capacity);
let mut placed = false;
for _ in 0..capacity {
let s = slot as usize;
if counts[s] == 0 {
keys[s] = key;
starts[s] = start;
counts[s] = count;
placed = true;
break;
}
slot = (slot + 1) & (capacity - 1);
}
if !placed {
return Err(EngineError::execution("device join index is full"));
}
}
Ok(Self {
capacity,
keys,
starts,
counts,
distinct,
})
}
pub(crate) fn distinct(&self) -> usize {
self.distinct
}
#[cfg(test)]
pub(crate) fn probe(&self, key: i64) -> (Option<(u32, u32)>, u32) {
let mut slot = slot_hash(key, self.capacity);
let mut visits = 0u32;
for _ in 0..self.capacity {
visits += 1;
let s = slot as usize;
let count = self.counts[s];
if count == 0 {
break;
}
if self.keys[s] == key {
return (Some((self.starts[s], count)), visits);
}
slot = (slot + 1) & (self.capacity - 1);
}
(None, visits)
}
}
#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tests {
use std::sync::Arc;
use arrow::array::{Int64Array, RecordBatch};
use arrow::datatypes::{DataType, Field, Schema};
use super::*;
fn table(keys: Vec<Option<i64>>) -> (JoinTable, usize) {
let rows = keys.len();
let schema = Arc::new(Schema::new(vec![Field::new("k", DataType::Int64, true)]));
let batch = RecordBatch::try_new(schema, vec![Arc::new(Int64Array::from(keys))]).unwrap();
(JoinTable::build(&batch, 0).unwrap(), rows)
}
#[test]
fn slot_hash_is_the_kernels_hash() {
assert_eq!(slot_hash(0, 16), 0);
assert_eq!(slot_hash(1, 16), 12);
assert_eq!(slot_hash(-1, 1024), 801);
assert_eq!(slot_hash(42, 131_072), 22_988);
assert_eq!(slot_hash(i64::MIN, 1 << 20), 107_667);
let kernel = include_str!("../kernels/cuda/hash_join.cu");
for needle in [
"h ^= h >> 33;",
"h *= 0xff51afd7ed558ccdULL;",
"h *= 0xc4ceb9fe1a85ec53ULL;",
"(h & (unsigned long long)(capacity - 1u))",
] {
assert!(kernel.contains(needle), "hash_join.cu lost `{needle}`");
}
}
#[test]
fn every_key_finds_its_run_and_absent_keys_find_nothing() {
let keys: Vec<Option<i64>> = (0..500i64)
.map(|r| (r % 11 != 4).then_some((r * 7919) % 37 - 18))
.chain([Some(i64::MIN), Some(i64::MAX), None])
.collect();
let (table, rows) = table(keys);
let slots = JoinSlots::build(&table, rows).unwrap();
assert_eq!(slots.distinct(), table.distinct_keys());
assert!(slots.capacity as usize >= 2 * slots.distinct());
for (key, start, count) in table.runs() {
assert_eq!(slots.probe(key).0, Some((start, count)), "key {key}");
let run = &table.row_indices()[start as usize..(start + count) as usize];
assert_eq!(run, table.matches(key));
}
for absent in [19, -19, 1 << 40, i64::MIN + 1] {
assert_eq!(slots.probe(absent).0, None, "key {absent}");
}
}
#[test]
fn a_repeated_build_key_costs_a_probe_nothing() {
fn splitmix(s: &mut u64) -> u64 {
*s = s.wrapping_add(0x9E37_79B9_7F4A_7C15);
let mut z = *s;
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
let mut state = 7u64;
let probe: Vec<i64> = (0..65_536)
.map(|_| ((splitmix(&mut state) >> 1) as i64) | 1 << 62)
.collect();
let n = 100_000i64;
let shapes: [(&str, Vec<Option<i64>>); 4] = [
("unique", (0..n).map(Some).collect()),
(
"half key 0",
(0..n)
.map(|i| Some(if i % 2 == 0 { 0 } else { i }))
.collect(),
),
("all key 0", vec![Some(0); 100_000]),
("10 keys", (0..n).map(|i| Some(i % 10)).collect()),
];
for (name, keys) in shapes {
let (table, rows) = table(keys);
let slots = JoinSlots::build(&table, rows).unwrap();
assert_eq!(
slots.counts.iter().filter(|&&c| c > 0).count(),
table.distinct_keys(),
"{name}: one slot per distinct key"
);
let visits: u64 = probe
.iter()
.map(|&k| {
let (found, visits) = slots.probe(k);
assert_eq!(found, None);
u64::from(visits)
})
.sum();
let mean = visits as f64 / probe.len() as f64;
assert!(mean <= 2.5, "{name}: {mean:.1} slot reads per probe row");
}
}
#[test]
fn rows_outside_the_build_side_are_refused() {
let (table, rows) = table(vec![Some(1), Some(2), Some(1)]);
assert!(JoinSlots::build(&table, rows).is_ok());
let err = JoinSlots::build(&table, rows - 1).unwrap_err();
assert!(err.to_string().contains("out of range"), "{err}");
}
#[test]
fn an_empty_or_all_null_build_side_has_no_keys() {
for keys in [vec![], vec![None, None]] {
let (table, rows) = table(keys);
let slots = JoinSlots::build(&table, rows).unwrap();
assert_eq!(slots.distinct(), 0);
assert_eq!(slots.capacity, 16);
assert_eq!(slots.probe(0), (None, 1));
}
}
}