Skip to main content

polars_core/frame/column/
dictionary.rs

1use std::hash::BuildHasher;
2use std::sync::atomic::{AtomicU64, Ordering};
3use std::sync::{Arc, Mutex, OnceLock};
4
5use polars_arrow::array::{Array, MutableBinaryViewArray, Utf8ViewArray};
6use polars_buffer::Buffer;
7use polars_error::{PolarsResult, polars_ensure};
8use polars_utils::aliases::{InitHashMaps, PlHashMap, PlRandomState};
9use polars_utils::pl_str::PlSmallStr;
10
11use super::{Column, DataType, IntoColumn, Series};
12use crate::prelude::*;
13use crate::series::IsSorted;
14
15static NEXT_DICTIONARY_ID: AtomicU64 = AtomicU64::new(0);
16
17/// How many hashers' hashes a dictionary keeps.
18const MAX_CACHED_HASHERS: usize = 4;
19
20static STRING_DTYPE: DataType = DataType::String;
21
22/// The values of a dictionary that [`DictionaryColumn`]s index into, such as the dictionary page
23/// of a parquet column chunk.
24///
25/// The values need not be unique: equal codes mean equal values, but different codes may also.
26pub struct SharedDictionary {
27    /// Process-unique id; caches in operators are keyed by it.
28    id: u64,
29    /// The dictionary values; materialized columns share its data buffers.
30    values: Utf8ViewArray,
31    /// The hash of each value under recently used hashers, keyed by [`hasher_fingerprint`].
32    hashes: Mutex<Vec<CachedHashes>>,
33    /// The first code of each value, built on first use (see [`Self::code_of`]).
34    lookup: OnceLock<CodeLookup>,
35}
36
37/// The hashes of a dictionary's values under one hasher.
38struct CachedHashes {
39    fingerprint: u128,
40    random_state: PlRandomState,
41    hashes: Buffer<u64>,
42}
43
44/// A table from each distinct value of a dictionary to its first code.
45#[derive(Clone)]
46struct CodeLookup {
47    random_state: PlRandomState,
48    codes: hashbrown::HashTable<u32>,
49}
50
51impl std::fmt::Debug for SharedDictionary {
52    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
53        f.debug_struct("SharedDictionary")
54            .field("id", &self.id)
55            .field("len", &self.values.len())
56            .finish()
57    }
58}
59
60/// Identifies a hasher by the hashes it gives two values.
61fn hasher_fingerprint(random_state: &PlRandomState) -> u128 {
62    let lo = random_state.hash_one(0x243F_6A88_85A3_08D3_u64);
63    let hi = random_state.hash_one(0x1319_8A2E_0370_7344_u64);
64    ((hi as u128) << 64) | lo as u128
65}
66
67impl SharedDictionary {
68    /// The values must not contain nulls.
69    pub fn new(values: Utf8ViewArray) -> Arc<Self> {
70        assert!(
71            values.validity().is_none_or(|v| v.unset_bits() == 0),
72            "dictionary values must not be null"
73        );
74        let values = values.with_validity(None);
75        Arc::new(Self {
76            id: NEXT_DICTIONARY_ID.fetch_add(1, Ordering::Relaxed),
77            values,
78            hashes: Mutex::new(Vec::new()),
79            lookup: OnceLock::new(),
80        })
81    }
82
83    fn lookup(&self) -> &CodeLookup {
84        self.lookup.get_or_init(|| {
85            let random_state = PlRandomState::default();
86            let mut codes = hashbrown::HashTable::with_capacity(self.len());
87            for (c, v) in self.values.values_iter().enumerate() {
88                let h = random_state.hash_one(v);
89                // SAFETY: the codes in the table are in bounds.
90                let value = |k: &u32| unsafe { self.values.value_unchecked(*k as usize) };
91                if codes.find(h, |k| value(k) == v).is_none() {
92                    codes.insert_unique(h, c as u32, |k| random_state.hash_one(value(k)));
93                }
94            }
95            CodeLookup {
96                random_state,
97                codes,
98            }
99        })
100    }
101
102    /// The first code of `value`, if the dictionary holds it. The lookup table is built on the
103    /// first call and kept with the dictionary.
104    pub fn code_of(&self, value: &str) -> Option<u32> {
105        let lookup = self.lookup();
106        lookup
107            .codes
108            .find(lookup.random_state.hash_one(value), |k| {
109                // SAFETY: the codes in the table are in bounds.
110                unsafe { self.values.value_unchecked(*k as usize) == value }
111            })
112            .copied()
113    }
114
115    /// A new dictionary of these values followed by `added`, none of which this one holds. It
116    /// shares these values' buffers, and extends the lookup table and the cached hashes instead of
117    /// computing them again.
118    pub fn extended(&self, added: &[&str]) -> Arc<Self> {
119        let old_len = self.len();
120        let mut values = MutableBinaryViewArray::<str>::with_capacity(old_len + added.len());
121        for buffer in self.values.data_buffers().iter() {
122            values.push_buffer(buffer.clone());
123        }
124        // SAFETY: the views index the buffers just pushed, in the same order.
125        unsafe {
126            values.views_mut().extend(self.values.views().iter());
127            values.set_total_bytes_len(self.values.total_bytes_len());
128        }
129        values.extend_values(added.iter().copied());
130        let values: Utf8ViewArray = values.freeze();
131
132        // SAFETY: the codes in the tables are in bounds.
133        let value = |k: &u32| unsafe { values.value_unchecked(*k as usize) };
134        let lookup = OnceLock::new();
135        if let Some(old) = self.lookup.get() {
136            let mut new = old.clone();
137            for (i, v) in added.iter().enumerate() {
138                let h = new.random_state.hash_one(*v);
139                let random_state = &new.random_state;
140                new.codes
141                    .insert_unique(h, (old_len + i) as u32, |k| random_state.hash_one(value(k)));
142            }
143            _ = lookup.set(new);
144        }
145
146        let views = values.views();
147        let buffers = values.data_buffers();
148        let hashes = self
149            .hashes
150            .lock()
151            .unwrap()
152            .iter()
153            .map(|c| {
154                let tail = views[old_len..]
155                    .iter()
156                    // SAFETY: the views are valid for the buffers.
157                    .map(|v| unsafe { v.hash_with_buffers_unchecked(buffers, &c.random_state) });
158                CachedHashes {
159                    fingerprint: c.fingerprint,
160                    random_state: c.random_state.clone(),
161                    hashes: c
162                        .hashes
163                        .iter()
164                        .copied()
165                        .chain(tail)
166                        .collect::<Vec<_>>()
167                        .into(),
168                }
169            })
170            .collect();
171
172        Arc::new(Self {
173            id: NEXT_DICTIONARY_ID.fetch_add(1, Ordering::Relaxed),
174            values,
175            hashes: Mutex::new(hashes),
176            lookup,
177        })
178    }
179
180    pub fn id(&self) -> u64 {
181        self.id
182    }
183
184    pub fn values(&self) -> &Utf8ViewArray {
185        &self.values
186    }
187
188    pub fn len(&self) -> usize {
189        self.values.len()
190    }
191
192    pub fn is_empty(&self) -> bool {
193        self.values.is_empty()
194    }
195
196    /// The hashes [`Self::hashes`] gives, if they were already computed.
197    pub fn cached_hashes(&self, random_state: &PlRandomState) -> Option<Buffer<u64>> {
198        let fingerprint = hasher_fingerprint(random_state);
199        self.hashes
200            .lock()
201            .unwrap()
202            .iter()
203            .find(|c| c.fingerprint == fingerprint)
204            .map(|c| c.hashes.clone())
205    }
206
207    /// The hash of each value as `View::hash_with_buffers_unchecked` computes it with
208    /// `random_state`, computed once per hasher.
209    pub fn hashes(&self, random_state: &PlRandomState) -> Buffer<u64> {
210        if let Some(hashes) = self.cached_hashes(random_state) {
211            return hashes;
212        }
213        let fingerprint = hasher_fingerprint(random_state);
214
215        let values = self.values.to_binview();
216        let buffers = values.data_buffers();
217        let hashes: Buffer<u64> = values
218            .views()
219            .iter()
220            .map(|v| unsafe { v.hash_with_buffers_unchecked(buffers, random_state) })
221            .collect::<Vec<_>>()
222            .into();
223
224        let mut cache = self.hashes.lock().unwrap();
225        if !cache.iter().any(|c| c.fingerprint == fingerprint) {
226            if cache.len() == MAX_CACHED_HASHERS {
227                cache.remove(0);
228            }
229            cache.push(CachedHashes {
230                fingerprint,
231                random_state: random_state.clone(),
232                hashes: hashes.clone(),
233            });
234        }
235        hashes
236    }
237}
238
239/// A String [`Column`] held as codes into a [`SharedDictionary`]: row `i`, when valid, is
240/// `dict.values()[codes[i]]`.
241///
242/// This is lazily materialized into a [`Series`] that gathers the values.
243#[derive(Debug, Clone)]
244pub struct DictionaryColumn {
245    name: PlSmallStr,
246    dict: Arc<SharedDictionary>,
247    // invariants:
248    // codes[i] < dict.len() for every valid row i
249    codes: UInt32Chunked,
250    /// Whether the values are sorted, a hint as on a [`Series`].
251    sorted: IsSorted,
252
253    /// A lazily materialized [`Series`] variant of this [`DictionaryColumn`].
254    materialized: OnceLock<Series>,
255}
256
257/// Whether every valid code is below `dict_len`. Reads the arrays, not the sorted flag or other
258/// metadata of `codes`, which safe code can set wrongly.
259fn codes_in_bounds(codes: &UInt32Chunked, dict_len: usize) -> bool {
260    use polars_compute::min_max::MinMaxKernel;
261    codes
262        .downcast_iter()
263        .filter_map(MinMaxKernel::max_ignore_nan_kernel)
264        .max()
265        .is_none_or(|m| (m as usize) < dict_len)
266}
267
268impl DictionaryColumn {
269    /// # Safety
270    /// Every valid code must be in bounds for `dict`.
271    pub unsafe fn new_unchecked(
272        name: PlSmallStr,
273        dict: Arc<SharedDictionary>,
274        codes: UInt32Chunked,
275    ) -> Self {
276        debug_assert!(
277            codes_in_bounds(&codes, dict.len()),
278            "dictionary code out of bounds"
279        );
280        Self {
281            name,
282            dict,
283            codes: codes.with_name(PlSmallStr::EMPTY),
284            sorted: IsSorted::Not,
285            materialized: OnceLock::new(),
286        }
287    }
288
289    pub fn try_new(
290        name: PlSmallStr,
291        dict: Arc<SharedDictionary>,
292        codes: UInt32Chunked,
293    ) -> PolarsResult<Self> {
294        polars_ensure!(
295            codes_in_bounds(&codes, dict.len()),
296            ComputeError: "dictionary code out of bounds"
297        );
298        Ok(unsafe { Self::new_unchecked(name, dict, codes) })
299    }
300
301    pub fn name(&self) -> &PlSmallStr {
302        &self.name
303    }
304
305    pub fn rename(&mut self, name: PlSmallStr) {
306        if let Some(s) = self.materialized.get_mut() {
307            s.rename(name.clone());
308        }
309        self.name = name;
310    }
311
312    pub fn dtype(&self) -> &DataType {
313        &STRING_DTYPE
314    }
315
316    pub fn len(&self) -> usize {
317        self.codes.len()
318    }
319
320    pub fn is_empty(&self) -> bool {
321        self.codes.is_empty()
322    }
323
324    pub fn null_count(&self) -> usize {
325        self.codes.null_count()
326    }
327
328    pub fn has_nulls(&self) -> bool {
329        self.codes.has_nulls()
330    }
331
332    pub fn dict(&self) -> &Arc<SharedDictionary> {
333        &self.dict
334    }
335
336    pub fn codes(&self) -> &UInt32Chunked {
337        &self.codes
338    }
339
340    /// A column of the same dictionary with `codes`, which are not known to be sorted.
341    fn with_codes(&self, codes: UInt32Chunked) -> Self {
342        Self {
343            name: self.name.clone(),
344            dict: self.dict.clone(),
345            codes,
346            sorted: IsSorted::Not,
347            materialized: OnceLock::new(),
348        }
349    }
350
351    /// As [`Self::with_codes`], for codes that keep the order of this column's rows.
352    fn with_order_kept(&self, codes: UInt32Chunked) -> Self {
353        Self {
354            sorted: self.sorted,
355            ..self.with_codes(codes)
356        }
357    }
358
359    pub fn is_sorted_flag(&self) -> IsSorted {
360        self.sorted
361    }
362
363    pub fn set_sorted_flag(&mut self, sorted: IsSorted) {
364        if let Some(s) = self.materialized.get_mut() {
365            s.set_sorted_flag(sorted);
366        }
367        self.sorted = sorted;
368    }
369
370    /// Gathers the values into a String [`Series`].
371    pub fn to_series(&self) -> Series {
372        let values = StringChunked::with_chunk(self.name.clone(), self.dict.values.clone());
373        #[cfg(feature = "bigidx")]
374        let idx = self.codes.cast(&IDX_DTYPE).unwrap();
375        #[cfg(feature = "bigidx")]
376        let idx = idx.idx().unwrap();
377        #[cfg(not(feature = "bigidx"))]
378        let idx = &self.codes;
379        // SAFETY: the codes are in bounds (invariant).
380        let mut s = unsafe { values.take_unchecked(idx) }.into_series();
381        s.set_sorted_flag(self.sorted);
382        s
383    }
384
385    /// Get the [`DictionaryColumn`] as [`Series`] if it was already materialized.
386    pub fn lazy_as_materialized_series(&self) -> Option<&Series> {
387        self.materialized.get()
388    }
389
390    /// Get the [`DictionaryColumn`] as [`Series`]
391    ///
392    /// This needs to materialize upon the first call. Afterwards, this is cached.
393    pub fn as_materialized_series(&self) -> &Series {
394        self.materialized.get_or_init(|| self.to_series())
395    }
396
397    /// Take the [`DictionaryColumn`] and materialize as a [`Series`] if not already done.
398    pub fn take_materialized_series(self) -> Series {
399        match self.materialized.into_inner() {
400            Some(s) => s,
401            None => Self {
402                materialized: OnceLock::new(),
403                ..self
404            }
405            .to_series(),
406        }
407    }
408
409    pub fn slice(&self, slice: impl Into<Slice>) -> Self {
410        self.with_order_kept(self.codes.slice(slice))
411    }
412
413    pub fn filter(&self, filter: &BooleanChunked) -> PolarsResult<Self> {
414        Ok(self.with_order_kept(self.codes.filter(filter)?))
415    }
416
417    /// # Safety
418    /// The indices must be in bounds.
419    pub unsafe fn take_unchecked(&self, indices: &IdxCa) -> Self {
420        self.with_codes(unsafe { self.codes.take_unchecked(indices) })
421    }
422
423    /// # Safety
424    /// The indices must be in bounds.
425    pub unsafe fn take_slice_unchecked(&self, indices: &[IdxSize]) -> Self {
426        self.with_codes(unsafe { self.codes.take_unchecked(indices) })
427    }
428
429    pub fn rechunk(&self) -> Self {
430        if self.codes.chunks().len() <= 1 {
431            return self.clone();
432        }
433        self.with_order_kept(self.codes.rechunk().into_owned())
434    }
435
436    pub fn reverse(&self) -> Self {
437        let mut out = self.with_codes(self.codes.reverse());
438        out.sorted = self.sorted.reverse();
439        out
440    }
441
442    /// An empty column that holds no dictionary of its own to keep alive: it adopts the
443    /// dictionary of the first column appended to it.
444    pub fn new_empty(name: PlSmallStr) -> Self {
445        let dict = SharedDictionary::new(Utf8ViewArray::new_empty(
446            polars_arrow::datatypes::ArrowDataType::Utf8View,
447        ));
448        let codes = UInt32Chunked::from_vec(PlSmallStr::EMPTY, Vec::new());
449        // SAFETY: there are no rows.
450        unsafe { Self::new_unchecked(name, dict, codes) }
451    }
452
453    /// Appends `other`'s codes. With another dictionary, `other`'s values that this dictionary
454    /// lacks are added to it (into a new dictionary, unless there are none) and `other`'s codes
455    /// remapped, if the merged dictionary has no more values than the rows of both, as otherwise
456    /// it costs more than materializing; returns false then.
457    ///
458    /// Values are matched by value, so appending the chunks of many row groups whose dictionaries
459    /// share their values keeps one dictionary of the distinct values. Once the lookup table
460    /// exists, remapping costs the size of `other`'s dictionary and codes. Extending also copies
461    /// the existing dictionary's views, lookup and cached hashes, so this method returns false
462    /// when that extension would copy more existing entries than `other` has rows.
463    pub fn try_append(&mut self, other: &DictionaryColumn) -> bool {
464        if other.is_empty() {
465            return true;
466        }
467        if self.dict.id != other.dict.id {
468            if self.is_empty() {
469                // Nothing to keep: take `other`'s dictionary and codes, as they are.
470                self.dict = other.dict.clone();
471                self.codes = other.codes.clone().with_name(self.codes.name().clone());
472                self.sorted = IsSorted::Not;
473                self.materialized = OnceLock::new();
474                return true;
475            }
476            let max_len = (self.len() + other.len()).min(u32::MAX as usize);
477            if self.dict.len() > max_len {
478                return false;
479            }
480            // With fewer rows than dictionary entries, resolve only the values that rows use, so
481            // that appending a small morsel costs its rows, not the size of its dictionary.
482            let used = if other.len() < other.dict.len() {
483                other.used_codes(other.len())
484            } else {
485                None
486            };
487            let mut added = Vec::new();
488            let mut added_code_of = PlHashMap::<&str, u32>::new();
489            let mut remap = Vec::with_capacity(match &used {
490                Some((used, _)) => used.len(),
491                None => other.dict.len(),
492            });
493            let values = &other.dict.values;
494            let to_resolve: Box<dyn Iterator<Item = &str> + '_> = match &used {
495                // SAFETY: used codes are valid codes, which are in bounds (invariant).
496                Some((used, _)) => Box::new(
497                    used.iter()
498                        .map(|c| unsafe { values.value_unchecked(*c as usize) }),
499                ),
500                None => Box::new(values.values_iter()),
501            };
502            for v in to_resolve {
503                let c = match self.dict.code_of(v) {
504                    Some(c) => c,
505                    None => {
506                        let next = (self.dict.len() + added.len()) as u32;
507                        *added_code_of.entry(v).or_insert_with(|| {
508                            added.push(v);
509                            next
510                        })
511                    },
512                };
513                remap.push(c);
514                if self.dict.len() + added.len() > max_len {
515                    return false;
516                }
517            }
518            if !added.is_empty() && self.dict.len() > other.len() {
519                return false;
520            }
521            let other_codes = match used {
522                Some((_, row_slots)) => {
523                    let codes = other.codes.rechunk();
524                    let arr = codes.downcast_as_array();
525                    // Null rows have slot 0, which is out of bounds if no row is valid.
526                    let new_codes: Vec<u32> = row_slots
527                        .iter()
528                        .map(|s| remap.get(*s as usize).copied().unwrap_or(0))
529                        .collect();
530                    let arr = PrimitiveArray::<u32>::new(
531                        ArrowDataType::UInt32,
532                        new_codes.into(),
533                        arr.validity().cloned(),
534                    );
535                    UInt32Chunked::with_chunk(PlSmallStr::EMPTY, arr)
536                },
537                // Null slots may hold any value, out of bounds too.
538                None => other
539                    .codes
540                    .apply_values(|c| remap.get(c as usize).copied().unwrap_or(0)),
541            };
542            if !added.is_empty() {
543                self.dict = self.dict.extended(&added);
544            }
545            self.codes.append(&other_codes).unwrap();
546        } else {
547            self.codes.append(&other.codes).unwrap();
548        }
549        self.sorted = IsSorted::Not;
550        self.materialized = OnceLock::new();
551        true
552    }
553
554    /// Estimated size of the column, see [`Series::estimated_size`].
555    ///
556    /// The dictionary is shared by every slice of a column, so each counts the part of it its rows
557    /// would take materialized, at most all of it; counting all of it for each slice would
558    /// overstate the memory of the morsels of a row group many times over.
559    pub fn estimated_size(&self) -> usize {
560        let dict_size = polars_arrow::compute::aggregate::estimated_bytes_size(&self.dict.values);
561        let dict_part = if self.len() >= self.dict.len() {
562            dict_size
563        } else {
564            (dict_size as u128 * self.len() as u128 / self.dict.len() as u128) as usize
565        };
566        self.codes
567            .chunks()
568            .iter()
569            .map(|c| polars_arrow::compute::aggregate::estimated_bytes_size(c.as_ref()))
570            .sum::<usize>()
571            + dict_part
572            + self.materialized.get().map_or(0, |s| s.estimated_size())
573    }
574
575    /// The codes that valid rows use, in order of first use, and the position of each row's code
576    /// among them (0 for a null row). `None` once more than `max_used` codes are used.
577    ///
578    /// The time this takes depends on the rows, not on the size of the dictionary, which can be
579    /// far larger than the rows need after a filter or slice.
580    pub fn used_codes(&self, max_used: usize) -> Option<(Vec<IdxSize>, Vec<u32>)> {
581        /// A dense table of the dictionary's size is used up to this many entries per row.
582        const MAX_DENSE_ENTRIES_PER_ROW: usize = 4;
583
584        let codes = self.codes.rechunk();
585        let codes = codes.downcast_as_array();
586        let validity = codes.validity().filter(|v| v.unset_bits() > 0);
587
588        // `slot_of(code, next)` is the position of `code`, `next` if it is new.
589        fn assign(
590            codes: &[u32],
591            validity: Option<&polars_arrow::bitmap::Bitmap>,
592            max_used: usize,
593            mut slot_of: impl FnMut(u32, u32) -> u32,
594        ) -> Option<(Vec<IdxSize>, Vec<u32>)> {
595            let mut used: Vec<IdxSize> = Vec::new();
596            let mut row_slots = Vec::with_capacity(codes.len());
597            for (i, c) in codes.iter().enumerate() {
598                if validity.is_some_and(|v| !unsafe { v.get_bit_unchecked(i) }) {
599                    row_slots.push(0);
600                    continue;
601                }
602                let next = used.len() as u32;
603                let s = slot_of(*c, next);
604                if s == next {
605                    if used.len() >= max_used {
606                        return None;
607                    }
608                    used.push(*c as IdxSize);
609                }
610                row_slots.push(s);
611            }
612            Some((used, row_slots))
613        }
614
615        if self.dict.len() <= MAX_DENSE_ENTRIES_PER_ROW.saturating_mul(self.len()) {
616            let mut slot = vec![u32::MAX; self.dict.len()];
617            assign(codes.values(), validity, max_used, |c, next| {
618                // SAFETY: valid codes are in bounds (invariant).
619                let s = unsafe { slot.get_unchecked_mut(c as usize) };
620                if *s == u32::MAX {
621                    *s = next;
622                }
623                *s
624            })
625        } else {
626            let mut slot = polars_utils::aliases::PlHashMap::<u32, u32>::default();
627            assign(codes.values(), validity, max_used, |c, next| {
628                *slot.entry(c).or_insert(next)
629            })
630        }
631    }
632
633    /// Evaluates an elementwise `f` once per dictionary value that a valid row uses, and once on
634    /// a null if a row is null, and spreads the results to the rows by code. A String result stays
635    /// dictionary-coded. `f` gets a String [`Series`] of this column's name and returns one value
636    /// per input value.
637    ///
638    /// Only values that rows use are evaluated, so `f` errors exactly when it would on the rows.
639    /// When that is not fewer values than rows, `f` is evaluated on the materialized column. A
640    /// dictionary larger than the rows (a slice or filter) is not a reason: `used_codes` finds the
641    /// used values in time linear in the rows.
642    pub fn apply_elementwise(
643        &self,
644        f: impl FnOnce(&Series) -> PolarsResult<Series>,
645    ) -> PolarsResult<Column> {
646        let max_evaluated = self.len() / 2;
647        let Some((used, mut row_slots)) = self.used_codes(max_evaluated) else {
648            return f(self.as_materialized_series()).map(Column::from);
649        };
650        let null_slot = used.len() as u32;
651
652        let codes = self.codes.rechunk();
653        let validity = codes
654            .downcast_as_array()
655            .validity()
656            .filter(|v| v.unset_bits() > 0);
657        if let Some(v) = validity {
658            for (s, is_valid) in row_slots.iter_mut().zip(v.iter()) {
659                if !is_valid {
660                    *s = null_slot;
661                }
662            }
663        }
664
665        let values = StringChunked::with_chunk(self.name.clone(), self.dict.values.clone());
666        let mut input = unsafe { values.take_unchecked(&IdxCa::from_vec(PlSmallStr::EMPTY, used)) };
667        if validity.is_some() {
668            input.append(&StringChunked::full_null(PlSmallStr::EMPTY, 1))?;
669        }
670        let input = input.into_series();
671        let out = f(&input)?;
672        polars_ensure!(
673            out.len() == input.len(),
674            ComputeError: "elementwise function changed the length of a dictionary column"
675        );
676
677        if out.dtype() == &DataType::String {
678            // Rows whose result is null get a null code.
679            let name = out_name(&input, &out, &self.name);
680            let out = out.str().unwrap().rechunk();
681            let out = out.downcast_as_array();
682            let out_validity = out.validity().filter(|v| v.unset_bits() > 0);
683            let row_validity = out_validity.map(|ov| {
684                row_slots
685                    .iter()
686                    .map(|s| unsafe { ov.get_bit_unchecked(*s as usize) })
687                    .collect::<polars_arrow::bitmap::Bitmap>()
688            });
689            let dict = SharedDictionary::new(out.clone().with_validity(None));
690            let codes =
691                UInt32Chunked::from_vec_validity(PlSmallStr::EMPTY, row_slots, row_validity);
692            // SAFETY: every slot indexes `out`.
693            return Ok(unsafe { DictionaryColumn::new_unchecked(name, dict, codes) }.into_column());
694        }
695
696        #[cfg(feature = "bigidx")]
697        let idx = IdxCa::from_vec(
698            PlSmallStr::EMPTY,
699            row_slots.into_iter().map(|s| s as IdxSize).collect(),
700        );
701        #[cfg(not(feature = "bigidx"))]
702        let idx = IdxCa::from_vec(PlSmallStr::EMPTY, row_slots);
703        // SAFETY: every slot indexes `out`.
704        Ok(unsafe { out.take_unchecked(&idx) }.into_column())
705    }
706
707    /// Checks that the materialized values match the codes.
708    pub fn check_invariants(&self) {
709        let expected = self.to_series();
710        if let Some(m) = self.materialized.get() {
711            assert!(m.equals_missing(&expected));
712        }
713        assert_eq!(expected.len(), self.len());
714    }
715}
716
717/// The name of `out`, which `f` computed from `input`: `name` unless `f` renamed it.
718fn out_name(input: &Series, out: &Series, name: &PlSmallStr) -> PlSmallStr {
719    if out.name() == input.name() {
720        name.clone()
721    } else {
722        out.name().clone()
723    }
724}
725
726impl IntoColumn for DictionaryColumn {
727    #[inline(always)]
728    fn into_column(self) -> Column {
729        Column::Dictionary(self)
730    }
731}
732
733impl From<DictionaryColumn> for Column {
734    #[inline]
735    fn from(value: DictionaryColumn) -> Self {
736        value.into_column()
737    }
738}
739
740/// Whether dictionary-coded String columns are produced and used, `POLARS_DICT_CODES=0` turns them
741/// off.
742pub fn dictionary_codes_enabled() -> bool {
743    static ENABLED: OnceLock<bool> = OnceLock::new();
744    *ENABLED.get_or_init(|| std::env::var("POLARS_DICT_CODES").as_deref() != Ok("0"))
745}
746
747#[cfg(test)]
748mod test {
749    use super::*;
750    use crate::chunked_array::cast::CastOptions;
751    use crate::chunked_array::flags::StatisticsFlags;
752    use crate::frame::ChunkCursor;
753
754    fn dict_column(dict: &[&str], codes: &[Option<u32>]) -> DictionaryColumn {
755        let values = Utf8ViewArray::from_slice_values(dict);
756        let codes = UInt32Chunked::from_iter_options(PlSmallStr::EMPTY, codes.iter().copied());
757        DictionaryColumn::try_new("s".into(), SharedDictionary::new(values), codes).unwrap()
758    }
759
760    fn values(c: &DictionaryColumn) -> Vec<Option<String>> {
761        c.to_series()
762            .str()
763            .unwrap()
764            .iter()
765            .map(|v| v.map(str::to_owned))
766            .collect()
767    }
768
769    #[test]
770    fn try_append_merges_by_value() {
771        let mut a = dict_column(&["x", "y"], &[Some(0), Some(1), None, Some(0)]);
772        let id = a.dict().id();
773        // The same values in another order and another dictionary: nothing is added.
774        let b = dict_column(&["y", "x"], &[Some(0), None, Some(1), Some(1)]);
775        assert!(a.try_append(&b));
776        assert_eq!(a.dict().id(), id);
777        assert_eq!(a.dict().len(), 2);
778        // One new value: it is added once, after the existing ones.
779        let c = dict_column(&["z", "x"], &[Some(0), Some(1), Some(0), Some(0)]);
780        assert!(a.try_append(&c));
781        assert_eq!(a.dict().len(), 3);
782        a.check_invariants();
783        let s = |v: &str| Some(v.to_owned());
784        assert_eq!(
785            values(&a),
786            [
787                s("x"),
788                s("y"),
789                None,
790                s("x"),
791                s("y"),
792                None,
793                s("x"),
794                s("x"),
795                s("z"),
796                s("x"),
797                s("z"),
798                s("z"),
799            ]
800        );
801    }
802
803    #[test]
804    fn try_append_remaps_only_used_codes() {
805        // `b` has fewer rows than dictionary entries, one of its rows is null with a code out of
806        // the used ones, and the unused entries (never looked up) include a value `a` lacks.
807        let mut a = dict_column(
808            &["x", "y", "w"],
809            &[Some(0), Some(1), Some(2), Some(0), Some(1)],
810        );
811        let b = dict_column(
812            &[
813                "unused-1", "z", "x", "unused-2", "unused-3", "y", "unused-4",
814            ],
815            &[Some(1), None, Some(2), Some(5), Some(2)],
816        );
817        assert!(a.try_append(&b));
818        // Only "z" was added: the unused values are not.
819        assert_eq!(a.dict().len(), 4);
820        assert_eq!(a.dict().code_of("unused-1"), None);
821        a.check_invariants();
822        let s = |v: &str| Some(v.to_owned());
823        assert_eq!(values(&a)[5..], [s("z"), None, s("x"), s("y"), s("x")]);
824        // All rows null: nothing is looked up and nothing added.
825        let mut a = dict_column(&["x", "y", "w"], &[Some(0), Some(1), Some(2)]);
826        let b = dict_column(&["p", "q", "r", "s"], &[None, None]);
827        assert!(a.try_append(&b));
828        assert_eq!(a.dict().len(), 3);
829        assert_eq!(values(&a)[3..], [None, None]);
830        a.check_invariants();
831    }
832
833    #[test]
834    fn try_append_to_empty_adopts_the_other_dictionary() {
835        let mut a = dict_column(&["old-1", "old-2"], &[Some(0)]).slice((0usize, 0usize));
836        let b = dict_column(&["x", "y", "z"], &[Some(2), None, Some(0)]);
837        assert!(a.is_empty());
838        assert!(a.try_append(&b));
839        assert_eq!(a.dict().id(), b.dict().id());
840        a.check_invariants();
841        let s = |v: &str| Some(v.to_owned());
842        assert_eq!(values(&a), [s("z"), None, s("x")]);
843        assert_eq!(a.name(), "s");
844    }
845
846    #[test]
847    fn try_append_extends_lookup_and_hashes() {
848        let rs = PlRandomState::default();
849        let mut a = dict_column(&["x", "y"], &[Some(0), Some(1)]);
850        a.dict().hashes(&rs);
851        assert_eq!(a.dict().code_of("y"), Some(1));
852        let b = dict_column(
853            &["z", "a-value-longer-than-a-view", "x"],
854            &[Some(0), Some(1), Some(2)],
855        );
856        assert!(a.try_append(&b));
857        let dict = a.dict();
858        assert_eq!(dict.len(), 4);
859        // The lookup and the hashes were carried into the extended dictionary.
860        assert!(dict.lookup.get().is_some());
861        assert_eq!(dict.code_of("a-value-longer-than-a-view"), Some(3));
862        assert_eq!(dict.code_of("x"), Some(0));
863        assert_eq!(dict.code_of("absent"), None);
864        let cached = dict.cached_hashes(&rs).unwrap();
865        let fresh = SharedDictionary::new(dict.values().clone()).hashes(&rs);
866        assert_eq!(cached.as_slice(), fresh.as_slice());
867        a.check_invariants();
868    }
869
870    #[test]
871    fn compare_length_one_with_longer_constant_broadcasts() {
872        let lhs = Column::from(dict_column(&["a", "b"], &[Some(0)]));
873        let rhs = Column::new_scalar(
874            "c".into(),
875            Scalar::new(DataType::String, AnyValue::StringOwned("a".into())),
876            5,
877        );
878        let out = lhs.equal(&rhs).unwrap();
879        assert_eq!(out.len(), 5);
880        assert!(out.all());
881        let out = rhs.not_equal(&lhs).unwrap();
882        assert_eq!(out.len(), 5);
883        assert!(!out.any());
884    }
885
886    #[cfg(feature = "serde")]
887    #[test]
888    fn serializes_as_series() {
889        let col = Column::from(dict_column(&["a", "b"], &[Some(1), None, Some(0)]));
890        let series = Column::from(col.as_materialized_series().clone());
891        let json = serde_json::to_string(&col).unwrap();
892        assert_eq!(json, serde_json::to_string(&series).unwrap());
893        let back: Column = serde_json::from_str(&json).unwrap();
894        assert!(
895            back.as_materialized_series()
896                .equals_missing(&series.take_materialized_series())
897        );
898    }
899
900    #[test]
901    fn try_append_declines_a_large_dictionary() {
902        let mut a = dict_column(&["a", "b"], &[Some(0), Some(1)]);
903        let b = dict_column(&["c", "d", "e"], &[Some(0)]);
904        assert!(!a.try_append(&b));
905        assert_eq!(a.len(), 2);
906        assert_eq!(a.dict().len(), 2);
907    }
908
909    #[test]
910    fn try_append_bounds_dictionary_extension() {
911        let a = dict_column(&["a", "b", "c"], &[Some(0), Some(1), Some(2)]);
912        let b = dict_column(&["d"], &[Some(0), None, Some(0)]);
913        let mut at_limit = a.clone();
914        assert!(at_limit.try_append(&b));
915        assert_eq!(at_limit.dict().len(), 4);
916        let expected = values(&at_limit);
917
918        let mut above_limit = a.clone();
919        above_limit.set_sorted_flag(IsSorted::Ascending);
920        above_limit.as_materialized_series();
921        let smaller_b = b.slice(Slice::head(2));
922        assert!(!above_limit.try_append(&smaller_b));
923        assert_eq!(above_limit.dict().id(), a.dict().id());
924        assert_eq!(values(&above_limit), values(&a));
925        assert_eq!(above_limit.is_sorted_flag(), IsSorted::Ascending);
926        assert!(above_limit.lazy_as_materialized_series().is_some());
927
928        let mut col = Column::from(above_limit);
929        col.append(&Column::from(smaller_b)).unwrap();
930        assert!(col.as_dictionary_column().is_none());
931        assert_eq!(
932            col.str().unwrap().iter().collect::<Vec<_>>(),
933            expected[..5]
934                .iter()
935                .map(Option::as_deref)
936                .collect::<Vec<_>>(),
937        );
938    }
939
940    #[test]
941    fn try_append_reuses_dictionary_above_extension_bound() {
942        let mut a = dict_column(&["a", "b", "c"], &[Some(0), Some(1), Some(2)]);
943        let same_dict = a.slice((1usize, 1));
944        let overlapping = dict_column(&["c"], &[Some(0)]);
945        let id = a.dict().id();
946        assert!(a.try_append(&same_dict));
947        assert!(a.try_append(&overlapping));
948        assert_eq!(a.dict().id(), id);
949        assert_eq!(
950            a.as_materialized_series()
951                .str()
952                .unwrap()
953                .iter()
954                .collect::<Vec<_>>(),
955            [Some("a"), Some("b"), Some("c"), Some("b"), Some("c")],
956        );
957    }
958
959    #[test]
960    fn try_new_ignores_sorted_flag() {
961        let values = Utf8ViewArray::from_slice_values(["a"]);
962        let mut codes = UInt32Chunked::from_slice(PlSmallStr::EMPTY, &[5, 0]);
963        codes.set_sorted_flag(IsSorted::Ascending);
964        let dict = SharedDictionary::new(values);
965        assert!(DictionaryColumn::try_new("s".into(), dict, codes).is_err());
966    }
967
968    #[test]
969    fn clear_keeps_a_dictionary_column_without_its_dictionary() {
970        let col = Column::from(dict_column(&["x", "y"], &[Some(0), Some(1)]));
971        let mut empty = col.clear();
972        let d = empty.as_dictionary_column().unwrap();
973        assert_eq!(d.dict().len(), 0);
974        assert_eq!(empty.dtype(), &DataType::String);
975        assert_eq!(empty.len(), 0);
976        // It adopts the dictionary of the next column appended, and stays coded.
977        empty.append(&col).unwrap();
978        let d = empty.as_dictionary_column().unwrap();
979        assert_eq!(d.dict().len(), 2);
980        assert_eq!(empty.str().unwrap().get(1), Some("y"));
981    }
982
983    #[test]
984    fn try_append_empty_other_is_a_no_op() {
985        let mut a = dict_column(&["x", "y", "z"], &[Some(0)]);
986        let id = a.dict().id();
987        let b = dict_column(&["q"], &[]);
988        assert!(a.try_append(&b));
989        assert_eq!(a.dict().id(), id);
990        assert_eq!(a.len(), 1);
991    }
992
993    #[test]
994    fn apply_elementwise_on_a_filtered_big_dictionary_stays_coded() {
995        let dict: Vec<String> = (0..2000).map(|i| format!("value-{i}")).collect();
996        let dict: Vec<&str> = dict.iter().map(String::as_str).collect();
997        let codes: Vec<Option<u32>> = (0..200).map(|i| Some((i % 5) * 7)).collect();
998        let col = dict_column(&dict, &codes);
999        let out = col.apply_elementwise(|s| Ok(s.clone())).unwrap();
1000        // Only the 5 used values were evaluated: the result has a 5-value dictionary.
1001        let d = out.as_dictionary_column().expect("stays coded");
1002        assert_eq!(d.dict().len(), 5);
1003        assert_eq!(out.str().unwrap().get(8), Some("value-21"));
1004    }
1005
1006    #[test]
1007    fn strict_cast_counts_rows() {
1008        let codes: Vec<Option<u32>> = (0..100).map(|i| Some(u32::from(i >= 90))).collect();
1009        let col = Column::from(dict_column(&["bad", "1"], &codes));
1010        let err = col.strict_cast(&DataType::Int64).unwrap_err().to_string();
1011        assert!(err.contains("90 out of 100"), "{err}");
1012        let err = col
1013            .cast_with_options(&DataType::Int64, CastOptions::Strict)
1014            .unwrap_err()
1015            .to_string();
1016        assert!(err.contains("90 out of 100"), "{err}");
1017        let ok = Column::from(dict_column(&["2", "1"], &codes));
1018        assert_eq!(
1019            ok.strict_cast(&DataType::Int64)
1020                .unwrap()
1021                .i64()
1022                .unwrap()
1023                .get(95),
1024            Some(1)
1025        );
1026    }
1027
1028    #[test]
1029    #[cfg(feature = "dtype-struct")]
1030    fn strict_cast_to_nested_checks_the_fields() {
1031        let col = Column::from(dict_column(&["bad", "1"], &[Some(0), Some(1), Some(1)]));
1032        let dtype = DataType::Struct(vec![Field::new("n".into(), DataType::Int64)]);
1033        // The equivalent String column raises; so must the dictionary column.
1034        assert!(col.as_materialized_series().strict_cast(&dtype).is_err());
1035        assert!(col.strict_cast(&dtype).is_err());
1036        assert!(col.cast_with_options(&dtype, CastOptions::Strict).is_err());
1037    }
1038
1039    #[test]
1040    fn split_chunks_of_a_dictionary_only_frame() {
1041        let values = Utf8ViewArray::from_slice_values(["x", "y"]);
1042        let mut codes = UInt32Chunked::from_slice(PlSmallStr::EMPTY, &[0, 1, 0]);
1043        codes
1044            .append(&UInt32Chunked::from_slice(PlSmallStr::EMPTY, &[1, 1]))
1045            .unwrap();
1046        assert_eq!(codes.chunks().len(), 2);
1047        let col =
1048            DictionaryColumn::try_new("s".into(), SharedDictionary::new(values), codes).unwrap();
1049        let mut df = DataFrame::new_infer_height(vec![Column::from(col)]).unwrap();
1050        assert_eq!(df.first_col_n_chunks(), 2);
1051        let parts: Vec<DataFrame> = df.split_chunks().collect();
1052        assert_eq!(parts.len(), 2);
1053        assert_eq!(parts[0].height(), 3);
1054        assert_eq!(parts[1].height(), 2);
1055        for p in &parts {
1056            assert_eq!(p.columns()[0].len(), p.height());
1057        }
1058        let last = parts[1].columns()[0]
1059            .as_materialized_series()
1060            .str()
1061            .unwrap()
1062            .clone();
1063        assert_eq!(last.get(0), Some("y"));
1064    }
1065
1066    #[test]
1067    fn chunk_iterators_and_split_follow_dictionary_code_chunks() {
1068        let values = Utf8ViewArray::from_slice_values(["x", "y"]);
1069        let mut codes = UInt32Chunked::from_vec(PlSmallStr::EMPTY, vec![0; 1000]);
1070        codes
1071            .append(&UInt32Chunked::from_vec(PlSmallStr::EMPTY, vec![1; 1000]))
1072            .unwrap();
1073        let col =
1074            DictionaryColumn::try_new("s".into(), SharedDictionary::new(values), codes).unwrap();
1075        let df = DataFrame::new_infer_height(vec![Column::from(col)]).unwrap();
1076        assert_eq!(df.iter_chunks(CompatLevel::newest(), false).count(), 2);
1077        assert_eq!(df.iter_chunks_physical().count(), 2);
1078        let parts = crate::utils::split(&df, 2);
1079        assert_eq!(parts.len(), 2);
1080        assert!(parts.iter().all(|p| p.height() == 1000));
1081        let parts = crate::utils::split_and_flatten(&df, 2);
1082        assert_eq!(parts.len(), 2);
1083    }
1084
1085    #[test]
1086    fn chunk_cursor_of_an_unaligned_frame_follows_the_series_chunks() {
1087        let values = Utf8ViewArray::from_slice_values(["x", "y"]);
1088        let mut codes = UInt32Chunked::from_vec(PlSmallStr::EMPTY, vec![0; 1000]);
1089        codes
1090            .append(&UInt32Chunked::from_vec(PlSmallStr::EMPTY, vec![1; 1000]))
1091            .unwrap();
1092        let d =
1093            DictionaryColumn::try_new("s".into(), SharedDictionary::new(values), codes).unwrap();
1094        let ints = Column::new("i".into(), (0..2000i64).collect::<Vec<_>>());
1095        let df = DataFrame::new_infer_height(vec![Column::from(d), ints]).unwrap();
1096        // Unaligned, as callers of `iter_chunks` that rechunk lazily may hold it: the cursor must
1097        // follow the series column (as the batches select its chunks by index).
1098        assert_eq!(df.first_col_n_chunks(), 1);
1099        assert_eq!(df.first_col_chunk_lengths().collect::<Vec<_>>(), [2000]);
1100        let mut cursor = ChunkCursor::new(&df);
1101        assert_eq!(cursor.next(), Some((0, 2000)));
1102        assert_eq!(cursor.next(), None);
1103    }
1104
1105    #[test]
1106    fn sorted_flag() {
1107        let mut a = dict_column(&["b", "a"], &[Some(1), Some(1), Some(0)]);
1108        assert_eq!(a.is_sorted_flag(), IsSorted::Not);
1109        a.set_sorted_flag(IsSorted::Ascending);
1110        assert_eq!(a.slice((1usize, 2)).is_sorted_flag(), IsSorted::Ascending);
1111        assert_eq!(a.rechunk().is_sorted_flag(), IsSorted::Ascending);
1112        assert_eq!(a.reverse().is_sorted_flag(), IsSorted::Descending);
1113        assert_eq!(
1114            a.as_materialized_series().is_sorted_flag(),
1115            IsSorted::Ascending
1116        );
1117        let idx = IdxCa::from_vec(PlSmallStr::EMPTY, vec![2, 0]);
1118        assert_eq!(
1119            unsafe { a.take_unchecked(&idx) }.is_sorted_flag(),
1120            IsSorted::Not
1121        );
1122        let b = a.clone();
1123        assert!(a.try_append(&b));
1124        assert_eq!(a.is_sorted_flag(), IsSorted::Not);
1125
1126        let mut col = Column::from(dict_column(&["a"], &[Some(0)]));
1127        col.set_sorted_flag(IsSorted::Descending);
1128        assert_eq!(col.is_sorted_flag(), IsSorted::Descending);
1129        assert!(col.get_flags().contains(StatisticsFlags::IS_SORTED_DSC));
1130    }
1131}