Column Compression Extension

[cateagle]

I want to use the opportunity of the 0.5.0 release to show off, what I experimented with ever since the commit for the custom types.

I have build a turso extension that uses the custom types to use a simple dictionary compression algorithm to reduce the storage size of TEXT columns without loosing the ability to sort, edit, insert, and delete with the normal TEXT SQL interface. There is some performance overhead of course, but I managed to get it into a usable range. The target use case are short (<256 chars) low entropy TEXT columns like file paths, urls, logs, or enum-like strings. Common compression algorithms struggle to provide meaningful row level compression for this kind of short strings.

You can take a look at it here: https://github.com/cateagle/turso-column-compression

Some features:

• runtime finding of new compression dictionary entries with depreciation of old entries before actually removing them
• Incrementally finding new compression dictionary entries without breaking backward compatibility
• Optional re-encoding of old records after new dictionary entries
• Transparent TEXT interface without needing to use CAST all the time.
• Sorting and LIKE still works despite compression

Here is usage example to see the general usage (without candidate finding):

-- Load the extension
.load target/release/libturso_column_compression

-- Register dictionaries in session memory (IDs 1 and 2)
SELECT column_load_dict(1, x'C00005006874747073C00104002E636F6D'); -- urls
SELECT column_load_dict(2, x'C000040052757374C001070069732066617374'); -- slogans

-- Define transparent custom types
CREATE TYPE compressed_url(value text) BASE blob
    ENCODE column_compress(value, 1)
    DECODE column_decompress(value, 1)
    OPERATOR '<' column_compare;

CREATE TYPE compressed_slogan(value text) BASE blob
    ENCODE column_compress(value, 2)
    DECODE column_decompress(value, 2)
    OPERATOR '<' column_compare;

-- Create table using the custom types
CREATE TABLE assets (
    id INTEGER PRIMARY KEY,
    url compressed_url,
    slogan compressed_slogan
) STRICT;

-- Transparent INSERT (TEXT interface)
INSERT INTO assets (url, slogan) VALUES ('https://turso.tech', 'The Database for the Age of AI Agents');

-- Transparent SELECT (TEXT interface)
SELECT * FROM assets;

-- Verify storage savings (Raw BLOB length)
SELECT length(CAST(url AS BLOB)) FROM assets;

For a more complete usage example with compression dictionary management look at https://github.com/cateagle/turso-column-compression/blob/main/tests/prepare_e2e_test.sh

This is still just a proof of concept. It is the first time I have written anything related to compression algorithms so I would not trust production data to my code. I am also still not 100% happy with the way the compression dictionaries are registered and might change the API a little. I would really like to be able to share the compression dictionaries between columns and connect them to the type itself, but that would mean that I would need to handle cross column cross table sampling for the generation of the compression dictionaries.

It would obviously also be great to improve performance as it currently is still nowhere as fast as turso handles TEXT natively, but it has gotten usable already with only being 2-3x slower (depending on the operation). I would be able to achieve significant speed ups with using unsafe to skip the utf-8 validation, but I am too scared to do that for now. Even if I cannot get it to go faster, I still think that there are use cases where the compression could reduce database size by a lot. The theoretical upper limit of compression ratio is 0.0625, but 0.3 to 0.8 is a more realistic expectation.

If someone has any idea of how to improve this or how to better integrate it into turso, I always welcome help or constructive criticism. It is my first time using profiling in rust and I am sure that there are many smarter or more experienced developers than me out there.