Dictionary Encoding and its cousins: storage optimization patterns in data systems

In this post I'll show you a simple technique to reduce the size of your data. This pursuit isn't just about saving disk space and money, but it brings performance benefits as well. For example, smaller volume databases fit more contents into available RAM, reducing the need for costly disk I/O operations. In the ideal case when your working set fits in memory in its entirety, query performance will be impressive. In addition, I will cover other techniques which I found to be similar in nature with Dictionary Encoding, which I consider a testimony of its prevalence.

Dictionary Encoding

Dictionary encoding is a data compression technique where frequently occurring values are replaced with shorter identifiers that reference a separate lookup table (the "dictionary"). Instead of storing the same string value hundreds or thousands of times or more, we store it once in a dictionary table and reference it with a small integer key.

Example

Let's have a look at how it works. Let's consider a orders table with the following columns:

After transforming the table above with dictionary encoding, we get the following tables:

• orders

• customer_dictionary

• status_dictionary

Related techniques

In my research, I have noticed several techniques in building data systems which are very similar in nature to dictionary encoding. The fundamental idea is the same.

1. Database Normalization

Traditional database normalization through normal forms and dictionary encoding share a fundamental goal: eliminate data redundancy, however, normalization has broader benefits.

Normalization focuses on logical data modeling and integrity. When you normalize a database to Third Normal Form (3NF), you create separate tables to eliminate transitive dependencies and reduce update anomalies. For instance, moving customer information from an orders table to a dedicated customers table prevents data inconsistency if a customer's address changes.

2. String Interning

String interning is a memory management technique where identical strings share the same memory location. Instead of storing multiple copies in different variables, the system maintains one canonical copy and returns references to it.

Dictionary encoding resembles string interning but operates at the database storage level rather than in application memory. The crucial distinction lies in persistence and scope: string interning typically happens within a single program's runtime memory, while dictionary encoding creates persistent storage structures that survive database restarts and can be shared across all database operations.

3. "German" Strings

This solution is based on a 128-bit structure that optimizes for database workloads. German strings use two representations: short strings (12 characters or fewer) are stored inline within the 128-bit structure, while longer strings store a 32-bit length, a 4-character prefix for fast comparisons, and a pointer to the actual data. This design optimizes for common database operations like prefix matching and equality comparisons. You can find more information about this topic here.

Worked example with Postgres

Let's set up an experiment in Postgres to see what kind of savings we can have. I will create the tables I showed you in the Example section above and populate it with some generated test data. After the insertions are finished, I will retrieve the total volume and compare.

Without encoding

CREATE TABLE orders_without_encoding (
    id BIGSERIAL PRIMARY KEY,
    customer_name VARCHAR(100),
    status VARCHAR(20)
);

-- Insert sample data with repetitive values
INSERT INTO orders_without_encoding (customer_name, status)
SELECT 
    (ARRAY['John Smith', 'Jane Doe', 'Bob Wilson', 'Alice Johnson', 'Mike Brown', 'Sarah Davis', 'Tom Wilson', 'Lisa Anderson', 'Chris Martinez', 'Emma Taylor'])[1 + (i % 10)],
    (ARRAY['pending', 'processing', 'shipped', 'delivered', 'cancelled'])[1 + (i % 5)]
FROM generate_series(1, 100000) AS i;

With encoding

-- Create dictionary tables
CREATE TABLE customer_dictionary (
    id SERIAL PRIMARY KEY,
    name VARCHAR(100) UNIQUE NOT NULL
);

CREATE TABLE status_dictionary (
    id SMALLINT PRIMARY KEY,
    status VARCHAR(20) UNIQUE NOT NULL
);

-- Populate dictionary tables
INSERT INTO customer_dictionary (name) VALUES 
    ('John Smith'),
    ('Jane Doe'),
    ('Bob Wilson'),
    ('Alice Johnson'),
    ('Mike Brown'),
    ('Sarah Davis'),
    ('Tom Wilson'),
    ('Lisa Anderson'),
    ('Chris Martinez'),
    ('Emma Taylor');

INSERT INTO status_dictionary VALUES 
    (1, 'pending'),
    (2, 'processing'),
    (3, 'shipped'),
    (4, 'delivered'),
    (5, 'cancelled');

-- Create main table with dictionary encoding
CREATE TABLE orders_with_encoding (
    id BIGSERIAL PRIMARY KEY,
    customer_id INTEGER REFERENCES customer_dictionary(id),
    status_id SMALLINT REFERENCES status_dictionary(id)
);

-- Insert the same data using encoded values
INSERT INTO orders_with_encoding (customer_id, status_id)
SELECT 
    1 + (i % 10),  -- customer_id (1-10)
    1 + (i % 5)    -- status_id (1-5)
FROM generate_series(1, 100000) AS i;

Results

Let's have a look at the storage size of each option. For this, I will query the Postgres system views.

SELECT 
    'Without Encoding' as approach,
    pg_size_pretty(pg_total_relation_size('orders_without_encoding')) as total_size,
    pg_size_pretty(pg_relation_size('orders_without_encoding')) as table_size
UNION ALL
SELECT 
    'With Encoding' as approach,
    pg_size_pretty(
        pg_total_relation_size('orders_with_encoding') + 
        pg_total_relation_size('customer_dictionary') + 
        pg_total_relation_size('status_dictionary')
    ) as total_size,
    pg_size_pretty(
        pg_relation_size('orders_with_encoding') + 
        pg_relation_size('customer_dictionary') + 
        pg_relation_size('status_dictionary')
    ) as table_size;

     approach     | total_size | table_size 
------------------+------------+------------
 Without Encoding | 8216 kB    | 5976 kB
 With Encoding    | 6640 kB    | 4344 kB

As we can see, we saved about 20% storage space. Not bad, eh?