Instance-Optimized String Fingerprints
Preprint
Abstract
Recent research found that cloud data warehouses are text-heavy. However, their capabilities for efficiently processing string columns remain limited, relying primarily on techniques like dictionary encoding and prefix-based partition pruning. In recent work, we introduced string fingerprints - a lightweight secondary index structure designed to approximate LIKE predicates, albeit with false positives. This approach is particularly compelling for columnar query engines, where fingerprints can help reduce both compute and I/O overhead. We show that string fingerprints can be optimized for specific workloads using mixed-integer optimization, and that they can generalize to unseen table predicates. On an IMDb column evaluated in DuckDB v1.3, this yields table-scan speedups of up to 1.36$\times$.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Memento Filter: A Fast, Dynamic, and Robust Range FilterProceedings of the ACM on Management of Data, 2024
- Last fifty years of integer linear programming: A focus on recent practical advancesEuropean Journal of Operational Research, 2024
- Predicate Caching: Query-Driven Secondary Indexing for Cloud Data Warehouses2024
- Automated Multidimensional Data Layouts in Amazon Redshift2024
- LPLM: A Neural Language Model for Cardinality Estimation of LIKE-QueriesProceedings of the ACM on Management of Data, 2024
- InfiniFilter: Expanding Filters to Infinity and BeyondProceedings of the ACM on Management of Data, 2023
- Using positional sequence patterns to estimate the selectivity of SQL LIKE queriesExpert Systems with Applications, 2021
- Integer Programming2020
- Integer Programming2014
- Efficient processing of substring match queries with inverted variable-length gram indexesInformation Sciences, 2013