Aggregating Dictionary-Encoded Data

Recap: The Power of Codes

Just to refresh, we take a column and split it into two parts:

1. The Dictionary: Stores each unique value just once.
2. The Attribute Vector: Contains small integer codes representing the original values.

The goal today is to keep the data in this efficient, encoded form for as long as possible during query execution, avoiding the expensive cost of decompression (materialization).

The First Big Win: Aggregates on the Dictionary Itself

Let's start with a simple but powerful optimization. Consider this common analytical query:

SELECT COUNT(DISTINCT country) FROM sales;

On uncompressed data, the system would need to scan the entire country column, put all the values into a hash set to find the unique ones, and then count them. If the table has a billion rows, this is a lot of work.

With dictionary encoding, how can we do better?

This is a massive performance gain. The database can answer the query by looking at a tiny data structure (the dictionary) instead of scanning billions of values. The video segment below touches on this and other query processing benefits.

As the video shows, even for selection predicates, the system can first look up the value in the dictionary, get its code, and then perform a highly efficient scan over the integer attribute vector.

The Main Event: GROUP BY Aggregations

Now for the most common and interesting case: a GROUP BY query.

SELECT country, COUNT(*)
FROM sales
GROUP BY country;

A standard hash aggregate operator works by building a hash table. For each row, it hashes the country value and uses it to find the right slot in the hash table to update the running COUNT.

The Naive Way on Compressed Data:

1. For each row, read the integer code from the attribute vector.
2. Use the code to look up the original string value (e.g., "France") in the dictionary.
3. Hash the string "France".
4. Use this hash to find the entry in the aggregation hash table and increment the count.

This involves decompressing the value for every single row, defeating the purpose of our compression!

The Optimized Way: Aggregate on Codes
Since each unique country name already has a unique integer code, we can use these codes directly as the keys in our aggregation hash table.

1. Create a hash table where keys are integers (our dictionary codes).
2. For each row, read the integer code from the attribute vector.
3. Use this code directly to find the entry in the aggregation hash table and increment the count.
4. After processing all rows, the hash table contains entries like {code: count}, for example {4: 150210}.
5. Only now, at the very end, do we iterate through the few unique keys in our hash table and use them to look up the original country names in the dictionary to produce the final result.

This technique of delaying decompression is called late materialization. We performed the entire aggregation—the most expensive part of the query—using the small, fixed-length integer codes, which is much faster for the CPU than processing and hashing strings.

A Real-World Implementation: DuckDB's Compressed Aggregation

This isn't just a theoretical idea. High-performance analytical databases like DuckDB have highly specialized logic for this. To see a concrete example, let's look at a technical paper describing an optimization in DuckDB.

The TryAddCompressedGroups optimization is a beautiful piece of engineering. Instead of hashing every value from the column, it iterates through the much smaller set of unique values in a block's dictionary and uses those to probe the aggregation hash table. This is a direct implementation of the principle we've been discussing.

How Query Engines Access Encoded Data

From a programming perspective, you might wonder how an engineer implementing a query operator would interact with this data. You don't want every function to have complex if/else logic for every possible encoding.

Modern execution frameworks, like Facebook's Velox, provide an abstraction for this, often called a DecodedVector. This is a crucial component that makes it easier to write high-performance, encoding-aware code.

A DecodedVector takes any vector—which could be flat, constant, or have multiple layers of dictionary encoding—and gives the programmer a simplified view:

1. A pointer to the underlying base vector (the raw values).
2. An array of indices mapping the current selection of rows to that base vector.
3. A combined nulls buffer.

This allows an aggregate operator to efficiently access the data it needs without needing to recursively "peel" the layers of dictionary encoding itself.

The example of the optimized sum calculation in the Velox documentation is key. It demonstrates that a well-written query engine doesn't just use one method. It inspects the encoding and properties of the data (is it flat?, are all values the same?, does it have nulls?) and chooses the most efficient algorithm for that specific case. This is a fundamental design principle in high-performance database execution.

Conclusion

You've now seen the real power of dictionary encoding. It's not just about saving disk space; it's about enabling a whole new class of query processing optimizations that are essential for the speed of modern analytical databases.

Key Takeaways:

• By operating directly on dictionary codes, systems can avoid the high cost of decompressing data row-by-row. This principle is known as late materialization.
• Simple aggregates like COUNT(DISTINCT) can often be answered by only inspecting the dictionary, bypassing the main column data entirely.
• For complex GROUP BY aggregates, the hash table can be built using the integer codes as keys, which is significantly more CPU-efficient than using the original values. The full values are materialized only for the final, much smaller, result set.
• Modern execution frameworks like Velox use abstractions like DecodedVector and specialized code paths to make it possible to write efficient, encoding-aware query operators.

Preview of the Next Lesson

Dictionary encoding is powerful, but it's just one tool in the compression toolbox. Another technique, particularly effective for sorted or low-cardinality data, is Run-Length Encoding (RLE). In our next lesson, you will implement run-length encoding for compressing sorted or low-cardinality columns, adding another fundamental compression algorithm to your knowledge base.