Teach Your DBMS to LIKE Strings: Fast and General Pattern Matching for Wildcard Joins and Filters

summary

The gist

Modern database management systems (DBMSs) handle wildcard operations poorly, resorting to nested loops for joins and expensive interpreted evaluation for filters <ref:2608.23307#pg2> To address the…

In short

Modern database systems handle wildcard queries poorly, using slow methods like nested loops for joins and expensive interpretation for filters. The authors propose two solutions: an Aho-Corasick based algorithm for faster wildcard joins and code generation to create specialized code for LIKE filters. These techniques significantly outperform existing baselines in speed.

Key concepts

Aho-Corasick algorithm
This is a string matching algorithm used to find all occurrences of multiple patterns within a text simultaneously in a single pass. It replaces slow, sequential searching with an efficient automaton structure, drastically reducing the time complexity for multi-pattern matching in joins.
Positional Constraints
This concept uses wildcards like '%' and '_' to define strict rules for pattern placement. The system decomposes complex patterns into segments and literals, using these constraints to ensure that literals are placed exactly where required relative to each other, turning a complex search into an efficient greedy problem.
Compiled Wildcard Filters
Instead of interpreting the LIKE pattern every time it runs against a data row, the system generates specialized machine code specifically for that particular pattern. This eliminates the runtime overhead associated with repeatedly parsing and evaluating the pattern per tuple, leading to much faster filtering.
Wildcard Joins
This involves extending standard relational joins to handle patterns in the join condition. The authors use a two-phase approach: building a global automaton from patterns and then probing the text against this automaton, which is much more efficient than traditional nested-loop join strategies.

Terminology used across episodes

This episode discusses

The paper

Teach Your DBMS to LIKE Strings: Fast and General Pattern Matching for Wildcard Joins and Filters · Read on arXiv

Technische University of Munich

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Teach Your DBMS to LIKE Strings".

Jane: Here's the gist of the paper. Modern database management systems (DBMSs) handle wildcard operations poorly, resorting to nested loops for joins and expensive interpreted evaluation for filters <ref:2608.23307#pg2> To address the former, we propose a new join algorithm based on the Aho-Corasick algorithm, which significantly reduces the time complexity <ref:2608.23307#pg2> For wildcard filtering, we leverage the code-generation infrastructure to improve performance by generating specialized code for the LIKE predicate <ref:2608.23307#pg2> Our experimental results show that the new wildcard join algorithm significantly outperforms both baseline DuckDB and Umbra, achieving speedups of up to 30.6× and 114.75×, respectively <ref:2608.23307#pg2> The new wildcard filter approach likewise outperforms both baselines, achieving 13.3× speedups in a filter-focused stress benchmark <ref:2608.23307#pg2>.

Tom: Pruning redundant reasoning tokens The paper introduces two main techniques to optimize string pattern matching for database operations: an Aho-Corasick based algorithm for wildcard joins and code generation for compiled wildcard filters <ref:2608.23307#pg2> The core challenge addressed is the lack of specialized physical operators in DBMSs, which forces reliance on computationally expensive execution strategies like nested loop joins and interpreted evaluation <ref:2608.23307#pg2> Specifically, the authors propose an execution strategy based on the Aho-Corasick algorithm to eliminate the expensive combination of nested-loop join structure and standard LIKE evaluations for wildcard joins <ref:2608.23307#pg2> Furthermore, for wildcard filtering, they leverage code generation infrastructure to generate specialized code for the LIKE predicate, thereby eliminating the overhead of interpreting the pattern per tuple <ref:2608.23307#pg2>.

Jane: How the training signal is built The proposed wildcard join algorithm is based on decomposing complex patterns into segments and literals governed by positional constraints, which transforms the wildcard join into a highly efficient, greedy matching problem <ref:2608.23307#pg2> This tokenization strategy involves splitting the wildcard pattern using '%' as a delimiter to impose positional constraints allowing for an arbitrary number of characters between segments <ref:2608.23307#pg2> Subsequently, they tokenize these segments into literals using '' as the delimiter to establish precise positional constraints between literals, dictating the exact number of characters required to separate them <ref:2608.23307#pg2> The matching logic greedily anchors a segment at its earliest possible occurrence and sequentially commences the search for subsequent segments from that end position, which guarantees correctness while avoiding expensive backtracking <ref:2608.23307#pg2>.

Tom: Where the gains come from The performance gains stem from two distinct optimizations: efficient wildcard joins and compiled wildcard filters <ref:2608.23307#pg2> For joins, the Aho-Corasick algorithm is used to match multiple patterns in a single pass over input strings, which eliminates the nested-loop execution used by existing systems <ref:2608.23307#pg2> For filters, they exploit code compilation architectures to generate specialized code for LIKE predicate evaluation, reducing per-tuple runtime overhead and avoiding repeated memory accesses to the pattern <ref:2608.23307#pg2>.

