Faster String Aggregations with Dimension Tables

TL;DR: When a query groups on long, repeated strings, move the strings into a small dimension table with sorted, narrow integer keys. Aggregate on the keys, then join the strings back in at the very end. The query works as before, though on small fixed-width integers instead of variable-length text.

Analytical workloads are full of repeated strings: product names, country names, station names, user agents, category labels. Take DuckDB's public train services dataset, which has one row for every stop a Dutch railway train makes. The data comes from the open datasets published by the Rijden de Treinen (Are the trains running?) application. You can query it straight from its URL:

SELECT departure_time, station_name, type
FROM 'https://blobs.duckdb.org/train_services.parquet'
LIMIT 5;

The table has 380,959 rows but only 537 distinct station names, so each name is stored again in thousands of rows: Amsterdam Centraal (18 bytes) alone appears in 7,591 of them. Load it into a table to follow along, in the web shell or the DuckDB CLI:

CREATE TABLE train_services AS
    FROM 'https://blobs.duckdb.org/train_services.parquet';

When you GROUP BY the station name, DuckDB has to process the full string for every row. For example, this query counts how many trains call at each station:

SELECT station_name, count(*) AS calls
FROM train_services
GROUP BY station_name;

The string work repeats for every row, even though there are only two distinct stations here, and only 537 across the whole table.

This post shows how to do that work on small integers instead, by giving each distinct string a number and looking up the strings only at the end.

Background

The approach is the star schema from data warehousing, used here for query performance. It came up when we looked at a user report of heavy memory use in a high-cardinality grouping.

That report turned out not to involve strings, but Richard Wesley pointed out that in his own work, building dimension tables and joining the strings back at the end made a large difference to string-heavy aggregations.

Why Strings Are Expensive to Group On

DuckDB computes a GROUP BY with a hash aggregation, keeping one hash table entry per group. The aggregation uses the hash of each group key to find the key's slot in a hash table, then compares the key with the one stored in that slot. For integers, this takes a few CPU instructions. For strings, the cost grows with the length of the string.

In DuckDB, a string value is a 16-byte structure. Strings of up to 12 bytes are stored inline. Longer strings store a 4-byte prefix plus a pointer to the actual characters. That design keeps short strings cheap, but many real-world labels are longer than 12 bytes.

For these longer strings, hashing reads every byte of every string in every row. A match can't be confirmed from the prefix alone, so DuckDB follows the pointer and compares the full string. When a new group appears, its string is copied into the hash table's own memory, which makes the table larger than it would be with fixed-width keys.

Copying strings also affects memory use. A wider hash table fits less well into CPU caches, and in larger-than-memory aggregations it reaches the memory limit sooner and has to spill more data to disk. DuckDB does apply dictionary encoding to string columns on disk, but that is a storage optimization: once a column is read into an aggregation, each group key is a full string again.

Integer keys avoid these costs, as their fixed width makes hashing and comparing them cheap. When the key range is small, DuckDB can avoid hashing altogether: if the statistics show that the keys fit in a small enough domain, the optimizer picks a perfect hash aggregate, controlled by the perfect_ht_threshold setting, which uses the key value directly as an index into an array.

Building a Dimension Table with Sorted, Narrow Keys

The examples build on the train_services table loaded above. Each row records one stop: a service_id, the date, the service type, the train_number, the station_code and station_name, and the departure_time and arrival_time. The repeated string we want to encode is station_name.

Step 1: Measure the Cardinality

First, find out how many distinct values the column has, since that count sets how narrow the key can be.

SELECT count(DISTINCT station_name) AS num_stations
FROM train_services;

This returns 537, and that count decides how wide the key needs to be. You want the narrowest integer type whose range still covers every distinct value, because a narrower key means fewer bytes per row in the fact table and a smaller entry in the hash table you group on.

The keys come from row_number(), which starts at 1 and only counts upward, so an unsigned type is the right fit, spending none of its range on negative values. UTINYINT (1 byte) holds up to 255 distinct values, USMALLINT (2 bytes) up to 65,535, and UINTEGER (4 bytes) up to about 4.3 billion.

Step 2: Build the Dimension Table

Next, assign each distinct string an integer key. The important detail is the ORDER BY station_name inside the window: the keys are assigned in string order.

CREATE OR REPLACE TABLE stations AS
    SELECT
        station_name,
        (row_number() OVER (ORDER BY station_name))::USMALLINT AS station_id
    FROM (SELECT DISTINCT station_name FROM train_services WHERE station_name IS NOT NULL);

Step 3: Store the Key in the Fact Table

Finally, replace the string column in the fact table with its key, a rewrite of the table that you pay for once. The dimension table leaves out NULL, so the LEFT JOIN keeps the rows without a station and gives them a NULL key.

CREATE OR REPLACE TABLE train_services_encoded AS
    SELECT ts.* EXCLUDE (station_name), s.station_id
    FROM train_services ts
    LEFT JOIN stations s USING (station_name);

The fact table now stores the 2-byte USMALLINT key, so grouping on it is cheap. With a key range this small and dense, DuckDB can use a perfect hash aggregate, indexing directly by the key instead of hashing.

Querying the Encoded Table

With the key in place, the query aggregates on integers and only looks up the strings once the result is small.

WITH rollup AS (
    SELECT
        station_id,
        date,
        count(*) AS calls
    FROM train_services_encoded
    GROUP BY ALL
)
SELECT s.station_name, rollup.* EXCLUDE (station_id)
FROM rollup
LEFT JOIN stations s USING (station_id)
ORDER BY station_id, date;

For top-N queries, apply the LIMIT before the join, so that only ten strings are looked up:

WITH top_stations AS (
    SELECT station_id, count(*) AS calls
    FROM train_services_encoded
    GROUP BY station_id
    ORDER BY calls DESC
    LIMIT 10
)
SELECT s.station_name, top_stations.calls
FROM top_stations
LEFT JOIN stations s USING (station_id)
ORDER BY calls DESC;

Variations

Comparison with ENUM

DuckDB's ENUM type is dictionary encoding built into the type system: values are stored as small integers, and DuckDB picks the integer width for you. The dimension table is the better choice when:

• New values keep arriving. An ENUM's values are fixed when the type is created. A dimension table can grow.
• You need attributes. A dimension table can carry extra columns, such as the station's city or the line it sits on.
• The data leaves DuckDB. Integer keys and a lookup table can be exported to Parquet or CSV and used in other tools.

Several String Columns

The pattern applies per column: build one dimension table for each high-repetition string column. Each key gets its own integer type, sized to the cardinality of its column, and a query only joins back the dimensions it needs.

Keeping the Dimension Up to Date

When new data arrives, add unseen strings with keys that continue after the current maximum using an ANTI JOIN to identify new records, then encode the new fact table rows and append them.

When the Pattern Does Not Help

Don't use it when:

• The strings are short. Values of up to 12 bytes are already stored inline.
• The column is nearly unique. If most values are distinct, the dimension table has almost as many rows as the fact table and little is saved.
• You query the data once. Building the dimension table and rewriting the fact table costs a full pass over the data.
• You don't aggregate on the column.

Conclusion

Grouping on repeated strings is expensive. By moving them into a small dimension table with sorted, narrow integer keys, DuckDB can aggregate on fixed-width integers and keep its hash tables compact. The strings come back in a final join against a result that is already small.