1use std::sync::Arc;
2
3use rustc_hash::FxHashMap;
4
5use crate::columnar::ColumnBuilder;
6
7#[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#[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#[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#[derive(Debug, Clone)]
70pub struct DictValues {
71 pub data: Vec<u8>,
72 pub offsets: Vec<i32>,
73}
74
75pub(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 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 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 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 local_len == seed.len() && is_identity {
150 } 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#[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 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}