---
title: "levenshtein"
slug: "dev-database-reference-sql-functions-string-levenshtein"
updated: 2026-10-30T18:18:56Z
published: 2026-10-30T18:18:56Z
canonical: "docs.vastdata.com/dev-database-reference-sql-functions-string-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.

# 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 Levenshtein edit distance between two strings: the smallest number of single-unit insertions, deletions and substitutions that turn one string into the other. `editdist3` is the same function.

## Syntax

```
levenshtein(a, b)
editdist3(a, b)
```

| Argument | Type | Description |
| --- | --- | --- |
| `a` | `VARCHAR` | The first string. |
| `b` | `VARCHAR` | The string to compare it with. |

**Returns:** `BIGINT`.

**Aliases:** `editdist3`.

## 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_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 five people. The last row has no name:

```
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_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, "<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}.people"
run(f"CREATE SCHEMA IF NOT EXISTS {SCHEMA}")
run(f"CREATE TABLE IF NOT EXISTS {TABLE} (id BIGINT, name VARCHAR)")
run(f"INSERT INTO {TABLE} VALUES "
    "(1, 'Grace Hopper'), "
    "(2, 'Ada Lovelace'), "
    "(3, 'Alan Turing'), "
    "(4, 'grace hopper'), "
    "(5, NULL)")
```

```
[]
[]
[(5,)]
```

## What it does

`levenshtein` counts the edits needed to turn `a` into `b`. Each edit inserts one unit, deletes one unit or replaces one unit with another; every edit costs 1. A result of `0` means the strings are equal.

| Call | Result | Why |
| --- | --- | --- |
| `levenshtein(&apos;kitten&apos;, &apos;sitting&apos;)` | `3` | k→s, e→i, insert g |
| `levenshtein(&apos;&apos;, &apos;abc&apos;)` | `3` | three insertions: against an empty string, the distance is the length of the other string |
| `levenshtein(&apos;ab&apos;, &apos;ba&apos;)` | `2` | two substitutions: swapping two neighbours counts as two edits (use [damerau_levenshtein](/develop/docs/dev-database-reference-sql-functions-string-damerau-levenshtein) to count it as one) |
| `levenshtein(&apos;ab&apos;, &apos;AB&apos;)` | `2` | the comparison is case-sensitive: `a` and `A` are different |
| `levenshtein(repeat(&apos;a&apos;, 1000), repeat(&apos;b&apos;, 1000))` | `1000` | long strings work |

**It compares UTF-8 bytes, not characters.** An unaccented ASCII letter is one byte, so for ASCII text the result is the number of character edits. A letter outside ASCII takes two or more bytes, and each byte is edited on its own:

| Call | Result | Why |
| --- | --- | --- |
| `levenshtein(&apos;caf&#xe9;&apos;, &apos;cafe&apos;)` | `2` | `&#xe9;` is two bytes; replacing it with `e` is one substitution and one deletion |
| `levenshtein(&apos;e\u0301&apos;, &apos;&#xe9;&apos;)` | `3` | the decomposed form (`e` followed by U+0301, three bytes) shares no byte with the precomposed `&#xe9;` (two bytes) |
| `levenshtein(&apos;e\u0301&apos;, &apos;e&apos;)` | `2` | the combining accent U+0301 is two bytes, so deleting it is two edits |
| `levenshtein(&apos;&#xe9;&apos;, &apos;&#xe8;&apos;)` | `1` | both are precomposed and two bytes long, and only their 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), or bring both strings to the same form with [nfc_normalize](/develop/docs/dev-database-reference-sql-functions-string-nfc-normalize).

## NULLs and edge cases

| Input | Result |
| --- | --- |
| `NULL` as either argument | `NULL` |
| `&apos;&apos;` and `&apos;Hallo&apos;` | `5` |
| `&apos;kitten&apos;` and `&apos;sitting&apos;` | `3` |
| `&apos;ab&apos;` and `&apos;AB&apos;` | `2` |
| `&apos;caf&#xe9;&apos;` and `&apos;cafe&apos;` | `2` |
| `&apos;e\u0301&apos;` and `&apos;&#xe9;&apos;` | `3` |
| 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-levenshtein#set-up-the-examples):

```
run("SELECT levenshtein(NULL, 'Hallo'), levenshtein('a', NULL), levenshtein('', 'Hallo'), "
    "levenshtein('kitten', 'sitting'), editdist3('kitten', 'sitting')")
run("SELECT levenshtein('ab', 'AB'), levenshtein('café', 'cafe'), levenshtein('e\u0301', '\u00e9')")
run("SELECT levenshtein(123, 'Hallo')")
```

```
[(None, None, 5, 3, 3)]
[(2, 2, 3)]
InternalError: Binder Error: No function matches the given name and argument types 'levenshtein(INTEGER_LITERAL, STRING_LITERAL)'. You might need to add explicit type casts.
```

## Examples

The distance from each name to a misspelt search term, `Grace Hoper`. Row 1 is one edit away; row 4 differs in case as well, so it's further:

```
run(f"SELECT id, name, levenshtein(name, 'Grace Hoper') FROM {TABLE} ORDER BY id LIMIT 10")
```

```
[(1, 'Grace Hopper', 1), (2, 'Ada Lovelace', 10), (3, 'Alan Turing', 10), (4, 'grace hopper', 3), (5, None, None)]
```

Find the names within two edits of the search term, ignoring case by comparing [lower](/develop/docs/dev-database-reference-sql-functions-string-lower) of both strings:

