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

arXiv:2608.23307 · cs.DB · Submitted 2026-08-24 · Read on arXiv

Listen

Radio episode about this paper

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>.

Technische University of Munich

cs.DB

Submitted: 2026-08-24

Updated: 2026-11-02

Comments: The invariant in this manuscript is wrong. Also, the author set is changed

Code: https://github.com/lamduynguyen/wildcard-join

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 88/100

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…

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.

Summary

Modern database management systems (DBMSs) handle wildcard operations poorly, resorting to nested loops for joins and expensive interpreted evaluation for filters <ref:2608. p. 023307#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. p. 023307#pg2> For wildcard filtering, we leverage the code-generation infrastructure to improve performance by generating specialized code for the LIKE predicate <ref:2608. p. 023307#pg2> Our experimental results show that the new wildcard join algorithm significantly outperforms both baseline DuckDB and Umbra, achieving speedups of up to 30. p. 0 p. 06× and 114. p. 0 p. 075×, respectively <ref:2608. p. 0 p. 023307#pg2> The new wildcard filter approach likewise outperforms both baselines, achieving 13. p. 0 p. 03× speedups in a filter-focused stress benchmark <ref:2608. p. 0 p. 023307#pg2>.

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. p. 123307#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. p. 123307#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. p. 023307#pg2>.

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. p. 323307#pg2>.

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. p. 823307#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. p. 123307#pg2>. These techniques collectively demonstrate significant speedups over baseline approaches in experimental results <ref:2608. p. 023307#pg2>.

Evaluation and Comparison

Empirical evaluation using a new benchmark specifically designed for wildcard operations shows that the proposed wildcard join algorithm, UmbraOurs, achieves the highest throughput across three different join queries <ref:2608.23307#pg2> Specifically, UmbraOurs delivers at least 4. p. 82× throughput of the two other baselines in Query 2 and reaches a significant gap of 30. p. 86× over DuckDB and 114. p. 075× over UmbraBase in Query 3 <ref:2608. p. 023307#pg2>. Similarly, for wildcard filters, UmbraOurs achieves a massive 13. p. 83× speedup over DuckDB and a 14. p. 03× performance gap over UmbraBase in stress benchmarks <ref:2608. p. 023307#pg2>. The comparison also shows that compiled filters clearly outperform wildcard joins for low pattern counts, up to 7. p. 12× higher throughput at p=2 <ref:2608. p. 023307#pg2>.

Related Work and Future Directions

The work builds upon existing literature concerning string and pattern processing, including q-gram inverted indexes and string compression techniques <ref:2608.23307#pg2> While prior work on pattern matching with don’t-care characters exists, the authors note that achieving linear-time performance for single-pattern don’t-care matching remains an open question <ref:2608. p. 723307#pg2> The paper suggests that for long patterns, the memory overhead of an Aho-Corasick automaton outweighs the benefits of positional constraints, leading to a preference for simple greedy techniques in those scenarios <ref:2608. p. 823307#pg2>. Future work could explore detecting repetitive patterns during the build phase to avoid indexing them in the Aho-Corasick automaton <ref:2608. p. 323307#pg2>. The paper also touches upon string compression and pattern matching with don’t-care characters as areas for future investigation <ref:2608. p. 723307#pg2>.

Summary

The limitations of existing LIKE execution become particularly pronounced in text-heavy workloads, where the same patternmatching operations are applied across large volumes of data <ref:2608.23307#pg2> The authors tackle these limitations with two techniques: using Aho-Corasick for wildcard joins to match multiple patterns in a single pass, and leveraging code compilation to specialize LIKE evaluation for each input tuple <ref:2608. p. 823307#pg2> These specialized execution strategies substantially outperform existing approaches in modern query engines <ref:2608. p. 023307#pg2>. The paper concludes that these techniques play key roles for high-performance text analytics in modern query engines <ref:2608. p. 023307#pg2>. The source code, data, and/or other artifacts have been made available at https://github. p. 0com/lamduynguyen/wildcard-join <ref:2608. p. 023307#pg2>.

