@Rocky Title: Fuzzy string join at scale — can

ngram_search

ever avoid a NESTLOOP, or is n-gram blocking the intended pattern? StarRocks 4.1.3 shared-data. Goal. Match company names between two large sets, roughly one million distinct names on each side . The names are not equal, only similar (

crossbeam

vs

crosbeam inc

), so an equijoin is not available. What I tried.

ngram_search

as the join condition, symmetrised because the function is directional:

SELECT a.nm, b.nm
FROM a JOIN b
  ON LEAST(ngram_search(a.nm, b.nm, 2), ngram_search(b.nm, a.nm, 2)) >= 0.70;

`EXPLAIN`:

7:NESTLOOP JOIN
   join op: INNER JOIN
   other join predicates: least(ngram_search(25, 54, 2), ngram_search(54, 25, 2)) >= 0.7

No

equal join conjunct

, and both inputs arrive

UNPARTITIONED

. The equivalent equality join over the same two tables plans as expected:

10:HASH JOIN
   join op: INNER JOIN (PARTITIONED)
   equal join conjunct: 25: sanitized_name = 54: sanitized_name

So the similarity version is a cross product: one million against one million is 10^12 evaluations, well beyond our CPU budget for a single query. Moving the predicate to a

WHERE

changes nothing, since the rows being filtered are the pairs. On the input being computed. The columns above are stored physical columns, chosen deliberately to isolate the join behaviour. Our real query compares a derived value, a legal-suffix strip applied at query time, because we cannot add a column to the source table:

ON LEAST(ngram_search(strip(a.name), strip(b.name), 2),
         ngram_search(strip(b.name), strip(a.name), 2)) >= 0.70

The nested loop appears either way, which suggests the plan is driven by the predicate shape rather than by the input being computed. I would like that reading confirmed. The workaround I have. Explode each name into overlapping 4-character chunks, join on chunk equality (which restores the hash join), require 3 or more shared chunks, drop chunks appearing in over 0.5% of names to control skew, then apply

ngram_search

as a filter on the survivors. Measured on our data this preserves recall in the bulk length bands and reduces the pair count by roughly six orders of magnitude. Questions. 1. Is there any plan shape or hint that lets

ngram_search

drive a join without materialising the cross product, or is a nested loop unavoidable by design for a predicate that takes a column from each side? 2. Does the N-Gram bloom filter index apply only to a constant needle (

ngram_search(col, 'literal')

), or can it accelerate

ngram_search(col_a, col_b)

across a join? The documentation reads as constant-only and I would like to confirm before ruling it out. 3. An index needs a materialised column, and our compared value is computed at query time. Is there a way to index a derived expression, for example a generated column or an expression index? And given the answer to question 2, would that change anything? 4. Is n-gram blocking the recommended pattern for a fuzzy join at this scale, or is there something more native I have missed? I looked at the inverted index with

MATCH

, but that is tokenised full-text search and would not pair

crosbeam

with

crossbeam

. 5. Is a native fuzzy-join or similarity-index primitive on the roadmap? Thanks!

The behavior you are seeing is expected for StarRocks 4.1.3. Here are the answers to your specific questions regarding the optimization of fuzzy joins: 1. Can

ngram_search

ever avoid a NESTLOOP? No. In StarRocks, a Hash Join (the performant alternative to a Nested Loop) requires at least one equality join conjunct (e.g.,

a.id = b.id

). Since

ngram_search

returns a

DOUBLE

similarity score and your join condition uses a range predicate (

>= 0.70

), the Cost-Based Optimizer (CBO) has no way to build a hash table for the join. It is forced to evaluate the predicate for every possible pair, resulting in the $10^{12}$ evaluations you observed. 2. Does the N-Gram Bloom Filter accelerate column-to-column joins? No. The N-gram Bloom Filter index is designed specifically to accelerate needle-in-a-haystack queries where one side is a constant. * Documentation limit: The index is triggered when the

needle

(the pattern) is a constant literal. * Join behavior: In a join, both inputs are dynamic. StarRocks cannot use a Bloom Filter to "filter" one table against another during the join phase in the way it does during a single-table scan. The index only helps to "filter out data with a similarity of 0" during a table scan when compared against a literal. 3. Can you index a derived expression? Yes. StarRocks supports Generated Columns (v3.1+), which are the recommended way to handle your

strip(name)

requirement. * Implementation: You can add a generated column to your table:

