Skip to content

[Compression] Introduce DICT_FSST compression method #15637

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 116 commits into from
May 7, 2025
Merged

[Compression] Introduce DICT_FSST compression method #15637

merged 116 commits into from
May 7, 2025

Conversation

Tishj
Copy link
Contributor

@Tishj Tishj commented Jan 9, 2025 •
edited
Loading

This PR adds DICT_FSST, making use of the new NO_VALIDITY_REQUIRED behavior introduced in #15591

The new method is a mix of Dictionary and FSST (which will be deprecated by this method at a later point)

The method currently has 3 modes that it can decide to use for a block:

  • DICTIONARY, almost an exact replica of the existing Dictionary method, no further encoding added.
  • DICT_FSST, Dictionary but the created dictionary is further encoded using FSST.
  • FSST_ONLY, We don't perform dictionary encoding in this mode, so no string lookups are performed. Instead everything is added to the block without deduplication, everything is FSST encoded.

A couple separate improvements are made to the existing dictionary / fsst behaviors:

  • As well as bitpacking the dictionary_indices (formerly known as selection_buffer) we now also bitpack the string_lengths (formerly known as index_buffer, which was storing offsets instead of lengths)
  • To reduce the amount of computation done for each tuple, the BitpackingPrimitives::MinimumBitWidth and BitpackingPrimitives::GetRequiredSize calls are only performed when necessary.

Tishj added 24 commits January 7, 2025 13:32
@Tishj
dict_fsst start
c7b7690
@Tishj
forgot a couple include renames
126e6fa
@Tishj
wip
d554f99
@Tishj
apply the optimization/fix here as well
c87639f
@Tishj
remove the 'last_lookup_result' variable, not a fan of state like that
d924e35
@Tishj
prepare for the need to encode input strings once the dictionary is f…
468db86 
…sst encoded
@Tishj
added the fsst encoding step, code is compiling successfully
96297d7
@Tishj
implement the scan logic
b1295c5
@Tishj
fix up a test
375c8d9
@Tishj
fix up tests
825a620
@Tishj
introduce StringData to hold the uncompressed string, together with a…
7e704c1 
…n optional encoded string
@Tishj
Merge remote-tracking branch 'upstream/main' into dict_fsst_compressi…
4b1a066 
…on_combined
@Tishj
clear the encoder after flushing
0bc0296
@Tishj
this is a bit of a blocker..
7af2569
@Tishj
limit max string length so the encoded variant wont exceed string-blo…
1377b4b 
…ck-limit
@Tishj
fix issue with rewriting the current_string_map (off by one...), add …
54d1c3f 
…test
@Tishj
remove the analyze+compress code of Dictionary compression
5c964c6
@Tishj
remove analyze+compress code from FSST compression
ecf3045
@Tishj
moving to dict_fsst, already started on the deprecated read tests, bu…
9afe4c0 
…t I accidentally made a corrupted db..
@Tishj
Merge remote-tracking branch 'upstream/main' into dict_fsst_compressi…
67724ba 
…on_combined
@Tishj
Merge branch 'undo_dictionary_scan_changes' into dict_fsst_compressio…
2c8bd89 
…n_combined
@Tishj
read the fsst and dictionary db files
2b02271
@Tishj
adjust fsst compression ratio test for dict_fsst
c2405b5
@Tishj
Merge branch 'undo_dictionary_scan_changes' into dict_fsst_compressio…
28dcff0 
…n_combined
@carlopi
Copy link
Contributor

carlopi commented Jan 9, 2025 •
edited
Loading

One consideration, connected to file storage / cross compatibility, I think we should still support writing to files keeping them compatible with older versions.

It might be fine to forbid generating Dictionary / FSST and Dict_fsst entirely, when needing to write to files that needs to be compatible with older versions, unsure of what are the costs though (as is, how bigger / slower files will become given cross-compatibility will be the default).

@Mytherin
Copy link
Collaborator

Mytherin commented Jan 9, 2025

Yes agreed, we should still keep in the code for writing the old encodings for forwards compatibility purposes. We should automatically select DICT_FSST when targeting newer DuckDB versions (>= 1.2), and Dictionary or FSST when targeting older versions.

@Tishj
Copy link
Contributor Author

Tishj commented Jan 9, 2025

Alright I'll add the code back in and use the storage_compatibility_version to decide whether dictionary+fsst should be loaded

@Tishj Tishj marked this pull request as ready for review May 6, 2025 12:07
@duckdb-draftbot duckdb-draftbot marked this pull request as draft May 6, 2025 12:57
@Tishj Tishj marked this pull request as ready for review May 6, 2025 12:57
Mytherin and others added 2 commits May 6, 2025 21:19
@Mytherin
Merge branch 'dict_fsst_compression_combined' into dictfsstfilterselect
d39193d
@Tishj
Merge pull request #144 from Mytherin/dictfsstfilterselect
db3b51e 
Implement `Filter` and `Select` for `DICT_FSST`, fix stats gathering to skip `NULL` values and fix `LATEST_STORAGE` tests
@duckdb-draftbot duckdb-draftbot marked this pull request as draft May 6, 2025 20:28
@Tishj Tishj marked this pull request as ready for review May 6, 2025 20:30
@duckdb-draftbot duckdb-draftbot marked this pull request as draft May 7, 2025 08:32
@Tishj Tishj marked this pull request as ready for review May 7, 2025 09:28
@Mytherin Mytherin merged commit 7152079 into duckdb:main May 7, 2025
47 of 49 checks passed
@Mytherin
Copy link
Collaborator

Mytherin commented May 7, 2025

Thanks!

krlmlr added a commit to duckdb/duckdb-r that referenced this pull request May 18, 2025
@krlmlr
vendor: Update vendored sources to duckdb/duckdb@7152079
5af5cc8 
[Compression] Introduce `DICT_FSST` compression method (duckdb/duckdb#15637)
Remove bundled TPCH & TPCDS in Python wheels (duckdb/duckdb#15923)
krlmlr added a commit to duckdb/duckdb-r that referenced this pull request May 18, 2025
@krlmlr
vendor: Update vendored sources to duckdb/duckdb@7152079
debf035 
[Compression] Introduce `DICT_FSST` compression method (duckdb/duckdb#15637)
Remove bundled TPCH & TPCDS in Python wheels (duckdb/duckdb#15923)
krlmlr added a commit to duckdb/duckdb-r that referenced this pull request May 19, 2025
@krlmlr
vendor: Update vendored sources to duckdb/duckdb@7152079
f26e8dd 
[Compression] Introduce `DICT_FSST` compression method (duckdb/duckdb#15637)
Remove bundled TPCH & TPCDS in Python wheels (duckdb/duckdb#15923)
krlmlr added a commit to duckdb/duckdb-r that referenced this pull request May 19, 2025
@krlmlr
vendor: Update vendored sources to duckdb/duckdb@7152079
fa35b51 
[Compression] Introduce `DICT_FSST` compression method (duckdb/duckdb#15637)
Remove bundled TPCH & TPCDS in Python wheels (duckdb/duckdb#15923)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@Tishj @carlopi @Mytherin