REFERENCE RULES

The paper is 2608.23307v1 [cs. p. 0DB] 24 Aug 2026. p. 0 EVERY sentence must end with a reference token and the token names the page and quotes the words it rests on, copied word for word from that page N is the page number counting from 1 — the same N as that page's --- Page N --- line. Write the token BARE, with no backticks around it.

--- Page 1 ---

Teach Your DBMS to LIKE Strings: Fast and General Pattern Matching for Wildcard Joins and Filters<ref:2608.23307#pg2> The ubiquity of string data. p. 0 Modern applications heavily rely on strings as the catch-all data type for heterogeneous data <ref:2608. p. 023307#pg2> For example, in e-commerce platforms like Amazon, a product profile comprises a complex mix of string-based attributes, including <ref:2608. p. 023307#pg2> Product IDs, descriptions. p. 0<ref:2608.23307#pg2> Target customers, reviews, etc. p. 0<ref:2608.23307#pg2> Example: Product ID: B07PY42BRC<ref:2608. p. 023307#pg2> Review: This BrandA camera is better than BrandD<ref:2608. p. 023307#pg2> Business analysis<ref:2608. p. 023307#pg2> Filter:<ref:2608. p. 023307#pg2> WHERE Product. p. 0Desc LIKE %smart%<ref:2608.23307#pg2> Join: UserReviews u JOIN BrandDictionary b ON u. p. 0review LIKE '%' || b.name || '%'<ref:2608.23307#pg2> Wildcard filters<ref:2608. p. 023307#pg2> Text Pattern SQL engine Text relation Wildcard joins Pattern relation Inefficient nested loop join Figure 1: Deriving insights from text requires extensive pattern matching, which is typically performed using wildcard queries <ref:2608. p. 023307#pg2>

--- Page 2 ---

Primitives behind text analytics: Wildcards<ref:2608.23307#pg2> To perform these analyses, DBMSs rely heavily on string pattern matching In relational databases, this is often expressed using the SQL LIKE expression (e. p. 1g., WHERE review LIKE %smart%), as shown in Figure 1<ref:2608.23307#pg2> Two main operators associated with LIKE predicate: wildcard filters that scan text fields for a single, specific phrase (e. p. 1g., finding items containing smart – question (2)), and wildcard joins that match text data against a large set of target patterns, such as checking a review table against a dictionary of thousands of brand names (i.e., question (1) and (3) above)<ref:2608. p. 023307#pg2> Suboptimal wildcard processing in DBMSs. p. 1<ref:2608.23307#pg2> Consequently, current engines rely on computationally expensive execution strategies: They default to high-overhead interpreted evaluation for LIKE filters, and inefficient nested-loop execution for joins <ref:2608. p. 123307#pg2>

--- Page 3 ---

Contributions.<ref:2608.23307#pg2> Specifically, we make the following contributions:<ref:2608. p. 123307#pg2> • Efficient wildcard joins: We propose a novel execution strategy based on the Aho-Corasick algorithm [18], eliminating the expensive combination of nested-loop join structure and standard LIKE evaluations <ref:2608. p. 123307#pg2> The key innovation lies in the concept of positional constraints – how two wildcard metacharacters ’%’ and ’’ enforce space requirements between pattern literals <ref:2608. p. 123307#pg2> • Compiled wildcard filters: We exploit code compilation architectures to generate specialized code for LIKE predicate evaluation, eliminating the overhead of interpreting the pattern per tuple <ref:2608. p. 123307#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>.

--- Page 4 ---

Outline.<ref:2608.23307#pg2> Section 2 provides the necessary background on the LIKE predicate and its associated wildcard operations<ref:2608. p. 123307#pg2> Section 3 details our novel execution strategy for wildcard joins<ref:2608. p. 123307#pg2> Section 4 describes our compilationbased LIKE predicate evaluation method<ref:2608. p. 123307#pg2> Section 5 empirically evaluates the performance of both proposed techniques<ref:2608. p. 123307#pg2> Finally, Section 6 reviews related literature, and Section 7 concludes the paper<ref:2608. p. 123307#pg2>

--- Page 5 ---

Wildcard joins.<ref:2608.23307#pg2> Concept. p. 1<ref:2608.23307#pg2> Wildcard joins extend traditional string pattern matching to relational join operations<ref:2608. p. 123307#pg2> This approach allows users to dynamically add or update matching rules directly within the DBMSs, eliminating the need to constantly rewrite the SQL queries to adapt to new patterns<ref:2608. p. 123307#pg2> Wildcard joins: Sample query. p. 1<ref:2608.23307#pg2> Suppose we want to filter spam from the HackerNews dataset (c. p. 1f., Section 5. p. 11). By storing malicious patterns in a dedicated rule table – BlockLists(id, url pattern, category) – we can identify spam using the following query<ref:2608. p. 123307#pg2> Wildcard joins: Practical necessity. p. 2<ref:2608.23307#pg2> This flexible matching paradigm is highly valuable in many real-world applications <ref:2608. p. 223307#pg2> Wildcard joins: Challenges. p. 2<ref:2608.23307#pg2> As discussed, the pattern matching feature provided by wildcard joins is highly useful, but modern DBMSs handle them poorly<ref:2608. p. 223307#pg2> Neither sort-based (only suits orderbased queries) nor hash-based (only works for equi-join) strategies are suitable for wildcard joins; hence, query engines typically fall back to the nested loop joins plan for such scenarios, introducing significant overhead <ref:2608. p. 223307#pg2>

--- Page 6 ---

O(n2) LIKE evaluation<ref:2608.23307#pg2> Insight: Wildcard join is multi-pattern matching. p. 2<ref:2608.23307#pg2> We can drastically simplify the wildcard join by looking at the problem differently <ref:2608. p. 223307#pg2> Consider a simple case where all patterns are simple substring matches with the following format: '% substring %'<ref:2608.23307#pg2> Finding matches for a single text row across the this simple pattern table is a classic multi-pattern matching problem <ref:2608. p. 223307#pg2> Instead of checking patterns one by one, we can find all matching substrings simultaneously using the Aho-Corasick algorithm [18] <ref:2608. p. 323307#pg2> This observation suggests that the matching complexity can be reduced to O (T × lT + P × lP) <ref:2608. p. 323307#pg2> This raises an important question: Can we adapt this efficient, automaton-based approach to handle more complex wildcard patterns? p. 3 Doing so opens the door to formulating wildcard joins into the common two-phase join paradigm similar to hash joins: the build phase – the engine creates a global automaton – and the probe phase – matching the text against the pre-built automaton <ref:2608. p. 323307#pg2>

--- Page 7 ---

Idea: Positional constraints.<ref:2608.23307#pg2> To realize this two-phase join paradigm in the presence of wildcards (% and), we introduce the concept of positional constraints <ref:2608. p. 323307#pg2> We decompose complex patterns into segments and literals governed by these constraints, allowing the static literals to be indexed by the Aho-Corasick automaton for subsequent multi-pattern matching <ref:2608. p. 323307#pg2> This tokenization approach transforms the otherwise complex wildcard join into a highly efficient, greedy problem <ref:2608. p. 323307#pg2> The remaining problem reduces to verifying the internal structure of individual segments, specifically determining how to efficiently validate that the literals within a single segment satisfy the strict positional constraints imposed by the underscore wildcards <ref:2608. p. 323307#pg2> A novel single-pass automaton, termed matcher for brevity, is proposed to address Problem 1 by tracking relative offset states and using a fixed-size LRU cache to bound memory usage <ref:2608. p. 323307#pg2> The design ensures that the number of concurrently active partial states is strictly bounded under any adversarial input <ref:2608. p. 423307#pg2>

--- Page 8 ---

