Dictionary Encoding for Column Compression

Recap: Why Compression Matters in Column Stores

As we saw, because data in a column is of the same type and often has repeating values, it's highly compressible. This leads to:

1. Reduced I/O: Less data to read from disk.
2. Faster Queries: In some cases, we can operate directly on the compressed data without decompressing it.

Dictionary encoding is a perfect example of a scheme that enables both of these benefits.

The Core Idea: Replacing Values with Codes

At its heart, dictionary encoding is a simple but powerful idea. Instead of storing the same value (like the string "United States") millions of times in a column, you store it just once in a separate data structure called a dictionary. Then, in the column itself, you replace every occurrence of "United States" with a small, fixed-length integer code (e.g., 5).

This process transforms one large column of potentially variable-length data into two new structures:

1. The Dictionary: Contains the set of unique values from the column.
2. The Attribute Vector: A new column of the same length as the original, containing the integer codes that map to the dictionary.

The primary goals here are to reduce storage size (compression) and, crucially for columnar databases, to convert variable-length data like strings into fixed-length integer codes. These codes are much more efficient for the CPU to process.

Let's watch a short video segment that introduces this concept.

Implementing Dictionary Encoding: Design Choices

To implement this, you need to answer a few key questions. We'll focus on the most common scenario for analytical databases: creating the dictionary for an immutable block of data all at once. The most critical question for you as an implementer is: What data structure should I use for the dictionary?

There are three main choices, each with different trade-offs:

1. Sorted Array: Store the unique values in a sorted array. The integer code for a value is simply its index in this array.

   • Pros: Very memory-efficient and simple. Preserves the natural ordering of the data, which is a huge advantage for range queries (e.g., WHERE name > 'M'). Decoding is a fast array lookup.
   • Cons: Inefficient to update (requires rebuilding the array). Encoding can be slow as it requires searching for each value in the sorted array (though a binary search helps).

2. Hash Table: Map each unique value to an integer code using a hash table.

   • Pros: Very fast encoding (constant-time average lookup). Easy to update with new values.
   • Cons: Does not preserve data order, making range queries on the compressed data impossible. Higher memory overhead than a simple array.

3. B+ Tree: A more complex tree structure that keeps values sorted while also allowing efficient updates.

   • Pros: Combines the benefits of both: preserves order and allows efficient updates.
   • Cons: Significantly more complex to implement and has higher CPU and memory overhead than the other two options.

For analytical workloads where data is often written in large, immutable batches (column chunks), the Sorted Array is a very common and effective choice. We will focus on this approach for our implementation.

The following video provides a more detailed breakdown of these design choices.

A Step-by-Step Implementation Plan

Based on the sorted array approach, here is a concrete plan for how you would implement dictionary encoding for a column chunk:

Input: A column of values (e.g., an array of strings).
Output: A dictionary and an attribute vector of integer codes.

1. Build the Dictionary:
   a. Iterate through the input column and collect all unique values into a temporary data structure (a hash set is efficient for this).
   b. Convert the set of unique values into an array or list.
   c. Sort this array of unique values (e.g., lexicographically for strings). This is your dictionary.

2. Build the Attribute Vector:
   a. Create a new integer array of the same size as the original input column. This will be your attribute vector.
   b. Iterate through the original input column again. For each value:
   c. Perform a binary search on your sorted dictionary to find the index of the current value.
   d. Store this index in the corresponding position in your attribute vector.

After these steps, you have successfully compressed the column. You would then store both the dictionary and the new attribute vector to disk.

Dictionary Encoding in Practice: Apache Parquet

These concepts are at the core of real-world file formats like Apache Parquet, which is a standard for columnar storage in the big data ecosystem.

Parquet applies dictionary encoding on a per-column-chunk basis. However, it includes a practical optimization: if the dictionary for a chunk grows too large (e.g., for a column with many unique values), it "falls back" to storing the raw data without a dictionary. This avoids situations where the dictionary itself becomes a memory bottleneck.

The structure described in the blog post is visualized below.

For a much deeper dive into a state-of-the-art implementation, the design of the string dictionary in the DuckDB database is an excellent, if advanced, read. It uses a highly optimized hash table instead of a sorted array to achieve extremely fast performance.

Conclusion

In this lesson, we've deconstructed dictionary encoding, a foundational compression technique in columnar databases. You now have a practical blueprint for how to implement it.

Key Takeaways:

• Dictionary encoding compresses data by replacing values with integer codes, transforming variable-length data into a fixed-length format.
• The implementation consists of two main components: the dictionary (storing unique values) and the attribute vector (storing the integer codes).
• For immutable data blocks common in OLAP systems, a sorted array is a simple and effective data structure for the dictionary, with the added benefit of being order-preserving.
• Real-world systems like Apache Parquet use this technique extensively, adding practical trade-offs like fallback mechanisms for high-cardinality data.

Preview of the Next Lesson

Now that we know how to create and store a dictionary-encoded column, the next natural question is: how do we use it? In our next lesson, we will learn how to execute an aggregate query (e.g., SUM, COUNT) on a dictionary-encoded column without full decompression, leveraging the compact, CPU-friendly nature of our newly encoded data.