sql
    ALTER TABLE a ADD COLUMN stripped_nm VARCHAR AS strip(nm);

* Indexing: You can then create an N-gram Bloom Filter index on

stripped_nm

. * The Catch: While this removes the CPU overhead of computing

strip()

at query time, it will not solve the Nested Loop problem. The join remains a similarity join without an equality condition, so it will still be $O(N \times M)$. 4. Is "N-Gram Blocking" the recommended pattern? Yes. Your workaround—exploding names into n-gram "tokens," joining on those tokens to find candidates, and then refining with `ngram_search`—is the standard "blocking" pattern for similarity joins at scale in StarRocks. * Why it works: It introduces the

equal join conjunct

(on the chunk/token) that the optimizer needs to trigger a Shuffled Hash Join. * Refinement: To further optimize this, consider using a Inverted Index (v3.3+) with the

MATCH

function if your similarity can be redefined as "sharing enough words/tokens," though for character-level fuzziness (

crosbeam

vs

crossbeam

), your 4-char chunking strategy is more robust. 5. Is a native fuzzy-join primitive on the roadmap? There is currently no publicly documented "native similarity join" operator (like a specialized LSH-based join) on the immediate roadmap. The engineering focus has been on Inverted Indexes and Vector Search (v3.4+) to handle similarity. Recommendation: * Stick with your Blocking Workaround. It is the most performant way to scale fuzzy matching to 1M x 1M records. * Use Generated Columns to persist the "stripped" or "tokenized" versions of your names. This allows you to build standard indexes or inverted indexes on the pre-processed strings, significantly reducing the work done during the join. * If you can move to a token-based approach, the Inverted Index with

MATCH

is the most "native" high-scale search feature available. References • sql-reference/sql-statements/generated_columns.md • knowledge/usage/best-practice.md • sql-reference/sql-statements/table_bucket_part_index/ALTER_TABLE.md

@Rocky In such scenario, if I decide to go for

jaro-winkler

instead of

ngram_search

, do I still need the

N-gram blocking

similar pattern? Will it be easier to get the

jaro-winkler

set up done and then do fuzzy name company matching based on jaro instead of ngram?

Yes, you still absolutely need the blocking pattern. Switching to

jaro_winkler_similarity

(or any other edit-distance/similarity function) does not solve the fundamental architectural challenge of a fuzzy join at this scale. Here is why: 1. The "Equality Conjunct" Problem The StarRocks optimizer requires an equality condition (e.g.,

a.col = b.col

) to trigger a Hash Join. * Both

ngram_search

and

jaro_winkler_similarity

are scalar functions that output a similarity score. * A condition like

ON jaro_winkler_similarity(a.nm, b.nm) >= 0.8

is a range predicate, not an equality. * Without an equality condition, the engine must perform a Nested Loop Join, resulting in the same $10^{12}$ comparisons you encountered with N-grams. 2. Indexing Limitations StarRocks has specialized N-gram Bloom Filter indexes that can (in very specific scenarios) accelerate

ngram_search

. It does not have a native index structure designed to accelerate

jaro_winkler_similarity

for column-to-column joins. * With

jaro_winkler

, you lose even the theoretical possibility of the engine using a built-in index to "skip" rows during the cross-product. * The compute cost of Jaro-Winkler is generally higher than N-gram similarity because it involves complex character-distance calculations that are harder to vectorize than simple N-gram intersections. 3. Is it "Easier" to Set Up? It is not easier because the "setup" difficulty in StarRocks isn't the function itself, but the Join Strategy. * Jaro-Winkler: You still have no way to avoid the $O(N \times M)$ complexity natively. You would still need to build your own "blocking" mechanism (like Phonetic keys/Soundex or N-gram chunks) to generate candidate pairs before applying Jaro-Winkler as a final filter. * N-gram: Actually has better "native" alignment if you use the Inverted Index (GIN). In recent versions (3.3+), you can use

MATCH

against an inverted index, which is the closest thing to a native candidate generator. Comparison Summary Feature |

ngram_search

|

jaro_winkler_similarity

Join Type | Nested Loop (Cross Product) | Nested Loop (Cross Product) Native Index Support | N-gram Bloom Filter (limited) | None Computational Cost | Moderate (Vectorized) | Higher (Complex distance logic) Best For | Typos, substrings, technical IDs | Human names, short strings Blocking Required? | Yes | Yes Recommendation Stay with your N-gram blocking pattern. It is the standard industry "best practice" for similarity joins in distributed databases. To make it more "native," you can leverage Generated Columns (v3.1+) to handle the name stripping and tokenization. This moves the "setup" work into the table schema: 1. Generated Column: Create a column