Possible problem: Memory usage of matcher automaton.<ref:2608.23307#pg2> To mitigate this challenge, our design exploits a key structural invariant that the number of concurrently active partial states is strictly bounded under any adversarial input <ref:2608. p. 423307#pg2> This property allows the matcher automaton to manage its active states using a fixed-size LRU cache, which is resized to match the segment’s bound whenever the matcher transitions to a new segment <ref:2608. p. 423307#pg2> The strict LRU eviction policy causes the automaton to naturally forget stale candidates as the text cursor advances, guaranteeing that memory consumption remains strictly bounded under any adversarial input <ref:2608. p. 423307#pg2>.

--- Page 9 ---

Theorem 3.1.<ref:2608.23307#pg2> At any text cursor position, the number of concurrently active partial states is at most the maximum combined length of any literal and its subsequent underscore gap <ref:2608. p. 423307#pg2> This bound is derived from analyzing the lifespan of a state as Lk + Wk, where Lk denotes the length of literal Lk and Wk represents the number of underscore wildcards between Lk and L(k+1) <ref:2608. p. 323307#pg2>

--- Page 10 ---

Text A (4 bytes) B<ref:2608.23307#pg2> Text cursor (byte = 0, CPIndex = 0)<ref:2608. p. 523307#pg2> Normal matcher<ref:2608. p. 523307#pg2> + delayed queue<ref:2608. p. 523307#pg2> Delayed matching queue in Section 3. p. 53 correctly calculates the offset invariant (δ) by buffering matched events <ref:2608. p. 523307#pg2>

--- Page 11 ---

Text 'A' matches literal 'A'.<ref:2608.23307#pg2> Offsettext=0; Offsetpattern=0<ref:2608. p. 323307#pg2> Partial match set: [δ = 0]<ref:2608. p. 523307#pg2>

--- Page 12 ---

Text cursor (byte = 4, CPIndex = 1)<ref:2608.23307#pg2> Pop 'A' from queue, insert into the state set<ref:2608.23307#pg2> Partial match set: [δ = 4 - 1 = 3]<ref:2608. p. 523307#pg2>

--- Page 13 ---

Text cursor (byte = 5, CPIndex = 2)<ref:2608.23307#pg2> Expect δ = 3, found δ = 3. p. 4<ref:2608.23307#pg2>

--- Page 14 ---

Text 'B' matches literal 'B'.<ref:2608.23307#pg2> Offsettext=5; Offsetpattern=2<ref:2608. p. 323307#pg2> Partial match set: [δ = 5 - 2 = 3]<ref:2608. p. 523307#pg2>

--- Page 15 ---

Text cursor (byte = 6, CPIndex = 3)<ref:2608.23307#pg2> Validation success<ref:2608. p. 423307#pg2>

--- Page 16 --…

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Optimized Wildcard Joins using Aho-Corasick: The new join algorithm based on this algorithm significantly reduces time complexity by eliminating nested loop join structures and achieving speedups of up to 30.6 times over baseline DuckDB and 114.75 times over UmbraBase for wildcard joins.

  2. Compiled Wildcard Filters: Leveraging code generation infrastructure, the approach generates specialized code for LIKE predicate evaluation, which reduces per-tuple runtime overhead and outperforms other baselines by at least 13.3 times in a filter-focused stress experiment.

  3. Handling Unicode Data in Pattern Matching: The solution employs delayed matching queue to correctly calculate the offset invariant when dealing with UTF-8 encoding, restoring the invariant that was broken by variable-width characters spanning multiple bytes.

  4. Efficient Query Compilation for Wildcard Filters: By treating patterns as compile time constants and generating specialized machine code, this approach eliminates the overhead of interpreting the pattern for every input tuple, leading to a reduction in dynamic function calls and memory accesses by roughly half per character comparison.

  5. Specialized Join/Filter Strategy Selection: The system can dynamically choose between a compiled filter or a wildcard join based on pattern count; using compiled filters for a few patterns, and wildcard joins for many leads to 7.2 times higher throughput at low pattern counts (p <= 4).

Sources

Related papers