Compression-Aware LIKE: Matching Patterns in the FSST Domain

Authors:
Open Access
Publisher website
Google Scholar
Abstract
Database users frequently utilise string data types for general-purpose storage, even when more specialised alternatives are available [18]. Thus, modern analytical database systems rely on lightweight string compression schemes, such as Fast Static Symbol Table (FSST) [2] or OnPair [6], to reduce memory footprint. However, evaluating SQL LIKE predicates on compressed strings typically requires full decompression, negating the benefits of compression. We present an approach that reverses this paradigm: instead of decompressing data to match patterns, we compress the pattern by constructing finite automata that parse FSST-encoded symbol sequences directly. Our technique partitions LIKE patterns into prefixes, suffixes, and substrings, building specialised automata for each, while considering the properties of FSST. We provide interpreted and compiled implementations along with optimisations, including early rejection and SIMD-accelerated self-loop traversal. Evaluation on TPC-H, StackOverflow, and IMDB datasets demonstrates speedups of 2.5–17 × over decompression-based pattern matching, suggesting that co-designing compression schemes and query operators, already successful for integer data, represents a promising direction for string-dominated analytical workloads.

This publication has 12 references indexed in Scilit: