✔ PASS Search & Retrieval task_054_Q54_fuzzy_levenshtein_length_pruning Scaled: 1M+ Records Ordered: Yes

Typo-Tolerant Search with Levenshtein Edit Distance & Length Bounds

Candidate Latency (1M Rows)

134.56 ms

(1.0x slower than golden)

Golden Latency (1M Rows)

133.79 ms

DuckDB in-memory engine

Underlying Data Volume

1,000,000 rows

22.9 MiB across 1 table

Evaluated Model

gemini-3.8-flash-low

Gen Latency: 8.9s

✔ Correctness Verified on 1M+ Records

Candidate SQL output matches ground truth golden query across all multiset rows and numeric tolerances (tol=1e-3). Zero data skew or anti-patterns detected on full dataset scale.

1. Analytical Significance & What It Means

Scenario & Frontier Trap

Business Scenario & Problem

Users frequently misspell search terms (e.g. 'postgre' -> 'postgresql'). Levenshtein distance counts insertions, deletions, and substitutions.

⚡ The Frontier Trap (Why LLMs Fail)

Computing Levenshtein distance on every catalog word is CPU intensive without pre-filtering on string length (ABS(len_a - len_b) <= max_distance).

Prompt / User Request Given to Model

Users frequently misspell search terms (e.g. 'postgre' -> 'postgresql'). Levenshtein distance counts insertions, deletions, and substitutions.

Execute the required analytical SQL calculation in DuckDB.
Expected output columns: keyword_id, keyword, edit_distance.
Results should be ordered as specified.

2. Underlying Tables, Row Counts & Data Volume

1 Tables (1,000,000 rows • 22.9 MiB)

Production-scale fixtures loaded into the isolated DuckDB sandbox with at least 1,000,000 records per table:

📊 catalog_keywords 1,000,000 rows 22.9 MiB Data Volume

keyword_id (INTEGER) keyword (VARCHAR)

Data Preview (showing sample rows from 1,000,000 total rows):

#	keyword_id	keyword
1	1	postgresql
2	2	postgres
3	3	postgress
4	4	python
5	5	javascript
6	5	postgresql
7	6	postgres
8	7	postgress
9	8	python
10	9	javascript
11	10	postgresql
12	11	postgres
13	12	postgress
14	13	python
15	14	javascript

3. Graphical Query Execution Plan & Cost Bottlenecks

Physical Operator Tree (DuckDB 2.0 Profiler)

Visual flowchart of the physical execution pipeline. Operators with high relative costs (≥ 20% of query runtime or heavy latency) are visually highlighted:

Pipeline Latency Distribution (Total Plan Time: 383.12 ms) Nodes consuming ≥ 20% of query runtime are highlighted with glowing borders

📐 PROJECTION 0.3%

Latency: 1.24 ms

Rows In/Out: 200,000

Data Vol: 5.34 MB