```
run(f"SELECT id, name FROM {TABLE} "
    "WHERE levenshtein(lower(name), lower('Grace Hoper')) <= 2 ORDER BY id LIMIT 10")
```

```
[(1, 'Grace Hopper'), (4, 'grace hopper')]
```

The closest name first, with `editdist3`, which is the same function:

```
run(f"SELECT name, editdist3(name, 'Alan Turnig') AS distance FROM {TABLE} "
    "WHERE name IS NOT NULL ORDER BY distance, id LIMIT 1")
```

```
[('Alan Turing', 2)]
```

## 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 `levenshtein()` is always computed by the Query Engine:

- **In the `SELECT` list,** the scan reads the column and the Query Engine computes `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 `levenshtein()` and keeps the rows that match. No rows are skipped in storage.

The plan of a distance filter shows the `FILTER` step above the scan:

```
plan(f"SELECT id FROM {TABLE} WHERE levenshtein(name, 'Grace Hoper') <= 1")
```

```
┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│             #1            │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│ (levenshtein(name, 'Grace │
│        Hoper') <= 1)      │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         VAST_SCAN         │
│    ────────────────────   │
│    Function: VAST_SCAN    │
│                           │
│        Projections:       │
│            name           │
│             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 `levenshtein()`. In `id &gt; 100 AND levenshtein(name, &apos;Grace Hoper&apos;) &lt;= 2`, `id &gt; 100` is evaluated in storage.
- **Use a stored length as a cheap bound.** Each edit changes the length by at most one byte, so two strings whose byte lengths differ by more than `k` are always more than `k` edits apart. If you store [strlen](/develop/docs/dev-database-reference-sql-functions-string-strlen) of the name in its own column when you write the rows, in `name_bytes BETWEEN 9 AND 13 AND levenshtein(name, &apos;Grace Hoper&apos;) &lt;= 2` the length condition compares a raw column with constants, so `levenshtein()` runs only on the rows of a suitable length.
- **Look up exact matches without it.** `name = &apos;Grace Hopper&apos;` is pushed down; `levenshtein(name, &apos;Grace Hopper&apos;) = 0` gives the same rows but runs on every row. The plan for `name = &apos;Grace Hopper&apos;` has no `FILTER` step:

```
plan(f"SELECT id FROM {TABLE} WHERE name = 'Grace Hopper'")
```

```
┌───────────────────────────┐
│         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: `levenshtein(CAST(n AS VARCHAR), &apos;123&apos;)`.
- **Two arguments only.** There's no argument for a maximum distance or for the cost of each kind of edit: `levenshtein(&apos;a&apos;, &apos;b&apos;, 1)` fails with `No function matches the given name and argument types`.
- **Bytes, not characters.** Accented and other non-ASCII letters count as more than one edit. See [What it does](/develop/docs/dev-database-reference-sql-functions-string-levenshtein#what-it-does).
- **Case-sensitive.** Compare `lower()` of both strings to ignore case.
- **Other SQL dialects' names aren't available.** `soundex` and `similarity` fail with `Scalar Function with name ... does not exist!`. Use `levenshtein`, or a similarity score from [Similar functions](/develop/docs/dev-database-reference-sql-functions-string-levenshtein#similar-functions).

```
run("SELECT levenshtein('a', 'b', 1)")
run("SELECT soundex('Robert')")
run("SELECT similarity('ab', 'ab')")
```

```
InternalError: Binder Error: No function matches the given name and argument types 'levenshtein(STRING_LITERAL, STRING_LITERAL, INTEGER_LITERAL)'. You might need to add explicit type casts.
InternalError: Catalog Error: Scalar Function with name soundex does not exist!
InternalError: Catalog Error: Scalar Function with name similarity does not exist!
```

## Similar functions

| Function | Measures | Result for `&apos;kitten&apos;` and `&apos;sitting&apos;` (`levenshtein` gives `3`) |
| --- | --- | --- |
| [damerau_levenshtein](/develop/docs/dev-database-reference-sql-functions-string-damerau-levenshtein) | edit distance where swapping two neighbours is one edit | `3` |
| [hamming](/develop/docs/dev-database-reference-sql-functions-string-hamming) | byte positions that differ; the strings must be the same length in bytes | `2` (for `&apos;kitten&apos;` and `&apos;sittin&apos;`) |
| [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 | `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 | `0.746031746031746` |
| [jaro_winkler_similarity](/develop/docs/dev-database-reference-sql-functions-string-jaro-winkler-similarity) | Jaro similarity with extra weight for a common prefix | `0.746031746031746` |

`levenshtein` and `damerau_levenshtein` return a count of edits (lower is closer); `jaccard` and the Jaro functions return a score (higher is closer).

```
run("SELECT levenshtein('kitten', 'sitting'), damerau_levenshtein('kitten', 'sitting'), "
    "hamming('kitten', 'sittin'), jaccard('kitten', 'sitting'), "
    "jaro_similarity('kitten', 'sitting'), jaro_winkler_similarity('kitten', 'sitting')")
```

```
[(3, 3, 2, 0.42857142857142855, 0.746031746031746, 0.746031746031746)]
```

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.
- [damerau_levenshtein](/develop/docs/dev-database-reference-sql-functions-string-damerau-levenshtein), [strip_accents](/develop/docs/dev-database-reference-sql-functions-string-strip-accents) and [lower](/develop/docs/dev-database-reference-sql-functions-string-lower).