Skip to main content

rypipe_core/
dict.rs

1use std::sync::Arc;
2
3use rustc_hash::FxHashMap;
4
5use crate::columnar::ColumnBuilder;
6
7/// Immutable seed dictionary built from a sample.
8///
9/// Shared `Arc` across threads, read-only after construction.
10#[derive(Debug, Clone)]
11pub struct SeedDict {
12    pub values: Vec<u8>,
13    pub offsets: Vec<i32>,
14    pub index: FxHashMap<Box<str>, i32>,
15}
16
17impl SeedDict {
18    pub fn new(values: Vec<String>) -> Self {
19        let mut data = Vec::new();
20        let mut offsets = Vec::with_capacity(values.len() + 1);
21        offsets.push(0);
22        let mut index = FxHashMap::default();
23        for (i, s) in values.into_iter().enumerate() {
24            index.insert(s.clone().into_boxed_str(), i as i32);
25            data.extend_from_slice(s.as_bytes());
26            offsets.push(data.len() as i32);
27        }
28        Self {
29            values: data,
30            offsets,
31            index,
32        }
33    }
34
35    pub fn len(&self) -> usize {
36        self.offsets.len().saturating_sub(1)
37    }
38
39    pub fn is_empty(&self) -> bool {
40        self.len() == 0
41    }
42}
43
44/// Column plan from sampling.
45#[derive(Debug, Clone)]
46pub struct ColumnPlan {
47    pub encode_as_dict: bool,
48    pub seed: Option<Arc<SeedDict>>,
49    pub est_cardinality: usize,
50}
51
52/// Remap table for one chunk's codes.
53#[derive(Debug, Clone)]
54pub struct RemapTable {
55    pub map: Vec<i32>,
56    pub is_identity: bool,
57}
58
59impl RemapTable {
60    pub fn identity(len: usize) -> Self {
61        Self {
62            map: (0..len as i32).collect(),
63            is_identity: true,
64        }
65    }
66}
67
68/// Unified dictionary values.
69#[derive(Debug, Clone)]
70pub struct DictValues {
71    pub data: Vec<u8>,
72    pub offsets: Vec<i32>,
73}
74
75/// Unify per-chunk dictionaries with the seed.
76///
77/// Works with `ColumnBuilder::Dictionary { codes, data, offsets, index }`.
78/// Seed codes are `0..seed.len()`, overflow are `seed.len()..`.
79pub(crate) fn unify_dictionaries(
80    seed: &SeedDict,
81    locals: &[&ColumnBuilder],
82) -> (DictValues, Vec<RemapTable>) {
83    let mut global_index: FxHashMap<Box<str>, i32> = FxHashMap::default();
84    let mut global_data = seed.values.clone();
85    let mut global_offsets = seed.offsets.clone();
86    let mut next_code = seed.len() as i32;
87
88    for (k, &v) in &seed.index {
89        global_index.insert(k.clone(), v);
90    }
91
92    // Collect overflow values not in seed
93    for col in locals {
94        if let ColumnBuilder::Dictionary { data, offsets, .. } = col {
95            for i in seed.len()..(offsets.len() - 1) {
96                let start = offsets[i] as usize;
97                let end = offsets[i + 1] as usize;
98                let val = String::from_utf8_lossy(&data[start..end]);
99                let k: Box<str> = val.as_ref().into();
100                if !global_index.contains_key(&k) {
101                    global_index.insert(k.clone(), next_code);
102                    global_data.extend_from_slice(val.as_bytes());
103                    global_offsets.push(global_data.len() as i32);
104                    next_code += 1;
105                }
106            }
107        }
108    }
109
110    let dict_values = DictValues {
111        data: global_data,
112        offsets: global_offsets,
113    };
114
115    // Build remap tables: local code -> global code
116    let mut remaps = Vec::with_capacity(locals.len());
117    for col in locals {
118        if let ColumnBuilder::Dictionary {
119            data,
120            offsets,
121            index,
122            ..
123        } = col
124        {
125            let local_len = offsets.len() - 1;
126            let mut map = Vec::with_capacity(local_len);
127            let mut is_identity = true;
128            for i in 0..local_len {
129                let start = offsets[i] as usize;
130                let end = offsets[i + 1] as usize;
131                let val = String::from_utf8_lossy(&data[start..end]);
132                let k: Box<str> = val.as_ref().into();
133                let Some(&g) = global_index.get(&k) else {
134                    // Entry not in global index (corrupted chunk or adversarial input);
135                    // treat as unmappable, skip remapping for this code.
136                    map.push(i as i32);
137                    continue;
138                };
139                let Some(&local) = index.get(k.as_ref()) else {
140                    map.push(i as i32);
141                    continue;
142                };
143                if g != local {
144                    is_identity = false;
145                }
146                map.push(g);
147            }
148            // If no overflow, it's essentially identity if dict == seed
149            if local_len == seed.len() && is_identity {
150                // All seed, identity
151            } else if local_len > seed.len() {
152                is_identity = false;
153            }
154            remaps.push(RemapTable { map, is_identity });
155        } else {
156            remaps.push(RemapTable::identity(0));
157        }
158    }
159
160    (dict_values, remaps)
161}
162
163/// Apply remap to codes in place (parallel, L1-resident).
164#[inline]
165pub fn apply_remap(codes: &mut [Option<i32>], remap: &RemapTable) {
166    if remap.is_identity {
167        return;
168    }
169    for v in codes.iter_mut().flatten() {
170        if let Some(&remapped) = remap.map.get(*v as usize) {
171            *v = remapped;
172        }
173    }
174}
175
176#[cfg(test)]
177mod tests {
178    use super::*;
179    use crate::columnar::ColumnBuilder;
180    use crate::plan::FieldType;
181
182    fn make_dict(values: Vec<&str>) -> ColumnBuilder {
183        let mut b = ColumnBuilder::with_capacity(10, &FieldType::Dictionary);
184        for v in values {
185            b.push_str(Some(v));
186        }
187        b
188    }
189
190    #[test]
191    fn test_unify_no_overflow() {
192        let seed = SeedDict::new(vec!["a".into(), "b".into()]);
193        let col1 = make_dict(vec!["a", "b", "a"]);
194        let col2 = make_dict(vec!["b", "a"]);
195        let (dict, remaps) = unify_dictionaries(&seed, &[&col1, &col2]);
196        assert_eq!(dict.offsets.len(), 3);
197        // Both remaps should be identity or at least map correctly
198        assert_eq!(remaps.len(), 2);
199    }
200
201    #[test]
202    fn test_apply_remap_identity() {
203        let mut codes = vec![Some(0), Some(1), Some(0), None];
204        let remap = RemapTable::identity(2);
205        apply_remap(&mut codes, &remap);
206        assert_eq!(codes, vec![Some(0), Some(1), Some(0), None]);
207    }
208}