Paper summary: Tom: We’ve covered the details of how this paper, "Teach Your DBMS to LIKE Strings: Fast and General Pattern Matching for Wildcard Joins and Filters," tackles the slow performance issues in database string pattern matching <ref:2608.23307#pg1>.

Jane: The authors propose using an Aho-Corasick algorithm for joins and code generation infrastructure for filters to give database management systems better ways to handle those wildcard queries <ref:2608.23307#pg1>.

Lu: It suggests that the key innovation is using positional constraints to transform the complex wildcard join problem into a highly efficient greedy matching problem <ref:2608.23307#pg7>.

Meng: The implication for us in shipping models is that we need to consider these specialized execution strategies if we want our text analytics features to actually perform well under load and not just on small test cases <ref:2608.23307#pg1>.

Tom: So, while the paper shows significant speedups, like up to one hundred fourteen point seventy five times over baseline UmbraBase in Query three <ref:2608.23307#pg3>, it’s important to remember that these gains depend heavily on the specific workload you are running <ref:2608.23307#pg5>.

Jane: Exactly, and they also flagged a limitation: for very long patterns, the memory overhead of the Aho-Corasick automaton might become too much for the benefits of positional constraints <ref:2608.23307#pg9>.

Lu: So, to wrap up this discussion on "Teach Your DBMS to LIKE Strings: Fast and General Pattern Matching for Wildcard Joins and Filters," the main idea is that these specialized execution strategies are crucial for high performance text analytics in modern query engines <ref:2608.23307#pg1>.

Meng: It’s about making sure that when we build our systems, we aren't just relying on the standard, slow methods when dealing with complex string matching queries <ref:2608.23307#pg5>.

Tom: We should keep an eye on how they explore string compression and pattern matching with don't care characters in future work because that’s where the next big efficiency gains might be found <ref:2608.23307#pg9>.

Conclusion: Tom: So, we're wrapping up this look at "Teach Your DBMS to LIKE Strings: Fast and General Pattern Matching for Wildcard Joins and Filters" <ref:2608.23307#pg1>.

Jane: It basically takes those slow, old ways databases use to find patterns with wildcards—like the SQL LIKE command—and makes them way faster <ref:2608.23307#pg1>.

Lu: The authors are focusing on two main things: fixing how the database joins data using those wildcards and improving how it filters text fields <ref:2608.23307#pg1>.

Meng: What they actually did was propose a new way to do the join, based on something called Aho-Corasick, which cuts down on that slow nested loop execution <ref:2608.23307#pg1>.

Tom: That's because right now, when you have wildcards in a join, the system has to check everything one by one <ref:2608.23307#pg5>. This new approach lets it match multiple patterns at the same time <ref:2608.23307#pg6>.

Jane: And for the filtering part, they used code generation to create specialized code for those filters instead of just interpreting the pattern every single time <ref:2608.23307#pg1>. That sounds like a real win for speed <ref:2608.23307#pg1>.

Lu: The whole idea is about taking complex string patterns, which have those wildcards and positional constraints—like using percent signs and underscores—and turning them into a much simpler, greedy matching problem <ref:2608.23307#pg7>. That’s the core mechanism <ref:2608.23307#pg7>.

Meng: For me at scale, the thing that matters is that this isn't just a theoretical speedup on small tests; it’s about avoiding those expensive execution plans in production where things break under heavy traffic <ref:2608.23307#pg1>. I want to know what breaks when you try to deploy this kind of specialized code generation <ref:2608.23307#pg4>.

Tom: Exactly, and the experimental results show that these techniques beat the existing tools by massive margins, like speedups up to three point zero six times for the join part <ref:2608.23307#pg1>. That’s a big difference when you’re dealing with millions of records <ref:2608.23307#pg5>.

Jane: So, what does this mean for someone who just uses a database? It means that the next time they build an application that needs to search text data using wildcards, they can expect it to be significantly more responsive <ref:2608.23307#pg1>.

Lu: But we have to remember what the paper flags—that for really long patterns, the memory used by the Aho-Corasick structure might become too much, so they have to balance that against the efficiency gains <ref:2608.23307#pg9>. That’s a key limitation <ref:2608.23307#pg9>.

Meng: So it's not perfect for every single use case, but for high-volume text analytics, these execution strategies seem like they play a crucial role <ref:2608.23307#pg1>.

Tom: Right. This is how we tackle the slow parts of modern query engines when they're dealing with lots of text data <ref:2608.23307#pg5>. We’ll talk more about string compression and pattern matching with don't care characters next <ref:2608.23307#pg9>.

More episodes

← Home