You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by tu...@apache.org on 2022/07/29 08:05:07 UTC

[arrow-rs] branch master updated: Faster parquet DictEncoder (~20%) (#2123)

This is an automated email from the ASF dual-hosted git repository.

tustvold pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git


The following commit(s) were added to refs/heads/master by this push:
     new 6ce4c4ebf Faster parquet DictEncoder (~20%) (#2123)
6ce4c4ebf is described below

commit 6ce4c4ebf2d4c0a27feb7f341c6eee2525a1cce7
Author: Raphael Taylor-Davies <17...@users.noreply.github.com>
AuthorDate: Fri Jul 29 09:05:02 2022 +0100

    Faster parquet DictEncoder (~20%) (#2123)
    
    * Faster parquet DictEncoder
    
    * Reserve dictionary capacity
    
    * Split out interner
    
    * Fix RAT
---
 parquet/Cargo.toml                                 |   2 +
 parquet/src/encodings/encoding/dict_encoder.rs     | 185 +++++++++++++++++
 .../src/encodings/{encoding.rs => encoding/mod.rs} | 229 +--------------------
 parquet/src/util/hash_util.rs                      | 162 ---------------
 parquet/src/util/interner.rs                       |  94 +++++++++
 parquet/src/util/mod.rs                            |   4 +-
 6 files changed, 290 insertions(+), 386 deletions(-)

diff --git a/parquet/Cargo.toml b/parquet/Cargo.toml
index eb6207733..a0e164150 100644
--- a/parquet/Cargo.toml
+++ b/parquet/Cargo.toml
@@ -30,6 +30,7 @@ edition = "2021"
 rust-version = "1.62"
 
 [dependencies]
+ahash = "0.7"
 parquet-format = { version = "4.0.0", default-features = false }
 bytes = { version = "1.1", default-features = false, features = ["std"] }
 byteorder = { version = "1", default-features = false }
@@ -49,6 +50,7 @@ serde_json = { version = "1.0", default-features = false, features = ["std"], op
 rand = { version = "0.8", default-features = false, features = ["std", "std_rng"] }
 futures = { version = "0.3", default-features = false, features = ["std"], optional = true }
 tokio = { version = "1.0", optional = true, default-features = false, features = ["macros", "fs", "rt", "io-util"] }
+hashbrown = { version = "0.12", default-features = false }
 
 [dev-dependencies]
 base64 = { version = "0.13", default-features = false, features = ["std"] }
diff --git a/parquet/src/encodings/encoding/dict_encoder.rs b/parquet/src/encodings/encoding/dict_encoder.rs
new file mode 100644
index 000000000..7bf983254
--- /dev/null
+++ b/parquet/src/encodings/encoding/dict_encoder.rs
@@ -0,0 +1,185 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// ----------------------------------------------------------------------
+// Dictionary encoding
+
+use crate::basic::{Encoding, Type};
+use crate::data_type::private::ParquetValueType;
+use crate::data_type::{AsBytes, DataType};
+use crate::encodings::encoding::{Encoder, PlainEncoder};
+use crate::encodings::rle::RleEncoder;
+use crate::errors::{ParquetError, Result};
+use crate::schema::types::ColumnDescPtr;
+use crate::util::bit_util::num_required_bits;
+use crate::util::interner::{Interner, Storage};
+use crate::util::memory::ByteBufferPtr;
+use std::io::Write;
+
+#[derive(Debug)]
+struct KeyStorage<T: DataType> {
+    uniques: Vec<T::T>,
+
+    size_in_bytes: usize,
+
+    type_length: usize,
+}
+
+impl<T: DataType> Storage for KeyStorage<T> {
+    type Key = u64;
+    type Value = T::T;
+
+    fn get(&self, idx: Self::Key) -> &Self::Value {
+        &self.uniques[idx as usize]
+    }
+
+    fn push(&mut self, value: &Self::Value) -> Self::Key {
+        let (base_size, num_elements) = value.dict_encoding_size();
+
+        let unique_size = match T::get_physical_type() {
+            Type::BYTE_ARRAY => base_size + num_elements,
+            Type::FIXED_LEN_BYTE_ARRAY => self.type_length,
+            _ => base_size,
+        };
+        self.size_in_bytes += unique_size;
+
+        let key = self.uniques.len() as u64;
+        self.uniques.push(value.clone());
+        key
+    }
+}
+
+/// Dictionary encoder.
+/// The dictionary encoding builds a dictionary of values encountered in a given column.
+/// The dictionary page is written first, before the data pages of the column chunk.
+///
+/// Dictionary page format: the entries in the dictionary - in dictionary order -
+/// using the plain encoding.
+///
+/// Data page format: the bit width used to encode the entry ids stored as 1 byte
+/// (max bit width = 32), followed by the values encoded using RLE/Bit packed described
+/// above (with the given bit width).
+pub struct DictEncoder<T: DataType> {
+    /// Descriptor for the column to be encoded.
+    desc: ColumnDescPtr,
+
+    interner: Interner<KeyStorage<T>>,
+
+    /// The buffered indices
+    indices: Vec<u64>,
+}
+
+impl<T: DataType> DictEncoder<T> {
+    /// Creates new dictionary encoder.
+    pub fn new(desc: ColumnDescPtr) -> Self {
+        let storage = KeyStorage {
+            uniques: vec![],
+            size_in_bytes: 0,
+            type_length: desc.type_length() as usize,
+        };
+
+        Self {
+            desc,
+            interner: Interner::new(storage),
+            indices: vec![],
+        }
+    }
+
+    /// Returns true if dictionary entries are sorted, false otherwise.
+    pub fn is_sorted(&self) -> bool {
+        // Sorting is not supported currently.
+        false
+    }
+
+    /// Returns number of unique values (keys) in the dictionary.
+    pub fn num_entries(&self) -> usize {
+        self.interner.storage().uniques.len()
+    }
+
+    /// Returns size of unique values (keys) in the dictionary, in bytes.
+    pub fn dict_encoded_size(&self) -> usize {
+        self.interner.storage().size_in_bytes
+    }
+
+    /// Writes out the dictionary values with PLAIN encoding in a byte buffer, and return
+    /// the result.
+    pub fn write_dict(&self) -> Result<ByteBufferPtr> {
+        let mut plain_encoder = PlainEncoder::<T>::new(self.desc.clone(), vec![]);
+        plain_encoder.put(&self.interner.storage().uniques)?;
+        plain_encoder.flush_buffer()
+    }
+
+    /// Writes out the dictionary values with RLE encoding in a byte buffer, and return
+    /// the result.
+    pub fn write_indices(&mut self) -> Result<ByteBufferPtr> {
+        let buffer_len = self.estimated_data_encoded_size();
+        let mut buffer = vec![0; buffer_len];
+        buffer[0] = self.bit_width() as u8;
+
+        // Write bit width in the first byte
+        buffer.write_all((self.bit_width() as u8).as_bytes())?;
+        let mut encoder = RleEncoder::new_from_buf(self.bit_width(), buffer, 1);
+        for index in &self.indices {
+            if !encoder.put(*index as u64)? {
+                return Err(general_err!("Encoder doesn't have enough space"));
+            }
+        }
+        self.indices.clear();
+        Ok(ByteBufferPtr::new(encoder.consume()?))
+    }
+
+    fn put_one(&mut self, value: &T::T) {
+        self.indices.push(self.interner.intern(value));
+    }
+
+    #[inline]
+    fn bit_width(&self) -> u8 {
+        let num_entries = self.num_entries();
+        if num_entries <= 1 {
+            num_entries as u8
+        } else {
+            num_required_bits(num_entries as u64 - 1)
+        }
+    }
+}
+
+impl<T: DataType> Encoder<T> for DictEncoder<T> {
+    fn put(&mut self, values: &[T::T]) -> Result<()> {
+        self.indices.reserve(values.len());
+        for i in values {
+            self.put_one(i)
+        }
+        Ok(())
+    }
+
+    // Performance Note:
+    // As far as can be seen these functions are rarely called and as such we can hint to the
+    // compiler that they dont need to be folded into hot locations in the final output.
+    fn encoding(&self) -> Encoding {
+        Encoding::PLAIN_DICTIONARY
+    }
+
+    fn estimated_data_encoded_size(&self) -> usize {
+        let bit_width = self.bit_width();
+        1 + RleEncoder::min_buffer_size(bit_width)
+            + RleEncoder::max_buffer_size(bit_width, self.indices.len())
+    }
+
+    fn flush_buffer(&mut self) -> Result<ByteBufferPtr> {
+        self.write_indices()
+    }
+}
diff --git a/parquet/src/encodings/encoding.rs b/parquet/src/encodings/encoding/mod.rs
similarity index 84%
rename from parquet/src/encodings/encoding.rs
rename to parquet/src/encodings/encoding/mod.rs
index 651635af5..5cb94b7c0 100644
--- a/parquet/src/encodings/encoding.rs
+++ b/parquet/src/encodings/encoding/mod.rs
@@ -17,7 +17,7 @@
 
 //! Contains all supported encoders for Parquet.
 
-use std::{cmp, io::Write, marker::PhantomData};
+use std::{cmp, marker::PhantomData};
 
 use crate::basic::*;
 use crate::data_type::private::ParquetValueType;
@@ -27,10 +27,13 @@ use crate::errors::{ParquetError, Result};
 use crate::schema::types::ColumnDescPtr;
 use crate::util::{
     bit_util::{self, num_required_bits, BitWriter},
-    hash_util,
     memory::ByteBufferPtr,
 };
 
+pub use dict_encoder::DictEncoder;
+
+mod dict_encoder;
+
 // ----------------------------------------------------------------------
 // Encoders
 
@@ -154,225 +157,6 @@ impl<T: DataType> Encoder<T> for PlainEncoder<T> {
     }
 }
 
-// ----------------------------------------------------------------------
-// Dictionary encoding
-
-const INITIAL_HASH_TABLE_SIZE: usize = 1024;
-const MAX_HASH_LOAD: f32 = 0.7;
-const HASH_SLOT_EMPTY: i32 = -1;
-
-/// Dictionary encoder.
-/// The dictionary encoding builds a dictionary of values encountered in a given column.
-/// The dictionary page is written first, before the data pages of the column chunk.
-///
-/// Dictionary page format: the entries in the dictionary - in dictionary order -
-/// using the plain encoding.
-///
-/// Data page format: the bit width used to encode the entry ids stored as 1 byte
-/// (max bit width = 32), followed by the values encoded using RLE/Bit packed described
-/// above (with the given bit width).
-pub struct DictEncoder<T: DataType> {
-    // Descriptor for the column to be encoded.
-    desc: ColumnDescPtr,
-
-    // Size of the table. **Must be** a power of 2.
-    hash_table_size: usize,
-
-    // Store `hash_table_size` - 1, so that `j & mod_bitmask` is equivalent to
-    // `j % hash_table_size`, but uses far fewer CPU cycles.
-    mod_bitmask: u32,
-
-    // Stores indices which map (many-to-one) to the values in the `uniques` array.
-    // Here we are using fix-sized array with linear probing.
-    // A slot with `HASH_SLOT_EMPTY` indicates the slot is not currently occupied.
-    hash_slots: Vec<i32>,
-
-    // Indices that have not yet be written out by `write_indices()`.
-    buffered_indices: Vec<i32>,
-
-    // The unique observed values.
-    uniques: Vec<T::T>,
-
-    // Size in bytes needed to encode this dictionary.
-    uniques_size_in_bytes: usize,
-}
-
-impl<T: DataType> DictEncoder<T> {
-    /// Creates new dictionary encoder.
-    pub fn new(desc: ColumnDescPtr) -> Self {
-        let mut slots = vec![];
-        slots.resize(INITIAL_HASH_TABLE_SIZE, -1);
-        Self {
-            desc,
-            hash_table_size: INITIAL_HASH_TABLE_SIZE,
-            mod_bitmask: (INITIAL_HASH_TABLE_SIZE - 1) as u32,
-            hash_slots: slots,
-            buffered_indices: vec![],
-            uniques: vec![],
-            uniques_size_in_bytes: 0,
-        }
-    }
-
-    /// Returns true if dictionary entries are sorted, false otherwise.
-    #[inline]
-    pub fn is_sorted(&self) -> bool {
-        // Sorting is not supported currently.
-        false
-    }
-
-    /// Returns number of unique values (keys) in the dictionary.
-    pub fn num_entries(&self) -> usize {
-        self.uniques.len()
-    }
-
-    /// Returns size of unique values (keys) in the dictionary, in bytes.
-    pub fn dict_encoded_size(&self) -> usize {
-        self.uniques_size_in_bytes
-    }
-
-    /// Writes out the dictionary values with PLAIN encoding in a byte buffer, and return
-    /// the result.
-    #[inline]
-    pub fn write_dict(&self) -> Result<ByteBufferPtr> {
-        let mut plain_encoder = PlainEncoder::<T>::new(self.desc.clone(), vec![]);
-        plain_encoder.put(&self.uniques)?;
-        plain_encoder.flush_buffer()
-    }
-
-    /// Writes out the dictionary values with RLE encoding in a byte buffer, and return
-    /// the result.
-    pub fn write_indices(&mut self) -> Result<ByteBufferPtr> {
-        // TODO: the caller should allocate the buffer
-        let buffer_len = self.estimated_data_encoded_size();
-        let mut buffer: Vec<u8> = vec![0; buffer_len as usize];
-        buffer[0] = self.bit_width() as u8;
-
-        // Write bit width in the first byte
-        buffer.write_all((self.bit_width() as u8).as_bytes())?;
-        let mut encoder = RleEncoder::new_from_buf(self.bit_width(), buffer, 1);
-        for index in &self.buffered_indices {
-            if !encoder.put(*index as u64)? {
-                return Err(general_err!("Encoder doesn't have enough space"));
-            }
-        }
-        self.buffered_indices.clear();
-        Ok(ByteBufferPtr::new(encoder.consume()?))
-    }
-
-    #[inline]
-    #[allow(clippy::unnecessary_wraps)]
-    fn put_one(&mut self, value: &T::T) -> Result<()> {
-        let mut j = (hash_util::hash(value, 0) & self.mod_bitmask) as usize;
-        let mut index = self.hash_slots[j];
-
-        while index != HASH_SLOT_EMPTY && self.uniques[index as usize] != *value {
-            j += 1;
-            if j == self.hash_table_size {
-                j = 0;
-            }
-            index = self.hash_slots[j];
-        }
-
-        if index == HASH_SLOT_EMPTY {
-            index = self.insert_fresh_slot(j, value.clone());
-        }
-
-        self.buffered_indices.push(index);
-        Ok(())
-    }
-
-    #[inline(never)]
-    fn insert_fresh_slot(&mut self, slot: usize, value: T::T) -> i32 {
-        let index = self.uniques.len() as i32;
-        self.hash_slots[slot] = index;
-
-        let (base_size, num_elements) = value.dict_encoding_size();
-
-        let unique_size = match T::get_physical_type() {
-            Type::BYTE_ARRAY => base_size + num_elements,
-            Type::FIXED_LEN_BYTE_ARRAY => self.desc.type_length() as usize,
-            _ => base_size,
-        };
-
-        self.uniques_size_in_bytes += unique_size;
-        self.uniques.push(value);
-
-        if self.uniques.len() > (self.hash_table_size as f32 * MAX_HASH_LOAD) as usize {
-            self.double_table_size();
-        }
-
-        index
-    }
-
-    #[inline]
-    fn bit_width(&self) -> u8 {
-        let num_entries = self.uniques.len();
-        if num_entries <= 1 {
-            num_entries as u8
-        } else {
-            num_required_bits(num_entries as u64 - 1)
-        }
-    }
-
-    fn double_table_size(&mut self) {
-        let new_size = self.hash_table_size * 2;
-        let mut new_hash_slots = vec![];
-        new_hash_slots.resize(new_size, HASH_SLOT_EMPTY);
-        for i in 0..self.hash_table_size {
-            let index = self.hash_slots[i];
-            if index == HASH_SLOT_EMPTY {
-                continue;
-            }
-            let value = &self.uniques[index as usize];
-            let mut j = (hash_util::hash(value, 0) & ((new_size - 1) as u32)) as usize;
-            let mut slot = new_hash_slots[j];
-            while slot != HASH_SLOT_EMPTY && self.uniques[slot as usize] != *value {
-                j += 1;
-                if j == new_size {
-                    j = 0;
-                }
-                slot = new_hash_slots[j];
-            }
-
-            new_hash_slots[j] = index;
-        }
-
-        self.hash_table_size = new_size;
-        self.mod_bitmask = (new_size - 1) as u32;
-        self.hash_slots = new_hash_slots;
-    }
-}
-
-impl<T: DataType> Encoder<T> for DictEncoder<T> {
-    #[inline]
-    fn put(&mut self, values: &[T::T]) -> Result<()> {
-        for i in values {
-            self.put_one(i)?
-        }
-        Ok(())
-    }
-
-    // Performance Note:
-    // As far as can be seen these functions are rarely called and as such we can hint to the
-    // compiler that they dont need to be folded into hot locations in the final output.
-    #[cold]
-    fn encoding(&self) -> Encoding {
-        Encoding::PLAIN_DICTIONARY
-    }
-
-    #[inline]
-    fn estimated_data_encoded_size(&self) -> usize {
-        let bit_width = self.bit_width();
-        1 + RleEncoder::min_buffer_size(bit_width)
-            + RleEncoder::max_buffer_size(bit_width, self.buffered_indices.len())
-    }
-
-    #[inline]
-    fn flush_buffer(&mut self) -> Result<ByteBufferPtr> {
-        self.write_indices()
-    }
-}
-
 // ----------------------------------------------------------------------
 // RLE encoding
 
@@ -587,7 +371,8 @@ impl<T: DataType> DeltaBitPackEncoder<T> {
             }
 
             // Compute bit width to store (max_delta - min_delta)
-            let bit_width = num_required_bits(self.subtract_u64(max_delta, min_delta)) as usize;
+            let bit_width =
+                num_required_bits(self.subtract_u64(max_delta, min_delta)) as usize;
             self.bit_writer.write_at(offset + i, bit_width as u8);
 
             // Encode values in current mini block using min_delta and bit_width
diff --git a/parquet/src/util/hash_util.rs b/parquet/src/util/hash_util.rs
deleted file mode 100644
index dd23e7a65..000000000
--- a/parquet/src/util/hash_util.rs
+++ /dev/null
@@ -1,162 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements.  See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership.  The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License.  You may obtain a copy of the License at
-//
-//   http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied.  See the License for the
-// specific language governing permissions and limitations
-// under the License.
-
-use crate::data_type::AsBytes;
-
-/// Computes hash value for `data`, with a seed value `seed`.
-/// The data type `T` must implement the `AsBytes` trait.
-pub fn hash<T: AsBytes>(data: &T, seed: u32) -> u32 {
-    hash_(data.as_bytes(), seed)
-}
-
-fn hash_(data: &[u8], seed: u32) -> u32 {
-    #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
-    {
-        if is_x86_feature_detected!("sse4.2") {
-            unsafe { crc32_hash(data, seed) }
-        } else {
-            murmur_hash2_64a(data, seed as u64) as u32
-        }
-    }
-
-    #[cfg(any(
-        target_arch = "aarch64",
-        target_arch = "arm",
-        target_arch = "riscv64",
-        target_arch = "wasm32"
-    ))]
-    {
-        murmur_hash2_64a(data, seed as u64) as u32
-    }
-}
-
-const MURMUR_PRIME: u64 = 0xc6a4a7935bd1e995;
-const MURMUR_R: i32 = 47;
-
-/// Rust implementation of MurmurHash2, 64-bit version for 64-bit platforms
-fn murmur_hash2_64a(data_bytes: &[u8], seed: u64) -> u64 {
-    let len = data_bytes.len();
-    let len_64 = (len / 8) * 8;
-
-    let mut h = seed ^ (MURMUR_PRIME.wrapping_mul(data_bytes.len() as u64));
-    for mut k in data_bytes
-        .chunks_exact(8)
-        .map(|chunk| u64::from_ne_bytes(chunk.try_into().unwrap()))
-    {
-        k = k.wrapping_mul(MURMUR_PRIME);
-        k ^= k >> MURMUR_R;
-        k = k.wrapping_mul(MURMUR_PRIME);
-        h ^= k;
-        h = h.wrapping_mul(MURMUR_PRIME);
-    }
-
-    let data2 = &data_bytes[len_64..];
-
-    let v = len & 7;
-    if v == 7 {
-        h ^= (data2[6] as u64) << 48;
-    }
-    if v >= 6 {
-        h ^= (data2[5] as u64) << 40;
-    }
-    if v >= 5 {
-        h ^= (data2[4] as u64) << 32;
-    }
-    if v >= 4 {
-        h ^= (data2[3] as u64) << 24;
-    }
-    if v >= 3 {
-        h ^= (data2[2] as u64) << 16;
-    }
-    if v >= 2 {
-        h ^= (data2[1] as u64) << 8;
-    }
-    if v >= 1 {
-        h ^= data2[0] as u64;
-    }
-    if v > 0 {
-        h = h.wrapping_mul(MURMUR_PRIME);
-    }
-
-    h ^= h >> MURMUR_R;
-    h = h.wrapping_mul(MURMUR_PRIME);
-    h ^= h >> MURMUR_R;
-    h
-}
-
-/// CRC32 hash implementation using SSE4 instructions. Borrowed from Impala.
-#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
-#[target_feature(enable = "sse4.2")]
-unsafe fn crc32_hash(bytes: &[u8], seed: u32) -> u32 {
-    #[cfg(target_arch = "x86")]
-    use std::arch::x86::*;
-    #[cfg(target_arch = "x86_64")]
-    use std::arch::x86_64::*;
-
-    let mut hash = seed;
-    for chunk in bytes
-        .chunks_exact(4)
-        .map(|chunk| u32::from_le_bytes(chunk.try_into().unwrap()))
-    {
-        hash = _mm_crc32_u32(hash, chunk);
-    }
-
-    let remainder = bytes.len() % 4;
-
-    for byte in &bytes[bytes.len() - remainder..] {
-        hash = _mm_crc32_u8(hash, *byte);
-    }
-
-    // The lower half of the CRC hash has poor uniformity, so swap the halves
-    // for anyone who only uses the first several bits of the hash.
-    hash = (hash << 16) | (hash >> 16);
-    hash
-}
-
-#[cfg(test)]
-mod tests {
-    use super::*;
-
-    #[test]
-    fn test_murmur2_64a() {
-        let result = murmur_hash2_64a(b"hello", 123);
-        assert_eq!(result, 2597646618390559622);
-
-        let result = murmur_hash2_64a(b"helloworld", 123);
-        assert_eq!(result, 4934371746140206573);
-
-        let result = murmur_hash2_64a(b"helloworldparquet", 123);
-        assert_eq!(result, 2392198230801491746);
-    }
-
-    #[test]
-    #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
-    fn test_crc32() {
-        if is_x86_feature_detected!("sse4.2") {
-            unsafe {
-                let result = crc32_hash(b"hello", 123);
-                assert_eq!(result, 3359043980);
-
-                let result = crc32_hash(b"helloworld", 123);
-                assert_eq!(result, 3971745255);
-
-                let result = crc32_hash(b"helloworldparquet", 123);
-                assert_eq!(result, 1124504676);
-            }
-        }
-    }
-}
diff --git a/parquet/src/util/interner.rs b/parquet/src/util/interner.rs
new file mode 100644
index 000000000..e64ae0179
--- /dev/null
+++ b/parquet/src/util/interner.rs
@@ -0,0 +1,94 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use crate::data_type::AsBytes;
+use hashbrown::hash_map::RawEntryMut;
+use hashbrown::HashMap;
+use std::hash::Hash;
+
+/// Storage trait for [`Interner`]
+pub trait Storage {
+    type Key: Copy;
+
+    type Value: AsBytes + PartialEq + ?Sized;
+
+    /// Gets an element by its key
+    fn get(&self, idx: Self::Key) -> &Self::Value;
+
+    /// Adds a new element, returning the key
+    fn push(&mut self, value: &Self::Value) -> Self::Key;
+}
+
+/// A generic value interner supporting various different [`Storage`]
+pub struct Interner<S: Storage> {
+    state: ahash::RandomState,
+
+    /// Used to provide a lookup from value to unique value
+    ///
+    /// Note: `S::Key`'s hash implementation is not used, instead the raw entry
+    /// API is used to store keys w.r.t the hash of the strings themselves
+    ///
+    dedup: HashMap<S::Key, (), ()>,
+
+    storage: S,
+}
+
+impl<S: Storage> Interner<S> {
+    /// Create a new `Interner` with the provided storage
+    pub fn new(storage: S) -> Self {
+        Self {
+            state: Default::default(),
+            dedup: Default::default(),
+            storage,
+        }
+    }
+
+    /// Intern the value, returning the interned key, and if this was a new value
+    pub fn intern(&mut self, value: &S::Value) -> S::Key {
+        let hash = compute_hash(&self.state, value);
+
+        let entry = self
+            .dedup
+            .raw_entry_mut()
+            .from_hash(hash, |index| value == self.storage.get(*index));
+
+        match entry {
+            RawEntryMut::Occupied(entry) => *entry.into_key(),
+            RawEntryMut::Vacant(entry) => {
+                let key = self.storage.push(value);
+
+                *entry
+                    .insert_with_hasher(hash, key, (), |key| {
+                        compute_hash(&self.state, self.storage.get(*key))
+                    })
+                    .0
+            }
+        }
+    }
+
+    /// Returns the storage for this interner
+    pub fn storage(&self) -> &S {
+        &self.storage
+    }
+}
+
+fn compute_hash<T: AsBytes + ?Sized>(state: &ahash::RandomState, value: &T) -> u64 {
+    use std::hash::{BuildHasher, Hasher};
+    let mut hasher = state.build_hasher();
+    value.as_bytes().hash(&mut hasher);
+    hasher.finish()
+}
diff --git a/parquet/src/util/mod.rs b/parquet/src/util/mod.rs
index b49e32516..01ac39116 100644
--- a/parquet/src/util/mod.rs
+++ b/parquet/src/util/mod.rs
@@ -21,10 +21,10 @@ pub mod memory;
 pub mod bit_util;
 mod bit_packing;
 pub mod cursor;
-pub mod hash_util;
+pub(crate) mod interner;
+pub(crate) mod page_util;
 #[cfg(any(test, feature = "test_common"))]
 pub(crate) mod test_common;
-pub(crate)mod page_util;
 
 #[cfg(any(test, feature = "test_common"))]
 pub use self::test_common::page_util::{