name_tokens

that stores the array of 4-char chunks. 2. Inverted Index: Create an inverted index on that array. 3. Join: Join on the exploded tokens (your current workaround), which will now be significantly faster because the tokens are pre-computed and indexed. Conclusion: Jaro-Winkler is just a different way to measure the "final" score; it provides no shortcut to bypass the massive compute requirement of a $10^6 \times 10^6$ join. References • sql-reference/sql-functions/string-functions/ngram_search.md • table_design/indexes/Ngram_Bloom_Filter_Index.md • table_design/indexes/inverted_index.md

@Rocky can we do

ngram_search

or

jaro-winkler

without a range predicate (somehow without doing blocking), whats the importance of having range in such scenarios where we are doing fuzzy name matching for company names that too on huge dataset?

You cannot effectively perform fuzzy matching on a large dataset without either a range predicate (the threshold) or a Top-K limit, and you certainly cannot avoid "blocking" (or some indexing equivalent) if you want the query to finish. Here is the breakdown of why the range is there and why removing it doesn't solve the performance problem. 1. The Mathematical Role of the Range Similarity is not binary. Unlike an equality join (

A = B

), where a row either matches or doesn't, fuzzy matching is a spectrum. * Without a range predicate: If you just joined on

ngram_search(a.nm, b.nm)

, the database wouldn't know which pairs to keep. Every single row in Table A would "match" every single row in Table B, just with varying scores (most being 0.0). * The Result: For your $10^6 \times 10^6$ tables, you would get a result set of 1 trillion rows. The range predicate (

>= 0.7

) is the only thing preventing a storage/network explosion. 2. The Performance "Importance" of the Range In StarRocks, the range predicate itself is actually the filter, not the join mechanism. * The Problem: The reason your query is slow isn't the

> 0.7

. It's that the engine has to compute the score for all 1 trillion pairs to find which ones meet that

> 0.7

criteria. * The "No Range" Scenario: If you removed the range and just did

SELECT a.nm, b.nm, ngram_search(a.nm, b.nm) as score FROM a, b

, the performance would actually be worse because now the database has to materialize and return all 1 trillion scores instead of just the ones that pass the filter. 3. Can you do this without Blocking? The only way to avoid "Blocking" (manually creating tokens to join on) while maintaining performance is to use a Similarity Index that the database understands. In StarRocks, there are two native ways to do this without manual blocking, but they require a different setup: A. Vector Search (The Modern Alternative) If you transform your company names into "embeddings" (vectors) using a model (like BERT or even a simple character-level TF-IDF vector), you can use StarRocks Vector Index (HNSW). * How it avoids the range: You can query for the "Top 5 most similar names" using

ORDER BY approx_l2_distance(...) LIMIT 5

. * How it avoids the Nested Loop: The HNSW index allows the database to find those 5 names in logarithmic time ($O(\log N)$) rather than scanning the whole table ($O(N)$). * Trade-off: You have to pre-calculate vectors and store them in a specialized

VECTOR

column. B. Full-Text Inverted Index (GIN) with

MATCH

If you use the Inverted Index with the

MATCH

function, you are technically doing "token-based similarity." * The Difference: This is essentially "Internal Blocking." The database handles the explosion of tokens for you and uses a bitmap to find rows that share enough tokens. * Limitation: As noted previously, this is better for words than for character-level typos (like

crosbeam

vs

crossbeam

). Summary: Why you can't escape the logic 1. Logic: You need the Range to define what a "match" is. Without it, everything matches everything. 2. Performance: You need Blocking (or an Index) because the computer cannot "guess" which strings are similar without looking at them. To look at $10^6 \times 10^6$ pairs, it has to do $10^{12}$ operations. 3. Optimization: The only way to skip those $10^{12}$ operations is to have a "lookup" (Hash Join or Index) that points directly to potential candidates. Since

ngram_search

doesn't have a "lookup table" for every possible typo, your manual blocking strategy (the 4-char chunks) is effectively creating that lookup table yourself. The Verdict: Stick to the blocking pattern. It is the most transparent and controllable way to handle fuzzy joins at this specific scale. References • best_practices/query_tuning/query_hint.md