Database management systems face a significant challenge with string data, which represents about half of all real-world stored information due to its flexibility. This prevalence necessitates efficient storage methods that also guarantee rapid query execution, as users demand low-latency responses. Snowflake recently confirmed that string columns are the most common data type and the most frequently used in filtering operations within their analytical workloads.
While compression universally reduces data size, database experts emphasize that its main utility within these systems is performance enhancement, as noted by Professor Thomas Neumann. By decreasing the memory footprint, compressed strings can fit into faster CPU caches, potentially yielding access time improvements exceeding ten times. Furthermore, smaller data streams translate directly to better utilization of bandwidth-limited channels moving data from disk to the CPU.
CedarDB currently utilizes several compression schemes for text columns, including uncompressed, single value, and dictionary compression, as detailed in a recent publication. Dictionary compression works by replacing unique string values with fixed-size integer keys that serve as offsets into an index. This method allows for efficient random access to the original strings via the stored offsets.
CedarDB’s implementation of dictionary compression stores its dictionary entries in lexicographical order, a design choice that aids query evaluation. Although insertions and deletions are costly in ordered structures, CedarDB sidesteps this complexity by treating compressed data as immutable. This ordering ensures that the order of the integer keys mirrors the lexicographical order of the uncompressed strings.
Evaluating filters directly on the compressed representation is a core optimization strategy to avoid the CPU overhead associated with decompression. For example, searching for a specific URL involves performing a binary search on the ordered dictionary values to locate the corresponding key. If a match is found, subsequent processing relies on cheap integer comparisons rather than variable-length string comparisons.
These integer key comparisons are significantly faster because they permit the efficient use of modern processor features like SIMD (vectorized instructions) to execute multiple comparisons simultaneously. Only the tuples satisfying the predicate are then decompressed for output or further processing, minimizing overall computational work.
Despite its advantages, dictionary compression falters when data exhibits a high cardinality, as it mandates storing every distinct string in full. The analysis suggests that since many strings share common patterns and possess low entropy, superior compression schemes capable of exploiting this predictability are necessary for comprehensive string optimization.
CedarDB’s exploration into these more advanced compression techniques, such as FSST (Fast String Similarity Technique), aims to address the limitations of dictionary coding for highly variable string domains. The future direction involves exploiting string predictability to achieve better density and sustained query speed across diverse datasets.
