--- title: "damerau_levenshtein" slug: "dev-database-reference-sql-functions-string-damerau-levenshtein" updated: 2026-10-30T18:18:56Z published: 2026-10-30T18:18:56Z canonical: "docs.vastdata.com/dev-database-reference-sql-functions-string-damerau-levenshtein" --- > ## Documentation Index > Fetch the complete documentation index at: https://docs.vastdata.com/llms.txt > Use this file to discover all available pages before exploring further. # damerau_levenshtein *Applies to VAST Cluster 5.5.* *[Functions](/develop/docs/dev-database-reference-sql-functions-index) › [Text basics](/develop/docs/dev-database-reference-sql-functions-string-text-basics) › Similarity.* Returns the Damerau-Levenshtein edit distance between two strings: like [levenshtein](/develop/docs/dev-database-reference-sql-functions-string-levenshtein), but swapping two neighbouring units counts as one edit, not two. It has no aliases. ## Syntax ``` damerau_levenshtein(a, b) ``` | Argument | Type | Description | | --- | --- | --- | | `a` | `VARCHAR` | The first string. | | `b` | `VARCHAR` | The string to compare it with. | **Returns:** `BIGINT`. **Aliases:** none. ## Set up the examples The examples connect with the ADBC driver, as in [VAST Query Engine (ADBC)](/develop/docs/dev-database-integrations-adbc), and work in a schema called `docs_sql_fn_damerau_levenshtein`. Set `QE_ENDPOINT`, `AWS_ACCESS_KEY_ID`, `AWS_SECRET_ACCESS_KEY` and `VASTDB_BUCKET` ([SQL reference](/develop/docs/dev-database-reference-sql-index#example-connect-and-use-a-transaction)), and run the blocks in order in one Python session. Below each block is the output you should see. This block connects, defines the `run()` and `plan()` helpers, and creates a table of product names as customers typed them into a search box. The last row has no value: ``` import os import re import adbc_driver_manager import adbc_driver_manager.dbapi as dbapi import adbc_driver_vastdb BUCKET = os.environ["VASTDB_BUCKET"] SCHEMA = f'"{BUCKET}/docs_sql_fn_damerau_levenshtein"' conn = dbapi.connect( driver=adbc_driver_vastdb.get_driver_path(), db_kwargs={ "vast.db.endpoint": os.environ["QE_ENDPOINT"], "vast.db.access_key": os.environ["AWS_ACCESS_KEY_ID"], "vast.db.secret_key": os.environ["AWS_SECRET_ACCESS_KEY"], }, autocommit=True, ) def server_message(e): """The server's message in a driver error, without the request ID or the echoed statement.""" text = re.sub(r"\[req=0x[0-9a-f]+\]: ", "", str(e)) found = (re.search(r'message: "(.*?)", request_id', text, re.S) or re.search(r"description: (.*)\)", text, re.S)) message = found.group(1) if found else text.strip().splitlines()[-1] message = re.sub(r"^Plan query: '.*?' failed with: ", "", message, flags=re.S) message = re.split(r"\\n|\n", message)[0].replace('\\"', '"') return message.replace(BUCKET, "") def run(sql): """Run one statement. Print the rows it returns, or the error.""" try: with conn.cursor() as cur: cur.execute(sql) rows = cur.fetchall() if cur.description else [] except (adbc_driver_manager.Error, OSError) as e: print(f"{type(e).__name__}: {server_message(e)}") else: print(rows) def plan(sql): """Print the plan without its ~N Rows lines: the table's row count, which can still be 0 just after an insert.""" with conn.cursor() as cur: cur.execute("EXPLAIN " + sql) steps = cur.fetchall()[0][1] print("\n".join(line for line in steps.splitlines() if "Rows" not in line)) TABLE = f"{SCHEMA}.searches" run(f"CREATE SCHEMA IF NOT EXISTS {SCHEMA}") run(f"CREATE TABLE IF NOT EXISTS {TABLE} (id BIGINT, term VARCHAR)") run(f"INSERT INTO {TABLE} VALUES " "(1, 'keyboard'), " "(2, 'keybaord'), " "(3, 'kyeboard'), " "(4, 'keyborad'), " "(5, 'monitor'), " "(6, NULL)") ``` ``` [] [] [(6,)] ``` ## What it does `damerau_levenshtein` counts the edits needed to turn `a` into `b`. Each edit costs 1 and is one of: - inserting one unit, - deleting one unit, - replacing one unit with another, - swapping two neighbouring units (a transposition). The last kind is what makes it different from [levenshtein](/develop/docs/dev-database-reference-sql-functions-string-levenshtein), which needs two substitutions for a swap. That suits typing mistakes such as `teh` for `the`. | Call | Result | Why | | --- | --- | --- | | `damerau_levenshtein('ab', 'ba')` | `1` | one swap (`levenshtein` gives `2`) | | `damerau_levenshtein('abcd', 'acbd')` | `1` | the swapped pair is in the middle | | `damerau_levenshtein('ca', 'abc')` | `2` | swap to `ac`, then insert `b` between the swapped characters | | `damerau_levenshtein('', 'ab')` | `2` | against an empty string, the distance is the length of the other string | | `damerau_levenshtein('kitten', 'sitting')` | `3` | no swaps help, so it's the same as `levenshtein` | **It compares UTF-8 bytes, not characters**, as [levenshtein](/develop/docs/dev-database-reference-sql-functions-string-levenshtein#what-it-does) does: a letter outside ASCII takes two or more bytes, and each byte is edited on its own. The string `'e\u0301 🇫🇷 ẞ'` is 7 code points but 16 bytes, and its distance from `'Hlelo'` is `16`. With a precomposed `é` (two bytes), `damerau_levenshtein('café', 'cafe')` is `2`, not `1`, and `damerau_levenshtein('é', 'è')` is `1`, because only the second bytes differ. To compare accented text by letters, remove the accents first with [strip_accents](/develop/docs/dev-database-reference-sql-functions-string-strip-accents). ## NULLs and edge cases | Input | Result | | --- | --- | | `NULL` as either argument | `NULL` | | `''` and `'Hlelo'` | `5` | | `'ab'` and `'ba'` | `1` | | `'ca'` and `'abc'` | `2` | | `'e\u0301 🇫🇷 ẞ'` and `'Hlelo'` | `16` | | A number, decimal, date, boolean, `BLOB` or list | Error: `No function matches the given name and argument types` | The same cases, as the cluster returns them. They use the table and helpers from [Set up the examples](/develop/docs/dev-database-reference-sql-functions-string-damerau-levenshtein#set-up-the-examples): ``` run("SELECT damerau_levenshtein(NULL, 'Hlelo'), damerau_levenshtein('a', NULL), " "damerau_levenshtein('', 'Hlelo'), damerau_levenshtein('ab', 'ba'), damerau_levenshtein('ca', 'abc')") run("SELECT damerau_levenshtein('e\u0301 🇫🇷 ẞ', 'Hlelo')") run("SELECT damerau_levenshtein(123, 'Hlelo')") ``` ``` [(None, None, 5, 1, 2)] [(16,)] InternalError: Binder Error: No function matches the given name and argument types 'damerau_levenshtein(INTEGER_LITERAL, STRING_LITERAL)'. You might need to add explicit type casts. ``` ## Examples Each search term against the product name `keyboard`, with both distances. Each of rows 2 to 4 has two neighbouring letters swapped: one edit for `damerau_levenshtein`, two for `levenshtein`: ``` run(f"SELECT id, term, damerau_levenshtein(term, 'keyboard'), levenshtein(term, 'keyboard') " f"FROM {TABLE} ORDER BY id LIMIT 10") ``` ``` [(1, 'keyboard', 0, 0), (2, 'keybaord', 1, 2), (3, 'kyeboard', 1, 2), (4, 'keyborad', 1, 2), (5, 'monitor', 7, 7), (6, None, None, None)] ``` Keep the searches that are at most one typing mistake away from `keyboard`: ``` run(f"SELECT id, term FROM {TABLE} WHERE damerau_levenshtein(term, 'keyboard') <= 1 ORDER BY id LIMIT 10") ``` ``` [(1, 'keyboard'), (2, 'keybaord'), (3, 'kyeboard'), (4, 'keyborad')] ``` ## How it runs in VAST The Query Engine runs on the cluster's CNodes, and a query on a table starts with a scan in VAST DataBase (`VAST_SCAN`). VAST DataBase can evaluate a comparison of a column with a constant, but not a function of a column, so `damerau_levenshtein()` is always computed by the Query Engine: - **In the `SELECT` list,** the scan reads the column and the Query Engine computes `damerau_levenshtein()` for each row it returns. - **In `WHERE`,** the scan sends the column for every row, and a `FILTER` step in the Query Engine computes `damerau_levenshtein()` and keeps the rows that match. No rows are skipped in storage. The plan of the `WHERE` example shows the `FILTER` step above the scan: ``` plan(f"SELECT id FROM {TABLE} WHERE damerau_levenshtein(term, 'keyboard') <= 1") ``` ``` ┌───────────────────────────┐ │ PROJECTION │ │ ──────────────────── │ │ #1 │ │ │ └─────────────┬─────────────┘ ┌─────────────┴─────────────┐ │ FILTER │ │ ──────────────────── │ │ (damerau_levenshtein(term,│ │ 'keyboard') <= 1) │ │ │ └─────────────┬─────────────┘ ┌─────────────┴─────────────┐ │ VAST_SCAN │ │ ──────────────────── │ │ Function: VAST_SCAN │ │ │ │ Projections: │ │ term │ │ id │ │ │ └───────────────────────────┘ ``` ## Make it faster - **Narrow the rows with a pushed-down condition first.** A comparison of a raw column with a constant is evaluated in VAST DataBase, so only the rows that pass it reach `damerau_levenshtein()`. In `id > 100 AND damerau_levenshtein(term, 'keyboard') <= 1`, `id > 100` is evaluated in storage. - **Look up exact matches without it.** `term = 'keyboard'` is pushed down; `damerau_levenshtein(term, 'keyboard') = 0` gives the same rows but runs on every row. The plan for `term = 'keyboard'` has no `FILTER` step: ``` plan(f"SELECT id FROM {TABLE} WHERE term = 'keyboard'") ``` ``` ┌───────────────────────────┐ │ VAST_SCAN │ │ ──────────────────── │ │ Function: VAST_SCAN │ │ Projections: id │ │ │ └───────────────────────────┘ ``` ## Limitations and errors - **Strings only.** A number, decimal, date, boolean, `BLOB` or list fails with `No function matches the given name and argument types`. Cast it first: `damerau_levenshtein(CAST(n AS VARCHAR), '123')`. - **Bytes, not characters.** Accented and other non-ASCII letters count as more than one unit. See [What it does](/develop/docs/dev-database-reference-sql-functions-string-damerau-levenshtein#what-it-does). - **Case-sensitive.** `damerau_levenshtein('Keyboard', 'keyboard')` is `1`. To ignore case, compare `lower()` of both strings. This block compares `'Keyboard'` with and without `lower()`: ``` run("SELECT damerau_levenshtein(123, 'Hlelo')") run("SELECT damerau_levenshtein('Keyboard', 'keyboard'), damerau_levenshtein(lower('Keyboard'), 'keyboard')") ``` ``` InternalError: Binder Error: No function matches the given name and argument types 'damerau_levenshtein(INTEGER_LITERAL, STRING_LITERAL)'. You might need to add explicit type casts. [(1, 0)] ``` ## Similar functions | Function | Measures | `'ab'` and `'ba'` | `'kitten'` and `'sitting'` | | --- | --- | --- | --- | | `damerau_levenshtein` | edit distance; a swap of neighbours is one edit | `1` | `3` | | [levenshtein](/develop/docs/dev-database-reference-sql-functions-string-levenshtein) (also `editdist3`) | edit distance; a swap is two edits | `2` | `3` | | [jaccard](/develop/docs/dev-database-reference-sql-functions-string-jaccard) | distinct bytes the strings share, as a share of all their distinct bytes, from 0 to 1; order is ignored | `1.0` | `0.42857142857142855` | | [jaro_similarity](/develop/docs/dev-database-reference-sql-functions-string-jaro-similarity) | similarity from 0 to 1, based on matching bytes and transpositions | (see its page) | `0.746031746031746` | | [hamming](/develop/docs/dev-database-reference-sql-functions-string-hamming) | byte positions that differ; the strings must be the same length in bytes | (see its page) | `2` (for `'kitten'` and `'sittin'`) | ``` run("SELECT damerau_levenshtein('ab', 'ba'), levenshtein('ab', 'ba'), jaccard('ab', 'ba')") run("SELECT damerau_levenshtein('kitten', 'sitting'), levenshtein('kitten', 'sitting'), " "jaccard('kitten', 'sitting'), jaro_similarity('kitten', 'sitting'), hamming('kitten', 'sittin')") ``` ``` [(1, 2, 1.0)] [(3, 3, 0.42857142857142855, 0.746031746031746, 2)] ``` Clean up: ``` run(f"DROP TABLE IF EXISTS {TABLE}") run(f"DROP SCHEMA IF EXISTS {SCHEMA}") conn.close() ``` ``` [] [] ``` ## See also - [Text basics](/develop/docs/dev-database-reference-sql-functions-string-text-basics): all the text functions. - [Where filters run](/develop/docs/dev-database-reference-sql-select#where-filters-run) and [pushdowns](/develop/docs/dev-database-reference-pushdowns). - [EXPLAIN](/develop/docs/dev-database-reference-sql-explain): how to read a plan. - [levenshtein](/develop/docs/dev-database-reference-sql-functions-string-levenshtein) and [jaro_winkler_similarity](/develop/docs/dev-database-reference-sql-functions-string-jaro-winkler-similarity).