📁 Projections: ['#0', '__internal_...

⏳ ORDER_BY 5.8%

Latency: 22.22 ms

Rows In/Out: 200,000

Data Vol: 5.34 MB

📐 PROJECTION 0.5%

Latency: 2.01 ms

Rows In/Out: 200,000

Data Vol: 5.34 MB

📁 Projections: ['#0', '__internal_...

📐 PROJECTION 🔥 14.7% Cost

Latency: 56.14 ms

Rows In/Out: 200,000

Data Vol: 5.34 MB

📁 Projections: ['keyword_id', 'key...

🎯 FILTER 0.4%

Latency: 1.49 ms

Rows In/Out: 200,000

Data Vol: 3.81 MB

🔍 TABLE_SCAN 🔥 78.3% Cost

Latency: 300.03 ms

Rows In/Out: 200,000

Data Vol: 3.81 MB

📁 memory.main.catalog_keywords

Operator	Cost %	Latency	Processed Rows	Data Volume	Details / Table	Status
TABLE_SCAN	78.3%	300.03 ms	200,000	3.81 MB	memory.main.catalog_keywords	🔥 BOTTLENECK
PROJECTION	14.7%	56.14 ms	200,000	5.34 MB	Projections: ['keyword_id', 'keyword', 'edit_dis	🔥 BOTTLENECK
ORDER_BY	5.8%	22.22 ms	200,000	5.34 MB	-	Normal
PROJECTION	0.5%	2.01 ms	200,000	5.34 MB	Projections: ['#0', '__internal_compress_string_	Normal
FILTER	0.4%	1.49 ms	200,000	3.81 MB	-	Normal
PROJECTION	0.3%	1.24 ms	200,000	5.34 MB	Projections: ['#0', '__internal_decompress_strin	Normal

4. Queries Executed (Candidate vs Golden Ground Truth)

Beautified & Syntax Highlighted

SELECT keyword_id,
       keyword,
       levenshtein(keyword, 'posgresql') AS edit_distance
FROM catalog_keywords
WHERE abs(length(keyword) - length('posgresql')) <= 2
  AND levenshtein(keyword, 'posgresql') <= 2
ORDER BY edit_distance ASC;

-- Find keywords within edit distance <= 2 of search query 'posgresql'

SELECT keyword_id,
       keyword,
       levenshtein(keyword, 'posgresql') AS edit_distance
FROM catalog_keywords -- Pre-filter: word length cannot differ by more than max allowed edit distance (2)

WHERE abs(length(keyword) - length('posgresql')) <= 2
  AND levenshtein(keyword, 'posgresql') <= 2
ORDER BY edit_distance ASC;

CREATE TABLE catalog_keywords (keyword_id INT, keyword VARCHAR);


INSERT INTO catalog_keywords
VALUES (1, 'postgresql'),
       (2, 'postgres'),
       (3, 'postgress'),
       (4, 'python'),
       (5, 'javascript');

5. Query Results & Expected Ground Truth

Tabular Comparison

Actual Candidate Output (200,000 rows × 3 cols)

#	keyword_id	keyword	edit_distance
1	122,885	postgresql	1
2	122,890	postgresql	1
3	122,895	postgresql	1
4	122,900	postgresql	1
5	122,905	postgresql	1
6	122,910	postgresql	1
7	122,915	postgresql	1
8	122,920	postgresql	1
9	122,925	postgresql	1
10	122,930	postgresql	1
11	122,935	postgresql	1
12	122,940	postgresql	1
13	122,945	postgresql	1
14	122,950	postgresql	1
15	122,955	postgresql	1
16	122,960	postgresql	1
17	122,965	postgresql	1
18	122,970	postgresql	1
19	122,975	postgresql	1
20	122,980	postgresql	1
21	122,985	postgresql	1
22	122,990	postgresql	1
23	122,995	postgresql	1
24	123,000	postgresql	1
25	123,005	postgresql	1

Showing first 25 of 200,000 total rows.

Expected Golden Output (200,000 rows × 3 cols)

#	keyword_id	keyword	edit_distance
1	368,645	postgresql	1
2	368,650	postgresql	1
3	368,655	postgresql	1
4	368,660	postgresql	1
5	368,665	postgresql	1
6	368,670	postgresql	1
7	368,675	postgresql	1
8	368,680	postgresql	1
9	368,685	postgresql	1
10	368,690	postgresql	1
11	368,695	postgresql	1
12	368,700	postgresql	1
13	368,705	postgresql	1
14	368,710	postgresql	1
15	368,715	postgresql	1
16	368,720	postgresql	1
17	368,725	postgresql	1
18	368,730	postgresql	1
19	368,735	postgresql	1
20	368,740	postgresql	1
21	368,745	postgresql	1
22	368,750	postgresql	1
23	368,755	postgresql	1
24	368,760	postgresql	1
25	368,765	postgresql	1

Showing first 25 of 200,000 total rows.

← Prev: Min-Max Normalized Convex... ⊞ Back to Benchmark Dashboard Next: Brand & Name Fuzzy Search... →